Undominated Groves mechanisms

DOI10.1613/JAIR.3810MaRDI QIDQ4907834zbMATH OpenOpenAlexFDO

Authors Mingyu Guo, Evangelos Markakis, Krzysztof R. Apt, Vincent Conitzer

Publication date 25 February 2013

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.1809

zbMATH Keywords

Clarke mechanismGroves mechanismindividually dominatedindividually undominatedVCG

Mathematics Subject Classification ID

Agent technology and artificial intelligence (68T42) Auctions, bargaining, bidding and selling, and other market models (91B26)

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$ {em individually dominates} another non-deficit Groves mechanism $M^{\prime }$ if for every type profile, every agent's utility under $M$ is no less than that under $M^{\prime }$, and this holds with strict inequality for at least one type profile and one agent. We say that a non-deficit Groves mechanism $M$ {em collectively dominates} another non-deficit Groves mechanism $M^{\prime }$ if for every type profile, the agents' total utility under $M$ is no less than that under $M^{\prime }$, 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 {em individually undominated} mechanisms and the {em collectively undominated} mechanisms, respectively.

Recommendations

• Sequential pivotal mechanisms for public project problems
• A new characterization of the Groves-Clarke mechanism
• Vickrey-Clarke-Groves mechanisms in continuum economies. Characterization and existence
• The participatory Vickrey-Clarke-Groves mechanism
• On the uniqueness of Groves mechanisms and the payoff equivalence principle

Cited in

(19)

• Vickrey-Clarke-Groves mechanisms in continuum economies. Characterization and existence
• A new characterization of the Groves-Clarke mechanism
• Binary public decisions and undominated mechanisms
• Undominated mechanisms and the provision of a pure public good in two agent economies
• Strongly budget balanced auctions for multi-sided markets
• A Shapley-based Groves mechanism: when the mechanism designer plays the \textit{wise man}
• Constrained-optimal strategy-proof assignment: beyond the Groves mechanisms
• Optimal VCG mechanisms to assign multiple bads
• Groves mechanisms and communication externalities
• Sequential pivotal mechanisms for public project problems
• Competitive VCG redistribution mechanism for public project problem
• Better redistribution with inefficient allocation in multi-unit auctions
• Spanning tree auctions: a complete characterization
• Generalized Groves-Ledyard mechanisms
• On Groves mechanisms for costly inclusion
• Greater flexibility in mechanism design through altruism
• Comparing multiagent systems research in combinatorial auctions and voting
• Expressive markets for donating to charities
• Optimal-in-expectation redistribution mechanisms

This page was built for publication: Undominated Groves mechanisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4907834)