Implementing efficient graphs in connection networks

We consider the problem of sharing the cost of a network that meets the connection demands of a set of agents. The agents simultaneously choose paths in the network connecting their demand nodes. A mechanism splits the total cost of the network formed among the participants. We introduce two new properties of implementation. The first property, Pareto Nash implementation (PNI), requires that the efficient outcome always be implemented in a Nash equilibrium and that the efficient outcome Pareto dominates any other Nash equilibrium. The average cost mechanism and other asymmetric variations are the only mechanisms that meet PNI. These mechanisms are also characterized under strong Nash implementation. The second property, weakly Pareto Nash implementation (WPNI), requires that the least inefficient equilibrium Pareto dominates any other equilibrium. The egalitarian mechanism (EG) and other asymmetric variations are the only mechanisms that meet WPNI and individual rationality. EG minimizes the price of stability across all individually rational mechanisms. Copyright Springer-Verlag Berlin Heidelberg 2013