שיווי משקל נאש

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

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

שיווי משקל בתכסיסים טהורים

נניח שיש $I$ שחקנים וכל שחקן $i\in \left\{1,2,\ldots ,I\right\}$ יכול לבחור אסטרטגיה (תכסיס) אחת מתוך קבוצת האסטרטגיות הקיימות עבורו: $s_{i}\in S_{i}$. נסמן את צירוף האסטרטגיות של כל השחקנים באות $s$ (ללא סימון שחקן): $s\in S=S_{1}\times S_{2}\times \cdots \times S_{I}$ . תוצאת המשחק נקבעת לפי צירוף האסטרטגיות וכך גם ווקטור התשלום לשחקנים: $g\left(s\right)$. נהוג לכתוב את צירוף האסטרטגיות מנקודת מבטו של שחקן $i$ כך: $s=\left(s_{i},s_{-i}\right)$ . כלומר, האסטרטגיה שלי והאסטרטגיה של שאר השחקנים.

צירוף האסטרגיות $s^{*}=\left(s_{1}^{*},s_{2}^{*},\ldots ,s_{I}^{*}\right)$ הוא שיווי משקל נאש אם לכל שחקן i מתקיים: $g\left(s_{i}^{*},s_{-i}^{*}\right)>=g\left(s_{i},s_{-i}^{*}\right)$ לכל $s_{i}\in S_{i}$ כלומר אין $s_{i}$ שיכול להביא לתשלום גבוה יותר כל עוד שאר השחקנים "תקועים" עם $s_{i}^{*}$.

דוגמא: נניח שני שחקנים. שחקן 1 יכול לבחור בין תכסיסים $S_{1}=\left(A,B,C\right)$ ושחקן 2 יכול לבחור מתוך הקבוצה $S_{2}=\left(d,e,f\right)$ . התשלומים מתוארים בעזרת הטבלה הבאה (כל משבצת היא כמו הפונקציה $g\left(s\right)$ כאשר $s$ הוא הצירוף הרלוונטי של השורה והטור (Ae לדוגמא). התשלום של שחקן 1 מופיע קודם ואחריו התשלום של שחקן 2.

משחק לדוגמא

	שחקן 2 בוחר באסטרטגיה d	שחקן 2 בוחר באסטרטגיה e	שחקן 2 בוחר באסטרטגיה f
שחקן 1 בוחר באסטרטגיה A	4, 4	3, 12	2, 1
שחקן 1 בוחר באסטרטגיה B	3, 1	1, 3	3, 2
שחקן 1 בוחר באסטרטגיה C	2, 3	4, 3	2, 0

עבור כל אחד מהצירופים של האסטרטגיות אנחנו יכולים לבדוק האם הוא שיווי משקל נאש. ישנם שני שיוויי משקל נאש במשחק זה. הראשון הוא $\left(A,d\right)$ עם תשלומים $\left(4,4\right)$. כל עוד שחקן 1 בוחר A, הדבר הטוב ביותר ששחקן 2 יכול לעשות זה לבחור d. כל אסטרטגיה אחרת מצד שחקן 2 תפחית את התשלום עבורו. אם יבחר e יקבל 3 ואם יבחר f יקבל 2. כעת, אם שחקן 2 בוחר ב-d, הדבר הכי כל אסטרטגיה אחרת מצד שחקן 1 תפחית את התשלום שלו מ-4 ל-2, לכן לא משתלם לו לסטות מ-A.

שיווי משקל נוסף הוא $\left(B,f\right)$ עם תשלומים $\left(2,3\right)$ . אם שחקן 1 בוחר B, שחקן 2 אינו יכול לשפר את מצבו. הוא יכול להשיג את אותו תשלום אם יבחר d, אך הוא לא יוכל להשיג יותר מ-3. לכן אין לו בעיה להישאר עם f. כעת, אם שחקן 2 נשאר על f, הדבר הטוב ביותר ששחקן 1 יכול לעשות זה לבחור B.

שיווי משקל בתכסיסים מעורבים

כעת נרחיב את הבחירה של השחקן מבחירה של תכסיס מסוים להגרלה בין תכסיסים (תכסיס מעורב). לדוגמא, במקום לבחור $A$ במשחק הקודם, שחקן 1 יכול להטיל קוביה ולשחק $A$ אם התוצאה היא 1 או 2, $B$ אם התוצאה היא 3 או 4, או $C$ אם התוצאה היא 5 או 6. כך השחקן מערב את התכסיסים באופן כזה שהוא משחק כל אחת מהאסטרטגיות בהסתברות שליש.

משחק לדוגמא

	שוער קופץ ימינה	שוער קופץ שמאלה
חלוץ בועט ימינה	10, 10-	10-, 10
חלוץ בועט שמאלה	10-, 10	10, 10-

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

עם זאת, ישנו שיווי משקל נאש באסטרטגיות מעורבות. אם החלוץ יטיל מטבע ויבעט בהסתברות 0.5 ימינה ובהסתברות 0.5 שמאלה, השוער אדיש בין לקפוץ ימינה או שמאלה, כי בממוצע הוא יקבל את אותו התשלום: 0. $E\left[g_{2}\left(Left\right)\right]=E\left[g_{2}\left(Right\right)\right]=10\cdot 0.5+\left(-10\right)\cdot 0.5=0$

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

מכאן, שיווי המשקל היחיד במשחק הזה הוא שיווי המשקל בו שני השחקנים מערבים בין ימינה ושמאלה בהסתברות 0.5. תוחלת (ממוצע) התשלום הוא 0 לשני השחקנים.

שיווי משקל נאש באסטרטגיות מעורבות כולל בתוכו את מושג שיווי המשקל נאש באסטרטגיות טהורות: אם נגדיר אסטרטגיה טהורה כהגרלה בין אסטרטגיות בה אחת האסטרטגיות משוחקת בהסתברות 1 והשאר בהסתברות 0.

משפט: לכל משחק סופי קיים שיווי משקל נאש בתכסיסים מעורבים.

תוצאות התנהגותיות

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

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