On Some Network Flow Games

We analyze three subclasses of cooperative games arising from network optimization problems in which the resources, such as arcs or nodes in the network, are controlled by individuals who have conflicting objectives. The first subclass of cooperative games is induced by network optimization problems over directed augmented trees. We show that for this subclass of games the kernel coincides with the nucleolus, and that the nucleolus can be characterized as the unique revenue allocation vector in which every pair of arc owners who are adjacent in the tree are located symmetrically with respect to their bargaining range. We further give a linear characterization of the core of this subclass of games, which is then used to provide a more explicit representation of the nucleolus and to construct a strongly polynomial algorithm for generating it. The second subclass of cooperative games is induced by maximum flow problems in simple undirected networks. We provide a useful parametric representation of the core of this subclass of games, which is used to characterize the nucleolus and the intersection of the core and the kernel. Explicitly, we show that the intersection of the core and the kernel consists of all revenue allocations in the core which assign equal payoffs to any pair of unseparated arc owners. We further demonstrate that among the core vectors, the nucleolus is the unique revenue allocation vector in which the smallest allocations are maximized in a lexicographical sense. The third cooperative game that we study is the assignment game, introduced by Shapley and Shubik (1972). This game is induced by the assignment problem which can be cast as a network optimization problem. We investigate the relationship between the kernel and the core of the assignment game, and provide a necessary and sufficient condition for the core to be contained in the kernel. We further show that, in general, the intersection of the kernel and the core is not a convex set. We also exhibit that under certain conditions the nucleolus has a simple characterization as the unique vector in the core in which the smallest revenue allocations are maximized in a lexicographical sense. Finally, we consider the horse market example of Bohm-Bawerk (1923), for which it is shown that the core is contained in the kernel and that the nucleolus is the midpoint of the core.