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

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

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

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

הגדרת שיווי משקל חזק

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

הגדרת שיווי משקל K-נאש

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

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

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

קיום

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

שימושים

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