Iterative Auction Design for Tree Valuations

Ozan Candogan (), Asuman Ozdaglar () and Pablo A. Parrilo ()
Additional contact information
Ozan Candogan: The University of Chicago Booth School of Business, Chicago, Illinois 60637
Asuman Ozdaglar: Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Pablo A. Parrilo: Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2015, vol. 63, issue 4, 751-771

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 (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1388 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:63:y:2015:i:4:p:751-771

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().