You are cordially invited to our next Monday Lecture &
Colloquium on May 10th at 14:15 h & 16:00 h, online via Zoom. Invitation link: Zoom - Invitation Time: Monday, May 10th - 14:15 h Lecture: Max Klimm (Technische Universität Berlin) Title: Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games Abstract:We settle the complexity of computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions as we show that the computation is PPAD-complete. To prove that the problem is contained in PPAD, we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique for this method is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix where each entry of the Laplacian is a Laplacian again. These insights give rise to a path following formulation eventually putting the problem into PPAD. For the PPAD—hardness, we reduce from computing an approximate equilibrium for bimatrix win-lose games. As a byproduct of our analyse, we obtain that also computing a multi-class Wardrop equilibrium with class-dependent affine cost functions is PPAD-complete as well. As another byproduct, we obtain an algorithm that computes a continuum of equilibria parametrised by the players’ flow demand. For games with player-independent costs, this yields an output-polynomial algorithm. (Joint work with Philipp Warode) BreakTime: Monday, May 10th - 16:00 h s.t. Colloquium: Aniket Shah (Ohio State University) Title: A q-analogue of Brion's identity Abstract: |