| Description |
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 due to congestion. It is known that equilibria exist in these games, and can be computed in polynomial-time for the case of linear cost functions. However, the case of equilibrium computation with more general cost functions has been an open problem for many years.
We give an algorithm for computing an equilibrium in the case of parallel-edge graphs with quadratic cost functions and two players. Our algorithm is obtained by using support enumeration, along with convex programming and results about the structure of equilibrium with quadratic cost functions. We also present some obstacles to generalizing our algorithm to more general cases.
Finally, we present some hardness results regarding equilibrium computation in more general games, when different players may experience different delays on an edge.
|