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

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

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

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

הוא ערך המינמקס של שחקן i באסטרטגיות מעורבות.
F = Feasible set, קבוצת התשלומים האפשריים במשחק (קמור התשלומים האפשריים) מוגדרת
{(
Conv { U(a.

קבוצת וקטורי התשלומים האפשריים והסבירים פרטית.

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

קבוצת תשלומי שיווי המשקל במשחק ה-T שלבי.

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

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

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

יש שיווי משקל 

במשחק הבסיסי, המקיים

אזי לכל

קיים

כך שלכל

ולכל וקטור תשלומים אפשרי וסביר פרטית

קיים שיווי משקל

במשחק ה-T שלבי שהתשלום המתאים לו קרוב עד כדי

ל-x:
 > 

.

רעיון ההוכחה

לשם הבנת רעיון ההוכחה, מומלץ לעקוב בעזרת הדוגמה בהמשך דף זה.
נבחר וקטור x ב-.
מכיוון ש-x נמצא ב-F, ניתן להציג אותו כצרוף קמור של תאים במטריצה. המקדמים בצרוף הקמור יכולים להיות אי-רציונליים. ניתן לקרב כל מקדם על ידי מספר רציונלי. במילים אחרות, קיים צרוף קמור של התאים במטריצת התשלומים עם מקדמים רציונליים השווה לווקטור y הקרוב עד כדי אפסילון ל-x. 
נגדיר וקטור אסטרטגיות 
 במשחק ה-T-שלבי
אשר יהיה תלוי ב-3 פרמטרים שלמים R, K, L. 
T שלבי המשחק יחולקו ל-R מחזורים באורך K ולזנב באורך L, כלומר 
T = RK + L.
K - אורך המחזור, יהיה הכפולה המשותפת המינימלית של מכני המקדמים של המשקלות הרציונליים בהצגה הנזכרת לעיל.
R - מספר המחזורים שישוחקו.
L - מספר השלבים שישוחקו בזנב (יוסבר בהמשך).
וקטור האסטרטגיות  בנוי באופן הבא: 
1. במהלך RK השלבים הראשונים השחקנים משחקים בצורה מחזורית אותה סדרה של K וקטורי פעולות. בכל מחזור, מספר הפעמים ש- משחקת כל אחד מתאי המטריצה שווה למונה המתאים בצרוף הקמור שנותן את y. כך, בכל מחזור, ממוצע התשלומים קרוב עד כדי אפסילון ל-x.
2. אם שחקן סוטה באחד מ-RK השלבים הראשונים, שאר השחקנים יענישו אותו על ידי אסטרטגיית הענישה הבאה:
אם שחקן מסוים סוטה בשלב t, החל משלב t+1 שאר השחקנים ישחקו וקטור אסטרטגיות המבטיח שתוחלת התשלום של שחקן זה בכל שלב תהיה לכל היותר ערך המינמקס שלו באסטרטגיית מעורבות.
3. ב-L השלבים האחרונים (הזנב) השחקניו ישחקו בצורה מחזורית את שיוויי המשקל שיווי משקל במשחק הבסיסי.
אם L קטן יחסית ל-RK, ממוצע התשלומים לפי 
 יהיה קרוב ל-x עד כדי אפסילון.
נראה עתה שזהו ש"מ. אכן, בזנב לשום שחקן לא כדאי לסטות, כי לאורך הזנב השחקנים משחקים בכל שלב ש"מ במשחק החד-שלבי. גם לאורך RK השלבים הראשונים לא כדאי לשום שחקן לסטות, שכן על ידי סטייה יכול שחקן להרוויח לכל היותר 2KM (בכל אחד מ-K השלבים במחזור שבו השחקן סטה הוא יכול להרוויח לכל היותר M, כאשר M הוא הערך המוחלט המקסימלי של תשלום במטריצת המשחק), ולאחר מכן השחקן לא ירוויח (מכיוון שיענש על ידי השחקנים האחרים, ויקבל לכל היותר את ערך המינמקס שלו); אם הזנב ארוך דיו, ניתן לוודא שהענישה אפקטיבית ושהסטייה לא תהיה כדאית.

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

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

הוא ש"מ במשחק האינסופי.
אם x ניתן להצגה כממוצע משוקלל של וקטורי תשלומים עם מקדמים רציונליים, נגדיר תוכנית בסיסית (אינסופית) בה כל אחד מהשחקנים משחק באופן מחזורי פעולות אשר יביאו לכך שממוצע התשלומים יהיה בדיוק x. (בדוגמה - שחקן 1 ישחק באופן מחזורי את וקטור הפעולות {T,T,B,T}, שחקן 2 ישחק באופן מחזורי את וקטור הפעולות {L,L,R,R}), ונוסיף לכל אסטרטגיה את איום הענישה (בו כל השחקנים מענישים לערך המינמקס באסטרטגיות מעורבות, שחקן שסטה).
בדיקה ישירה מראה כי x הוא ש"מ במשחק האינסופי.
אם x אינו ניתן להצגה כממוצע משוקלל עם מקדמים רציונליים, נקרב את x על ידי הצגות עם מקדמים רציונליים. כלומר, לכל k טבעי, נמצא מקדמים רציונליים

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