WikiDer > Линейная производственная игра

Линейная производственная игра (LP игра) - это игра с участием N человек, в которой значение коалиции можно получить, решив линейное программирование проблема. Он широко используется в контексте выделения ресурсов и распределения выплат. Математически есть м типы ресурсов и п из них можно производить продукцию. Товар j требует ${ displaystyle a_ {k} ^ {j}}$ количество kth ресурс. Продукция может продаваться по заданной рыночной цене. ${ displaystyle { vec {c}}}$ пока сами ресурсы не могут. Каждый из N игрокам дается вектор ${ displaystyle { vec {b ^ {i}}} = (b_ {1} ^ {i}, ..., b_ {m} ^ {i})}$ ресурсов. Ценность коалиция S это максимальная прибыль, которую он может получить со всеми ресурсами, которыми обладают его участники. Его можно получить, решив соответствующую задачу линейного программирования ${ Displaystyle P (S)}$ следующее.

${ displaystyle v (S) = max _ {x geq 0} (c_ {1} x_ {1} + ... + c_ {n} x_ {n})}$ ${ displaystyle st 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}$

Основной

Каждая игра LP v это полностью сбалансированная игра. Итак, в каждой подигре v имеет непустой основной. Один вменение можно вычислить, решив двойная проблема из ${ Displaystyle P (N)}$. Позволять ${ displaystyle alpha}$ быть оптимальным двойным решением ${ Displaystyle P (N)}$. Выплата игроку я является ${ displaystyle x ^ {i} = sum _ {k = 1} ^ {m} alpha _ {k} b_ {k} ^ {i}}$. Это может быть доказано двойственность теоремы, которые ${ displaystyle { vec {x}}}$ находится в основе v.

Важное толкование вменения ${ displaystyle { vec {x}}}$ заключается в том, что при текущем рынке стоимость каждого ресурса j точно ${ displaystyle alpha _ {j}}$, хотя и не ценится в себе. Итак, выигрыш, который должен получить один игрок, - это общая стоимость ресурсов, которыми он обладает.

Однако не все вменения в ядре могут быть получены из оптимальных двойственных решений. По этой проблеме ведется много дискуссий. Один из наиболее широко используемых методов - рассмотрение r-кратная репликация исходной проблемы. Можно показать, что если вменение ты лежит в основе r-кратной воспроизводимой игры для всех r, то ты можно получить из оптимального двойственного решения.

Рекомендации

• ОВЕН, Гильермо (1975) "В основе линейных производственных игр", Математическое программирование, Математическое программирование , 9: 358–370, Дои:10.1007 / BF01681356