Research Article
Minimum cut tree games
@INPROCEEDINGS{10.1109/GAMENETS.2009.5137378, author={Anne M. Schwahn}, title={Minimum cut tree games}, proceedings={1st International Conference on Game Theory for Networks}, publisher={IEEE}, proceedings_a={GAMENETS}, year={2009}, month={6}, keywords={Cooperative game minimum cut tree core Shapley value cactus graph}, doi={10.1109/GAMENETS.2009.5137378} }- Anne M. Schwahn
Year: 2009
Minimum cut tree games
GAMENETS
IEEE
DOI: 10.1109/GAMENETS.2009.5137378
Abstract
In this paper we introduce a cooperative game based on the minimum cut tree problem which is also known as multi-terminal maximum flow problem. In a routing situation a network with capacities induced by vertices of a coalition has to be substituted by a network providing the same capacity for non-simultaneous flows but having a minimum number of edges and minimum total capacity. The solutions to this requirement are exactly the minimum cut trees. Minimum cut tree games are shown to be totally balanced and a solution in their core can be obtained in polynomial time. This special core allocation is closely related to the solution of the original graph theoretical problem. We give an example showing that the game is not supermodular in general, however, it is for special cases and for some of those we give an explicit formula for the calculation of the Shapley value.
