תורת המשחקים

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

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

התפתחות תורת המשחקים

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

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

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

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

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

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

שיטות ומושגים מתורת המשחקים תופסים מקום של כבוד בענפי הכלכלה השונים ובמנהל עסקים ומשמשים גם במדעי חברה אחרים, כמו מדע המדינה ופסיכולוגיה, וכן במשפטים. תורת המשחקים משמשת גם בענפי ביולוגיה שונים, בעיקר בחקר התנהגות ואסטרטגיות אבולוציוניות של יצורים חיים. בשנים האחרונות גובר העניין בתורת המשחקים במדעי המחשב. התפתחות זו קשורה לחשיבותם הגוברת של רשתות מחשבים, ובמיוחד רשת האינטרנט. בציבור הכללי, המודעות הגדלה לתורת המשחקים מתבטאת בחדירה של מושגים הלקוחים מתחום זה, כמו משחק סכום אפס, לשפה המדוברת. תרמו לכך כמה ספרים פופולריים שנכתבו בזמן האחרון, ובמיוחד נפלאות התבונה, ביוגרפיה של המתמטיקאי ג'ון נאש, מחלוצי תורת המשחקים, שעובדה בשנת 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 הנחקרים הם סימטריים. משחקים רגילים של 'פחדן', 'דילמת האסיר', ו'צייד האייל' הם משחקים סימטריים. חוקרים מסוימים יחשיבו משחקים אלו כמשחקים א-סימטריים. אולם מרבית הרווחים למשחקים כגון אלו הם סימטריים.

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

תורת המשחקים בישראל

חתן פרס נובל לכלכלה, פרופסור ישראל אומן

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

רשימת משחקים

שם המשחק	מספר השחקנים	כמות האסטרטגיות לשחקן	מספר הנקודות שיווי משקל נאש של אסטרטגיות טהורות לשחקן	משחק בתורים	משחק מידע מלא	משחק סכום אפס
מלחמת המינים	2	2	2	לא	לא	לא
משחק ה"נדל"	2	כלשהו	1	כן	כן	לא
"צ'יקן"/"שפן"	2	2	2	לא	לא	לא
משחק ה"תיאום"	כלשהו	כלשהו	לפחות 2	לא	לא	לא
תחרות מחירים	2	אינסוף	1	לא	לא	כן
משחק ללא מוצא	2	2	1	לא	לא	לא
משחק הדיקטטור	2	אינסוף	1	לא	לא	כן
הבר ב"אל פארו"	כלשהו	2	0	לא	לא	לא
2/3 מהממוצע	כלשהו	אינסוף	1	לא	לא	כן
פוקר קאהן	2	קשה לחשב	קשה לחשב	כן	לא	כן
זוג או פרט	2	2	0	לא	לא	כן
משחק המיעוט	כלשהו	2	0	לא	לא	כן
משחק ההתמקחות של נאש	2	אינסוף	אינסוף	לא	לא	כן
דילמת האסיר	2	2	1	לא	לא	לא
אבן נייר ומספריים	2	3	0	לא	לא	כן
משחקי תמסורת	כלשהו	כלשהו	כלשהו	כן	לא	לא
דילמת הצייד	2	2	2	לא	לא	לא
משחק האמון	2	אינסוף	1	כן	כן	לא
התראה (אולטימטום)	2	אינסוף	1	כן	כן	לא
משחק המפקח	+2	כלשהי	תלוי משחק	כן	לא	תלוי משחק
משחק הנסיכה והמפלצת	2	אינסוף	0	לא	לא	כן

יישומים של תורת המשחקים

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

מכרזים - מכרז מחיר שני

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

לדוגמה: אם חיים הציע 2 ₪ משה הציע 5 ₪ ודוד הציע 20 ₪, דוד יזכה במכרז ויצטרך לשלם רק 5 ש"ח אף על פי שהוא הציע הרבה יותר.

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

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

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

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

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

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

מיזוגים ורכישות

בשנת 1988 התקיים מכרז להשתלטות על חברת הקמעונאות, Federated, חברת האב של הרשת בלומינגדיילס. במכרז השתתפו שתי חברות - Macy’s ו-Campeau. שתי החברות שהיו מעוניינות במיזוג חברת Federated לתוך החברה שלהן היו צריכות לקנות 50% או יותר ממניות חברת Federated אשר היו מוחזקות בידי פרטים שונים.

הפירוט להלן הוא פישוט של תהליך המיזוג הארוך שהתרחש, שבסופו ניצחה Campeau, אולם זמן מה לאחר הרכישה החברה פשטה את הרגל וכיום Macy’s Inc היא ההמשך של חברת Federated.

מחיר מניית Federated בשוק היה 60$, וזה היה גם מחירה הצפוי של מניית החברה לאחר רכישתה בידי אחת החברות המתחרות.

Macy’s הציעה הצעת רכישה של 70$ למנייה, בתנאי שיקבלו יותר מ-50% מהמניות.

