Linear production game
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>a^j_k</math> amount of the *kth* resource. The products can be sold at a given market price <math>\vec{c}</math> while the resources themselves can not. Each of the *N* players is given a vector <math>\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>P(S)</math> as follows.
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>P(N)</math>. Let <math>\alpha</math> be the optimal dual solution of <math>P(N)</math>. The payoff to player i is <math>x^i=\sum_{k=1}^m\alpha_k b^i_k</math>. It can be proved by the duality theorems that <math>\vec{x}</math> is in the core of v.
An important interpretation of the imputation <math>\vec{x}</math> is that under the current market, the value of each resource j is exactly <math>\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.