Bondareva-Shapley-Theorem - Bondareva–Shapley theorem

Das Bondareva-Shapley-Theorem beschreibt in der Spieltheorie eine notwendige und ausreichende Bedingung für die Nichtleere des Kerns eines kooperativen Spiels in charakteristischer Funktionsform. Insbesondere ist der Kern des Spiels genau dann nicht leer, wenn das Spiel ausgeglichen ist . Das Bondareva-Shapley-Theorem impliziert, dass Marktspiele und konvexe Spiele nicht leere Kerne haben. Der Satz wurde in den 1960er Jahren von Olga Bondareva und Lloyd Shapley unabhängig formuliert .

Satz

Lassen Sie das Paar sein , kooperatives Spiel in charakteristischer Funktion Form, wobei die Menge des Spielers ist und wo der Wert Funktion auf definiert ist ‚s Potenzmenge (die Menge aller Teilmengen von ). ${\ displaystyle \ langle N, v \ rangle}$${\ displaystyle N}$ ${\ displaystyle v: 2 ^ {N} \ to \ mathbb {R}}$${\ displaystyle N}$${\ displaystyle N}$

Der Kern ist nicht leer , wenn und nur wenn für jede Funktion , wenn die folgende Bedingung erfüllt ist : ${\ displaystyle \ langle N, v \ rangle}$${\ displaystyle \ alpha: 2 ^ {N} \ setminus \ {\ Emptyset \} \ bis [0,1]}$

${\ displaystyle \ forall i \ in N: \ sum _ {S \ in 2 ^ {N}: \; i \ in S} \ alpha (S) = 1}$

${\ displaystyle \ sum _ {S \ in 2 ^ {N} \ setminus \ {\ emptyyset \}} \ alpha (S) v (S) \ leq v (N).}$

Verweise

• Bondareva, Olga N. (1963). "Einige Anwendungen linearer Programmiermethoden auf die Theorie kooperativer Spiele (auf Russisch)" (PDF) . Problemy Kybernetiki . 10 : 119–139.
• Kannai, Y (1992), "Der Kern und die Ausgewogenheit", in Aumann, Robert J . ; Hart, Sergiu (Hrsg.), Handbuch der Spieltheorie mit wirtschaftlichen Anwendungen, Band I. , Amsterdam: Elsevier, S. 355–395, ISBN   978-0-444-88098-7
• Shapley, Lloyd S. (1967). "Auf ausgeglichenen Sets und Kernen". Naval Research Logistics Quarterly . 14 (4): 453–460. doi : 10.1002 / nav.3800140404 . hdl : 10338.dmlcz / 135729 .