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.
Supported in part by NSF grants CCR-0105533 and CCR-9820897.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lawrence M. Ausubel, “An Efficient Ascending-Bid Auction for Multiple Objects,” Working Paper, University of Maryland, Department of Economics, 1997.
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit, “Local search heuristics for k-median and facility location problems”, Proceedings of the 33rd ACM symposium on the theory of computing, 2001.
Aaron Archer, Christos Papadimitriou, Kunal Talwar, Éva Tardos, “An approximate truthful mechanism for combinatorial auctions with single parameter agents”, To appear in SODA 2003
Aaron Archer, Éva Tardos “Truthful mechanisms for one-parameter agents”,Proceedings of the 42nd IEEE annual symposium on Foundations of Computer Science, 2001.
Aaron Archer, Éva Tardos “Frugal Path Mechanisms”, SODA 2002.
Sushil Bikhchandani, Sven de Vries, James Schummer, Rakesh Vohra “Linear Programming and Vickrey Auctions,” IMA Volumes in Mathematics and its Applications, Mathematics of the Internet: E-Auction and Markets, 127:75–116, 2001.
Sushil Bikhchandani, Joseph M. Ostroy, “The package assignment model”, working paper, 2001.
E. H. Clarke “Multipart pricing of public goods”, Public Choice, 8:17–33, 1971.
Edith Elkind, Amit Sahai, “Shortest Paths are costly”, manuscript, October 2002.
Joan Feigenbaum, Christos Papadimitriou, and Scott Shenker, “Sharing the cost of multicast transmissions”, Journal of Computer and System Sciences 63:21–41, 2001.
Theodore Groves “Incentives in teams”, Econometrica, 41(4):617–631, 1973.
Rahul Garg, Vijay Kumar, Atri Rudra and Akshat Verma, “When can we devise frugal mechanisms for network design problems?”, manuscript, 2002.
Philip Hall, “On representatives of subsets,” Journal of London Mathematics Society, 10:26–30, 1935.
Frank Harary, “Graph Theory”, Addison Wesley, 1971.
John Hershberger, Subhash Suri, “. Vickrey Pricing in network routing: Fast payment computation”, Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 2001.
Daniel Lehmann, Liadan Ita O’Callaghan, Yoav Shoham “Truth revelation in rapid approximately efficient combinatorial auctions”, 1st ACM conference on electronic commerce, 1999
Ahuva Mu’alem, Noam Nisan “Truthful approximation mechanism for restricted combinatorial auctions”, to appear in AAAI 2002
Andreu Mas-Colell, Michael D. Whinston, Jerry R. Green “, Microeconomic Theory”, Oxford University Press, 1995.
Noam Nisan, Amir Ronen “Algorithmic mechanism design”, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999.
Noam Nisan, Amir Ronen “Computationally feasible VCG mechanisms”, ACM conference on electronic commerce, 242–252, 2000.
Martin J. Osborne, Ariel Rubinstein “A course in game theory”, MIT Press, Cambridge, 1994.
Christos Papadimitriou “Algorithms, games and the Internet”, Proceedings of the 33rd Annual ACM Symposium on Theory of Computation, 749–753, 2001.
David Parkes, Lyle Ungar, “Iterative Combinatorial Auctions: Theory and Practice”, In Proc. 17th National Conference on Artificial Intelligence, (AAAI-00) pp. 74–81, 2000.
William Vickrey “Counterspeculation, auctions and competitive sealed tenders”, Journal of Finance, 16:8–37, 1961.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Talwar, K. (2003). The Price of Truth: Frugality in Truthful Mechanisms. In: Alt, H., Habib, M. (eds) STACS 2003. STACS 2003. Lecture Notes in Computer Science, vol 2607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36494-3_53
Download citation
DOI: https://doi.org/10.1007/3-540-36494-3_53
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00623-7
Online ISBN: 978-3-540-36494-8
eBook Packages: Springer Book Archive