משפט קון

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

זיכרון שלם

נאמר שלשחקן $i$ יש זיכרון שלם אם לכל שני קדקודים $Y$, $X$ הנמצאים באותה קבוצת ידיעה של שחקן $i$, המסילות מהשורש לקדקודים $Y$, $X$ עוברות דרך אותן קבוצות ידיעה של שחקן $i$ ובאותו סדר. יתר על כן, הפעולה שבה שחקן $i$ נוקט בקדקוד ההחלטה ה-$k$ שלו על המסילה לקדקוד $X$ שווה לפעולה בה הוא נוקט בקדקוד ההחלטה ה-$k$ שלו על המסילה לקדקוד $Y$ .

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

השקילות באה לידי ביטוי במובן שבו ללא תלות באסטרטגיות בהן נוקטים השחקים האחרים, ההסתברות להגיע לקדקוד בעץ כאשר שחקן $i$ משתמש באסטרטגיה מעורבת מסוימת זהה להסתברות להגיע לאותו הקדקוד כאשר שחקן $i$ נוקט באסטרטגיית ההתנהגות השקולה לה. כלומר, אם $\sigma _{i}$ היא אסטרטגיה מעורבת ו- $b_{i}$ היא אסטרטגית התנהגות של שחקן $i$ במשחק בצורה רחבה אז הן שקולות זו לזו אם לכל קומבינציה $\sigma _{-i}$ של אסטרטגיות של שאר השחקנים הן משרות הסתברויות שוות על כל אחד מקדקודי עץ המשחק כלומר על כל אחת מהתוצאות האפשריות במשחק.

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

1. קבוצת אסטרטגיות ההתנהגות "קטנה יותר" מקבוצת האסטרטגיות המעורבות כיוון שהיא חוסכת בפרמטרים. למשל, אם לשחקן מסוים יש 3 קבוצות ידיעה עם שתי פעולות אפשריות בכל אחת, הרי שמספר האסטרטגיות הטהורות הן $2^{3}=8$ ואז כל אסטרטגיה מעורבת כוללת 7 משתנים בעוד שאסטרטגית התנהגות כוללת רק 3 משתנים.
2. קל יותר לחשוב על עשיית הגרלה על הפעולות האפשריות בכל קבוצת ידיעה ולא לחשוב על תוכנית פעולה כוללת לכל המשחק.

דוגמאות

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

Desktop

לשחקן יש ארבע אסטרטגיות טהורות {${T_{1}T_{2},T_{1}B_{2},B_{1}T_{2},B_{1}B_{2}}$}.
נראה כי לאסטרטגיה המעורבת $\sigma _{1}=[0.5(T_{1}T_{2}),0(T_{1}B_{2}),0(T_{2}B_{1}),0.5(B_{1}B_{2})]$ אין אסטרטגית התנהגות שקולה.
אסטרטגיה מעורבת זו משרה את ההתפלגות הבאה על תוצאות המשחק: $[0.5(O_{1}),0(O_{2}),0(O_{3}),0.5(O_{4})]$.
אסטרטגית התנהגות $([\alpha (T_{1}),(1-\alpha )(B_{1})],[\beta (T_{2}),(1-\beta )(B_{2})])$ משרה את ההתפלגות הבאה על התוצאות:
$[(1-\alpha )(1-\beta )(O_{1}),(1-\alpha )\beta (O_{2}),\alpha (1-\beta )(O_{3}),\alpha \beta (O_{4})]$.
אם אסטרטגית ההתנהגות $(\alpha ,\beta )$ שקולה לאסטרטגיה המעורבת $\sigma _{1}$, שתיהן משרות אותה התפלגות על התוצאות. לכן:
$\alpha \beta =0.5$
$\alpha (1-\beta )=0$
$(1-\alpha )\beta =0$
$(1-\alpha )(1-\beta )=0.5$
למערכת משוואות זו אין פתרון. כלומר, אין אסטרטגית התנהגות שקולה.

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

Desktop

לשחקן יש שתי אסטרטגיות $L$ ו- $R$. האסטרטגיה הטהורה $L$ מביאה לתוצאה $O_{3}$, והאסטרטגיה הטהורה $R$ מביאה לתוצאה $O_{1}$. כידוע, אסטרטגיה מעורבת היא התפלגות על האסטרטגיות הטהורות, מכאן ניתן להסיק שאין אסטרטגיה מעורבת שניתן לקבל באמצעותה את התוצאה $O_{2}$.
נסתכל על אסטרטגיית ההתנהגות בה השחקן מגריל בין שתי האפשרויות בהסתברויות שוות: $[0.5(L),0.5(R)]$.
במקרה כזה ההתפלגות על התוצאות האפשריות הן: $[0.5(O_{1}),0.25(O_{2}),0.25(O_{3})]$.
מכיוון שהתפלגות זו אינה יכולה להתקבל באמצעות אסטרטגיה מעורבת כלשהי נאמר שאין אסטרטגיה מעורבת שקולה לאסטרטגיית ההתנהגות הנתונה.

הכיוון ההפוך למשפט קון

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

כל מסילה היוצאת מהשורש עוברת דרך כל קבוצת ידיעה של שחקן $i$ לכל היותר פעם אחת.

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, הוצאת מאגנס, 2008
• ישראל אומן, שמואל זמיר ויאיר טאומן, תורת המשחקים, האוניברסיטה הפתוחה, 1981
• ויליאם פאונדסטון, דילמת האסיר, הוצאת זמורה ביתן, 2000
• אבינש דיקסיט ובארי ניילבאף, תורת המשחקים, הוצאת ידיעות אחרונות, 2005
• חיים שפירא (מתמטיקאי), שיחות על תורת המשחקים, הוצאת כנרת, 2008

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

28615284משפט קון