Simultaneous auctions are (almost) efficient

ABSTRACT

Simultaneous item auctions are simple and practical procedures for allocating items to bidders with potentially complex preferences. In a simultaneous auction, every bidder submits independent bids on all items simultaneously. The allocation and prices are then resolved for each item separately, based solely on the bids submitted on that item. We study the efficiency of Bayes-Nash equilibrium (BNE) outcomes of simultaneous first- and second-price auctions when bidders have complement-free (a.k.a. subadditive) valuations. While it is known that the social welfare of every pure Nash equilibrium (NE) constitutes a constant fraction of the optimal social welfare, a pure NE rarely exists, and moreover, the full information assumption is often unrealistic. Therefore, quantifying the welfare loss in Bayes-Nash equilibria is of particular interest. Previous work established a logarithmic bound on the ratio between the social welfare of a BNE and the expected optimal social welfare in both first-price auctions (Hassidim et al., 2011) and second-price auctions (Bhawalkar and Roughgarden, 2011), leaving a large gap between a constant and a logarithmic ratio. We introduce a new proof technique and use it to resolve both of these gaps in a unified way. Specifically, we show that the expected social welfare of any BNE is at least 1/2 of the optimal social welfare in the case of first-price auctions, and at least 1/4 in the case of second-price auctions.

References

1. Noga Alon, Yuval Emek, Michal Feldman, and Moshe Tennenholtz. Bayesian ignorance. In PODC, pages 384-?391, 2010.
2. Kshipra Bhawalkar and Tim Roughgarden. Welfare guarantees for combinatorial auctions with item bidding. In SODA, pages 700?-709, 2011.
3. Kshipra Bhawalkar and Tim Roughgarden. Simultaneous single-item auctions. In WINE, 2012.
4. Sushil Bikhchandani. Auctions of heterogeneous objects. Games and Economic Behavior, 26(2): 193?-220, 1999.
5. Ioannis Caragiannis, Panagiotis Kanellopoulos, Christos Kaklamanis, and Maria Kyropoulou. On the efficiency of equilibria in generalized second price auctions. In EC, pages 81-?90, 2011.
6. George Christodoulou, Annam ?aria Kov ?acs, and Michael Schapira. Bayesian combinatorial auctions. In ICALP, pages 820?-832, 2008.
7. Benjamin Edelman, Michael Ostrovsky, Michael Schwarz, Thank Drew Fudenberg, Louis Kaplow, Robin Lee, Paul Milgrom, Muriel Niederle, and Ariel Pakes. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97, 2005.
8. Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM J. Comput., 39(1): 122-?142, 2009.
9. Hu Fu, Robert Kleinberg, and Ron Lavi. Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding. In EC, page 586, 2012.
10. Faruk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87(1):95?-124, 1999.
11. Avinatan Hassidim, Haim Kaplan, Yishay Mansour, and Noam Nisan. Non-price equilibria in markets of discrete goods. In EC, pages 295?-296, 2011.
12. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In STACS, pages 404?-413, 1999.
13. Benny Lehmann, Daniel J. Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55 (2):270-?296, 2006.
14. Brendan Lucier and Allan Borodin. Price of anarchy for greedy auctions. In SODA, pages 537-?553, 2010.
15. Brendan Lucier and Renato Paes Leme. Gsp auctions with correlated types. In EC, pages 71?-80, 2011.
16. J. Mamer and S. Bikhchandani. Competitive equilibrium in an exchange economy with indivisibilities. Journal of Economic Theory, 74: 385?-413, 1997.
17. Evangelos Markakis and Orestis Telelis. Uniform price auctions: Equilibria and efficiency. In SAGT, pages 227?-238, 2012.
18. Paul Milgrom. Putting auction theory to work: The simultaneous ascending auction. Journal of Political Economy, 108:245?-272, 1998.
19. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007.
20. Renato Paes Leme and Eva Tardos. Pure and bayes-nash price of anarchy for generalized second price auction. In FOCS, pages 735?-744, 2010.
21. Tim Roughgarden. The price of anarchy in games of incomplete information. In EC, pages 862?-879, 2012.
22. Tim Roughgarden and Eva Tardos. Introduction to the inefficiency of equilibria. In Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors, Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007.
23. Vasilis Syrgkanis. Bayesian games and the smoothness framework. CoRR, abs/1203.5155, 2012.
24. Hal R. Varian. Position auctions. International Journal of Industrial Organization, 25(6):1163-?1178, 2007.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

• Theory of computation

  • Design and analysis of algorithms