ויקיפדיה

שיווי משקל חזק – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
אין תקציר עריכה
שורה 1:
{{בעבודה אקדמית|קורס="על גבול כלכלה וחישוב"|יעד=01.02.10}}
 
'''שיווי משקל חזק''' הוא הרחבה של [[שיווי משקל נאש]] (המהווה מצב, בו אף אחד מהשחקנים לא יכול לשפר את מצבו בלי תיאום עם שחקנים אחרים (ויתכן שאף עם תיאום כזה, אינו יכול לבצע שיפור) למצב שבו אף קואוליציה[[קואליציה]] של שחקנים לא יכולה לשפר את מצבה, ע"י סטייה של כל חברי הקואוליציההקואליציה.
 
שיווי משקל חזק הוגדר לראשונה ע"י פרופסור ישראל אומן <ref> ראה מקור 2</ref> על מנת לתת הרחבה למושג שיווי משקל נאש.
 
נקודת שיווי משקל חזק במשחק היא צירוף של אסטרטגיות השחקנים ([[תכסיס (בתורת המשחקים)|תכסיס]]ים), כך שלאף קואוליציהקואליציה של שחקנים לא משתלם לשנות את התכסיסים שלה אם שאר השחקנים אינם משנים את התכסיס שלהם. לקואוליציהלקואליציה משתלם לשנות את התכסיסים של חבריה, אם כל חבר בקואליציה מרוויח ממש מהשינוי.
 
==שיווי משקל עבור קואוליציות==
בניגוד לשיווי משקל נאש, המהווה שיווי משקל בו אף שחקן לא יכול להרוויח מסטיה ומתעלם מהאפשרות של שחקנים ליצור [[קואוליציות|קואליציה]] שישפרו את מצבם, הגדרת שיווי משקל K-נאש ושיווי משקל חזק, מסתכלת על סטיות של קואוליציות של שחקנים.
 
נניח שיש <math>I</math> שחקנים וכל שחקן <math> i \in \left \{ 1, 2, \ldots , I \right \} </math> יכול לבחור אסטרטגיה ([[תכסיס]]) אחת מתוך קבוצת האסטרטגיות הקיימות עבורו: <math>s_i \in S_i</math>.
שורה 14:
לצורך פשטות ההסבר נשתמש בהגדרה של אסטרגיות טהורות. ניתן ע"י החלפה של <math>S^*</math> שהגדרנו המהווה פרופיל של אסטרגיות טהורות ל - <math>S^*</math> פרופיל של אסטרגיות מעורבות.
 
הגדרה: [[קואליציה]]. תת קבוצה של השחקנים <math>\displaystyle T\subseteq I</math> תיקרא קואליציה.
נסמן את וקטור האסטרגיות שנבחר ע"י קואוליציהקואליציה כלשהי T של שחקנים כ <math>s_T \in S_T</math>.
נסמן את צירוף האסטרטגיות של כל השחקנים באות <math>s</math> (ללא סימון שחקן\קואליציה): <math> s \in S = S_1 \times S_2 \times \cdots \times S_I </math>. תוצאת המשחק נקבעת לפי צירוף האסטרטגיות וכך גם ווקטור התשלום לשחקנים: <math> g\left ( s \right ) </math>.
נהוג לכתוב את צירוף האסטרטגיות מנקודת מבטה של קואוליציהקואליציה T כך: <math> s = \left ( s_T, s_{-T} \right ) </math>.כלומר, האסטרטגיה של הקואליציה והאסטרטגיה של שאר השחקנים.
 
הגדרה: פרופיל אסטרגיות <math>S_T </math> מהווה שיפור עבור קואוליציהקואליציה T מפרופיל אסטרגיות <math> s^* = (s^*_T,s_{-T}^*)</math> אם לכל שחקן <math>\displaystyle i\in T</math>
<math> g\left ( s_T^*,s_{-T}^* \right ) < g \left (s_T, s_{-T}^* \right ) </math>. זאת אומרת, כל השחקנים בקואוליציהבקואליציה משפרים ממש את מצבם, באם הם סוטים במשותף מהפרופיל <math>s_T^* </math> לפרופיל <math>S_T </math>.
 
קואוליציהקואליציה T נמצאת בשיווי משקל בפרופיל אסטרגיות <math> s^*=\left (s_1^*,s_2^*,\ldots,s_I^*\right ) </math> אם לא קיים פרופיל אסטרגיות <math>S_T </math> המהווה שיפור קואוליציוני (עבור קואוליציהקואליציה T) שלו.
 
== הגדרת שיווי משקל חזק ==
פרופיל אסטרגיות <math> s^*=\left (s_1^*,s_2^*,\ldots,s_I^*\right ) </math> הוא שיווי משקל חזק, אם לא קיימת קואוליציהקואליציה (בכל גודל, ובפרט עבור שחקן בודד) <ref>ובכך מהווה שיווי משקל |I| נאש - ראה להלן הגדרת שיווי משקל K - נאש </ref>. שקיים עבורה שיפור קואליציאני.
 
כיוון ששיווי משקל חזק מהווה שיווי משקל עבור כל גודל של קואלוציהקואליציה ובפרט עבור שחקן בודד, הוא מהווה בהכרח [[שיווי משקל נאש]].
 
הגדרה פורמלית:
שורה 37:
<math>\forall T \neq \emptyset \subseteq I,\forall s_T \in S_T , \exist i \in I , g_i(s^*_{T}, s^*_{-T}) >= g_i(s_{T},s^*_{-T}).</math>
 
ובמילים: לכל קואוליציהקואליציה, לכל סטיה של הקואליציה, קיים שחקן בקואליציה שלא משפר את מצבו. זאת אומרת, אין אף קואוליציהקואליציה שיכולה לסטות וכל השחקנים בה ישפרו את מצבם.
 
== דוגמאות לשיווי משקל חזק ==
שורה 57:
|}
 
המצב בו שני הגמדים מתבטלים הוא שיווי משקל נאש, אבל הוא לא שיווי משקל חזק. כי אם קואוליציהקואליציה של שני הגמדים, תתאחד ותחליט לעבוד, שניהם ישיגו ערך 100 (שטוב עבור שניהם מהערך 0 שהשיגו בפרופיל האסרגיות הקודם).
לעומת זאת, המצב בו שני הגמדים עובדים, הוא שיווי משקל חזק <ref> ובפרט שיווי משקל נאש</ref> כיוון ששני הגמדים מקבלים 100. אם אחד הגמדים סוטה, הוא מקבל 0 ולא משפר את מצבו. וכמובן אותו הענין קורה אם שני הגמדים סוטים מהפרופיל ומתבטלים. לכן זהו שיווי משקל חזק.
 
שורה 93:
עבור <math>1<=K<=|I|</math>.פרופיל אסטרגיות <math> s^*=\left (s_1^*,s_2^*,\ldots,s_I^*\right ) </math> יקרא שיווי משקל K - נאש אם לא קיימת קואליציה שקטנה או שווה בגודלה לK. שקיים עבורה שיפור קואליציאני.
 
בדומה לשיווי משקל חזק, כיוון ששיווי משקל K מהווה שיווי משקל עבור כל גודל של קואולוציהקואליציה קטנה מ-K ובפרט עבור שחקן בודד, הוא מהווה בהכרח [[שיווי משקל נאש]].
 
הגדרה פורמלית:
שורה 103:
<math>\forall T \neq \emptyset \subseteq I,|T|<=K, \forall s_T \in S_T , \exist i \in I , g_i(s^*_{T}, s^*_{-T}) >= g_i(s_{T},s^*_{-T}).</math>
 
ובמילים: לכל קואליציה בגודל לכל היותר - K, ולכל סטיה של הקואליציה, קיים שחקן בקואוליציהבקואליציה שלא משפר את מצבו. זאת אומרת, אין אף קואוליציהקואליציה שיכולה לסטות וכל השחקנים בה ישפרו את מצבם.
 
אם פרופיל אסטרגיות מסוים מהווה שיווי משקל K-נאש אזי לכל t<K הוא מהווה שיווי משקל t-נאש.
אוחזר מתוך "https://he.wikipedia.org/wiki/שיווי_משקל_חזק"