Combinatorics Seminar
When: Sunday, February 21, 10am
Where: Schreiber 309
Speaker: Allan Borodin, University of Toronto
Title: The Power and Limitation of Greedy Mechanism Design
for Combinatorial Auctions
Abstract:
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
``conceptually 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.