משחק פיקטיבי

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

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

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

  • הערה - בערך זה נקרא "פעולות" לאסטרטגיות במשחק G, כדי להבדיל מאסטרטגיות במשחק החוזר

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

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

שפלי (Shapley)‏[3] מציג משפחה רחבה של משחקים 3x3 שאינם סכום אפס בה אין התכנסות של סדרת תוצאות המשחקים בשיטת בראון, ואף לא תת-גבול שהוא שיווי משקל של המשחק החד-שלבי. משפחת המשחקים מוגדרת על ידי מספר אי-שיוויונות לינאריים באיברי מטריצת המשחק. מאמר מ-1998 מראה שתוצאה זו נכונה ברוב המשחקים שאינם סכום אפס.[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. ^ Lloyd 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", Mathematics of Operations Research" Vol. 23 No. 2, 1998