Research map / Learning theory and algorithms / Submodular and game algorithms
The Complexity of Optimizing Atomic Congestion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies the parameterized complexity of computing system-optimal flow assignments in atomic congestion games (SOAC) and its min-max variant (mSOAC), giving NP-hardness, W[1]-hardness, and an FPT algorithm parameterized by slim treecut width plus maximum capacity.
Problem
Computing a system-optimal set of strategies (minimum total cost routing) in atomic congestion games, and its min-max variant where up to alpha agents may be left unrouted; the goal is to identify structural parameters giving tractability.
Approach
Shows that vertex-separator parameters (treewidth, treedepth) do not yield tractability and that edge-cut based parameters are the right ones; gives a dynamic program over spanning-tree decompositions (slim treecut width, local feedback edge number) with snapshot records parameterized by maximum link capacity.
Key results
- SOAC is NP-hard even on skeletons in K_{2,N} and on DAGs with treewidth and max degree at most 3.
- SOAC is FPT when parameterized by slim treecut width of the skeleton plus maximum capacity, via a dynamic program running in cmax^{kappa^{O(kappa^4)}} time.
- SOAC is W[1]-hard parameterized by treecut width even with maximum capacity 1, showing the FPT result cannot be lifted to treecut width.
- mSOAC is FPT parameterized by treewidth plus maximum degree, maximum capacity and alpha.
Surprising findings
- SOAC remains NP-hard even on networks with treewidth 2 (star plus a vertex) and on DAGs of treewidth at most 3, ruling out standard width parameters alone.
- mSOAC is NP-hard on trees with maximum capacity 1, even though it generalizes SOAC.
Limitations
- Algorithms are FPT only under the combined parameter slim treecut width plus maximum capacity; running time is hyper-exponential in the parameter.
- mSOAC tractability is shown only for bounded-degree networks parameterized by treewidth; bounded-capacity star networks remain open for alpha.
Experimental setup
Builds on: Rosenthal congestion games treecut width slim treecut width spanning tree decompositions
Closest papers by meaning
- Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games (NeurIPS 2021 · similarity 0.88)
- Practical Frank–Wolfe Method with Decision Diagrams for Computing Wardrop Equilibrium of Combinatorial Congestion Games (AAAI 2020 · similarity 0.87)
- Information Design for Congestion Games with Unknown Demand (AAAI 2024 · similarity 0.86)
- Enhancing the Efficiency of Altruism and Taxes in Affine Congestion Games through Signalling (AAAI 2024 · similarity 0.85)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.85)
- Strategic Network Creation for Enabling Greedy Routing (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.