Decision Sciences Seminar
Tuesday February 12, 2013
10:00AM - 11:30AM
Massachusetts Institute of Technology
Iterative Auction Design for Graphical Valuations
Multi-item iterative auctions are a class of mechanisms that are commonly employed in practice, for instance, in the context of spectrum and procurement auctions. However, the existing iterative auction formats that are provably efficient have certain limitations. Specifically, they are either restricted to environments that do not allow for value complementarity between different items, or they require complex pricing structures. In this work, we develop new practical and efficient iterative auctions for multi-item settings that exhibit both value complementarity and substitutability. We obtain such auctions by focusing on a natural class of valuation functions that admit a compact representation, which we refer to as graphical valuations.
For special classes of graphical valuations, such as tree valuations, our auctions implement the efficient outcome using item pricing, i.e., offering an anonymous price for each item. However, we establish that this simple pricing structure is not sufficient when the underlying value graph has cycles. On the other hand, we show that for general graphical valuations, auction formats, which rely on offering a bidder-specific price for each item and discounts for pairs of items, can guarantee efficiency. These results suggest that by exploiting the special graphical structure of valuations, it is possible to implement the efficient outcome using simple auction formats.
Bio: Ozan Candogan is a Ph.D. candidate in the Electrical Engineering and Computer Science Department of the Massachusetts Institute of Technology. He is also a member of the Laboratory for Information and Decision Systems. His research focuses on game theory, optimization, and mechanism design with applications to social and economic networks, e-commerce, and online markets.