תורת המשחקים האלגוריתמית

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

שורשים

ג'ון פון נוימן, מתמטיקאי ממוצא יהודי-הונגרי שהיגר לארצות הברית, נחשב כאבי תורת המשחקים. בשנת 1928 פרסם פון נוימן מאמר ובו הוכחה למשפט המינימקס. בשנת 1944 פרסם, יחד עם אוסקר מורגנשטרן, את הספר Theory of Games and Economic Behavior, בו נולדה תורת המשחקים כתחום מדעי עצמאי. בשנת 1946 פרסם פון נוימן את טיוטת המאמר בו הציג את EDVAC ושבו הוצגה הארכיטקטורה המכונה ארכיטקטורת פון נוימן העומדת בבסיסם של מחשבים מודרניים רבים. פון נוימן הוא גם מראשוני החישוביות המודרנית. הופעת האינטרנט בסוף המאה העשרים סיפקה את התמריץ, וכך נולדה התורה שמשלבת בין תורת המשחקים והחישוביות - תורת המשחקים האלגוריתמית.

לידתה של תורת המשחקים האלגוריתמית

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

אמרה ידועה של חוקר הרשתות סקוט שנקר היא כי "האינטרנט הוא שיווי משקל, כל שעלינו לעשות הוא למצוא את המשחק" ("The internet is an equilibrium we just have to identify the game", ). תורת המשחקים מתמקדת בחיפוש שיווי משקל מסוגים שונים (למשל שיווי משקל נאש) למצבי מציאות שונים הממודלים כמשחקים. האינטרנט בפרט הוא תחום שבו ישנה חשיבות רבה למציאת שיווי משקל. זוהי זירה שאינה נשלטת באופן אבסולוטי בידי יחיד (או מעטים) אלא מנוהלת מכח המשתתפים בה. מכיוון שכך, מציאת שיווי משקל תאפשר מציאת פתרונות יציבים לצרכים שונים, החל מאיזון עומסים בין שרתים או בתעבורת מידע, דרך פרוטוקולים שמאפשרים תקשורת אמינה בין שחקנים שאינם מכירים זה את זה ואינם מחויבים לדבר, וכלה ביצירת מערכות מסחר אלקטרוניות על הרשת. תורת המשחקים מטבעה נותנת כלים חזקים למציאת שיווי המשקל למשחק נתון. מידול נכון של מצב באינטרנט כמשחק, יאפשר שימוש בכלים אלה על מנת להגיע לפתרון. או במילותיו של שנקר - נשאר רק "למצוא את המשחק".

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

תחומי מחקר

שלושה ענפים מרכזיים מתוך המחקר בתחום הם:

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

קישורים חיצוניים

• יסודות תורת המשחקים האלגוריתמית – הרצאה ב-12 דקות של פרופסור תמי תמיר

• John von Neumann, Oskar Morgenstern (1944) Theory of Games and Economic Behavior. Princeton Univ. Press. 2007 edition: ISBN 978-0-691-13061-3
• "First Draft of a Report on the EDVAC" (PDF) by John von Neumann, Contract No.W-670-ORD-4926, between the United States Army Ordnance Department and the University of Pennsylvania. Moore School of Electrical Engineering, University of Pennsylvania, June 30, 1945.
• Vijay V. Vazirani; Nisan, Noam; Tim Roughgarden; Éva Tardos (2007). Algorithmic Game Theory. Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0 (ניתן להורדה כאן)