The complexity of optimizing atomic congestion
Title Of the Talk: “ The complexity of optimizing atomic congestion “
Speakers: Dr.Subrahmanyam Kalyanasundaram
Host Faculty: Dr. Maria Fransis
Date: : November 13; 4:30 pm
Abstract:
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.
This work is based on collaboration with Cornelius Brand, Robert Ganian and Fionn Mc Inerney. It was published in AAAI 2024 and Artificial Intelligence Journal.
Venue :C-LH5