תורת המשחקים - מונחים

• תורת המשחקים: ענף של המתמטיקה העוסק בבניה וניתוח של מודלים מתמטיים לתיאור מצבים של קונפליקט.

• שחקן: יחידה מגיבה בעלת יכולת תכנון בתורת המשחקים.
  • שחקן וטו: שחקן שכל קואליציה שאינה מכילה אותו, שוויה הוא אפס.
• רווח: שינוי סטטוס של שחקן כך שמצבו מוגדר חיובי יותר.
• הפסד: שינוי סטטוס של שחקן כך שמצבו מוגדר חיובי פחות.
• משחק: התרחשות מתמטית המתארת קונפליקט בין שחקנים, המבוסס על בחירה רציונלית מונחת-רווח של אפשרות מועדפת מבין אפשרויות קיימות על ידי כל אחד מהשחקנים, השתנות ההתרחשות עקב תוצאות בחירות אלו, וקביעת הסטטוס הסופי של השחקנים בהתאם להשתנות.
  • משחק דמוי שחמט: משחק לשני שחקנים שמשחקים לסירוגין כאשר שחקן אחד מתחיל, ובעל ידיעה שלמה.
  • משחק בצורה רחבה: מודל מתמטי לתיאור של משחק n שחקנים, שיכול להכיל ידיעה לא שלמה וצעדי גורל.
  • משחק בצורה תכסיסית (אסטרטגית): מודל מתמטי לתיאור של משחק שבו מתעניינים רק בתוצאות המשחק הנובעות מבחירת השחקנים, מבלי להתעניין בפרטי המשחק עצמו.
  • משחק סכום אפס (Zero-sum game): משחק שבו הרווח הכולל של כל השחקנים הוא אפס, כך שרווח של שחקן אחד בא על חשבון הפסד של שחקן שני.
  • משחק שיתופי: משחק שבו השחקנים יכולים לתקשר ביניהם ולקבל החלטות משותפות.
    • משחק שוק: סוג מיוחד של משחק שיתופי.
    • משחק עץ פורש: סוג מיוחד של משחק שיתופי.
  • משחק בייסיאני משחק בו לשחקן לא ידועות פונקציות התועלת של השחקנים האחרים באופן מדויק, אלא רק כי לכל שחקן אחר יכולה להיות אחת מכמה פונקציות תועלת לפי התפלגות מסוימת.
• דילמת האסיר: דוגמה למשחק חד-שלבי שבו השחקנים מעוניינים לשתף פעולה אך מכיוון שאין לאף אחד מהם דרך לכפות שיתוף פעולה על האחר, בשיווי המשקל היחיד השחקנים אינם משתפים פעולה. דוגמה זו נוצרה בשנת 1950 על ידי מריל פלאד ומלווין דרשר מ"מכון ראנד" בארצות הברית.
• מודל Hotelling: מודל מסביר התנהגות בסביבה מרובת סוחרים/מוצרים ומתאים גם לניתוח מצבים פוליטיים.

מונחים במשחקים לא שיתופיים

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

מונחים במשחקים שיתופיים

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

אם {1,2,3}=N, אז {(2,3),(1)}, {(3),(2),(1)}, {(1,2,3)}, {(3),(1,2)}, {(1,3),(2)} הם המבנים הקואליציוניים האפשריים.

משפטים חשובים

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