Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
אינדוקציה לאחור הוא תהליך של הסקה, אחורה בזמן, מסופם של בעיה או מצב, על-מנת לבחור רצף פעולות אופטימלי. התהליך מתחיל בנקודת ההחלטה האחרונה, בה מסתכל השחקן מה הפעולה שהכי משתלם לו לשחק. בהינתן המידע הזה, ניתן להחליט בצעד הלפני אחרון מה הצעד המשתלם ביותר (בהנחה שבצעד האחרון בחר השחקן המחליט את הפעולה המשתלמת ביותר עבורו), וכך הלאה. את התהליך הזה ניתן לבצע עד לתחילת המשחק, וכך להסיק מה הפעולה האופטימלית, לכל שחקן, בכל נקודת זמן במשחק.
בתכנון דינמי, אינדוקציה לאחור היא אחת השיטות המרכזיות לפתירת משוואת בלמן. בתורת המשחקים, אינדוקציה לאחור משמשת לחישוב שיווי משקל תת-משחקי משוכלל במשחקים סדרתיים. ההבדל היחיד הוא שהאופטימיזציה מערבת מקבל החלטות יחיד, שבוחר מה לעשות בכל נקודה בזמן, בעוד שבתורת המשחקים, ניתן לנתח קבלת החלטות של מספר שחקנים, כפי שתואר לעיל.
בתורת המשחקים, אינדוקציה לאחור הוצגה לראשונה על ידי ג'ון פון נוימן ואוסקר מורגנשטרן בספרם "תורת המשחקים והתנהגות כלכלית" (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 ש"ח, או עבודה 'גרועה' שבה יקבל 44 ש"ח, בהסתברות 50/50 בכל פעם. ברגע שהוא מסכים לעבודה, הוא יעבוד בה עד לסוף עשר השנים. (נניח, לשם פשטות, שכל שמעניין את אותו אדם הוא הרווחים הכספיים שלו, ושהוא מעריך כסף בצורה זהה בזמנים שונים. כלומר, לריבית אין משמעות במשחק זה). האם עליו לקבל עבודה גרועה שהוצעה לו? כדי לענות על השאלה נשתמש באינדוקציה לאחור מהזמן t=10 אחורה.
ניתן להמשיך ולראות שכדאי לאדם המובטל לקבל הצעות גרועות רק בזמנים 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 ש"ח, דני יקבל שקל אחד, וכל שאר הסכום ייתרם לצדקה.
נניח כי המורה מחליטה להודיע לכיתה ביום ראשון כי השבוע ייערך בוחן פתע במתמטיקה. אם ישתמשו התלמידים באינדוקציה לאחור, יבינו מיד כי אם עד ליום חמישי לא נערך הבוחן, הוא יהיה חייב להיות בשישי, ולכן לא יפתיע אף אחד. לכן, חייבת המורה לערוך אותו בחמישי. אך, אם יפסלו את יום שישי, בהגיעם ליום רביעי יסיקו כי הבוחן ייערך בחמישי. התלמידים ימשיכו כך, עד לתחילת השבוע ויסיקו, לשמחתם, כי המורה לא יכולה לקיים בוחן פתע באף יום בשבוע. המורה, מצדה, תקיים את בוחן הפתע ביום רביעי, למשל, ותפתיע את כולם.
כאן, התלמידים משתמשים באינדוקציה לאחור, ומגיעים למסקנה שגויה. אך, שימו לב כי תיאור הבעיה מניח כי ניתן להפתיע שחקן שמשתמש באינדוקציה לאחור. התאוריה המתמטית שמאחורי השיטה אינה מניחה הנחה זו, ולכן הפרדוקס אינו סותר את התאוריה. אף על פי כן, פרדוקס זה ידוע מאוד ונדון רבות בהקשרים פילוסופיים.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.