תורת המשחקים

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

[עריכה] סוגי משחקים

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

משחק בסגנון הרגיל
	שחקן ב' בוחר ימין	שחקן ב' בוחר שמאל
שחקן א' בוחר למעלה	-1, -1	4, 3
שחקן א' בוחר למטה	3, 4	0, 0

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

התשלומים לשחקן 1 (תשלום שמאלי) ולשחקן 2 (תשלום ימני) במשחק אבן נייר ומספריים

במשחק בצורה אסטרטגית (תכסיסית) (strategic, or normal, form game) השחקנים בוחרים את פעולותיהם בעת ובעונה אחת, מבלי לדעת כיצד בחרו האחרים. במשחק עם שני שחקנים, ניתן לבטא את תוצאת המשחק עבור כל אחד מהם – במונחים של רווח כספי או תועלת מופשטת – על ידי מטריצת תשלומים, ששורותיה מתאימות לפעולות האפשריות של שחקן 1 ועמודותיה לפעולות של שחקן 2. במשחק הילדים אבן נייר ומספריים, למשל, התשלום לשחקן המנצח הוא 1, למפסיד 1-, ובמקרה של תיקו שני השחקנים מקבלים 0. אבן נייר ומספריים הוא דוגמה למשחק סכום אפס (Zero-sum game): הרווח הכולל של השחקנים הוא אפס, כך שרווח של אחד בהכרח בא על חשבונו של שחקן אחר. משחקים רבים בכלכלה ובפוליטיקה אינם משחקי סכום אפס, משום שתוצאות מסוימות פירושן רווח לכל המשתתפים (מצבי "win-win") ואחרות פירושן הפסד לכול. משחקים כאלו מותירים פתח לשיתוף פעולה בין השחקנים, אך זה עשוי שלא להתממש אם הוא אינו עולה בקנה אחד עם האינטרסים האנוכיים של חלק מהשחקנים (כמו, למשל, בדילמת האסיר).

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

האסטרטגיה (תכסיס) של כל שחקן במשחק בצורה אסטרטגית יכולה להיות בחירה באחת מדרכי הפעולה הפתוחות בפניו (אסטרטגיה טהורה) או הגרלה, בה לכל אחת מהפעולות יש הסתברות מסוימת להיבחר (אסטרטגיה מעורבת). האסטרטגיות של השחקנים מהוות שווי משקל נאש אם כל אחד מהם בוחר בתשובה טובה ביותר לאסטרטגיות של השחקנים האחרים, כלומר, הוא אינו יכול להשיג תוצאה טובה יותר עבורו באופן חד־צדדי, על ידי בחירה באסטרטגיה אחרת כלשהי. קיום שווי משקל באסטרטגיות מעורבות מובטח על־ידי משפט נאש; שווי משקל באסטרטגיות טהורות לא תמיד קיים. במשחק היונה–נץ (הנקרא גם משחק ה"שפן", Chicken) ובקרב המינים, למשל, קיימים שני שוויי משקל טהורים ושווי משקל מעורב אחד, בעוד שבאבן נייר ומספריים קיים רק שווי משקל מעורב, בו כל שחקן בוחר באקראי, בהסתברות שווה, אחת משלושת הפעולות.

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

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

בתמונת המשחק פה, ישנם שני שחקנים. שחקן 1 זז ראשון ובוחר או ב- F או ב- U. שחקן 2 רואה את הצעד של שחקן 1 ויכול לבחור או ב- A או ב- R. נניח ושחקן 1 בוחר U ולאחר מכן שחקן 2 בוחר A, אז שחקן 1 מקבל 8 ושחקן 2 מקבל 2.

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

כיתוב תמונה

במשחק בצורה רחבה (extensive form game) השחקנים פועלים בזה אחר זה. סדר השחקנים ואפשרויות הפעולה הפתוחות בפניהן, העשויים להיות תלויים בפעולות השחקנים הקודמים, מתוארים בעץ המשחק. המשחק מסתיים באחד מעלי העץ, בו רשומים התשלומים המתאימים של השחקנים. כל קדקוד אחר בעץ מייצג צומת החלטה של אחד השחקנים, והענפים המסתעפים ממנו מייצגים את הפעולות האפשריות עבורו. במשחקים מסוימים, כמו שחמט או משחק מרבה־הרגליים ("נדל", centipede game), פעולות השחקנים גלויות וידועות לבאים אחריהם. באחרים, הקרויים משחקים עם ידיעה לא שלמה (imperfect information games), חלק מהשחקנים אינם יודעים בוודאות כיצד פעלו קודמיהם. משחקים בהם האי־ודאות ביחס לעבר קשורה למאורעות חיצוניים, כמו פוקר ומשחקי קלפים אחרים בהם סדר הקלפים בחפיסה אינו ידוע, נקראים משחקים עם ידיעה לא מלאה (incomplete information games).

