מחיר האנרכיה

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

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

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

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

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

הגדרה מתמטית

בהינתן משחק $G=(N,A,u)$, ננסה למקסם את התועלת החברתית, דהיינו את התועלת של כלל המשתתפים במשחק. יש פונקציות רבות, המתארות את התועלת החברתית, מביניהן:

פונקציה "תועלתנית"

הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle w(a)=\sum _{i=1}^{N}u_{i}(a)}

פונקציית שיויון-זכויות

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(a) = \min_i u_i(a)}

האופטימום החברתי ממקסם את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(a)} על-פני כל פרופילי הפעולה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in A } .

דוגמה: מחיר האנרכיה בעיית תזמון עבודות

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

ביטוי מתמטי לבעיית תזמון העבודות

ישנן $N$ עבודות ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} מכונות. לכל מכונה קצב ביצוע עבודה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_1,\ldots,s_M>0} , ולכל עבודה יש משקל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_1,\ldots,w_N>0} . כל שחקן בוחר מכונה עליה תרוץ עבודתו. פעולה של כל שחקן מסומנת באופן הבא: הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle A_{i}=\{1,2,\ldots ,M\}} .

נגדיר "עומס" בצורה הבאה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_j(a)=\frac{\sum_{i:a_i=j} w_i}{s_j}} .

הרווח של השחקן ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} -י הוא :הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle u_{i}(a)=-L_{a_{i}}(a)} , משמע השלילה של עומס על המכונה, שנבחרה על ידי השחקן הנ"ל. נגדיר את המחיר באופן הבא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_i=-u_i} , ומכאן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_i(a)=L_{a_i}(a)} . על ידי הגדרה זו של המחיר יהיה ניתן לדון במחירים, שערכם חיובי, במקום להתעסק עם תועלות שליליות. מטרתנו תהיה לשפר את הרווח בצורה שיוויונית לכלל השחקנים, וזאת נשיג על ידי מיזעור של העומס המקסימלי. העומס המקסימלי

הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle {\mbox{MS}}(a)=\max _{j}L_{j}(a)} נקרא "makespan".

על-מנת לפתור את בעיית תזמון העבודות נגדיר את מחיר האנרכיה PoA להיות היחס בין ה-MS הגדול ביותר עבור כל שיווי משקל נאש לבין ה-MS הקטן ביותר האפשרי. נשים-לב כי mixed PoA ≥ pure PoA שכן כל שיווי משקל נאש טהור הוא גם שיווי משקל נאש מעורב (אי-שוויון זה יכול להיות גם א"ש חזק כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N=2} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_1=w_2=1} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M=2} וגם $s_{1}=s_{2}=1$. האסטרטגיות המעורבות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\sigma_1=\sigma_2=(1/2,1/2} מניבות makespan ממוצע, שערכו 1.5, בעוד עבור כל אסטרטגיה טהורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle PoA\leq 4/3} ). ראשית, יש להוכיח כי קיים שיווי משקל נאש.

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

הוכחה. נסמן ב-$a^{*}$ את האופטימום החברתי - פרופיל הפעולה האופטימלי מבחינה חברתית. זה הוא פרופיל פעולה שה-makespan שלו הוא מנימאלי. ייתכן וקיימים מספר פרופילי פעולה שכאלו, שיניבו התפלגויות עומסים שונות, כאשר לכולן יהיה את אותו עומס מקסימלי. מבין כל פרופילי פעולה אלו נבחר את זה שיש לו את העומס המקסימלי השני בגודלו (אחרי העומס המקסימלי שזהה בכל הפרופילים) המנימאלי. כאמור ההגבלה בדרישות לא מחייבת כי יתקבל פרופיל פעולה יחיד גם לאחר רדוקציה זו, ולכן יש להמשיך ולחזור על התהליך עד אשר העומס ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} -י המקסימלי,הקטן ביותר מבין כל יתר העומסים ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} מקסימליים, מניב התפלגות יחידה עד כדי פרמוטציה. עומס זה נקרא גם lexicographic smallest sorted load vector, ונראה כי הוא שיווי משקל נאש טהור. נניח בשלילה כי העומס הנ"ל אינו שיווי משקל נאש. נניח כי השחקן ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} -י, בה"כ, יכול לשפר מצבו על ידי שימוש במכונה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -ית במקום במכונה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} -ית, משמע העומס על המכונה העמוסה יותר יקטן משום שהשחקן ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} -י בהכרח השתמש בה לפני ההחלפה במכונה העמוסה פחות (שכן אחרת ההחלפה לא הייתה כרוחה בשיפור), בסתירה למינימאליות הלקסיקוגרפית של $a$. סוף הוכחה

טענה. לכל משחק "תזמון עבודות" מחיר האנרכיה הטהור הוא לכל היותר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} .

הוכחה. ניתן לחסום מלמעלה את הרווח, המושג עבור כל שיווי משקל נאש מעורב $\sigma$, ע"י: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(\sigma) \leq \frac{\sum_i{w_i}}{\max_j{s_j}}} .

