Optimal collusion-resistant mechanisms with verification

ABSTRACT

We present the first general positive result on the construction of collusion-resistant mechanisms, that is, mechanisms that guarantee dominant strategies even when agents can form arbitrary coalitions and exchange compensations (sometimes referred to as transferable utilities or side payments). This is a much stronger solution concept as compared to truthful or even group-strategyproof mechanisms, and only impossibility results were known for this type of mechanisms in the "classical" model.

We describe collusion-resistant mechanisms with verification that return optimal solutions for a wide class of mechanism design problems (which includes utilitarian ones as a special case). Note that every collusion-resistant mechanism without verification has an unbounded approximation factor and, in general, optimal solutions cannot be obtained even if we content ourselves with truthful ("non-collusion-resistant") mechanisms. All these results apply to problems that have been extensively studied in the algorithmic mechanism design literature such as task scheduling and inter-domain routing.

REFERENCES

• 1: N. Andelman, Y. Azar, and M. Sorani. Truthful approximation mechanisms for scheduling selfish related machines. In Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS) , Lecture Notes in Computer Science, pages 69--82, 2005.
• 2: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 3: A. Archer and E. Tardos. Frugal path mechanisms. ACM Transactions on Algorithms , 3(1), 2007.
• 4: Vincenzo Auletta , Roberto De Prisco , Paolo Penna , Giuseppe Persiano, The power of verification for one-parameter agents, Journal of Computer and System Sciences, v.75 n.3, p.190-211, May, 2009 [doi>10.1016/j.jcss.2008.10.001]
• 5: V. Auletta, R. De Prisco, P. Penna, G. Persiano, and C. Ventre. New constructions of mechanisms with verification. In Proc. of International Colloquium on Automata, Languages, and Programming (ICALP), pages 596--607, 2006.
• 6: Chandra Chekuri , Sanjeev Khanna, A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.848-861, July 08-12, 2001
• 7: George Christodoulou , Elias Koutsoupias , Angelina Vidali, A lower bound for scheduling mechanisms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1163-1170, January 07-09, 2007, New Orleans, Louisiana
• 8: E.H. Clarke. Multipart Pricing of Public Goods. Public Choice, pages 17--33, 1971.
• 9: Edith Elkind , Amit Sahai , Ken Steiglitz, Frugality in path auctions, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 10: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Distributed Computing, v.18 n.1, p.61-72, July 2005 [doi>10.1007/s00446-005-0122-y]
• 11: I. Gamzu. Improved lower bounds for non-utilitarian truthfulness. In Proceedings of the 5th Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science, pages 15--26, 2007.
• 12: Andrew V. Goldberg , Jason D. Hartline, Collusion-resistant mechanisms for single-parameter agents, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: T. Groves. Incentive in Teams. Econometrica, 41:617--631, 1973.
• 14: Ellis Horowitz , Sartaj Sahni, Exact and Approximate Algorithms for Scheduling Nonidentical Processors, Journal of the ACM (JACM), v.23 n.2, p.317-327, April 1976 [doi>10.1145/321941.321951]
• 15: Anna R. Karlin , David Kempe , Tami Tamir, Beyond VCG: Frugality of Truthful Mechanisms, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.615-626, October 23-25, 2005 [doi>10.1109/SFCS.2005.25]
• 16: E. Koutsoupias and A. Vidali. A lower bound of 1+φ for truthful scheduling mechanisms. In Proceedings of the 32nd Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, pages 454--464, 2007.
• 17: Ron Lavi , Chaitanya Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250947]
• 18: Ahuva Mu'alem , Michael Schapira, Setting lower bounds on truthfulness: extended abstract, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1143-1152, January 07-09, 2007, New Orleans, Louisiana
• 19: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 20: Paolo Penna , Carmine Ventre, Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_59]
• 21: P. Penna and C. Ventre. Optimal Collusion-Resistant Mechanisms with Verification. Technical Report, 2009. Available at www.dia.unisa.it/~penna/papers/collusion.pdf'.
• 22: J. Schummer. Manipulation through bribes. Journal of Economic Theory, 91(3):180--198, 2000.
• 23: C. Ventre. Mechanisms with verification for any finite domain. In Proc. of the 2nd Workshop on Internet and Network Economics (WINE), volume 4286 of Lecture Notes in Computer Science, pages 37--49. Springer, 2006.
• 24: W. Vickrey. Counterspeculation, Auctions and Competitive Sealed Tenders. Journal of Finance, pages 8--37, 1961.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
algorithmic mechanism design, collusion, transferable utilities