Undominated Groves mechanisms
Files
(Restricted Access)
Date
2013
Authors
Guo, M.
Markakis, E.
Apt, K.
Conitzer, V.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Journal of Artificial Intelligence Research, 2013; 46:129-163
Statement of Responsibility
Mingyu Guo, Evangelos Markakis, Krzysztof R. Apt, Vincent Conitzer
Conference Name
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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
©2013 AI Access Foundation. All rights reserved.