Undominated groves mechanisms
Published
Journal Article
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. © 2013 AI Access Foundation. All rights reserved.
Full Text
Duke Authors
Cited Authors
- Guo, M; Markakis, E; Apt, KR; Conitzer, V
Published Date
- January 1, 2013
Published In
Volume / Issue
- 46 /
Start / End Page
- 129 - 163
Electronic International Standard Serial Number (EISSN)
- 1076-9757
Digital Object Identifier (DOI)
- 10.1613/jair.3810
Citation Source
- Scopus