משפט נאש

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

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

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

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

		דן
		כדורגל	אופרה
דנה	כדורגל	1,2	0,0
	אופרה	0,0	2,1

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

הוכחת המשפט

הוכחת המשפט נעשית באמצעות משפט נקודת השבת של בראואר.

משפט נקודת השבת קובע כי לכל $\ f:S\rightarrow S$ רציפה ו- $\ S\subset \mathbb {R} ^{n}$ קבוצה לא ריקה, קומפקטית וקמורה, יש ל־$\ f$ נקודת שבת.

נניח כי נתון המשחק הבא: במשחק יש $\ n$ שחקנים הממוספרים ב-$\ i$ כאשר $\ i$ נע מ-1 עד $\ n$, ולכל אחד מהם $\ m_{i}$ אסטרטגיות.

כעת, נסתכל על הקבוצה של כל האסטרטגיות המעורבות $\ S_{m_{1}}\times S_{m_{2}}\times ...\times S_{m_{n}}$.

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

נסמן $\ x_{j}^{i}$ - המשקל של הפעולה $\ j$ בהתפלגות $\ x^{i}$.

נגדיר את $\ d_{j}^{i}=u_{i}(j,x^{-i})-u_{i}(x^{i},x^{-i})$ להיות ההפרש בין ערך פונקציות התועלת של השחקן ה-$\ i$

בבחירת הפעולה $\ j$ במקום האסטרטגיה $\ x^{i}$ (כלומר, הרווח שמתקבל מהמעבר לאסטרטגיה $\ j$).

כמו כן, נגדיר $\ max_{j}^{i}=max(d_{j}^{i},0)$.

כעת, נגדיר $\ k_{j}^{i}={\frac {x_{j}^{i}+max_{j}^{i}}{1+\sum _{j=1}^{n}max_{j}^{i}}}$ נשים לב כי קיבלנו פונקציה רציפה ממרחב האסטרטגיות לעצמו.

לכן, ע"פ משפט נקודת השבת של בראואר, קיימת לה נקודת שבת.

נטען כי בנקודת השבת שקיבלנו מתקיים כי לכל $\ i,j$, מתקיים כי $\ d_{j}^{i}\leq 0$.

כלומר, לאף שחקן אין איך להשתפר מנקודה זו ולכן זוהי נקודת שיווי משקל.

ואכן, טענה זו מתקיימת, נוכיח בשלילה. נניח שקיימים $\ i,j$ כך ש-$\ d_{j}^{i}>0$ ואז נקבל סתירה לכך שזו נקודת שבת.

תורת המיקוח של נאש

תורת המיקוח של נאש היא חלק ממשפט נאש השלם.

תורת המיקוח של נאש מציגה פתרונות כאשר:

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

ניתן לחלק זאת באמצעות כותרות כדלהלן:

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

את הגישה הציע המתמטיקאי ג'ון פורבס נאש, בספר בעל 1,950 עמודים, שבו הוא קובע:

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

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

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

• 2 השחקנים מסכימים (יעיל), כל אחד לקבל מחצית (סימטריה)
• בשלב הבא אנו רואים תרחיש כללי יותר. אנו נשתמש ב- X כדי לציין קבוצה של הסכמים אפשריים ו-D לציון תוצאת מחלוקת.

דוגמה נוספת:

X = {(x1, x2)|x1 + x2 = 1, xi≥ 0}, D =(0,0).

נניח כי לכל שחקן i יש העדפות, המיוצגות על ידי תועלות Ui כפונקציה של {X {D. נציין את סט התוצאות האפשריות הניתנות על ידי הקבוצה U שמוגדרות על ידי:

U = {(v1, v2) | u1(x)= v1, u2(x)= v2 for some x . X } (d =(u1(D), u2(D)

בעיה המיקוח היא זוג ( U, ד) שבו U . R2 ו-D. U. אנו נניח כי U הוא קמור וקבוצה קומפקטית.

קיים v שייך ל u כך ש:v > d (i.e., vi > di, לכל i.

נסמן את קבוצת כל בעיות המיקוח האפשריות ב-b.

פתרון מיקוח הוא פונקציית b→u.