Truth-telling and Nash equilibria in minimum cost spanning tree models
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Truth-telling and Nash equilibria in minimum cost spanning tree models. / Hougaard, Jens Leth; Tvede, Mich.
In: European Journal of Operational Research, Vol. 222, No. 3, 2012, p. 566-570.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Truth-telling and Nash equilibria in minimum cost spanning tree models
AU - Hougaard, Jens Leth
AU - Tvede, Mich
PY - 2012
Y1 - 2012
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.
U2 - 10.1016/j.ejor.2012.05.023
DO - 10.1016/j.ejor.2012.05.023
M3 - Journal article
VL - 222
SP - 566
EP - 570
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 3
ER -
ID: 38252493