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