On the complexity of computing an equilibrium in combinatorial auctions

DOI10.1137/1.9781611973730.9MaRDI QIDQ5363024zbMATH OpenOpenAlexFDO

Authors Shahar Dobzinski, Hu Fu, Robert D. Kleinberg

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.2041

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We study combinatorial auctions where each item is sold separately but simultaneously via a second price auction. We ask whether it is possible to efficiently compute in this game a pure Nash equilibrium with social welfare close to the optimal one. We show that when the valuations of the bidders are submodular, in many interesting settings (e.g., constant number of bidders, budget additive bidders) computing an equilibrium with good welfare is essentially as easy as computing, completely ignoring incentives issues, an allocation with good welfare. On the other hand, for subadditive valuations, we show that computing an equilibrium requires exponential communication. Finally, for XOS (a.k.a. fractionally subadditive) valuations, we show that if there exists an efficient algorithm that finds an equilibrium, it must use techniques that are very different from our current ones.

Recommendations

• Bayesian combinatorial auctions
• Bayesian Combinatorial Auctions
• Welfare guarantees for combinatorial auctions with item bidding
• Simple combinatorial auctions with budget constraints
• Approximation algorithms for combinatorial auctions with complement-free bidders

Cited in

(28)

• On complexity of single-minded auction
• Combinatorial auctions with endowment effect
• Learning in auctions: regret is hard, envy is easy
• Best-response dynamics in combinatorial auctions with item bidding
• Simultaneous auctions without complements are (almost) efficient
• Optimization with demand oracles
• On the polynomial time computation of equilibria for certain exchange economies
• Equilibrium in combinatorial public projects
• Computing equilibria for a service provider game with (im)perfect information
• Smoothness for Simultaneous Composition of Mechanisms with Admission
• Market Equilibrium for Combinatorial Auctions and the Matching Core of Nonnegative TU Games
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
• On the Economic Efficiency of the Combinatorial Clock Auction
• Best-response dynamics in combinatorial auctions with item bidding
• On simultaneous two-player combinatorial auctions
• Algorithms as mechanisms: the price of anarchy of relax and round
• Almost envy-freeness with general valuations
• Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification
• Computational analysis of perfect-information position auctions
• Welfare guarantees for combinatorial auctions with item bidding
• Note on an Auction Procedure for a Matching Game in Polynomial Time
• Equilibria of greedy combinatorial auctions
• Communication complexity of combinatorial auctions with submodular valuations
• On the Complexity of Equilibrium Computation in First-Price Auctions
• Bayesian combinatorial auctions
• Mechanism design for perturbation stable combinatorial auctions
• On rational computability and communication complexity

This page was built for publication: On the complexity of computing an equilibrium in combinatorial auctions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363024)