Aaron Archer
Éva Tardos
Abstract
We consider the problem of selecting a low-cost s - t path in a graph where the edge costs are a secret, known only to the various economic agents who own them. To solve this problem, Nisan and Ronen applied the celebrated Vickrey-Clarke-Groves (VCG) mechanism, which pays a premium to induce the edges so as to reveal their costs truthfully. We observe that this premium can be unacceptably high. There are simple instances where the mechanism pays Θ(n) times the actual cost of the path, even if there is an alternate path available that costs only (1 + ϵ) times as much. This inspires the frugal path problem, which is to design a mechanism that selects a path and induces truthful cost revelation, without paying such a high premium.
This article contributes negative results on the frugal path problem. On two large classes of graphs, including those having three node-disjoint s - t paths, we prove that no reasonable mechanism can always avoid paying a high premium to induce truthtelling. In particular, we introduce a general class of min function mechanisms, and show that all min function mechanisms can be forced to overpay just as badly as VCG. Meanwhile, we prove that every truthful mechanism satisfying some reasonable properties is a min function mechanism.
Our results generalize to the problem of hiring a team to complete a task, where the analog of a path in the graph is a subset of the agents constituting a team capable of completing the task.
- Archer, A., Papadimitriou, C., Talwar, K., and Tardos, &Eactue;. 2004. An approximate truthful mechanism for combinatorial auctions with single parameter agents. Internet Math. 1, 129--150.Google Scholar
Cross Ref
- Archer, A., and Tardos, &Eactue;. 2001. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. 482--491. Google ScholarDigital Library
- Archer, A., and Tardos, &Eactue;. 2002. Frugal path mechanisms. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 991--999. Google ScholarDigital Library
- Archer, A. F. 2004. Mechanisms for discrete optimization with rational agents. Ph.D. thesis, Cornell University, Ithaca, NY. Google ScholarDigital Library
- Bikhchandani, S., de Vries, S., Schummer, J., and Vohra, R. V. 2002. Linear programming and Vickrey auctions. In Mathematics of the Internet: E-Auction and Markets, B. Dietrich and R. V. Vohra, Eds. IMA Volumes in Mathematics and its Applications, vol. 127. Springer-Verlag, New York. 75--116.Google Scholar
- Clarke, E. H. 1971. Multipart pricing of public goods. Public Choice 8, 17--33.Google ScholarCross Ref
- Czumaj, A., and Ronen, A. 2004. On the expected payment of mechanisms for task allocation. In Proceedings of the 2004 ACM Symposium on Principles of Distributed Computing. 98--106. Google ScholarDigital Library
- DeVries, S., and Vohra, R. 2003. Combinatorial auctions: A survey. INFORMS J. Comput. 15, 284--309. Google ScholarDigital Library
- Elkind, E., Goldberg, L. A., and Goldberg, P. W. 2006. Frugality ratios and improved truthful mechanisms for vertex cover. http://arxiv.org/abs/cs.GT/0606044.Google Scholar
- Elkind, E., Sahai, A., and Steiglitz, K. 2004. Frugality in path auctions. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms. 701--709. Google ScholarDigital Library
- Feigenbaum, J., Papadimitriou, C., Sami, R., and Shenker, S. 2005. A BGP-based mechanism for lowest-cost routing. Distrib. Comput. 18, 1, 61--72. Google ScholarDigital Library
- Fudenberg, D., and Tirole, J. 1991. Game Theory. MIT Press, Cambridge, MA.Google Scholar
- Garg, R., Kumar, V., Rudra, A., and Verma, A. 2003. Coalitional games on graphs: Core structure, substitutes and frugality. In Proceedings of the 5th ACM Conference on Electronic Commerce. 248--249. Google ScholarDigital Library
- Groves, T. 1973. Incentives in teams. Econometrica 41, 617--631.Google ScholarCross Ref
- Groves, T. 1982. On theories of incentive compatible choice with compensation. In Advance in Econonic Theory. Cambridge University Press, New York. 1--29.Google Scholar
- Hershberger, J., and Suri, S. 2001. Vickrey prices and shortest paths: What is an edge worth? In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. 252--259. Google ScholarDigital Library
- Hildenbrand, W., Ed. 1982. Advances in Economic Theory. Cambridge University Press, New York.Google Scholar
- Immorlica, N., Karger, D. R., Nikolova, E., and Sami, R. 2005. First-Price path auctions. In Proceedings of the 7th ACM Conference on Electronic Commerce. 203--212. Google ScholarDigital Library
- Karger, D. R., and Nikolova, E. 2005. Brief announcement: On the expected overpayment of VCG mechanisms in large networks. In Proceedings of the 2005 ACM Symposium on Principles of Distributed Computing. 126. Google ScholarDigital Library
- Karlin, A. R., Kempe, D., and Tamir, T. 2005. Beyond VCG: Frugality of truthful mechanisms. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. 615--626. Google ScholarDigital Library
- Krishna, V. 2002. Auction Theory. Academic Press, New York.Google Scholar
- Laffont, J.-J., and Maskin, E. 1982. The theory of incentives: An overview. In Advance in Econonic Theory. Cambridge University Press, New York. 31--94.Google Scholar
- Lavi, R., Mu'alem, A., and Nisan, N. 2003. Towards a characterization of truthful combinatorial auctions. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science. 574--583. Google ScholarDigital Library
- Mas-Collel, A., Whinston, M., and Green, J. 1995. Microeconomic Theory. Oxford University Press.Google Scholar
- Mihail, M., Papadimitriou, C. H., and Saberi, A. 2006. On certain connectivity properties of the internet topology. J. Comput. Syst. Sci. 72, 2, 239--251. Google ScholarDigital Library
- Nisan, N., and Ronen, A. 2000. Computationally feasible VCG mechanisms. In Proceedings of the 2nd ACM Conference on Electronic Commerce. 242--252. Google ScholarDigital Library
- Nisan, N., and Ronen, A. 2001. Algorithmic mechanism design. Games and Economic Behavior 35, 166--196.Google ScholarCross Ref
- Osborne, M. J., and Rubinstein, A. 1994. A Course in Game Theory. MIT Press, Cambridge, MA.Google Scholar
- Papadimitriou, C. H. 2001. Algorithms, games, and the Internet. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing. 749--753. Google ScholarDigital Library
- Roberts, K. 1979. The characterization of implementable choice rules. In Aggregation and Revelation of Preferences, J.-J. Laffont, Ed. North-Holland, Amsterdam. 321--348.Google Scholar
- Talwar, K. 2003. The price of truth: Frugality in truthful mechanisms. In 20th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2607. Springer-Verlag, Heidelberg, 608--619. Google ScholarDigital Library
- Vickrey, W. 1961. Counterspeculation, auctions and competitive sealed tenders. J. Finance 16, 8--37.Google ScholarCross Ref
Index Terms
- Frugal path mechanisms
Recommendations
A robust combinatorial auction mechanism against shill bidders
AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systemsThis paper presents a method for discovering and detecting shill bids in combinatorial auctions. The Vickrey-Clarke-Groves Mechanism is one of the most important combinatorial auctions because it can satisfy the strategy-proof property, individual ...
Optimal-in-expectation redistribution mechanisms
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2Many important problems in multiagent systems involve the allocation of multiple resources to multiple agents. If agents are self-interested, they will lie about their valuations for the resources if they perceive this to be in their interest. The well-...
Frugal path mechanisms
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithmsWe consider the problem of selecting a low cost s --- t path in a graph, where the edge costs are a secret known only to the various economic agents who own them. To solve this problem, Nisan and Ronen applied the celebrated Vickrey-Clarke-Groves (VCG) ...
Comments