On the Complexity of Equilibrium Computation in First-Price Auctions

DOI10.1137/21M1435823MaRDI QIDQ5885597zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

first-price auctionsapproximate equilibriaBayes-Nash equilibriaPPADFIXPsubjective priors

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 5942357 (Why is no real title available?)
• scientific article; zbMATH DE number 232878 (Why is no real title available?)
• scientific article; zbMATH DE number 5032929 (Why is no real title available?)
• A class of games possessing pure-strategy Nash equilibria
• A note on discrete bid first-price auction with general value distribution
• Bayesian Mechanism Design
• Bayesian combinatorial auctions
• Bounding the inefficiency of outcomes in generalized second price auctions
• Can PPAD hardness be based on standard cryptographic assumptions?
• Characterization and computation of Nash-equilibria for auctions with incomplete information
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• 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
• Equilibria, fixed points, and complexity classes
• Equilibrium in Sealed High Bid Auctions
• Existence of an equilibrium in first price auctions
• Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
• First-Price Auctions With General Information Structures: Implications for Bidding and Revenue
• Games with Incomplete Information Played by “Bayesian” Players, I–III Part I. The Basic Model
• How easy is local search?
• Inapproximability of Nash equilibrium
• Limit games and limit equilibria
• Market equilibrium under separable, piecewise-linear, concave utilities
• Monotone Comparative Statics
• New complexity results about Nash equilibria
• Numerical analysis of asymmetric first price auctions
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Optimal Auction Design
• Price of anarchy for greedy auctions
• Ranking sealed high-bid and open asymmetric auctions
• Rational Learning Leads to Nash Equilibrium
• Rationalizable conjectural equilibrium: Between Nash and rationalizability
• Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
• Settling the complexity of Nash equilibrium in congestion games
• Settling the complexity of computing two-player Nash equilibria
• Simultaneous auctions without complements are (almost) efficient
• Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information
• Solving systems of polynomial inequalities in subexponential time
• Subjective games and equilibria
• The Complexity of Non-Monotone Markets
• The Hairy Ball problem is PPAD-complete
• The complexity of computing a Nash equilibrium
• The complexity of gradient descent: CLS = PPAD ∩ PLS
• The complexity of pure Nash equilibria
• The discrete bid first auction
• Toward a study of bidding processes part IV ‐ games with unknown costs
• Uniqueness and existence of equilibrium in auctions with a reserve price
• Uniqueness of equilibrium in sealed high-bid auctions.
• Uniqueness of the equilibrium in first-price auctions
• Welfare guarantees for combinatorial auctions with item bidding

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)