בשווי משקל של משחק מרבה־הרגליים, שחקן 1 יוצא מיד (י'), ואינו ממשיך (מ'), כך שתשלומי השווי משקל הם 4 לשחקן 1 ו-1 לשחקן 2

במשחקים בצורה רחבה בהם העבר גלוי, משפט קון (Kuhn) (הידוע גם כמשפט צרמלו, אף שייחוסו למתמטיקאי צרמלו בטעות יסודו) מבטיח קיום שווי משקל באסטרטגיות טהורות. אלגוריתם הקרוי אינדוקציה לאחור (שעץ מינמקס הוא מקרה פרטי שלו) מאפשר למצוא שווי משקל כזה שהוא אף משוכלל (subgame perfect), במובן שאינו כולל פעולות שאינן סבירות בעת שהן מוצאות אל הפועל. למשל, בשווי משקל משוכלל שחקן אינו מאיים בנקיטת פעולה שתפגע גם בו עצמו. שכלול היא אחת מכמה דרכים "לעדן" את מושג השווי משקל של נאש, כלומר, להוציא מגדר המותר שוויי משקל הנראים כבלתי סבירים.

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

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

[עריכה] משחק סימטרי ומשחק א-סימטרי

משחק א-סימטרי
F	E
0, 0	1, 2	E
1, 2	0, 0	F

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

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

[עריכה] התפתחות תורת המשחקים

מאמר של המתמטיקאי הגרמני ארנסט צרמלו (Zermelo) שפורסם בשנת 1913 ומאמרים של המתמטיקאי הצרפתי אמיל בורל (Borel) מהשנים 1921–1927 הם מבשריה של תורת המשחקים. מאמרים אלו מתייחסים לדוגמאות של שחמט ופוקר, אך עיקר עניינם הוא שאלות כלליות יותר, עקרוניות, העולות ממשחקים אלו. בשנת 1928 פירסם ג'ון פון נוימן מאמר ובו הוכחה למשפט המינמקס, העוסק במשחק סכום אפס לשני שחקנים, והוא ממשפטי היסוד של תורת המשחקים.

ראשיתה של תורת המשחקים כתחום עצמאי היא ספרם של פון נוימן ואוסקר מורגנשטרן, "תורת המשחקים וההתנהגות הכלכלית" (Theory of Games and Economic Behavior), שיצא לאור בשנת 1944.

בשנים 1953-1950 פירסם ג'ון נאש ארבעה מאמרים העוסקים במשחקים שיתופיים ולא שיתופיים. בין השאר הוכיח במאמר מ־1951 קיומו של שיווי משקל במשחקים לא שיתופיים, הקרוי כיום על שמו, שווי משקל נאש. עבודתו של נאש, שנקטעה למשך שנים רבות בעטייה של מחלת הסכיזופרניה, הביאה לזכייתו בפרס נובל לכלכלה בשנת 1994. הפרס הוענק במשותף לנאש, ג'ון הרסני (Harsanyi) וריינהרד סלטן (Selten) על עבודתם החלוצית בתחום תורת המשחקים הלא שיתופית.

בעקבות עבודתו של נאש הציגו מריל פלאד (Flood) ומלווין דרשר (Dersher) מ"מכון ראנד", בשנת 1950, את הבעיה הידועה בשם דילמת האסיר.

ב-1982 פרסם ג'ון מיינרד סמית' (John Maynard Smith) את הספר "אבולוציה ותורת המשחקים" (Evolution and the Theory of Games), שקידם מאוד את השימוש בתורת המשחקים האבולוציונית בביולוגיה.

פרס נובל שני בכלכלה על עבודה מתחום תורת המשחקים הוענק בשנת 2005 במשותף לישראל אומן ותומס שלינג (Schelling).

[עריכה] תורת המשחקים בישראל

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