Kooperativní hra: Porovnání verzí

Definice jádra hry připouští situaci, kdy je jádro prázdné (a tedy skupinově stabilní rozdělení zisku velké koalice neexistuje). Pro <math>n>2</math> hráče tato situace může nastat i u monotónní hry, tzn. u takové, kdy větší koalice přináší vždy větší hodonotu než koalice menší.

[[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>

[[Olga N. Bondareva|Bondareva]] formulovala výsledek čtyři roky před [[Lloyd Shapley|Shapleyem]], ovšem [[Ruština|rusky]] a navíc v periodiku ''Проблемы кибернетики'' málo známém vědcům mimo [[Sovětský svaz]], takže dlouho byl za objevitele považován [[Lloyd Shapley]]. [[Lloyd Shapley]] se později zasazoval za používání názvu Bondareva theorem. Dnešní podoba názvu Bondareva-Shapley theorem je kompromisní, lze se rovněž setkat s podobou Shapley-Bondareva theorem<ref>Lehrer, Ehud. "Allocation processes in cooperative games." ''International Journal of Game Theory'' 31.3 (2003): 341-351.</ref>, ve starší literatuře také Shapley theorem<ref>Schmeidler, David. ''On balanced games with infinitely many players''. No. RM-28. HEBREW UNIV JERUSALEM (ISRAEL) DEPT OF MATHEMATICS, 1967.<br /></ref>

* {{citace monografie | jméno = Martin| příjmení = Dlouhý| jméno2 = Petr| příjmení2 = Fiala | titul = Úvod do teorie her| vydavatel = Nakladatelství Oeconomica | místo = Praha | rok = 2007| počet stran = 114| isbn = 978-80-245-1273-0|}}