On Social Optimal Routing Under Selfish Learning
| Autor: | Alexandre M. Bayen, Walid Krichene, Milena Suarez Castillo |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Computer Science::Computer Science and Game Theory
0209 industrial biotechnology Mathematical optimization Control and Optimization Theoretical computer science Computational complexity theory Computer Networks and Communications Computer science Approximation algorithm 020206 networking & telecommunications 02 engineering and technology Optimal control symbols.namesake 020901 industrial engineering & automation Flow (mathematics) Control and Systems Engineering Nash equilibrium Signal Processing 0202 electrical engineering electronic engineering information engineering symbols Stackelberg competition Routing (electronic design automation) Greedy algorithm |
| Zdroj: | IEEE Transactions on Control of Network Systems. 5:479-488 |
| ISSN: | 2325-5870 |
| DOI: | 10.1109/tcns.2016.2619910 |
| Popis: | We consider a repeated routing game over a finite horizon with partial control under selfish response, in which a central authority can control a fraction of the flow and seeks to improve a network-wide objective, while the remaining flow applies an online learning algorithm. This finite horizon control problem is inspired from the one-shot Stackelberg routing game. Our setting is different in that we do not assume that the selfish players play a Nash equilibrium; instead, we assume that they apply an online learning algorithm. This results in an optimal control problem under learning dynamics. We propose different methods for approximately solving this problem: A greedy algorithm and a mirror descent algorithm based on the adjoint method. In particular, we derive the adjoint system equations of the Hedge dynamics and show that they can be solved efficiently. We compare the performance of these methods (in terms of achieved cost and computational complexity) on parallel networks, and on a model of the Los Angeles highway network. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|