Skip to main content

Welfare undominated groves mechanisms

Publication ,  Journal Article
Apt, K; Conitzer, V; Guo, M; Markakis, E
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
December 1, 2008

A common objective in mechanism design is to choose the outcome (for example, allocation of resources) that maximizes the sum of the agents' valuations, without introducing incentives for agents to misreport their preferences. The class of Groves mechanisms achieves this; however, these mechanisms require the agents to make payments, thereby reducing the agents' total welfare. In this paper we introduce a measure for comparing two mechanisms with respect to the final welfare they generate. This measure induces a partial order on mechanisms and we study the question of finding minimal elements with respect to this partial order. In particular, we say a non-deficit Groves mechanism is welfare undominated if there exists no other non-deficit Groves mechanism that always has a smaller or equal sum of payments. We focus on two domains: (i) auctions with multiple identical units and unit-demand bidders, and (ii) mechanisms for public project problems. In the first domain we analytically characterize all welfare undominated Groves mechanisms that are anonymous and have linear payment functions, by showing that the family of optimal-in-expectation linear redistribution mechanisms, which were introduced in [6] and include the Bailey-Cavallo mechanism [1,2], coincides with the family of welfare undominated Groves mechanisms that are anonymous and linear in the setting we study. In the second domain we show that the classic VCG (Clarke) mechanism is welfare undominated for the class of public project problems with equal participation costs, but is not undominated for a more general class. © 2008 Springer Berlin Heidelberg.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

December 1, 2008

Volume

5385 LNCS

Start / End Page

426 / 437

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Apt, K., Conitzer, V., Guo, M., & Markakis, E. (2008). Welfare undominated groves mechanisms. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5385 LNCS, 426–437. https://doi.org/10.1007/978-3-540-92185-1_48
Apt, K., V. Conitzer, M. Guo, and E. Markakis. “Welfare undominated groves mechanisms.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5385 LNCS (December 1, 2008): 426–37. https://doi.org/10.1007/978-3-540-92185-1_48.
Apt K, Conitzer V, Guo M, Markakis E. Welfare undominated groves mechanisms. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008 Dec 1;5385 LNCS:426–37.
Apt, K., et al. “Welfare undominated groves mechanisms.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5385 LNCS, Dec. 2008, pp. 426–37. Scopus, doi:10.1007/978-3-540-92185-1_48.
Apt K, Conitzer V, Guo M, Markakis E. Welfare undominated groves mechanisms. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008 Dec 1;5385 LNCS:426–437.

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

December 1, 2008

Volume

5385 LNCS

Start / End Page

426 / 437

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences