[Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - May 10th 2021

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

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:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09
No password required.

Online via:
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)

Break

Time: Monday, May 10th - 16:00 h s.t.

Colloquium: Aniket Shah (Ohio State University)

Title: A q-analogue of Brion's identity

Abstract:

Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0.