אסטרטגיית התנהגות

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

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

הגדרה

יהי $\Gamma$ משחק בצורה רחבה. נסמן את קבוצות הידיעה של שחקן $i$ כך: $\left\{U_{i}^{1},U_{i}^{2},\ldots ,U_{i}^{k_{i}}\right\}$. בכל קבוצת ידיעה $j$ נסמן את המהלכים האפשריים לשחקן $i$ מתוך הקבוצה ב $A\left(U_{i}^{j}\right)$. אז אסטרטגיית ההתנהגות של שחקן $i$ היא וקטור של התפלגויות: $b_{i}\in \prod _{i=1}^{k_{i}}{\Delta \left(A\left(U_{i}^{j}\right)\right)}$.
כל אסטרטגיית התנהגות $b_{i}$ מגדירה הסתברות על המהלכים $a\in A\left(U_{i}^{j}\right)$, המסומנת כך: $b_{i}\left(U_{i}^{j};a\right)$.

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

דוגמאות

משחק בו קיימת אסטרטגיה מעורבת ללא אסטרטגיית התנהגות מקבילה. למשחק שתי קבוצות ידיעה (עליונה ותחתונה) ולא ניתן לשלוט בתוחלת על תוצאותיו באסטרטגיית התנהגות.

אסטרטגיית התנהגות שאין לה שקולה מעורבת

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

כיוון שמטרת הנהג היא רווח, הוא ירצה להגדיל את סיכוייו לצאת ביציאה השנייה. באסטרטגיות טהורות אין לשחקן בכלל אפשרות לעשות זאת: אם יבחר לשחק "המשך", יפספס את שתי היציאות ויגיע לקצה הכביש. אם יבחר לשחק "צא", ייצא מיד בראשונה. מכיוון שתוצאה של אסטרטגיה מעורבת היא הגרלה על תוצאות של אסטרטגיות טהורות, התוצאה המקסימלית במשחק "הנהג השכחן" המתואר כאן היא 1 באסטרטגיות מעורבות. לעומת זאת, באסטרטגיית התנהגות יוכל הנהג לקבוע הסתברות מראש, ולפיה להגריל את החלטותיו בכל נקודת החלטה מחדש, באופן בלתי תלוי בהגרלה הקודמת: אם יבחר, למשל, באסטרטגיה : $b=\left[{\frac {1}{3}}{\mbox{Exit}},{\frac {2}{3}}{\mbox{Drive}}\right]$ (כלומר, בכל פעם שייקרא לשחק בתוך קבוצת הידיעה היחידה שיש במשחק, יסע ישר בהסתברות $2/3$ ויצא בהסתברות $1/3$), יוכל להגיע ליעד (התוצאה 4) בהסתברות חיובית, ואז תהיה תוחלת התוצאות שלו:

$u\left(\left[{\frac {1}{3}}{\mbox{Exit}},{\frac {2}{3}}{\mbox{Drive}}\right]\right)={\frac {1}{3}}u\left({\mbox{Exit}}_{1}\right)+{\frac {2}{3}}u\left({\mbox{Drive}}_{1}\right)=$

$={\frac {1}{3}}\cdot 0+{\frac {2}{3}}\left({\frac {1}{3}}u\left({\mbox{Exit}}_{2}\right)+{\frac {2}{3}}u\left({\mbox{Drive}}_{2}\right)\right)=0+{\frac {2}{9}}\cdot 4+{\frac {4}{9}}\cdot 1=1{\frac {1}{3}}$

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

אסטרטגיה מעורבת שאין לה שקולה התנהגותית

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

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

במשחק זה, לשחקן יש ארבע אסטרטגיות טהורות: $L_{1}L_{2}$, $L_{1}R_{2}$,$R_{1}L_{2}$, $R_{1}R_{2}$, לכן לצירוף קמור שלהם (צירוף ליניארי שמקדמיו מסתכמים ב-1) ישנן 3 דרגות חופש: השחקן יכול לקבוע הסתברויות $p_{1}L_{1}L_{2},p_{2}L_{1}R_{2},p_{3}R_{1}L_{2}$ וההסתברות הרביעית $(1-(p_{1}+p_{2}+p_{3}))R_{1}R_{2}$ תנבע מהם (כלומר, האסטרטגיה המעורבת במקרה זה היא נקודה במרחב תלת־ממדי).

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

מקרים של שקילות לאסטרטגיה מעורבת

ערך מורחב – משפט קיון וזיכרון שלם

תנאי הזיכרון השלם

זיכרון שלם הוא תכונה המיוחסת לשחקן $i$, אם על עץ המשחק מתקיימים התנאים הבאים:

1. כל קבוצת ידיעה של שחקן $i$ חותכת כל מסילה לכל היותר פעם אחת.
2. כל שתי מסילות מהשורש של עץ המשחק המסתיימות בקבוצת ידיעה $U_{i}^{k}$ עוברות דרך אותן קבוצות הידיעה עד אליה, ובאותו הסדר.

משפט קיון

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

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

שימושים

במקרים מסוימים, אורך התיאור של אסטרטגיות התנהגות קטן משמעותית מזה של אסטרטגיה מעורבת, זאת בגלל מימד האסטרטגיה: אסטרטגיה מעורבת מוצגת כנקודה במרחב בעל כמות ממדים ככמות האסטרטגיות הטהורות השונות: $\dim \left(\Sigma \right)=\left|S\right|-1$ (ה-1 מוחסר ממימד האסטרטגיה מכיוון שמדובר בצירוף קמור, לכן מימד אחד תמיד שמור להשלמת סכום המקדמים ל-1) בעוד שמימד אסטרטגיות ההתנהגות תלוי במספר המהלכים השונים המתאפשרים בקבוצות ידיעה שונות: $\dim \left(B\right)=\sum _{j}\dim \left(U^{j}\right)=\sum _{j}\left(\left|A\left(U^{j}\right)\right|-1\right)$. במצבים מסוימים (למשל, משחק עם כמות מצומצמת של מצבים המופיעים בסדר מתחלף באסטרטגיות שונות) מספר זה יכול להיות קטן ממספר האסטרטגיות הטהורות.

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

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946
• ישראל אומן, שמואל זמיר ויאיר טאומן, תורת המשחקים, תל אביב: האוניברסיטה הפתוחה, 1981