Logo Logo

Cost Allocation for a Tree Network with Heterogeneous Customers, Mathematics of Operations Research


We analyze a cost allocation problem which could naturally arise from a situation wherein a tree network T = (NU{0}, E), serving heterogeneous customers, has to be constructed. The customers, located at N, require some service from a central supplier, located at vertex 0. The customers have heterogeneous preferences for the level or quality of service received from the central supplier. We formulate the above cost allocation problem as a cooperative game, referred to as an extended tree game. The extended tree game is a proper extension of Megiddo's (1978) tree game, wherein all the customers have identical preferences regarding the level of service received. We prove that an extended tree game is convex, and we show that its Shapley value can be computed in tex-math$\scr{O}(p|N|)$/tex-math time, where p is the number of distinct preference levels. We further provide a complete facial description of the core polytope of an extended tree game, and demonstrate that even when there are only two classes of customers, the number of nonredundant core constraints could be exponential in |N|. Nevertheless, we are able to construct an tex-math$\scr{O}(p|N|)$/tex-math algorithm to check the core membership of an arbitrary cost allocation, which can be used to construct an tex-math$\scr{O}(p|N|^{3})$/tex-math combinatorial algorithm to compute the nucleolus of an extended tree game. Finally, we show that the complements of the facet-defining coalitions for the core are all connected in an auxiliary tree graph with node set N.




Sunil Chopra, Daniel Granot, Jeroen Kuipers

Date Published



Chopra, Sunil, Daniel Granot, and Jeroen Kuipers. 2002. Cost Allocation for a Tree Network with Heterogeneous Customers. Mathematics of Operations Research. 27(4): 647-661.


Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more


Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.


Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more