Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Competitive repeated allocation without payments
Author: Guo, M.
Conitzer, V.
Reeves, D.
Citation: Lecture Notes in Artificial Intelligence, 2009 / Stefano Leonardi (ed./s), pp.244-255
Publisher: Springer
Publisher Place: Berlin, Germany
Issue Date: 2009
ISBN: 9783642108402
ISSN: 0302-9743
Conference Name: International Workshop on Internet and Network Economics (WINE) (14 Dec 2009 - 18 Dec 2009 : Rome, Italy)
Editor: Stefano Leonardi
Statement of
Mingyu Guo, Vincent Conitzer, and Daniel M. Reeves
Abstract: We study the problem of allocating a single item repeatedly among multiple competing agents, in an environment where monetary transfers are not possible. We design (Bayes-Nash) incentive compatible mechanisms that do not rely on payments, with the goal of maximizing expected social welfare. We first focus on the case of two agents. We introduce an artificial payment system, which enables us to construct repeated allocation mechanisms without payments based on one-shot allocation mechanisms with payments. Under certain restrictions on the discount factor, we propose several repeated allocation mechanisms based on artificial payments. For the simple model in which the agents’ valuations are either high or low, the mechanism we propose is 0.94-competitive against the optimal allocation mechanism with payments. For the general case of any prior distribution, the mechanism we propose is 0.85-competitive. We generalize the mechanism to cases of three or more agents. For any number of agents, the mechanism we obtain is at least 0.75-competitive. The obtained competitive ratios imply that for repeated allocation, artificial payments may be used to replace real monetary payments, without incurring too much loss in social welfare.
Rights: © Springer-Verlag Berlin Heidelberg 2009
DOI: 10.1007/978-3-642-10841-9
Appears in Collections:Aurora harvest 7
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.