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.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20210510-L-Klimm.html
END:VEVENT
END:VCALENDAR