BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: 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 equilibriu
 m 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 La
 placian matrix where each entry of the Laplacian is a Laplacian again. Thes
 e insights give rise to a path following formulation eventually putting the
  problem into PPAD. For the PPAD—hardness\, we reduce from computing an app
 roximate equilibrium for bimatrix win-lose games. As a byproduct of our ana
 lyse\, 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-independen
 t costs\, this yields an output-polynomial algorithm. (Joint work with Phil
 ipp Warode) 
DTSTAMP:20210506T152100
DTSTART:20210510T141500
CLASS:PUBLIC
LOCATION:online
SEQUENCE:0
SUMMARY:Max Klimm (Technische Universität Berlin): Complexity and Parametri
 c Computation of Equilibria in Atomic Splittable Congestion Games
UID:107776845@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20210510-L-Kli
 mm.html
END:VEVENT
END:VCALENDAR