שיווי משקל חזק

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

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

שיווי משקל חזק הוגדר לראשונה על ידי פרופסור ישראל אומן[1] על מנת לתת הרחבה למושג שיווי משקל נאש.

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

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

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

נניח שיש I שחקנים וכל שחקן  i \in \left \{ 1, 2, \ldots , I \right \} יכול לבחור אסטרטגיה (תכסיס) אחת מתוך קבוצת האסטרטגיות הקיימות עבורו: s_i \in S_i.

לצורך פשטות ההסבר נשתמש בהגדרה של אסטרגיות טהורות. ניתן על ידי החלפה של S^* שהגדרנו המהווה פרופיל של אסטרגיות טהורות ל - S^* פרופיל של אסטרגיות מעורבות.

הגדרה: קואליציה. תת-קבוצה של השחקנים \displaystyle T\subseteq I תיקרא קואליציה. נסמן את וקטור האסטרגיות שנבחר על ידי קואליציה כלשהי T של שחקנים כ s_T \in S_T. נסמן את צירוף האסטרטגיות של כל השחקנים באות s (ללא סימון שחקן\קואליציה):  s \in S = S_1 \times S_2 \times \cdots \times S_I . תוצאת המשחק נקבעת לפי צירוף האסטרטגיות וכך גם ווקטור התשלום לשחקנים:  g\left ( s \right ) . נהוג לכתוב את צירוף האסטרטגיות מנקודת מבטה של קואליציה T כך:  s = \left ( s_T, s_{-T} \right ) .כלומר, האסטרטגיה של הקואליציה והאסטרטגיה של שאר השחקנים.

הגדרה: פרופיל אסטרגיות S_T מהווה שיפור עבור קואליציה T מפרופיל אסטרגיות  s^* = (s^*_T,s_{-T}^*) אם לכל שחקן \displaystyle i\in T  g\left ( s_T^*,s_{-T}^* \right ) < g \left (s_T, s_{-T}^* \right ) . זאת אומרת, כל השחקנים בקואליציה משפרים ממש את מצבם, אם הם סוטים במשותף מהפרופיל s_T^* לפרופיל S_T .

קואליציה T נמצאת בשיווי משקל בפרופיל אסטרגיות  s^*=\left (s_1^*,s_2^*,\ldots,s_I^*\right ) אם לא קיים פרופיל אסטרגיות S_T המהווה שיפור קואוליציוני (עבור קואליציה T) שלו.

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

פרופיל אסטרגיות  s^*=\left (s_1^*,s_2^*,\ldots,s_I^*\right ) הוא שיווי משקל חזק, אם לא קיימת קואליציה (בכל גודל, ובפרט עבור שחקן בודד) ‏[2]. שקיים עבורה שיפור קואליציאני.

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

הגדרה פורמלית:

\forall T \subseteq I,\nexists s_T \in S_T : \forall i \in I , g_i(s^*_{T}, s^*_{-T}) < g_i(s_{T},s^*_{-T}).

הגדרה פורמלית מקבילה‏[3] :

\forall T \neq \emptyset \subseteq I,\forall s_T \in S_T , \exist i \in I , g_i(s^*_{T}, s^*_{-T}) >= g_i(s_{T},s^*_{-T}).

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

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

