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

Jens Leth Hougaard, Mich Tvede

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)566-570
Number of pages5
JournalEuropean Journal of Operational Research
Issue number3
StatePublished - Nov 1 2012


  • Bayesian Nash equilibrium
  • Incomplete information
  • Minimum cost spanning tree
  • Nash equilibrium
  • Shapley value
  • Truth-telling

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Truth-telling and Nash equilibria in minimum cost spanning tree models'. Together they form a unique fingerprint.

Cite this