ערך שפלי

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

קבוצת שחקנים (קואליציה), משתפת פעולה ומרויחה סכום מסוים מעצם שיתוף הפעולה. מאחר שחלק מהשחקנים תרמו יותר לקואליציה מאשר שחקנים אחרים או שהיה ברשותם יותר כוח מיקוח נרצה לדעת איזו חלוקה של הרווחים תהיה "הוגנת" במשחק.

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

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

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

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

1. יעילות: התועלת היא המקסימלית אותה ניתן להשיג. בנוסף, התועלת מחולקת כולה בין השחקנים, ללא בזבוז.
2. אקסיומת שחקן האפס: שחקן שאינו יכול לשפר את רווחיותה של אף קבוצה, אינו ראוי לקבל כל תמורה.
3. סימטריות: שני שחקנים שתרומתם שווה לכל קואליציה, יזכו באותה תמורה.
4. אדיטיביות: כאשר מחברים שני מקורות הכנסה המבוססים על אותה קבוצת שחקנים, אפשר לחשב את חלוקת הרווחים לכל מקור הכנסה בנפרד.

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

ניסוח פורמלי

משחק שיתופי מוגדר על ידי זוג סדור (N,v), כאשר N היא קבוצת השחקנים ו-$\ v$ היא פונקציה קואליציונית - פונקציה חיובית $\ v:2^{N}\rightarrow \mathbb {R}$, המתאימה לכל קואליציה את התועלת הקבוצתית, ועונה על שתי הדרישות הבאות:

1. $\ v(\emptyset )=0$ - הקואליציה הריקה אינה מרוויחה דבר.
2. לכל שתי קבוצות זרות S ו- T, $\ v(S\cup T)\geq v(S)+v(T)$, כלומר, שיתוף פעולה בין קבוצות לעולם אינו מקטין את הרווח המשותף של שתי הקבוצות.

נסמן ב-$\ G^{N}$ את קבוצת פונקציות התועלת על קבוצת השחקנים N.

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

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

פתרון הוא פונקציה $\ \phi$ המתאימה לכל משחק בצורה קואליציונית $\ (N,v)$) וקטור ב-$\ \mathbb {R} ^{N}$ . הגודל $\ \phi _{i}(N,v)$ נקרא הערך של שחקן $\ i$ במשחק $\ (N;v)$ לפי הפתרון $\ \phi$. את שלוש הדרישות הראשונות להוגנות שהזכרנו בפתיח לערך אפשר לנסח באופן הבא:

1. יעילות: לכל פונקציית תועלת $\ v$ מתקיים $\sum _{i=1}^{n}\phi (v,i)=v(N)$.
2. אקסיומת שחקן האפס: לכל פונקציית תועלת $\ v$ ולכל שחקן אפס $i\in N$ ב-$\ v$ מתקיים ש- $\ \phi (v,i)=0$.
3. סימטריות: לכל פונקציית תועלת $\ v$ ולכל שני שחקנים $i,j\in N$ שחילופיים ב-$\ v$ מתקיים $\ \phi (v,i)=\phi (v,j)$.

