@article{Gan2026, 
author = {Hangxin Gan and Xianhao Meng and Chunying Ren and Yongtang Shi},
title = {Approximate Nash Equilibria Algorithms for Shapley Network Design Games},
year = {2026},
journal = {Tsinghua Science and Technology},
keywords = {Artificial intelligence, Approximate Nash equilibrium, Affine linear cost function, Best response dynamics, Potential function},
url = {https://www.sciopen.com/article/10.26599/TST.2026.9010022},
doi = {10.26599/TST.2026.9010022},
abstract = {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 the weights of the players choosing the edge. We first show the existence of an α-approximate pure Nash equilibrium by constructing a potential function and establish an upper bound O(log2(W )) on α, where W is the sum of the weights of all players. Furthermore, we assume that the coefficients of the cost function (affine linear function) of the edge are all ϕ-smooth random variables on [0, 1]. In this case, we show that ϵ-best response dynamics can compute the (1 + ϵ)α-approximate pure Nash equilibrium (ϵ is a positive constant close to 0) in polynomial time by proving that the expected number of iterations is polynomial in 1/ϵ , ϕ, the number of players and the number of edges in the network.}
}