שידוך יציב

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

בעיית השידוכים

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

הגדרת שידוך יציב

בהינתן שידוך בין חברי הקבוצות, הזוג ${\displaystyle a\in A}$ ו- ${\displaystyle b\in B}$ מערער על השידוך אם הם מעדיפים אחד את השני על פני בני הזוג אליהם הם שודכו. שידוך בין חברי הקבוצה A לבין חברי הקבוצה B יקרא יציב אם אין אף זוג שמערער עליו.

משפט גייל שפלי

ב-1962 פרסמו דייוויד גייל ולויד שפלי מאמר^[1] שהציג את הבעיה ובו הם הוכיחו כי לכל בעיית שידוכים ניתן למצוא שידוך יציב. ההוכחה הייתה קונסטרוקטיבית והציעה אלגוריתם לפתרון הבעיה. לימים זכה לויד שפלי בפרס נובל לכלכלה לשנת 2012, בין היתר על תרומה זו (דייוויד גייל נפטר בשנת 2008).

תיאור האלגוריתם למטה מתייחס למקרה שבו הקבוצה A היא קבוצת הגברים המחזרים, והקבוצה B הוא קבוצת הנשים שאחריהן הם מחזרים.

הוכחה

שלב ראשון - האלגוריתם

אלגוריתם חיזור הגברים

בתחילת האלגוריתם כל הגברים והנשים נמצאים בביתם. בכל שלב באלגוריתם יקרו הדברים הבאים:

• כל גבר ניגש אל ביתה של האישה המועדפת עליו, מבין הנשים שלא דחו אותו עד לשלב זה.
• כל אישה שגברים עומדים ליד ביתה, משאירה איתה את הגבר המועדף עליה ושולחת את השאר בחזרה.

התהליך מסתיים כאשר אף גבר לא נמצא בביתו. נסמן את השידוך היציב שמתקבל באלגוריתם חיזור גברים ב - A^m. כאשר הגברים והנשים מחליפים תפקידים והנשים הן אלה שמציעות נסמן את השידוך היציב שמתקבל ב - A^w.

לאורך כל ביצוע האלגוריתם מתקיימות התכונות הבאות:

• כל הנשים העדיפות - בעבר: גבר שמגיע לביתה של אישה כבר נדחה על ידי כל הנשים שהוא מעדיף על פניה
• כל הגברים העדיפים - בעתיד: אישה שנשאר איתה גבר עדיין לא פגשה את הגברים שהיא מעדיפה על פניו
• כל אישה מבוקרת - תפוסה: כל אישה שביקר אותה לפחות גבר אחד תהיה תפוסה

ביצוע האלגוריתם מסתיים בשידוך יציב תוך לכל היותר ${\displaystyle n(n-1)+1}$ צעדים.

שלב שני - סופיות האלגוריתם

נרצה להראות כי יש שלב שבו אף גבר לא נשלח לביתו

• כל אישה דוחה לכל היותר n-1 גברים
• יש n נשים. לכן, לאחר ${\displaystyle n(n-1)}$ צעדים אף גבר לא דחוי
• נניח בשלילה כי אבי נמצא בביתו לאחר שנדחה על ידי כל הנשים. מכאן נובע כי כל הנשים כבר תפוסות
• אבל זו סתירה שכן יש מספר זהה של נשים וגברים

ולכן התהליך סופי.

שלב שלוש

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

שלב ארבע - השידוך יציב

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

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

דוגמה לשימוש באלגוריתם גייל שפלי

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

יחסי העדפות גברים
	עדיפות ראשונה	עדיפות שנייה	עדיפות שלישית	עדיפות רביעית
מעין	רותם	נועה	גרטה	ליטל
אמיר	נועה	ליטל	גרטה	רותם
יונתן	גרטה	נועה	ליטל	רותם
ישעיהו	ליטל	נועה	גרטה	רותם

יחסי העדפות נשים
	עדיפות ראשונה	עדיפות שנייה	עדיפות שלישית	עדיפות רביעית
רותם	מעין	אמיר	ישעיהו	יונתן
נועה	מעין	יונתן	ישעיהו	אמיר
גרטה	אמיר	מעין	ישעיהו	יונתן
ליטל	יונתן	אמיר	ישעיהו	מעין

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

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

אלגוריתם חיזור נשים
	מעין	אמיר	יונתן	ישעיהו	נשלחו הביתה
שלב ראשון	רותם (1), נועה (1)	גרטה (1)	ליטל (1)		נועה
שלב שני	רותם (1)	גרטה (1)	ליטל (1), נועה (2)		ליטל
שלב שלישי	רותם (1)	גרטה (1), ליטל (2)	נועה (2)		גרטה
שלב רביעי	רותם (1), גרטה (2)	ליטל (2)	נועה (2)		גרטה
שלב חמישי	רותם (1)	ליטל (2)	נועה (2)	גרטה (3)

אלגוריתם חיזור גברים
	רותם	נועה	גרטה	ליטל	נשלחו הביתה
שלב ראשון	מעין (1)	אמיר (1)	יונתן (1)	ישעיהו (1)

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

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

חיזור הגברים יוצר את הזוגות הבאים: מעין-רותם, אמיר-נועה, יונתן-גרטה, ישעיהו-ליטל.

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

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

המבנה הסריגי של קבוצת השידוכים היציבים

יהיו A ו-B שני שידוכים. A ${\displaystyle \vee ^{w}}$ B היא ההתאמה המתאימה לכל אישה y את הגבר שאותו היא מעדיפה מבין הגברים שלהם היא משודכת ב-A וב-B. באותו אופן ניתן להגדיר את ההתאמה A ${\displaystyle \vee ^{m}}$ B, שבה כל גבר בוחר באישה העדיפה בעיניו מבין הנשים המשודכות לו ב-A וב-B.

הגדרות אלו מגדירות מבנה של סריג על קבוצת השידוכים היציבים, כאשר פעולת המקסימום מתייחסת ל"מקסימום נשים" ופעולת המינימום מתייחסת ל"מקסימום גברים". כלומר, המקסימום עבור קבוצת השידוכים היציבים ${\displaystyle \{A^{1},A^{2},...,A^{K}\}}$, יהיה ${\displaystyle A^{1}\vee ^{w}...\vee ^{w}A^{K}}$ והמינימום יהיה ${\displaystyle A^{1}\vee ^{m}...\vee ^{m}A^{K}}$.

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

משפט: אם A ו-B הם שידוכים יציבים, אז גם A ${\displaystyle \vee ^{w}}$ B ו- A ${\displaystyle \vee ^{m}}$ B הם שידוכים יציבים.
הוכחה: נוכיח עבור A ${\displaystyle \vee ^{w}}$ B ועל ידי החלפת המינים נקבל את המבוקש עבור A ${\displaystyle \vee ^{m}}$ B.
נסמן C = A ${\displaystyle \vee ^{w}}$ B. ראשית נוכיח כי C הוא שידוך, ולאחר מכן נוכיח כי הוא שידוך יציב.

• שלב ראשון - C הוא שידוך:

נניח בשלילה כי C אינו שידוך. כלומר, נניח כי בתהליך בו כל אישה בוחרת בגבר העדיף בעיניה מבין המשודכים לה ב-A וב-B, יש גבר הנבחר על ידי שתי נשים. נניח למשל כי דוד נבחר ב-C הן על ידי מיכל והן על ידי בת-שבע. מכאן שבשידוך A הוא משודך לאחת מהן, ובשידוך B לשנייה. נניח כי בשידוך A דוד משודך למיכל ואוריה לבת שבע, ובשידוך B דוד משודך לבת שבע ויוחאי למיכל. (איננו פוסלים את האפשרות כי אוריה ויוחאי הם אותו אדם). כיוון שלפי C הן מיכל והן בת שבע בחרו בדוד, נקבל כי:
מיכל: דוד ${\displaystyle \prec }$ יוחאי,
בת שבע: דוד ${\displaystyle \prec }$ אוריה.
אם דוד מעדיף את מיכל על פני בת-שבע, אז הזוג (דוד, מיכל) מערער על השידוך B.
אם דוד מעדיף את בת-שבע על פני מיכל, אז הזוג (דוד, בת-שבע) מערער על השידוך A,
בסתירה לכך שגם A וגם B הם שידוכים יציבים. הסתירה נובעת מההנחה כי C אינו שידוך, ולכן C הוא שידוך.

• שלב שני - C הוא שידוך יציב:

נניח בשלילה כי C אינו שידוך יציב. אזי, יש זוג, נאמר דוד ובת-שבע, שאינם משודכים ב-C זה בזה ומערערים על השידוך.
נניח כי בשידוך C דוד משודך למיכל, ואוריה משודך לבת-שבע. מכיוון שדוד ובת-שבע מערערים על השידוך, בהכרח מתקיים:
בת-שבע: דוד ${\displaystyle \prec }$ אוריה,
דוד: בת-שבע ${\displaystyle \prec }$ מיכל.
מכיוון שב-C בת-שבע משודכת לאוריה, הרי שהיא משודכת לו או ב-A או ב-B. נניח בה"כ כי היא משודכת לו ב-A, ונניח כי ב-B היא משודכת ליואב. אזי, בת-שבע מעדיפה את דוד על פני אוריה, ואת אוריה על פני יואב (שכן ב-C היא משודכת לאוריה ולא ליואב), ובפרט גם את דוד על פני יואב:
בת שבע: דוד ${\displaystyle \prec }$ אוריה ${\displaystyle \prec }$ יואב.
מכיוון ש-A הוא שידוך יציב, דוד ובת-שבע אינם מערערים עליו. מכיוון שבת-שבע מעדיפה את דוד על פני אוריה, הרי שדוד מעדיף את המשודכת לו ב-A על פני בת-שבע. מכיוון שדוד מעדיף את בת-שבע על פני מיכל, לא ייתכן שמיכל משודכת לדוד ב-A.
מכיוון ש-B הוא שידוך יציב, דוד ובת-שבע אינם מערערים עליו. מכיוון שבת-שבע מעדיפה את דוד על פני יואב, הרי שדוד מעדיף את המשודכת לו ב-B על פני בת-שבע. מכיוון שדוד מעדיף את בת-שבע על פני מיכל, לא ייתכן שמיכל משודכת לדוד ב-B.
כלומר, מיכל אינה משודכת לדוד לא ב-A ולא ב-B, וזאת סתירה לכך שמיכל משודכת לדוד ב-C.
קיבלנו סתירה להנחה כי C אינו שידוך יציב, ולכן C הוא אכן שידוך יציב, כנדרש.

