论文标题
组合拍卖的简化先知不平等现象
Simplified Prophet Inequalities for Combinatorial Auctions
论文作者
论文摘要
我们考虑对XOS和MPH- $ K $组合拍卖的先知不平等，并为存在静态和匿名商品价格提供简化的证据，以恢复最先进的竞争比率。 我们的证明利用线性编程公式，如果有价格承认给定的竞争比$α\ geq 1 $，则具有非负目标价值。通过应用强LP二元性的应用将我们的观点更改为双重空间，我们将双重变量的解释用作直接获得我们结果的概率。与以前的工作相反，我们的证据不需要争论购买者的特定价值捆绑包，而只需就物品的存在或不存在。 另外，对于任何$ k \ geq 2 $，此简化还会导致MPH- $ K $ COMBINATORIAL AUCTIONS的最佳竞争比率从$ 4K-2 $到$ 2K + 2K + 2 \ 2 \ SQRT {K（K-1）} -1 $。
We consider prophet inequalities for XOS and MPH-$k$ combinatorial auctions and give a simplified proof for the existence of static and anonymous item prices which recover the state-of-the-art competitive ratios. Our proofs make use of a linear programming formulation which has a non-negative objective value if there are prices which admit a given competitive ratio $α\geq 1$. Changing our perspective to dual space by an application of strong LP duality, we use an interpretation of the dual variables as probabilities to directly obtain our result. In contrast to previous work, our proofs do not require to argue about specific values of buyers for bundles, but only about the presence or absence of items. As a side remark, for any $k \geq 2$, this simplification also leads to a tiny improvement in the best competitive ratio for MPH-$k$ combinatorial auctions from $4k-2$ to $2k + 2 \sqrt{k(k-1)} -1$.
