אינדוקציה לאחור

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

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

בתורת המשחקים, אינדוקציה לאחור הוצגה לראשונה על ידי ג'ון פון נוימן ואוסקר מורגנשטרן בספרם "תורת המשחקים והתנהגות כלכלית" (1944).

פסאודו-קוד

eval(node):

if node is a leaf
   return value(node)

if node is a min-node
   current-min = +infinity
   for all children u of node do
      x = eval(u)
      current-min = minimum(x, current-min)
   return current-min

else // node is a max-node
   current-max = -infinity
   for all children u of node do
      x = eval(u)
      current-max = maximum(x, current-max)
   return current-max

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

קבלת החלטות בעזרת אינדוקציה לאחור: דוגמה

ניקח, לדוגמה, אדם מובטל שיהיה מסוגל לעבוד רק בעשר השנים הקרובות: $t=1,2,...,10$. נניח כי בכל שנה שבה הוא נשאר מובטל, מציעים לו עבודה 'טובה' בה יקבל 100 ש"ח, או עבודה 'גרועה' שבה יקבל 44 ש"ח, בהסתברות 50/50 בכל פעם. ברגע שהוא מסכים לעבודה, הוא יעבוד בה עד לסוף עשר השנים. (נניח, לשם פשטות, שכל שמעניין את אותו אדם הוא הרווחים הכספיים שלו, ושהוא מעריך כסף בצורה זהה בזמנים שונים. כלומר, לריבית אין משמעות במשחק זה). האם עליו לקבל עבודה גרועה שהוצעה לו? כדי לענות על השאלה נשתמש באינדוקציה לאחור מהזמן t=10 אחורה.

• בזמן 10, הערך של קבלת עבודה טובה הוא 100 ש"ח. הערך של קבלת עבודה גרועה הוא 44 ש"ח. הערך של דחיית עבודה כלשהי הוא 0. לכן, אם הוא עדיין מובטל בפרק הזמן האחרון, כדאי לו לקבל כל עבודה שהוצעה לו, בזמן זה.
• בזמן 9, הערך של קבלת עבודה טובה הוא 200 ש"ח (כי הוא יחזיק בעבודה זו במשך שנתיים). הערך של קבלת עבודה גרועה הוא 88 ש"ח. הערך של דחיית עבודה כלשהי הוא 0 + הערך של המתנה להצעה הבאה, שהיא 44 ש"ח בהסתברות של 50% ו-100 ש"ח בהסתברות של 50%, כלומר, בממוצע 72 ש"ח. לכן, גם בשלב 9 עדיף לו לקבל כל הצעה, מאשר לדחות אותה.
• בזמן 8, הערך של קבלת עבודה טובה הוא 300 ש"ח. הערך של קבלת עבודה גרועה הוא 132 ש"ח. הערך של דחיית עבודה כלשהי הוא 0 + הערך של המתנה להצעה הבאה. מכיוון שכבר הסקנו שכל הצעה בזמן 9 צריכה להיענות בחיוב, הערך הממוצע של המתנה להצעה בזמן 9 הוא 0.5*(200+88) = 144 ש"ח. לכן, בזמן 8, עדיף לו לחכות להצעה הבאה מאשר לקבל הצעה גרועה.

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

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

אינדוקציה לאחור בתורת המשחקים: דוגמאות

משחק הפיראטים

ערך מורחב – משחק הפיראטים

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

אינדוקציה לאחור עוזרת לנו למצוא את הפתרון. נתחיל מהסוף. בנקודת ההחלטה האחרונה נשארו הפיראטים D ו-E. הפיראט D יודע כי כל הצעה שיציע, מלבד 0 עבורו ו-100 עבור הפיראט E, לא תקבל רוב, והוא ישחה עם הכרישים (כיוון שעדיף ל-E לסרב ולקחת את כל השלל). לכן, הוא מציע ל-E את כל השלל. כעת, בנקודת ההחלטה הקודמת, נשארו C, D ו-E. הפיראט C צריך למשוך אליו רק עוד פיראט אחד על מנת שהצעתו תתקבל, ולכן הוא יציע לפיראט D מטבע בודד, וייקח 99 לעצמו. נחזור עוד אחורה, אל B, C, D ו-E. הפיראט B צריך איתו עוד שני פיראטים, ולכן יציע ל-D שני מטבעות, ול-E מטבע אחד. נזכיר, שבהינתן שכל הפיראטים פועלים על פי אותו ההיגיון, זהו באמת תשלום טוב יותר מכל מצב אחר, אם יסרבו. לבסוף, אם נחזור להתחלה, A יודע שכל שעליו לעשות הוא לשכנע שני פיראטים. לכן, הוא ייתן לפיראט C מטבע אחד, ולפיראט E שני מטבעות. הוא עצמו יישאר עם 97 מטבעות.

משחק מרבה-הרגליים

איש עשיר מת והוריש לשני בניו, יוסי ודני, הון בשווי מיליון ועשרת אלפים ש"ח (1,010,000). יחד עם הירושה, השאיר האב הוראות: יוסי, האח הבכור, יכול לקחת לעצמו 100 ש"ח, להשאיר לאחיו שקל אחד, ואת כל שאר הסכום לתרום לצדקה. יוסי אינו חייב לקבל את החלוקה הזו. הוא יכול להעביר את ההחלטה לאחיו, אך הפעם החלוקה תהיה שונה לגמרי: דני יקבל 1,000 ש"ח, בעוד יוסי, שקיבל קודם 100 ש"ח, יקבל רק 10 ש"ח. השאר ייתרם לצדקה. גם דני לא חייב לקבל את החלוקה הזו. הוא יכול להעביר את ההחלטה שוב לידיו של יוסי שיוכל לקחת לעצמו 10,000 ש"ח, ולתת לדני 100 ש"ח. היתר ייתרם לצדקה. יוסי יכול להעביר את ההחלטה לידיו של דני שוב, והתשלומים יהיו 100,000 ש"ח לדני ו-1,000 ש"ח ליוסי. ולבסוף, יכול דני להעביר את ההחלטה ליוסי שיקבל 1,000,000 ש"ח בעוד דני יקבל 10,000 ש"ח ואף שקל לא ייתרם לצדקה.

מה יקרה במצב כזה? דני יבין שאם הוא לא ייקח לעצמו 100,000 ש"ח. יוסי ייקח לעצמו 1,000,000, וישאיר אותו, דני, עם 10,000 בלבד. לכן הוא ייקח לעצמו 100,000 ש"ח. יוסי יבין זאת, ולכן כבר בשלב הקודם יחליט לקחת לעצמו 10,000 ש"ח, ולתת לדני 100. כך, יגיעו שני האחים למצב העגום בו יוסי יקבל 100 ש"ח, דני יקבל שקל אחד, וכל שאר הסכום ייתרם לצדקה.

פרדוקס בוחן הפתע

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

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

קישורים חיצוניים

מדיה וקבצים בנושא אינדוקציה לאחור בוויקישיתוף

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