Optimal decision-making with minimal waste: strategyproof redistribution of VCG payments

ABSTRACT

Mechanisms for coordinating group decision-making among self-interested agents often employ a trusted center, capable of enforcing the prescribed outcome. Typically such mechanisms, including the ubiquitous Vickrey Clarke Groves (VCG), require significant transfer payments from agents to the center. While this is sought after in some settings, it is often an unwanted cost of implementation. We propose a modification of the VCG framework that---by using domain information regarding agent valuation spaces---is often able to achieve redistribution of much of the required transfer payments back among the agents, thus coming closer to budget-balance. The proposed mechanism is strategyproof, ex post individual rational, no-deficit, and leads to an efficient outcome; we prove that among all mechanisms with these qualities and an anonymity property it is optimally balanced, in that no mechanism ever yields greater payoff to the agents. We provide a general characterization of when strategyproof redistribution is possible, and demonstrate specifically that substantial redistribution can be achieved in allocation problems.

REFERENCES

• 1: {Bailey, 1997} Martin J. Bailey. The demand revealing process: To distribute the surplus. Public Choice, 91:107--126, 1997.
• 2: {Clarke, 1971} Edward Clarke. Multipart pricing of public goods. Public Choice, 8:19--33, 1971.
• 3: {d'Aspremont and Gerard-Varet, 2002} Claude d'Aspremont and Louis-Andre Gerard-Varet. Incentives and incomplete information. In Game Theory in the Tradition of Bob Wilson, 2002.
• 4: {Faltings, 2004} Boi Faltings. A budget-balanced, incentive-compatible scheme for social choice. In Agent-mediated E-commerce AMEC, 2004.
• 5: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 6: {Green and Laffont, 1977} Jerry Green and Jean-Jacques Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45:427--438, 1977.
• 7: {Groves, 1973} Theodore Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 8: {Holmstrom, 1979} Bengt Holmstrom. Groves' scheme on restricted domains. Econometrica, 47(5):1137--1144, 1979.
• 9: {Hurwicz, 1975} Leonid Hurwicz. On the existence of allocation systems whose manipulative nash equilibria are pareto optimal. (presented at the 3rd World Congress of the Econometric Society), 1975.
• 10: {Krishna and Perry, 1998} Vijay Krishna and Motty Perry. Efficient mechanism design. Game theory and information, Economics Working Paper Archive at WUSTL, December 1998.
• 11: {Myerson and Satterthwaite, 1983} Roger Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 28:265--281, 1983.
• 12: {Parkes et al., 2001} David C. Parkes, J. R. Kalagnanam, and M. Eso. Achieving budget-balance with vickrey-based payment schemes in exchanges. In Proc. 17th Int. Joint Conf. on Artificial Intelligence, pages 1161--1168, 2001.
• 13: Adrian Petcu , Boi Faltings , David C. Parkes, MDPOP: faithful distributed implementation of efficient social choice problems, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160895]
• 14: Jeffrey Shneidman , David C. Parkes, Specification faithfulness in networks with rational nodes, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011781]
• 15: {Vickrey, 1961} William Vickrey. Counterspeculations, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

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

General Terms:
Algorithms, Economics, Theory

Keywords:
VCG, mechanism design, social choice