במקרה כזה, הווקטור הוא תשלום שיווי משקל ב-formula_38.
נוח כאן להניח כי המשחק החוזר הוא אינסופי.
תשלום מהוון
יהי formula_37 מספר ממשי, ויהי formula_49 וקטור אסטרטגיות במשחק האינסופי. התשלום המהוון תחת formula_32 לשחקן formula_19 הוא:
formula_52
הקבוע formula_39 נקרא קבוע היוון (discount factor).
הסבר
החזקה formula_54 מביעה את העובדה שתשלום של 1 מחר, שקול לתשלום של formula_39 היום, תשלום של 1 מחרתיים שקול לתשלום של formula_56 היום, וכו'. מכיוון ש-formula_57, התשלום המהוון הוא ממוצע משוקלל של התשלומים היומיים, עם משקלות היורדים בקצב גאומטרי. כאשר formula_39 קרוב לאפס, formula_59 (המשקל של התשלום בשלב הראשון) גדול יחסית ל-formula_39 (המשקל של התשלומים בכל שאר השלבים), ולכן התשלום בשלב הראשון חשוב ביותר: השחקן חושב על היום, ומוכן לוותר על תשלומים גבוהים בעתיד. כאשר formula_39 קרוב ל-1 המשל של שלב formula_8 קרוב יותר לזה של שלב formula_7, ולכן השחקן "סבלני" - הוא יהיה מוכן לוותר בשלב מסוים כדי לקבל רווח גדול יותר בעתיד הקרוב.
הכפל ב-formula_64הוא גורם נירמול המבטיח שנקבל מספר המבטא מעין "תוחלת תשלום לשלב".
המשפט העממי עבור המשחק המהוון.
לכל formula_28 קיים formula_66 ולכל וקטור formula_31 קיים שיווי משקל formula_32 ב-formula_69 המקיים:
formula_70
דוגמה למשחק חוזר.
דילמת האסיר החוזרת
דילמת האסיר היא המשחק החד שלבי עם שני שחקנים הנתון על ידי מטריצת התשלומים המופיעה בתרשים הבא:
לשני השחקנים, הפעולה D שולטת חזק על הפעולה C, ולכן במשחק החד שלבי שיווי המשקל היחיד הוא (D,D).
נתבונן עתה במקרה שבו השחקנים משחקים את המשחק פעמיים, ובפעם השנייה הם יודעים מה שיחקו בפעם הראשונה. בתיאור המצב כמשחק בצורה רחבה יש בעץ קבוצות ידיעה מכיוון שבכל שלב השחקנים בוחרים פעולות באופן סימולטני. בתרשים הבא, בכל עלה מופיע סך התשלומים בשני השלבים של השחקנים.
מה הם שיוויי המשקל במשחק זה?
בדיקה ישירה מראה שוקטור האסטרטגיות שבו השחקנים חוזרים על שיווי המשקל החד-שלבי (D,D) פעמיים הוא שיווי משחק במשחק הדו-שלבי. זהו מקרה פרטי של טענה כללית יותר האומרת שכל וקטור אסטרטגיות שבו, בכל שלב, השחקנים משחקים שיווי משקל במשחק החד-שלבי, הוא שיווי משקל במשחק ה-T-שלבי.
במקרה שלפנינו, נראה כי בכל שיווי משקל במשחק החוזר הדו-שלבי השחקנים משחקים (D,D) בשני השלבים. אכן, נניח בשלילה שיש שיווי משקל שבו בהסתברות חיובית ישנו שלב שבו השחקנים אינם משחקים (D,D). יהי formula_71 השלב האחרון שבו השחקנים בהסתברות חיובית אינם משחקים (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 עלה.
משחק אינסופי
בתורת המשחקים, משחק חוזר אינסופי הוא מודל פשוט של משחקים בו השחקנים משחקים פעם אחר פעם אותו משחק חד שלבי. בדומה למשחק חוזר T שלבי, הפעולות האפשריות לשחקנים, כמו גם פונקציית התשלומים שלהם, אינן משתנות עם הזמן, ואינן תלויות במהלך המשחק. לעומת משחקים חד-שלביים, הממדלים מצבים שבהם האינטראקציה בין השחקנים היא חד-פעמית, ולאחר שהיא מסתיימת, אין לה כל השפעה על אינטראקציות נוספות בין השחקנים, במקרים רבים האינטראקציה בין השחקנים מתמשכת לאורך זמן, ומכיוון שהשחקנים חוזרים ומשחקים אחד עם השני פעם אחר פעם, עולות תופעות התנהגותיות שונות במשחק חוזר.
המוטיבציות לבחינת משחקים אינסופיים הן:
א. נוחות מתמטית.
ב. לעיתים קשה לאמוד את מספר השלבים במשחק חוזר, או שמספר השלבים אינו ידוע. במקרים אלו, ניתן לקרב משחק בעל מספר גדול אך לא ידוע של שלבים כמשחק בעל אינסוף שלבים.
ג. לעיתים, לסופיות של משחק חוזר ארוך לא משפיעה על שיקולים אסטרטגיים, על כן ניתן לבחון אותו כמשחק חוזר אינסופי.
תכונות.
• אורך המשחק אינו ידוע מראש: בעל חנות טניס אינו יודע אם ומתי ימכור את חנותו, ושחקני טניס אינם יודעים מתי יפסיקו לשחק טניס, או מתי יעברו לגור בעיר אחרת.
• בניגוד למשחק חד שלבי, היסטוריית הפעולות של שחקן משפיעה על התנהגות שאר השחקנים בכל שלב במשחק.
היסטוריות.
מכיוון שבמשחק חוזר השחקנים נפגשים פעם אחר פעם, הם צוברים אינפורמציה אחד על השני ככל שהמשחק מתקדם. המידע העומד לרשותו של כל שחקן בשלב
formula_1
הוא הפעולות ששיחקו כל השחקנים ב-
formula_2
השלבים הראשונים של המשחק. לכן נגדיר לכל
formula_3
את אוסף ההיסטוריות ה-
formula_2
שלביות כ:
formula_5.
עבור
formula_6
אנו מזהים
formula_7
, כאשר
formula_8
היא ההיסטוריה בתחילת המשחק, שאינה מכילה אף פעולה. היסטוריה ב-
formula_9
תסומן לעיתים ב-
formula_10
ולעיתים ב-
formula_11
, כאשר
formula_12
הוא וקטור הפעולות ששוחק בשלב
formula_13
אסטרטגיות במשחק אינסופי.
אסטרטגיית התנהגות במשחק חוזר אינסופי עבור שחקן
formula_13
היא פונקציה המתאימה פעולה מעורבת לכל היסטוריה סופית:
formula_15
אסטרטגיה טהורה מתאימה לכל היסטוריה פעולה של שחקן formula_13.
אוסף כל האסטרטגיות של שחקן i במשחק אינסופי יסומן ב-
formula_17.
המודל.
משחק חוזר מבוסס על משחק חד שלבי שאותו השחקנים משחקים שוב ושוב. נניח שמשחק זה נתון בצורה אסטרטגית על די
formula_18
כאשר
formula_19
היא קבוצת השחקנים,
formula_20
היא קבוצת הפעולות של שחקן
formula_21
formula_22
היא פונקציית התשלומים החד-שלבית של שחקן
formula_21
, כאשר
formula_24
היא קבוצת וקטורי הפעולות, אזי המשחק החוזר האינסופי
formula_25
המתאים ל
formula_26
הוא משחק מעל קבוצת השחקנים
formula_27
, שבו קבוצת האסט' לשחקן
formula_13
היא
formula_17
נסמן ב
formula_30
את אוסף כל מהלכי המשחק האפשריים במשחק האינסופי:
formula_31
איבר כללי בקבוצה זו הוא סדרה אינסופית
formula_32
של וקטורי פעולות, כאשר
formula_33
הוא וקטור הפעולות של השחקנים בשלב
formula_34
. וקטור האסטרטגיות
formula_35
של השחקנים משרה התפלגות
formula_36
על אוסף מהלכי המשחק האפשריים.
formula_37
-אלגברה על המרחב
formula_30
היא ה-
formula_37
-אלגברה הנפרשת על ידי הקבוצות הגליליות, שהן הקבוצות מהצורה הבאה:
formula_40
כלומר, קבוצת כל הסדרות האינסופיות בעלות אותן
formula_2
קואורדינטות ראשונות.
נסמן ב
formula_42
את אופרטור התוחלת המתאים להסתברות
formula_36
לכל שלב
formula_44
ולכל שחקן
formula_45
נסמן ב
formula_46
את התשלום של שחקן
formula_13
בשלב
formula_48
שיווי משקל.
וקטור אסטרטגיות
formula_49
נקרא שיווי משקל (במשחק האינסופי
formula_25
) והווקטור
formula_51
נקרא תשלום שיווי משקל אם בהסתברות 1 לפי
formula_52
לכל שחקן
formula_13
הגבול:
formula_54
קיים ושווה ל
formula_55
, ולכל אסטרטגיה של שחקן
formula_13
מתקיים
formula_57
במילים, וקטור אסטרטגיות
formula_49
הוא שיווי משקל עם תשלום
formula_59
אם ממוצע התשלומים תחת
formula_49
שואף ל-
formula_59
בהסתברות 1, ואף שחקן אינו יכול להרוויח על ידי סטייה.
המשפט העממי.
המשפט העממי עבור משחק אינסופי
formula_62
קובע:
אוסף תשלומי שיווי המשקל ב-
formula_63
הוא הקבוצה
formula_64
, כאשר
formula_65
הוא הקמור של כל התשלומים החד-שלביים האפשריים, ו-
formula_66
קבוצת התשלומים הסבירים פרטית.
המשחק האינסופי
משפט זרימה־מקסימלית חתך־מינימלי
דו שיח
מיכה בר עם
סמינר לרבנים
מולטקה הצעיר
הר אשכר
הר אשכר הוא הר בגליל העליון המערבי, בחבל תפן. למרגלותיו נמצא היישוב כפר ורדים.
ההר מתנשא לגובה של 695 מטרים מעל פני הים ובתוכו מתפתל "שביל נורמן", מסלול טיול שנחצב בתוך החורש הים התיכוני הסבוך.
סמוכה להר אשכר, חורבת אשכר, גלי אבנים ושברי חרסים מהתקופה הישראלית, הרומית והביזנטית.
מההר יורד נחל אשכר, המתחבר לנחל פקיעין מול היישוב חוסן.
יוסף גרפינקל
יוסף גרפינקל (נולד ב-23 ביולי 1956 בחיפה) הוא ארכאולוג ישראלי, פרופסור מן המניין לארכאולוגיה באוניברסיטה העברית בירושלים, המתמחה בארכאולוגיה מקראית ובתקופה הפרוטו-היסטורית. גרפינקל ניהל מספר רב של חפירות באתרים מן התקופה הנאוליתית של המזרח הקרוב, ופרסם 15 ספרים וכמאה מאמרים על מגוון נושאים בארכאולוגיה של ארץ ישראל, שבמרכזם אומנות, פולחן וריקוד.
תולדות חייו וקריירה מדעית.
יוסף גרפינקל השלים לימודי תואר ראשון בגאוגרפיה וארכאולוגיה באוניברסיטה העברית בירושלים בשנת 1981, ולימודי תואר שני בארכאולוגיה מקראית בשנת 1987.