משתמש:דני י'/טיוטה

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

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

נתאר שיטה שמיועדת לשפר תוצאות משחק G מעבר לתוצאות שמתקבלות כשמשוחקת וקטור פעולות ${\vec {A}}^{(0)}$ . חזרה על 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) מציגה הוכחה שמשחק פיקטיבי לפי האסטרטגיה המקורית של בראון מקרבת את ערך המשחק. האם מכאן נובעת התכנסות ${\vec {\sigma }}^{(t)}$ לווטקור פעולות אופטימאליות? המשפט מתיחס רק למשחקים שני שחקנים סכום 0.

שייפלי 1963

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

מקורות

</refrerences>