Iterative Auction Design for Tree Valuations

• 成果类型: Article
• 署名作者: Candogan, Ozan; Ozdaglar, Asuman; Parrilo, Pablo A.
• 署名单位: University of Chicago; Massachusetts Institute of Technology (MIT)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2015.1388
• 发表日期: 2015
• 页码: 751-771
• 关键词: Combinatorial auctions; vickrey auctions; substitutes; equilibrium; synergies

摘要

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.