@article{Nakamura_Sakaue_Yasuda_2020, title={Practical Frank–Wolfe Method with Decision Diagrams for Computing Wardrop Equilibrium of Combinatorial Congestion Games}, volume={34}, url={https://ojs.aaai.org/index.php/AAAI/article/view/5596}, DOI={10.1609/aaai.v34i02.5596}, abstractNote={<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>}, number={02}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Nakamura, Kengo and Sakaue, Shinsaku and Yasuda, Norihito}, year={2020}, month={Apr.}, pages={2200-2209} }