מחיר האנרכיה

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

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

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

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

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

הגדרה מתמטית

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

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

$w(a)=\sum _{i=1}^{N}u_{i}(a)$

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

$w(a)=\min _{i}u_{i}(a)$

האופטימום החברתי ממקסם את $w(a)$ על-פני כל פרופילי הפעולה $a\in A$.

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

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

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

ישנן $N$ עבודות ו-$M$ מכונות. לכל מכונה קצב ביצוע עבודה $s_{1},\ldots ,s_{M}>0$, ולכל עבודה יש משקל $w_{1},\ldots ,w_{N}>0$. כל שחקן בוחר מכונה עליה תרוץ עבודתו. פעולה של כל שחקן מסומנת באופן הבא: $A_{i}=\{1,2,\ldots ,M\}$.

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

$L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}$.

הרווח של השחקן ה-$i$-י הוא :$u_{i}(a)=-L_{a_{i}}(a)$, משמע השלילה של עומס על המכונה, שנבחרה על ידי השחקן הנ"ל. נגדיר את המחיר באופן הבא: $c_{i}=-u_{i}$, ומכאן $c_{i}(a)=L_{a_{i}}(a)$. על ידי הגדרה זו של המחיר יהיה ניתן לדון במחירים, שערכם חיובי, במקום להתעסק עם תועלות שליליות. מטרתנו תהיה לשפר את הרווח בצורה שוויונית לכלל השחקנים, וזאת נשיג על ידי מזעור של העומס המקסימלי. העומס המקסימלי

${\mbox{MS}}(a)=\max _{j}L_{j}(a)$ נקרא "makespan".

על-מנת לפתור את בעיית תזמון העבודות נגדיר את מחיר האנרכיה PoA להיות היחס בין ה-MS הגדול ביותר עבור כל שיווי משקל נאש לבין ה-MS הקטן ביותר האפשרי. נשים-לב כי mixed PoA ≥ pure PoA שכן כל שיווי משקל נאש טהור הוא גם שיווי משקל נאש מעורב (אי-שוויון זה יכול להיות גם א"ש חזק כאשר $N=2$, $w_{1}=w_{2}=1$, $M=2$ וגם $s_{1}=s_{2}=1$. האסטרטגיות המעורבות $(\sigma _{1}=\sigma _{2}=(1/2,1/2$ מניבות makespan ממוצע, שערכו 1.5, בעוד עבור כל אסטרטגיה טהורה $PoA\leq 4/3$). ראשית, יש להוכיח כי קיים שיווי משקל נאש.

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

הוכחה. נסמן ב-$a^{*}$ את האופטימום החברתי - פרופיל הפעולה האופטימלי מבחינה חברתית. זה הוא פרופיל פעולה שה-makespan שלו הוא מינמאלי. ייתכן וקיימים מספר פרופילי פעולה שכאלו, שיניבו התפלגויות עומסים שונות, כאשר לכולן יהיה את אותו עומס מקסימלי. מבין כל פרופילי פעולה אלו נבחר את זה שיש לו את העומס המקסימלי השני בגודלו (אחרי העומס המקסימלי שזהה בכל הפרופילים) המנימאלי. כאמור ההגבלה בדרישות לא מחייבת כי יתקבל פרופיל פעולה יחיד גם לאחר רדוקציה זו, ולכן יש להמשיך ולחזור על התהליך עד אשר העומס ה-$M$-י המקסימלי, הקטן ביותר מבין כל יתר העומסים ה-$M$ מקסימליים, מניב התפלגות יחידה עד כדי פרמוטציה. עומס זה נקרא גם lexicographic smallest sorted load vector, ונראה כי הוא שיווי משקל נאש טהור. נניח בשלילה כי העומס הנ"ל אינו שיווי משקל נאש. נניח כי השחקן ה-$i$-י, בה"כ, יכול לשפר מצבו על ידי שימוש במכונה ה-$k$-ית במקום במכונה ה-$j$-ית, משמע העומס על המכונה העמוסה יותר יקטן משום שהשחקן ה-$i$-י בהכרח השתמש בה לפני ההחלפה במכונה העמוסה פחות (שכן אחרת ההחלפה לא הייתה כרוחה בשיפור), בסתירה למינימליות הלקסיקוגרפית של $a$. סוף הוכחה

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

הוכחה. ניתן לחסום מלמעלה את הרווח, המושג עבור כל שיווי משקל נאש מעורב $\sigma$, ע"י: $w(\sigma )\leq {\frac {\sum _{i}{w_{i}}}{\max _{j}{s_{j}}}}$.

נסמן פרופיל פעולה של אסטרטגיות טהורות ב-$a$. על כל פרופיל כזה

$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 )$ וגם את $w(a)$. סוף הוכחה

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

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

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

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

