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

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

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

הגדרה

יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Gamma} משחק בצורה רחבה. נסמן את קבוצות הידיעה של שחקן $i$ כך: $\left\{U_{i}^{1},U_{i}^{2},\ldots ,U_{i}^{k_{i}}\right\}$. בכל קבוצת ידיעה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} נסמן את המהלכים האפשריים לשחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} מתוך הקבוצה ב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\left(U_i^j\right)} . אז אסטרטגית ההתנהגות של שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} היא וקטור של התפלגויות: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i\in\prod_{i=1}^{k_i}{\Delta\left(A\left(U_i^j\right)\right)}} .
כל אסטרטגית התנהגות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} מגדירה הסתברות על המהלכים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\in A\left(U_i^j\right)} , המסומנת כך: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i \left(U_i^j;a\right)} .

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

דוגמאות

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

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

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

כיוון שמטרת הנהג היא רווח, הוא ירצה להגדיל את סיכוייו לצאת ביציאה השנייה. באסטרטגיות טהורות אין לשחקן בכלל אפשרות לעשות זאת: אם יבחר לשחק "המשך", יפספס את שתי היציאות ויגיע לקצה הכביש. אם יבחר לשחק "צא", ייצא מיד בראשונה. מכיוון שתוצאה של אסטרטגיה מעורבת היא הגרלה על תוצאות של אסטרטגיות טהורות, התוצאה המקסימלית במשחק "הנהג השכחן" המתואר כאן היא 1 באסטרטגיות מעורבות. לעומת זאת, באסטרטגית התנהגות יוכל הנהג לקבוע הסתברות מראש, ולפיה להגריל את החלטותיו בכל נקודת החלטה מחדש, באופן בלתי תלוי בהגרלה הקודמת: אם יבחר, למשל, באסטרטגיה : $b=\left[{\frac {1}{3}}{\mbox{Exit}},{\frac {2}{3}}{\mbox{Drive}}\right]$ (כלומר, בכל פעם שייקרא לשחק בתוך קבוצת הידיעה היחידה שיש במשחק, יסע ישר בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2/3} ויצא בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/3} ), יוכל להגיע ליעד (התוצאה 4) בהסתברות חיובית, ואז תהיה תוחלת התוצאות שלו:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)=}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle =\frac{1}{3}\cdot0+\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}\cdot4+\frac{4}{9}\cdot1=1\frac{1}{3}}

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

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

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

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

במשחק זה, לשחקן יש ארבע אסטרטגיות טהורות: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_1L_2} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_1R_2} ,הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_1L_2} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_1R_2} , לכן לצירוף קמור שלהם (צירוף לינארי שמקדמיו מסתכמים ב-1) ישנן 3 דרגות חופש: השחקן יכול לקבוע הסתברויות הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle p_{1}L_{1}L_{2},p_{2}L_{1}R_{2},p_{3}R_{1}L_{2}} וההסתברות הרביעית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-(p_1+p_2+p_3))R_1R_2} תנבע מהם (כלומר, האסטרטגיה המעורבת במקרה זה היא נקודה במרחב תלת ממדי).

לעומת זאת, באסטרטגית התנהגות ישנן רק שתי דרגות חופש בקביעת התוצאות: השחקן בוחר את התנהגותו (בחירה בין שני מצבים) הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1, 1-p_1} בקבוצת הידיעה העליונה ובהתאם את התנהגותו בקבוצת הידיעה התחתונה (גם שם שני מהלכים אפשריים), הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_2, 1-p_2} , ומכאן שזו נקודה במרחב דו-ממדי. מכאן שבמשחק זה קיימות תוצאות של אסטרטגיות מעורבות שלא ניתן לתאר באמצעות אסטרטגיות התנהגות.

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

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

זיכרון שלם הוא תכונה המיוחסת לשחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} , אם על עץ המשחק מתקיימים התנאים הבאים:

1. כל קבוצת ידיעה של שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} חותכת כל מסילה לכל היותר פעם אחת.
2. כל שתי מסילות מהשורש של עץ המשחק המסתיימות בקבוצת ידיעה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_i^k} עוברות דרך אותן קבוצות הידיעה עד אליה, ובאותו הסדר.

משפט קיון

משפט קיון (שהוכח על ידי הרולד קיון ב-1957) קובע כי במשחק בצורה רחבה בעל זיכרון שלם לשחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} , לכל אסטרטגיה מעורבת יש אסטרטגית התנהגות השקולה לה.

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

שימושים

במקרים מסוימים, אורך התיאור של אסטרטגיות התנהגות קטן משמעותית מזה של אסטרטגיה מעורבת, זאת בגלל מימד האסטרטגיה: אסטרטגיה מעורבת מוצגת כנקודה במרחב בעל כמות ממדים ככמות האסטרגיות הטהורות השונות: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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