משפט בונדרבה-שפלי

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

המשפט נקרא על שם המתמטיקאים אולגה בונדרבה ולויד שפלי (Lloyd Shapley, Olga Bondareva) אשר הוכיחו אותו כל אחד בנפרד (בונדרבה ב-1963, שפלי ב-1967).

רקע

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

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

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

המשפט

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

ניסוח ראשון

עבור המשחק $\;\left(N;v\right)\;$, כאשר $\;N=\left\{1,2,...,n\right\}\;$ היא קבוצת השחקנים ו $\;v:2^{N}\to \mathbb {R} \;$ היא הפונקציה הקואליציונית.
תנאי הכרחי ומספיק לכך שהליבה של המשחק $\;\left(N;v\right)\;$ איננה ריקה הוא שלכל אוסף מאוזן $\;D\;$ של קואליציות ולכל אוסף של וקטורי מקדמים מאזנים $\;\left(\delta _{S}\right)_{S\in D}\;$ מתקיים: $\;\sum \limits _{S\in D}{\delta _{S}v\left(S\right)\leq v\left(N\right)}\;$.

ניסוח שני

נסמן את אוסף הקואליציות הלא ריקות ב - $D^{*}:=\left\{S\subseteq N:S\neq \emptyset \right\}$. נסמן ב-$\;P\;$ את אוסף כל המשקלות המאזנים חלש את $\;D^{*}\;$: $$P=\left\{\delta =\left(\delta _{S}\right)_{S\in D^{*}}:\delta _{S}\geq 0\quad \forall S\in D^{*},\sum _{S\in D^{*}}{\delta _{S}{\chi ^{S}}}={\chi ^{N}}\right\}$$

כאשר נשים לב כי $\;\chi ^{S}$ הוא וקטור החילה של הקואליציה $\;S$.

המשפט: תנאי הכרחי ומספיק לכך שהליבה של המשחק $\;\left(N;v\right)\;$ איננה ריקה הוא שלכל $\;\delta \in P$ מתקיים: $\;\sum \limits _{S\in D*}{\delta _{S}v\left(S\right)\leq v\left(N\right)}\;$.

הוכחת המשפט

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

שלב ראשון - הגדרת בעיית תכנון ליניארי (הבעיה הפרימאלית)

נתבונן בבעיית התכנון הליניארי במשתנים $\left(\delta _{S}\right)_{S\in D^{*}}$:

חשב את: ___________________________________________________ $Z_{P}=max\sum _{S\in D^{*}}{\delta _{S}v\left(S\right)}$

תחת האילוצים: ______ $\textstyle \sum _{\left\{S:i\in S\right\}}{\delta _{S}}=1,\quad \forall S\in D^{*}\qquad ;\qquad \delta _{S}\geq 0,\quad \forall S\in D^{*}$

הערה: בסימונים רגילים של בעיית תכנון ליניארי: $\;A\sim \chi ^{S}\quad ;\quad B\sim {\vec {1}}\quad ;\quad C\sim v\left(S\right)\quad ;\quad x\sim \delta _{S}\;$

קבוצת הפתרונות האפשריים של בעיה זו היא $\;P\;$, שהיא קבוצה קומפקטית ולא ריקה, ולכן $\;Z_{P}\;$ סופי.

שלב שני - הבעיה הדואלית

ניתן להראות כי הבעיה הדואלית לבעיה שהוגדרה בשלב הראשון היא:

חשב את: ________________________________ $Z_{D}=min\;x\left(N\right)$

תחת האילוצים: _____________ $\;x\left(S\right)\geq v\left(S\right)\quad ,\quad \forall S\in D^{*}\;$

כפי שראינו $\;Z_{P}\;$ סופי, ולכן ממשפט הדואליות של תכנון ליניארי נובע ש-$\;Z_{D}\;$ אף הוא סופי ומתקיים $\;Z_{D}=Z_{P}\;$.

שלב שלישי

בשלב זה נראה שאם הליבה אינה ריקה אז $Z_{D}\leq v\left(N\right)$.

יהי $\;x\;$ וקטור בליבה. אזי $\;x\left(S\right)\geq v\left(S\right)\;$ לכל קואליציה $\;S\;$. לכן, $\;x\;$ מקיים את כל האילוצים הקיימים בבעיה הדואלית. כמו כן, ערך פונקציית המטרה ב-$\;x\;$ הוא $x\left(N\right)=v\left(N\right)$. לכן, $Z_{D}\leq v\left(N\right)$ כנדרש.

שלב רביעי

בשלב זה נראה את הכיוון ההפוך, כלומר אם $Z_{D}\leq v\left(N\right)$ אז הליבה אינה ריקה.

יהי $\;x\;$ וקטור אפשרי בבעיה הדואלית שבו מתקבל המינימום, כלומר $x\left(N\right)=Z_{D}$. מכיוון ש-$\;x\;$ מקיים את האילוצים של הבעיה הדואלית, הוא סביר קבוצתית. נראה כי $x\left(N\right)=v\left(N\right)$. מכיוון שההנחה היא ש - $Z_{D}\leq v\left(N\right)$, מתקיים כי $x\left(N\right)=\textstyle \sum _{i\in N}{x_{i}}=Z_{D}\leq v\left(N\right)$. עבור $\;S=N\;$ האילוץ $x\left(S\right)\geq v\left(S\right)$ הוא למעשה $x\left(N\right)\geq v\left(N\right)$, כלומר נקבל כי $x\left(N\right)=v\left(N\right)$. לכן, $\;x\;$ נמצא בליבה, כלומר הליבה אינה ריקה, כנדרש.

שלב חמישי

לסיום ההוכחה נראה כי $Z_{P}\leq v\left(N\right)$ אם ורק אם תנאי בונדרבה-שפלי מתקיים.

ממבט על הבעיה הפרימאלית $Z_{P}\leq v\left(N\right)$ אם ורק אם לכל פתרון אפשרי $\delta =\left(\delta _{S}\right)_{S\in D^{*}}$ מתקיים $\textstyle \sum _{\left\{S:i\in S\right\}}{\delta _{S}v\left(S\right)}\leq v\left(N\right)$, וזהו בדיוק תנאי בונדרבה-שפלי. בשלב השני הוכחנו כי $\;Z_{P}=Z_{D}\;$ ובשלבים שלוש וארבע הראינו כי $Z_{D}\leq v\left(N\right)$ אם ורק אם הליבה אינה ריקה.

בסה"כ קיבלנו כי הליבה אינה ריקה אם ורק אם מתקיים תנאי בונדרבה-שפלי. _______________________________________________________ $\blacksquare$

לקריאה נוספת

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