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

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

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

משחק חוזר בנוי על משחק בסיסי המגדיר אותו, כלומר, המשחק שאותו השחקנים משחקים שוב ושוב. נכנה את המשחק הבסיסי בשם "המשחק החד-שלבי", ונניח שהוא נתון בצורה אסטרטגית על ידי ${\displaystyle \Gamma =(N,(S_{i})_{i\in N},(u_{i})_{i\in N})}$ כאשר ${\displaystyle N=\{1,2,...,n\}}$ היא קבוצת השחקנים, ${\displaystyle S_{i}}$ היא קבוצת הפעולות של שחקן ${\displaystyle _{i}}$, ו-${\displaystyle u_{i}:S\rightarrow R}$ היא פונקציית התשלומים החד-שלבית של שחקן i, כאשר ${\displaystyle S=S_{1}\times S_{2}\times \cdot \cdot \cdot \times S_{n}}$ היא קבוצת וקטורי הפעולות. במשחק חוזר נפגשים אותם השחקנים שוב ושוב מספר פעמים, ובכל פעם משחקים את אותו משחק בצורה אסטרטגית. כדי לתאר באופן מלא משחק חוזר, יש לומר גם כמה שלבים המשחק נמשך. בנוסף, מכיוון שבכל שלב השחקנים מקבלים תשלום, יש לציין כיצד השחקנים מעריכים את סדרת התשלומים שהם מקבלים. כלומר, כיצד כל שחקן משווה בין סדרת תשלומים אחת לסדרת תשלומים אחרת.

מכיוון שבמשחק חוזר השחקנים נפגשים פעם אחר פעם, הם צוברים אינפורמציה אחד על השני ככל שהמשחק מתקדם. המידע העומד לרשותו של כל שחקן בשלב ${\displaystyle t+1}$ הוא הפעולות ששיחקו כל השחקנים ב- ${\displaystyle t}$ השלבים הראשונים של המשחק. לכן נגדיר לכל ${\displaystyle t\geq 0}$ את אוסף ההיסטוריות ה- t שלביות כ: ${\displaystyle H(t)=S^{t}=S\times S\times \cdot \cdot \cdot \times S}$ ( t פעמים)

עבור ${\displaystyle t=0}$ אנו מזהים ${\displaystyle H(0)=\{\emptyset \}}$, כאשר ${\displaystyle \emptyset }$ היא ההיסטוריה בתחילת המשחק, שאינה מכילה אף פעולה. היסטוריה ב- ${\displaystyle H(t)}$ תסומן לעיתים ב-${\displaystyle h}$ולעיתים ב- ${\displaystyle (s^{1},s^{2},...,s^{t})}$, כאשר ${\displaystyle s^{j}=(s_{i}^{j})_{i\in N}}$ הוא וקטור הפעולות ששוחק בשלב ${\displaystyle j}$.

אסטרטגיה עבור שחקן ${\displaystyle i}$ היא תוכנית פעולה שאומרת לשחקן איזו פעולה מעורבת הוא אמור לשחק אחרי כל היסטוריה אפשרית.

אסטרטגית התנהגות עבור שחקן ${\displaystyle i}$ במשחק ה- T שלבי היא פונקציה המתאימה לכל היסטוריה באורך קטן מ-T פעולה מעורבת : ${\displaystyle \tau _{i}:\bigcup _{t=0}^{T-1}H(t)\rightarrow \Sigma _{i}}$ קבוצת אסטרטגיות ההתנהגות של שחקן ${\displaystyle i}$ המשחק ה-T שלבי מסומנת ב${\displaystyle \Sigma _{i}^{T}}$.

המשפט העממי, או The folk theorem, הוא משפט חשוב בנושא משחקים חוזרים. נניח כי לכל שחקן ${\displaystyle i\in N}$ יש שיווי משקל ${\displaystyle \beta (i)}$ במשחק החד-שלבי ${\displaystyle (N,(S_{i})_{i\in N},(u_{i})_{i\in N})}$ המקיים ${\displaystyle u_{i}(\beta (i))>{\bar {v}}_{i}}$. אזי לכל ${\displaystyle \epsilon >0}$ קיים ${\displaystyle T_{0}\in N}$ כך שלכל ${\displaystyle T\geq T_{0}}$ ולכל וקטור תשלומים אפשרי וסביר פרטית ${\displaystyle x\in F\cap V}$ קיים שיווי משקל ${\displaystyle \tau }$ במשחק ה-T שלבי שהתשלום המתאים לו קרוב עד כדי ${\displaystyle \epsilon }$ל- ${\displaystyle x}$:

