משפט יאנג

משפט יאנג הוא משפט בתורת המשחקים, הנותן אפיון נוסף לערך שפלי. המשפט נקרא על שמו של המתמטיקאי האמריקאי הוברט פייטון יאנג (Hobart Peyton Young), שהוכיח אותו בשנת 1985. המשפט מחליף את עקרונות החיבוריות (אדיטיביות) ושחקן האפס (אדישות) בערך שפלי, בעקרון השוליות.
המשפט קובע כי ערך שפלי הוא מושג הפתרון הנקודתי היחיד המקיים את עקרונות היעילות, הסימטריה והשוליות.

הוכחה

תחילה נראה כי פתרון המקיים את עקרונות היעילות, הסימטריה והשוליות מקיים גם את עקרון שחקן האפס.
אכן, יהי \varphi מושג פתרון המקיים יעילות, סימטריה ושוליות. יהי \left( N;v \right) משחק ויהי i שחקן אפס במשחק זה.
יהי \left( N;z \right) משחק האפס: z(S)= 0 לכל קואליציה S. במשחק \left( N;z \right) כל השחקנים סימטריים ולכן מיעילות וסימטריה נובע כי:
\varphi_j\left( N;z \right)= 0  \forall{j}\in{N},   .
מכאן התרומה השולית של i לכל קואליציה הן ב v והן ב z היא 0, ולכן מעיקרון השוליות \varphi_i\left( N;v \right)= \varphi_i\left( N;z \right)= 0 .

כעת, נראה כי כל פתרון \varphi המקיים את עקרונות היעילות, הסימטריה והשוליות הוא ערך שפלי, כלומר שמתקיים  \varphi = Sh .
לכל משחק \left( N;v \right) נסמן I \left( N;v \right)= \left\{S\subseteq N: \ \exists T\subseteq S, v\left(T \right)\ \neq 0 \right\}.
לכל קואליציה S נגדיר משחק \left( N;\ v^s \right) באופן הבא: \ v^s\left( T\right)    = v \left( S\cap T \right),    \forall{T}\subseteq{N}  .
ניתן לראות כי כל השחקנים שאינם ב S הם שחקני אפס ב \left( N;\ v^s \right), לכן עבור i שאינו ב S מתקיים \ Sh_i \left( N;\ v^s \right) = 0 = \varphi_i\left( N;v^s \right).

נשים לב כי I \left( N;v-v^s \right)\subset I\left( N;v \right)  לכל קואליציה S\in I\left( N;v \right) .
אכן, I \left( N;v-v^s \right)\subseteq I\left( N;v \right)  : תהי T\in I\left( N;v-v^s \right) , אז יש R \subseteq T  תת-קואליציה שמקיימת \left(v-v^s\right)\left(R\right) \neq 0 .
לכן בהכרח v \left(R\right)\neq 0 או v^s \left(R\right)= v \left(R\cap S\right)\neq 0. אך מכאן שיש ל T תת-קואליציה שערכה אינו 0 ונקבל ש T\in I\left( N;v \right), כנדרש.
כמו כן S \not\in I\left( N;v-v^s \right) : לכל תת-קואליציה T \subseteq S, \left(v-v^s\right)\left(T\right)= v \left(T\right)- v^s \left(T\right) = v \left(T\right)- v \left(T\right) = 0   
ולכן S \not\in I\left( N;v-v^s \right).

הוכחת המשפט תעשה באינדוקציה על מספר האיברים ב I\left( N;v \right).

אם \left| I\left( N;v \right) \right| = 0 , אז  v \left(S\right)= 0     \  לכל S. מכיוון שגם \varphi וגם Sh מקיימים את עקרון שחקן האפס, \varphi_i\left( N;v \right)= Sh_i\left( N;v \right)= 0  לכל i.

נניח באינדוקציה ש \varphi\left( N;v \right)= Sh\left( N;v \right) לכל משחק \left( N;v \right) שעבורו \left| I\left( N;v \right) \right| < k  ויהי \left( N;v \right) משחק שבו \left| I\left( N;v \right) \right| = k .

