January 28, 2010: Seminar - Allan Borodin: "The Power and Limitation of Greedy Mechanism Design for Combinatorial Auctions"

Seminar Announcement

The Power and Limitation of Greedy Mechanism Design for Combinatorial Auctions

Allan Borodin
Department of Computer Science
University of Toronto
Monday Februray 8, 2009
11:00 a.m., 1000 SEO


We consider combinatorial auctions in which objects are sold to selfish bidders, each having a private valuation function that expresses values for sets of objects. In particular, we consider the social welfare objective where the goal of the auctioneer is to allocate the objects so as to maximize the sum of the values of the allocated sets. Our specific interest is to understand the power and limitations of "simple" allocation algorithms in this regard. We show that monotone greedy algorithms can be made into mechanisms whose price of anarchy (i.e. at every ex-post Nash equilibria) is almost as good as the approximation that the greedy allocation achieves (disregarding selfish interest). In contrast to this positive result on the price of anarchy, we also consider the limitation of greedy truthful mechanisms, where we model the notion of greediness with a broad class of algorithms known as priority algorithms. For single minded bidders, there is a known truthful deterministic mechanism (Lehmann, O'Callaghan and Shoham) using a greedy allocation that achieves an O(sqrt{m}) approximation ratio to the social welfare. We show that no truthful priority mechanism obtains a sub-linear (i.e. o(min {m,n}) approximation ratio. In fact, this linear inapproximation for truthful greedy mechanisms holds for the special case of s-CAs in which in which an agent's values are determined by sets of size at most s. This is in contrast to the s+1-approximation obtained by the "standard" greedy algorithm (disregarding selfish interests).

(Joint work with Brendan Lucier)

Brief Bio:

Allan Borodin received his B.A. from Rutgers University in 1963, and obtained an M.S. degree in 1966 from Stevens Institute of Technology while working as a Member of the Technical Staff at Bell Laboratories. He returned full time to graduate school at Cornell in 1966 and received his PhD in 1969. He came to Canada and the University of Toronto in 1969 for a year or two but forgot to leave. He has been on the faculty of the Department of Computer Science at Toronto since 1969 and served as department chair from 1980-1985. He has held visiting positions at Cornell, ETH Zurich, Universite' de Nice, Hebrew University, Weizmann University, Technion, University of Washington and the Institute for Advanced Study. Professor Borodin is a fellow of the Royal Society of Canada and a recipient of the 2008 CRM-Fields-PIMS Prize in recognition of his exceptional achievement in mathematical computer sciences especially in the theory of efficient and "simple" algorithms. Allan Borodin has made fundamental contributions to many areas, including algebraic computations, resource tradeoffs, routing in interconnection networks, parallel algorithms, online algorithms, and adversarial queuing theory.

Host: Bhaskar DasGupta

Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF