From spanning trees to arborescences: new and extended cost sharing solutions
Eric Bahel, Christian Trudeau*
Date: 2016-05-07 4:30 pm – 5:00 pm
Last modified: 2016-04-15
Abstract
The paper examines minimum cost arborescence problems, which generalize the well-known minimum 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 minimum 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.