תכנון מנגנונים אלגוריתמי
תכנון מנגנונים אלגוריתמי הוא תחום מחקר בתורת המשחקים האלגוריתמית, החוקר מושגי פתרון עבור משחקים שבהם:
- ישנו מתכנן למשחק, שבונה את מבנה המשחק וכלליו
- המתכנן מעוניין בתוצאת המשחק
משחקים אלה מוגדרים כ"מנגנונים", ותכנונם נחקר כבר שנים רבות, ואף זכה לפרס נובל לכלכלה. תכנון המנגנונים האלגוריתמי בא לבדוק כיצד והאם ניתן לתכנן משחקים כאלו בכלים החישוביים העומדים לרשותנו. בעיות שימושיות רבות ניתנות למידול כמנגנונים (למשל מכרזים מקוונים ופרסום מקוון) ועל כן תכנון מגנונים אלגוריתמי הוא כלי שימושי בתחומים אלה.
מאפייני התחום
תכנון מנגנונים קלאסי
תכנון מנגנונים קלאסי הוא תחום בכלכלה המנתח מצבים כלכליים בהם גורם מעוניין להקצות משאבים בין שחקנים אסטרטגיים כך שתועלת החברתית תהיה מקסימלית. תחום זה נחקר שנים רבות ואף הגיע לתוצאות, אך במנותק מהשימוש המעשי, כלומר מהיכולת לממש למעשה את העקרונות במנגנונים קיימים. את האספקט הזה משלים תכנון המנגנונים האלגוריתמי
עקרונות תכנון מנגנונים אלגוריתמי
תכנון מנגנונים אלגוריתמי שונה מתכנון מנגנונים כלכלי קלאסי בכמה היבטים:
- תכנון מנגנונים אלגוריתמי מנתח משחקים מנקודת המבט של מדעי המחשב, ומשתמש בנושגי הניתוח החישוביים. כך למשל, תכנון מנגנונים אלגורתימי מנתח את מן הריצה הגרוע ביותר ואת יחס הקירוב של מנגנון, בניגוד לתכנון מנגנונים קלאסי שעושה שימוש רב בהנחות הסתברותיות על התנהגות הסוכנים.
- בתכנון מנגנונים אלגוריתמי מייחסים חשיבות מרכזית לשיקולי יעילות ביצוע האלגוריתם וסיבוכיותו, שיקולים מרכזיים בעולם התכנון האלגוריתמי אך זרים לעולם תכנון המנגנונים הקלאסי. כך, מנגנון שלא ניתן יהיה ליישמו בזמן פולינומי לא ייחשב לפתרון בר קיימא. שיקולים כאלה פוסלים לעיתים קרובות מנגנונים קלאסיים נפוצים; כך למשל, מכרז Vickrey-Clarke-Groves, שהוא מנגנון קלאסי נפוץ, יפסל כמנגנון ישים לעיתים מסיבות חישוביות.
שימושים מעשיים
תכנון מנגנונים אלגוריתמי הוא כלי מרכזי בניהול של מכרזים (ובפרט, מכרזים קומבינטורים) במדינות שונות. הדוגמה הטובה ביותר לכך היא ניהול הקצאת תדרים למפעילים סלולריים, מכרזים שנוהלו בשיטות של ניהול מכרזים אלגוריתמי בארצות הברית, בריטניה וניו זילנד.
לקריאה נוספת
- Nisan, Noam; Amir Ronen (2001). "Algorithmic mechanism design". Games and Economic Behavior (35): 166–196. ניתן גם להורדה כאן.
- Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V ., Algorithmic Game Theory. Cambridge University Press, 2007. עותק מקוון, פרקים 9-16.
קישורים חיצוניים
- נועם ניסן, הרצאה על עריכת מנגנונים אלגוריתמית, במסגרת "google TechTalks"