Simultaneous 2nd price item auctions with no-underbidding

• 成果类型: Article
• 署名作者: Feldman, Michal; Shabtai, Galia
• 署名单位: Tel Aviv University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2023.03.009
• 发表日期: 2023
• 页码: 316-340
• 关键词: Algorithmic game theory; Simultaneous item bidding auctions; Price of anarchy

摘要

The literature on the Price of Anarchy (PoA) of simple auctions employs a no-overbidding assumption but has completely overlooked the no-underbidding phenomenon, which is evident in empirical studies on variants of the second price auction. In this work, we provide a theoretical foundation for the no-underbidding phenomenon. We study the PoA of simultaneous 2nd price auctions (S2PA) under a new natural condition of no underbidding, meaning that agents never bid on items less than their marginal values. We establish improved (mostly tight) bounds on the PoA of S2PA under no-underbidding for different valuation classes, in both full-information and incomplete information settings. Specifically, we show that the PoA is at least 1/2 for general monotone valuations, which extends to Bayesian PoA with arbitrary correlated distributions. We also establish a tight PoA bound of 2/3 for S2PA with XOS valuations, under no-overbidding and nounderbidding, which extends to Bayesian PoA with independent distributions. & COPY; 2023 Elsevier Inc. All rights reserved.