המחיר ה"טהור" של האנרכיה מתייחס רק לשיווי משקל נאש טהור, דהיינו שיווי משקל בו כל השחקנים נוקטים באסטרטגיות טהורות בלבד, ולא באסטרטגיות מעורבות או רנדומיות. יש לשים לב כי שיווי משקל מעין זה לא תמיד קיים.
את המונח הציע חוקר מדעי המחשב כריסטוס פאפאדימיטריו. מחיר האנרכיה מהווה מדד חדש לאיכות שיווי משקל.
הגדרה מתמטית.
בהינתן משחק formula_1, ננסה למקסם את התועלת החברתית, דהיינו את התועלת של כלל המשתתפים במשחק. יש פונקציות רבות, המתארות את התועלת החברתית, מביניהן:
פונקציה "תועלתנית"
פונקציית שיויון-זכויות
האופטימום החברתי ממקסם את formula_4 על-פני כל פרופילי הפעולה formula_5.
דוגמה: מחיר האנרכיה בעיית תזמון עבודות.
כל שחקן בוחר מכונה עליה יריץ את עבודתו כך שהיא תבוצע בצורה המהירה ביותר. ביצוע אוסף בחירות השחקנים, כאשר בחירתם בוצעה לפי השיקול הנ"ל, יגרום לכך שכל שחקן ימתין לסיום עבודתו משך זמן ארוך יותר לעומת המצב בו כל שחקן היה בוחר את המכונה כך שתבצע את עבודתו בזמן בינוני (לא מהר ולא לאט מדי).
ביטוי מתמטי לבעיית תזמון העבודות.
ישנן formula_6 עבודות ו-formula_7 מכונות. לכל מכונה קצב ביצוע עבודה formula_8, ולכל עבודה יש משקל formula_9. כל שחקן בוחר מכונה עליה תרוץ עבודתו. פעולה של כל שחקן מסומנת באופן הבא:
formula_10.
נגדיר "עומס" בצורה הבאה:
הרווח של השחקן ה-formula_12-י הוא :formula_13, משמע השלילה של עומס על המכונה, שנבחרה על ידי השחקן הנ"ל.
נגדיר את המחיר באופן הבא: formula_14, ומכאן formula_15. על ידי הגדרה זו של המחיר יהיה ניתן לדון במחירים, שערכם חיובי, במקום להתעסק עם תועלות שליליות. מטרתנו תהיה לשפר את הרווח בצורה שוויונית לכלל השחקנים, וזאת נשיג על ידי מזעור של העומס המקסימלי. העומס המקסימלי
formula_16 נקרא "makespan".
על-מנת לפתור את בעיית תזמון העבודות נגדיר את מחיר האנרכיה PoA להיות היחס בין ה-MS הגדול ביותר עבור כל שיווי משקל נאש לבין ה-MS הקטן ביותר האפשרי. נשים-לב כי mixed PoA ≥ pure PoA שכן כל שיווי משקל נאש טהור הוא גם שיווי משקל נאש מעורב (אי-שוויון זה יכול להיות גם א"ש חזק כאשר formula_17, formula_18, formula_19 וגם formula_20. האסטרטגיות המעורבות formula_21 מניבות makespan ממוצע, שערכו 1.5, בעוד עבור כל אסטרטגיה טהורה formula_22). ראשית, יש להוכיח כי קיים שיווי משקל נאש.
טענה. לכל משחק "תזמון עבודות" קיים לפחות שיווי משקל נאש טהור אחד.
הוכחה. נסמן ב-formula_23 את האופטימום החברתי - פרופיל הפעולה האופטימלי מבחינה חברתית. זה הוא פרופיל פעולה שה-makespan שלו הוא מינמאלי. ייתכן וקיימים מספר פרופילי פעולה שכאלו, שיניבו התפלגויות עומסים שונות, כאשר לכולן יהיה את אותו עומס מקסימלי. מבין כל פרופילי פעולה אלו נבחר את זה שיש לו את העומס המקסימלי השני בגודלו (אחרי העומס המקסימלי שזהה בכל הפרופילים) המנימאלי. כאמור ההגבלה בדרישות לא מחייבת כי יתקבל פרופיל פעולה יחיד גם לאחר רדוקציה זו, ולכן יש להמשיך ולחזור על התהליך עד אשר העומס ה-formula_7-י המקסימלי, הקטן ביותר מבין כל יתר העומסים ה-formula_7 מקסימליים, מניב התפלגות יחידה עד כדי פרמוטציה. עומס זה נקרא גם lexicographic smallest sorted load vector, ונראה כי הוא שיווי משקל נאש טהור.
נניח בשלילה כי העומס הנ"ל אינו שיווי משקל נאש. נניח כי השחקן ה-formula_12-י, בה"כ, יכול לשפר מצבו על ידי שימוש במכונה ה-formula_27-ית במקום במכונה ה-formula_28-ית, משמע העומס על המכונה העמוסה יותר יקטן משום שהשחקן ה-formula_12-י בהכרח השתמש בה לפני ההחלפה במכונה העמוסה פחות (שכן אחרת ההחלפה לא הייתה כרוחה בשיפור), בסתירה למינימליות הלקסיקוגרפית של formula_30. "סוף הוכחה"
טענה. לכל משחק "תזמון עבודות" מחיר האנרכיה הטהור הוא לכל היותר formula_7.
הוכחה. ניתן לחסום מלמעלה את הרווח, המושג עבור כל שיווי משקל נאש מעורב formula_32, ע"י: formula_33.
נסמן פרופיל פעולה של אסטרטגיות טהורות ב-formula_30. על כל פרופיל כזה
מאחר שהביטוי שלעיל נכון לכל פרופיל פעולה של אסטרטגיות טהורות, הוא גם נכון עבור האופטימום חברתי, המקיים, אפוא, את formula_36 וגם את formula_4. "סוף הוכחה"
מחיר האנרכיה בניתוב.
הפרדוקס של ברס.
חשבו על רשת כבישים, בה מספר קבוע של נהגים מעוניין להגיע מנקודת מוצא משותפת לנקודת סיום משותפת; הניחו שכל נהג בוחר את מסלולו בצורה אנוכית, ושהזמן הדרוש להגיע מתחילתה לסופה של דרך תלוי באופן ליניארי במספר הנהגים שבחרו בה.
ניתן להתייחס לבעיה זו כבעיית זרימה בגרף קשיר formula_38, לו קדקוד מקור formula_39 וקודקוד מטרה formula_40, כאשר כל אחת מקשתותיו מהווה דרך בה יכול לבחור כל אחד מהנהגים. המעבר מקודקוד המקור לקודקוד המטרה יהיה בהתאם לבחירות הנהגים. נגדיר את הזרימה בגרף באופן הבא:
1. פונקציית קשת formula_41, המגדירה לכל קשת מספר ממשי אי-שלילי.
2. אוסף פונקציות ליניאריות formula_42, הממפות את כמות הנהגים המשתמשים בקשת לקיבולת שלה.
3. הרווח החברתי של זרימה נתונה formula_43 דרך הגרף מוגדר כ- formula_44.
נתבונן ברשת שבתמונה. אם הדרך המקווקוות לא זמינה אז שיווי משקל נאש מעורב מתקבל כאשר כל אחד מהשחקנים בוחר בקשת העליונה והתחתונה בהסתברות שווה. לשיווי משקל זה יש של 1.5 ולוקח לכל נהג 1.5 יחידות זמן לעבור מ-formula_45 ל-formula_46. על מנת לשפר את הזרימה, המחוקק (גורם חיצוני כלשהו) יכול לקבוע כי הדרך המקווקוות והמהירה זמינה לשימושם של הנהגים. אם המחוקק מאפשר זאת אז שיווי משקל נאש יתקבל רק כאשר כל אחד מהנהגים ישתמש בדרך החדשה, אך במקרה זה העלות החברתית גדלה וערכה 2, כלומר בתסריט זה לכל נהג ייקח 2 יחידות זמן להגיע מ- formula_45 ל-formula_46.
כלומר, באופן פרדוקסלי, מוטב היה לנהגים להתעלם מהדרך המהירה שהתווספה לרשת.
הכללה של בעיית הניתוב.
ניתן להכליל את בעיית הניתוב, המציגה את הפרדוקס של בראס, עבור רשתות תנועה שונות בו"ז.
הגדרה (רשת מוכללת). יהיו formula_49, formula_50 ו-formula_51 כפי שהדרנו אותם לעיל. נניח שברצוננו לנתב את formula_52 דרך כל זוג קודקודים formula_53. "זרימה" formula_54 מוגדרת כהשמה formula_55 של מספר ממשי אי-שלילי לכל "דרך" formula_56 מ-formula_57 ל-formula_58 (קודקודי המקור והמטרה בהתאמה שב- formula_59), תחת הדרישה ש-
זרימה דרך קשת ספציפית בגרף formula_61 מוגדרת כ-:formula_62.
הערה: לשם קיצור נרשום formula_63 בלי formula_64.
הגדרה (שיווי משקל נאש של זרימה). זרימה formula_54 תקרא "שיווי משקל נאש של זרימה" אא"ם formula_66 ו-formula_67 מ-formula_57 ל-formula_58 (דרכים מהמקור למטרה) מתקיים
הערה: הגדרה זו שקולה למה שנאמר על שיווי משקל נאש מעורב במשחקים נורמלים.
הגדרה (רווח תחת תנאי של זרימה).
תהיינה formula_54 ו-formula_72 2 זרימות ב-formula_61 (המתייחסות לאותן קבוצות formula_59 ו-formula_75). "רווח תחת תנאי" של זרימה formula_76 ביחס ל-formula_43 מוגדר כ-:formula_78.
טענה 1. בהינתן שיווי משקל נאש של זרימה formula_43 וזרימה כלשהי formula_76, מתקיים: formula_81.
הוכחה. נניח ש-formula_82. מהגדרה :formula_83. מאחר ש-formula_43 ו-formula_76 מתייחסות לאותן קבוצות formula_86, אז:
מכאן נובע כי בהכרח קיים זוג formula_88 ו-2 דרכים formula_89 מ-formula_57 ל-formula_58 כך ש- formula_92, formula_93, וגם formula_94.
במילים אחרות, הזרימה formula_76 יכולה להשיג רווח נמוך יותר מאשר formula_43 רק בתנאי שישנן 2 דרכים מ-formula_57 ל-formula_58 בעלות מחירים שונים, ובתנאי ש-formula_76 ישנה מספר זרימות שב-formula_43 על ידי שימוש בדרכים זולות יותר במקום שימוש בדרכים יקרות יותר. מצב זה לא אפשרי תחת ההנחה ש- formula_43 הוא שיווי משקל נאש של זרימה. "סוף ההוכחה"
הערה: שימו-לב כי טענה 1 לא מניחה מבנה מסוים של formula_50.
טענה 2. בהינתן 2 מספרים ממשיים formula_103 ו-formula_104 מתקיים formula_105.
הוכחה. זו דרך נוספת לבטא את הא"ש formula_106. "סוף ההוכחה" .
משפט. מחיר האנרכיה הטהור של כל בעיית ניתוב מוכלל formula_107 עם קיבולות ליניאריות, קטן/שווה ל-4/3.
הוכחה. משפט זה שקול לקביעה כי לכל שיווי משקל נאש של זרימה formula_43, formula_109, כאשר formula_76 היא זרימה שונה כלשהי. לפי הגדרה:
על ידי שימוש בטענה 2 נקבל כי:
שכן
נסיק ש-formula_118, ולבסוף על ידי שימוש בטענה 1 הוכח הדרוש. "סוף ההוכחה"
הערה: בהוכחה נעשה שימוש מורחב של ההנחה לפיה הפונקציות ב-formula_50 הן ליניאריות. נוכיח את המשפט גם עבור פונקציות פולינומיות.
משפט. בהינתן בעיית ניתוב מוכללת עם גרף formula_61 וקיבולת פלינומיאלית מדרגה formula_121 גם שאריות אי-שליליות אזי מחיר האנרכיה הטהור קטן/שווה ל- formula_122 .
יש לשים-לב כי מחיר האנרכיה יכול לגדול עם דרגת הפולינום formula_121. בדוגמה בתמונה שלעיל, בה הנחנו זרימה של יחידות זמן, לשיווי משקל נאש של זרימה יש תועלת חברתית שערכה 1, אולם התועלת הטובה ביותר מושגת כאשר formula_124 וכאשר
גודל זה שואף לאפס כאשר formula_121 שואף לאינסוף.
ירושת&quot;ו
חברת גרמופון האמריקאית
ברלינר גרמופון
ברלינר גרמופון או חברת גרמופון האמריקאית (באנגלית: Berliner Gramophone או United States Gramophone Company) הייתה אחת מחלוצות חברות התקליטים שייצרו תקליטים, להבדיל מגלילי פונוגרף.