ON THE COMPLEXITY OF EQUILIBRIUM COMPUTATION IN FIRST-PRICE AUCTIONS

被引：2

作者：

Filos-Ratsikas, Aris ^{[1
]}

Giannakopoulos, Yiannis ^{[2
]}

Hollender, Alexandros ^{[3
]}

Lazos, Philip ^{[4
]}

Pocas, Diogo ^{[5
]}

机构：

[1] Univ Edinburgh, Sch Informat, Informat Forum, Edinburgh EH8 9AB, Midlothian, Scotland

[2] Friedrich Alexander Univ Erlangen Nurnberg, Dept Data Sci, D-91058 Erlangen, Germany

[3] Univ Oxford, Dept Comp Sci, Oxford OX1 3QD, England

[4] IOHK, 4 Battery Rd, Singapore, Singapore

[5] Univ Lisbon, Fac Ciencias, LASIGE, P-1749016 Lisbon, Portugal

来源：

SIAM JOURNAL ON COMPUTING | 2023年 / 52卷 / 01期

基金：

英国工程与自然科学研究理事会;

关键词：

first-price auctions; Bayes--Nash equilibria; approximate equilibria; subjective pri-ors; PPAD; FIXP; NASH-EQUILIBRIA; EXISTENCE; PRICE; GAMES; UNIQUENESS;

D O I：

10.1137/21M1435823

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 \varepsilon-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.

引用

页码：80 / 131

页数：52

共 50 条

[31] Using all bids in parametric estimation of first-price auctions
Li, T
Vuong, Q
ECONOMICS LETTERS, 1997, 55 (03) : 321 - 325
[32] Separating probability weighting and risk aversion in first-price auctions
Haruvy, Ernan
Heinrich, Timo
Walker, Matthew J.
ECONOMICS LETTERS, 2022, 221
[33] Quantile-based nonparametric inference for first-price auctions
Marmer, Vadim
Shneyerov, Artyom
JOURNAL OF ECONOMETRICS, 2012, 167 (02) : 345 - 357
[34] Nonparametric estimation of first-price auctions with risk-averse bidders
Zincenko, Federico
JOURNAL OF ECONOMETRICS, 2018, 205 (02) : 303 - 335
[35] Inference for first-price auctions with Guerre, Perrigne, and Vuong's estimator
Ma, Jun
Marmer, Vadim
Shneyerov, Artyom
JOURNAL OF ECONOMETRICS, 2019, 211 (02) : 507 - 538
[36] On stability of efficient cartel mechanisms in first-price auctions with uninformed bidders
Cao, Xiaoyong
Hsueh, Shao-Chieh
Wang, Wei
ECONOMICS LETTERS, 2020, 187
[37] Spying and imperfect commitment in first-price auctions: a case of tacit collusion
Fan, Cuihong
Jun, Byoung Heon
Wolfstetter, Elmar G.
ECONOMIC THEORY BULLETIN, 2023, 11 (02) : 255 - 275
[38] Monotonicity-constrained nonparametric estimation and inference for first-price auctions
Ma, Jun
Marmer, Vadim
Shneyerov, Artyom
Xu, Pai
ECONOMETRIC REVIEWS, 2021, 40 (10) : 944 - 982
[39] Bribing in first-price auctions (vol 77, pg 214, 2013)
Kotowski, Maciej H.
Rachmilevitch, Shiran
GAMES AND ECONOMIC BEHAVIOR, 2014, 87 : 616 - 618
[40] On Rationalizability and Beliefs in Discrete Private-Value First-Price Auctions
Robles, Jack
Shimoji, Makoto
B E JOURNAL OF THEORETICAL ECONOMICS, 2012, 12 (01):

← 1 2 3 4 5 →