Premium
A network flow approach to cost allocation for rooted trees
Author(s) -
Iwata Satoru,
Zuiki Nozomu
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20040
Subject(s) - shapley value , cost allocation , cooperative game theory , computer science , core (optical fiber) , mathematical optimization , game theory , tree (set theory) , mathematical economics , root (linguistics) , operations research , theoretical computer science , mathematics , combinatorics , economics , telecommunications , linguistics , philosophy , accounting
In the game theory approach to cost allocation, the main computational issue is an algorithm for finding solutions such as the Shapley value and the nucleolus. In this article, we consider the problem of allocating the maintenance cost of a tree network that connects the supply source at the root to the users at the leaves. We show that the core of the game can be expressed in terms of network flows. Based on this observation, we present O ( n log n ) algorithms for computing the nucleolus and the egalitarian allocation. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 297–301 2004