משפט קון

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

זיכרון שלם[עריכת קוד מקור | עריכה]

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

שקילות בין אסטרטגיה מעורבת לאסטרטגית התנהגות[עריכת קוד מקור | עריכה]

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

יתרונות בהחלפת אסטרטגיה מעורבת באסטרטגיית התנהגות שקולה לה[עריכת קוד מקור | עריכה]

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

דוגמאות[עריכת קוד מקור | עריכה]

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

Desktop

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




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

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

Desktop

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


הכיוון ההפוך למשפט קיון[עריכת קוד מקור | עריכה]

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

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

לקריאה נוספת[עריכת קוד מקור | עריכה]