Skip to main content

Evolutionary Equilibria in Computer Networks

This talk applies ideas from evolutionary and Bayesian game theory to analyzing traffic patterns in a computer network.

In many computer systems, users share a common set of resources, which can lead to strategic interactions. An example is a computer network through which many users may send messages. A traditional approach is to collect all service requests and have a central mechanism compute an allocation that maximizes some measure of desired network performance. In economic terms, this corresponds to central planning. A decentralized approach would be to let users choose their own routes for their messages. This leads to a strategic game situation with many similarities to traffic flow. In a seminal paper, Koutsoupias and Papadimitriou investigated the difference between the (socially) worst Nash equilibrium and the best allocation achievable by central planning for such a network routing game. This talk analyzes the evolutionarily stable strategies of a Bayesian variant of Papadimitrou's network game. I consider the difference between the worst evolutionary equilibrium and the optimal central allocation, and how to compute an evolutionarily stable equilibrium. The talk does not presuppose familiarity with evolutionary game theory.