הצגת המקור של הדף "ערך שפלי"

ב[[תורת המשחקים]], '''ערך שֵׁפְּלִי''' הוא אחד הפתרונות למשחקים בצורת פונקציה קואליציונית. 
[[פתרון (תורת המשחקים)|הפתרון]] פותח על ידי [[לויד שפלי|לוֹיְד שֵׁפְּלִי]] בשנת 1953 ונקרא על שמו.
 
קבוצת שחקנים ([[קואליציה (תורת המשחקים)|קואליציה]]), משתפת פעולה ומרויחה סכום מסוים מעצם שיתוף הפעולה. מאחר שחלק מהשחקנים תרמו יותר לקואליציה מאשר שחקנים אחרים או שהיה ברשותם יותר [[כוח מיקוח]] נרצה לדעת איזו חלוקה של הרווחים תהיה "הוגנת" במשחק. 

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

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

כמו בכל השאלות מסוג זה, התשובה תלויה בהגדרה ל'הגינות'. שפלי הציע ארבעה קריטריונים:

# '''יעילות''': התועלת היא המקסימלית אותה ניתן להשיג. בנוסף, התועלת מחולקת כולה בין השחקנים, ללא בזבוז.
# '''אקסיומת שחקן האפס''': שחקן שאינו יכול לשפר את רווחיותה של אף קבוצה, אינו ראוי לקבל כל תמורה.
# '''סימטריות''': שני שחקנים שתרומתם שווה לכל קואליציה, יזכו באותה תמורה. 
# '''[[עקרון החיבוריות|אדיטיביות]]''': כאשר מחברים שני מקורות הכנסה המבוססים על אותה קבוצת שחקנים, אפשר לחשב את חלוקת הרווחים לכל מקור הכנסה בנפרד.

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

== ניסוח פורמלי ==
משחק שיתופי מוגדר על ידי [[זוג סדור]] (N,v), כאשר N היא קבוצת השחקנים ו-<math>\ v</math> היא פונקציה קואליציונית - פונקציה חיובית <math>\ v : 2^N \rightarrow \mathbb{R}</math>, המתאימה לכל קואליציה את התועלת הקבוצתית, ועונה על שתי הדרישות הבאות:
# <math>\ v(\emptyset)=0</math> - הקואליציה הריקה אינה מרוויחה דבר.
# לכל שתי [[קבוצות זרות]] S ו- T, <math>\ v(S\cup T) \geq v(S) + v(T)</math>, כלומר, שיתוף פעולה בין קבוצות לעולם אינו מקטין את הרווח המשותף של שתי הקבוצות.

נסמן ב-<math>\ G^N</math> את קבוצת פונקציות התועלת על קבוצת השחקנים N.

שני שחקנים <math>i,j \in N</math> יקראו '''חילופיים ב-<math>\ v</math>''' אם לכל <math>S \subseteq N-\left\{ i,j \right\}</math> מתקיים  <math>\ v(S\cup \left\{i \right\}) = v(S\cup \left\{j\right\})</math>.

שחקן <math>i \in N</math> יקרא '''שחקן אפס ב-<math>\ v</math>''' אם לכל <math>S \subseteq N</math> מתקיים <math>\ v(S\cup \left\{i \right\}) = v(S)</math>.

פתרון הוא [[פונקציה]]  <math>\ \phi </math>  המתאימה לכל משחק בצורה קואליציונית  <math>\ (N,v)</math> וקטור ב-<math>\ \mathbb{R}^N</math> .  הגודל  <math>\ \phi_i(N,v) </math> נקרא הערך של שחקן <math>\ i</math> במשחק <math>\ (N;v)</math> לפי הפתרון <math>\ \phi </math>.
את שלוש הדרישות הראשונות להוגנות שהזכרנו בפתיח לערך אפשר לנסח באופן הבא: 
# יעילות: לכל פונקציית תועלת <math>\ v</math>  מתקיים <math>\sum_{i=1}^n\phi(v,i)=v(N)</math>. 
# אקסיומת שחקן האפס: לכל פונקציית תועלת <math>\ v</math>  ולכל שחקן אפס <math>i \in N</math> ב-<math>\ v</math> מתקיים ש- <math>\ \phi(v,i) = 0</math>.
# סימטריות: לכל פונקציית תועלת <math>\ v</math> ולכל שני שחקנים <math>i,j \in N</math> שחילופיים ב-<math>\ v</math> מתקיים <math>\ \phi(v,i) = \phi(v,j)</math>.

