Manipulations Among Two Agents Based On Allocation Policy Of Loser Reporting

In the process of Multi-Agent resource allocation,since agents will continue to pursue the maximization of their own interests,deceptive strategic behaviors will appear,such as manipulation under the parallel allocation system.Parallel allocation is one of the most fundamental mechanisms for allocating indivisible objects to agents in a decentralized manner,in which agents are allowed to parallel report their favorite objects among the remainder according to a policy that is insensitive to agent’s identities.In recent years,algorithmic issues about agent’s manipulations have been investigated,such as the computational complexity of verifying whether a manipulator can obtain a given bundle possibly,and maximizing her utility optimistically,and so on.This thesis mainly considers the allocation policy of loser reporting,in which the allocation process is divided into rounds.In each round,each agent that has obtained the smallest number of objects can report exactly one remaining object,and each reported object is allocated to one of the agents that report it at random.Since an object may be reported by multiple agents,this random allocation process can be expressed as a directed acyclic graph.Under optimistic assumption(i.e.,the manipulator can obtain an object once she reports it),we can find a polynomial time manipulation algorithm to calculate the optimal manipulation.Considering that accidents may happen in the allocation process,it is natural to expect that finding a manipulation that can consider all the possible accidents and always be optimal and optimistic in the following allocation process.This calculation problem seems to be difficult even for the case of two agents,since a manipulator may consider exponentially many possible sets of remaining objects.However,for general additive utilities,it is show that such a manipulation can be expressed as a directed acyclic graph,and be computed in polynomial time with respect to the number of objects.In addition,a polynomial manipulation algorithm is designed to find the best bundle and the optimal optimistic manipulation strategy(including accident recovery streategy),and strictly proved the correctness and completeness of the algorithm through the relevant theorems and lemma.