פרופ' משנה יעקב בביצ'נקו זכה בפרס קירל היוקרתי הניתן לחוקרים צעירים מטעם קרן וולף על מחקרו בתחום תורת המשחקים ובבעיית סיבוכיות התקשורת של שיווי משקל נאש.

סיבוכיות ולמידה של שיווי משקל

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

בהינתן הבשורה המשמחת הזו על לגיטימיות מושג השיווי משקל עולה השאלה: באיזו מהירות יכולים שחקנים ללמוד לשחק שיווי משקל? לאחרונה גילו יעקב בביצ'נקו ואביעד רובינשטיין כי קצב ההתכנסות של תהליכי למידה לשיווי משקל עלול להיות איטי. כל כך איטי, עד שבפועל לא ילמדו השחקנים שיווי משקל לעולם. למשל, במשחק של 100 מקבלי החלטות, הזמן שדרוש בכדי להתכנס לשיווי משקל הוא 100^2 (2 בחזקת 100). התוצאה השלילית הזו תקפה באופן אוניברסלי לגבי כל תהליכי הלמידה האפשריים. בכדי להראות תוצאה שלילית זו, חקרו יעקב ואביעד את בעיית הסיבוכיות תקשורת של שיווי משקל. מחקרם ממשיך אמנם מחקרים אחרים על הקשר ההדוק  והמוכר למדע שנים רבות, בין סיבוכיות תקשורת לבין קצב התכנסות של תהליכי למידה, אך התוצאה שלו היא פורצת דרך.

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

עוד על המחקר ניתן לקרוא במגזין קוונטה

ברכות ליעקב על הזכיה המרגשת.