יחסים על שידוכים יציבים

יהיו ${\displaystyle C_{1}}$ ו - ${\displaystyle C_{2}}$ שני שידוכים יציבים, בין הגברים לנשים.

• ${\displaystyle C_{1}>_{m}C_{2}}$ אם ורק אם לכל גבר שמשודך לנשים שונות ב - ${\displaystyle C_{1}}$ ו - ${\displaystyle C_{2}}$, הוא מעדיף את השידוך שלו ב - ${\displaystyle C_{1}}$ על פני השידוך שלו ב - ${\displaystyle C_{2}}$.
• ${\displaystyle C_{1}>_{w}C_{2}}$ אם ורק אם לכל אישה שמשודכת לגברים שונים ב - ${\displaystyle C_{1}}$ ו - ${\displaystyle C_{2}}$, היא מעדיפה את השידוך שלה ב - ${\displaystyle C_{1}}$ על פני השידוך שלה ב - ${\displaystyle C_{2}}$.

משפט: לכל שני שידוכים ${\displaystyle C_{1}}$ ו - ${\displaystyle C_{2}}$ מתקיים: ${\displaystyle C_{1}>_{m}C_{2}}$ אם ורק אם ${\displaystyle C_{2}>_{w}C_{1}}$.
משפט: לכל שידוך יציב ${\displaystyle D}$ מתקיים:

• ${\displaystyle C^{m}>_{m}D>_{m}C^{w}}$
• ${\displaystyle C^{w}>_{w}D>_{w}C^{m}}$

שידוך לא סימטרי

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

שידוך רב ערכי

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

אדישות

כשמישהו מחברי הקהילה אדיש לבחירה בין שניים או יותר מבני המין השני, פירושו של דבר שבבואו לדרג את בני המין השני בקהילה בסדר העדפות, לא יוכל להעדיף ממש בן זוג אחד על פני השני (יהיה אדיש ביניהם). למשל, יוכל גבר לדרג את אישה B בעדיפות ראשונה, בעדיפות שנייה להיות אדיש בין A ו-D ובעדיפות שלישית להיות אדיש בין C ל-E ובעדיפות רביעית לבחור את F. מהגדרת היציבות של שידוך משתמע שגבר לא יעזוב את האישה המשודכת לו בעבור אישה אחרת, כשהוא אדיש לבחירה בין השתיים ושאישה לא תעזוב גבר בעבור גבר אחר, כשהיא אדישה לבחירה בין השניים.

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

שידוכים באוכלוסייה חד מינית

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

יחסי העדפות נשים
	עדיפות ראשונה	עדיפות שנייה	עדיפות שלישית
אורית	בתיה	גליה	דנה
בתיה	גליה	אורית	דנה
גליה	אורית	בתיה	דנה
דנה	אורית	גליה	בתיה

נוכיח שלנשים עם יחסי ההעדפות הללו אין שידוך יציב. ישנם שלושה שידוכים אפשריים:

1. דנה-אורית, בתיה-גליה
2. דנה-בתיה, אורית-גליה
3. דנה-גליה, אורית-בתיה

• השידוך הראשון אינו יציב, שכן אורית וגליה יערערו עליו: אורית מעדיפה את גליה על פני דנה וגליה מעדיפה את אורית על פני בתיה
• השידוך השני אינו יציב, שכן אורית ובתיה יערערו עליו: אורית מעדיפה את בתיה על פני גליה ובתיה מעדיפה את אורית על פני דנה
• השידוך השלישי אף הוא אינו יציב; הפעם המערערות הן בתיה וגליה. בתיה מעדיפה את גליה על פני אורית וגליה מעדיפה את בתיה על פני דנה

רוברט אירווינג הציע בשנת 1986 אלגוריתם יעיל למציאת שידוך חד-מיני יציב במקרה שקיים כזה.^[2]

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946
• עין-יה גורה, מיכאל משלר, פרקים בתורת המשחקים, האוניברסיטה העברית בירושלים - המרכז להוראת המדעים, 1996

הערות שוליים

1. D. Gale and L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962
2. Irving, Robert W.; Leather, Paul (1986). "The complexity of counting stable marriages". SIAM Journal on Computing. 15 (3): 655–667. doi:10.1137/0215048. MR 0850415

.