2019/09/15 by Mingyu Xiao, Xiao, Mingyu, Jiaxing Ling +1 · 2 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1909.06747
openalex publication_date 2019/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sequential allocation is a simple and widely studied mechanism to allocate indivisible items in turns to agents according to a pre-specified picking sequence of agents. At each turn, the current agent in the picking sequence picks its most preferred item among all items having not been allocated yet. This problem is well-known to be not strategyproof, i.e., an agent may get more utility by reporting an untruthful preference ranking of items. It arises the problem: how to find the best response of an agent? It is known that this problem is polynomially solvable for only two agents and NP-complete for arbitrary number of agents. The computational complexity of this problem with three agents was left as an open problem. In this paper, we give a novel algorithm that solves the problem in polynomial time for each fixed number of agents. We also show that an agent can always get at least half of its optimal utility by simply using its truthful preference as the response.