Title: Selfish Agents and Approximation Mechanisms

Speaker: Moshe Babaioff, U.C. Berkeley.
http://www.ischool.berkeley.edu/~moshe/

Issues on the border of Computer Science and Economics have drawn much recent 
research attention, mostly motivated by the Internet, where selfish agents 
interact in computational settings. I discuss various issues on this 
borderline, and in particular the problem of market design under computational
constraints and in the presence of selfish agents with private preferences. 
To overcome strategic behavior, the predominant approach in the literature is 
to construct dominant strategy truthful mechanisms, but unfortunately not 
every approximation algorithm can be used for such a construction.

In this talk I present a general deterministic technique to decouple the 
algorithmic allocation problem from the strategic aspects, by a procedure 
that converts any approximation algorithm to a dominant-strategy ascending 
mechanism. I also show how approximation can be achieved when agents do not 
have dominant strategies, using our new notion of "Algorithmic Implementation 
in Undominated Strategies". These results are taken from a joint research 
with Ron Lavi and Elan Pavlov.