Strategy-proof allocation of multiple items between two agents without payments or priors


Conference Paper

We investigate the problem of allocating items (private goods) among competing agents in a setting that is both prior-free and payment-free. Specificall, we focus on allocating multiple heterogeneous items between two agents with additive valuation functions. Our objective is to design strategy-proof mechanisms that are competitive against the most efficien (first-best allocation. We introduce the family of linear increasing-price (LIP) mechanisms. The LIP mechanisms are strategy-proof, prior-free, and payment-free, and they are exactly the increasing-price mechanisms satisfying a strong responsiveness property. We show how to solve for competitive mechanisms within the LIP family. For the case of two items, we fin a LIP mechanism whose competitive ratio is near optimal (the achieved competitive ratio is 0.828, while any strategy-proof mechanism is at most 0.841-competitive). As the number of items goes to infinit, we prove a negative result that any increasing-price mechanism (linear or nonlinear) has a maximal competitive ratio of 0.5. Our results imply that in some cases, it is possible to design good allocation mechanisms without payments and without priors. Copyright © 2010, International Foundation for Autonomous Agents and Multiagent Systems ( All rights reserved.

Duke Authors

Cited Authors

  • Guo, M; Conitzer, V

Published Date

  • January 1, 2010

Published In

Volume / Issue

  • 2 /

Start / End Page

  • 881 - 888

Electronic International Standard Serial Number (EISSN)

  • 1558-2914

International Standard Serial Number (ISSN)

  • 1548-8403

International Standard Book Number 13 (ISBN-13)

  • 9781617387715

Citation Source

  • Scopus