Finding Highly Social Nash Equilibria in the Spanning Tree Congestion Game

Finding Nash equilibria can be a difficult task. We investigate a method for finding desirable equilibria in terms of social welfare by first approximating the social optimum and then finding a nearby equilibrium by means of social and selfish best response dynamics. We evaluate equilibrium quality by examining the cost-ratio between the found equilibrium and a random benchmark. To illustrate this approach we employ the spanning tree congestion game in which each player tries to create a minimum-cost spanning tree where the cost of using an edge is dependent on the number of players using the edge. We find that in some cases using a heuristic approach to obtain a starting point for best response dynamics will very quickly lead to a Nash equilibrium of better social value than one found from a random best response starting point