משתמש:Israelkr/ המשפט העממי (תורת המשחקים)

המשפט העממי (The Folk theorem) הינו משפט בתורת המשחקים, המאפיין את תשלומי שיווי המשקל במשחקים חוזרים. המשפט אומר כי לכל וקטור תשלומים אפשרי וסביר x, קיים שיווי משקל במשחק החוזר אשר התשלום המתאים לו קרוב עד כדי אפסילון ל-x. במשך מספר שנים משפט זה היה ידוע בקהילה המדעית למרות שלא פורסם באף מאמר מדעי. המשפט העממי הוכח ע"י Benoit and Krishna בשנת 1985. כיום המשפט מיוחס לאומן ושפלי אשר ניסחו את המשפט העממי למשחק האינסופי בשנת 1994.

מושגי יסוד וסימונים

קבוצת וקטורי התשלומים V מוגדרת {$x\in R^{N}:\forall i.x_{i}\leq {\bar {v_{i}}}$ } כאשר ${\bar {v_{i}}}$ הינו ערך המינמקס.

F = Feasible set, קבוצת התשלומים האפשריים במשחק (קמור התשלומים האפשריים) מוגדרת {$:a\in A=A_{1}\times ...\times A_{n}$( Conv { U(a

$F\cap V$ קבוצת וקטורי התשלומים האפשריים והסבירים פרטית

$\gamma ^{T}(\sigma )$ - וקטור התשלומים לשחקנים במשחק ה-T שלבי, כאשר השחקנים משחקים את וקטור האסטרטגיות $\sigma$

$E_{T}$ קבוצת תשלומי שיווי המשקל במשחק ה-T שלבי. $E_{T}\subseteq F\cap V$ שכן כל שחקן יכול להבטיח לעצמו לפחות את ערך המינמקס

ניסוח המשפט למשחקים סופיים

יהי G משחק בסיסי בצורה האסטרטגית. נניח כי לכל שחקן $i\in N$ יש שיווי משקל $\beta (i)$ במשחק החד שלבי, המקיים $u_{i}(\beta (i))>{\bar {v_{i}}}$ אזי לכל $\epsilon >0$ קיים $T_{0}\in N$ כך שלכל $T\geq T_{0}$ ולכל וקטור תשלומים אפשרי וסביר פרטית $x\in F\cap V$ קיים שיווי משקל $\sigma$ במשחק ה-T שלבי שהתשלום המתאים לו קרוב עד כדי $\epsilon$ ל-x: $\epsilon$ > $||\gamma ^{T}(\sigma )-x||_{\infty }$

רעיון ההוכחה

אינטואיציה להוכחת המשפט - כל מה שסביר במשחק הוא גם אפשרי (פרט לשלילת הברור, אין אפשרות לניבוי). נרצה לקחת וקטור ב- $F\cap V$ ונראה שניתן לקרב אותו עד כדי אפסילון כתשלום ש"מ במשחק עבור T מספיק גדול. שחקן i ישחק בתורו אסטרטגיית $\sigma _{i}$ כך ששילוב האסטרטגיות יוביל לוקטור התשלומים שבחרנו. מצב זה כמובן אינו שיווי משקל (מכיוון שיש סטיות כדאיות) לכן על מנת למנוע סטיות - נאיים על כלל השחקנים:

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

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

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

המשפט העממי למשחקים אינסופיים

ניסוח המשפט - בכל משחק חוזר אינסופי, קבוצת תשלומי שיווי המשקל היא $F\cap V$

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

נוסיף את איום הענישה (בו כל השחקנים מענישים למינמקס, שחקן שסטה). נגדיר $Z^{l}$ שואף ל-X כך ש $Z^{l}$ ממוצע משוקלל של תשלומים עם מקדמים רציונאליים. תחילה נשחק את $Z^{1}$ אח"כ $Z^{2}$ וכך הלאה. אם מישהו סוטה כאמור מעלה נעניש אותו באסטרטגיית המינמקס.

בדיקה ישירה מראה כי קיבלנו שיווי משקל במשחק האינסופי.

ראו גם

• משפט המינימקס
• משחק חוזר
• שיווי משקל נאש

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים (עמודים 528-552), הוצאת מאגנס, ירושלים.

קישורים חיצוניים

• Ratliff, J. (1996). A Folk Theorem Sampler. Great introductory notes to the Folk Theorem.