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

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

שורשים

ג'ון פון נוימן, מתמטיקאי ממוצא יהודי-הונגרי שהיגר לארצות הברית, נחשב כאבי תורת המשחקים. בשנת 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 (ניתן להורדה כאן)