תגובה טובה ביותר

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

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

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

משחק בן n שחקנים יסומן G=(S_1,S_2,\ldots,S_n,u_1,u_2,\ldots,u_n) כאשר \!\ S_i היא קבוצת האסטרטגיות של השחקן ה-i, ו-\!\ u_i היא פונקציה u_i:S_1\times S_2 \times\ldots\times S_n\rarr \R שמתאימה לכל בחירת אסטרטגיות של כל השחקנים את התועלת (נקרא גם תשלום, או רווח) שמפיק שחקן ה-i ממנה.

נסמן את צירוף האסטרטגיות של כל השחקנים באות s (ללא סימון שחקן):  s \in S = S_1 \times S_2 \times \cdots \times S_n . נהוג לכתוב את צירוף האסטרטגיות מנקודת מבטו של שחקן  i כך:  s = \left ( s_i, s_{-i} \right ) . כלומר, האסטרטגיה של שחקן ה- i וכל האסטרטגיות של שאר השחקנים.

אסטרטגיה \!\ s_i היא תגובה טובה ביותר ל - \!\ s_{-i} אם לכל אסטרטגיה אחרת \!\ s_{i'} של שחקן ה- i מתקיים:  u_i \left ( s_i, s_{-i} \right ) \ge u_i \left ( s_{i'}, s_{-i} \right ).

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

נסתכל על משחק בין שני שחקנים (באסטרטגיות טהורות). שחקן 1 יכול לבחור אסטרטגיה אחת מתוך הקבוצה S_1 = \left ( a, b, c \right ) ושחקן 2 יכול לבחור אסטרטגיה אחת מתוך הקבוצה S_2 = \left ( d, e, f \right ) . התועלות מתוארות בעזרת הטבלה הבאה. כל משבצת מגדירה את תוצאת הפונקציה u\left ( s \right ) כאשר s הוא הצירוף הרלוונטי של השורה והטור (\{a,e\} לדוגמה). התועלת של שחקן 1 מופיע משמאל והתועלת של שחקן 2 מופיע מימין.

משחק לדוגמה
שחקן 2 בוחר באסטרטגיה d שחקן 2 בוחר באסטרטגיה e שחקן 2 בוחר באסטרטגיה f
שחקן 1 בוחר באסטרטגיה a 4, 4 3, 12 2, 1
שחקן 1 בוחר באסטרטגיה b 3, 1 1, 3 3, 2
שחקן 1 בוחר באסטרטגיה c 2, 3 4, 3 2, 0

נסתכל על נקודות מבטו של שחקן 1, בהינתן האסטרטגיה שבחר שחקן 2:

  • אם שחקן 2 בחר לשחק את אסטרטגיה d, בחירה של שחקן 1 באסטרטגיה a תוביל לתועלת 4, בחירה באסטרטגיה b תוביל לתועלת 1, ובחירה באסטרטגיה c תוביל לתועלת 3. לכן התגובה הטובה ביותר במקרה זה תהיה אסטרטגיה a.
  • אם שחקן 2 בחר לשחק את אסטרטגיה e, בחירת אסטרטגיה a על ידי שחקן 1 היא תגובה טובה ביותר שתוביל לתועלת 12.
  • אם שחקן 2 בחר לשחק את אסטרטגיה f, בחירת אסטרטגיה b היא תגובה טובה ביותר שתוביל לתועלת 2.

עתה, נסתכל על נקודת מבטו של שחקן 2, בהינתן האסטרטגיה של שחקן 1:

  • אם שחקן 1 בחר לשחק את אסטרטגיה a, בחירה של שחקן 2 באסטרטגיה d תוביל לתועלת 4, בחירה באסטרטגיה e תוביל לתועלת 3, ובחירה באסטרטגיה f תוביל לתועלת 2. לכן התגובה הטובה ביותר במקרה זה תהיה אסטרטגיה d.
  • אם שחקן 1 בחר לשחק את אסטרטגיה b, נשים לב שיש כאן שתי אסטרטגיות העונות להגדרה של תגובה טובה ביותר. בחירת אסטרטגיה d או f על ידי שחקן 2 היא תגובה טובה ביותר שתוביל לתועלת 3.
  • אם שחקן 1 בחר לשחק את אסטרטגיה c, בחירת אסטרטגיה e היא תגובה טובה ביותר שתוביל לתועלת 4.

הערה: מצב בו שני השחקנים בוחרים אסטרטגיות כך שכל אחת היא תגובה טובה ביותר לשנייה נקרא שיווי משקל נאש. בדוגמה שלנו יש שיווי משקל נאש: \{b,f\}.

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

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

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

במשחק הבא קיים שיווי משקל נאש עבור בחירת האסטרטגיות \{c,d\}, אך אם נתחיל את דינמיקת התגובה הטובה ביותר מאחד התאים \{b,f\}, \{a,d\}, \{a,f\}, או \{b,e\} כל שחקן בתורו ירצה לעבור לאסטרטגיה טובה יותר - כזו בה התועלת שלו היא 1 ולא -1. כך השחקנים "יסתובבו" במעגל, ולא יגיעו אף פעם ל - \{c,d\}, שהיא נקודת שיווי משקל, ובעלת תועלות גבוהות יותר לשני השחקנים.

d e f
a 0, 0 1, 1- 1-, 1
b 0, 0 1-, 1 1, 1-
c 3, 3 0, 0 0, 0

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

אסטרטגיה מעורבת הינה תגובה טובה ביותר \iff כל אחת מהאסטרטגיות בתומך שלה (כלומר, האסטרטגיות שהסתברותן גדולה מ-0) הינה תגובה טובה ביותר.

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

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