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 条

[41] Asymmetric First-Price Auctions-A Dynamical-Systems Approach
Fibich, Gadi
Gavish, Nir
MATHEMATICS OF OPERATIONS RESEARCH, 2012, 37 (02) : 219 - 243
[42] LARGE ASYMMETRIC FIRST-PRICE AUCTIONS-A BOUNDARY-LAYER APPROACH
Fibich, Gadi
Gavish, Nir
SIAM JOURNAL ON APPLIED MATHEMATICS, 2015, 75 (01) : 229 - 251
[43] Disentangling risk aversion and loss aversion in first-price auctions: An empirical approach
Kim, Dong-Hyuk
Ratan, Anmol
EUROPEAN ECONOMIC REVIEW, 2022, 150
[44] Affiliation and Entry in First-Price Auctions with Heterogeneous Bidders: An Analysis of Merger Effects
Li, Tong
Zhang, Bingyu
AMERICAN ECONOMIC JOURNAL-MICROECONOMICS, 2015, 7 (02) : 188 - 214
[45] Identification in first-price and Dutch auctions when the number of potential bidders is unobservable
Shneyerov, Artyom
Wong, Adam Chi Leung
GAMES AND ECONOMIC BEHAVIOR, 2011, 72 (02) : 574 - 582
[46] Asymmetric first-price auctions with uniform distributions: analytic solutions to the general case
Todd R. Kaplan
Shmuel Zamir
Economic Theory, 2012, 50 : 269 - 302
[47] A pricing scheme for QoS in overlay networks based on first-price auctions and reimbursement
Amigo, Isabel
Belzarena, Pablo
Vaton, Sandrine
NETNOMICS, 2013, 14 (1-2): : 69 - 93
[48] On the analysis of asymmetric first price auctions
Mares, Vlad
Swinkels, Jeroen M.
JOURNAL OF ECONOMIC THEORY, 2014, 152 : 1 - 40
[49] A shape constrained estimator of bidding function of first-price sealed-bid auctions
Zhang, Yu Yvette
ECONOMICS LETTERS, 2017, 150 : 67 - 72
[50] Asymmetric first price auctions
Kirkegaard, Rene
JOURNAL OF ECONOMIC THEORY, 2009, 144 (04) : 1617 - 1635

← 1 2 3 4 5 →