About scarce resources allocation in conditions of incomplete information N.L. Dodonova1, O.A. Kuznetsova1 1 Samara National Research University, 34 Moskovskoe Shosse, 443086, Samara, Russia Abstract The article examines the problem of the efficient allocation of resources in conditions of incomplete information concerning the parameters of agents’ utility functions. Through business game the results are modeled and compared in conditions of incomplete information concerning the agents’ utility functions.We experimentally prove the inexpediency of information distortion of the agents’ effectiveness when using a non- manipulative distribution mechanism in a multi-step game. Keywords: game theory; reflexive games; incomplete information; information structure; information management; distribution mechanisms; behavior models; utility functions; nontransferable utility; fuzzy logic 1. Introduction The problem of effective resource allocation occurs in various applied problems [4]. If the resource value is limited and the participants interests do not coincide, a conflict situation arises. Interaction of participants in this case can be considered as a game. The description of several agents interaction includes the following parameters: • the multitude of agents; • agent preferences (he/she is assumed that each agent is interested in maximizing his profits); • set of permissible actions; • awareness of agents (at the time of making decisions about the chosen action); • the order of functioning (the sequence of actions). These parameters set the game. The game purpose is to define the multitude of active agents’ actions. It means finding an equilibrium situation. Decision-making models, behavior models, the equilibrium concept have been studied in game theory for more than 100 years. The review of the results is given, for example, in [3]. Basically, it is assumed that participants have the same information about the parameters of the game. A class of reflexive games in which agent awareness is not a common knowledge and agents make decisions according to their perceptions of opponents' preferences. Their permissible actionsare described in [8]. Obviously, in the situation of incomplete information, participants' behavior patterns. Indeed, if the agent assumes that his rivals are "strong" players, he/she will stick to one behavior pattern; If he/she thinks that opponents are "weak" players, then the behavior pattern can change. The process and result of the agent's thinking about the values of uncertain parameters, and what about these competitors think about these parameters, are called information reflection [8]. The players' perception hierarchy is represented by the form of information structuretree. The research and analysis of the game information structure allows to determine the conditions for the information equilibrium, as well as to set the information management task–to create the information structure creation that implements the equilibrium situation that is most beneficial to the Resources Allocation Center. This paper is devoted to the investigation of the appropriateness of information distortion about the agents’ effectivenessin different behavior models in the situation of incomplete awareness of the participants about the parameters of the game. It is assumed that the game participants can distort information about their target functions parameters, posing as "strong" or "weak" players. A hypothesis that the information distortion about the values effectiveness, with the possibility of requests further distortion, does not have a significant effect on the limited resource distribution between the players, is confirmed experimentally. The study was carried out using an original Fuzzy Logic Model (FLM) [6] and the Best Response Model (BRM) [1]. 2. Basic concepts and parameters Let us consider the problem of distributing the resource R between n players. R be a distributable resource; N is the number of players; 𝑢(𝑥𝑖 ) = 𝑏𝑥𝑖 − 𝑎𝑖 𝑥𝑖2 , 𝑎 > 0, 𝑏 > 0 is the utility function of the i-th player. 𝒃 Obviously, the player will get the maximum profit at the point 𝒙∗𝒊 = . 𝟐𝒂𝒊 In the case ∑𝑛𝑖=1 𝑥𝑖∗ > 𝑅, the conflict situation develops and players are forced to fight for the resource. If 𝑆(𝑥1 , 𝑥2 , … 𝑥𝑛 ) = ∑𝑛𝑖=1(𝑏𝑥𝑖 − 𝑎𝑖 𝑥𝑖2 ) is the players total profit and there exists a restriction ∑𝑛𝑖=1 𝑥𝑖 = 𝑅, then it is easy to show that 𝑆(𝑥1 , 𝑥2 , … 𝑥𝑛 ) reaches a maximum at the point (𝑥1 0 , 𝑥2 0 , … 𝑥𝑛 0 ), where 𝒂𝟏 𝒂𝟐 …𝒂𝒊−𝟏 𝒂𝒊+𝟏 …𝒂𝒏 𝒙𝒊 𝟎 = ∑𝒊≠𝒋 𝒂𝒊 𝒂𝒋 , 𝒊 = ̅̅̅̅̅ 𝟏, 𝒏, 𝒋 = ̅̅̅̅̅ 𝟏, 𝒏. 3rd International conference “Information Technology and Nanotechnology 2017” 130 Mathematical Modeling / N.L. Dodonova, O.A. Kuznetsova If 𝒙∗𝒊 ≠ 𝒙𝟎𝒊 then the i-th player will be interested in increasing his profit. As a mathematical model of the described interest conflict situation, we will use the business game for resource allocation R between n players with a reverse priority mechanism. At each step of the game the participant makes an request si to the resource. The request is satisfied by the Resource Allocation Center in the volume 𝐴𝑖 1, 𝑛, where 𝐴𝑖 = 𝑢(𝑥𝑖∗ ). 𝑠𝑖 𝑥(𝑠𝑖 ) = 𝐴𝑗 𝑅, 𝑖 = ̅̅̅̅̅ ∑𝑛 𝑗=1 𝑠𝑗 The winning is determined by the player's profit from the resource obtained in the last step. It should be note that the resource distribution is based on the knowledge of the values 𝐴𝑖 = 𝑢(𝑥𝑖∗ ) of each of the participants. In a sense, Ai can be interpreted as the utility limit of the i-th player. Let us suppose that the true values of Ai are not known to the Center (the cost factor ai is known only to the player) and for the distribution of the resource the players themselves inform the Center of the value Ai. In this case, the player has the opportunity to exaggerate, downplay the limit of its usefulness or to convey its true meaning. Also, at each step, players report the value of the required resource, which is adjusted by the players in order to obtain the desired amount. How will the distribution of the resource change in conditions of incomplete information of the Center about the usefulness of the players? Is it possible in such conditions to maximize the profit of an individual player and the total utility of the players? Is it profitable for participants to hide the true meaning of the limit of their usefulness? Purpose of the study The purpose of this study is to compare the participants profit size in a business game on the resource distribution in different information levels of the players parameters conditions. We tasks: - to conduct a computational experiment in incomplete information conditions about the needs of players in resources, using different participants' behavior models; - to conduct a computational experiment in incomplete information conditions about the players target functions and their resource needs, using different participants' behavior models; - to conduct a comparative analysis of the results. 3. Description of the experiment For carrying out the computing experiment two models will be used: - Best Response Model (BRM); - Fuzzy Logic Model (FLM). The BRM [7] assumes that at the k+1 step of the game, the bid value sik +1 must be such that x(sik +1) = xi*. If the remaining players do not change their bids, then the volume of the requestcan be calculated from the condition 𝐴𝑖 𝑠𝑖𝑘+1 𝑥(𝑠𝑖𝑘+1 ) = 𝐴𝑗 𝐴 𝑅 = 𝑥𝑖∗ , ∑𝑛𝑗=1 𝑘 − 𝑘+1 𝑖 𝑠𝑗 𝑠𝑖 then 𝐴𝑖 𝑥𝑖∗ 𝑠𝑖𝑘+1 = 𝐴𝑗 𝐴𝑖 (𝑅 − 𝑥𝑖∗ ) ∑𝑛𝑗=1 𝑘 − 𝑠𝑗 𝑠𝑖 𝑘 The FLM [6] uses the following input data: 𝑥(𝑠𝑖 ) 𝛼𝑖 = 𝑥𝑖∗ αi is the degree of satisfaction of the request; N is the proportion of players with αi ≥ 1. The rules base, which gives an assessment of the attractiveness of the player's actions, consists of the possible actions: - to increase the request, - to lower the request, - not to change the request. The rules base has the form: R1. If the degree of the request satisfaction αi is small and the players share N is low, then the declining of the request attractiveness is great. R2. If the degree of the request satisfaction αi is small and the players proportion N is high, then the attractiveness not to change the request is great. R3. If the degree of the requests satisfaction αi is close to 1 and the players share N is low, then the declining of the request attractiveness is great. R4. If the degree of the requests satisfaction αi is close to 1 and the share of players N is high, then the attractiveness of the bid increase is great. 3rd International conference “Information Technology and Nanotechnology 2017” 131 Mathematical Modeling / N.L. Dodonova, O.A. Kuznetsova R5. If the degree of the request satisfaction αi is large and the players share N is low, then the attractiveness not to change the request is great. R6. If the degree of the requests satisfaction αi is large and the share of players N is high, then the attractiveness of the bid increase is great. As a result of FLM, the evaluation λ[0,1] of the attractiveness of player actions is given. The player may increase the bid (P↑), lower the bid (P↓) or not to change the request (P0). Special software was developedfor the experiment in the program environment O-Tree [9]. In the course of study, various combinations of the input parameters considered in Table 1 were considered. In each experiment, a series of 10 stepswas conducted. Table 1. Experiments input parameters combinations. № experiment Utility function Deficiency of resorce Relative location of 𝑥𝑖∗ Behavior model 𝑛 𝑢(𝑥𝑖 ) = 𝑏𝑥𝑖 − 𝑎𝑖 𝑥𝑖2 |𝑅 − ∑ 𝑥𝑖∗ | 𝑖=1 1 the same small the same BRM 2 the same large the same BRM 3 different small narrow spread BRM 4 different small wide spread BRM 5 different large narrow spread BRM 6 different large wide spread BRM 7 the same small the same FLM 8 the same large the same FLM 9 different small narrow spread FLM 10 different small wide spread FLM 11 different large narrow spread FLM 12 different large wide spread FLM The form of utility function determines whether the player should maximize the amount of the resource he receives, or optimize it. Deficiency of resource impliesvarious tensions in the game and level request distortion. Relative location of 𝑥𝑖∗ means that the optimal resource values in different functions have the same deviation from equal distribution. In this caseplayers have the same chance to be winner. Behavior model means that players use special rules for their actions. 4. Results and Discussion 600 х1 Resorce 400 х2 200 х3 0 1 2 3 4 5 6 7 8 9 10 Step Fig. 1. Agents report the exact value of their effectiveness. 600 х1 Resorce 400 х2 200 х3 0 1 2 3 4 5 6 7 8 9 10 Step Fig. 2. The first agent overestimates the importance of its effectiveness. 3rd International conference “Information Technology and Nanotechnology 2017” 132 Mathematical Modeling / N.L. Dodonova, O.A. Kuznetsova The dynamics of resource allocation is presented on Figures 1, 2, 3. Here x1 is the value ofthe resource allocated to the first player, x2 is the value of the resourceallocated to the second player, x1 is the value of the resource allocated to the third player. 600 х1 Resorce 400 х2 200 х3 0 1 2 3 4 5 6 7 8 9 10 Step Fig. 3. The first agent underestimates the importance of its effectiveness. In all cases, the deviation of the obtained resource from the optimal individual indicator is approximately the same. Table 2 shows the relative deviations of the resource obtained by agents in cases of reliable reporting of information on effectiveness, overestimation of the first agent effectiveness, underestimation of the first agent effectiveness in the first step. Table 2. The relative deviations of the resource obtained by agents in the first step. №1 №2 №3 х1 0,33 0,25 0,43 х2 0,07 0,12 0,00 х3 -0,07 0,00 -0,15 № 1. In the first step all players provide reliable information about their own effectiveness and the amount of the required resource. In the next steps distorting the value of the resource request is distorted in accordance with the chosen behavior model. № 2. In the first step the player 1 overstates the information on its own efficiency by 20%, other players provide reliable information about their own effectiveness and all players report reliable information about the amount of the required resource. In the next steps distorting the value of the resource request in accordance with the chosen behavior model. № 3. In the first step the player 1 understates information about its own efficiency by 20%other players provide reliable information about their own effectiveness and all players report reliable information about the amount of the required resource. In the next steps distorting the value of the resource request in accordance with the chosen behavior model. Table 3 shows the resources relative deviations obtained by agents in cases of reliable reporting of information on effectiveness, overestimation of the first agent effectiveness, underestimation of the first agent effectiveness in the tenth step. Table 3.The relative deviations of the resource obtained by agents in the tenth step. №1 №2 №3 х1 0,12 0,12 0,12 х2 0,16 0,16 0,16 х3 0,17 0,17 0,16 The results of the calculations presented in the tables 2, 3. The information distortion about efficiency leads to a significant change in the distribution results in the first step. As we can see from the results of the calculations presented in the Table 3, the information distortion about efficiency does not lead to a change in the distribution results in the tenth step. Figure 4 presents the averaged values of the relative deviations from the optimal resource values in games with BRM (exact information about the effectiveness of players, distorted information about the effectiveness of players). 600 a Resource 400 b 200 c 0 Р1 Р2 Р3 d Players Fig. 4. The resource distribution. a is the players provide reliable information about the maximum of their profits; b is the players overestimate the value of their maximum profit; c is the players underestimate the value of their maximum profit; d is the players distort information about the maximum of their profits. 3rd International conference “Information Technology and Nanotechnology 2017” 133 Mathematical Modeling / N.L. Dodonova, O.A. Kuznetsova P1 is the first player, P2 is the second player, P1 is the third player. Figure 5 shows the averaged values of the total utility of participants in games with BRM and FLM (exact information about the effectiveness of players, distorted information about the effectiveness of players) 600000 a Profit 400000 200000 b 0 c 1 2 3 4 d Players Fig. 5. The averaged values of the total utility. Table 4 presents numerical data on the resource distribution among participants, the magnitude of individual and total profits. Table 4.The resource distribution among participants. The value of the resource distribution Profit of player Player a b c d a b c d Р1 453,57 455,4782 460,1372 455,9209 289962,8 288575,2 285095,7 288250,2 Р2 355,1272 353,4823 349,4531 353,096 79677,78 82215,97 88318,84 82808,03 Р3 191,3028 191,0396 190,4097 190,9831 89831,48 90110,22 90772,57 90169,83 Total profit 459472 460901,4 464187,1 461228,1 You can see that difference between total profit in the different experiments consists less of than 1%. We consider this deviation to be insignificant. 5. Conclusion The article discusses the effectiveness of distorting information about the agents’ effectiveness in incomplete information conditions in the limited resource distribution problem. Experiments were performed by robots with various input parameters combinations. A comparative analysis of the games results with reliable and inaccurate information about the players effectiveness was carried out. The agents’ profit and the system total profit are calculated. The conducted experiments showed that a single distortion of information about the effectiveness of players, with constant distortion of players 'requests, does not affect the distribution of players' profits. References [1] Burkov VN, Danev B, Enaleev AK. Large systems: modeling of organizational mechanisms. M.: Science, 1989; 248 p. [2] Arifovic J, Ledyard J. A Behavioral Model for Mechanism Design: Individual Evolutionary Learning. Journal of Economic Behavior & Organization 2010. [3] Avtonomov VS. Model of man in economics. St. Petersburg: Economic School, 1998; 230 p. [4] Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya EB. Dividing Goods and Bads Under Additive Utilities. NRU Higher School of Economics. Series EC "Economics" 2016; 153. [5] Geraskin MI. Transferable utility distribution algorithm for multicriteria control in strongly coupled system with priorities. CEUR Workshop Proceedings 2016; 1638: 542—551. DOI: 10.18287/1613-0073-2016-1638-542- 551. [6] Geraskin MI, Egorova VV. The algorithm for dynamic optimization of the production cycle when custom planning in industry. CEUR Workshop Proceedings 2016; 1638: 552—568. DOI: 10.18287/1613-0073-2015-1638-552- 568. [7] Dodonov MV, Dodonova NL, Kuznetsova OA, Elistratov AA. Model of a decision support system using fuzzy logic in business resource allocation games with nontransferable utility. Management of large systems. Materials XIII Vseros. School-conf. young scientists. Moscow: IMP RAS, 2016. [8] Korgin NA. Representing sequential resource allocation mechanism in form of strategy-proof mechanism of multi-criteria active expertise. Management of large systems. Moscow: IMP RAS 2012; 36: 186—208. [9] Novikov DA, Chkhartishvili AG. Reflective games. Moscow: SINTEG, 2003; 160 p. [10] A software platform for economics experiments URL: http://www.otree.org/. 3rd International conference “Information Technology and Nanotechnology 2017” 134