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

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

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

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

שיווי משקל עבור קואוליציות

בניגוד לשיווי משקל נאש, המהווה שיווי משקל בו אף שחקן לא יכול להרוויח מסטיה ומתעלם מהאפשרות של שחקנים ליצור קואליציות שישפרו את מצבם, הגדרת שיווי משקל 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_{i}\left(s_{T}^{*},s_{-T}^{*}\right)<g_{i}\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)$ הוא שיווי משקל חזק, אם לא קיימת קואליציה (בכל גודל, ובפרט עבור שחקן בודד). שקיים עבורה שיפור קואליציאני.

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

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

$\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}^{*}).$

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

$\forall T\neq \emptyset \subseteq I,\forall s_{T}\in S_{T},\exists i\in I,g_{i}(s_{T}^{*},s_{-T}^{*})>=g_{i}(s_{T},s_{-T}^{*}).$

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

דוגמאות לשיווי משקל חזק

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

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

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

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

$\forall T\neq \emptyset \subseteq I,|T|<=K,\forall s_{T}\in S_{T},\exists 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 שחקנים לא יכולה להיווצר).

ראו גם

• שיווי משקל נאש
• שיווי משקל מתואם

לקריאה נוספת

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

קישורים חיצוניים

• 1 - מאמר על שיווי משקל שונים (באנגלית)(הקישור אינו פעיל) - באתר אוניברסיטת קוק (Koc), טורקיה.
• 2 - In: Kuhn, hw, Tucker, ww (Eds.), Contributions to the theory of games, vol. II, Princeton University Press, pp. 10-11. 5 Lewis, D., 1969 באתר - גוגל ספרים.