| 08 |
Toward uncongested infrastructures under user-equalityEquilibrium optimization of combinatorial congestion games 
|
|---|
In social infrastructures such as road and telecommunication networks, a link is congested and incurs more cost if many people use it. We introduce a method to compute better social design where users' cost lowers even when each user chooses a path or a combination of links selfishly. We develop a new method to compute the difference in cost when we modify the social design using a differentiable computation technique. Moreover, we compress a massive number of available paths into a data structure called a binary decision diagram, enabling us to deal with broader settings in a reasonable time. Our approach can contribute to reducing the congestion of people's flows and telecommunication networks by designing infrastructures, e.g., improving roads and expanding the bandwidth of links. Moreover, the proposed method is versatile and thus may be applicable for broader areas such as machine learning problems containing combinatorial optimization tasks.
[1] S. Sakaue, K. Nakamura, “Differentiable equilibrium computation with decision diagrams for Stackelberg models of combinatorial congestion games,” in Proc. 35th Conference on Neural Information Processing Systems (NeurIPS), 2021.
Kengo Nakamura / Linguistic Intelligence Research Group, Innovative Communication Laboratory
Email: cs-openhouse-ml@hco.ntt.co.jp