Computing Equilibria in Atomic Splittable Routing Games

An atomic splittable routing game (ASRG) is a network congestion problem where each player has some finite amount of flow he wants to send in the network, while minimizing his cost.

It has been known that equilibrium exists in ASRG games. But computing the equilibrium for ASRG has been an open problem for many years.

In this report we give an algorithm for finding the equilibrium when the underlying network is parallel edge graph with linear latencies. Our algorithm is similar to an earlier algorithm by Huang [Theory Comp. Sys., 2013], but uses a modified support enumeration step.

Next we give an algorithm for finding the equilibrium for two player ASRG when the underlying network is a parallel-edge graph with quadratic latencies. Our algorithm is obtained by using support enumeration, along with convex programming and results about the structure of equilibrium with quadratic latencies. We assume in this report that exact solutions to convex programs and binary searches can be obtained in polynomial time.