Simultaneous auctions without complements are (almost) efficient (Q2206818)

This article debates the current topic related to the non-price equilibria in markets of discrete goods. The authors show that when buyer valuations are complement-free (a.k.a. subadditive), the (Bayesian) price of anarchy of the simultaneous item auction mechanism is at most a constant, in both the first- and second-price auctions. This improves upon the previously best-known bound of \(O(\log\,m)\) (see [\textit{A. Hassidim} et al., ``Non-price equilibria in markets of discrete goods'', in: Proceedings of the 12th ACM conference on electronic commerce, EC'11. New York, NY: Association of Computing Machinery (ACM). 295--296 (2011; \url{doi:10.1145/1993574.1993619})]), where \(m\) is the number of items. More precisely, the authors study the efficiency of Bayesian Nash equilibrium (BNE) outcomes of simultaneous first- and second-price auctions when bidders have complement-free (a.k.a. subadditive) valuations and show that the expected social welfare of any BNE is at least \(\frac{1}{2}\) of the optimal social welfare in the case of first-price auctions, and at least \(\frac{1}{4}\) in the case of second-price auctions. Moreover, this bound applies also to coarse correlated equilibria in the full information setting. A polynomial lower bound, \(\Omega(n^{\frac{1}{6}})\), on the Bayesian price of anarchy for first-price auctions with subadditive valuations, when the valuation distributions are correlated among the bidders is given in Section 6.