Approximate Nash Equilibria Algorithms for Network Design Games

We consider a weighted network design game, where selfish players chooses paths in a network to minimize their cost. The cost function of each edge in the network is affine linear, namely c_e(W_e) = a_eW_e + b_e, where a_e, b_e > 0 are only related to the edge e and We is the total weight of the players that choose a path containing edge e. We first show the existence of \alpha-approximate Nash equilibrium and prove the upper bound of \alpha is O(log2(W)), where W is the sum of the weight of all players. Furthermore, considering that compute the \alpha-approximate Nash equilibrium is PLS-complete, we assume that {ae, be}_{e\in E} are \phi-smooth random variables on [0, 1]. In this case, we show that \epsilon-better response dynamics can compute the {\alpha}-approximate Nash Equilibrium in polynomial time by proving the expected number of iterations is polynomial in 1/\epsilon, \phi, the number of players and the number of edges in the network.