TY - JOUR
AU - Nakamura, Kengo
AU - Sakaue, Shinsaku
AU - Yasuda, Norihito
PY - 2020/04/03
Y2 - 2021/04/22
TI - Practical Frank–Wolfe Method with Decision Diagrams for Computing Wardrop Equilibrium of Combinatorial Congestion Games
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 34
IS - 02
SE - AAAI Technical Track: Game Theory and Economic Paradigms
DO - 10.1609/aaai.v34i02.5596
UR - https://ojs.aaai.org/index.php/AAAI/article/view/5596
SP - 2200-2209
AB - <p>Computation of equilibria for congestion games has been an important research subject. In many realistic scenarios, each strategy of congestion games is given by a combination of elements that satisfies certain constraints; such games are called combinatorial congestion games. For example, given a road network with some toll roads, each strategy of routing games is a path (a combination of edges) whose total toll satisfies a certain budget constraint. Generally, given a ground set of <em>n</em> elements, the set of all such strategies, called the strategy set, can be large exponentially in <em>n</em>, and it often has complicated structures; these issues make equilibrium computation very hard. In this paper, we propose a practical algorithm for such hard equilibrium computation problems. We use data structures, called zero-suppressed binary decision diagrams (ZDDs), to compactly represent strategy sets, and we develop a Frank–Wolfe-style iterative equilibrium computation algorithm whose per-iteration complexity is linear in the size of the ZDD representation. We prove that an ϵ-approximate Wardrop equilibrium can be computed in <em>O</em>(poly(<em>n</em>)/<em>ϵ</em>) iterations, and we improve the result to <em>O</em>(poly(<em>n</em>) log <em>ϵ</em><sup>−1</sup>) for some special cases. Experiments confirm the practical utility of our method.</p>
ER -