נסמן פרופיל פעולה של אסטרטגיות טהורות ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} . על כל פרופיל כזה

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(a) \geq \frac{\sum_i{w_i}}{\sum_j{s_j}} \geq \frac{\sum_i{w_i}}{M \cdot \max_j{s_j}}} .

מאחר שהביטוי שלעיל נכון לכל פרופיל פעולה של אסטרטגיות טהורות, הוא גם נכון עבור האופטימום חברתי, המקיים, אפוא, את $w(\sigma )$ וגם את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(a)} . סוף הוכחה

מחיר האנרכיה בניתוב

הפרדוקס של ברס

ערך מורחב – פרדוקס ברס

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

ניתן להתייחס לבעיה זו כבעיית זרימה בגרף קשיר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G=(V,E)} , לו קדקוד מקור $s\in V$ וקודקוד מטרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \in V} , כאשר כל אחת מקשתותיו מהווה דרך בה יכול לבחור כל אחד מהנהגים. המעבר מקודקוד המקור לקודקוד המטרה יהיה בהתאם לבחירות הנהגים. נגדיר את הזרימה בגרף באופן הבא:

1. פונקציית קשת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f: E \mapsto \Re} , המגדירה לכל קשת מספר ממשי אי-שלילי.

2. אוסף פונקציות לינאריות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L = \{ l_e(f_e) = a \cdot f_e + b \; | \; e \in E, \; a \geq 0, \; b \geq 0\}} , הממפות את כמות הנהגים המשתמשים בקשת לקיבולת שלה.

3. הרווח החברתי של זרימה נתונה $f$ דרך הגרף מוגדר כ- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(f) = \sum_e{f_e \cdot l_e(f_e)}} .

שגיאה ביצירת תמונה ממוזערת:

דוגמה לפרדוקס של ברס

נתבונן ברשת שבתמונה. אם הדרך המקווקוות לא זמינה אז שיווי משקל נאש מעורב מתקבל כאשר כל אחד מהשחקנים בוחר בקשת העליונה והתחתונה בהסתברות שווה. לשיווי משקל זה יש עלות חברתית של 1.5 ולוקח לכל נהג 1.5 יחידות זמן לעבור מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} . על מנת לשפר את הזרימה, המחוקק (גורם חיצוני כלשהו) יכול לקבוע כי הדרך המקווקוות והמהירה זמינה לשימושם של הנהגים. אם המחוקק מאפשר זאת אז שיווי משקל נאש יתקבל רק כאשר כל אחד מהנהגים ישתמש בדרך החדשה, אך במקרה זה העלות החברתית גדלה וערכה 2, כלומר בתסריט זה לכל נהג יקח 2 יחידות זמן להגיע מ- $s$ ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} . כלומר, באופן פרדוקסלי, מוטב היה לנהגים להתעלם מהדרך המהירה שהתווספה לרשת.

הכללה של בעיית הניתוב

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

הגדרה (רשת מוכללת). יהיו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G=(V, E)} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} כפי שהדרנו אותם לעיל. נניח שברצוננו לנתב את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R = \{ r_1, r_2, \dots, r_k, \; | \; r_i > 0\}} דרך כל זוג קודקודים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Gamma = \{(s_1,t_1), (s_2,t_2), \dots, (s_k,t_k) \} \subseteq (V \times V)} . זרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{\Gamma, R}} מוגדרת כהשמה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \mapsto \Re} של מספר ממשי אי-שלילי לכל דרך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} מ-$s_{i}$ ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_i} (קודקודי המקור והמטרה בהתאמה שב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Gamma} ), תחת הדרישה ש-

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{p: \, s_i \rightarrow t_i}{f_p} = r_i \; \; \forall (s_i,t_i) \in \Gamma} .

זרימה דרך קשת ספציפית בגרף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} מוגדרת כ-:הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{e,\Gamma, R}=\sum_{p: \, e \in p}{f_p}} .

הערה: לשם קיצור נרשום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_e} בלי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Gamma,R} .

הגדרה (שיווי משקל נאש של זרימה). זרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{\Gamma, R}} תקרא שיווי משקל נאש של זרימה אא"ם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall (s_i, t_i) \in \Gamma} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall p, q} מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_i} (דרכים מהמקור למטרה) מתקיים

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{p}>0 \Rightarrow \sum_{e \in p}{l_e(f_e)} \leq \sum_{e \in q}{l_e(f_e)}} .

הערה: הגדרה זו שקולה למה שנאמר על שיווי משקל נאש מעורב במשחקים נורמלים.

הגדרה (רווח תחת תנאי של זרימה). תהיינה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{\Gamma, R}} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{\Gamma, R}^{*}} 2 זרימות ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} (המתייחסות לאותן קבוצות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Gamma} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} ). רווח תחת תנאי של זרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}} ביחס ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} מוגדר כ-:הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w^{f}(f^{*}) = \sum_{e \in E}{f^{*}_e \cdot l_{e}(f_{e})}} .

טענה 1. בהינתן שיווי משקל נאש של זרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} וזרימה כלשהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}} , מתקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(f) = w^{f}(f) \leq w^{f}(f^{*})} .

