English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We show that computing an equilibrium in atomic splittable congestion gameswith player-specific affine cost functions $l_{e,i}(x) = a_{e,i} x + b_{e,i}$is $\mathsf{PPAD}$-complete. To prove that the problem is contained in$\mathsf{PPAD}$, we develop a homotopy method that traces an equilibrium forvarying flow demands of the players. A key technique for this method is todescribe the evolution of the equilibrium locally by a novel block Laplacianmatrix. Using the properties of this matrix give rise to a path followingformulation for computing an equilibrium where states correspond to supportsthat are feasible for some demands. A closer investigation of the blockLaplacian system further allows to orient the states giving rise to uniquepredecessor and successor states thus putting the problem into $\mathsf{PPAD}$.For the $\mathsf{PPAD}$-hardness, we reduce from computing an approximateequilibrium of a bimatrix win-lose game. As a byproduct of our reduction wefurther show that computing a multi-class Wardrop equilibrium with classdependent affine cost functions is $\mathsf{PPAD}$-complete as well.  As another byproduct of our $\mathsf{PPAD}$-completeness proof, we obtain analgorithm that computes a continuum of equilibria parametrized by the players'flow demand. For player-specific costs, the algorithm runs in polynomial space.For games with player-independent costs, we obtain an algorithm computing allequilibria as a function of the flow demand that runs in time polynomial in theoutput.

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