Dutta, Bhaskar and Mishra, Debasis (2009) Minimum cost arborescences. Working Paper. Coventry: University of Warwick, Department of Economics. (Warwick economic research papers.

Preview

PDF WRAP_Dutta_twerp_889.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (297Kb)

Abstract

In this paper, we analyze the cost allocation problem when a group of agents or nodes have to be connected to a source, and where the cost matrix describing the cost of connecting each pair of agents is not necessarily symmetric, thus extending the well-studied problem of minimum cost spanning tree games, where the costs are assumed to be symmetric. The focus is on rules which satisfy axioms representing incentive and fairness properties. We show that while some results are similar, there are also signifcant differences between the frameworks corresponding to symmetric and asymmetric cost matrices.

Item Type:	Working or Discussion Paper (Working Paper)
Subjects:	H Social Sciences > HF Commerce
Divisions:	Faculty of Social Sciences > Economics
Library of Congress Subject Headings (LCSH):	Cost allocation, Game theory, Stability, Symmetry (Mathematics)
Series Name:	Warwick economic research papers
Publisher:	University of Warwick, Department of Economics
Place of Publication:	Coventry
Date:	8 January 2009
Number:	No.889
Number of Pages:	30
Status:	Not Peer Reviewed
Access rights to Published version:	Open Access
References:	A. Bogomolnaia, R. H., , and H. Moulin (2008): \Sharing the Cost of a Capacity Network,"Working Paper, Rice University. Bergantinos, G. and A. Kar (2008): \Obligation Rules,"Working Paper, Universidade Vigo. Bergantinos, G. and J. J. Vidal-Puga (2007a): \A Fair Rule for Minimum Cost Spanning Tree Problems," Journal of Economic Theory, 137, 326{352. ||| (2007b): \The Optimistic TU Game in Minimum Cost Spanning Tree Problems," International Journal of Game Theory, 36, 223{239. ||| (2007c): \Several Approaches to the Same Rule in Minimum Cost Spanning Tree Problems,"Working Paper, Universidade Vigo. Bird, C. G. (1976): \On Cost Allocation of a Spanning Tree: A Game Theoretic Approach," Networks, 6, 335{350. Bogomolnaia, A. and H. Moulin (2008): \Beyond the Folk Solution in the Minimum Cost Spanning Tree Problem,"Working Paper, Rice University. Branzei, R., S. Moretti, H. Norde, and S. Tijs (2004): \The P-Value for Cost Sharing in Minimum Cost Spanning Tree Situations," Theory and Decision, 56, 47{61. |||(2005): \The Bird Core for Minimum Cost Spanning Tree Problems Revisited: Mono- tonicity and Additivity Aspects,"Working Paper, Tilburg University (CentER DP). Chu, Y. J. and T. H. Liu (1965): \On the Shortest Arborescence of a Directed Graph," Science Sinica, 14, 1396{1400. Dutta, B. and A. Kar (2004): \Cost Monotonicity, Consistency and Minimum Cost Spanning Tree Games," Games and Economic Behavior, 48, 223{248. Edmonds, J. (1967): \Optimum Branchings," Journal of Reseseach National Bureau Stan- dards, 71B, 233{240. Feltkamp, V., S. Muto, and S. Tijs (1994): \On the Irreducible Core and the Equal Remaining Obligations Rule of Minimum Cost Spanning Extension Problems," Working Paper, Tilburg University (CentER DP). Herzog, S., S.Shenker, and D.Estrin (1997): \Sharing the Cost of Multicast Trees: An Axiomatic Analysis," IEEE/ACM Transactions on Networking, 847{860. Kar, A. (2002): \Axiomatization of the Shapley Value on Minimum Cost Spanning Tree Games," Games and Economic Behavior, 38, 265{277. Norde, H., S. Morettie, and S. Tijs (2001): \Minimum Cost Spanning Tree Games and Population Monotonic Allocation Schemes," European Journal of Operational Research, 154, 84{97. Shapley, L. (1971): \Cores of Convex Games," International Journal of Game Theory, 1, 11{26.
URI:	http://wrap.warwick.ac.uk/id/eprint/1328

Request changes to a record

Actions (login required)

View Item