שיווי משקל נאש – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־08:45, 5 ביוני 2009

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

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

שיווי משקל באסטרטגיות טהורות

נניח שיש $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.

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

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

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

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

@@ שורה 2: / שורה 2: @@
 נקודת שיווי משקל במשחק היא צירוף של אסטרטגיות השחקנים ([[תכסיס (בתורת המשחקים)|תכסיס]]ים), כך שלאף אחד מהשחקנים לא משתלם לשנות את התכסיס שלו אם שאר השחקנים אינם משנים את התכסיס שלהם.
-באופן מדויק, עבור אסטרטגיות טהורות, נניח שיש <math>I</math> שחקנים ולכל שחקן <math>i</math> קבוצת אסטרטגיות <math>S_i</math> ממנה הוא בוחר אחת לפעול לפיה: <math>s_i \in S_i</math>. צירוף האסטרטגיות של כל השחקנים הוא <math> s \in S = S_1 \times S_2 \times \cdots \times S_I </math> . תוצאת המשחק נקבעת לפי צירוף האסטרטגיות וכך גם ווקטור התשלום לשחקנים: <math> g\left ( s \right ) </math>. נהוג לכתוב את צירוף האסטרטגיות מנקודת מבטו של שחקן <math> i </math> כך: <math> s = \left ( s_i, s_{-i} \right ) </math> . כלומר, האסטרטגיה שלי והאסטרטגיה של שאר השחקנים.
+==שיווי משקל באסטרטגיות טהורות==
+נניח שיש <math>I</math> שחקנים וכל שחקן <math> i \in \left \{ 1, 2, \ldots , I \right \} </math> יכול לבחור אסטרטגיה אחת מתוך קבוצת האסטרטגיות הקיימות עבורו: <math>s_i \in S_i</math>. נסמן את צירוף האסטרטגיות של כל השחקנים באות <math>s</math> (ללא סימון שחקן): <math> s \in S = S_1 \times S_2 \times \cdots \times S_I </math> . תוצאת המשחק נקבעת לפי צירוף האסטרטגיות וכך גם ווקטור התשלום לשחקנים: <math> g\left ( s \right ) </math>. נהוג לכתוב את צירוף האסטרטגיות מנקודת מבטו של שחקן <math> i </math> כך: <math> s = \left ( s_i, s_{-i} \right ) </math> . כלומר, האסטרטגיה שלי והאסטרטגיה של שאר השחקנים.
 צירוף האסטרגיות <math> s^*=\left (s_1^*,s_2^*,\ldots,s_I^*\right ) </math> הוא שיווי משקל נאש אם לכל שחקן i מתקיים:
@@ שורה 40: / שורה 42: @@
 שיווי משקל נוסף הוא <math>\left ( B, f \right )</math> עם תשלומים <math>\left ( 2, 3 \right )</math> . אם שחקן 1 בוחר B, שחקן 2 אינו יכול לשפר את מצבו. הוא יכול להשיג את אותו תשלום אם יבחר d, אך הוא לא יוכל להשיג יותר מ-3. לכן אין לו בעיה להישאר עם f. כעת, אם שחקן 2 נשאר על f, הדבר הטוב ביותר ששחקן 1 יכול לעשות זה לבחור B.
