שליטה של אסטרטגיות

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

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

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

כששחקן משווה בין שתי אסטרטגיות א' ו-ב' התוצאה יכולה להיות אחת מהבאות:

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

ובהשוואה לכל האסטרטגיות נקבל:

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

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

עבור שחקן i אסטרטגיה s^*\in S_i היא 'אסטרטגיה שלטת חזק אם לכל אסטרטגיה אחרת s^\prime\in S_i מתקיים:

\forall s_{-i}\in S_{-i}\left[u_i(s^*,s_{-i})> u_i(s^\prime,s_{-i})\right]

עבור שחקן i אסטרטגיה s^*\in S_i היא 'אסטרטגיה שלטת חלש אם לכל אסטרטגיה אחרת s^\prime\in S_i מתקיימים:

\forall s_{-i}\in S_{-i}\left[u_i(s^*,s_{-i})\geq u_i(s^\prime,s_{-i})\right]
\exists s_{-i}\in S_{-i}\left[u_i(s^*,s_{-i})> u_i(s^\prime,s_{-i})\right]

שליטה ושיווי משקל נאש[עריכת קוד מקור | עריכה]

א ב
א 1, 1 0, 0
ב 0, 0 0, 0

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

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

מחיקה חוזרת של אסטרטגיות נשלטות[עריכת קוד מקור | עריכה]

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

התהליך יכול להתבצע בשתי דרכים:

  • מחיקה רק של אסטרטגיות נשלטות חזק. אם בסוף התהליך נשארה רק אסטרטגיה אחת לכל שחקן אזי קיבלנו שיווי משקל נאש ייחודי.
  • מחיקה גם של אסטרטגיות נשלטות חזק וגם של אסטרטגיות נשלטות חלש. אם בסוף התהליך נשארה רק אסטרטגיה אחת לכל שחקן אזי קיבלנו שיווי משקל נאש אבל לא בהכרח ייחודי ובמשחקים שונים מחיקה בסדר מסוים יכולה להוביל לשיווי משקל אחר.

קישורים חיצוניים[עריכת קוד מקור | עריכה]