No truthful mechanism can be better than n approximate for two natural problems

Stefano Leucci, Akaki Mamageishvili and Paolo Penna

Games and Economic Behavior, 2018, vol. 111, issue C, 64-74

Abstract: This work gives the first natural non-utilitarian problems for which the trivial napproxima-tion via VCG mechanisms is the best possible. That is, no truthful mechanism can be better than n approximate, where n is the number of agents. The problems we study are the min-max variant of the shortest path and the (directed) minimum spanning tree mechanism design problems. In these procurement auctions, agents own the edges of a network, and the corresponding edge costs are private. Instead of the total weight of the subnetwork, in the min-max variant we aim to minimize the maximum agent cost.

Keywords: Mechanism design; Truthful mechanisms; Inapproximability; Non-utilitarian problems; Lower bounds (search for similar items in EconPapers)
JEL-codes: C72 D4 D82 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S089982561830071X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:111:y:2018:i:c:p:64-74

DOI: 10.1016/j.geb.2018.05.003

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().