Cooperative games arising from network flow problems

The paper gives a new class of mathematical programming games without side payments that have nonempty cores. In these games, players control nodes or arcs in a network and participate in optimizing an objective function while attempting to share the costs or returns. Disjoint paths in the network correspond to alternative production routes or streams of jobs that are concurrently processed and yield costs or returns along the way; the problem of fair cost allocation or profit sharing motivates the formulation of a cooperative game. The present results extend work on games with side payments, and are relevant for situations in which the various players involved have dissimilar and nonlinear utilities for the generated returns. For some games of this type efficient algorithms exist to allocate costs or revenues among the players.