Worst-case optimal redistribution of VCG payments

ABSTRACT

For allocation problems with one or more items, the well-known Vickrey-Clarke-Groves (VCG) mechanism is efficient, strategy-proof, 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. If there is an auctioneer who is selling the items, this may be desirable, because the surplus payment corresponds to revenue for the auctioneer. However, if the items do not have an owner and the agents are merely interested in allocating the items efficiently among themselves, any surplus payment is undesirable, because it will have to flow out of the system of agents. In 2006, Cavallo [3] proposed a mechanism that redistributes some of the VCG payment back to the agents, while maintaining efficiency, strategy-proofness, individual rationality, and the non-deficit property. In this paper, we extend this result in a restricted setting. We study allocation settings where there are multiple indistinguishable units of a single good, and agents have unit demand. (For this specific setting, Cavallo's mechanism coincides with a mechanism proposed by Bailey in 1997 [2].) Here we propose a family of mechanisms that redistribute some of the VCG payment back to the agents. All mechanisms in the family are efficient, strategy-proof, individually rational, and never incur a deficit. The family includes the Bailey-Cavallo mechanism as a special case. We then provide an optimization model for finding the optimal mechanism--that is, the mechanism that maximizes redistribution in the worst case--inside the family, and show how to cast this model as a linear program. We give both numerical and analytical solutions of this linear program, and the (unique) resulting mechanism shows significant improvement over the Bailey-Cavallo mechanism (in the worst case). Finally, we prove that the obtained mechanism is optimal among all anonymous deterministic mechanisms that satisfy the above properties.

REFERENCES

• 1: Gagan Aggarwal , Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Nicole Immorlica , Madhu Sudan, Derandomization of auctions, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060682]
• 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: E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 5: B. Faltings. A budget-balanced, incentive-compatible scheme for social choice. AMEC, 30--43, 2005.
• 6: 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]
• 7: Eric J. Friedman , David C. Parkes, Pricing WiFi at Starbucks: issues in online mechanism design, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779978]
• 8: A. Goldberg, J. Hartline, A. Karlin, M. Saks, and A. Wright. Competitive auctions. Games and Economic Behavior, 2006.
• 9: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 10: D. A. Graham and R. C. Marshall. Collusive bidder behavior at single-object second-price and English auctions. Journal of Political Economy, 95(6):1217--1239, 1987.
• 11: J. Green and J.-J. Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45:427--438, 1977.
• 12: T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 13: Mohammad T. Hajiaghayi, Online auctions with re-usable goods, Proceedings of the 6th ACM conference on Electronic commerce, p.165-174, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064027]
• 14: Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988784]
• 15: Jason D. Hartline , Robert McGrew, From optimal limited to unlimited supply auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.175-182, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064028]
• 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: Kevin Leyton-Brown , Yoav Shoham , Moshe Tennenholtz, Bidding clubs in first-price auctions, Eighteenth national conference on Artificial intelligence, p.373-378, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 18: E. Maskin and J. Riley. Optimal multi-unit auctions. In F. Hahn, editor, The Economics of Missing Markets, Information, and Games, chapter 14, 312--335. Clarendon Press, Oxford, 1989.
• 19: H. Moulin. Efficient and strategy-proof assignment with a cheap residual claimant. Working paper, March 2007.
• 20: R. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58--73, 1981.
• 21: R. Myerson and M. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 28:265--281, 1983.
• 22: D. Parkes, J. Kalagnanam, and M. Eso. Achieving budget-balance with Vickrey-based payment schemes in exchanges. IJCAI, 1161--1168, 2001.
• 23: 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
            Subjects: Multiagent systems

General Terms:
Algorithms, Economics, Theory

Keywords:
Vickrey-Clarke-Groves mechanism, mechanism design, payment redistribution