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

ג'ון פורבס נאש

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

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

הסבר אינטואיטיבי ודוגמה בסיסית

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

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

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

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

נניח שיש $I$ שחקנים וכל שחקן $i\in \left\{1,2,\ldots ,I\right\}$ יכול לבחור אסטרטגיה (תכסיס) אחת מתוך קבוצת האסטרטגיות הקיימות עבורו: $s_{j}\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)\geq 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 יכול לעשות זה לבחור A. כל אסטרטגיה אחרת מצד שחקן 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.

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

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

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

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

ראו גם

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

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

• שיווי משקל נאש, באתר MathWorld (באנגלית)