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

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

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

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

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

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

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

{| align=left border="1" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
|+ align=bottom |משחק לדוגמה
|
!style="width: 90px"|שחקן 2 בוחר באסטרטגיה <math>d</math>
!style="width: 90px"|שחקן 2 בוחר באסטרטגיה <math>e</math>
!style="width: 90px"|שחקן 2 בוחר באסטרטגיה <math>f</math>
|-
!style="width: 90px"|שחקן 1 בוחר באסטרטגיה <math>a</math>
|align=center|4, 4
|align=center|3, 12
|align=center|2, 1
|-
!style="width: 90px"|שחקן 1 בוחר באסטרטגיה <math>b</math>
|align=center|3, 1
|align=center|1, 3
|align=center|3, 2
|-
!style="width: 90px"|שחקן 1 בוחר באסטרטגיה <math>c</math>
|align=center|2, 3
|align=center|4, 3
|align=center|2, 0
|-
|}

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

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

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

*אם שחקן 1 בחר לשחק את אסטרטגיה <math>a</math>, בחירה של שחקן 2 באסטרטגיה <math>d</math> תוביל לתועלת 4, בחירה באסטרטגיה <math>e</math> תוביל לתועלת 3, ובחירה באסטרטגיה <math>f</math> תוביל לתועלת 2. לכן התגובה הטובה ביותר במקרה זה תהיה אסטרטגיה <math>d</math>.

*אם שחקן 1 בחר לשחק את אסטרטגיה <math>b</math>, נשים לב שיש כאן שתי אסטרטגיות העונות להגדרה של התגובה הטובה ביותר. בחירת אסטרטגיה <math>d</math> או <math>f</math> על ידי שחקן 2 היא התגובה הטובה ביותר שתוביל לתועלת 3.

*אם שחקן 1 בחר לשחק את אסטרטגיה <math>c</math>, בחירת אסטרטגיה <math>e</math> היא התגובה הטובה ביותר שתוביל לתועלת 4.

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

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

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

{| align="" border="1" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
|+ align=bottom |
|
!style="width: 90px"|<math>d</math>
!style="width: 90px"|<math>e</math>
!style="width: 90px"|<math>f</math>
|-
!style="width: 90px"|<math>a</math>
|align=center|0, 0
|align=center|1, 1-
|align=center|1-, 1
|-
!style="width: 90px"|<math>b</math>
|align=center|0, 0
|align=center|1-, 1
|align=center|1, 1-
|-
!style="width: 90px"|<math>c</math>
|align=center|3, 3
|align=center|0, 0
|align=center|0, 0
|-
|}

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

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

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

קטגוריה:תורת המשחקים