Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians

We settle the complexity of computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions l e,i (x) = a e,i x + b e,i 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. Using the properties of this matrix allows to recompute efficiently the Laplacian after the support of the equilibrium changes by matrix pivot operations. These insights give rise to a path following formulation for computing an equilibrium where states correspond to supports that are feasible for some demands and neighboring supports are feasible for increased or decreased flow demands. A closer investigation of the block Laplacian system further allows to orient the states giving rise to unique predecessor and successor states thus putting the problem into PPAD. For the PPAD-hardness, we reduce from computing an approximate equilibrium of a bimatrix win-lose game. As a byproduct of our reduction we further show that computing a multi-class Wardrop equilibrium with class dependent affine cost functions is PPAD-complete as well.

As another byproduct of our PPAD-completeness proof, we obtain an algorithm that computes a continuum of equilibria parametrized by the players' flow demand. For player-specific costs, the continuum may involve several increases and decreases of the demand and yields an algorithm that runs in polynomial space. For games with player-independent costs, only demand increases are necessary yielding an algorithm computing all equilibria as a function of the flow demand that runs in time polynomial in the output.