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/

Global: Zendy Tools annual

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

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We present polynomial-time algorithms as well as hardness results forequilibrium computation in atomic splittable routing games, for the case ofgeneral convex cost functions. These games model traffic in freighttransportation, market oligopolies, data networks, and various otherapplications. An atomic splittable routing game is played on a network wherethe edges have traffic-dependent cost functions, and player strategiescorrespond to flows in the network. A player can thus split it's trafficarbitrarily among different paths. While many properties of equilibria in thesegames have been studied, efficient algorithms for equilibrium computation areknown for only two cases: if cost functions are affine, or if players aresymmetric. Neither of these conditions is met in most practical applications.We present two algorithms for routing games with general convex cost functionson parallel links. The first algorithm is exponential in the number of players,while the second is exponential in the number of edges; thus if either of theseis small, we get a polynomial-time algorithm. These are the first algorithmsfor these games with convex cost functions. Lastly, we show that in generalnetworks, given input $C$, it is NP-hard to decide if there exists anequilibrium where every player has cost at most $C$.

Equilibrium Computation in Atomic Splittable Routing Games with Convex Cost Functions