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

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

הגדרה פורמלית

משחק בן 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}\rightarrow \mathbb {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)\geq 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$. כך נקבל אסטרטגיה מעורבת שתועלתה גדולה יותר מזו המקורית.

ראו גם

• תורת המשחקים
• שיווי משקל נאש
• משחק פוטנציאל
• אסטרטגיה מעורבת