Linear production game

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 amount of the kth resource. The products can be sold at a given market price while the resources themselves can not. Each of the N players is given a vector 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 as follows.


The core of the LP game[edit]

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 . Let be the optimal dual solution of . The payoff to player i is . It can be proved by the duality theorems that is in the core of v.


An important interpretation of the imputation is that under the current market, the value of each resource j is exactly , 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[edit]