Title: Spectral methods for the convergence of best-response dynamics
Context: Game theory has emerged as a fundamental tool for the design and analysis of decentralized resource allocation mechanisms in networks. It has found applications in as diverse areas as load-balancing in server farms, power control and spectrum allocation in wireless networks, or congestion control in the Internet.
In particular, a substantial research effort has been devoted to the study of non-cooperative routing games in which each origin/destination flow is controlled by an autonomous agent that decides how its own traffic is routed through the network. Apart from the gain in scalability with respect to a centralized routing, there are wide-ranging advantages to such a decentralized routing scheme, including ease of deployment and robustness to failures and environmental disturbances. However, several questions arise when seeking to design and implement such a non-cooperative routing scheme.
One of the most fundamental of those questions concerns the convergence of uncoordinated routing agents to a Nash equilibrium. Among the most « natural » dynamics, there are the so-called best-response dynamics: each player adapts its routing strategy in turn to the strategies of the others. As frustrating as it may seem, even for very simple « parallel-links » topologies, very few convergence results are available. An original approach recently proposed is based on the concept of joint spectral radius, a mathematical tool used in control theory for the analysis of discrete-time switched dynamical systems. The fundamental idea is not to try to show the monotonic convergence of the best response dynamics, but rather to establish their asymptotic convergence by studying the joint spectral radius of the Jacobian matrices of the best response operators.
Link: https://emploi.cnrs.fr/Offres/CDD/UPR8001-BALPRA-002/Default.aspx?lang=EN
