Truth-telling and Nash equilibria in minimum cost spanning tree models

TY - JOUR

T1 - Truth-telling and Nash equilibria in minimum cost spanning tree models

AU - Hougaard, Jens Leth

AU - Tvede, Mich

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.

U2 - 10.1016/j.ejor.2012.05.023

DO - 10.1016/j.ejor.2012.05.023

M3 - Journal article

SN - 0377-2217

VL - 222

SP - 566

EP - 570

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -