TY - JOUR
T1 - Truth-telling and Nash equilibria in minimum cost spanning tree models
AU - Hougaard, Jens Leth
AU - Tvede, Mich
N1 - Funding Information:
The authors thank Yves Balasko, Gustavo Bergantinos, Hervé Moulin, Kurt Nielsen, Katrine Stagaard, Rodrigo Velez and two anonymous referees for helpful comments. Financial support from the Center for research in the Foundations of Electronic Markets (CFEM), funded by the Danish Council for Strategic Research is gratefully acknowledged.
PY - 2012/11/1
Y1 - 2012/11/1
N2 - In this paper we consider the minimum cost spanning tree model. We assume that a central planner aims at implementing a minimum cost spanning tree not knowing the true link costs. The central planner sets up a game where agents announce link costs, a tree is chosen and costs are allocated according to the rules of the game. We characterize ways of allocating costs such that true announcements constitute Nash equilibria both in case of full and incomplete information. In particular, we find that the Shapley rule based on the irreducible cost matrix is consistent with truthful announcements while a series of other well-known rules (such as the Bird-rule, Serial Equal Split, and the Proportional rule) are not.
AB - In this paper we consider the minimum cost spanning tree model. We assume that a central planner aims at implementing a minimum cost spanning tree not knowing the true link costs. The central planner sets up a game where agents announce link costs, a tree is chosen and costs are allocated according to the rules of the game. We characterize ways of allocating costs such that true announcements constitute Nash equilibria both in case of full and incomplete information. In particular, we find that the Shapley rule based on the irreducible cost matrix is consistent with truthful announcements while a series of other well-known rules (such as the Bird-rule, Serial Equal Split, and the Proportional rule) are not.
KW - Bayesian Nash equilibrium
KW - Incomplete information
KW - Minimum cost spanning tree
KW - Nash equilibrium
KW - Shapley value
KW - Truth-telling
UR - http://www.scopus.com/inward/record.url?scp=84863988855&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863988855&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2012.05.023
DO - 10.1016/j.ejor.2012.05.023
M3 - Article
AN - SCOPUS:84863988855
SN - 0377-2217
VL - 222
SP - 566
EP - 570
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 3
ER -