Bounding the price of stability of undirected network design games with fair cost allocation is a challenging open problem in the Algorithmic Game Theory research agenda. Even though the generalization of such games in directed networks is well understood in terms of the price of stability (it is exactly $H_n$, the $n$-th harmonic number, for games with $n$ players), far less is known for network design games in undirected networks. The upper bound carries over to this case as well while the best known lower bound is $42/23approx 1.826$. For more restricted but interesting variants of such games such as broadcast and multicast games, sublogarithmic upper bounds are known while the best known lower bound is $12/7approx 1.714$. In the current paper, we improve the lower bounds as follows. We break the psychological barrier of $2$ by showing that the price of stability of undirected network design games is at least $348/155approx 2.245$. Our proof uses a recursive construction of a network design game with a simple gadget as the main building block. For broadcast and multicast games, we present new lower bounds of $20/11approx 1.818$ and $1.862$, respectively.

We consider broadcast network design games in undirected networks in which every player is a node wishing to receive communication from a distinguished source node $s$ and the cost of each communication link is equally shared among the downstream receivers according to the Shapley value. We prove that the Price of Stability of such games is constant, thus closing a long-standing open problem raised in cite{ADKTWR08}. Our result is obtained by means of homogenization, a new technique that, in any intermediate state locally diverging from a given optimal solution $T^*$, is able to restore local similarity by exploiting cost differences between nearby players in $T^*$.

In non-cooperative games played on highly decentralized networks the assumption that each player knows the strategy adopted by any other player may be too optimistic or even infeasible. In such situations, the set of players of which each player knows the chosen strategy can be modeled by means of a social knowledge graph in which nodes represent players and there is an edge from i to j if i knows j. Following the framework introduced in [7], we study the impact of social knowledge graphs on the fundamental multicast cost sharing game in which all the players want to receive the same communication from a given source in an undirected network. In the classical complete information case, such a game is known to be highly inefficient, since its price of anarchy can be as high as the total number of players $rho$. We first show that, under our incomplete information setting, pure Nash equilibria always exist only if the social knowledge graph is directed acyclic (DAG). We then prove that the price of stability of any DAG is at least $frac{1}{2}logrho$ and provide a DAG lowering the classical price of anarchy to a value between $frac{1}{2}logrho$ and $log^2rho$ . If specific instances of the game are concerned, that is if the social knowledge graph can be selected as a function of the instance, we show that the price of stability is at least $frac{4rho}{rho+3}$, and that the same bound holds also for the price of anarchy of any social knowledge graph (not only DAGs). Moreover, we provide a nearly matching upper bound by proving that, for any fixed instance, there always exists a DAG yielding a price of anarchy less than 4. Our results open a new window on how the performances of non-cooperative systems may benefit from the lack of total knowledge among players.