הוכחה. נניח ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (w^{f}(f^{*}) < w^{f}(f} . מהגדרה :הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{k} \sum_{p: s_i \rightarrow t_i} f_p^{*} \cdot \sum_{e \in p} l_e(f_e) < \sum_{i=1}^{k} \sum_{p: s_i \rightarrow t_i} f_p \cdot \sum_{e \in p} l_e(f_e)} . מאחר ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}} מתייחסות לאותן קבוצות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Gamma, R} , אז:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{p: s_i \rightarrow t_i}f_p = \sum_{p: s_i \rightarrow t_i} f_p^{*} = r_i \; \; \forall i} .

מכאן נובע כי בהכרח קיים זוג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s_i, t_i)} ו-2 דרכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p, q} מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} ל-$t_{i}$ כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_p^{*} > f_p} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_q^{*} < f_q} , וגם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{e \in p}l_e(f_e) < \sum_{e \in q}l_e(f_e)} .

במילים אחרות, הזרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}} יכולה להשיג רווח נמוך יותר מאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} רק בתנאי שישנן 2 דרכים מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_i} בעלות מחירים שונים, ובתנאי ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}} ישנה מספר זרימות שב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} על ידי שימוש בדרכים זולות יותר במקום שימוש בדרכים יקרות יותר. מצב זה לא אפשרי תחת ההנחה ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} הוא שיווי משקל נאש של זרימה. סוף ההוכחה

הערה: שימו-לב כי טענה 1 לא מניחה מבנה מסוים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} .

טענה 2. בהינתן 2 מספרים ממשיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \cdot y \leq x^2 + y^{2}/4} .

הוכחה. זו דרך נוספת לבטא את הא"ש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x-y/2)^2 \geq 0} . סוף ההוכחה .

משפט. מחיר האנרכיה הטהור של כל בעיית ניתוב מוכלל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (G, L)} עם קיבולות לינאריות, קטן/שווה ל-4/3.

הוכחה. משפט זה שקול לקביעה כי לכל שיווי משקל נאש של זרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w(f) \leq (4/3) \cdot \min_{f^{*}} \{ w(f^{*}) \}} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}} היא זרימה שונה כלשהי. לפי הגדרה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w^{f}(f^{*}) = \sum_{e \in E} f_e^{*}(a_e \cdot f_e + b_e)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle = \sum_{e}(a_{e}f_{e}f_{e}^{*}) + \sum_{e \in E}f_e^{*}b_e.}

על ידי שימוש בטענה 2 נקבל כי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w^{f}(f^{*}) \leq \sum_{e \in E} \left( a_e \cdot \left( (f_e^{*})^2 + (f_e)^{2}/4 \right) \right) + \sum_{e \in E} f_e^{*} \cdot b_e}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle = \left( \sum_{e \in E} a_e(f_e^{*})^2 + f_e^{*}b_e \right) + \sum_{e \in E} a_{e}(f_e)^{2}/4}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \leq w(f^{*}) + \frac{w(f)}{4},}

שכן

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1/4) \cdot w(f) = (1/4) \cdot \sum_{e \in E}f_e(a_{e}f_{e}+b_{e})}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle = (1/4) \cdot \sum_{e \in E}(f_{e})^2 + \underbrace{(1/4) \cdot \sum_{e \in E}f_{e}b_{e}}_{\geq 0}.}

נסיק ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w^{f}(f^{*}) \leq w(f^{*}) + w(f)/4} , ולבסוף על ידי שימוש בטענה 1 הוכח הדרוש. סוף ההוכחה

הערה: בהוכחה נעשה שימוש מורחב של ההנחה לפיה הפונקציות ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} הן לינאריות. נוכיח את המשפט גם עבור פונקציות פולינומיות.

משפט. בהינתן בעיית ניתוב מוכללת עם גרף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} וקיבולת פלינומיאלית מדרגה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} גם שאריות אי-שליליות אזי מחיר האנרכיה הטהור קטן/שווה ל- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d+1} .

יש לשים-לב כי מחיר האנרכיה יכול לגדול עם דרגת הפולינום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} . בדוגמה בתמונה שלעיל, בה הנחנו זרימה של יחידות זמן, לשיווי משקל נאש של זרימה יש תועלת חברתית שערכה 1, אולם התועלת הטובה ביותר מושגת כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x=1-1/{\sqrt{d+1}}} וכאשר

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle w = \left( 1-\frac{1}{\sqrt{d+1}} \right)^d \cdot \left( 1-\frac{1}{\sqrt{d+1}} \right) + 1 \cdot \frac{1}{\sqrt{d+1}}}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle =\left(\left( 1-\frac{1}{\sqrt{d+1}} \right)^{\sqrt{d+1}}\right)^\sqrt{d+1}+\frac{1}{\sqrt{d+1}}}

$\leq e^{-{\sqrt {d+1}}}+{\frac {1}{\sqrt {d+1}}}$.

גודל זה שואף לאפס כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} שואף לאינסוף.