משפט הנישואים היציבים

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

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

רוס: רייצ'ל, פיבי, מוניקה.

צ'נדלר: מוניקה, פיבי, רייצ'ל.

ג'ואי: רייצ'ל,מוניקה, פיבי.

רייצ'ל: רוס, ג'ואי, צ'נדלר.

מוניקה: צ'נדלר, ג'ואי, רוס.

פיבי: ג'ואי, רוס, צ'נדלר.

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

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

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

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

ביום השני כל הבנים שגורשו לכל הרוחות ביום הראשון הולכים אל הבת הבאה ברשימה שלהם. היא נוהגת באותו האופן כמו אתמול – מעיפה לכל הרוחות את כל הבנים שנמצאים לה ליד הבית פרט לזה שהכי מוצא חן בעיניה (אם היה בן ששרד את אתמול והגיע היום בן שמוצא חן בעיניה יותר הוא יגורש כמו כולם). ויהי ערב ויהי בוקר יום שני.

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

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

אם כן, למה המשחק נגמר תמיד בשידוך לכולם ומדוע הוא יציב? ההוכחות הן יפות מאוד, לטעמי, בגלל הפשטות והאלגנטיות שלהן. נתחיל מכך שהמשחק חייב להיגמר בשידוך לכולם. האבחנה המרכזית היא שמרגע שבו לאישה יש לפחות מחזר אחד, יהיה לה תמיד בסוף היום מחזר אחד, פשוט כי היא תמיד שומרת אצלה מחזר אחד כשהיא מעיפה את היתר. לכן כל מה שצריך להשתכנע בו הוא שמתישהו כל אישה תקבל מחזר. מכיוון שכל אישה נמצאת במקום כלשהו ברשימה של כל גבר, בהכרח יגיע אליה מתישהו כל גבר אלא אם הוא "נלכד" קודם על ידי בחורה אחרת שלא מוותרת עליו יותר; אבל יש $latex n-1$ בחורות (פרט לזו שאנו עוסקים בה) ו-$latex n$ גברים, ולא ייתכן שכולם יילכדו על ידי $latex n-1$ הבחורות (אחרת הייתה בחורה שלוכדת 2 גברים, מעקרון שובך היונים; אבל כל בחורה מותירה אצלה רק גבר אחד) – סוף פסוק.

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

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

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

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

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

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

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

מבלבל? מצד אחד כן – מצד שני, אפשר לחשוב ש"חברים" המקורי היה פחות מבלבל.

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

אני חושב שהמסקנות ברורות.

15 תגובות על הפוסט “משפט הנישואים היציבים

  1. אומר קודם שהיה כיף לקרוא את המאמר והצורה שבו אתה מסביר את ההוכחה מאוד אינטואיטיבית.

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

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

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

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

    כמובן, ייתכן שלבוב יש בחורות שמדורגות עוד יותר גבוה מאליס ברשימה, אבל אין לו סיכוי איתן מלכתחילה – באף שידוך יציב הוא לא איתן.

    מה שהראיתי הוא שג'ואי משיג את הבחורה האופטימלית שלו אם הוא לוקח יוזמה. לעומת זאת רייצ'ל, אם היא מחכה, "נתקעת" עם בחירה שאיננה אופטימלית עבורה – קיים שידוך יציב אחר שבו היא נמצאת עם גבר שמדורג גבוה יותר (אז למה כעת היא נתקעה עם ג'ואי? בגלל שהגבר האחר פשוט לא טרח להגיע אליה).

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

    אבל – אני לא משוכנע שיכול להיות סידור כזה. אני אנסה לשחק אם זה קצת ואחזור אליך אם אמצא משהו מעניין.

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

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

  6. בהמשך לשיחתנו מאתמול:

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

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

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

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

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

  10. לזה התכוונתי "אני יודע שאתה יודע את זה". אני רק לא בטוח שזה "ברור לכולנו" – למשל, לא לעיתונאי ממוצע.

    ומה עושים בבתי חולים ומתמחים? הרי מספר בתי החולים לא שווה למספר המתמחים. צריך וריאציה של האלגוריתם.

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

  12. פינגבאק: צבר – בלוג עם קוצים » ארכיון הבלוג » על אהבה

  13. פינגבאק: הזמנה לתערוכה, והרצאות לקהל הרחב! « לא מדויק

  14. פינגבאק: משפט רמזי « לא מדויק

כתיבת תגובה

האימייל לא יוצג באתר.