תהי S\in I\left( N;v \right) ויהי i\not\in S, נראה כי \varphi_i\left( N;v \right)= Sh_i\left( N;v \right):
ראינו ש \left| I \left( N;v-v^s \right)\right| < \left|I\left( N;v \right)\right|= k  ולכן מהנחת האינדוקציה\varphi_i\left( N;v-v^s \right)= Sh_i\left( N;v-v^s \right)    ,\forall{i}\in{N}  .
לכל קואליציה { i }\T \subseteq N \ :
\left(v-v^s \right) \left(T \cup \ i \right)= v\left(T \cup \ i \right) - v\left(S \cap \left(T \cup \ i \right)\right )= v\left(T \cup \ i \right) - v^s\left(T\right)
לכן התרומה השולית של i במשחק v - v^s היא:

\left(v-v^s \right) \left(T \cup \ i \right) - \left(v-v^s \right) \left(T  \right)=v\left(T \cup \ i \right) - v^s\left(T  \right) - v\left(T \right) + v^s\left(T  \right)= v\left(T \cup \ i \right) - v\left(T \right)  
כלומר התרומה השולית של שחקן i ב v - v^s שווה לתרומה השולית שלו ב v.
נתון ש \varphi מקיים את עקרון השוליות. בנוסף ידוע כי גם ערך שפלי מקיים עקרון זה, לכן -
\varphi_i\left( N;v \right) = \varphi_i\left( N;v-v^s \right) ו- Sh_i\left( N;v \right) = Sh_i\left( N;v-v^s \right) לכל שחקן i\not\in S .
ונקבל (מהנחת האינדוקציה) כי \varphi_i\left( N;v \right) = Sh_i\left( N;v \right)  לכל שחקן i\not\in S .

יהי i שחקן שנמצא בכל הקואליציות ב I\left( N;v \right), נראה כי \varphi_i\left( N;v \right)= Sh_i\left( N;v \right):
נסמן ב *S את חיתוך כל הקואליציות ב I\left( N;v \right) ונניח כי *S אינה ריקה (אחרת המסקנה מתקיימת באופן ריק).
נבחין כי לכל קואליציה T שאינה מכילה את *S מתקיים v\left(T\right) = 0  (כי אם v\left(T\right) \neq 0, אז T\in I\left( N;v \right) ובפרט מכילה את *S).
כמו כן כל שני שחקנים i,j ב *S הם סימטריים כי לכל קואליציה R שאינה מכילה את i ו- j הקואליציות R \cup j  ו- R \cup i  אינן מכילות את *S ולכן v שלהן הוא 0.
מכיוון ש\varphi ו- Sh מקיימים את עקרון הסימטריה:
\varphi_i\left( N;v \right)= \varphi_j\left( N;v \right), Sh_i\left( N;v \right)= Sh_j\left( N;v \right)     לכל i,j שאינם ב *S.
מכיוון ש\varphi ו- Sh מקיימים את עקרון היעילות וראינו ש \varphi_i\left( N;v \right)= Sh_i\left( N;v \right) לכל שחקן i שאינו ב *S,
\sum_{i\in{S^*} }\varphi_i\left( N;v \right)= v\left(N\right) - \sum_{i\not\in{S^*} }\varphi_i\left( N;v \right)=
v\left(N\right) - \sum_{i\not\in{S^*}}Sh_{i} (N;v) =
\sum_{i\in{S^*}}Sh_{i} (N;v)
מכאן, שלכל שחקן j ב *S:
 \varphi_j\left( N;v \right)= \frac{1}{|S^*|}\sum_{i\in{S^*} }\varphi_i\left( N;v \right)
 =\frac{1}{|S^*|}\sum_{i\in{S^*} }Sh_i( N;v ) = 
Sh_j\left( N;v \right)

וסה"כ  \varphi = Sh   כנדרש.   \blacksquare