מחיר האנרכיה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

הגדרה מתמטית[עריכת קוד מקור | עריכה]

בהינתן משחק 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. סוף הוכחה

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

הפרדוקס של ברס[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – פרדוקס ברס

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

ניתן להתייחס לבעיה זו כבעיית זרימה בגרף קשיר 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 שואף לאינסוף.