تقرير
The Complexity of Optimizing Atomic Congestion
| العنوان: | The Complexity of Optimizing Atomic Congestion |
|---|---|
| المؤلفون: | Brand, Cornelius, Ganian, Robert, Kalyanasundaram, Subrahmanyam, Inerney, Fionn Mc |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computer Science and Game Theory, Computer Science - Artificial Intelligence, Computer Science - 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. Comment: Accepted at AAAI 2024 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2312.10219 |
| رقم الأكسشن: | edsarx.2312.10219 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |