Computing The Sub-game Perfect Nash Equilibriums In Parallel Allocation Indivisible Item

Resource allocation is a long-term problem facing human society.Economic,political and survival pressures require us to do more with less resources and to do it more fairly.On the other hand,in recent years,the problem of multi-agent resource allocation has become a research hotspot in the field of artificial intelligence.Many related works are aimed at designing a programmatic resource allocation system with execution efficiency,and analyzing the strategic behavior of intelligent agents from the perspective of computational complexity.A “good” distribution plan often needs to balance economic benefits with social equality.In economics,most related research focuses on the existence of "good" distribution schemes on mathematical models.In the field of computer science and artificial intelligence,scholars are more concerned about the computational efficiency of allocation schemes.Therefore,a comprehensive study of the design of distribution systems for multiple Agents from the three dimensions(computing efficiency,economic efficiency and social equality)is a trend and challenge for the cross development of modern economics and artificial intelligence in their core research directions.How to design a multi-Agent resource allocation mechanism that satisfies computing efficiency,economic benefits and social equality has always been one of the focuses in the field of economics and artificial intelligence.Our research work is carried out under a parallel allocation system.The system is very simple and insensitive to the identity of Agents.In each round of parallel allocation,each Agent reports its favorite one from the remaining items according to its own preference.If a remaining item is only reported by a single agent,then the agent will get the item;otherwise,the ownership of the item will be determined by the drawing of all the agents reporting the item.The main work and research results of this article are as follows:(1)Further study the parallel allocation system and propose a method for constructing a game tree.This method can construct a game tree that describes the entire allocation process.At the same time,the attributes of the game tree are also researched,and the corresponding relationship between the total number of branches of the game tree and the number of allocated items is found.(2)We also study the situation where two agents allocate items with complete information(that is,both sides of the distribution know the other agent's preference),and find the perfect Nash equilibrium of the subgame by inverse induction and parallel distribution of the game tree(SPNE)results.At the same time,propose a calculation method that directly calculates the two agents' picking strategies through partial order of both sides to achieve the perfect Nash equilibrium of the subgame,and propose a polynomial algorithm for computing the subgame perfect nash equilibriums in parallel allocation indivisible items and verify its correctness and completeness.