Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2312.10219 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913558568108032 |
|---|---|
| author | Brand, Cornelius Ganian, Robert Kalyanasundaram, Subrahmanyam Inerney, Fionn Mc |
| author_facet | Brand, Cornelius Ganian, Robert Kalyanasundaram, Subrahmanyam Inerney, Fionn Mc |
| contents | Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies -- that is, a centrally planned routing that minimizes the average cost of agents -- is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_10219 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Complexity of Optimizing Atomic Congestion Brand, Cornelius Ganian, Robert Kalyanasundaram, Subrahmanyam Inerney, Fionn Mc Computer Science and Game Theory Artificial Intelligence Computational Complexity Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies -- that is, a centrally planned routing that minimizes the average cost of agents -- is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem. |
| title | The Complexity of Optimizing Atomic Congestion |
| topic | Computer Science and Game Theory Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2312.10219 |