הצגת המקור של הדף "המשפט העממי (תורת המשחקים)"

'''המשפט העממי''' ('''Folk theorem''') הוא משפט ב[[תורת המשחקים]], המאפיין את תשלומי שיווי המשקל ב[[משחק חוזר |משחקים חוזרים]].

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

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

במשך מספר שנים משפט זה היה ידוע בקהילה המדעית אף על פי שלא פורסם באף [[מאמר מדעי]]. המשפט העממי למשחקים חוזרים סופיים הוכח על ידי Benoit and Krishna בשנת 1985. המשפט העממי למשחקים חוזרים '''אינסופיים''' הוכח בשנת 1994 על ידי [[ישראל אומן |אומן]] ו[[לויד שפלי |שפלי]].

== מושגי יסוד וסימונים ==
'''המשחק הבסיסי G''' מוגדר על ידי קבוצת השחקנים, קבוצת הפעולות האפשריות לכל שחקן, ופונק' התשלומים של כל שחקן, כלומר:
<math> G = (N, (A_i)_{i\in N}, (u_i)_{i \in N}) </math>.

''' קבוצת וקטורי התשלומים V''' מוגדרת
{<math>x \in R^N : \forall i. x_i \ge \bar{v_i} </math> }
כאשר
<math> \bar{v_i} </math>
הוא ערך ה[[משפט המינימקס |מינמקס]] של שחקן i ב[[הרחבה של משחק לאסטרטגיות מעורבות |אסטרטגיות מעורבות]].

