ערך שפלי

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

בתורת המשחקים, ערך שפלי (Shapley value) הוא פתרון לאחת הבעיות המרכזיות במשחקים שיתופיים, שפותח על-ידי לויד שפלי בשנת 1953.

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

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

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

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

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

[עריכה] ניסוח פורמלי

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

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

פונקציית חלוקה $\ \phi(\nu) : N\rightarrow \mathbb{R}$ , היא וקטור תשלומים המתאים לכל שחקן את הנתח ההוגן עבורו (על-פי פונקציית הרווח). את שלוש האקסיומות הראשונות אפשר לנסח באופן הבא:

יעילות: $\sum_{i=1}^n\phi(\nu,i)=v(N)$ .
אדישות: שחקן סרק הוא x כזה שעבורו, לכל קבוצה $\ x \not \in S$ , מתקיים $\ \nu(S\cup \{x\})=\nu(S)+\nu(\{x\})$ . במקרה כזה דורשים ש- $\ \phi(\nu,x) = \nu(\{x\})$ .
סימטריות: אם x,y הם שחקנים המקיימים $\ \phi(S\cup\{x\})=\phi(S\cup\{y\})$ לכל קואליציה S שאינה מכילה את x ואת y, אז $\ \phi(\nu,x) = \phi(\nu,y)$ .

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

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

[עריכה] חישוב הערך

ערך שפלי של שחקן i שווה לתרומה הממוצעת של i לקבוצה שאיננה כוללת אותו, כלומר, לערך הממוצע של ההפרש $\ \nu(S\cup\{i\})-\nu(S)$ , כאשר הקבוצה S מוגרלת באופן הבא: מסדרים את n השחקנים באקראי (לזה יש $\ n!$ אפשרויות), ואז הקבוצה S כוללת את כל השחקנים הקודמים ל- i.

כך למשל במשחק בן שלושה שחקנים, הערך ההוגן עבור השחקן a שווה ל- $\ \frac{\nu(\{a\})}{3} + \frac{\nu(\{a,b\})-\nu(\{b\})}{6}+\frac{\nu(\{a,c\})-\nu(\{c\})}{6}+\frac{\nu(\{a,b,c\})-\nu(\{b,c\})}{3}$ .

[עריכה] דוגמה

לשחקנים A,B ו- C יש אפשרות לקבל 6 יחידות אם B או C ישתפו פעולה עם השחקן A, ו- 12 יחידות אם הם ישתפו פעולה זה עם זה (עם A או בלעדיו). ערך שפלי מעניק במקרה כזה 5 יחידות ל- B ול- C, ושתי יחידות ל- A. התוצאה איננה מקיימת את תנאי הסבירות הקואליציונית (B ו- C יכולים לקבל יחד 12, בעוד שחלוקת שפלי מציעה להם רק 10). אם כך, ערך שפלי עשוי שלא להשתייך לליבה של המשחק.