Optimal-in-expectation redistribution mechanisms

ABSTRACT

Many 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-known VCG mechanism allocates the items efficiently, is incentive compatible (agents have no incentive to lie), and never runs a deficit. Nevertheless, the agents may have to make large payments to a party outside the system of agents, leading to decreased utility for the agents. Recent work has investigated the possibility of redistributing some of the payments back to the agents, without violating the other desirable properties of the VCG mechanism.

We study multi-unit auctions with unit demand, for which previously a mechanism has been found that maximizes the worst-case redistribution percentage. In contrast, we assume that a prior distribution over the agents' valuations is available, and try to maximize the expected total redistribution. We analytically solve for a mechanism that is optimal among linear redistribution mechanisms. The optimal linear mechanism is asymptotically optimal. We also propose discretization redistribution mechanisms. We show how to automatically solve for the optimal discretization redistribution mechanism for a given discretization step size, and show that the resulting mechanisms converge to optimality as the step size goes to zero. We also present experimental results showing that for auctions with many bidders, the optimal linear redistribution mechanism redistributes almost everything, whereas for auctions with few bidders, we can solve for the optimal discretization redistribution mechanism with a very small step size.

REFERENCES

• 1: M. J. Bailey. The demand revealing process: to distribute the surplus. Public Choice, 91:107--126, 1997.
• 2: 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]
• 3: S. Chakravarty and T. Kaplan. Manna from heaven or forty years in the desert: Optimal allocation without transfer payments, October 2006. Working Paper.
• 4: E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 5: 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.
• 6: C. d'Aspremont and L.-A. Gérard-Varet. Incentives and incomplete information. Journal of Public Economics, 11:25--45, 1979.
• 7: B. Faltings. A budget-balanced, incentive-compatible scheme for social choice. In Agent-Mediated Electronic Commerce (AMEC), LNAI, 3435, pages 30--43, 2005.
• 8: 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]
• 9: J. Green and J.-J. Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 1977.
• 10: T. Groves. Incentives in teams. Econometrica, 1973.
• 11: 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]
• 12: Mingyu Guo , Vincent Conitzer, Undominated VCG redistribution mechanisms, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 13: J. Hartline and T. Roughgarden. Money burning and implementation, January 2007. Working Paper.
• 14: B. Holmström. Groves' scheme on restricted domains. Econometrica, 47(5):1137--1144, 1979.
• 15: 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.
• 16: H. Moulin. Efficient, strategy-proof and almost budget-balanced assignment, March 2007. Working Paper.
• 17: R. Myerson and M. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 28:265--281, 1983.
• 18: 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.
• 19: R. Porter, Y. Shoham, and M. Tennenholtz. Fair imposition. Journal of Economic Theory, 118:209--228, 2004. Early version appeared in IJCAI-01.
• 20: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.

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, mechanism design, payment redistribution, prior distributions over preferences