Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/90045
Citations
Scopus Web of Science® Altmetric
?
?
Type: Journal article
Title: Undominated Groves mechanisms
Author: Guo, M.
Markakis, E.
Apt, K.
Conitzer, V.
Citation: Journal of Artificial Intelligence Research, 2013; 46:129-163
Publisher: AI Access Foundation
Issue Date: 2013
ISSN: 1076-9757
1943-5037
Statement of
Responsibility: 
Mingyu Guo, Evangelos Markakis, Krzysztof R. Apt, Vincent Conitzer
Abstract: The family of Groves mechanisms, which includes the well-known VCG mechanism (also known as the Clarke mechanism), is a family of efficient and strategy-proof mechanisms. Unfortunately, the Groves mechanisms are generally not budget balanced. That is, under such mechanisms, payments may flow into or out of the system of the agents, resulting in deficits or reduced utilities for the agents. We consider the following problem: within the family of Groves mechanisms, we want to identify mechanisms that give the agents the highest utilities, under the constraint that these mechanisms must never incur deficits. We adopt a prior-free approach. We introduce two general measures for comparing mechanisms in prior-free settings. We say that a non-deficit Groves mechanism M individually dominates another non-deficit Groves mechanism M' if for every type profile, every agent's utility under M is no less than that under M', and this holds with strict inequality for at least one type profile and one agent. We say that a non-deficit Groves mechanism M collectively dominates another non-deficit Groves mechanism M' if for every type profile, the agents' total utility under M is no less than that under M', and this holds with strict inequality for at least one type profile. The above definitions induce two partial orders on non-deficit Groves mechanisms. We study the maximal elements corresponding to these two partial orders, which we call the individually undominated mechanisms and the collectively undominated mechanisms, respectively.
Rights: ©2013 AI Access Foundation. All rights reserved.
RMID: 0020134981
DOI: 10.1613/jair.3810
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_90045.pdfRestricted Access316.47 kBAdobe PDFView/Open


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