ניתן להתייחס לבעיה זו כבעיית זרימה בגרף קשיר $G=(V,E)$, לו קדקוד מקור $s\in V$ וקודקוד מטרה $t\in V$, כאשר כל אחת מקשתותיו מהווה דרך בה יכול לבחור כל אחד מהנהגים. המעבר מקודקוד המקור לקודקוד המטרה יהיה בהתאם לבחירות הנהגים. נגדיר את הזרימה בגרף באופן הבא:

1. פונקציית קשת $f:E\mapsto \Re$, המגדירה לכל קשת מספר ממשי אי-שלילי.

2. אוסף פונקציות ליניאריות $L=\{l_{e}(f_{e})=a\cdot f_{e}+b\;|\;e\in E,\;a\geq 0,\;b\geq 0\}$, הממפות את כמות הנהגים המשתמשים בקשת לקיבולת שלה.

3. הרווח החברתי של זרימה נתונה $f$ דרך הגרף מוגדר כ- $w(f)=\sum _{e}{f_{e}\cdot l_{e}(f_{e})}$.

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

נתבונן ברשת שבתמונה. אם הדרך המקווקוות לא זמינה אז שיווי משקל נאש מעורב מתקבל כאשר כל אחד מהשחקנים בוחר בקשת העליונה והתחתונה בהסתברות שווה. לשיווי משקל זה יש עלות חברתית של 1.5 ולוקח לכל נהג 1.5 יחידות זמן לעבור מ-$s$ ל-$t$. על מנת לשפר את הזרימה, המחוקק (גורם חיצוני כלשהו) יכול לקבוע כי הדרך המקווקוות והמהירה זמינה לשימושם של הנהגים. אם המחוקק מאפשר זאת אז שיווי משקל נאש יתקבל רק כאשר כל אחד מהנהגים ישתמש בדרך החדשה, אך במקרה זה העלות החברתית גדלה וערכה 2, כלומר בתסריט זה לכל נהג ייקח 2 יחידות זמן להגיע מ- $s$ ל-$t$. כלומר, באופן פרדוקסלי, מוטב היה לנהגים להתעלם מהדרך המהירה שהתווספה לרשת.

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

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

הגדרה (רשת מוכללת). יהיו $G=(V,E)$, $L$ ו-$w$ כפי שהדרנו אותם לעיל. נניח שברצוננו לנתב את $R=\{r_{1},r_{2},\dots ,r_{k},\;|\;r_{i}>0\}$ דרך כל זוג קודקודים $\Gamma =\{(s_{1},t_{1}),(s_{2},t_{2}),\dots ,(s_{k},t_{k})\}\subseteq (V\times V)$. זרימה $f_{\Gamma ,R}$ מוגדרת כהשמה $p\mapsto \Re$ של מספר ממשי אי-שלילי לכל דרך $p$ מ-$s_{i}$ ל-$t_{i}$ (קודקודי המקור והמטרה בהתאמה שב- $\Gamma$), תחת הדרישה ש-

$\sum _{p:\,s_{i}\rightarrow t_{i}}{f_{p}}=r_{i}\;\;\forall (s_{i},t_{i})\in \Gamma$.

זרימה דרך קשת ספציפית בגרף $G$ מוגדרת כ-:$f_{e,\Gamma ,R}=\sum _{p:\,e\in p}{f_{p}}$.

הערה: לשם קיצור נרשום $f_{e}$ בלי $\Gamma ,R$.

הגדרה (שיווי משקל נאש של זרימה). זרימה $f_{\Gamma ,R}$ תקרא שיווי משקל נאש של זרימה אא"ם $\forall (s_{i},t_{i})\in \Gamma$ ו-$\forall p,q$ מ-$s_{i}$ ל-$t_{i}$ (דרכים מהמקור למטרה) מתקיים

$f_{p}>0\Rightarrow \sum _{e\in p}{l_{e}(f_{e})}\leq \sum _{e\in q}{l_{e}(f_{e})}$.

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

הגדרה (רווח תחת תנאי של זרימה). תהיינה $f_{\Gamma ,R}$ ו-$f_{\Gamma ,R}^{*}$ 2 זרימות ב-$G$ (המתייחסות לאותן קבוצות $\Gamma$ ו-$R$). רווח תחת תנאי של זרימה $f^{*}$ ביחס ל-$f$ מוגדר כ-:$w^{f}(f^{*})=\sum _{e\in E}{f_{e}^{*}\cdot l_{e}(f_{e})}$.

