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 a k j {\displaystyle a_{k}^{j}} amount of the kth resource. The products can be sold at a given market price c → {\displaystyle {\vec {c}}} while the resources themselves can not. Each of the N players is given a vector b i → = ( b 1 i , . . . , b m i ) {\displaystyle {\vec {b^{i}}}=(b_{1}^{i},...,b_{m}^{i})} 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 P ( S ) {\displaystyle P(S)} as follows.

v ( S ) = max x ≥ 0 ( c 1 x 1 + . . . + c n x n ) {\displaystyle v(S)=\max _{x\geq 0}(c_{1}x_{1}+...+c_{n}x_{n})}

s . t . a j 1 x 1 + a j 2 x 2 + . . . + a j n x n ≤ ∑ i ∈ S b j i ∀ j = 1 , 2 , . . . , m {\displaystyle s.t.\quad a_{j}^{1}x_{1}+a_{j}^{2}x_{2}+...+a_{j}^{n}x_{n}\leq \sum _{i\in S}b_{j}^{i}\quad \forall j=1,2,...,m}

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 P ( N ) {\displaystyle P(N)} . Let α {\displaystyle \alpha } be the optimal dual solution of P ( N ) {\displaystyle P(N)} . The payoff to player i is x i = ∑ k = 1 m α k b k i {\displaystyle x^{i}=\sum _{k=1}^{m}\alpha _{k}b_{k}^{i}} . It can be proved by the duality theorems that x → {\displaystyle {\vec {x}}} is in the core of v.

An important interpretation of the imputation x → {\displaystyle {\vec {x}}} is that under the current market, the value of each resource j is exactly α j {\displaystyle \alpha _{j}} , 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, 9, Mathematical Programming : 358–370, doi:10.1007/BF01681356