Undominated VCG redistribution mechanisms

ABSTRACT

Many important problems in multiagent systems can be seen as resource allocation problems. For such problems, the well-known Vickrey-Clarke-Groves (VCG) mechanism is efficient, incentive compatible, individually rational, and does not incur a deficit. However, the VCG mechanism is not (strongly) budget balanced: generally, the agents' payments will sum to more than 0. Very recently, several mechanisms have been proposed that redistribute a significant percentage of the VCG payments back to the agents while maintaining the other properties. This increases the agents' utilities.

One redistribution mechanism dominates another if it always redistributes at least as much to each agent (and sometimes more). In this paper, we provide a characterization of undominated redistribution mechanisms. We also propose several techniques that take a dominated redistribution mechanism as input, and produce as output another redistribution mechanism that dominates the original. One technique immediately produces an undominated redistribution mechanism that is not necessarily anonymous. Another technique preserves anonymity, and repeated application results in an undominated redistribution mechanism in the limit. We show experimentally that these techniques improve the known redistribution mechanisms.

REFERENCES

• 1: L. M. Ausubel and P. Milgrom. The lovely but lonely Vickrey auction. In P. Cramton, Y. Shoham, and R. Steinberg, editors, Combinatorial Auctions, chapter 1. MIT Press, 2006.
• 2: M. J. Bailey. The demand revealing process: to distribute the surplus. Public Choice, 91:107--126, 1997.
• 3: Ruggiero Cavallo, Optimal decision-making with minimal waste: strategyproof redistribution of VCG payments, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160790]
• 4: S. Chakravarty and T. Kaplan. Manna from heaven or forty years in the desert: Optimal allocation without transfer payments, October 2006. Working Paper.
• 5: E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 6: V. Conitzer and T. Sandholm. Complexity of mechanism design. In Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence (UAI), pages 103--110, Edmonton, Canada, 2002.
• 7: Vincent Conitzer , Tuomas Sandholm, Failures of the VCG mechanism in combinatorial auctions and exchanges, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160729]
• 8: B. Faltings. A budget-balanced, incentive-compatible scheme for social choice. In Agent-Mediated Electronic Commerce (AMEC), LNAI, 3435, pages 30--43, 2005.
• 9: 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]
• 10: J. Green and J.-J. Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45:427--438, 1977.
• 11: T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 12: Mingyu Guo , Vincent Conitzer, Worst-case optimal redistribution of VCG payments, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250915]
• 13: Mingyu Guo , Vincent Conitzer, Optimal-in-expectation redistribution mechanisms, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 14: J. Hartline and T. Roughgarden. Money burning and implementation, January 2007. Working Paper.
• 15: B. Holmström. Groves' scheme on restricted domains. Econometrica, 47(5):1137--1144, 1979.
• 16: L. Hurwicz. On the existence of allocation systems whose manipulative Nash equilibria are Pareto optimal, 1975. Presented at the 3rd World Congress of the Econometric Society.
• 17: H. Moulin. Efficient, strategy-proof and almost budget-balanced assignment, March 2007. Working Paper.
• 18: R. Myerson and M. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 28:265--281, 1983.
• 19: D. Parkes, J. Kalagnanam, and M. Eso. Achieving budget-balance with Vickrey-based payment schemes in exchanges. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI), pages 1161--1168, Seattle, WA, 2001.
• 20: R. Porter, Y. Shoham, and M. Tennenholtz. Fair imposition. Journal of Economic Theory, 118:209--228, 2004.
• 21: B. Rastegari, A. Condon, and K. Leyton-Brown. Revenue monotonicity in combinatorial auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI), Vancouver, BC, Canada, 2007.
• 22: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.
• 23: M. Yokoo. The characterization of strategy/false-name proof combinatorial auction protocols: Price-oriented, rationing-free protocol. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), pages 733--742, Acapulco, Mexico, 2003.
• 24: Makoto Yokoo , Yuko Sakurai , Shigeo Matsubara, Robust combinatorial auction protocol against false-name bids., Artificial Intelligence, v.130 n.2, p.167-181, 08/01/2001 [doi>10.1016/S0004-3702(01)00077-7]
• 25: M. Yokoo, Y. Sakurai, and S. Matsubara. The effect of false-name bids in combinatorial auctions: New fraud in Internet auctions. Games and Economic Behavior, 46(1):174--188, 2004.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Economics, Theory

Keywords:
Vickrey-Clarke-Groves mechanism, comparing and improving redistribution mechanisms, mechanism design, payment redistribution