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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

היסטוריה[עריכת קוד מקור | עריכה]

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

לידתה של תורת המשחקים האלגוריתמית[עריכת קוד מקור | עריכה]

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

תורת המשחקים האלגוריתמית - תוצר טבעי של האינטרנט[עריכת קוד מקור | עריכה]

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

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

תחומי מחקר[עריכת קוד מקור | עריכה]

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

בנוסף לתת-תחומים אלה ניכרות בתחום מספר התחלות חדשות ומבטיחות.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  • 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 (ניתן להורדה כאן)