Abstract:

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.