From spanning trees to arborescences: new and extended cost sharing solutions

Eric Bahel () and Christian Trudeau

No 1601, Working Papers from University of Windsor, Department of Economics

Abstract: The paper examines minimal cost arborescence problems, which generalize the well-known minimal cost spanning tree (mcst) problems. We propose a new family of cost sharing methods that are easy to compute, as they closely relate to the network-building algorithm. These methods, called minimal incoming cost rules for arborescences (MICRAs), include as a particular case the extension of the folk solution introduced by Dutta and Mishra (2012). A simpler computational procedure thus obtains for this method. We also provide new axiomatizations of (a) the set of stable and symmetric MICRAs and (b) the folk solution. Finally, we closely examine two remarkable MICRAs. The first one relates to the cycle-complete rule for mcst problems introduced in Trudeau (2012). The second one contrasts with the folk rule by fully rewarding agents who help others connect to the source.

Keywords: arborescence problems; stable allocations, minimal incoming cost rules, leftover cost matrix (search for similar items in EconPapers)
JEL-codes: C71 D63 (search for similar items in EconPapers)
Pages: 29 pages
Date: 2016-01
New Economics Papers: this item is included in nep-cmp and nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://web2.uwindsor.ca/economics/RePEc/wis/pdf/1601.pdf First version, 2016 (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:wis:wpaper:1601

Access Statistics for this paper

More papers in Working Papers from University of Windsor, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Christian Trudeau ().