Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational players. $i$-th player wants to connect $s_i$ vertex of an edge-weighted graph $G$ to target vertex $t$ with a path $p_i$ as cheaply as possible. A strategy for player $i$ can be any path connecting $s_i$ to $t$. The cost for player $i$ is $\displaystyle \sum_{e\in p_i}\frac{c(e)}{n(e)}$ where $n(e)$ is the number of players that use the edge $e$ in their chosen paths. A strategy profile $p$ is a vector of strategies of all players, $p=(p_0,\ldots, p_{n-1})$. A strategy profile is Nash equilibrium if no player can change its strategy $p_i$ to $p_i'$ and improve its cost. The (social) cost of a strategy profile $p$ is the cost of the created network, i.e., the sum of the costs of all edges in the created network, which is, in turn, the sum of all players' costs. Note that in a multicast game an optimum social cost network forms a Steiner tree on the terminals $s_i$ and $t$ for $i=0,\ldots,n-1$.
I am interested into the price of stability, which is the ratio of the cost of the best Nash equilibrium strategy profile over the cost of a social optimum. Major part of the work has been done bounding this value as a function of $n$, but my question is in a slightly different direction.
After checking small number of players(e.g. 3 players, in http://arxiv.org/pdf/1211.2090.pdf), special type of underlying graphs(e.g. cycles, in http://link.springer.com/chapter/10.1007%2F978-3-642-35311-6_45 and http://arxiv.org/pdf/1507.04222v1.pdf) and the existing worst lower bounds(http://link.springer.com/chapter/10.1007%2F978-3-642-16170-4_9), I conjecture the following: the worst case price of stability for $n$ players $PoS(n)$ is achieved by games which have unique Nash equilibrium. This is the conjecture in a strong sense. In a weak sense it would sound as follows: $PoS(n)$ is achieved by games with $m\geq n$ players and unique Nash equilibrium.
Some motivation why this question might be interesting:
- Games with unique Nash equilibrium are interesting because there is no central authority needed to help players achieve the best equilibrium state.
- It is not immediate that this question is harder or easier than finding exact bounds of $PoS(n)$ (which on its own is considered to be a difficult problem), and probably it requires different techniques/approaches.
- One could immediately try to generalize the result to general network design games. I do not have counterexample for that case as well. Another direction for generalization could be towards congestion games, but some care should be taken into congestion functions and defining price of stability.
Could you help to prove (disprove) conjecture(s)?
