משחק פיקטיבי

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

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

שיטת משחק פיקטיבי של בראון[עריכת קוד מקור | עריכה]

נתאר שיטה שמיועדת לשפר תוצאות משחק G מעבר לתוצאות שמתקבלות כשמשוחקת וקטור פעולות \vec A^{(0)} . ב"שיפור" הכוונה לדרישה כלשהי לווקטור פעולות מעורבת. למשל, לשחקן רשע שיפור יכול להיות ווקטור פעולות שלפיו השחקנים האחרים מרוויחים פחות ממה שהם היו מרוויחים לו היו משחקים \vec A^{(0)} , ולמבקר חיצוני שיפור יכול להיות הדרישה שווקטור הפעולות הוא \epsilon -שיווי משקל. חזרה על G כשמתחילים ב- \vec A^{(0)} זאת מערכת עם מצב \vec A^{(t)} המתפתחת הלוך זמן בדיד בהשפעת G - בכל זמן t השחקנים בודקים איך G הגיבה להם בעבר ועל סמך הבחנותיהם מחשבים איזה פעולה לעשות בזמן t. בבמט זה, יש ב- \vec A^{(0)}, \vec A^{(1)}, ... \vec A^{(t)}, t \in N מידע על המבנה של G. אפשר לנסות להשתמש במידע הזאת כדי לשפר את תוצאות המשחק G. אולי לזה התכוון בראון במונח "משחק פיקטיבי" שהוא המציא בתיאור שיטה כזאת עם וקטור אסטרטגיות מסוים.[1] אולי התואר "פיקטיבי" מתייחס למשחקים שמבטאים מצבים במצאיות בהם חזרה על המשחק אינה מעשית, שאז החזרות על המשחק יכולות להתקבל בתור הדמיה ממוחשבת. אע"פ שבראון השתמש בווקטור אסטרטגיות מסוימת, ייתכן שווקטורי אסטרטגיות יותר מורכבים יובילו לאלגוריתמים שיעבדו בתחום יותר רחב של משחקים.

האסטרטגיה של בראון[עריכת קוד מקור | עריכה]

במאמרו בראון מתאר את זה בתור האסטרטגיה של סטטיסטיקאי שבזמן t מעריך את משחק כל שחקן i בתור ההתפלגות \sigma^{(t)}_i של הפעולות שלו בעבר A^{(0)}_i, A^{(1)}_i, ... A^{(t-1)}_i . בזמן t השחקן בוחר \vec A^{(t)} פעולה טהורה המהווה אופטימום לפונקציית הרווח שלו באותו רגע. בראון מציע שכשכל השחקנים משחקים לפי אסטרטגיה זו, \vec \sigma^{(t)}= (\sigma^{(t)}_i)_{i =1}^N מתכנסת לפתרון המשחק. שני פירושים לזה - א' התכנסות \vec \sigma^{(t)} לווקטור פעולות אופטימליות. ב' התכנסות \vec u(\vec \sigma^{(t)}) לערך המשחק.

ניתוח שיטת בראון[עריכת קוד מקור | עריכה]

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

רובינסון 1951[עריכת קוד מקור | עריכה]

רובינסון (בלועזית Robinson)‏[2] מציגה הוכחה שמשחק פיקטיבי לפי האסטרטגיה המקורית של בראון מקרבת את ערך המשחק. האם מכאן נובעת התכנסות \vec \sigma^{(t)} לווטקור פעולות אופטימאליות? המשפט מתייחס רק למשחקים שני שחקנים סכום 0.

שייפלי 1963[עריכת קוד מקור | עריכה]

שייפלי (בלועזית Shapley)‏[3] מציג משפחה רחבה של משחקים 3x3 שאינם סכום 0 בה אין התכנסות של סדרת תוצאות המשחקים בשיטת בראון, ואף לא תת-גבול שהוא שיווי משקל של המשחק החד-שלבי. משפחת המשחקים מוגדרת על ידי מספר אי-שיוויונות לינאריים באיברי מטריצת המשחק. מאמר מ-1998 בא להראות שזה נכון ברוב המשחקים שאינם סכום 0.[4]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ George W. Brown, "Iterative Solution of Games by Fictitious Play", Activity Analysis of Production and Allocation, 1951 John Wiley & Sons
  2. ^ Julia Robinson, "An Iterative Method of Solving a Game", The Annals of Mathematics Vol. 54 No. 2, 1951
  3. ^ Loyd S. Shapley, Some Topics in Two Person Games, Memorandum RM-3672-PR, The RAND Corporation, 1963
  4. ^ Krishna and Sjöström, "On the Convergence of Fictitious Play", Matheamtics of Operations Research" Vol. 23 No. 2, 1998