Simultaneous auctions without complements are (almost) efficient
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.
- Simultaneous auctions are (almost) efficient
- On monotone strategy equilibria in simultaneous auctions for complementary goods
- On the complexity of computing an equilibrium in combinatorial auctions
- Welfare guarantees for combinatorial auctions with item bidding
- Equilibrium and efficiency in auctions of complementary goods without bundling
- Algorithmic Game Theory
- Auctions of heterogeneous objects
- Bayesian Combinatorial Auctions
- Bayesian ignorance
- Combinatorial auctions with decreasing marginal utilities
- Competitive equilibrium in an exchange economy with indivisibilities
- Composable and efficient mechanisms
- Discontinuous Games and Endogenous Sharing Rules
- Introduction to the inefficiency of equilibria
- On maximizing welfare when utility functions are subadditive
- Price of anarchy for greedy auctions
- Valuation compressions in VCG-based combinatorial auctions
- Welfare guarantees for combinatorial auctions with item bidding
- Auctions of heterogeneous objects
- An optimal auction for complements
- Towards a characterization of worst case equilibria in the discriminatory price auction
- Limits of efficiency in sequential auctions
- Welfare and rationality guarantees for the simultaneous multiple-round ascending auction
- A New Analysis of Expected Revenue
- Expressiveness and robustness of first-price position auctions
- Simultaneous auctions are (almost) efficient
- On the Complexity of Equilibrium Computation in First-Price Auctions
- A Bayesian equilibrium for simultaneous first-price auctions for complementary goods and quasi-linear bids
- Optimal and Efficient Auctions for the Gradual Procurement of Strategic Service Provider Agents
- Simultaneous 2nd price item auctions with no-underbidding
- Equilibrium and efficiency in auctions of complementary goods without bundling
- Fair and truthful allocations under leveled valuations
- Auctioning off a non-rivalrous good with interference
- Simultaneous independent online auctions with discrete bid increments
This page was built for publication: Simultaneous auctions without complements are (almost) efficient
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2206818)
