Kooperativní hra: Porovnání verzí

Přidáno 32 bajtů ,  před 2 lety
m
bez shrnutí editace
(Bondareva - Shapley theorem, balancované systémy. Nutná a postačující podmínka pro neprázdné jádro.)
m
 
====== Bondareva-Shapley theorem: Nutná a postačující podmínka neprázdného jádra hry ======
[[Olga N. Bondareva]]<ref>Bondareva, Olga N. "Some applications of linear programming methods to the theory of cooperative games." ''Problemy kibernetiki'' 10 (1963): 119-139</ref> v roce 1963 a nezávisle [[Lloyd Shapley|Lloyd S. Shapley]]<ref>Shapley, Lloyd S. "On balanced sets and cores." ''Naval research logistics quarterly'' 14.4 (1967): 453-460.</ref> v roce 1967 formulovali a dokázali nutnou a postačující podmínku pro hru koaliční hru <math>(v(S))_{S \subseteqq N}</math>k tomu, aby daná hra měla neprázdné jádro, tedy aby výšezmíněná soustava <math> \sum_{i \in L} a_i \geq v(L), L \subset N</math> , <math>\sum_{i \in N} a_i = v(N)</math>měla řešení. Především: soustava žádné řešení nemá, pokud váženým součtem několika nerovností soustavy jsme schopni dostat spor s koncovou rovností, tedy <math> \sum_{i \in N} a_i > v(N)</math>Například ve hře tří hráčů s charakteristickou funkcí <math> v({i})=0 </math> pro jednoprvkové koalice, <math> v({i,j})=1000 </math> pro kteroukoli koalici dvou hráčů a <math>v({1,2,3})=1200 </math>dosáváme pro jádro (mimo dalších) podmínky <math> \begin{array}{lcl} a_1+a_2 \geqq 1000 \\ a_1+a_3 \geqq 1000 \\ a_2+a_3 \geqq 1000 \end{array}
</math>, což v součtu dává <math> 2(a_1+a_2+a_3) \geqq 3000</math>- spor s <math> a_1+a_2+a_3 = 1200</math> Bondareva i Shapley dokázali, že platí rovněž opačné tvrzení: Z neexistence součtu některých z nerovností <math> \sum_{i \in L} a_i \geq v(L), L \subset N</math> , který by vedl ke sporu s rovností <math>\sum_{i \in N} a_i = v(N)</math>již plyne, že jádro hry je neprázdné.
'''Formálně:''' Systém podmnožin množiny <math> N</math> <math>(S)_{S \subset N} \subset 2^N</math> je '''[[Balancovaný systém|balancovaný]]''', pokud lze najít nezápornou váhu <math> \lambda_S</math> pro každou z množin systému tak, že každý prvek z <math> N</math> je ve váženém součtu obsažen v tomto systému s vahou právě <math> 1</math>. Podle Bondareva-Shapley teorému je jádro hry neprázdné právě když pro jakýkoli balancovaný systém <math>(S)_{S \subset N} \subset 2^N</math> a odpovídající váhy <math> \lambda_S</math> platí <math>\sum_{S } \lambda_Sv(S) \leqq v(N)</math>
 
== Shapleyova hodnota ==
'''Shapleyova hodnota''' říká, jak významnou pozici má hráč v kooperativní hře, protože vyjadřuje průměrný přínos hráče do všech koalic, jichž může být členem. Pracuje s rozdílem mezi výhrou koalice s hráčem a podkoalice bez hráče. Shapleyovy hodnoty vycházejí z metody odhadu síly hráče z hlediska jeho mezního přínosu ke všem koalicím, jichž může být členem, kterou navrhl v roce [[1953]] americký matematik a ekonom [[Lloyd Shapley|L. S. Shapley]].
Shapleyovy hodnoty tvoří Shapleyův vektor, který je pro kooperativní hru ''N'' hráčů definován jako
<center><math>h = (h_1, h_2, ..., h_N)</math></center>
160

editací