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 effectiveness of mechanisms. Existing models of behavior "Fixed orders"; "Indicator behavior" "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 behavior of players [8]. In [2] a model of behavior based on fuzzy logic for the 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' behavior, 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.
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 criteria 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; G i is the profit i of the player, is calculated with the payment included in it; X i is the allocation of the resource i to the player, s i 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:
(1)
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 :
A comparison of the resource allocation to each of the players in the step of t with the resource allocation on the stept − 1:
A comparison of the player i's bid on the t + 1 run with the player i's bid on the step t − 1:
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. 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, s i 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. In Table 2 "↑" is parameter of increase, "↓" is parameter of decrease, "0" is invariance of the parameter, x i is change in the resource allocation to the i-player, ∆ϕ i is change in the i-player's payoff, s i 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.
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 application 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.