Research On The Game Problem Between Two-Agent Under Parallel Allocation

How to allocate the limited resources reasonably,efficiently and fairly has always been a difficult problem in social life.When agents involved in resource allocation know the preference information of other participants,in order to maximize their own benefits,agents will choose deceptive strategies to obtain better bundles of items.Manipulation becomes a game when all agents choose to manipulate other players.The game problem studied in this paper is based on the parallel allocation system,which is a basic allocation mechanism based on rotation and insensitive to the identities of the players.All the agents involved in the distribution can declare an item at the same time.When the item is declared by only one agent,the declaring agent will get the item.Otherwise,all the agents who declare the item will draw lots to decide the final ownership of the item.This paper mainly studies the game between two agents under parallel allocation.We construct a three-layer game tree by using the items declared by the two agents participating in the game in the first round,calculate the benefits of the two agents in leaf nodes of the game tree in turn and find a path(from the root to a leaf node)that is a subgame-perfect Nash equilibrium.Formally,we prove that a subgame-perfect Nash equilibrium can be compute by reversing the sequence obtained from the reverse declaration of the least liked object of the other party.In addition,a polynomial algorithm is designed to find a subgameperfect Nash equilibrium strategy under parallel allocation,and the effectiveness of the algorithm is verified by simulation experiments.Considering that there is an extreme case in parallel allocation,where both agents have the same preference order and one agent wins the lot all the time,then he gets all the items and the another gets none.This is unfair.The loser reporting policy is introduced to ensure that the difference in the number of items obtained by the two sides of the game is not more than 1.This paper studies the expected bundle of items under the loser declaration system,and proves that there is no method only considering agents’ preference order can calculate the subgame-perfect Nash equilibrium under the loser reporting policy.