בנוסף לדרישות אלה, ההעתקה המתאימה לכל פונקציית תועלת <math>\ v</math> את פונקציית החלוקה <math>\ \phi(v)</math>, צריכה להיות [[עקרון החיבוריות|אדיטיבית]], כלומר: לכל שתי פונקציות רווח <math>\ v,v'</math> מתקיים <math>\!\, \phi(v+v')=\phi(v)+\phi(v')</math>. מדרישה זו נובע שההעתקה <math>\ \phi</math> היא [[העתקה ליניארית|ליניארית]] ממרחב פונקציות התועלת (שממדו <math>\ 2^n</math>) למרחב וקטורי התשלומים (שממדו n).

== הגדרת ערך שפלי ==
כאמור, משפט שפלי מוכיח כי תחת הקריטריונים של הוגנות שהוגדרו קיימת [[חלוקה הוגנת]] יחידה. אם נתון [[סדר מלא]] של השחקנים (ראשון, שני וכו'), ה'''תועלת''' שמביא השחקן ה-i היא ההפרש <math>\ \nu(\{1,2,\dots,i\}) - \nu(\{1,2,\dots,i-1\})</math>. '''ערך שפלי''', שהוא החלוקה ההוגנת היחידה, מקצה לשחקן i את התועלת הממוצעת שהוא מביא. כלומר, 
:<math>\psi(v,i)= \frac{1}{|N|!}\sum_R\left [\ v(P_i^R \cup \left \{ i \right \}) - \ v(P_i^R) \right ]\,\!</math>
כאשר R הוא תמורה של השחקנים, הסכום רץ על כל התמורות האפשריות (קיימות !n כאלה) ו-<math>P_i^R</math> היא קבוצת כל השחקנים שמקדימים את i ביחס הסדר R.

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

=== נוסחה שקולה ===
עבור כל [[סדר חלקי|יחס סדר]] כזה R, אנו למעשה מתייחסים רק לקואליציה <math>P_i^R</math>, ולא ליחס הסדר בין האיברים שבה. לכן, לכל קואליציה <math>S\subseteq N\setminus \{i\}</math>, ניתן לאגד את אוסף כל יחסי הסדר R עבורם <math>P_i^R = S</math> יחדיו. מספר יחסי הסדר עבורם <math>P_i^R = S</math> הוא <math>|S|!\cdot (|N|-|S|-1)!</math>, ולכן ערך שפלי מתקבל על ידי הנוסחה השקולה:
:<math>\psi(v,i)= \frac{1}{|N|!}\sum_{S\subseteq N\setminus \{i\}} |S|!\cdot \left (|N|-|S|-1\right )!\cdot \left (v\left (S\cup \{i\}\right )-v\left (S\right )\right ) </math>
במקרים רבים, נוסחה זו קלה יותר לחישוב מהנוסחה הראשונה.

== אפיון נוסף לערך שפלי: עקרון השוליות ==

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

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

אם <math>\ v(S\cup \{i\})-v(S)=u(S\cup \{i\})-u(S)</math>  לכל קואליציה  <math>\ S</math> של  <math>\ N</math>, אז הקואורדינטה ה-i של הפתרון עבור המשחק   <math>\ (N;v)</math> שווה לקואורדינטה ה-i של הפתרון עבור המשחק   <math>\ (N;u)</math>.

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

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

ראו גם [[עקרון ההערכה של דוביי]].

== עקביות הערך של שפלי ==
עבור ה[[ליבה של משחק שיתופי|ליבה]] הוגדר מושג [[תכונת המשחק המצומצם|המשחק המצומצם]] לפי דייוויס ומשלר, וידוע כי הליבה מקיימת את תכונת העקביות: אם <math>\ x</math>   היא נקודה בליבה של משחק <math>\ (N;v)</math> אז לכל משחק מצומצם   <math>(S;v_s)\,\!</math> הווקטור<math>(x_i)_i\in S</math>הוא נקודה בליבה של המשחק   <math>(S;v_s)\,\!</math>. תכונה דומה מתקיימת גם עבור הערך של שפלי, אלא שהגדרת המשחק המצומצם שונה, והיא ניתנה על ידי [[סרג'יו הרט]] ו[[אנדרו מס-כולל]]{{הערה|1= Hart and Mas-Colell  1989}} . יתר על כן, תכונת המשחק המצומצם יכולה לשמש לאפיון אקסיומטי לערך שפלי, בדיוק כשם שהיא משמשת לאפיון אקסיומטי של הגרעינון. לשני מושגי הפתרון הנקודתיים ישנה אותה מערכת [[אקסיומה|אקסיומות]] מאפיינת, ורק הגדרת המשחק המצומצם שונה. לכן, כשבאים לבחור באחד ממושגי הפתרון, כדאי לבדוק איזה משחק מצומצם מתאים יותר בסיטואציה הנידונה.

== דוגמאות==
=== משחק הכפפה ===
משחק הכפפה הוא משחק שיתופי שבו לשחקנים יש כפפה ימנית או שמאלית והמטרה של השחקנים היא לסדר זוג כפפות עם השחקנים האחרים. בדוגמה שלנו:
:<math>N = \{1, 2, 3\}\,\!</math> 
כאשר לשחקנים 1 ו-2 יש כפפה ימנית ולשחקן 3 יש כפפה שמאלית. [[פונקציית תועלת|פונקציית התועלת]] למשחק זה היא:
:<math>
V(S) = 
\begin{cases} 
  1  & \mbox{if }\ S \in \left\{ \{1,3\},\{2,3\},\{1,2,3\} \right\}\\
  0 & \mbox{else}\\
\end{cases}
</math>
נחשב את ערך שפלי לשחקן 1. נרשום בטבלה את ערך הביטוי <math>v(P_1^R \cup \left \{ 1 \right\})-v(P_1^R)</math> לכל יחס סדר R: 
{| border="1"
! <math>R\,\!</math> !! <math>v(P_1^R \cup \left \{ 1 \right\})-v(P_1^R)</math> 
|-
! <math>{1,2,3}\,\!</math>
|  <math>v(\{1\}) - v(\varnothing) = 0 - 0 = 0\,\!</math>
|-
! <math>{1,3,2}\,\!</math>
|  <math>v(\{1\}) - v(\varnothing) = 0 - 0 = 0\,\!</math>
|-
! <math>{2,1,3}\,\!</math>
|  <math>v(\{1,2\}) - v(\{2\}) = 0 - 0 = 0\,\!</math>
|-
! <math>{2,3,1}\,\!</math>
|  <math>v(\{1,2,3\}) - v(\{2,3\}) = 1 - 1 = 0\,\!</math>
|-
! <math>{3,1,2}\,\!</math>
|  <math>v(\{1,3\}) - v(\{3\}) = 1 - 0 =1\,\!</math>
|-
! <math>{3,2,1}\,\!</math>
|  <math>v(\{1,2,3\}) - v(\{2,3\}) = 1 - 1 = 0\,\!</math>
|}

:<math>\psi(v,1)=(1)(\frac{1}{3!})=\frac{1}{6}\,\!</math>.
משיקולי סימטריה נקבל כי גם :<math>\psi(v,2)=\frac{1}{6}\,\!</math>, ומכך שערך שפלי מקיים יעילות נקבל כי:

:<math>\psi(v,3)=v(N)-\psi(v,1)-\psi(v,2)=1-\frac{1}{6}-\frac{1}{6}=\frac{2}{3}\,\!</math>.
ובכך חישבנו את ערך שפלי של משחק  הכפפה.

=== בניית קואליציה בפרלמנט ===
במדינה מסוימת יש בפרלמנט 27 חברים. 11 מפלגות התמודדו בבחירות. נסמן את קבוצת המפלגות ב<math>N=\left\{1 \dots 11 \right\}</math>. לאחר הבחירות התקבלה חלוקת המנדטים הבאה בפרלמנט:
*מפלגות 1 ו-2 קיבלו 9 מנדטים כל אחת.
*מפלגות 3-11 קיבלו  מנדט אחד כל אחת.
כדי להעביר הצעת חוק צריך רוב (לפחות 14 חברים בפרלמנט). נניח כי כל החברים באותה מפלגה מצביעים באותו אופן. נגדיר את פונקציית התועלת של קבוצת מפלגות <math>S</math> כ <math>v(S)=1</math> אם המפלגות ב-<math>S</math> כוללות לפחות 14 חברי פרלמנט ו <math>v(S)=0</math> אחרת. 

נחשב את ערך שפלי עבור המפלגה 3 (ומסימטריה זה יהיה אותו ערך למפלגות 3-11). ברור מהגדרת פונקציית התועלת שהביטוי  <math>v(P_3^R \cup \left \{ 3 \right\})-v(P_3^R)</math> יכול לקבל רק את הערכים 0 או 1. הוא יקבל את הערך 1 רק כאשר <math>v(P_3^R \cup \left \{ 3 \right\})=1</math> וגם <math>v(P_3^R)=0</math>, וזה מתקיים רק כאשר ביחס הסדר R מופיעות לפני המפלגה 3 מפלגה אחת גדולה (1 או 2) ו-4 מפלגות קטנות (מפלגות 4-11). ביחסי הסדר שמקיימים זאת יש 2 מפלגות גדולות שיכולות להופיע לפני מפלגה 3, כל אחת מהן יכולה להיות ב-5 מקומות שונים, והמפלגות הקטנות יכולות להסתדר ב- !8 סידורים שונים במקומות שנותרו. בסה"כ נקבל כי:<br />
<br />
<math>\psi(V,3)=\psi(V,4)=\dots=\psi(V,11)=\frac{2\cdot5\cdot5\cdot8!}{11!}=\frac{5}{99}</math><br />
<br />
מיעילות ערך שפלי וסימטריה של המפלגות 1,2 נקבל כי:
<br />
<br />
<math>\psi(v,1)=\psi(v,2)=\frac{1}{2}\cdot(v(N)-\sum_{3 \le i \le 11} \psi(v,i))=\frac{1}{2}\cdot(1-\frac{9\cdot5}{99})=\frac{3}{11}</math>.
<br />
מהחישוב שעשינו עולה כי הכוח של כל המפלגות הקטנות ביחד הוא <math>\frac{5}{11}</math>, אך מספר המנדטים שלהם שווה למספר המנדטים של מפלגה גדולה. מכאן נוכל להסיק כי אם מפלגה גדולה מתפצלת לכמה מפלגות קטנות אז הכוח הפרלמנטרי שלה עולה.

==ראו גם==
*[[מונחים בתורת המשחקים]]
*[[משפט יאנג]]
*[[מדד הכוח של שפלי ושוביק]]


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

[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:תורת המשחקים]]