Stepwise randomized combinatorial auctions achieve revenue monotonicity

ABSTRACT

In combinatorial auctions that use VCG, a seller can sometimes increase revenue by dropping bidders (see e.g. [5]). In our previous work [26], we showed that such failures of "revenue monotonicity" occur under an extremely broad range of deterministic strategyproof combinatorial auction mechanisms, even when bidders have "known single-minded" valuations. In this work we consider the question of whether revenue monotonic, strategyproof mechanisms for such bidders can be found in the broader class of randomized mechanisms. We demonstrate that---surprisingly- such mechanisms do exist, show how they can be constructed, and consider algorithmic techniques for implementing them in polynomial time.

More formally, we characterize a class of randomized mechanisms defined for known single-minded bidders that are strategyproof and revenue monotonic, and furthermore satisfy some other desirable properties, namely participation, consumer sovereignty and maximality, representing the mechanism as a solution to a quadratically constrained linear program (QCLP). We prove that the QCLP is always feasible (i.e., for all bidder valuations) and give its solution analytically. Furthermore, we give an algorithm for running such a mechanism in time polynomial in the number of bidders and goods; this is interesting because constructing an instance of such mechanisms from our QCLP formulation in a naive way can require exponential time.

REFERENCES

• 1: Gagan Aggarwal , Jason D. Hartline, Knapsack auctions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1083-1092, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109677]
• 2: Nir Andelman , Yishay Mansour, A sufficient condition for truthfulness with single parameter agents, Proceedings of the 7th ACM conference on Electronic commerce, p.8-17, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134709]
• 3: 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
• 4: L. M. Ausubel and P. Milgrom. Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1, 2002.
• 5: 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, pages 17--40. MIT Press, Cambridge, Massachusetts, 2006.
• 6: Moshe Babaioff , Ron Lavi , Elan Pavlov, Single-value combinatorial auctions and implementation in undominated strategies, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1054-1063, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109674]
• 7: Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846250]
• 8: Avrim Blum , Jason D. Hartline, Near-optimal online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 10: R. Day and P. Milgrom. Core-selecting package auctions. International Journal of Game Theory, July 2007.
• 11: Shahar Dobzinski , Noam Nisan , Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132607]
• 12: Uriel Feige, On maximizing welfare when utility functions are subadditive, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132523]
• 13: Uriel Feige , Jan Vondrak, Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.667-676, October 21-24, 2006 [doi>10.1109/FOCS.2006.14]
• 14: Andrew V. Goldberg , Jason D. Hartline, Envy-free auctions for digital goods, Proceedings of the 4th ACM conference on Electronic commerce, p.29-35, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779932]
• 15: J. Green and J. Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45(2):427--438, 1977.
• 16: M. Haris and A. Riley. Allocation mechanisms and the design of auctions. Econometrica, 49(6):1477--1499, 1981.
• 17: Ron Lavi , Ahuva Mu'alem , Noam Nisan, Towards a Characterization of Truthful Combinatorial Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.574, October 11-14, 2003
• 18: 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]
• 19: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 20: A. Likhodedov and T. Sandholm. Approximating revenue-maximizing combinatorial auctions. AAAI'05, pages 267--274, 2005.
• 21: P. Milgrom. Incentives in core-selecting auctions. Stanford University, 2006.
• 22: Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 23: R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.
• 24: N. Nisan. Introduction to mechanism design. In N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors, Algorithmic Game Theory, chapter 9. Cambridge University Press, 2007.
• 25: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 26: B. Rastegari, A. Condon, and K. Leyton-Brown. Revenue monotonicity in combinatorial auctions. AAAI'07, pages 122--127, 2007.
• 27: B. Rastegari, A. Condon, and K. Leyton-Brown. Revenue monotonicity in deterministic, dominant strategy combinatorial auctions. Working paper, http://cs.ubc.ca/~baharak/research/RevenueMonotonicity.pdf, 2008.
• 28: J. G. Riley and W. F. Samuelson. Optimal auctions. American Economic Review, 71(3):381--392, 1981.
• 29: Amir Ronen, On approximating optimal auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.11-17, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501160]
• 30: M. H. Rothkopf. Thirteen reasons why the Vickrey-Clarke-Groves process is not practical. Operations Research, 55(2):191--197, March-April 2007.
• 31: M. Yokoo. Pseudonymous bidding in combinatorial auctions. In P. Cramton, Y. Shoham, and R. Steinberg, editors, Combinatorial Auctions, chapter 7, pages 161--187. MIT Press, Cambridge, Massachusetts, 2006.
• 32: 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, January 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming