משתמש:Meital.albo/מחיר האנרכיה

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

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

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

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

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

הגדרה מתמטית

בהינתן משחק $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, בעוד עבור כל אסטרטגיה טהורה $\leq 4/3$ PoA ). ראשית, יש להוכיח כי קיים שו"מ נאש.

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

הוכחה. נסמן ב-$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})}$.

Example of Braess's paradox

נתבונן ברשת שבתמונה. אם הדרך המשובשת לא זמינה אז שו"מ נאש מעורב מתקבל כאשר כל אחד מהשחקנים בוחר בקשת העליונה והתחתונה בהסתברות שווה. לשו"מ זה יש רווח חברתי של 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}$ $\in \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}$ כאשר $p$ מציין $\Gamma ,R$.

הגדרה (שו"מ נאש של זרימה). זרימה $f_{\Gamma ,R}$ תקרא שו"מ נאש של זרימה אא"ם $\forall (s_{i},t_{i})\in \Gamma$ וגם $\forall p,q$ from $s_{i}$ to $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)$ עם קיבולות לינאריות הוא $\leq 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$ גם שאריות אי-שליליות אזי מחיר האנרכיה הטהור הינו $\leq 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$ שואף לאינסוף.