משחק אינסופי

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

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

תכונות

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

היסטוריות

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

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

אסטרטגיות במשחק אינסופי

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

אוסף כל האסטרטגיות של שחקן i במשחק אינסופי יסומן ב- $\Sigma _{i}^{\infty }$.

המודל

משחק חוזר מבוסס על משחק חד שלבי שאותו השחקנים משחקים שוב ושוב. נניח שמשחק זה נתון בצורה אסטרטגית על די $\Gamma =(N,(S_{i})_{i\in N},(u_{i})_{i\in N})$ כאשר $N={1,2,...n}$ היא קבוצת השחקנים, $S_{i}$ היא קבוצת הפעולות של שחקן $i$ , ו- $R\rightarrow u_{i}:S$ היא פונקציית התשלומים החד-שלבית של שחקן $i$ , כאשר $S=s_{1}\times s_{2}\times ...\times s_{n}$ היא קבוצת וקטורי הפעולות, אזי המשחק החוזר האינסופי $\Gamma _{\infty }$ המתאים ל $\Gamma$ הוא משחק מעל קבוצת השחקנים $N$ , שבו קבוצת האסט' לשחקן $i$ היא $\Sigma _{i}^{\infty }$ .
נסמן ב $H(\infty )$ את אוסף כל מהלכי המשחק האפשריים במשחק האינסופי: $H(\infty )=S^{N}$
איבר כללי בקבוצה זו הוא סדרה אינסופית $(s^{1},s^{2},...)$ של וקטורי פעולות, כאשר $s^{t}$ הוא וקטור הפעולות של השחקנים בשלב $t$ . וקטור האסטרטגיות $\tau$ של השחקנים משרה התפלגות $P_{\tau }$ על אוסף מהלכי המשחק האפשריים. ה- $\sigma$ -אלגברה על המרחב $H(\infty )$ היא ה- $\sigma$ -אלגברה הנפרשת על ידי הקבוצות הגליליות, שהן הקבוצות מהצורה הבאה:
$C(s^{1},s^{2},...,s^{t}):={(s^{1},s^{2},...):s^{1}=s^{1},s^{2}=s^{2},...,s^{t}=s^{t}}$
כלומר, קבוצת כל הסדרות האינסופיות בעלות אותן $t$ קואורדינטות ראשונות.
נסמן ב $E_{\tau }$ את אופרטור התוחלת המתאים להסתברות $P_{\tau }$ .
לכל שלב $t\in N$ ולכל שחקן $i\in N$ נסמן ב $u_{i}^{t}$ את התשלום של שחקן $i$ בשלב $t$ .

שיווי משקל

וקטור אסטרטגיות $\tau ^{*}$ נקרא שיווי משקל (במשחק האינסופי $\Gamma _{\infty }$ ) והווקטור $x\in R^{N}$ נקרא תשלום שיווי משקל אם בהסתברות 1 לפי $P_{\tau ^{*}}$ לכל שחקן $i$ הגבול:
$\lim _{T\rightarrow \infty }{\frac {1}{T}}\sum _{t=1}^{T}u_{i}^{t}$
קיים ושווה ל $x_{i}$ , ולכל אסטרטגיה של שחקן $i$ מתקיים $E_{\tau ^{*}}(\lim _{T\rightarrow \infty }{\frac {1}{T}}\sum _{t=1}^{T}u_{i}^{t})=x_{i}\geq E_{\tau ^{*},\tau _{-i}^{*}}(\limsup _{T\rightarrow \infty }{\frac {1}{T}}\sum _{t=1}^{T}u_{i}^{t})$
במילים, וקטור אסטרטגיות $\tau ^{*}$ הוא שיווי משקל עם תשלום $x$ אם ממוצע התשלומים תחת $\tau ^{*}$ שואף ל- $x$ בהסתברות 1, ואף שחקן אינו יכול להרוויח על ידי סטייה.

המשפט העממי

המשפט העממי עבור משחק אינסופי $\Gamma _{\infty }$ קובע: אוסף תשלומי שיווי המשקל ב- $\Gamma _{\infty }$ הוא הקבוצה $F\cap V$ , כאשר $F$ הוא הקמור של כל התשלומים החד-שלביים האפשריים, ו- $V$ קבוצת התשלומים הסבירים פרטית.

ראו גם

• משחק T שלבי
• משחק חוזר
• המשפט העממי

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, עמ' 528-552, מסת"ב 9654932946