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^j\_k$ amount of the "kth" resource. The products can be sold at a given market price $vec\{c\}$ while the resources themselves can not. Each of the "N" players is given a vector $vec\{b^i\}=(b^i\_1,...,b^i\_m)$ 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)$ as follows.

The core of the LP game

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

An important interpretation of the imputation $vec\{x\}$ is that under the current market, the value of each resource "j" is exactly $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

*