Minimum cost spanning tree problems as value sharing problems

Christian Trudeau

International Journal of Game Theory, 2023, vol. 52, issue 1, No 10, 253-272

Abstract: Abstract Minimum cost spanning tree (mcst) problems study situations in which agents must connect to a source to obtain a good, with the cost of building an edge being independent of the number of users. We reinterpret mcst problems as value sharing problems, and show that the folk and cycle-complete solutions, two of the most studied cost-sharing solutions for mcst problems, do not share values in a consistent way. More precisely, two mcst problems yielding the same value sharing problem might lead to value being shared in different ways. However, they satisfy a weaker version of the property that applies only to elementary problems, in which the cost on an edge can only be 0 or 1. The folk solution satisfies the version related to the public approach, while the cycle-complete solution satisfies the one related to the private approach, which differ depending if we allow a group to use the nodes of other agents or only their own nodes. We then build axiomatizations built on these properties. While the two solutions are usually seen as competitors in the private approach, the results point towards a different interpretation: the two solutions are based on different interpretations of the mcst problem, but are otherwise conceptually very close.

Keywords: Minimum cost spanning tree; Value sharing; Cycle-complete solution; Folk solution (search for similar items in EconPapers)
JEL-codes: C71 D63 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-022-00818-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
Working Paper: Minimum cost spanning tree problems as value sharing problems (2021)
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:spr:jogath:v:52:y:2023:i:1:d:10.1007_s00182-022-00818-z

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-022-00818-z

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().