Investigation on irreducible cost vectors in minimum cost arborescence problems
Yoshifumi Kusunoki and
European Journal of Operational Research, 2017, vol. 261, issue 1, 214-221
We study cost allocation rules in minimum cost arborescence problems, where agents need to build a network to a source in order to obtain some resource. Provided a vector of costs of edges (agent/source pairs), the agents cooperate to construct a minimum cost arborescence rooted at the source in order to reduce the total building cost. Minimum cost arborescence problems are extensions of well-studied minimum cost spanning tree problems to deal with asymmetric edge costs. Regarding cost allocation rules in minimum cost arborescence problems, Dutta and Mishra (2012) extended the folk rule, which is one of the most important rules in minimum cost spanning tree problems, based on the problem with the vector of the most reduced costs, called irreducible form. In minimum cost spanning tree problems, several axiomatic characterizations of the folk rule have been proposed. However, it is difficult to extend them in minimum cost arborescence problems. One of the reasons is that strong and reasonable axioms in minimum cost spanning tree problems, which imply irreducible-form dependence of cost allocation rules, are not satisfied by the folk rule in minimum cost arborescence problems. Hence, we search for other axioms which imply irreducible-form dependence. For this purpose, we investigate irreducible cost vectors in minimum cost arborescence problems, and characterize the irreducible form.
Keywords: Game theory; Graph theory; Minimum cost arborescence problem; Irreducible cost; Cost allocation rule (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations Track citations by RSS feed
Downloads: (external link)
Full text for ScienceDirect subscribers only
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: http://EconPapers.repec.org/RePEc:eee:ejores:v:261:y:2017:i:1:p:214-221
Access Statistics for this article
European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati
More articles in European Journal of Operational Research from Elsevier
Series data maintained by Dana Niculescu ().