מחיר היציבות

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

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

רקע ואבני דרך

מחיר היציבות נחקר לראשונה בעבודתם של A. Schulzan ו־N. Moses וזכה להתייחסות גם במחקרם של E. Anshelevich ועמיתיו. הם הראו, כי עבור גרפים מכוונים בהם קיים שווי משקל נאש באסטרטגיה טהורה, מחיר היציבות הוא לכל היותר המספר ההרמוני ה-$n$. עבור גרפים לא מכוונים עם מקור אחד ושני שחקנים, E. Anshelevich ועמיתיו הציגו חסם הדוק למחיר היציבות של $4/3$.

ג'יאן לי הוכיח במאמרו שעבור גרף לא מכוון עם יעד ברור אליו צריכים להגיע כל השחקנים, מחיר היציבות של משחקי בניית רשת של שאפלי חסום אסימפטוטית על ידי $O(\log n/\log \log n)$ כאשר $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