Exhibition Program

Science of Communication and Computation

07

What happens if every player rushs selfishly?

Equilibrium computation of congestion games

Abstract

In a road or telecommunication network, an edge (link) may be congested and may incur more cost if many people use it. We can compute how much each edge will be congested if each user of such network chooses a path (route) selfishly, i.e. chooses a path with minimum cost without any guidance or control. The computation of congestion requires calculation of probability for each of all available paths, which is generally prohibitive because there are a great many number of paths. To overcome this problem, we use a data structure called binary decision diagram to represent all available paths compactly. With this data structure, we can speed up the computation dramatically, and can compute such state of a network with realistic size. This study enables us to predict the state of congestion for a road and telecommunication network in a simple way, which is useful for designing such networks.

References

  1. K. Nakamura, S. Sakaue, N. Yasuda, “Practical Frank—Wolfe method with decision diagrams for computing Wardrop equilibrium of combinatorial congestion games,” in Proc. 34th AAAI Conference on Artificial Intelligence (AAAI), 2020.

Poster

Contact

Kengo Nakamura / Linguistic Intelligence Research Group, Innovative Communication Laboratory
Email: