תורת המשחקים
סוגי משחקים

תורת המשחקים חוקרת את המשחקים במונחים מתמטיים מוגדרים.
המשחק מכיל מספר שחקנים, סדרת פעולות (או אסטרטגיות) אפשריות לשחקנים אלו ומִפְרט של הרווחים לכל אחד מצירופי התכסיסים. ישנן שתי דרכים להציג את המשחקים הנפוצים בספרות:
| משחק בסגנון הרגיל>  | משחק בסגנון הרגיל> שחקן ב' בוחר ימין | משחק בסגנון הרגיל> שחקן ב' בוחר שמאל |
| --- | --- | --- |
| שחקן א' בוחר למעלה | -1, -1 | 4, 3 |
| שחקן א' בוחר למטה | 3, 4 | 0, 0 |
המשחק הרגיל, הנורמלי (או האסטרטגי) הוא טבלה אשר מראה לשחקנים את התכסיסים ואת הרווח (ראו דוגמה). יש שני שחקנים: האחד בוחר בשורה והשני בעמודה. לכל אחד מהשחקנים יש שתי אסטרטגיות, אשר מפורטות במספר השורות ובמספר העמודות. הרווחים מצוינים בפנים. הספרה הראשונה היא הרווח של שחקן השורה (בדוגמה שלנו הוא שחקן אחד), המספר השני הוא הרווח של שחקן העמודה (בדוגמה שלנו – השחקן השני). אם שחקן א' נוקט בצעד למעלה ושחקן ב' שמאלה, התוצאה שחקן א' מקבל 4, ושחקן ב' מקבל 3.
במשחק בצורה אסטרטגית (תכסיסית) (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).
במשחקים בצורה רחבה בהם העבר גלוי, משפט קון (Kuhn) (הידוע גם כמשפט צרמלו, אף שייחוסו למתמטיקאי צרמלו בטעות יסודו) מבטיח קיום שווי משקל באסטרטגיות טהורות. אלגוריתם הקרוי אינדוקציה לאחור (שעץ מינימקס הוא מקרה פרטי שלו) מאפשר למצוא שווי משקל כזה שהוא אף משוכלל (subgame perfect), במובן שאינו כולל פעולות שאינן סבירות בעת שהן מוצאות אל הפועל. למשל, בשווי משקל משוכלל שחקן אינו מאיים בנקיטת פעולה שתפגע גם בו עצמו. שכלול היא אחת מכמה דרכים "לעדן" את מושג השווי משקל של נאש, כלומר, להוציא מגדר המותר שוויי משקל הנראים כבלתי סבירים.
משחק שיתופי מתאפיין בכך שהשחקנים יכולים לתאם את מהלכיהם באופן מחייב, כך שאף שחקן לא יוכל לסטות מדרך הפעולה עליה הוחלט. שיתוף הפעולה מבטיח תוצאה יעילה, וזאת בניגוד למצב במשחקים לא שיתופיים (כמודגם בדילמת האסיר). את פירות שיתוף הפעולה בין השחקנים ניתן בדרך כלל לחלק באופנים שונים. מוכר וקונה, למשל, יכולים להסכים על מחיר גבוה או נמוך. חלקם של כל שחקן ושל כל קבוצת שחקנים (הקרויה, בהקשר זה, קואליציה) תלויים במה שיכלו להשיג לו בחרו לפרוש מן הכלל ולפעול לבדם – דבר הקובע את כוח המיקוח שלהם. תורת המשחקים השיתופית מציעה מגוון של מושגי פתרון, כמו ערך שפלי והליבה, הקובעים לכל משחק שיתופי תוצאה יעילה אחת או יותר, באופן המשקף דרישות מסוימות, כמו יחס שוויוני לכל השחקנים. אלגוריתמים שמקורם בתורה זו משמשים בפתרון בעיות מעשיות של התאמה. בבעיות סבוכות, כמו יצירת התאמה בין תורמי כליות לבין חולים הזקוקים להשתלה, הם עשויים להביא לתוצאות יעילות יותר מפתרונות מסורתיים.
במשחק בייסיאני לשחקן לא ידוע במדויק אוסף הפעולות האפשריות של השחקנים האחרים והתועלת עבורן. במקום זאת, השחקן יודע כי שחקן אחר יכול להיות אחד מכמה סוגים, שלכל אחד מהם פעולות אפשריות ופונקציית תועלת, וסוג השחקן נבחר בהתפלגות מסוימת. משחק בייסיאני הוא דרך טובה למדל משחקים בהם יש אלמנט של מזל, כמו פוקר ושש בש.
בתורת המשחקים האבולוציונית בחירה רציונלית של פעולות מוחלפת בתהליך ברירה (סלקציה), המעניק יתרון לפרטים המיטיבים לפעול. חלקם של אלו באוכלוסיית השחקנים עולה, בעוד חלקם של שחקנים המיטיבים פחות להגיב לפעולות השחקנים האחרים – יורד. אסטרטגיה נקראת יציבה־אבולוציונית אם באוכלוסייה בה הכול משחקים לפיה – שום אסטרטגיה חלופית אינה יכולה להתפשט. תורת המשחקים האבולוציונית מתאימה לתיאור משחקים בין בעלי חיים או צמחים, אשר האסטרטגיות שלהם, הנקבעות באופן גנטי, קובעות את כשירותו של הפרט, כלומר, את מספר ואיכות הצאצאים שיעמיד בימי חייו. על־פי נקודת השקפה אחת, שריצ'רד דוקינס הוא מדובריה הבולטים, הגנים הם השחקנים האמיתיים במשחק, בעוד היצורים החיים אינם אלא כלי להפצת הגנים. בחברה האנושית, מקבילים לגנים ה"ממים" (memes), שהם רעיונות, אופנות, צורות חשיבה וכיוצא בזה, המתחרים אלו באלו והמופצים בדרך של חיקוי.