Strategyproof Nash Equilibria in Minimum Cost Spanning Tree Models

Jens Hougaard () and Mich Tvede

No 01_2010, MSAP Working Paper Series from University of Copenhagen, Department of Food and Resource Economics

Abstract: In this paper we consider the Minimum Cost Spanning Tree model. We assume that a central planner aims at implementing the minimum cost spanning tree not knowing the true link costs. The central planner sets up a game where agents announce the 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. In particular, we nd that the Shapley rule with respect to 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, the Proportional rule etc.) are not.

Keywords: Minimum cost spanning tree; Strategyproof Implementation; Nash equilibrium; Shapley value (search for similar items in EconPapers)
Pages: 20 pages
Date: 2010-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://okonomi.foi.dk/workingpapers/MSAPpdf/MSAP2010/MSAP_WP01_2010.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:foi:msapwp:01_2010

Access Statistics for this paper

More papers in MSAP Working Paper Series from University of Copenhagen, Department of Food and Resource Economics Contact information at EDIRC.
Bibliographic data for series maintained by Geir Tveit ().