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

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

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

המשפט נקרא על שם המתמטיקאים אולגה בונדרבה ולויד שפלי (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)\le v\left( N \right)} \;.

ניסוח שני[עריכת קוד מקור | עריכה]

נסמן את אוסף הקואליציות הלא ריקות ב -  D^* := \left\{S \subseteq N : S \ne \emptyset \right\} . נסמן ב-\;P \; את אוסף כל המשקלות המאזנים חלש את \;D^* \;:

 P = \left\{\delta = \left(\delta_{S} \right)_{S \in D^*} : \delta_{S} \ge 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)\le 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} \ge 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) \ge v\left(S \right) \quad , \quad \forall S \in D^* \;

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

שלב שלישי[עריכת קוד מקור | עריכה]

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

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

שלב רביעי[עריכת קוד מקור | עריכה]

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

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

שלב חמישי[עריכת קוד מקור | עריכה]

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

ממבט על הבעיה הפרימאלית  Z_{P} \le 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)} \le v \left(N \right) , וזהו בדיוק תנאי בונדרבה-שפלי. בשלב השני הוכחנו כי \; Z_{P} = Z_{D} \; ובשלבים שלוש וארבע הראינו כי  Z_{D} \le v \left(N \right) אם ורק אם הליבה אינה ריקה.

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

מסקנות[עריכת קוד מקור | עריכה]

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

לקריאה נוספת[עריכת קוד מקור | עריכה]