Strategy-proof Allocation of Multiple Items between Two Agents without Payments or Priors

We investigate the problem of allocating items (private goods) amongcompeting agents in a setting that is both prior-free and payment-free. Specifically, we focus on allocating multiple heterogeneousitems between two agents with additive valuation functions. Ourobjective is to design strategy-proof mechanisms that are competitive against the most efficient (first-best) allocation. We introduce the family of linear increasing-price (LIP) mechanisms. TheLIP mechanisms are strategy-proof, prior-free, and payment-free, and they are exactly the increasing-price mechanisms satisfying astrong responsiveness property. We show how to solve for competitive mechanisms within the LIP family. For the case of two items, we find a LIP mechanism whose competitive ratio is near optimal(the achieved competitive ratio is $0. 828$, while any strategy-proofmechanism is at most $0. 841$-competitive). As the number of itemsgoes to infinity, we prove a negative result that any increasing-pricemechanism (linear or nonlinear) has a maximal competitive ratio of$0. 5$. Our results imply that in some cases, it is possible to designgood allocation mechanisms without payments and without priors.

Authors

• Mingyu Guo Adelaide University
• Vincent Conitzer Carnegie Mellon University

Keywords

No keywords are indexed for this paper.