Computer Science Colloquium, 2006-2007

Moshe Babaioff
December 27, 2006

Title: Selfish Agents and Approximation Mechanisms

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.

Benny Pinkas