דוגמה פשוטה היא המשחק הבא: שני גמדים, עצלני ובטלני. צריכים להכין לעצמם ארוחה. רק אם שניהם עובדים על הארוחה, הם יכולים להכין אותה. אם הארוחה תהיה מוכנה, כל גמד יקבל ערך 100, אחרת כל גמד יקבל ערך 0. (אנחנו מתעלמים מהטרחה הכרוכה בהכנת הארוחה ‏[4]

עובד נח
עובד 100,100 0,0
נח 0,0 0,0
משחק הגמדים

המצב בו שני הגמדים מתבטלים הוא שיווי משקל נאש, אבל הוא לא שיווי משקל חזק. כי אם קואליציה של שני הגמדים, תתאחד ותחליט לעבוד, שניהם ישיגו ערך 100 (שטוב עבור שניהם מהערך 0 שהשיגו בפרופיל האסרגיות הקודם). לעומת זאת, המצב בו שני הגמדים עובדים, הוא שיווי משקל חזק ‏[5] כיוון ששני הגמדים מקבלים 100. אם אחד הגמדים סוטה, הוא מקבל 0 ולא משפר את מצבו. וכמובן אותו העניין קורה אם שני הגמדים סוטים מהפרופיל ומתבטלים. לכן זהו שיווי משקל חזק.

דוגמה למשחק בו לא קיים שווי משקל חזק, דילמת האסיר:

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

שותק מלשין
שותק שנה אחת, שנה אחת 15 שנה, אפס שנים
מלשין אפס שנים, 15 שנה חמש שנים, חמש שנים
דילמת האסיר

ניתן לראות כי פרופיל האסטרגיות {מלשין,מלשין} הוא שווי משקל נאש, ולא קיים שיווי משקל נאש נוסף, כיוון שלכל אסיר , בלא תלות מה בוחר האסיר השני, עדיף לשחק 'מלשין'. אולם, זהו לא שיווי משקל חזק, כי אם שני האסירים סוטים לפרופיל האסטרגיות {שותק,שותק} שניהם משפרים את מצבם. כמו כן, אף אחד מהפרופילים האחרים אינו שווי משקל חזק כי תמיד אסיר ששותק (שזו קואליציה בגודל אחד) יכול לסטות ולהלשין ובכך לשפר את מצבו.

הגדרת שיווי משקל K-נאש[עריכת קוד מקור | עריכה]

עבור 1<=K<=|I|.פרופיל אסטרגיות  s^*=\left (s_1^*,s_2^*,\ldots,s_I^*\right ) יקרא שיווי משקל K - נאש אם לא קיימת קואליציה שקטנה או שווה בגודלה לK. שקיים עבורה שיפור קואליציאני.

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

הגדרה פורמלית:

\forall T \subseteq I, |T|<=K ,\nexists s_T \in S_T : \forall i \in I , g_i(s^*_{T}, s^*_{-T}) < g_i(s_{T},s^*_{-T}).

הגדרה פורמלית מקבילה‏[6] :

\forall T \neq \emptyset \subseteq I,|T|<=K, \forall s_T \in S_T , \exist i \in I , g_i(s^*_{T}, s^*_{-T}) >= g_i(s_{T},s^*_{-T}).

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

אם פרופיל אסטרגיות מסוים מהווה שיווי משקל K-נאש אזי לכל t<K הוא מהווה שיווי משקל t-נאש.

עבור K=1 שיווי משקל K-נאש הוא שיווי משקל נאש הרגיל

כאמור לעיל, שווי משקל חזק מהווה מקרה פרטי של שיווי משקל K נאש, ובמשחק בן n=|I| שחקנים מהווה שיווי משקל n-נאש. ולכן לכל t<=n הוא מהווה שיווי משקל t נאש.

דוגמאות לשיווי משקל K-נאש שאיננו שיווי משקל חזק[עריכת קוד מקור | עריכה]

נסתכל בדוגמה דומה למקרה הקודם. שלושה גמדים ישנים, אם שלושתם יקומו ויכינו ארוחה, כולם יהנו וירויחו 100, אחרת כל הגמדים ישארו רעבים והתועלת שלהם תהיה 0.

בהגדרה פורמלית.

התועלת עבור כל גמד.

אם כל הגמדים עובדים - 100.

אחרת - 0.

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

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

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

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

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

  1. ^ ראו מקור 2
  2. ^ I
  3. ^ מתוך מקור [1]
  4. ^ נניח שהגמד יכול לראות שחברו לא מעוניין לעבוד, ומיד לחזור ולהתבטל
  5. ^ ובפרט שיווי משקל נאש
  6. ^ ואריצה של ההגדרה מתוך מקור [1], עמוד 15