ערך שפלי

בתורת המשחקים, ערך שֵׁפְּלִי הוא אחד הפתרונות למשחקים בצורת פונקציה קואליציונית. הפתרון פותח על ידי לוֹיְד שֵׁפְּלִי בשנת 1953 ונקרא על שמו.

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

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

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

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

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

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

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

ניסוח פורמלי

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

$\ v(\emptyset )=0$ - הקואליציה הריקה אינה מרוויחה דבר.
לכל שתי קבוצות זרות 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$ . את שלוש הדרישות הראשונות להוגנות שהזכרנו בפתיח לערך אפשר לנסח באופן הבא:

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

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

כאמור, משפט שפלי מוכיח כי תחת הקריטריונים של הוגנות שהוגדרו קיימת חלוקה הוגנת יחידה. אם נתון סדר מלא של השחקנים (ראשון, שני וכו'), התועלת שמביא השחקן ה-i היא ההפרש $\ \nu (\{1,2,\dots ,i\})-\nu (\{1,2,\dots ,i-1\})$ . ערך שפלי, שהוא החלוקה ההוגנת היחידה, מקצה לשחקן i את התועלת הממוצעת שהוא מביא. כלומר,

\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.

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

נוסחה שקולה

עבור כל יחס סדר כזה 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\}}|S|!\cdot \left(|N|-|S|-1\right)!\cdot \left(v\left(S\cup \{i\}\right)-v\left(S\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})\,\!$ . תכונה דומה מתקיימת גם עבור הערך של שפלי, אלא שהגדרת המשחק המצומצם שונה, והיא ניתנה על ידי סרג'יו הרט ואנדרו מס-כולל^[1] . יתר על כן, תכונת המשחק המצומצם יכולה לשמש לאפיון אקסיומטי לערך שפלי, בדיוק כשם שהיא משמשת לאפיון אקסיומטי של הגרעינון. לשני מושגי הפתרון הנקודתיים ישנה אותה מערכת אקסיומות מאפיינת, ורק הגדרת המשחק המצומצם שונה. לכן, כשבאים לבחור באחד ממושגי הפתרון, כדאי לבדוק איזה משחק מצומצם מתאים יותר בסיטואציה הנידונה.

דוגמאות

משחק הכפפה

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

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}}$ , אך מספר המנדטים שלהם שווה למספר המנדטים של מפלגה גדולה. מכאן נוכל להסיק כי אם מפלגה גדולה מתפצלת לכמה מפלגות קטנות אז הכוח הפרלמנטרי שלה עולה.