Ruben Juarez
University of Hawai‘i at Manoa
Abstract
We consider the problem of sharing the cost of a network which meets the connection demands of a set of agents. The agents simultaneously choose a path in the network connecting the demand nodes of the agents, and a mechanism splits the total cost of the network formed among the participants.
The recent literature has converged to the Shapley mechanism (Sh) which splits the cost of edges equally among its users. We look at alternatives to this mechanism because of two reasons. On one hand, Sh is inefficient, asymmetric and discontinuous at equilibrium. On the other hand, Sh requires the amount of information which may not be practical in many settings.
We characterize a class of mechanisms in a setting of minimal information requirement, specifically when the inputs of a mechanism are the total cost of the network formed and the cost of the paths demanded by the agents. The Average Cost mechanism (AC) and other asymmetric mechanisms implement the efficient connection. These mechanisms are characterized under three alternative robust properties of efficient implementation.
We also show that efficiency and individual rationality are mutually incompatible. The Egalitarian mechanism (EG), a variation of AC that meets individual rationality, is an optimal mechanism (under the price of stability measure) across all individually rational mechanisms. EG outperforms Sh on the grounds of information requirements, stability and symmetry at equilibrium. Moreover, EG is no more inefficient than Sh.