Линейная производственная игра - Linear production game

Линейная производственная игра (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 s.t.\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