EUVIMEDEUVIMED entdecken
Crossref

Approximate Mechanism Design without Money

Ariel D. Procaccia, Moshe Tennenholtz

ACM Transactions on Economics and Computation · 2013-12 · 1 (4) · 1-26

DOI: 10.1145/2542174.2542175 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, 2013-12. Verfasst von Ariel D. Procaccia und 1 weiteren Autor:innen. Die Arbeit wurde bisher 129-mal zitiert (Crossref) und nennt 58 Literaturangaben. Gefördert von: Division of Computing and Communication Foundations.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The literature on algorithmic mechanism design is mostly concerned with game-theoretic versions of optimization problems to which standard economic money-based mechanisms cannot be applied efficiently. Recent years have seen the design of various truthful approximation mechanisms that rely on payments. In this article, we advocate the reconsideration of highly structured optimization problems in the context of mechanism design. We explicitly argue for the first time that, in such domains, approximation can be leveraged to obtain truthfulness without resorting to payments. This stands in contrast to previous work where payments are almost ubiquitous and (more often than not) approximation is a necessary evil that is required to circumvent computational complexity. We present a case study in approximate mechanism design without money. In our basic setting, agents are located on the real line and the mechanism must select the location of a public facility; the cost of an agent is its distance to the facility. We establish tight upper and lower bounds for the approximation ratio given by strategyproof mechanisms without payments, with respect to both deterministic and randomized mechanisms, under two objective functions: the social cost and the maximum cost. We then extend our results in two natural directions: a domain where two facilities must be located and a domain where each agent controls multiple locations.

Förderung

  • Division of Computing and Communication Foundations

Zitieren

APA

Procaccia, A. D., & Tennenholtz, M. (2013). Approximate Mechanism Design without Money. ACM Transactions on Economics and Computation, 1(4), 1-26. https://doi.org/10.1145/2542174.2542175

Vancouver

Procaccia AD, Tennenholtz M. Approximate Mechanism Design without Money. ACM Transactions on Economics and Computation. 2013;1(4):1-26. doi:10.1145/2542174.2542175

BibTeX
@article{Procaccia2013,
  author = {Procaccia, Ariel D. and Tennenholtz, Moshe},
  title = {Approximate Mechanism Design without Money},
  journal = {ACM Transactions on Economics and Computation},
  year = {2013},
  volume = {1},
  number = {4},
  pages = {1--26},
  doi = {10.1145/2542174.2542175}
}
Kostenlos starten →