Campeau לעומת זאת, הציעה 74$ למנייה, ללא תנאי מקדים. אם יותר מ-50% מהמניות היו מוצעות למכירה, Campeau הייתה משלמת, לכל מניה, $74-14*(x\%-50\%)/100\%$ כש%X הוא אחוז המניות הנמכרות. כלומר, אם 100% מהמניות היו מוצעות למכירה, Campeau הייתה משלמת רק 67$ למניה.

חברת Campeau עשתה שימוש באסטרטגיות שולטות כדי להבטיח את השתלטות על Federated תוך כדי תשלום נמוך יותר.

הסבר האסטרטגיה השולטת:

לכל המוכרים היה עדיף למכור את המניות שלהם לCampeau משום שהם הציעו מחיר גבוה יותר למניה. אם 50% מהמניות כבר הובטחו לCampeau להצעה של Macy’s לא הייתה משמעות, משום שהצעה של מעל 50% מהמניות למכירה תמורת 70$ לא הייתה אפשרית, במצב זה מוכרי המניות היו מעדיפים למכור את מניותיהם לCampeau ברווח נמוך יותר, על פני הישארות עם מניות בשווי של 60$.

ניתן לקרוא פירוט של תהליך המיזוג בלינק הבא: Campeau Corp.’s Acquisition of Federated Department Stores

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

שידוך יציב

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

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

לדוגמה, אם אבי הותאם לבית החולים תל השומר, אף על פי שהוא מעדיף את בית החולים איכילוב על פני בית החולים תל השומר, ומשה הותאם לבית חולים איכילוב, אף על פי שהוא מעדיף את בית החולים תל השומר על בית החולים איכילוב, ובית החולים איכילוב מעדיף את אבי על משה, ואילו בית החולים תל השומר מעדיף את משה על אבי, הרי שההתאמה שתיארנו אינה אופטימלית.

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

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

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

שימוש נוסף של משחק זה הוא בשידוך של תורמי כליות לנזקקים לתרומות.

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

משחק המפקח – אסטרטגיות מעורבות

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

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

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

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

התועלת של הסובייטים מביצוע ניסוי גרעיני שלא התגלה: 1, וביצוע ניסוי שהתגלה: 0

התועלת של האמריקאים מגילוי ניסוי גרעיני: 1, ואי-גילוי של ניסוי שהתבצע: 0

אם הסובייטים לא ביצעו ניסוי כלל, התועלת שלהם היא $1>{\beta }>0$ והתועלת של האמריקאים היא${\alpha }>1$

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

חומר נוסף לגבי ההיסטוריה בנושא ניתן לקרוא באתר של משרד ההגנה האמריקאי

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

ביקורת

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

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

— פרופ' אריאל רובינשטיין, איך תורת המשחקים תפתור את בעיות גוש היורו ותעצור את הגרעין האיראני, מתוך הארץ, 19 באפריל 2013

ראו גם

• תורת המשחקים - מונחים
• למידת חיזוק מרובת סוכנים

לקריאה נוספת

• אבינש דיקסיט ובארי ניילבאף, תורת המשחקים, ידיעות אחרונות, 2005
• ויליאם פאונדסטון, דילמת האסיר, זמורה ביתן, 2000
• חיים שפירא, שיחות על תורת המשחקים, כנרת, 2008
• ישראל אומן, שמואל זמיר ויאיר טאומן, תורת המשחקים, האוניברסיטה הפתוחה, 1981
• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, מאגנס, 2008. 9789650614737 ISBN.
• אביעד חפץ, חשיבה אסטרטגית: תורת המשחקים ושימושיה בכלכלה וניהול, האוניברסיטה הפתוחה, 2008
• אברהם דיסקין, החיים כמשחק - הסיפור הלא־מתמטי של תורת המשחקים, גיבוריה ומשמעותה, כנרת זמורה דביר, 2021

קישורים חיצוניים

• אריאל רובינשטיין, דילמה לוקה בחסר, הארץ
• יגאל מילכטייך, משחקים, גליליאו 8, פברואר 1995.
• ישראל אומן, תורת המשחקים קורס מצולם של האוניברסיטה העברית
• פרופ' ישראל אומן על יישום תורת המשחקים בזירה הסביבתית, כתב עת 'אקולוגיה וסביבה'
• שיחה עם ישראל אומן, ‏תורת המשחקים משחק?, מחשבות 29, פברואר 1970, עמ' 9–17
• תורת המשחקים, באתר הספרייה הווירטואלית של מטח
• תורת המשחקים, באתר אנציקלופדיה למתמטיקה (באנגלית)
• Gabe Zichermann: How games make kids smarter – הרצאה מאתר TED אודות ההשפעה של משחוק על למידה ואינטליגנציה - העתיד המהנה.
• תורת המשחקים ויישומיה במשפט, ד"ר עדי אייל, סרטון באתר יוטיוב
• תורת המשחקים, באתר MathWorld (באנגלית)
• תורת המשחקים, באתר אנציקלופדיה בריטניקה (באנגלית)
• תורת המשחקים, דף שער בספרייה הלאומית