משפט נאש

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

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

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

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

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

ניתן לראות כי קיימים שני שיווי משקל נאש טהורים: כדורגל-כדורגל ואופרה-אופרה. בנוסף להם, קיימים שני שיוויי משקל נאש מעורבים: $\ (1/3,2/3)$ ו- $\ (2/3,1/3)$ - כלומר, דן בוחר בכדורגל בהסתברות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2/3} ובאופרה בהסתברות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1/3} ודנה בוחרת הפוך. באופן זה, ללא תלות בבחירה של ה"שחקן" השני, הם יכולים להבטיח לעצמם תוחלת רווח של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 4/3} .

הוכחת המשפט

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

משפט נקודת השבת קובע כי לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f:S\rightarrow S} רציפה ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S\subset\mathbb{R}^n} קבוצה לא ריקה, קומפקטית וקמורה, יש ל־הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f} נקודת שבת.

נניח כי נתון המשחק הבא: במשחק יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} שחקנים הממוספרים ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i} כאשר $\ i$ נע מ-1 עד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n} , ולכל אחד מהם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m_i} אסטרטגיות.

כעת, נסתכל על הקבוצה של כל האסטרטגיות המעורבות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S_{m_1}\times S_{m_2}\times ...\times S_{m_n}} .

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

נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^i_j} - המשקל של הפעולה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ j} בהתפלגות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^i} .

נגדיר את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d^i_j = u_i(j,x^{-i}) - u_i(x^i,x^{-i})} להיות ההפרש בין ערך פונקציות התועלת של השחקן ה- $\ i$

בבחירת הפעולה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ j} במקום האסטרטגיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ x^i} (כלומר, הרווח שמתקבל מהמעבר לאסטרטגיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ j} ).

כמו כן, נגדיר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ max^i_j = max(d^i_j, 0)} .

כעת, נגדיר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ k^i_j=\frac {x^i_j + max^i_j} {1+\sum_{j=1}^n max^i_j}} נשים לב כי קיבלנו פונקציה רציפה ממרחב האסטרטגיות לעצמו.

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

נטען כי בנקודת השבת שקיבלנו מתקיים כי לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i, j} , מתקיים כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ d^i_j \le 0} .

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

ואכן, טענה זו מתקיימת, נוכיח בשלילה. נניח שקיימים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ i, j} כך ש- $\ d_{j}^{i}>0$ ואז נקבל סתירה לכך שזו נקודת שבת.