משחק פיקטיבי

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

שיטת משחק פיקטיבי של בראון

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

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

האסטרטגיה של בראון

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

ניתוח שיטת בראון

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

רובינסון 1951

רובינסון (Robinson)‏ מציגה הוכחה שמשחק סכום אפס פיקטיבי בין שני שחקנים לפי האסטרטגיה של בראון מקרב את ערך המשחק.

שפלי 1963

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