Liniowa gra produkcyjna

Liniowa gra produkcyjna ( LP Game ) to N-osobowa gra, w której wartość koalicji można uzyskać rozwiązując problem programowania liniowego . Jest szeroko stosowany w kontekście alokacji zasobów i dystrybucji wypłat. Z matematycznego punktu widzenia istnieje m rodzajów surowców i można z nich wytworzyć n produktów. Produkt j wymaga $_$ tego zasobu . Produkty można sprzedać po określonej cenie rynkowej ${\ displaystyle {\ vec {c}}},$ podczas gdy same zasoby nie mogą. Każdy z N graczy ${\ vec {b ^ {i}}} = (b_ {1} ^ {i} ,...,b_{m}^{i})}$ wektor zasobów. Wartość koalicji S to maksymalny zysk, jaki może ona osiągnąć przy wszystkich zasobach posiadanych przez jej członków. Można to uzyskać, rozwiązując odpowiednie zadanie programowania liniowego ${\ Displaystyle P (S)}$ w następujący sposób.

${\ Displaystyle v (S) = \ max _ {x \ geq 0} (c_ {1} x_ {1}$ ${\ displaystyle st \ quad a_ {j} ^ {1} x_ {1} + a_ {j} ^ {2} x_ {2} + ... + a_ {j} ^ {n} x_ {n} \ równoważnik \sum _{i\in S}b_{j}^{i}\quad \forall j=1,2,...,m}$

Rdzeń

Każda gra LP v jest grą całkowicie zbalansowaną. Tak więc każda podgra v ma niepusty rdzeń . Jedno imputację można obliczyć ${\ Displaystyle P (N)}$ rozwiązując podwójny problem P. . Niech $P.$ podwójnym rozwiązaniem ${\ displaystyle P (N)$ . Wypłata dla gracza i wynosi ${\ Displaystyle x ^ {i} = \ suma _ {k = 1} ^ {m} \ alfa _ {k} b_ {k} ^ {i}}$ . Twierdzeniami o dualności można udowodnić , że rdzeń v . $\ displaystyle {\ vec {x}}}$ {

Ważną interpretacją imputacji $wynosi$ to, że na obecnym rynku wartość każdego zasobu j dokładnie $}}$ displaystyle \ alpha _ { nie cenione same w sobie. Tak więc wypłata, którą powinien otrzymać jeden gracz, to całkowita wartość posiadanych przez niego zasobów.

Jednak nie wszystkie imputacje w rdzeniu można uzyskać z optymalnych rozwiązań dualnych. Jest wiele dyskusji na temat tego problemu. Jedną z najczęściej stosowanych metod jest rozważenie r-krotnej replikacji pierwotnego problemu. Można pokazać, że jeśli imputacja u jest w rdzeniu r-krotnie replikowanej gry dla wszystkich r, to u można otrzymać z optymalnego rozwiązania dualnego.

• OWEN, Guillermo (1975), „On the Core of Linear Production Games”, Programowanie matematyczne , Programowanie matematyczne , 9 : 358–370, doi : 10.1007 / BF01681356