Partition Games and the Core of Hierarchically Convex Cost Games

摘要

Partition games are introduced as a general framework for the study ofcooperative N-person cost games. The cost of each coalition in a partition game is determined by the cost of a minimal partition into 'essential' subcoalitions. A partition game has a non-empty core if and only if the LP-relaxation of the induced cost problem for the grand coalition has an integral optimal solution. Extending the model of Shapley's convex games, a special class of partitions games is studied that arises in the following way. A partial order structure is imposed on the grand coalition so that each player has at most one upper neighbor. Each antichain A in this order has a cost c(A) and it is assumed that c is submodular on the lattice of antichains. c naturally implies a cost C(S) for every coalition S. It is shown that core(c) is non-empty. Moreover, from a primal-dual setting within the framework of linear programming a greedy algorithm is derived that optimizes arbitrary linear objective functions over core(c). Finally, an appropriate notion of a Shapley value for this class of hierarchically convex cost games is discussed.