מחיר היציבות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Gnome-edit-clear.svg ערך זה זקוק לעריכה: הסיבה לכך היא: תרגום ותעתיקים.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.

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

רקע ואבני דרך[עריכת קוד מקור | עריכה]

מחיר היציבות היה לראשונה נושא למחקר בעבודתם של 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