Duality and optimality of auctions for uniform distributions
Duality and optimality of auctions for uniform distributions
复制标题
均匀分布拍卖的二元性和最优性
DOI：
10.1145/2600057.2602883
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
E. Koutsoupias
中科院分区：
文献类型：
--
作者：
Yiannis Giannakopoulos;E. Koutsoupias
我们推导出精确的最优解的问题，在单一投标人的多项目拍卖统一的i.i.d.的收入优化。估值我们给出了最多6个项目的最优拍卖;以前的结果只知道最多3个项目。为了做到这一点，我们开发了一个一般的对偶框架，在多投标人多项目添加剂贝叶斯拍卖连续概率估值分布的收入最大化的一般问题。该框架扩展了线性规划的对偶性和互补性的约束偏导数。该对偶系统揭示了该问题的几何本质，并强调了其与二部图匹配理论的联系。对偶框架不仅用于证明最优性，但也许更重要的是，用于导出最优拍卖;因此，最优拍卖是由自然几何约束定义的。
We derive exact optimal solutions for the problem of optimizing revenue in single-bidder multi-item auctions for uniform i.i.d. valuations. We give optimal auctions of up to 6 items; previous results were only known for up to three items. To do so, we develop a general duality framework for the general problem of maximizing revenue in many-bidders multi-item additive Bayesian auctions with continuous probability valuation distributions. The framework extends linear programming duality and complementarity to constraints with partial derivatives. The dual system reveals the geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings. The duality framework is used not only for proving optimality, but perhaps more importantly, for deriving the optimal auction; as a result, the optimal auction is defined by natural geometric constraints.