Linear production game explained

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

	j
a
	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

	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.

v(S)=max_x\geq(c_1x_1+...+c_nx_n)

s.t.

	1
a
	jx

	2

	jx

	n

	jx

_n\leq\sum_i\in

	i
b
	j

\forallj=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)

. Let

\alpha

be the optimal dual solution of

P(N)

. The payoff to player i is

	m\alpha
x
	k

	i
b
	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.