משפט יאנג

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

המשפט קובע כי ערך שפלי הוא מושג הפתרון הנקודתי היחיד המקיים את עקרונות היעילות, הסימטריה והשוליות.

העקרונות של יאנג

עקרון היעילות

על פי עיקרון זה, הזכייה הכוללת מחולקת כולה בין השחקנים, ללא בזבוז.

הגדרה פורמלית: פתרון $\varphi$ מקיים את עקרון היעילות אם לכל משחק $\left(N;v\right)$ מתקיים:

$\sum _{i\in N}\varphi _{i}(N;v)=v(N)$

כלומר, סכום הרווחים של כל השחקנים שווה לשווי של הקואליציה.

עקרון הסימטריה

על פי עיקרון זה, שני שחקנים שתרומתם שווה לכל קואליציה, יזכו באותה תמורה.

הגדרה פורמלית: פתרון $\varphi$ מקיים את עקרון הסימטריה אם לכל משחק $\left(N;v\right)$ ולכל זוג שחקנים סימטריים i ו-j במשחק מתקיים:

$\varphi _{i}\left(N;v\right)=\varphi _{j}\left(N;v\right)$

עקרון השוליות

על פי עיקרון זה, אם התרומה השולית של שחקן מסוים לכל קואליציה במשחק אחד זהה לתרומתו השולית לכל קואליציה במשחק אחר, אזי הוא יקבל את אותו הסכום בשני המשחקים.

הגדרה פורמלית: פתרון $\varphi$ מקיים את עקרון השוליות אם לכל שני משחקים $\left(N;v\right)$ ו-$\left(N;w\right)$ עם אותה קבוצת שחקנים, ולכל שחקן i מתקיים התנאי הבא:

אם $\forall S\subseteq N\setminus \left\{i\right\}$ ,

$v(S\cup \left\{i\right\})-v(S)=w(S\cup \left\{i\right\})-w(S)$

אז $\varphi _{i}\left(N;v\right)=\varphi _{i}\left(N;w\right)$ .

נשים לב שערך שפלי מקיים את שלושת העקרונות המצוינים במשפט.

הוכחה

תחילה נראה כי פתרון המקיים את עקרונות היעילות, הסימטריה והשוליות מקיים גם את עקרון שחקן האפס.

אכן, יהי $\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$

ראו גם

• ערך שפלי
• פתרון (תורת המשחקים)
• מונחים בתורת המשחקים

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946