Iterative Auction Design for Tree Valuations
Iterative Auction Design for Tree Valuations
复制标题
DOI：
10.1287/opre.2015.1388
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Ozan Candogan;A. Ozdaglar;P. Parrilo
中科院分区：
文献类型：
--
作者：
Ozan Candogan;A. Ozdaglar;P. Parrilo
我们研究了一类特殊的多项目估值(树形估值)，它既表现出价值的互补性，又表现出可替代性。我们给出了代理和物品数量为多项式大小的有效分配问题的线性规划公式。这揭示了一类新的估值，在存在价值互补的情况下，存在沃尔拉斯均衡。这个线性规划的迭代算法，结合适当的支付规则，产生一个迭代拍卖，实现了有效的结果(在事后完美均衡)。这次拍卖依赖于简单的定价规则、紧凑的需求报告，并使用一种新颖的(交错)价格更新结构来将最终付款分配给投标人，以保证真实的竞价。
We study a special class of multi-item valuations (tree valuations) that exhibit both value complementarity and substitutability. We provide a linear programming formulation of the efficient allocation problem that is of polynomial size in the number of agents and items. This reveals a new class of valuations for which a Walrasian equilibrium exists in the presence of value complementarities. An iterative algorithm for this linear program, in conjunction with an appropriate payment rule, yields an iterative auction that implements the efficient outcome (at an ex post perfect equilibrium). This auction relies on a simple pricing rule, compact demand reports, and uses a novel (interleaved) price update structure to assign final payments to bidders that guarantee truthful bidding.