Linear production game

Linear production game (LP Game) is a N-person game in which the value of a coalition can be obtained by solving a linear programming problem. It is widely used in the context of resource allocation and payoff distribution. Mathematically, there are m types of resources and n products can be produced out of them. Product j requires [math]\displaystyle{ a^j_k }[/math] amount of the kth resource. The products can be sold at a given market price [math]\displaystyle{ \vec{c} }[/math] while the resources themselves can not. Each of the N players is given a vector [math]\displaystyle{ \vec{b^i}=(b^i_1,...,b^i_m) }[/math] of resources. The value of a coalition S is the maximum profit it can achieve with all the resources possessed by its members. It can be obtained by solving a corresponding linear programming problem [math]\displaystyle{ P(S) }[/math] as follows.

[math]\displaystyle{ v(S)=\max_{x\geq 0} (c_1x_1+...+c_nx_n) }[/math] [math]\displaystyle{ s.t. \quad a^1_jx_1+a^2_jx_2+...+a^n_jx_n\leq \sum_{i\in S}b^i_j \quad \forall j=1,2,...,m }[/math]

Core

Every LP game v is a totally balanced game. So every subgame of v has a non-empty core. One imputation can be computed by solving the dual problem of [math]\displaystyle{ P(N) }[/math]. Let [math]\displaystyle{ \alpha }[/math] be the optimal dual solution of [math]\displaystyle{ P(N) }[/math]. The payoff to player i is [math]\displaystyle{ x^i=\sum_{k=1}^m\alpha_k b^i_k }[/math]. It can be proved by the duality theorems that [math]\displaystyle{ \vec{x} }[/math] is in the core of v.

An important interpretation of the imputation [math]\displaystyle{ \vec{x} }[/math] is that under the current market, the value of each resource j is exactly [math]\displaystyle{ \alpha_j }[/math], although it is not valued in themselves. So the payoff one player i should receive is the total value of the resources he possesses.

However, not all the imputations in the core can be obtained from the optimal dual solutions. There are a lot of discussions on this problem. One of the mostly widely used method is to consider the r-fold replication of the original problem. It can be shown that if an imputation u is in the core of the r-fold replicated game for all r, then u can be obtained from the optimal dual solution.

References

• OWEN, Guillermo (1975), "On the Core of Linear Production Games", Mathematical Programming (Mathematical Programming) 9: 358–370, doi:10.1007/BF01681356