On the Complexity of Equilibrium Computation in First-Price Auctions
From MaRDI portal
Publication:5885597
DOI10.1137/21M1435823OpenAlexW3135479805MaRDI QIDQ5885597FDOQ5885597
Authors: 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
Recommendations
- On the complexity of computing an equilibrium in combinatorial auctions
- Computing Bayes-Nash Equilibria in Combinatorial Auctions with Verification
- Existence of an equilibrium in first price auctions
- The price of stability for first price auction
- Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types
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)
Cites Work
- A class of games possessing pure-strategy Nash equilibria
- The complexity of computing a Nash equilibrium
- Games with Incomplete Information Played by “Bayesian” Players, I–III Part I. The Basic Model
- On the Complexity of Nash Equilibria and Other Fixed Points
- Rational Learning Leads to Nash Equilibrium
- Monotone Comparative Statics
- New complexity results about Nash equilibria
- How easy is local search?
- On the complexity of the parity argument and other inefficient proofs of existence
- Uniqueness and existence of equilibrium in auctions with a reserve price
- Optimal Auction Design
- Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information
- The complexity of pure Nash equilibria
- Title not available (Why is that?)
- Settling the complexity of computing two-player Nash equilibria
- On total functions, existence theorems and computational complexity
- Characterization and computation of Nash-equilibria for auctions with incomplete information
- Uniqueness of equilibrium in sealed high-bid auctions.
- Bounding the inefficiency of outcomes in generalized second price auctions
- Toward a study of bidding processes part IV ‐ games with unknown costs
- Solving systems of polynomial inequalities in subexponential time
- Numerical analysis of asymmetric first price auctions
- Uniqueness of the equilibrium in first-price auctions
- Equilibrium in Sealed High Bid Auctions
- Ranking sealed high-bid and open asymmetric auctions
- Limit games and limit equilibria
- Rationalizable conjectural equilibrium: Between Nash and rationalizability
- Subjective games and equilibria
- First-Price Auctions With General Information Structures: Implications for Bidding and Revenue
- Existence of an equilibrium in first price auctions
- The discrete bid first auction
- Title not available (Why is that?)
- Equilibria, fixed points, and complexity classes
- Welfare guarantees for combinatorial auctions with item bidding
- Bayesian combinatorial auctions
- A note on discrete bid first-price auction with general value distribution
- Price of anarchy for greedy auctions
- The Complexity of Non-Monotone Markets
- Bayesian Mechanism Design
- Inapproximability of Nash equilibrium
- Market equilibrium under separable, piecewise-linear, concave utilities
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Title not available (Why is that?)
- Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
- The Hairy Ball problem is PPAD-complete
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- The complexity of gradient descent: CLS = PPAD ∩ PLS
- Settling the complexity of Nash equilibrium in congestion games
- Simultaneous auctions without complements are (almost) efficient
- Consensus Halving for Sets of Items
- Constant rank two-player games are PPAD-hard
- Dichotomies in equilibrium computation and membership of PLC markets in FIXP
- Can PPAD hardness be based on standard cryptographic assumptions?
Cited In (7)
- The pricing problem. Part II: Computational complexity
- PPAD-complete pure approximate Nash equilibria in Lipschitz games
- Financial networks with singleton liability priorities
- Learning Equilibria in Asymmetric Auction Games
- Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
- The price of stability for first price auction
- Computational analysis of perfect-information position auctions
This page was built for publication: On the Complexity of Equilibrium Computation in First-Price Auctions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5885597)
