On the Complexity of Equilibrium Computation in First-Price Auctions
From MaRDI portal
Publication:5885597
DOI10.1137/21M1435823OpenAlexW3135479805MaRDI QIDQ5885597
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, Diogo Poças
Publication date: 4 April 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2103.03238
Analysis of algorithms and problem complexity (68Q25) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic game theory and complexity (91A68)
Related Items
Financial networks with singleton liability priorities ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Equilibria, fixed points, and complexity classes
- On total functions, existence theorems and computational complexity
- Ranking sealed high-bid and open asymmetric auctions
- New complexity results about Nash equilibria
- Limit games and limit equilibria
- How easy is local search?
- Solving systems of polynomial inequalities in subexponential time
- Characterization and computation of Nash-equilibria for auctions with incomplete information
- Rationalizable conjectural equilibrium: Between Nash and rationalizability
- On the complexity of the parity argument and other inefficient proofs of existence
- Numerical analysis of asymmetric first price auctions
- Uniqueness of equilibrium in sealed high-bid auctions.
- The discrete bid first auction
- Existence of an equilibrium in first price auctions
- Subjective games and equilibria
- Uniqueness and existence of equilibrium in auctions with a reserve price
- Simultaneous auctions without complements are (almost) efficient
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- The Hairy Ball problem is PPAD-complete
- Bounding the inefficiency of outcomes in generalized second price auctions
- Uniqueness of the equilibrium in first-price auctions
- A class of games possessing pure-strategy Nash equilibria
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Market equilibrium under separable, piecewise-linear, concave utilities
- On the Complexity of Nash Equilibria and Other Fixed Points
- Rational Learning Leads to Nash Equilibrium
- Settling the complexity of computing two-player Nash equilibria
- The complexity of pure Nash equilibria
- A NOTE ON DISCRETE BID FIRST-PRICE AUCTION WITH GENERAL VALUE DISTRIBUTION
- Optimal Auction Design
- Monotone Comparative Statics
- Equilibrium in Sealed High Bid Auctions
- Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information
- Constant Rank Two-Player Games are PPAD-hard
- Inapproximability of Nash Equilibrium
- First-Price Auctions With General Information Structures: Implications for Bidding and Revenue
- The Complexity of Non-Monotone Markets
- The Complexity of Computing a Nash Equilibrium
- Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
- Bayesian Mechanism Design
- Games with Incomplete Information Played by “Bayesian” Players, I–III Part I. The Basic Model
- Toward a study of bidding processes part IV ‐ games with unknown costs
- Consensus Halving for Sets of Items
- Bayesian Combinatorial Auctions
- Can PPAD hardness be based on standard cryptographic assumptions?
- The complexity of gradient descent: CLS = PPAD ∩ PLS
- Settling the complexity of Nash equilibrium in congestion games