טענה 1. בהינתן שיווי משקל נאש של זרימה $f$ וזרימה כלשהי $f^{*}$, מתקיים: $w(f)=w^{f}(f)\leq w^{f}(f^{*})$.

הוכחה. נניח ש-$(w^{f}(f^{*})<w^{f}(f$. מהגדרה :$\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})$. מאחר ש-$f$ ו-$f^{*}$ מתייחסות לאותן קבוצות $\Gamma ,R$, אז:

$\sum _{p:s_{i}\rightarrow t_{i}}f_{p}=\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}=r_{i}\;\;\forall i$.

מכאן נובע כי בהכרח קיים זוג $(s_{i},t_{i})$ ו-2 דרכים $p,q$ מ-$s_{i}$ ל-$t_{i}$ כך ש- $f_{p}^{*}>f_{p}$, $f_{q}^{*}<f_{q}$, וגם $\sum _{e\in p}l_{e}(f_{e})<\sum _{e\in q}l_{e}(f_{e})$.

במילים אחרות, הזרימה $f^{*}$ יכולה להשיג רווח נמוך יותר מאשר $f$ רק בתנאי שישנן 2 דרכים מ-$s_{i}$ ל-$t_{i}$ בעלות מחירים שונים, ובתנאי ש-$f^{*}$ ישנה מספר זרימות שב-$f$ על ידי שימוש בדרכים זולות יותר במקום שימוש בדרכים יקרות יותר. מצב זה לא אפשרי תחת ההנחה ש- $f$ הוא שיווי משקל נאש של זרימה. סוף ההוכחה

הערה: שימו-לב כי טענה 1 לא מניחה מבנה מסוים של $L$.

טענה 2. בהינתן 2 מספרים ממשיים $x$ ו-$y$ מתקיים $x\cdot y\leq x^{2}+y^{2}/4$.

הוכחה. זו דרך נוספת לבטא את הא"ש $(x-y/2)^{2}\geq 0$. סוף ההוכחה .

משפט. מחיר האנרכיה הטהור של כל בעיית ניתוב מוכלל $(G,L)$ עם קיבולות ליניאריות, קטן/שווה ל-4/3.

הוכחה. משפט זה שקול לקביעה כי לכל שיווי משקל נאש של זרימה $f$, $w(f)\leq (4/3)\cdot \min _{f^{*}}\{w(f^{*})\}$, כאשר $f^{*}$ היא זרימה שונה כלשהי. לפי הגדרה:

$w^{f}(f^{*})=\sum _{e\in E}f_{e}^{*}(a_{e}\cdot f_{e}+b_{e})$

$=\sum _{e}(a_{e}f_{e}f_{e}^{*})+\sum _{e\in E}f_{e}^{*}b_{e}.$

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

$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}$

$=\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$

$\leq w(f^{*})+{\frac {w(f)}{4}},$

שכן

$(1/4)\cdot w(f)=(1/4)\cdot \sum _{e\in E}f_{e}(a_{e}f_{e}+b_{e})$

$=(1/4)\cdot \sum _{e\in E}(f_{e})^{2}+\underbrace {(1/4)\cdot \sum _{e\in E}f_{e}b_{e}} _{\geq 0}.$

נסיק ש-$w^{f}(f^{*})\leq w(f^{*})+w(f)/4$, ולבסוף על ידי שימוש בטענה 1 הוכח הדרוש. סוף ההוכחה

הערה: בהוכחה נעשה שימוש מורחב של ההנחה לפיה הפונקציות ב-$L$ הן ליניאריות. נוכיח את המשפט גם עבור פונקציות פולינומיות.

משפט. בהינתן בעיית ניתוב מוכללת עם גרף $G$ וקיבולת פלינומיאלית מדרגה $d$ גם שאריות אי-שליליות אזי מחיר האנרכיה הטהור קטן/שווה ל- $d+1$ .

יש לשים-לב כי מחיר האנרכיה יכול לגדול עם דרגת הפולינום $d$. בדוגמה בתמונה שלעיל, בה הנחנו זרימה של יחידות זמן, לשיווי משקל נאש של זרימה יש תועלת חברתית שערכה 1, אולם התועלת הטובה ביותר מושגת כאשר $x=1-1/{\sqrt {d+1}}$ וכאשר

$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}}}$

$=\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}}}$.

גודל זה שואף לאפס כאשר $d$ שואף לאינסוף.