On some network flow games

The authors 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. The authors 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. They further give a linear characterization of the core of this sublcass 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. The authors 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, they 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. The authors 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 they study is the assignment game, introduced by Shapley and Shubik. This game is induced by the assignment problem which can be cast as a network optimization problem. The authors 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. They further show that, in general, the intersection of the kernel and the core is not a convex set. The authors also exhibit that under certain conditions the nucleolus has a simple characterization as the unqiue vector in the core in which the smallest revenue allocations are maximized in a lexicographical sense. Finally, they consider the horse market example of Bohm-Bawerk, for which it is shown that the core is contained in the kernel and that the nucleolus is midpoint of the core.