הצגת המקור של הדף "משפט יאנג"

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

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

== העקרונות של יאנג ==
=== עקרון היעילות ===
על פי עיקרון זה, הזכייה הכוללת מחולקת כולה בין השחקנים, ללא בזבוז.
 
'''הגדרה פורמלית''': פתרון
<math>\varphi</math> מקיים את עקרון היעילות אם לכל משחק <math>\left( N;v \right)</math> מתקיים:

:<math>\sum_{i \in N} \varphi_i(N;v)=v(N)</math>

כלומר, סכום הרווחים של כל השחקנים שווה לשווי של ה[[קואליציה (תורת המשחקים)|קואליציה]]. 

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

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

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

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

אם <math>\forall S \subseteq N \setminus \left\{ i \right\} </math> ,
:<math>v( S \cup \left\{ i \right\} )-v(S)=w( S \cup \left\{i \right\} )-w(S)</math>

אז <math>\varphi_i\left( N;v \right)=\varphi_i\left( N;w \right)</math> .


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

== הוכחה ==
תחילה נראה כי [[פתרון (תורת המשחקים)|פתרון]]  המקיים את עקרונות '''היעילות, הסימטריה והשוליות''' מקיים גם את עקרון [[שחקן אפס|שחקן האפס]]. 

אכן, יהי <math>\varphi</math> מושג פתרון המקיים יעילות, סימטריה ושוליות.
יהי <math>\left( N;v \right)</math> משחק ויהי i שחקן אפס במשחק זה.
 
יהי <math>\left( N;z \right)</math> משחק האפס: z(S)= 0 לכל [[קואליציה]] S. 
במשחק <math>\left( N;z \right)</math> כל השחקנים סימטריים
ולכן מיעילות וסימטריה נובע כי: 

<math>\varphi_j\left( N;z \right)= 0 </math>   <math>\forall{j}\in{N},  </math> .

מכאן התרומה השולית של i לכל קואליציה הן ב v והן ב z היא 0, ולכן מעיקרון השוליות  <math>\varphi_i\left( N;v \right)= \varphi_i\left( N;z \right)= 0 </math>. 


כעת, נראה כי כל פתרון '''<math>\varphi</math>''' המקיים את עקרונות '''היעילות, הסימטריה והשוליות''' הוא [[ערך שפלי]], כלומר שמתקיים <math> \varphi = Sh</math> .

לכל משחק <math>\left( N;v \right)</math>  נסמן     
<math>I \left( N;v \right)= \left\{S\subseteq N: \ \exists T\subseteq S, v\left(T \right)\ \neq 0 \right\}</math>.

לכל קואליציה S נגדיר משחק  <math>\left( N;\ v^s \right)</math> באופן הבא:
<math>\ v^s\left( T\right)    = v \left( S\cap T \right),    \forall{T}\subseteq{N} </math>
. 

ניתן לראות כי כל השחקנים שאינם ב S הם שחקני אפס ב <math>\left( N;\ v^s \right)</math>, לכן עבור i שאינו ב S מתקיים <math>\ Sh_i \left( N;\ v^s \right) = 0 = \varphi_i\left( N;v^s \right)</math>.   


נשים לב כי <math>I \left( N;v-v^s \right)\subset I\left( N;v \right) </math> לכל קואליציה <math>S\in I\left( N;v \right) </math>. 

אכן, <math>I \left( N;v-v^s \right)\subseteq I\left( N;v \right) </math> :
תהי <math>T\in I\left( N;v-v^s \right) </math>, אז יש <math>R \subseteq T </math> תת-קואליציה שמקיימת <math>\left(v-v^s\right)\left(R\right) \neq 0 </math>. 

לכן בהכרח  <math>v \left(R\right)\neq 0</math> או <math>v^s \left(R\right)= v \left(R\cap S\right)\neq 0</math>. אך מכאן שיש ל <big>T</big> תת-קואליציה שערכה אינו 0 ונקבל ש <math>T\in I\left( N;v \right)</math>, כנדרש.

כמו כן <math>S \not\in I\left( N;v-v^s \right) </math>: לכל תת-קואליציה <math>T \subseteq S</math>,   <math>\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   </math> 

