|
|||||
|
|
Strongly polynomial-time truthful mechanisms in one shot |
|
| Authors: | Paolo Penna Guido Proietti Peter Widmayer |
| Affiliation: | 1. Institut für Theoretische Informatik, ETH, Zürich, Switzerland;2. Dipartimento di Informatica ed Applicazioni “Renato M. Capocelli”, Università di Salerno, Italy;3. Dipartimento di Informatica, Università di L’Aquila, Italy;4. Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”, CNR, Roma, Italy |
| Abstract: | One of the main challenges in algorithmic mechanism design is to turn (existing) efficient algorithmic solutions into efficient truthful mechanisms. Building a truthful mechanism is indeed a difficult process since the underlying algorithm must obey certain “monotonicity” properties and suitable payment functions need to be computed (this task usually represents the bottleneck in the overall time complexity). |
| Keywords: | Algorithmic game theory Mechanism design Design and analysis of algorithms Minimum diameter spanning tree |
| 本文献已被 ScienceDirect 等数据库收录！ | |