In this paper, motivated by the work of Azar et al. [3] we consider selective network design on bottleneck routing games. Assuming P ≠ NP we achieve the following results. For the unsplittable bottleneck games the trivial algorithm is a best possible approximation algorithm. For the k-splittable unweighted bottleneck games it is NP-hard to compute a best pure-strategy Nash equilibrium. Moreover no polynomial time algorithms can have a constant approximation ratio if the edge latency functions are continuous and non-decreasing.
展开▼
