Algorithms and Complexity Seminar
The Power and Limitations of Greedy Mechanism Design
for Combinatorial Auctions
Allan Borodin (University of Toronto)
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