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

אינדוקציה לאחור הוא תהליך של הסקה, אחורה בזמן, מסופם של בעיה או מצב, על-מנת לבחור רצף פעולות אופטימלי. התהליך מתחיל בנקודת ההחלטה האחרונה, בה מסתכל השחקן מה הפעולה שהכי משתלם לו לשחק. בהינתן המידע הזה, ניתן להחליט בצעד הלפני אחרון מה הצעד המשתלם ביותר (בהנחה שבצעד האחרון בחר השחקן המחליט את הפעולה המשתלמת ביותר עבורו), וכך הלאה. את התהליך הזה ניתן לבצע עד לתחילת המשחק, וכך להסיק מה הפעולה האופטימלית, לכל שחקן, בכל נקודת זמן במשחק.
בתכנון דינמי, אינדוקציה לאחור היא אחת השיטות המרכזיות לפתירת משוואת בלמן. בתורת המשחקים, אינדוקציה לאחור משמשת לחישוב שיווי משקל תת-משחקי משוכלל במשחקים סדרתיים. ההבדל היחיד הוא שהאופטימיזציה מערבת מקבל החלטות יחיד, שבוחר מה לעשות בכל נקודה בזמן, בעוד שבתורת המשחקים, ניתן לנתח קבלת החלטות של מספר שחקנים, כפי שתואר לעיל.
בתורת המשחקים, אינדוקציה לאחור הוצגה לראשונה על ידי ג'ון פון נוימן ואוסקר מורגנשטרן בספרם "תורת המשחקים והתנהגות כלכלית" (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
לאלגוריתם זה ניתן לעשות אופטימיזציה בעזרת שיטה שנקראת גיזום אלפא-ביתא, מבלי לשנות את התוצאה שהיה מחזיר האלגוריתם המקורי.

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

נניח כי ישנם חמישה פיראטים שרוצים להתחלק באוצר של 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 ש"ח, דני יקבל שקל אחד, וכל שאר הסכום ייתרם לצדקה.

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

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