Adv Syst Sci Appl 2019; 04; 58-65 Published online at http://ijassa.ipu.ru/index.php/ijassa/article/view/763 Resource Allocation with a Probabilistic Amount of Resource Vladimir Burkov*1, Irina Burkova1,2, Larisa Rossikhina2,3 1) Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia E-mail: vlab17@bk.ru 2) Academy of Management, the Ministry of Internal Affairs of the Russian Federation, Moscow, Russia 3) Voronezh Institute of the Federal Penitentiary Service of the Russian Federation, Voronezh, Russia Received July 7, 2019; Revised December 14, 2019; Published December 31, 2019 Abstract: The allocation problem of a limited resource under the probabilistic uncertainty over its amount is considered. The Principal has a certain amount of resources to be allocated by him/her among consumers (agents). Each agent submits the request for the resource to the Principal. The Principal allocates the resource in accordance with a specified resource allocation mechanism. In the theory of active systems, the priority-based resource allocation mechanisms were proposed and investigated. With these mechanisms, the resource is allocated proportionally to the values of the agent’s priority functions. Three types of the priority-based mechanisms were identified, namely, the mechanism of absolute priorities, the mechanism of straight priorities and the mechanism of reverse priorities. Previously, the priority-based mechanisms were considered under the assumption that the amount of available resource to be allocated by the Principal is known. However, in many real resource allocation problems arising in practice this amount is often unknown. In this paper, the priority-based mechanisms are studied for the case in which the agents know the Principal’s resource allocation function. The mechanisms of resource allocation based on the principle of reverse priorities are studied. Keywords: resource allocation; mechanisms of reverse priorities; probabilistic uncertainty; Nash equilibrium. 1. INTRODUCTION The allocation problems of limited resources are widespread in practice [1, 2, 3]. The classical resource allocation scheme is as follows [4]. The Principal has a certain amount of resources to be allocated by him/her among consumers (agents). Each agent submits the request for the resource to the Principal. The Principal allocates the resource in accordance with a specified resource allocation mechanism [5, 6, 7]. In the theory of active systems, the priority-based resource allocation mechanisms were proposed and investigated [8, 9]. With these mechanisms, the resource is allocated proportionally to the values of the agent’s priority functions. Three types of the priority-based mechanisms were identified, namely, the mechanism of absolute priorities, the mechanism of straight priorities and the mechanism of reverse priorities. In absolute priority mechanisms, resource allocation is proportional to the priorities set by the Principal. These mechanisms are non-manipulated. It means that submit a request that * Corresponding author: vlab17@bk.ru RESOURCE ALLOCATION WITH A PROBABILISTIC AMOUNT OF RESOURCE 59 Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) reflects the true needs of the resource is beneficial for agents. Their disadvantage is the fact that agents do not actually affect resource allocation. In the mechanisms of direct priority resources are allocated proportionally to the priorities that grow with the request on the principle of "more you ask – more you get". This principle leads to a trend of increasing of the request. It is significant disadvantage of the principle of direct priorities. However, it is still widely used in practice. In the mechanisms of reverse priority resource allocation is also proportional to functions of priority. However, these functions are decreasing functions of the request value on the principle of "more you ask – less you get". The principle of reverse priorities encourages resource savings. This is its significant advantage. It is experimentally tested in the allocation of water resources [2]. Of the three described mechanisms of priority, the reverse priority principle is the most preferred. Previously, the priority-based mechanisms were considered under the assumption that the amount of available resource to be allocated by the Principal is known. However, in many real resource allocation problems arising in practice this amount is often unknown [10, 11]. In this paper, the mechanism of reverse priorities is investigated for the case in when agents know the Principal’s resource allocation function. 2. PROBLEM STATEMENT Consider an active system consisting of the Principal and agents. The Principal has a resource to be allocated among the agents in accordance with their requests. While submitting the requests, the agents have information about the Principal’s allocation function F(R) only, where R is the amount of available resource to be allocated. The goal function of each agent i is an increasing function of the received resource xi. Denote by Si the request for the resource submitted by agent i. The Principal allocates the resource using the mechanism of reverse priorities. The problem is to determine the Nash equilibrium situation for three cases. In the first case the amount of resource available to the Principal is known to the agents. In the second case, the agents know the distribution function F(R) of the resource available to the Principal. In the third case, the distribution function of the resource available to the Principal is discrete (more precisely, the resource takes two values with corresponding probabilities). 3. MECHANISM OF REVERSE PRIORITIES: DETERMINISTIC CASE Consider the deterministic case in which the amount of resource available to the Principal is known to the agents. Define the priority function of agent i by   iS iA iSi  , ni ,1 , where Ai is a parameter that restricts the agent’s priority. The resource allocation mechanism has the form   min , A Rix S Si i S Yi           , (3.1) where Aj Y Sj j   . Assume the goal functions of the agents are increasing in xi. The deterministic statement of the problem yields the Nash equilibrium 60 V. BURKOV, I. BURKOVA, L. ROSSIKHINA Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) 2 1 Y Aj R j         , A Ri Si A j j    . In this case, iSix  for all ni ,1 . Now, consider another modification of the priority function given by   iSiAiSi  , ni ,1 . First, analyze the deterministic case:           R Y iSiA iSSix ,min , where    j jSjAY . In the Nash equilibrium, R Y iSiA iS   , which gives RY iRA iS   and RY YiA iSiA   . From the condition      j j jA YR Y jsjaY it follows that RAY  * , R j jA iA iS   * . The Nash equilibrium exists only if the condition A > R is satisfied. 4. MECHANISM OF REVERSE PRIORITIES: PROBABILISTIC CASE Consider the probabilistic case in which the agents choose their requests for the resource using the information about the distribution F(R) of the available amount R only. Consider the priority function   iS iA iSi  , ni ,1 , and the resource allocation mechanism   min , A Rix S Si i S Yi           . Denote by F(R) a distribution function of the available amount of the resource and let it be continuously differentiable with respect to R. The expected amount of resource requested by agent i is RESOURCE ALLOCATION WITH A PROBABILISTIC AMOUNT OF RESOURCE 61 Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019)      1 0 Ri A RiM S dF R S F Ri i S Yi        , where 2 S YiRi Ai   , ni ,1 . Find the maximum of this value over Si under the hypothesis of weak contagion (the influence of Si on Y is small). In other words, while choosing their requests for the resource, the agents neglect the influence of Si on Y, considering Y to be just a parameter. Note that        iR iR dRRFiRFiRRRdF 0 0 . Calculate     2 0 RiAdM i R F R F R dRi i dS S Yi i                 ' ' 1 A dR dRi i iR F R F R S F Ri i i i i S Y dS dSi i i      . A series of trivial transformations finally give     1 1 2 0 RidM F R F R dRi dS Ri i     . The resulting expression is independent of Ai. Assume the function М(S) is convex and therefore has a maximum point. The equilibrium value Ri is the same for all agents, i.e., Ri=R* for all i. The maximum point R* can be determined from the first-order optimality condition     * 1* 2 1 0 R F R F R dR Ri   , where Y RiA iS * *   . Further, calculate  j jA R Y j jS jA Y ** * , * * R j jA Y   . Finally, the Nash equilibrium is ** R j iA iA iS    . Now, consider the priority function   iSiAiSi  , ni ,1 and the resource allocation mechanism           R Y iSiA iSSix ,min . By analogy with the previous case, 62 V. BURKOV, I. BURKOVA, L. ROSSIKHINA Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019)             iR iRFiSRRdF Y iSiA iSM 0 1 , where S YiRi A Si i   ,  2iSiA iYA idS dR   . Calculate               iRF iR dRRFiRFiR YidS dM 1 0 1           iR dRRF Y iRF Y iR 0 1 11 ,             iRF Y iRF Y iR iRF YdR Md 1' 1 1 2   0 ' 1        iRF Y iR . Hence, the function  iSM is concave, and the maximum point can be determined from the first-order optimality condition (the same for all agents)        R YdxxFRFYR 0 . 5. MECHANISM OF REVERSE PRIORITIES: DISCRETE CASE Suppose the available resource R is Q1 with a probability p1 and Q2 with the probability 2 11p p  . Adopt the mechanism of reverse priorities with the priority function   iS iA iSi  , ni ,1 . Establish how the expected amount of the agent’s resource depends his/her request (for simplicity, the agent’s number i is omitted). Calculate Y AQ d 1  and Y AQ D 2  . Then three situations are possible as follows: 1) dS  . In this case , with the mechanism of reverse priorities the minimum will be achieved on the request, if 1QR  and if 2QR  . Therefore,   SSM  . 2) DSd  . In this case, the minimum point YS AQ x   1 will be achieved if 1QR  , and the minimum point Sx  will be achieved if 2QR  . The expected amount of the resource will be   Sp YS AQ pSM 2 1 1    . 3) DS  . In this case, the minimum point YS AQ x   1 will be achieved if 1QR  , and the minimum point YS AQ x   2 will be achieved if 2QR  . The expected amount of the resource will be     R SY A SY A QpQpSM     2211 . RESOURCE ALLOCATION WITH A PROBABILISTIC AMOUNT OF RESOURCE 63 Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) The graph of the function  SM can be seen in Fig 4.1. Fig. 4.1 Graph of function  SM . On the interval  Dd , ,  SM is a convex function of S. Therefore, it achieves a maximum at the points d or D. Note that, if 1dS  , then dM  ; with 1QQ  or 2QQ  , the agent will receive the same amount dx  . If DS  , then Dpp YD AQ M 21 1    . The maximum of M is given by                 221 2 1 ;1max2 1 1;max pQp Q Q Q Y A Dp YD Q pd If the maximum is achieved on 1Q , the agent will choose the strategy d; if on 22 2 1 1 Qp Q Q p  , then the strategy D. Define * 1p from the equation   2121 2 1 1 pQp Q Q Q  . After simple calculations, 21 2* 1 QQ Q p   . So, if * 1 pp  , then each agent will choose the strategy d; if * 1 pp  , then the strategy D. In both cases, in the Nash equilibrium the resources will be allocated as follows: Q B iA ix  , where  i iAB . Next, consider the priority function   iSiAiSi  , ni ,1 . By analogy with the previous analysis,           Y QSA Sx ;min , where    j jSjAY . Using the equation   Y QSA S   , find 64 V. BURKOV, I. BURKOVA, L. ROSSIKHINA Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) 1 1 QY AQ d   and 2 2 QY AQ D   . If dS  , then   dxM  . If DSd  , then              2 11 2 1 1 p Y Qp S Y A RSp Y QSA pxM . If DS  , then       2211 QpQp Y SA xM    . Obviously, the maximum of  xM is achieved either at the point d or at the point D. Hence,              Dp Y QDA pdxM 2 1 1;             2 2 2 1 2 1 ; 1 1 max p YQ Q p YQ Q YQ Q A . The boundary value * 1p can be defined from the equation 2 2 2 1 2 1 1 1 p YQ Q p YQ Q YQ Q      . Trivial calculations yield YQ Y p   1 * 1 . In contrast to the previous case, the value * 1p depends on Y. If jdjS  , then    j BjdjAY , 1QBY  , B Q p 1 1 * 1  . If iDiS  , ni ,1 , then B Q p 2 1 * 1  . Again, three cases are possible as follows. 1) B Q p 1 1 . In this case, all agents will choose the strategy id , ni ,1 . 2) B Q p 2 1 . In this case, all agent will choose the strategy iD , ni ,1 . 3) B Q p B Q 1 1 2 1  . This situation has uncertainty. If all agents choose the strategy id , then B Q p 1 1 * 1  ; therefore, * 1pp  and they will benefit more from the strategy iD . If they choose the strategy iD , then B Q p 2 1 * 1  ; therefore, * 1pp  and the agent will benefit more from the strategy id . The situation is difficult to predict. RESOURCE ALLOCATION WITH A PROBABILISTIC AMOUNT OF RESOURCE 65 Copyright ©2019 ASSA Adv. in Systems Science and Appl. (2019) 6. CONCLUSIONS In this paper, a study of the mechanism of inverse priorities for resource allocation in the deterministic and probabilistic case has been presented. For different priority functions the Nash equilibrium has been obtained under the assumption that the goal functions of the agents are monotonically increasing in their amounts of resource. REFERENCES 1. Burkov V. N., Gorgidze I. I., Novikov D.A & Yusupov B. S. (1997). Models and mechanisms of distribution of costs and income in the market economy. Moscow: Institute of Control Sciences 2. Burkov V. N., Danev B. D. & Enaev, A. K. (1989). Large Systems: modeling of organizational mechanisms. - Moscow: Science. 3. Burkov V. N., Korgin N. A. & Novikov D. A. (2009). Introduction to the theory of control of organizational systems. - Moscow: Librocom. 4. Novikov, D. (2013), Theory of Control in Organizations, New York: Nova Science Publishers. 5. Control mechanism (2013). Organization management: planning, organization, stimulation, control, ed. by D. A. Novikov. Moscow: LENAND. 6. Mas-Colell, A., Whinston, M. D., & Green, J. R. (1995). Microeconomic theory (Vol. 1). New York: Oxford university press. 7. Maschler, M., Solan, E., & Zamir, S. (2013). Game Theory (Translated from the Hebrew by Ziv Hellman and edited by Mike Borns). Cambridge University Press. 8. Salanié, B. (2005). The economics of contracts: a primer. MIT press. 9. Goubko, M., Burkov, V., Kondrat’ev, V., Korgin, N., & Novikov, D. (2013). Mechanism design and management: mathematical methods for smart organizations. New York: Nova Science Publishers 10. Burkov V. N., & Kondratyev V. V. (1981) Mechanisms of functioning of organizational systems. - Moscow: Science. 11. Ponomarev, V. A. & Rossikhina , L.V. (2018) Applied modeling of the mechanism of inverse priorities in the tasks of resource allocation using active experiment. Bulletin of the Voronezh Institute of the Federal penitentiary service of Russia, 2, 94–99. 12. Ponomarev V. A. (2018) A game-theoretic models of resource allocation. Bulletin of the Voronezh Institute of the Federal penitentiary service of Russia, 4, 98–105.