Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions
Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions
复制标题
DOI：
10.1145/2847520
复制
发表时间：
2013-12
期刊：
影响因子：
--
通讯作者：
G. Christodoulou;Annamária Kovács;A. Sgouritsa;Bo Tang
中科院分区：
文献类型：
--
作者：
G. Christodoulou;Annamária Kovács;A. Sgouritsa;Bo Tang
我们研究了具有下次和亚降低价值的买家的简单第一价格拍卖的无政府状态（POA）的价格。 ）[Syrgkanis and Tardos 2013]和2 [Feldman等人]，分别为我们提供了两种情况的匹配范围。 E/（E-1）的上限，用于fpa的fPA，揭示了最差的价格分布，这被用作匹配下限构造的基础。我们称之为竞标依赖的拍卖的项目竞标拍卖（包括FPA和全薪拍卖），其中获胜者始终是最高的投标人，每个投标人的付款仅取决于他自己的竞标。 。 ，我们能够使用我们的非平滑方法来重现E/（E -1）的上限。
We study the price of anarchy (PoA) of simultaneous first-price auctions (FPAs) for buyers with submodular and subadditive valuations. The current best upper bounds for the Bayesian price of anarchy (BPoA) of these auctions are e/(e − 1) [Syrgkanis and Tardos 2013] and 2 [Feldman et al. 2013], respectively. We provide matching lower bounds for both cases even for the case of full information and for mixed Nash equilibria via an explicit construction. We present an alternative proof of the upper bound of e/(e − 1) for FPAs with fractionally subadditive valuations that reveals the worst-case price distribution, which is used as a building block for the matching lower bound construction. We generalize our results to a general class of item bidding auctions that we call bid-dependent auctions (including FPAs and all-pay auctions) where the winner is always the highest bidder and each bidder’s payment depends only on his own bid. Finally, we apply our techniques to discriminatory price multiunit auctions. We complement the results of de Keijzer et al. [2013] for the case of subadditive valuations by providing a matching lower bound of 2. For the case of submodular valuations, we provide a lower bound of 1.109. For the same class of valuations, we were able to reproduce the upper bound of e/(e − 1) using our nonsmooth approach.