Lower and upper bounds for linear production

Abstract

We study a model of a production economy in which every set of agents owns a set of resources, and where they all have access to the same technology. The agents can cooperate by pooling their resources, and the total profit from the joint venture is given by the optimal value to a linear program. The problem of allocating the total profit among the participants of such a joint venture can be formulated as a cooperative game, as in Owen (1975), and it is well-known that some core points can be obtained from optimal solutions to the dual of the LP-problem corresponding to the grand coalition. We provide lower (upper) bounds on the values of the game by aggregating over columns (rows) of the LP-problem. By choosing aggregation weights corresponding to optimal solutions of the primal (dual) LP-problem, we can create new games whose core form a superset (subset) of the original core. An estimate of the resulting error, in terms of an ε-core, is obtained by solving a mixed-integer programming problem, and we also suggest an iterative procedure for improving the bounds. Using a set of numerical examples, we investigate how the performance of the aggregation approach depends on the structure of the problem data.