Evolutionary equilibrium in Bayesian routing games: Specialization and niche formation

In this paper we consider Nash equilibria for the selfish task allocation game proposed in Koutsoupias, Papadimitriou (1999) [26], where a set of n users with unsplittable tasks of different size try to access m parallel links with different speeds. In this game, a player can use a mixed strategy (where he uses different links with a positive probability); then lie is indifferent between the different link choices. This means that the player may well deviate to a different strategy over time. We propose the concept of evolutionary stable strategies (ESS) as a criterion for stable Nash equilibria, i.e. equilibria where no player is likely to deviate from his strategy. An ESS is a steady state that can be reached by a user community via evolutionary processes in which more successful strategies spread over time. The concept has been used widely in biology and economics to analyze the dynamics of strategic interactions. We first define a symmetric version of a Bayesian parallel links game where every player is not assigned a task of a fixed size but instead is assigned a task drawn from a distribution, which is the same for all players. We establish that the ESS is uniquely determined for a given symmetric Bayesian parallel links game (when it exists). Thus evolutionary stability places strong constraints on the assignment of tasks to links. We characterize ESS for the Bayesian parallel links game, and investigate the structure of evolutionarily stable equilibria: In an ESS, links acquire niches, meaning that there is minimal overlap in the tasks served by different links. Furthermore, all links with the same speed are interchangeable for every task with weight w: Every player must place a task with weight in on links having the same speed with the same probability. Also, bigger tasks must be assigned to faster links and faster links Must have a bigger load. Finally, we introduce a clustering condition - roughly, distinct links must serve distinct tasks - that is sufficient for evolutionary stability, and can be used to find an ESS in many models. Published by Elsevier B.V.