הצגת המקור של הדף "משפט נאש"

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

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

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

{| border=1
|
|
| colspan=2 align=center bgcolor=yellow | '''דן'''
|-
|
|
| align=center bgcolor=yellow | כדורגל
| align=center bgcolor=yellow | אופרה
|-
| rowspan=2 bgcolor=yellow | '''דנה'''
| bgcolor=yellow | כדורגל
| 1,2
| 0,0
|-
| bgcolor=yellow | אופרה
| 0,0
| 2,1
|}

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

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

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

נניח כי נתון המשחק הבא: במשחק יש <math>\ n</math> שחקנים הממוספרים ב-<math>\ i</math> כאשר <math>\ i</math> נע מ-1 עד <math>\ n</math>, ולכל אחד מהם <math>\ m_i</math> אסטרטגיות.

כעת, נסתכל על הקבוצה של כל האסטרטגיות המעורבות  <math>\ S_{m_1}\times S_{m_2}\times ...\times S_{m_n}</math>.  

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


נסמן   <math>\ x^i_j</math> - המשקל של הפעולה <math>\ j</math> בהתפלגות <math>\ x^i</math>. 

נגדיר את <math>\ d^i_j = u_i(j,x^{-i}) - u_i(x^i,x^{-i})</math> להיות ההפרש בין ערך פונקציות התועלת של השחקן ה-<math>\ i</math> 

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

כמו כן, נגדיר <math>\ max^i_j = max(d^i_j, 0)</math>.


כעת, נגדיר <math>\ k^i_j=\frac {x^i_j + max^i_j} {1+\sum_{j=1}^n max^i_j}</math>  נשים לב כי קיבלנו פונקציה רציפה ממרחב האסטרטגיות לעצמו. 

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


נטען כי בנקודת השבת שקיבלנו מתקיים כי לכל <math>\ i, j</math>, מתקיים כי <math>\ d^i_j \le 0</math>. 

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

ואכן, טענה זו מתקיימת, [[הוכחה בדרך השלילה|נוכיח בשלילה]]. נניח שקיימים <math>\ i, j</math> כך ש-<math>\ d^i_j > 0</math> ואז נקבל סתירה לכך שזו נקודת שבת.

==ראו גם==
* [[תורת המיקוח של נאש]]

[[קטגוריה:משפטים בתורת המשחקים|נאש]]