+== שיווי משקל בתכסיסים מעורבים ==
+כעת נרחיב את הבחירה של השחקן מבחירה של [[תכסיס]] מסוים להגרלה בין תכסיסים ([[תכסיס מעורב]]). לדוגמא, במקום לבחור <math>A</math> במשחק הקודם, שחקן 1 יכול להטיל קוביה ולשחק <math>A</math> אם התוצאה היא 1 או 2, <math>B</math> אם התוצאה היא 3 או 4, או <math>C</math> אם התוצאה היא 5 או 6. כך השחקן מערב את התכסיסים באופן כזה שהוא משחק כל אחת מהאסטרטגיות ב[[הסתברות]] שליש.
+{| align=left border="1" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
+|+ align=bottom |''משחק לדוגמא
+|
+!style="width: 90px"| שוער קופץ ימינה
+!style="width: 90px"| שוער קופץ שמאלה
+|-
+!style="width: 90px"| חלוץ בועט ימינה
+|align=center|''10'', ''10-''
+|align=center|''10-'', ''10''
+|-
+!style="width: 90px"| חלוץ בועט שמאלה
+|align=center|''10-'', ''10''
+|align=center|''10'', ''10-''
+|-
+|-
+|}
+קל לראות מדוע שחקן ירצה לערב בדוגמא של משחק בעיטות עונשין בכדורגל. נניח שיש שני שחקנים: החלוץ והשוער. החלוץ יכול לבעוט לימין השער או לשמאלו והשוער יכול לזנק לימין השער או לשמאלו. נניח שהשוער והחלוץ מחליטים בו-זמנית ואינם יכולים לדעת מה השחקן האחר יעשה בזמן שהם מחליטים. אם החלוץ והשוער מחליטים על אותו צד השוער עוצר את הכדור וזוכה בתשלום חיובי בעוד החלוץ מקבל תשלום שלילי. במצב ההפוך החלוץ מצליח להבקיע ומקבל תשלום חיובי בעוד השוער מסתפק בתשלום שלילי.
+במשחק זה אין שיווי משקל נאש באסטרטגיות טהורות. בכל משבצת אחד השחקנים מרוויח מסטייה למשבצת שליד. ממשבצת בה השחקנים מתואמים על אותו צד, החלוץ מרוויח אם הוא יסטה לצד השני. לכן שתי המשבצות הללו אינן שיווי משקל. גם מצב בו השחקנים אינם מתואמים אינו שיווי משקל, כי השוער ירוויח מסטיה לצד השני.
+עם זאת, ישנו שיווי משקל נאש באסטרטגיות מעורבות. אם החלוץ יטיל מטבע ויבעט בהסתברות 0.5 ימינה ובהסתברות 0.5 שמאלה, השוער אדיש בין לקפוץ ימינה או שמאלה, כי בממוצע הוא יקבל את אותו התשלום: 0.
+<math> 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</math>
+כדי שהחלוץ יסכים להטיל מטבע הוא צריך להיות אדיש בין שתי האסטרטגיות. אם אחת האסטרטגיות טובה מהאחרת הוא ישפר את מצבו אם ישחק רק על האסטרטגיה הטובה יותר ולא יערב בה אסטרטגיה אחרת שצפויה להניב תשלום נמוך יותר. לכן שיווי משקל בו החלוץ מטיל מטבע - במקרה הזה - הוא שיווי משקל בו גם השוער מטיל מטבע. רק אם השוער יקפוץ ימינה ושמאלה בהסתברות 0.5 לכל צד יהיה החלוץ אדיש בין ימינה ושמאלה ויוכל להגריל גם הוא ימינה ושמאלה בהסתברות 0.5. השוער מוכן להגריל כי כבר הראינו שהוא אדיש.
+מכאן, שיווי המשקל היחיד במשחק הזה הוא שיווי המשקל בו שני השחקנים מערבים בין ימינה ושמאלה בהסתברות 0.5. [[תוחלת]] (ממוצע) התשלום הוא 0 לשני השחקנים.
+שיווי משקל נאש באסטרטגיות מעורבות כולל בתוכו את מושג שיווי המשקל נאש באסטרטגיות טהורות: אם נגדיר אסטרטגיה טהורה כהגרלה בין אסטרטגיות בה אחת האסטרטגיות משוחקת בהסתברות 1 והשאר בהסתברות 0.
+'''משפט''': לכל משחק סופי קיים שיווי משקל נאש בתכסיסים מעורבים.
-נקודת שיווי משקל אינה בהכרח התוצאה הטובה ביותר לכל השחקנים, כפי שמודגם היטב ב[[דילמת האסיר]], שם נקודת שיווי המשקל היא כזו ששני השחקנים מפסידים אם הם בוחרים בה. למרות זאת זהו המצב הטוב ביותר אליו אפשר להגיע בלי ששני השחקנים יוכלו לשפר את מצבם על חשבון האחר.
+== תוצאות התנהגותיות ==
-במשחק יכולות להיות נקודות שיווי משקל אחדות, ואז קרוב לוודאי שתוצאת המשחק תהיה אחת מהן. במשחק יכולות גם לא להיות שום נקודות שיווי משקל, אך נאש הוכיח ב[[משפט נאש]] כי אם מרשים [[תכסיס מעורב|תכסיסים מעורבים]] - כלומר, לבחור דרך פעולה אחת מתוך כמה אפשרויות תוך מתן [[הסתברות]] שונה לאפשרות של בחירה בכל אחת מהאפשרויות - תמיד קיימת במשחק לפחות נקודת שיווי משקל אחת. אם קיימת במשחק נקודת שיווי משקל אחת, וכל השחקנים הם רציונליים לחלוטין (כלומר, פועלים תמיד כדי למקסם את הרווח שלהם, בלי תלות במה שעושים השחקנים האחרים) תוצאת המשחק תהיה זו של נקודת שיווי המשקל.
+קיומו של שיווי משקל נאש אינו מבטיח ששחקנים אכן ישחקו אותו. במשחקים שונים כמו [[התראה (משחק)|משחק ההתראה]] ואחרים, ניסויים הראו כי בני אדם נוטים לשחק אחרת לפעמים. הסבר אחד יכול להיות שהשחקנים לא הבינו את המשחק, טעו בשקילת צעדיהם, הניחו שהשחקנים האחרים לא הבינו או טעו. הסבר נוסף טמון במטרות אחרות של השחקנים שהמשחק לא לקח בחשבון. עם זאת, במקרים מסוימים גם אם בהתחלה שחקנים לא שיחקו כפי ששיווי המשקל מנבא, לאחר מספר משחקים התוצאות התכנסו לשיווי משקל.
 מושג שיווי המשקל מהווה [[הכללה (מתמטיקה)|הכללה]] של מושג הפתרון ב[[משחק סכום אפס|משחקי סכום אפס]] שהוצע על ידי [[ג'ון פון נוימן]], ומשפט נאש מהווה הכללה של [[משפט המינימקס]] שלו.