Iterative Auction Design for Tree Valuations
Ozan Candogan, Asuman Ozdaglar, Pablo A. Parrilo
Operations Research · 2015 · Volume 63 · Issue 4
Abstract
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.
Keywords
games/group decisions, bidding/auctions, noncooperative, programming, linear
Enable JavaScript for citation tools and additional paper interactions.