View in EDS

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

Saved in:
Bibliographic Details
Title: Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians.
Authors: Klimm, Max1 (AUTHOR) klimm@tu-berlin.de, Warode, Philipp1 (AUTHOR) warode@math.tu-berlin.de
Source: SIAM Journal on Computing. 2025, Vol. 54 Issue 5, p1241-1293. 53p.
Subjects: Computational complexity, Equilibrium, Cost functions, Traffic flow, Laplacian operator, Laplacian matrices
Abstract: 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 \(\mathsf{PPAD}\) -complete. To prove that the problem is contained in \(\mathsf{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 us 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 us to orient the states giving rise to unique predecessor and successor states, thus putting the problem into \(\mathsf{PPAD}\). For the \(\mathsf{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 multiclass Wardrop equilibrium with class-dependent affine cost functions is \(\mathsf{PPAD}\) -complete as well. As another byproduct of our \(\mathsf{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. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract: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 \(\mathsf{PPAD}\) -complete. To prove that the problem is contained in \(\mathsf{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 us 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 us to orient the states giving rise to unique predecessor and successor states, thus putting the problem into \(\mathsf{PPAD}\). For the \(\mathsf{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 multiclass Wardrop equilibrium with class-dependent affine cost functions is \(\mathsf{PPAD}\) -complete as well. As another byproduct of our \(\mathsf{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. [ABSTRACT FROM AUTHOR]
ISSN:00975397
DOI:10.1137/20M1361523