תורת המשחקים

דניס לופרב

על מה הספר?

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

אילו סוגי משחקים קיימים?

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

מילים מ-ynet.

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