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.
翻译：我们研究拍卖中一般打结规则下第一价格拍卖中寻找一个近似的（纯）贝叶斯纳什均衡的复杂度问题。我们表明即使是当打结规则是三边形的（即，仅当不超过三个出价者打结时，它指定物品分配并采用统一的打结规则），该问题也是PPAD完全的问题。这是第一价格拍卖中公共先验条件下均衡计算的第一种难度结果。在积极方面，我们在统一打结规则下提出了一个问题的PTAS。
相关内容
微信扫码咨询专知VIP会员