The Price of Truth: Frugality in Truthful Mechanisms
Lists
Only you see this
Abstract
The celebrated Vickrey-Clarke-Grove(VCG) mechanism induces selfish agents to behave truthfully by paying them a premium. In the process, it may end up paying more than the actual cost to the agents. For the minimum spanning tree problem, if the market is “competitive”, one can show that VCG never pays too much. On the other hand, for the shortest s-t path problem, Archer and Tardos [5] showed that VCG can overpay by a factor of Ω(n). A natural question that arises then is: For what problems does VCG overpay by a lot? We quantify this notion of overpayment, and show that the class of instances for which VCG never overpays is a natural generalization of matroids, that we call frugoids. We then give some sufficient conditions to upper bound and lower bound the overpayment in other cases, and apply these to several important combinatorial problems. We also relate the overpayment in an suitable model to the locality ratio of a natural local search procedure.
BibTeX
@inproceedings{talwar2003price,
author = {Kunal Talwar},
title = {{The Price of Truth: Frugality in Truthful Mechanisms}},
booktitle = {STACS},
year = {2003},
url = {https://openreview.net/forum?id=eqgKHpDGrBF},
}Loading related content...