Tel-Aviv University - Computer Science Colloquium
Sunday, February 21, 14:15-15:15
at 14:00 This talk considers algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather will follow their own self-interest. Such scenarios arise, in particular, when computers or users aim to cooperate or trade over the Internet. As such participants, termed agents, are capable of manipulating any specified algorithm, the algorithm designer should ensure in advance that the agents' interests are best served by behaving "correctly".
The talk presents a model to formally study such algorithms. This model, based on the field of mechanism design, is similar in spirit to approaches taken in the distributed AI community and in the network design community in recent years. Using this model, we will demonstrate how some of the basic techniques of mechanism design can be applied towards distributed computation problems. We will also present new results in this distributed computation context that require going beyond the existing theory of mechanism design.
This talk assumes no prior knowledge. Most of it will be devoted to a thinly-disguised exposition of mechanism design. All new results presented are joint work with Amir Ronen.
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html