${\displaystyle \|\gamma ^{T}(\tau )-x\|_{\infty }<\epsilon }$

בהגדרת המשחק ה-T שלבי הנחנו כי כל שחקן מנסה למקסם את תוחלת סכום התשלומים שהוא מקבל בכל שלבי המשחק. בפרט, אם משה מקבל עשרת אלפים שקלים היום, ויעקב מקבל עשרת אלפים שקלים בעוד שנה, הנחנו כי מצבם של שני השחקנים זהה. במציאות, הנחה זו אינה מתקיימת: אם משה ישקיע את כספו בבנק, כסף זה יצבור ריבית (נאמר של 5%), ולכן בעוד שנה יהיו למשה 10,500 שקלים - מצבו יהיה טוב יותר ממצבו של יעקב. לכן במודלים כלכליים מקובל להניח כי השחקנים אינם ממקסמים את סכום התשלומים שלהם, אלא סכום מהוון של התשלומים, הלוקח בחשבון את הריבית שאותה יכולים השחקנים לקבל עבור כספם.

הגדרה

יהי ${\displaystyle \Gamma =(N,(S_{i})_{i\in N},(u_{i})_{i\in N})}$ משחק חד-שלבי ויהי ${\displaystyle \lambda \in (0,1)}$. המשחק המהוון ${\displaystyle \Gamma _{\lambda }}$ (עם קבוע היוון ${\displaystyle \lambda }$) המתאים ל-${\displaystyle \Gamma }$ הוא המשחק ${\displaystyle \Gamma _{\lambda }=(N,(\Sigma _{i}^{T})_{i\in N},(\gamma _{i}^{\lambda })_{i\in N})}$.

