Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 189718070 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Klimm%2C+Max%22">Klimm, Max</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> klimm@tu-berlin.de</i><br /><searchLink fieldCode="AR" term="%22Warode%2C+Philipp%22">Warode, Philipp</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> warode@math.tu-berlin.de</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 2025, Vol. 54 Issue 5, p1241-1293. 53p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Equilibrium%22">Equilibrium</searchLink><br /><searchLink fieldCode="DE" term="%22Cost+functions%22">Cost functions</searchLink><br /><searchLink fieldCode="DE" term="%22Traffic+flow%22">Traffic flow</searchLink><br /><searchLink fieldCode="DE" term="%22Laplacian+operator%22">Laplacian operator</searchLink><br /><searchLink fieldCode="DE" term="%22Laplacian+matrices%22">Laplacian matrices</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=189718070 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/20M1361523 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 53 StartPage: 1241 Subjects: – SubjectFull: Computational complexity Type: general – SubjectFull: Equilibrium Type: general – SubjectFull: Cost functions Type: general – SubjectFull: Traffic flow Type: general – SubjectFull: Laplacian operator Type: general – SubjectFull: Laplacian matrices Type: general Titles: – TitleFull: Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Klimm, Max – PersonEntity: Name: NameFull: Warode, Philipp IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: 2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 00975397 Numbering: – Type: volume Value: 54 – Type: issue Value: 5 Titles: – TitleFull: SIAM Journal on Computing Type: main |
| ResultId | 1 |
