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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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