מההגדרה נובע כי וקטור אסטרטגיות ${\displaystyle \tau }$ הוא שיווי משקל ב-${\displaystyle \Gamma _{\lambda }}$ אם לכל שחקן ${\displaystyle i\in N}$ ולכל אסטרטגיה ${\displaystyle \tau _{i}^{'}}$ שלו מתקיים:

${\displaystyle \gamma _{i}^{\lambda }(\tau )\geq \gamma _{i}^{\lambda }(\tau _{i}^{'},\tau _{-i})}$.

במקרה כזה, הווקטור הוא תשלום שיווי משקל ב-${\displaystyle \Gamma _{\lambda }}$. נוח כאן להניח כי המשחק החוזר הוא אינסופי.

תשלום מהוון

יהי ${\displaystyle \lambda \in (0,1)}$ מספר ממשי, ויהי ${\displaystyle \tau =(\tau _{i})_{i\in N}}$ וקטור אסטרטגיות במשחק האינסופי. התשלום המהוון תחת ${\displaystyle \tau }$ לשחקן ${\displaystyle i}$ הוא:

${\displaystyle \gamma _{i}^{\lambda }(\tau )=E_{\tau }[(1-\lambda )\sum _{t=1}^{\infty }\lambda ^{t-1}u_{i}^{t}]}$

הקבוע ${\displaystyle \lambda }$ נקרא קבוע היוון (discount factor).

הסבר

החזקה ${\displaystyle \lambda ^{t-1}}$ מביעה את העובדה שתשלום של 1 מחר, שקול לתשלום של ${\displaystyle \lambda }$ היום, תשלום של 1 מחרתיים שקול לתשלום של ${\displaystyle \lambda ^{2}}$ היום, וכו'. מכיוון ש-${\displaystyle (1-\lambda )\sum _{t=1}^{\infty }\lambda ^{t-1}=1}$, התשלום המהוון הוא ממוצע משוקלל של התשלומים היומיים, עם משקלות היורדים בקצב גאומטרי. כאשר ${\displaystyle \lambda }$ קרוב לאפס, ${\displaystyle 1-\lambda }$ (המשקל של התשלום בשלב הראשון) גדול יחסית ל-${\displaystyle \lambda }$ (המשקל של התשלומים בכל שאר השלבים), ולכן התשלום בשלב הראשון חשוב ביותר: השחקן חושב על היום, ומוכן לוותר על תשלומים גבוהים בעתיד. כאשר ${\displaystyle \lambda }$ קרוב ל-1 המשל של שלב ${\displaystyle t}$ קרוב יותר לזה של שלב ${\displaystyle t+1}$, ולכן השחקן "סבלני" - הוא יהיה מוכן לוותר בשלב מסוים כדי לקבל רווח גדול יותר בעתיד הקרוב.

הכפל ב-${\displaystyle (1-\lambda )}$הוא גורם נירמול המבטיח שנקבל מספר המבטא מעין "תוחלת תשלום לשלב".

לכל ${\displaystyle \epsilon >0}$ קיים ${\displaystyle \lambda _{0}\in (0,1)}$ ולכל וקטור ${\displaystyle x\in F\cap V}$ קיים שיווי משקל ${\displaystyle \tau }$ ב-${\displaystyle \Gamma _{\tau }}$ המקיים:

${\displaystyle \|\gamma ^{\lambda }(\tau )-x\|_{\infty }<\epsilon }$

דילמת האסיר החוזרת

דילמת האסיר היא המשחק החד שלבי עם שני שחקנים הנתון על ידי מטריצת התשלומים המופיעה בתרשים הבא:

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

מה הם שיוויי המשקל במשחק זה? בדיקה ישירה מראה שוקטור האסטרטגיות שבו השחקנים חוזרים על שיווי המשקל החד-שלבי (D,D) פעמיים הוא שיווי משחק במשחק הדו-שלבי. זהו מקרה פרטי של טענה כללית יותר האומרת שכל וקטור אסטרטגיות שבו, בכל שלב, השחקנים משחקים שיווי משקל במשחק החד-שלבי, הוא שיווי משקל במשחק ה-T-שלבי. במקרה שלפנינו, נראה כי בכל שיווי משקל במשחק החוזר הדו-שלבי השחקנים משחקים (D,D) בשני השלבים. אכן, נניח בשלילה שיש שיווי משקל שבו בהסתברות חיובית ישנו שלב שבו השחקנים אינם משחקים (D,D). יהי ${\displaystyle t\in {1,2}}$ השלב האחרון שבו השחקנים בהסתברות חיובית אינם משחקים (D,D). נראה כי אסטרטגיה כזו אינה יכולה להיות שיווי משקל.

מקרה ראשון: t = 1. נתבונן באסטרטגיה של שחקן 1 שבה בשני השלבים הוא משחק D. נראה כי התשלום לשחקן 1 עלה. מכיוון ש D שולטת חזק על C, התשלום לשחקן 1 בשלב הראשון עלה. מכיוון שלאחר שלב t השחקנים היו אמורים לשחק (D,D) (מכיוון ש-tהוא השלב האחרון שבו לא משחקים (D,D)), התשלום לשחקן 1 בשלב השני היה אמור להיות 1. מכיוון שבאסטרטגיה החדשה הוא משחק בשלב השני D, הרי שהתשלום לו הוא 1 או 4 (תלוי אם שחקן 2 משחק D או C), ובכל מקרה הוא אינו מפסיד בשלב השני. לכן סכום התשלומים של שחקן 1 במשחק עלה.

מקרה שני: t = 2. נתבונן באסטרטגיה של שחקן 1 שבה הוא משחק בשלב הראשון כפי שמורה לו האסטרטגיה המקורית, ובשלב השני הוא משחק D. התשלום לשחקן 1 בשלב הראשון אינו משתנה, אך מכיוון ש-D שולטת על C, התשלום לשחקן 1 בשלב השני עלה. לכן בסך הכל סכום התשלומים של שחקן 1 עלה.

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, מאגנס, 2008