language: en

Optimal Routing Control: Game Theoretic Approach

Richard J. La, and Venkat Anantharam
Department of Electrical Engineering and Computer Science University of California at Berkeley
hyongla@eecs.berkeley.edu, ananth@eecs.berkeley.edu

Abstract Communication networks shared by selfish users are considered and modeled as noncooperative repeated games. Each user is interested only in optimizing its own performance by controlling the routing of its load. We investigate the existence of a NEP that achieves the system-wide optimal cost. The existence of a NEP that not only achieves the system-wide optimal cost but also yields a cost for each user no greater than its stage game NEP cost is shown for two-node multiple link networks. It is shown that more general networks where all users have the same source-destination pair have a NEP that achieves the minimum total system cost under a mild technical condition. It is shown general networks with users having multiple source-destination pairs don't necessarily have such an NEP.

1 Introduction