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

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

$v(S)=\max _{x\geq 0}(c_{1}x_{1}+...+c_{n}x_{n})$ $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 имеет непустое ядро . Одно вменение можно вычислить, решив двойственную задачу $P(N)$. Позволять $\alpha$ будет оптимальным двойным решением $P(N)$. Выигрыш игроку i равен $x^{i}=\sum _{k=1}^{m}\alpha _{k}b_{k}^{i}$. можно доказать, С помощью теорем двойственности что ${\vec {x}}$ находится в ядре v .

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

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

Ссылки

• ОУЭН, Гильермо (1975), « О основе игр линейного производства », Математическое программирование , 9 , Математическое программирование : 358–370, doi : 10.1007/BF01681356