פתרון נאש

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

פתרון נאש

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

$N(S,d)=argmax_{x\in S,d\leq x}(x_{1}-d_{1})(x_{2}-d_{2})$

כאשר, $\,S\subseteq \mathbb {R} ^{2}$ היא קבוצת כל התוצאות האפשריות של המשחק, $d\in S$ היא נקודת אי ההסכמה, והנוסחה לעיל מבטאת את הנקודה היעילה $(x_{1},x_{2})\in S$ שעבורה המלבן שקודקודו השמאלי תחתון הוא d והימני עליון הוא $(x_{1},x_{2})$ הוא בעל שטח מרבי.

אפיון גאומטרי

הגדרת עזר

תהי $S$ קבוצה קמורה וסגורה ב-$\,\mathbb {R} ^{2}$ ותהי $x$ נקודה על השפה של $S$. תומך של $S$ ב- $x$ הוא כל ישר העובר דרך $x$ כך שהקבוצה $S$ נמצאת מצד אחד של הישר.

משפט

לכל משחק מיקוח $(S,d)$ המקיים את ארבעת העקרונות של נאש, הנקודה $y$ מזדהה עם הפתרון של נאש, אם ורק אם היא נקודה יעילה ב- $S$, ויש ישר תומך $l$ של $S$ ב- $y$ כך שהמשולש שקודקודיו הם $y,d$ ונקודת החיתוך של $l$ עם הישר $x_{2}=d_{2}$ הוא משולש שווה-שוקיים, שבסיסו על הישר $x_{2}=d_{2}$.

• במילים פשוטות, אם ניתן לשרטט משולש שווה-שוקיים, שבסיסו הוא הישר האופקי שיוצא מ-$d$ ימינה, קודקודו העליון הוא נקודה יעילה ב-$S$ שיש לה תומך, וקודקודו הימני הוא מפגש התומך עם בסיס המשולש, אזי הקודקוד העליון מזדהה עם הפתרון של נאש.

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

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

ראו גם

• משחק מיקוח
• מונוטוניות (משחק מיקוח)
• פתרון קלעי סמורודינסקי
• מונחים בתורת המשחקים

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, הוצאת הספרים ע"ש י"ל מאגנס, 2008.