Conferences at Department of Economics, University of Toronto, Canadian Economic Theory Conference 2016

Font Size:  Small  Medium  Large

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.

Full Text: Untitled