Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules

• Tác giả: Xi Chen, Binghui Peng
• Ngôn ngữ: eng
• Ký hiệu phân loại: 795.414 Auction bridge
• Thông tin xuất bản: 2023
• Bộ sưu tập: Báo, Tạp chí
• ID: 196729

Tóm tắt

We study the complexity of finding an approximate (pure) Bayesian Nash equilibrium in a first-price auction with common priors when the tie-breaking rule is part of the input. We show that the problem is PPAD-complete even when the tie-breaking rule is trilateral (i.e., it specifies item allocations when no more than three bidders are in tie, and adopts the uniform tie-breaking rule otherwise). This is the first hardness result for equilibrium computation in first-price auctions with common priors. On the positive side, we give a PTAS for the problem under the uniform tie-breaking rule.