שיווי משקל נאש
בתורת המשחקים, שיווי משקל נאש (באנגלית: Nash equilibrium, על שם ג'ון פורבס נאש) הוא מושג המשמש בחקר משחקים שאינם שיתופיים, כלומר משחקים שבהם השחקנים אינם מתקשרים ביניהם, ולכן אינם יכולים לקבל החלטות משותפות.
נקודת שיווי משקל במשחק היא צירוף של אסטרטגיות השחקנים (תכסיסים), כך שלאף אחד מהשחקנים לא משתלם לשנות את האסטרטגיה שלו אם שאר השחקנים אינם משנים את האסטרטגיה שלהם. שיווי משקל נאש אינו בהכרח מצב יעיל פארטו כפי שמדגימה דילמת האסיר, ובמקרה בו נוצר שיווי משקל שאינו יעיל פארטו, קיים תמריץ לאחד או יותר מהשחקנים להציע תשלום צד לשחקנים אחרים כדי להביא את המערכת למצב יעיל פארטו.
הסבר אינטואיטיבי ודוגמה בסיסית
על מנת שיתקיים שיווי משקל נאש נדרש שכל שחקן יבחר אסטרטגיה שאילו גם היה יודע לגבי האסטרטגיה שבה יבחר כל אחד מבין השחקנים האחרים, לא היה מתחרט לגביה. במקרה של דילמת האסיר, נקודת שיווי המשקל היא במקרה ששני השחקנים בוחרים להסגיר זה את זה. ההסבר לכך הוא שאילו היה שחקן A מביניהם בוחר באסטרטגיית השתיקה, היה מתחרט על כך בכל מקרה (אילו B היה בוחר לשתוק, היה A מעדיף להסגיר את B ולצאת ללא עונש ואילו B היה בוחר להסגיר את A, היה A מעדיף להסגיר גם את B מאשר לרצות את העונש המקסימלי במקרה זה). לפיכך שיווי המשקל הוא כאשר כל אחד מבין השחקנים A ו-B בוחרים להסגיר את חברם.
שיווי משקל בתכסיסים טהורים
בערך זה |
נניח שיש שחקנים וכל שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in \left \{ 1, 2, \ldots, I \right \} } יכול לבחור אסטרטגיה (תכסיס) אחת מתוך קבוצת האסטרטגיות הקיימות עבורו: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_j \in S_i} . נסמן את צירוף האסטרטגיות של כל השחקנים באות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} (ללא סימון שחקן): הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s \in S = S_1 \times S_2 \times \cdots \times S_I } . תוצאת המשחק נקבעת לפי צירוף האסטרטגיות וכך גם ווקטור התשלום לשחקנים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\left ( s \right ) } . נהוג לכתוב את צירוף האסטרטגיות מנקודת מבטו של שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i } כך: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s = \left ( s_i, s_{-i} \right ) } . כלומר, האסטרטגיה שלי והאסטרטגיה של שאר השחקנים.
צירוף האסטרטגיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s^*=\left (s_1^*,s_2^*,\ldots,s_I^*\right ) } הוא שיווי משקל נאש אם לכל שחקן i מתקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\left ( s_i^*,s_{-i}^* \right ) \ge g \left (s_i, s_{-i}^* \right ) } לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i \in S_i } כלומר אין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} שיכול להביא לתשלום גבוה יותר כל עוד שאר השחקנים "תקועים" עם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i^*} .
דוגמה: נניח שני שחקנים. שחקן 1 יכול לבחור בין תכסיסים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_1 = \left ( A, B, C \right )} ושחקן 2 יכול לבחור מתוך הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_2 = \left ( d, e, f \right )} . התשלומים מתוארים בעזרת הטבלה הבאה (כל משבצת היא כמו הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\left ( s \right )} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 |
עבור כל אחד מהצירופים של האסטרטגיות אנחנו יכולים לבדוק האם הוא שיווי משקל נאש. ישנם שני שיוויי משקל נאש במשחק זה. הראשון הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left ( A, d \right )} עם תשלומים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left ( 4, 4 \right )} . כל עוד שחקן 1 בוחר A, הדבר הטוב ביותר ששחקן 2 יכול לעשות זה לבחור d. כל אסטרטגיה אחרת מצד שחקן 2 תפחית את התשלום עבורו. אם יבחר e יקבל 3 ואם יבחר f יקבל 2. כעת, אם שחקן 2 בוחר ב-d, הדבר הטוב ביותר ששחקן 1 יכול לעשות זה לבחור A. כל אסטרטגיה אחרת מצד שחקן 1 תפחית את התשלום שלו מ-4 ל-2, לכן לא משתלם לו לסטות מ-A.
שיווי משקל נוסף הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left ( B, f \right )} עם תשלומים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left ( 2, 3 \right )} . אם שחקן 1 בוחר B, שחקן 2 אינו יכול לשפר את מצבו. הוא יכול להשיג אותו תשלום אם יבחר d, אך הוא לא יוכל להשיג יותר מ-3. לכן אין לו בעיה להישאר עם f. כעת, אם שחקן 2 נשאר על f, הדבר הטוב ביותר ששחקן 1 יכול לעשות זה לבחור B.
דוגמאות נוספות: בדילמת האסיר שיווי משקל הוא כששניהם בוגדים, ובמשחק השפן שיווי משקל הוא כשאחד נוסע ישר והשני סוטה.
שיווי משקל בתכסיסים מעורבים
כעת נרחיב את הבחירה של השחקן מבחירה של תכסיס מסוים להגרלה בין תכסיסים (תכסיס מעורב). לדוגמה, במקום לבחור במשחק הקודם, שחקן 1 יכול להטיל קובייה ולשחק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} אם התוצאה היא 1 או 2, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} אם התוצאה היא 3 או 4, או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} אם התוצאה היא 5 או 6. כך השחקן מערב את התכסיסים באופן כזה שהוא משחק כל אחת מהאסטרטגיות בהסתברות שליש.
| שוער קופץ ימינה | שוער קופץ שמאלה | |
|---|---|---|
| חלוץ בועט ימינה | 10, 10- | 10-, 10 |
| חלוץ בועט שמאלה | 10-, 10 | 10, 10- |
קל לראות מדוע שחקן ירצה לערב בדוגמה של משחק בעיטות עונשין בכדורגל. נניח שיש שני שחקנים: החלוץ והשוער. החלוץ יכול לבעוט לימין השער או לשמאלו והשוער יכול לזנק לימין השער או לשמאלו. נניח שהשוער והחלוץ מחליטים בו-זמנית ואינם יכולים לדעת מה השחקן האחר יעשה בזמן שהם מחליטים. אם החלוץ והשוער מחליטים על אותו צד השוער עוצר את הכדור וזוכה בתשלום חיובי בעוד החלוץ מקבל תשלום שלילי. במצב ההפוך החלוץ מצליח להבקיע ומקבל תשלום חיובי בעוד השוער מסתפק בתשלום שלילי. במשחק זה אין שיווי משקל נאש באסטרטגיות טהורות. בכל משבצת אחד השחקנים מרוויח מסטייה למשבצת שליד. ממשבצת בה השחקנים מתואמים על אותו צד, החלוץ מרוויח אם הוא יסטה לצד השני. לכן שתי המשבצות הללו אינן שיווי משקל. גם מצב בו השחקנים אינם מתואמים אינו שיווי משקל, כי השוער ירוויח מסטיה לצד השני.
עם זאת, ישנו שיווי משקל נאש באסטרטגיות מעורבות. אם החלוץ יטיל מטבע ויבעט בהסתברות 0.5 ימינה ובהסתברות 0.5 שמאלה, השוער אדיש בין לקפוץ ימינה או שמאלה, כי בממוצע הוא יקבל אותו התשלום: 0. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 (באנגלית)
34381592שיווי משקל נאש