בנוסף לדרישות אלה, ההעתקה המתאימה לכל פונקציית תועלת $\ v$ את פונקציית החלוקה $\ \phi (v)$, צריכה להיות אדיטיבית, כלומר: לכל שתי פונקציות רווח $\ v,v'$ מתקיים $\!\,\phi (v+v')=\phi (v)+\phi (v')$. מדרישה זו נובע שההעתקה $\ \phi$ היא לינארית ממרחב פונקציות התועלת (שממדו $\ 2^{n}$) למרחב וקטורי התשלומים (שממדו n).

הגדרת ערך שפלי

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

$\psi (v,i)={\frac {1}{|N|!}}\sum _{R}\left[\ v(P_{i}^{R}\cup \left\{i\right\})-\ v(P_{i}^{R})\right]\,\!$

כאשר R הוא יחס סדר על השחקנים, הסכום רץ על כל יחסי הסדר האפשריים (קיימים !n כאלה) ו-$P_{i}^{R}$ היא קבוצת כל השחקנים שמקדימים את i ביחס הסדר R.

משמעות הנוסחה

כאמור, ערך שפלי הוא מדד לתרומה של כל שחקן לשווי הקואליציה. אם נניח שהשחקנים מצטרפים לקואליציה לפי סדר R, אז כאשר שחקן i מצטרף לקואליציה, תרומתו לשווי הקואליציה היא $v(P_{i}^{R}\cup \left\{i\right\})-\ v(P_{i}^{R})$. ערך שפלי של השחקן i הוא ממוצע התרומות שלו על פני כל הסדרים האפשריים.

נוסחה שקולה

עבור כל יחס סדר כזה R, אנו למעשה מתייחסים רק לקואליציה $P_{i}^{R}$, ולא ליחס הסדר בין האיברים שבה. לכן, לכל קואליציה $S\subseteq N\setminus \{i\}$, ניתן לאגד את אוסף כל יחסי הסדר R עבורם $P_{i}^{R}=S$ יחדיו. מספר יחסי הסדר עבורם $P_{i}^{R}=S$ הוא $|S|!\cdot (|N|-|S|-1)!$, ולכן ערך שפלי מתקבל על ידי הנוסחה השקולה:

$\psi (v,i)={\frac {1}{|N|!}}\sum _{S\subseteq N\setminus \{i\}}\left[|S|!\cdot \left(|N|-|S|-1\right)!\cdot \left(v\left(S\cup \{i\}\right)-v\left(S\right)\right)\right]$

במקרים רבים, נוסחה זו קלה יותר לחישוב מהנוסחה הראשונה.

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

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

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

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

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

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

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

עקביות הערך של שפלי

עבור הליבה הוגדר מושג המשחק המצומצם לפי דייויס ומשלר, וידוע כי הליבה מקיימת את תכונת העקביות: אם $\ x$ היא נקודה בליבה של משחק $\ (N;v)$ אז לכל משחק מצומצם $(S;v_{s})\,\!$ הווקטור$(x_{i})_{i}\in S$הוא נקודה בליבה של המשחק $(S;v_{s})\,\!$. תכונה דומה מתקיימת גם עבור הערך של שפלי, אלא שהגדרת המשחק המצומצם שונה, והיא ניתנה על ידי סרג'יו הרט ואנדרו מס-כולל . יתר על כן, תכונת המשחק המצומצם יכולה לשמש לאפיון אקסיומטי לערך שפלי, בדיוק כשם שהיא משמשת לאפיון אקסיומטי של הגרעינון. לשני מושגי הפתרון הנקודתיים ישנה אותה מערכת אקסיומות מאפיינת, ורק הגדרת המשחק המצומצם שונה. לכן, כשבאים לבחור באחד ממושגי הפתרון, כדאי לבדוק איזה משחק מצומצם מתאים יותר בסיטואציה הנידונה.

דוגמאות

משחק הכפפה

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

$N=\{1,2,3\}\,\!$

כאשר לשחקנים 1 ו-2 יש כפפה ימנית ולשחקן 3 יש כפפה שמאלית. פונקציית התועלת למשחק זה היא:

$V(S)={\begin{cases}1&{\mbox{if }}\ S\in \left\{\{1,3\},\{2,3\},\{1,2,3\}\right\}\\0&{\mbox{else}}\\\end{cases}}$

נחשב את ערך שפלי לשחקן 1. נרשום בטבלה את ערך הביטוי $v(P_{1}^{R}\cup \left\{1\right\})-v(P_{1}^{R})$ לכל יחס סדר R:

$R\,\!$	$v(P_{1}^{R}\cup \left\{1\right\})-v(P_{1}^{R})$
${1,2,3}\,\!$	$v(\{1\})-v(\varnothing )=0-0=0\,\!$
${1,3,2}\,\!$	$v(\{1\})-v(\varnothing )=0-0=0\,\!$
${2,1,3}\,\!$	$v(\{1,2\})-v(\{2\})=0-0=0\,\!$
${2,3,1}\,\!$	$v(\{1,2,3\})-v(\{2,3\})=1-1=0\,\!$
${3,1,2}\,\!$	$v(\{1,3\})-v(\{3\})=1-0=1\,\!$
${3,2,1}\,\!$	$v(\{1,2,3\})-v(\{2,3\})=1-1=0\,\!$

$\psi (v,1)=(1)({\frac {1}{3!}})={\frac {1}{6}}\,\!$.

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

$\psi (v,3)=v(N)-\psi (v,1)-\psi (v,2)=1-{\frac {1}{6}}-{\frac {1}{6}}={\frac {2}{3}}\,\!$.

ובכך חישבנו את ערך שפלי של משחק הכפפה.

בניית קואליציה בפרלמנט

במדינה מסוימת יש בפרלמנט 27 חברים. 11 מפלגות התמודדו בבחירות. נסמן את קבוצת המפלגות ב$N=\left\{1\dots 11\right\}$. לאחר הבחירות התקבלה חלוקת המנדטים הבאה בפרלמנט:

• מפלגות 1 ו-2 קיבלו 9 מנדטים כל אחת.
• מפלגות 3-11 קיבלו מנדט אחד כל אחת.

כדי להעביר הצעת חוק צריך רוב (לפחות 14 חברים בפרלמנט). נניח כי כל החברים באותה מפלגה מצביעים באותו אופן. נגדיר את פונקציית התועלת של קבוצת מפלגות $S$ כ $v(S)=1$ אם המפלגות ב-$S$ כוללות לפחות 14 חברי פרלמנט ו $v(S)=0$ אחרת.

נחשב את ערך שפלי עבור המפלגה 3 (ומסימטריה זה יהיה אותו ערך למפלגות 3-11). ברור מהגדרת פונקציית התועלת שהביטוי $v(P_{3}^{R}\cup \left\{3\right\})-v(P_{3}^{R})$ יכול לקבל רק את הערכים 0 או 1. הוא יקבל את הערך 1 רק כאשר $v(P_{3}^{R}\cup \left\{3\right\})=1$ וגם $v(P_{3}^{R})=0$, וזה מתקיים רק כאשר ביחס הסדר R מופיעות לפני המפלגה 3 מפלגה אחת גדולה (1 או 2) ו-4 מפלגות קטנות (מפלגות 4-11). ביחסי הסדר שמקיימים זאת יש 2 מפלגות גדולות שיכולות להופיע לפני מפלגה 3, כל אחת מהן יכולה להיות ב-5 מקומות שונים, והמפלגות הקטנות יכולות להסתדר ב- !8 סידורים שונים במקומות שנותרו. בסה"כ נקבל כי:

$\psi (V,3)=\psi (V,4)=\dots =\psi (V,11)={\frac {2\cdot 5\cdot 5\cdot 8!}{11!}}={\frac {5}{99}}$

מיעילות ערך שפלי וסימטריה של המפלגות 1,2 נקבל כי:

$\psi (v,1)=\psi (v,2)={\frac {1}{2}}\cdot (v(N)-\sum _{3\leq i\leq 11}\psi (v,i))={\frac {1}{2}}\cdot (1-{\frac {9\cdot 5}{99}})={\frac {3}{11}}$.
מהחישוב שעשינו עולה כי הכוח של כל המפלגות הקטנות ביחד הוא ${\frac {5}{11}}$, אך מספר המנדטים שלהם שווה למספר המנדטים של מפלגה גדולה. מכאן נוכל להסיק כי אם מפלגה גדולה מתפצלת לכמה מפלגות קטנות אז הכוח הפרלמנטרי שלה עולה.

ראו גם

• מונחים בתורת המשחקים
• משפט יאנג
• מדד הכוח של שפלי ושוביק

לקריאה נוספת

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