Algorithms for Selfish Agents

Many computer scientists look at the world from a new perspective: they study problems assuming there are selfish entities working for their own interests rather than for community interests. This implies that one has to design new algorithms/protocols that have to deal, not just with the combinatorial structure of the problem, but also, and perhaps mainly, with private interests conflicting with the aim of "optimizing". The new perspective is motivated by many real-life situations. Consider, for example, computations over the Internet. They often involve self-interested parties (selfish agents) which could not follow the protocol. For instance, (i) routers could forward only packets of their "friends" and (ii) clients could not follow congestion avoidance/slow start protocols of TCP in order to improve their own throughput.

In order to face the conflict between selfishness and optimization one designs a mechanism. A mechanism augments an algorithm with a carefully designed payment function which makes following the protocol "rational". This concept developed by economists gained a lot of attention in computer science community.

The talk will mainly focus on some recent results of the speaker and can be considered an overview of his PhD thesis. In particular, we will talk about the construction of mechanisms for so-called cost-sharing games showing that simple solutions are often the best possible ones. A second topic will concern so-called mechanisms with verification. These are mechanisms that somehow can verify the correctness of agents' actions. We will show that such a natural assumption gives to mechanisms the capability of solving a large class of optimization functions that classical mechanisms (without verification) cannot do.