Evolutionary dynamics and potential games in non-cooperative routing

Eitan Altman; Yezekael  Hayel; Hisao Kameda

1st International ICST Workshop on Wireless Networks: Communication, Cooperation and Competition

Research Article

Evolutionary dynamics and potential games in non-cooperative routing

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/WIOPT.2007.4480096,
    author={Eitan Altman and Yezekael  Hayel and Hisao Kameda},
    title={Evolutionary dynamics and potential games in non-cooperative routing},
    proceedings={1st International ICST Workshop on Wireless Networks: Communication, Cooperation and Competition},
    publisher={IEEE},
    proceedings_a={WNC\^{}3},
    year={2008},
    month={3},
    keywords={Cities and towns  Context modeling  Convergence  Cost function  Nash equilibrium  Network topology  Roads  Routing  Telecommunication traffic  Traffic control},
    doi={10.1109/WIOPT.2007.4480096}
}

Eitan Altman
Yezekael Hayel
Hisao Kameda
Year: 2008
Evolutionary dynamics and potential games in non-cooperative routing
WNC^3
IEEE
DOI: 10.1109/WIOPT.2007.4480096

Eitan Altman¹^,*, Yezekael Hayel²^,*, Hisao Kameda³^,*

1: INRIA Sophia Antipolis 2004, route des Lucioles 06902, Sophia Antipolis, France
2: LIA/University of Avignon 339, chemin des Meinajaries 84911, Avignon, France
3: University of Tsukuba Tsukuba Science City, 305-8573, Japan

*Contact email: eitan.altman@sophia.inria.fr, yezekael.hayel@univ-avignon.fr, kameda@cs.tsukuba.acjp

Abstract

We consider a routing problem in a network with a general topology. Considering a link cost which is linear in the link flow, we obtain a unique Nash equilibrium and show that the non-cooperative game can be expressed as a potential game. We establish various convergence and stability properties of of the equilibrium related to the routing problem being a potential game. We then consider the routing problem in the framework of a population game and study the evolution of the size of the populations when the replicator dynamics is used.

Keywords: Cities and towns Context modeling Convergence Cost function Nash equilibrium Network topology Roads Routing Telecommunication traffic Traffic control

Published: 2008-03-31
Publisher: IEEE
Modified: 2011-07-28

: http://dx.doi.org/10.1109/WIOPT.2007.4480096