ולכן <math>S \not\in I\left( N;v-v^s \right)</math>. 


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


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


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


תהי <math>S\in I\left( N;v \right)</math> ויהי <math>i\not\in S</math>, נראה כי <math>\varphi_i\left( N;v \right)= Sh_i\left( N;v \right)</math>: 

ראינו ש  <math>\left| I \left( N;v-v^s \right)\right| < \left|I\left( N;v \right)\right|= k </math> ולכן מהנחת האינדוקציה<math>\varphi_i\left( N;v-v^s \right)= Sh_i\left( N;v-v^s \right)    ,\forall{i}\in{N}  </math>.

לכל קואליציה  { <big>i</big> }<big>\</big><math>T \subseteq N \ </math>:

<math>\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)</math>

לכן התרומה השולית של i במשחק<big> <math>v - v^s</math></big> היא:

<math>
\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)  </math>

כלומר התרומה השולית של שחקן i ב <big> <math>v - v^s</math></big> שווה לתרומה השולית שלו ב <big><math>v</math></big>.

נתון ש <math>\varphi</math> מקיים את עקרון השוליות. בנוסף ידוע כי גם [[ערך שפלי]] מקיים עיקרון זה, לכן -

<math>\varphi_i\left( N;v \right) = \varphi_i\left( N;v-v^s \right)</math>
ו- <math>Sh_i\left( N;v \right) = Sh_i\left( N;v-v^s \right)</math>    לכל שחקן <math>i\not\in S </math>.

ונקבל (מהנחת האינדוקציה) כי <math>\varphi_i\left( N;v \right) = Sh_i\left( N;v \right) </math> לכל שחקן  <math>i\not\in S </math>. 


יהי i שחקן שנמצא בכל הקואליציות ב <math>I\left( N;v \right)</math>, נראה כי <math>\varphi_i\left( N;v \right)= Sh_i\left( N;v \right)</math>:

נסמן ב *S את חיתוך כל הקואליציות ב <math>I\left( N;v \right)</math> ונניח כי *S אינה ריקה (אחרת המסקנה מתקיימת [[באופן ריק]]). 

נבחין כי לכל קואליציה T שאינה מכילה את *S מתקיים  <math>v\left(T\right) = 0 </math> (כי
אם  <math>v\left(T\right) \neq 0</math>, אז <math>T\in I\left( N;v \right)</math>  
ובפרט מכילה את *S).

כמו כן כל שני שחקנים i, j ב *S הם סימטריים כי לכל קואליציה R שאינה מכילה את i ו- j הקואליציות <math>R \cup j </math> ו- <math>R \cup i </math> אינן מכילות את *S ולכן <big>v</big> שלהן הוא 0.

מכיוון ש<math>\varphi</math> ו- <big>Sh</big> מקיימים את עקרון הסימטריה: 

<math>\varphi_i\left( N;v \right)= \varphi_j\left( N;v \right)</math>,   <math>Sh_i\left( N;v \right)= Sh_j\left( N;v \right)    </math>             לכל i,j שאינם ב *S.

מכיוון ש<math>\varphi</math> ו- <big>Sh</big> מקיימים את עקרון היעילות וראינו ש 
<math>\varphi_i\left( N;v \right)= Sh_i\left( N;v \right)</math> לכל שחקן i שאינו ב *S,

<math>\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)
</math>  

מכאן, שלכל שחקן j ב *S:

<math> \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)
</math>


וסה"כ  <math> \varphi = Sh  </math>  כנדרש.   <math>  \blacksquare   </math>

==ראו גם==
* [[ערך שפלי]]
* [[פתרון (תורת המשחקים)]]
* [[מונחים בתורת המשחקים]]

==לקריאה נוספת==
*{{צ-ספר|מחבר=שמואל זמיר, [[מיכאל משלר]], [[אילון סולן]]|שם=תורת המשחקים|מו"ל=[[הוצאת מאגנס|מאגנס]]|שנת הוצאה=2008|מקום הוצאה=ירושלים|ISBN=9654932946}}
[[קטגוריה:משפטים בתורת המשחקים|יאנג]]