Journal article icon

Journal article

On the complexity of equilibrium computation in first-price auctions

Abstract:
We consider the problem of computing a (pure) Bayes–Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an ε-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete. We also provide an efficient algorithm for solving a special case of the problem for a fixed number of bidders and available bids.
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1137/21M1435823

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
All Souls College
Role:
Author
ORCID:
0000-0001-5255-9349
Publisher:
Society for Industrial and Applied Mathematics
Journal:
SIAM Journal on Computing More from this journal
Volume:
52
Issue:
1
Pages:
80-131
Publication date:
2023-02-14
Acceptance date:
2022-09-14
DOI:
EISSN:
1095-7111
ISSN:
0097-5397
Language:
English
Keywords:
Pubs id:
1285575
Local pid:
pubs:1285575
Deposit date:
2022-10-19

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP