מחיר היציבות

מחיר היציבות הוא מונח מתורת המשחקים.

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

רקע ואבני דרך

מחיר היציבות היה לראשונה נושא למחקר בעבודתם של A. Schulzan ו- N. Moses וזכה להתייחסות גם במחקרם של E. Anshelevich ועמיתיו. הם הראו כי עבור גרפים מכוונים בהם קיים שווי משקל נאש באסטרטגיה טהורה מחיר היציבות הוא לכל היותר המספר ההרמוני ה-$n$. עבור גרפים לא מכוונים עם מקור אחד ושני שחקנים E. Anshelevich ועמיתיו הציגו חסם הדוק למחיר היציבות של $4/3$. Jian li הוכיח במאמרו שעבור גרף לא מכוון עם יעד ברור אליו צריכים להגיע כל השחקנים מחיר היציבות של Shapely network design game חסום אסימפטוטית על ידי $logn/loglogn$ כאשר $n$ הוא מספר השחקנים.

שימושים

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

החשיבות

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

לקריאה נוספת

• Algorithmic game theory By Noam Nisan
• The price of stability in selfish scheduling games by Lucas Agussurja and Hoong Chuin Lau
• An $O(logn/loglogn)$ upper bound on the price of stability for undirected Shapely network design games by Jian Li