[A&C seminar] The Power and Limitations of Greedy Mechanism Design for Combinatorial Auctions
Speaker: Allan Borodin , University of Toronto
Date: May 15 2009
Time: 4:00PM to 5:10PM
Location: G575
Host: Silvio Micali, MIT
Contact: Aleksander Madry, madry@mit.edu
Relevant URL: http://people.csail.mit.edu/madry/algcompsem/We study 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 present a simple
greedy mechanism
that obtains an approximation ratio of Theta(sqrt{m}) at every (ex-post)
pure Nash equilibrium, and for which such an equilibrium is guaranteed to
exist. In contrast to this positive result on the price of
anarchy, we also consider the limitations 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. However,
for general CAs the best known deterministic truthful (or universally truthful
randomized) mechanism has approximation ratio O(m/sqrt{log m})
(Blumrosen and Nisan).
We show that no truthful priority mechanism obtains a sub-linear
approximation ratio. We also consider certain priority algorithms for use
with submodular bidders, and show that no such algorithm can be made truthful.
Joint work with Brendan Lucier
See other events that are part of
See other events happening in May 2009
