论文标题
同时进行第二次价格拍卖，无价不足
Simultaneous 2nd Price Item Auctions with No-Underbidding
论文作者
论文摘要
关于简单拍卖的无政府状态（POA）价格（POA）的文献采用了无关紧要的假设，但完全忽略了不企业不足的现象，这在第二次价格拍卖的变体的经验研究中很明显。在这项工作中，我们为无档现象提供了理论基础。我们研究了在新的自然条件下，同时第二次价格拍卖（s2pa）的POA {\ em no no Bustbidding}，这意味着代理永远不会竞标小于其边际价值的项目。我们在全面信息和不完整的信息设置中都没有针对不同估值类别（包括单位需求，子模具，XOS，XOS，亚辅助和一般单调估值）的S2PA的POA建立改进的（大部分）范围。 为了获得我们的结果，我们引入了一种新的拍卖的参数化特性，称为$（γ，δ）$ - 保证的收入，这意味着POA至少为$γ/（1+δ）$。通过扩展定理，此保证在完整信息设置中扩展到粗糙相关的平衡（CCE），并在具有不完整的信息和任意（相关）分布的设置中延伸至贝叶斯POA（BPOA）。然后，我们证明S2PA是$（1,1）$ - 收入保证的，就不满意的投标而言。这意味着通用单调评估的POA至少为$ 1/2 $，该估值延伸到BPOA，并具有任意相关的分布。此外，我们表明$（λ，μ）$ - 平滑度与$（γ，δ）$ - 收入保证保证至少$（γ+λ）/（1+δ+μ）$。这意味着许多结果，例如S2PA的$ 2/3 $的紧张POA，具有子模型（或XOS）估值，在没有过度昂贵的情况下，也没有不足。除了建立改善S2PA的界限外，没有未进行的假设为S2PA相对于同时的第1个价格拍卖的性能提供了新的启示。
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 {\em 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 (including unit-demand, submodular, XOS, subadditive, and general monotone valuations), in both full-information and incomplete information settings. To derive our results, we introduce a new parameterized property of auctions, termed $(γ,δ)$-revenue guaranteed, which implies a PoA of at least $γ/(1+δ)$. Via extension theorems, this guarantee extends to coarse correlated equilibria (CCE) in full information settings, and to Bayesian PoA (BPoA) in settings with incomplete information and arbitrary (correlated) distributions. We then show that S2PA are $(1,1)$-revenue guaranteed with respect to bids satisfying no underbidding. This implies a PoA of at least $1/2$ for general monotone valuation, which extends to BPOA with arbitrary correlated distributions. Moreover, we show that $(λ,μ)$-smoothness combined with $(γ,δ)$-revenue guaranteed guarantees a PoA of at least $(γ+λ)/(1+δ+μ)$. This implies a host of results, such as a tight PoA of $2/3$ for S2PA with submodular (or XOS) valuations, under no overbidding and no underbidding. Beyond establishing improved bounds for S2PA, the no underbidding assumption sheds new light on the performance of S2PA relative to simultaneous 1st price auctions.
