דילמת האסיר

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

דילמת האסיר האבולוציונית

אחד מתחומי המחקר הפעילים ביותר בדילמת האסיר עוסק בגרסאות אבולוציוניות של המשחק. העניין בתחום נובע מכך שרבים מהקונפליקטים בחברה ובטבע תואמים את המודל של דילמת האסיר, כפי שאפשר להיווכח מהדוגמאות שהובאו לעיל. לכן ההנחה היא שמחקר אבולוציוני של דילמת האסיר עשוי לעזור לנו להבין את ההתפתחות הספונטנית של שיתוף פעולה בחברה ובטבע. המחקרים בנושא מתייחסים לשאלות כגון עד כמה התפתחות ספונטנית כזו אפשרית, אילו תבניות של שיתוף פעולה היינו מצפים לראות, ואיך משפיעים תנאי רעש ואי-וודאות.
הסכֶמה הכללית של דילמת האסיר האבולוציונית היא סימולציה של משחק איטרטיבי, בו אוכלוסיית שחקנים בעלי אסטרטגיות שונות משחקת בינה לבין עצמה. בכל צעד של הסימולציה מתקיימים משחקים בין זוגות שחקנים, כאשר תוצאות המשחקים משפיעות על הרכב האוכלוסייה בצעד הבא: חלקו היחסי של כל שחקן (אסטרטגיה) באוכלוסייה גדל או קטן בהתאם למידת ההצלחה שלו במשחקים האחרונים. במשחק איטרטיבי כזה, אסטרטגיות לא יציבות אבולוציונית צפויות להכחד, ואסטרטגיות יציבות צפויות לשגשג.
הסכֶמה כוללת בדרך-כלל גם אקראיות, הנחוצה הן כדי להתאים לתנאים המציאותיים בטבע, והן כדי להימנע מתלות גדולה מדי בתנאי ההתחלה השרירותיים של הסימולציה. האקראיות עשויה להתבטא בהגרלת השחקנים המתמודדים זה מול זה בכל צעד, ובסיכוי קטן ל"מוטציה" (תשנית) באוכלוסייה, שמשמעותה הכנסת אסטרטגיות חדשות לאוכלוסייה בכל צעד בהסתברות קטנה. לעיתים נעשה שימוש גם באופרטורים גנטיים נוספים, כגון שחלוף (כמובן, באינטרפרטציה המתאימה לסימולציה).
אחת הסימולציות הראשונות נערכה על ידי רוברט אקסלרוד במהלך שנות השמונים, והתוצאות היו מובהקות לטובת מידה כנגד מידה: לאחר כאלף "דורות" של ריצת הסימולציה מידה כנגד מידה הייתה האסטרטגיה הדומיננטית באוכלוסייה, וגם זו שגדלה בקצב המהיר ביותר. כאמור, אקסלרוד הוא גם זה שערך את הטורניר בין תוכניות המחשב, שגם בו ניצחה אותה אסטרטגיה.
הסימולציה של אקסלרוד כללה יחסית מעט אסטרטגיות, ולא כללה תנאי רעש. בתחילת שנות התשעים שני חוקרים, מרטין נוואק  וקארל סיגמונד, פרסמו תוצאות של סימולציות בתנאים יותר מציאותיים שכללו גם רעש ומוטציות. מהסימולציות האלה עלה שהאסטרטגיה היציבה ביותר היא מידה תחת מידה סלחנית (Generous Tit-for-Tat, ובקיצור GTFT), שבסיכוי מסוים מגיבה בשיתוף פעולה גם על בגידה של היריב בצעד הקודם. ה"סלחנות" הזו מאפשרת ל-GTFT להתגבר על מצבים שבהם מידה כנגד מידה הייתה עשויה להיכנס לשרשרת של בגידות הדדיות, כתוצאה מהרעש (שאולי ניתן לפרש כאן כ"אי הבנה").
אלא שגם סימולציות אלה היו פשטניות יחסית, משום שהן כללו רק אסטרטגיות שפעלו רק בהתאם לפעולה האחרונה של היריב. לכן בהמשך עבודתם, נוואק וסיגמונד שכללו את הסימולציות שלהם, כך שהן כללו אסטרטגיות שפעלו בהתאם לפעולה האחרונה של היריב ושל עצמן, או בהצגה אחרת, בהתאם לרווח האחרון שהתקבל. אסטרטגיות כאלה ניתנות לתיאור כווקטור ארבע-ממדי, , המייצג את ההסתברויות לשיתוף פעולה בהינתן שיתוף פעולה הדדי בצעד הקודם (Reward), שיתוף פעולה חד-צדדי שלי (Sucker), בגידה חד-צדדית שלי (Temptation), או בגידה הדדית (Punishment). המונחים בסוגריים הם המונחים המקובלים בספרות. בהצגה הזו, "תמיד בגידה" היא , מידה כנגד מידה היא , ומידה כנגד מידה סלחנית היא, למשל, . בסימולציות על מרחב האסטרטגיות הזה התקבלו תוצאות מפתיעות: לאחר 10 מיליון דורות, ביותר מ-80 אחוז מהסימולציות שלטה האסטרטגיה , אותה כינו החוקרים "פבלוב" (Pavlov) על שום התנהגותה הדומה להתניה פבלובית: כאשר היא מקבלת את אחת מהתשואות הנמוכות היא משנה את התנהגותה, וכאשר היא מקבלת את אחת מהתשואות הגבוהות היא נשארת עם אותה התנהגות. רק אחוז קטן מהסימולציות הסתיימו עם דומיננטיות של GTFT.
לאחר מכן פורסמו תוצאות נוספות בתחום, הן על ידי נוואק וסיגמונד והן על ידי חוקרים נוספים. בעבודות אלה הסתבר שישנם הבדלים לא זניחים באופי האסטרטגיות היציבות המתקבלות עבור ואריאציות שונות של סימולציות (קריטריונים מעט שונים ליציבות אבולוציונית, או אסטרטגיות דטרמיניסטיות לעומת הסתברותיות).
חרף ההבדלים באסטרטגיות היציבות שהתקבלו במחקרים השונים, אפיון משותף שלהם הוא שבסופו של דבר הסימולציות מתכנסות למצב שבו רוב הפעולות של השחקנים הן שיתוף פעולה. תכונה זו מתקיימת, למשל, גם כאשר האסטרטגיה השלטת היא "פבלוב" וגם כאשר היא מידה-כנגד-מידה או GTFT. אלא שההתכנסות לשיתוף-פעולה נובעת מתכונה מאוד לא טבעית של הסימולציות: בכל עימות השחקנים הם שווי-כוחות (מטריצת התשלום שלהם זהה), וכך נוצר ביניהם מאזן אימה. במציאות כמעט בכל עימות קיימת אסימטריה בין השחקנים, כך שהשחקן החזק יותר יכול "להעניש" באופן משמעותי יותר את יריבו. ב-2007 הראו חוקרים ממכון מקס פלאנק שניסויים בדילמת האסיר האסימטרית נותנים אחוז משמעותית נמוך יותר של שיתופי פעולה, וגם כאשר יש התכנסות למצב של שיתוף פעולה הדדי, מצב זה הרבה פחות יציב מאשר במשחק הסימטרי.