משחק בעל ידיעה שלמה
בתורת המשחקים, משחק בצורה רחבה נקרא משחק בעל ידיעה שלמה אם בכל שלב ושלב של המשחק, השחקן שתורו לשחק יודע מה היו מהלכי כל השחקנים עד אותו שלב, ובמידה והיו הגרלות, השחקן יודע את תוצאותיהן. בפרט, במשחק בעל ידיעה שלמה השחקנים משחקים זה אחרי זה והם אינם משחקים באופן סימולטני.
קבוצת ידיעה של שחקן מסוים היא קבוצת קדקודים אשר השחקן אינו יכול להבחין ביניהם. משחק ייקרא "בעל ידיעה שלמה לשחקן i" אם כל קבוצת ידיעה של שחקן זה מכילה קדקוד אחד בלבד. כלומר, בבואו לבצע מהלך, השחקן יודע באיזה מקדקודי ההחלטה שלו בעץ המשחק נמצאת התחרות. משחק ייקרא "בעל ידיעה שלמה" אם הוא בעל ידיעה שלמה לכל אחד מהשחקנים.
במילים אחרות, משחק בעל ידיעה שלמה הוא משחק שבו כל אחד מהקדקודים של כל אחד מהשחקנים מהווה קבוצת ידיעה של אותו שחקן. אחרת, יקרא משחק בעל ידיעה לא שלמה.
שחמט הוא דוגמה למשחק עם ידיעה שלמה, כל שחקן יודע את המצב על הלוח בכל רגע נתון ויודע מה הייתה סדרת המהלכים שהביאה למצב הלוח הנוכחי. דוגמאות נוספות של משחקים בעלי ידיעה שלמה הם: דמקה, מונופול, סולמות ונחשים, איקס עיגול והקס. דוגמאות למשחקים ללא ידיעה שלמה: פוקר (שבו הקלפים של כל שחקן מוסתרים מהשחקנים האחרים), וזוג או פרט.
משפט פון-ניומן (Von Neumann)
בכל משחק שני שחקנים בעל ידיעה שלמה, שבו קבוצת התוצאות האפשריות היא:
- { תיקו, I מנצח, II מנצח } = O
מתקיימת אחת ורק אחת משלוש האפשרויות הבאות:
- לשחקן I יש אסטרטגיה מנצחת.
- לשחקן II יש אסטרטגיה מנצחת.
- לכל אחד משני השחקנים יש אסטרטגיה המבטיחה לפחות תיקו.
- אסטרטגיה SI של שחקן I נקראת אסטרטגיה מנצחת אם: I מנצח = (u(SI,SII לכל אסטרטגיה SII של שחקן II.
- אסטרטגיה SI של שחקן I מבטיחה לפחות תיקו לשחקן I אם: {תיקו, I מנצח} u(SI,SII) E לכל SII.
- אסטרטגיה מנצחת לשחור ואסטרטגיה שמבטיחה לשחור לפחות תיקו מוגדרות באופן אנלוגי.
משפט קיון (Kuhn)
בכל משחק סופי בעל ידיעה שלמה קיים לפחות שיווי משקל אחד באסטרטגיות טהורות.
ראו גם
לקריאה נוספת
- שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, מאגנס, 2008