=Paper=
{{Paper
|id=Vol-2018/paper-06
|storemode=property
|title=Process Description of Clustering Experimental Games on Allocation of Limited Resources
by the Modified Groves-Ledyard Mechanism
|pdfUrl=https://ceur-ws.org/Vol-2018/paper-06.pdf
|volume=Vol-2018
|authors=Vadim Glukhov,Olga Kuznetsova,Natalia Dodonova
}}
==Process Description of Clustering Experimental Games on Allocation of Limited Resources
by the Modified Groves-Ledyard Mechanism==
https://ceur-ws.org/Vol-2018/paper-06.pdf
Process Description of Clustering Experimental
Games on Allocation of Limited Resources by the
Modified Groves–Ledyard Mechanism?
Vadim Glukhov, Olga Kuznetsova1 , and Natalia Dodonova
Samara National Research University, Samara, Russia,
1
olga_5@list.ru
Abstract. The study describes the mechanism for the data clustering
of resource allocation business games with the modified Groves-Ledyard
mechanism. The algorithm is based on the evaluation of the players’ pa-
rameters changes in the previous step of the game to the logic of the
action of one of the players in the next move. In comparison, the follow-
ing parameters are involved: the player’s bids, the resource allocated to
him and his profit. Clustering is performed by comparing the moves of
players in three steps of the game. First, a comparison is made between
the change in profit and the distribution of players’ resources in the first
two steps, the next step is to compare the player’s bid in the second and
third moves of the game. The parameter comparison takes one of the
following values: the parameter is in-creased, the parameter is reduced,
the parameter has not changed. Depending on these characteristics, the
player’s move is entered into one of the clusters. After building a his-
togram and analyzing it at a significant level of elements in clusters, one
can draw a conclusion about the logic of the players’ actions in vari-
ous game situations and simulate the behavior of players, knowing the
current state of the game.
Keywords: clustering, business game, limited resource, modified Groves–
Ledyard mechanism
1 Introduction
One of the most common problems in economics is the distribution [3, 4] of a
limited resource. To solve the problem of the distribution of a limited resource
between se-veral agents, various mechanisms are used, either manipulated [1] or
non-manipulated [5, 6, 9] ones.
Adequate models of players’ behavior are needed for assessing the effective-
ness of mechanisms. Existing models of behavior “Fixed orders”; “Indicator be-
havior” “The best answer” [7] do not fully describe the bids of human players.
Also, these behavior patterns do not take into account the reflection in the be-
havior of players [8]. In [2] a model of behavior based on fuzzy logic for the
?
Supported in part by RFBR, grant 17-07-01550 А.
mechanism of reverse priorities takes into account the reflexive behavior of the
players.
This model is based on the knowledge (detection) of rules of agents’ behav-
ior, depending on the state of their environment, and assumes the existence of
reflexive behavior. The environment is defined as the known values of bids and
the players’ resource received on the last step.
The rules of conduct will differ in the games with different mechanisms. To
play the resource allocation game with the mechanism of reverse priorities, the
rules were determined by an expert method. For the games with more complex
mechanisms, the formulation of rules is a more complex process. To formulate
rules for the players behavior, it is suggested to use the clustering method.
An assumption was made about the typical behavior of players in standard
situations of the external environment.
2 Algorithm description
The study describes the algorithm for clustering business games’ data on the
distribution of a limited resource by the modified Groves–Ledyard mechanism.
This algorithm is based on the allocation of clusters based on the players behavior
and the identification of the most frequently used moves of players, grouped into
clusters, with their further description and analysis. The algorithm is based on
comparison of the parameters of the players previous and next moves in the
game. The analysis was carried out in the RStudio software environment using
the programming language R.
The original game database is an excel file containing information on 23
games and the actions of players on each turn of each game.
Before the execution of the clustering algorithm, the preparation of data is
re-quired: selecting games into separate excel files; sorting the data according
to the fact that every three lines show data only for one particular player; for
example, lines 1, 4, 7, 10 contain data for player 1, lines 2, 5, 8, 11 contain data
for player 2 and lines 3, 6, 9, 12 contain data on player 3.
The process of clustering consists of identifying steps that meet certain crite-
ria and fill in the relevant clusters. The criteria for initial clustering are: change
in the player’s bid, change in the amount of the resource received by the agent,
change in the player’s profit, and changes in the received resource and profits of
other agents.
The essence of clustering is the passage through the program on all lines of
the file, except the first and last steps (here in after, “every step” means every
admissible step, i.e. any step except the first and the last ones) and comparing
the characteristics of the i-player to the j step with the characteristics of players
on the j − 1 and j + 1 steps.
The comparison of the steps begins with step 2. Successively compare the
profits of the players on the current turn with the winnings in the previous step,
allocate the resource to each of the players in the current step with the allocation
of the resource in the previous step, and compare the player’s bid at the next
step with the player’s bid at the current step. The obtained result is included
into one of the clusters. If the cycle reaches the last step of the current game,
the cycle ends; the values of the last step of the game were used earlier because
there is not enough evaluation of changes in the profits of other players.
The following notations are accepted in the work: t is a current stroke number,
each step contains three iterations of the game (T ), one for each player (i); I
is the index of the current player, takes one of three values 1, 2 or 3; T is the
total number of the game iterations, is calculated as the product of the number
of players by the number of the game moves, T = t · i; Gi is the profit i of the
player, is calculated with the payment included in it; Xi is the allocation of the
resource i to the player, si is the player’s i bid for receiving the resource.
To calculate the index i by the iteration number of the game T , the following
formula is used: (
T
, if T = 3n, n ∈ N,
i = 3T (1)
3 + 1, if T 6= 3n, n ∈ N.
3 Clusters analysis
Clusters are considered to be significant if they contain more than 10% of the
total number of applications. In the absence of significant clusters, it is necessary
to use the modification of this algorithm: a reduction in the number of clusters,
the inclusion of additional parameters in the algorithm. With the use of classical
clustering methods, due to the specific nature of the problem, it is preferable to
use flat non-overlapping algorithms.
The general algorithm for clustering includes the following steps:
1. The beginning of the cycle: t = 2, i = 1, T = t · i, where t is the number of
the step, i is the player, T is the total number of iterations in the current
game.
2. Utilities’ comparison of all players in the course of t with the utilities’ on the
step t − 1 : ∆g i = gti − gt−1
i
, i = 1, 2, 3.
3. A comparison of the resource allocation to each of the players in the step of
t with the resource allocation on the stept − 1: ∆xi = xit − xit−1 , i = 1, 2, 3.
4. A comparison of the player i’s bid on the t + 1 run with the player i’s bid
on the step t − 1:
(
T
i i i , if T = 3n, n ∈ N,
∆s = st − st−1 , i = 3T (2)
3 + 1, if T 6= 3n, n ∈ N.
5. Based on the results of stages 2–4, the current move is determined in the
corresponding cluster.
6. The next iteration: t = t + 1 (2).
7. The cycle ending is when t = T .
In research, we used the data of the games [7] based on the Groves–Ledyard
mechanism for identification the behavior types of players.
The initial data for clustering is an “xlsx” format file containing data of the
23 games. The number of players in each of the games is 3, the number of moves
is variable and varies from one game to another, moves are made as the players
are ready for the same current move. Player’s profit, player’s application and
distribution at each of the steps are the criteria for clustering. Since the file was
formed automatically after the decision of the player at each step, there is a
disorder of the data. Thus, before starting the algorithm itself, it is necessary to
preprocess and sort the data.
As a result of the data preparation, 23 separate excel files with sorted player
data were identified. Each of the lines of the file contains a move and its numerical
characteristics for one of the players; each column is the criterion for the analysis.
As an example, Table 1 provides the data on first three game moves by the
modified Groves–Ledyard mechanism. It should be noted that for the entry of
a move into the cluster, information on the three subsequent moves is required,
which characterizes the situation of the influence the decisions made by the
players on the sub-sequent step.
Table 1. Initial data for clustering
Game Time Subject Gain Penalty x s1 s2 s3
27 1 1 7.07106781 0 49 49 41 25
27 1 2 7.07106781 0 41 49 41 25
27 1 3 7.07106781 0 25 49 41 25
27 2 1 6.72220297 -0.12675 42.5 49 41 25
27 2 2 7.45977310 0.156 49 34.5 70 10.5
27 2 3 6.99344413 -0.02925 23.5 44 36 35
27 3 1 6.63747321 -0.061 42.25 47 49.125 18.875
27 3 2 7.56048807 0.01414062 48.375 35.75 60 19.25
27 3 3 6.979875286 0.04685937 24.375 44 36 35
In Table 1 “Game” is the number of the game, “Time” is the move, “Subject”
is the player, “Gain” is the player’s profit, “Penalty” is the penalty of the player,
x is the allocation to the player, si is the bid for the player at current move.
To assess the player’s state on the second move, you need to compare his
profits and his rivals received with the previous move. Comparison occurs by
estimating the difference of two quantities. That is, for example, the profit of
player 3 in comparison with the second step decreased (6.99 − 7.07 < 0).
After the evaluation, there are data on the success of each of the players in
the previous move, it needs to be checked how this will affect the next step, what
strategy the player chooses from the results of a successful or an unsuccessful
previous step. To do this, the values of the player’s orders 2 on steps 2 and 3 are
compared.
As follows, each player’s turn is evaluated by seven parameters: the difference
of players’ profits between the second and the first move (3), the difference
between the distribution of players between the second and the first move (3)
and the difference of the current player’s bid between the third and the second
move (1). There are 972 potential clusters which are described in Table 2. It is
the product of the possible values of each of the seven parameters that can take
values: a positive parameter change, a negative change, and an unchanged state.
Table 2. Potential clusters
Criterion Possible changes of criterion
∆xi ↑ ↓ 0
∆x−i ↑↓, ↓↑, ↓↓, ↓0, 0↓ ↑↑, ↑↓, ↑0,↓↑, 0↑ ↑↓,↓↑
∆ϕi ↑, ↓, 0 ↑, ↓, 0 ↑, ↓, 0
∆ϕ−i ↑↑, ↑↓, ↑0, ↓↑, ↓↓, ↓0, ↑↑, ↑↓, ↑0, ↓↑, ↓↓, ↓0, ↑↑, ↑↓, ↑0, ↓↑, ↓↓, ↓0,
0↑, 0↓, 00 0↑, 0↓, 00 0↑, 0↓, 00
∆si ↑, ↓, 0 ↑, ↓, 0 ↑, ↓, 0
In Table 2 “↑“ is parameter of increase, “↓“ is parameter of decrease, “0”
is invariance of the parameter, xi is change in the resource allocation to the
i-player, ∆ϕi is change in the i-player’s payoff, si is change in the i-player’s bid,
∆x−i are changes in the allocation of the resource to players j ∈ N\{i}, ∆ϕ−i
are changes in the payoff to players j ∈ N\{i}.
Each of the clusters is stored in a vector where an array of all steps is stored.
Later, the vector will be converted into a list, counting the number of elements
for each of the clusters. The vector and the list above are the data structures of
the R language, not the mathematical concepts.
In total, as a result of clustering, a distribution of 170 clusters is obtained.
The result is shown in the figure. The horizontal axis indicates the clusters in
order of increasing elements in each cluster, on the vertical axis – the number of
elements in the cluster. The maximum number of elements is 60, the minimum
number of elements is 1.
The distribution of steps for clusters is shown in Fig. 1.
The five most common situations in the games are the situations described
in Table 3. The most frequently used decision is to do nothing. Increasing the
bid used less often. Reducing the bid is the most unused action.
Thus, knowing the distribution of the moves of players, one can predict their
behavior in one of the following moves, starting with the third. This information
can be used to simulate the game process, analyze the tactics of the winning and
losing player or identify the features of a specific mechanism.
Fig. 1. Distribution histogram of clusters
Table 3. Characteristics of the largest clusters
Parameters Number of
Clusters
∆xi ∆x−i ∆ϕi ∆ϕ−i ∆si elements
1 ↓ ↓↑ ↓ ↓↑ 0 60
2 ↑ ↓↓ ↑ ↓↓ ↓ 45
3 ↓ ↑↑ ↓ ↑↑ ↑ 39
4 ↑ ↓↑ ↑ ↓↑ 0 37
5 ↑ ↑↓ ↓ ↑↓ ↑ 36
4 Conclusion
This article describes the algorithm for clustering business game data on the
allocation of a limited resource by the mechanism of reverse priorities. A feature
of this clustering is the selection criteria. In this clustering, the selection criterion
is the difference between the current and previous win values, the distributed
resource of all agents, and the difference between the current and the next ap-
plication value of the selected agent. In this case, the sign of the difference (plus
or minus) matters.
Based on the results of clustering, several large clusters are identified. You
can identify typical rules of players’ behavior and simulate human actions in
each subsequent game.
Such an algorithm can be used as a base algorithm for the resource allocation
games by other mechanisms. It is possible to change the clustering criteria if the
clustering result is not good enough.
References
1. Burkov, V., Danev, B., Enaleev, A., et al.: Bolyshyesistemy: Modelirovanie organi-
zatsionnykh mekhanizmov. Nauka, Moscow (1989)
2. Dodonova, N., Kuznetsova, O., Yelistratov, A.: Model of decision support system
using fuzzy logic in business games of allotment problem for system with untrans-
ferable utility. In: Novikov, D., Burkov, V. (eds.) CONFERENCE 2016, vol. 404,
pp. 97–101. TAS, Moscow (2016)
3. Geras’kin, M.I.: Transferable utility distribution algorithm for multicriteria control
in strongly coupled system with priorities. CEUR-WS 1638, 542–551 (2016)
4. Geras’kin, M.I., Egorova, V.V.: The algorithm for dynamic optimization of the pro-
duction cycle when custom planning in industry. CEUR-WS 1638, 552–568 (2016)
5. Groves, T., Ledyard, J.: Optimal allocation of public goods: A solution to the ‘Free
rider’; problem. Econometrica 45(4), 783–809 (1977)
6. Korgin, N.: Efficient mechanism for resource allocation with quadratic payments and
its realization via an iterative bargaining process. IFAC Proceedings Volumes 46(9),
1176–1181 (2013), 7th IFAC Conference on Manufacturing Modelling, Management,
and Control
7. Korgin, N.A., Korepanov, V.O.: An efficient solution of the resource allotment prob-
lem with the Groves–Ledyard mechanism under transferable utility. Automation and
Remote Control 77(5), 914–942 (2016)
8. Novikov, D., Ckhartishvili, A.: Reflexion and Control: Mathematical Models. CRC
Pressw, Leiden (2014)
9. Yang, S., Hajek, B.: Revenue and stability of a mechanism for efficient allocation of
a divisible good. http://hajek.ece.illinois.edu/Papers/YangHajek06.pdf (Oct 2006)