  We consider a weighted Shapley network design game, where selfish players
choose paths in a network to minimize their cost. The cost function of each
edge in the network is affine linear with respect to the sum of weights of the
players who choose the edge. We first show the existence of \alpha-approximate
pure Nash equilibrium by constructing a potential function and establish an
upper bound O(log2(W)) of \alpha, where W is the sum of the weight of all
players. Furthermore, we assume that the coefficients of the cost function
(affine linear function) of the edge all are \phi-smooth random variables on
[0, 1]. In this case, we show that \epsilon-best response dynamics can compute
the (1 + \epsilon)\alpha-approximate pure Nash equilibrium (\epsilon is a
positive constant close to 0) 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.