'''F = Feasible set''', קבוצת התשלומים האפשריים במשחק ([[קמור]] התשלומים האפשריים) מוגדרת
{<math>: a \in A=A_1 \times ... \times A_n</math>(
'''Conv''' { U(a.

<math> F \cap V </math>
קבוצת וקטורי התשלומים האפשריים והסבירים פרטית.

<math> \gamma^T (\sigma) </math>
- וקטור התשלומים לשחקנים במשחק ה-T שלבי, כאשר השחקנים משחקים את וקטור האסטרטגיות 
<math> \sigma </math>.

<math> E_T </math>
קבוצת תשלומי שיווי המשקל במשחק ה-T שלבי.
<math> E_T \subseteq F \cap V </math>
שכן כל שחקן יכול להבטיח לעצמו לפחות את ערך המינמקס.

== ניסוח המשפט למשחקים סופיים ==
יהי G [[משחק בצורה תכסיסית |משחק בסיסי בצורה האסטרטגית]]. נניח כי לכל שחקן 
<math> i \in N </math>
יש שיווי משקל 
<math> \beta (i) </math>
במשחק הבסיסי, המקיים
<math> u_i(\beta (i)) > \bar{v_i} </math>
אזי לכל
<math> \epsilon > 0 </math>
קיים
<math> T_0 \in N </math>
כך שלכל
<math> T \ge T_0 </math>
ולכל וקטור תשלומים אפשרי וסביר פרטית
<math> x \in F \cap V </math>
קיים שיווי משקל
<math> \sigma </math>
במשחק ה-T שלבי שהתשלום המתאים לו קרוב עד כדי
<math> \epsilon </math>
ל-x:
<math> \epsilon </math> > 
<math> || \gamma^T (\sigma) - x ||_\infty </math>
.

== רעיון ההוכחה ==

לשם הבנת רעיון ההוכחה, מומלץ לעקוב בעזרת '''הדוגמה''' בהמשך דף זה.

נבחר וקטור x ב-<math> F \cap V </math>.
מכיוון ש-x נמצא ב-F, ניתן להציג אותו כ[[צירוף קמור]] של תאים במטריצה. המקדמים בצירוף הקמור יכולים להיות אי-רציונליים. ניתן לקרב כל מקדם על ידי [[מספר רציונלי]]. במילים אחרות, קיים צירוף קמור של התאים במטריצת התשלומים עם מקדמים רציונליים השווה לווקטור y הקרוב עד כדי אפסילון ל-x. 

נגדיר וקטור אסטרטגיות 
<math> \sigma </math> במשחק ה-T-שלבי
אשר יהיה תלוי ב-3 פרמטרים שלמים R, K, L. 
T שלבי המשחק יחולקו ל-R מחזורים באורך K ולזנב באורך L, כלומר 
T = RK + L.

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

R - מספר המחזורים שישוחקו.

L - מספר השלבים שישוחקו בזנב (יוסבר בהמשך).

וקטור האסטרטגיות <math> \sigma </math> בנוי באופן הבא: 

1. במהלך RK השלבים הראשונים השחקנים משחקים בצורה מחזורית אותה סדרה של K וקטורי פעולות. בכל מחזור, מספר הפעמים ש-<math> \sigma </math> משחקת כל אחד מתאי המטריצה שווה למונה המתאים בצירוף הקמור שנותן את y. כך, בכל מחזור, ממוצע התשלומים קרוב עד כדי אפסילון ל-x.

2. אם שחקן סוטה באחד מ-RK השלבים הראשונים, שאר השחקנים יענישו אותו על ידי '''אסטרטגיית הענישה''' הבאה:

אם שחקן מסוים סוטה בשלב t, החל משלב t+1 שאר השחקנים ישחקו וקטור אסטרטגיות המבטיח שתוחלת התשלום של שחקן זה בכל שלב תהיה לכל היותר ערך המינמקס שלו באסטרטגיית מעורבות.

3. ב-L השלבים האחרונים ('''הזנב''') השחקניו ישחקו בצורה מחזורית את שיוויי המשקל שיווי משקל <math> \beta(i)</math>במשחק הבסיסי.

אם L קטן יחסית ל-RK, ממוצע התשלומים לפי 
<math> \sigma </math> יהיה קרוב ל-x עד כדי אפסילון.

נראה עתה שזהו ש"מ. אכן, בזנב לשום שחקן לא כדאי לסטות, כי לאורך הזנב השחקנים משחקים בכל שלב ש"מ במשחק החד-שלבי. גם לאורך RK השלבים הראשונים לא כדאי לשום שחקן לסטות, שכן על ידי סטייה יכול שחקן להרוויח לכל היותר 2KM (בכל אחד מ-K השלבים במחזור שבו השחקן סטה הוא יכול להרוויח לכל היותר M, כאשר M הוא [[ערך מוחלט|הערך המוחלט]] המקסימלי של תשלום במטריצת המשחק), ולאחר מכן השחקן לא ירוויח (מכיוון שיענש על ידי השחקנים האחרים, ויקבל לכל היותר את ערך המינמקס שלו); אם הזנב ארוך דיו, ניתן לוודא שהענישה אפקטיבית ושהסטייה לא תהיה כדאית.

== המשפט העממי למשחקים אינסופיים ==
'''ניסוח המשפט''' - בכל משחק חוזר אינסופי, קבוצת תשלומי שיווי המשקל היא
<math> F \cap V </math>

'''רעיון הוכחה''' - נראה כי כל וקטור תשלומים x ב
<math> F \cap V </math>
הוא ש"מ במשחק האינסופי.

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

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

אם x אינו ניתן להצגה כממוצע משוקלל עם מקדמים רציונליים, נקרב את x על ידי הצגות עם מקדמים רציונליים. כלומר, לכל k טבעי, נמצא מקדמים רציונליים
<math> (\lambda_a(k))_{a \in A} </math>
כך שמתקיים:

<math> | x - \sum_{a \in A} \lambda_a(k)u(a) | < 1/k </math>

במקרה כזה, בתוכנית הבסיסית ישחקו השחקנים בבלוקים, כאשר בבלוק ה-k יש k שלבים:

בבלוק הראשון ישחקו כדי לממש את הממוצע
<math> \sum_{a \in A} \lambda_a(1)u(a) </math>, בבלוק השני 
<math> \sum_{a \in A} \lambda_a(2)u(a) </math>,
וכך הלאה. 

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

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

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

== דוגמה ==
נסתכל על המשחק הבא:
{| class="wikitable"
|-
| '''R''' || '''L''' || 
|-
| 2,7|| 6,6 || '''T'''
|-
| 0,0 || 7,2|| '''B'''
|}

ערך המינמקס של משחק זה הוא (2,2) - אסטרטגיית המינמקס של שחקן 1 במשחק הבסיסי היא לשחק B, כך שחקן 2 ירוויח לכל היותר 2, אסטרטגיית המינמקס של שחקן 2 במשחק הבסיסי היא לשחק R, כך שחקן 1 ירוויח לכל היותר 2, ולכן ערך המינמקס של המשחק הבסיסי הוא (2,2).

נרצה לקחת וקטור ב-
<math> F \cap V </math>
ונראה שניתן לקרב אותו כתשלום ש"מ במשחק עבור T מספיק גדול.

נבחר את הווקטור
(3.5,4.75) = (6,6)0.5 + (0,0)0.25 + (2,7)0.25 

נבנה "מחזור" בן 4 שלבים, בהם נשחק את הפעולות כך שיתאימו לוקטור הנ"ל, כלומר המחזור יראה כך:
{| class="wikitable"
|-
| 4 || 3 || 2 || 1 || '''שלב במחזור'''
|-
| T || B || T || T || '''שחקן 1'''
|-
| R || R || L || L || '''שחקן 2'''
|}
נסתכל על זוג האסטרטגיות הבא, בהם השחקנים ישחקו אסטרטגיות לפי המחזור שתוכנן, כלומר:

{| class="wikitable"
|-
| 100 || 99 || 98 || 97 || ...... || 8 || 7 || 6 || 5 || 4 || 3 || 2 || 1 || '''שלב במשחק החוזר'''
|-
| T || B || T || T || ...... || T || B || T || T || T || B || T || T || '''אסטרטגיה של שחקן 1'''
|-
| R || R || L || L || ...... || R || R || L || L || R || R || L || L || '''אסטרטגיה של שחקן 2'''
|}

ממוצע התשלומים הוא בדיוק (3.5,4.75), כדי למנוע סטיות נאיים בהענשה לערך המינמקס (בדוגמה - אם שחקן 1 סוטה בשלב ה-t, שחקן 2 ישחק R מהשלב ה-t+1).

כפי שנכתב בהוכחה, עדיין יש כדאיות סטייה בשלב ה-99 (לדוגמה - בשלב זה, שחקן 1 יחליט לשחק T במקום B, ממהלך זה ירוויח 2 לעומת 0, שחקן 2 לא יוכל להעניש אותו בשלב ה-100, שכן שחקן 1 יכול להבטיח לעצמו את ערך המינמקס באסטרטגיות מעורבות שהוא 2, כפי שהיה אמור לקבל ממילא לפי תוכנית המשחק), לכן נוסיף זנב המכיל 2 ש"מ לשחקנים, כך שיקבלו יותר מתשלום המינמקס, כלומר:

{| class="wikitable"
|-
|'''102''' || '''101''' || 100 || 99 || 98 || 97 || ...... || 8 || 7 || 6 || 5 || 4 || 3 || 2 || 1 || '''שלב במשחק החוזר'''
|-
|B|| T|| T || B || T || T || ...... || T || B || T || T || T || B || T || T || '''אסטרטגיה של שחקן 1'''
|-
|L|| R|| R || R || L || L || ...... || R || R || L || L || R || R || L || L || '''אסטרטגיה של שחקן 2'''
|}

זהו ש"מ מכיוון שבמחזור (4 שלבים) אם שחקן יסטה, הוא ירוויח לכל היותר 3, אך רווח זה קטן מההפסד שיגרם לו בגין הענישה (מינוס 5, במקום 7 ירוויח 2).

נשאר להראות כי ממוצע התשלומים (ללא סטיות) קרוב ל-(3.5,4.75), הממוצע הוא: 
<math>
{100(3.5,4.75) + (2,7) + (7,2) \over 102}
</math>
כלומר עבור
<math>
\epsilon > {1 \over 102}
</math>
מרחק וקטור התשלומים מ-(3.5,4.75) קטן מ-
<math>
\epsilon
</math>
כנדרש.

== ראו גם ==
* [[משפט המינימקס]]
* [[משחק חוזר]]
* [[שיווי משקל נאש]]
* [[משחק סכום אפס]]

== לקריאה נוספת ==
*{{צ-ספר|מחבר=שמואל זמיר, [[מיכאל משלר]], [[אילון סולן]]|שם=תורת המשחקים|מו"ל=[[הוצאת מאגנס|מאגנס]]|שנת הוצאה=2008|מקום הוצאה=ירושלים|ISBN=9654932946|עמ=528-552}}

== קישורים חיצוניים ==
* Ratliff, J. (1996). ''[http://www.virtualperfection.com/gametheory/5.3.FolkTheoremSampler.1.0.pdf A Folk Theorem Sampler]''. Great introductory notes to the Folk Theorem.

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