בעיית השידוכים
הבעיה מוגדרת על שתי קבוצות A ו-B כאשר בכל אחת מהן יש n חברים כאשר לכל חבר בקבוצה A יחס העדפות חזק על חברי הקבוצה B, ולכל חבר בקבוצה B יחס העדפות חזק על חברי הקבוצה A. שידוך בין חברי שתי הקבוצות יהיה פונקציה חד חד ערכית שמתאימה לכל חבר בקבוצה A חבר בקבוצה B.
הגדרת שידוך יציב
בהינתן שידוך בין חברי הקבוצות, הזוג ו- מערער על השידוך אם הם מעדיפים אחד את השני על פני בני הזוג אליהם הם שודכו. שידוך בין חברי הקבוצה A לבין חברי הקבוצה B יקרא יציב אם אין אף זוג שמערער עליו.
משפט גייל שפלי
משפט זה אשר הוכח בשנת 1962 טוען כי לכל בעיית שידוכים ניתן למצוא שידוך יציב, ובנוסף נותן אלגוריתם לפתרון הבעיה. אלגוריתם זה מתייחס למקרה בו הקבוצה A היא קבוצת הגברים המחזרים, והקבוצה B הוא קבוצת הנשים אחריהן הם מחזרים, אבל ניתן להרחבה באופן טריוויאלי לכל מקרה אחר.
הוכחה:
שלב ראשון- האלגוריתם:
אלגוריתם חיזור הגברים
תיאור האלגוריתם
בתחילת האלגוריתם כל הגברים והנשים נמצאים בביתם. בכל שלב באלגוריתם יקרו הדברים הבאים:
· כל גבר ניגש אל ביתה של האישה המועדפת אליו ביותר.
· כל אישה שעומדים ליד ביתה גברים משאירה איתה את הגבר המועדף אליה ביותר מבין כל אלה בנמצאים ליד ביתה ומשלחת את השאר לביתם.
התהליך מסתיים כאשר אף גבר לא נמצא בביתו. נסמן את השידוך היציב A שמתקבל באלגוריתם חיזור גברים ב - Am.
תכונות האלגוריתם
לאורך כל ביצוע האלגוריתם מתקיימות התכונות הבאות:
· כל הנשים העדיפות - בעבר: גבר שמגיע לביתה של אישה כבר נדחה על ידי כל הנשים שהוא מעדיף על פניה.
· כל הגברים העדיפים - בעתיד: אישה שנשאר איתה גבר עדיין לא פגשה את הגברים שהיא מעדיפה על פניו.
· כל אישה מבוקרת - תפוסה:כל אישה שביקר אותה לפחות גבר אחד תהיה תפוסה.
בסה״כ ביצוע האלגוריתם מסתיים בשידוך יציב תוך לכל היותר n(n − 1) + 1 צעדים.
אלגוריתם חיזור הנשים
זהו אלגוריתם זהה לאלגוריתם חיזור הגברים פרט לעובדה שהגברים והנשים מתחלפים תפקידיהם. נסמן את השידוך היציב A שמתקבל באלגוריתם חיזור גברים ב - Aw.
שלב שני - סופיות האלגוריתם:
התהליך סופי: נרצה להראות כי יש שלב שבו אף גבר אינו נשלח לביתו.
כל אישה דוחה לכל היותר n-1 גברים. יש n נשים.
לכן, לאחר n(n − 1) צעדים אף גבר לא דחוי.
נניח בשלילה כי אבי נמצא בביתו לאחר שנדחה על ידי כל הנשים.
מכאן נובע כי כל הנשים כבר תפוסות.
אבל זו סתירה שכן יש מספר זהה של נשים וגברים.
ולכן התהליך סופי.
שלב שלוש:
כעת בפני כל אישה עומד גבר אחד ויחיד. ולכן אכן קיבלנו שידוך.
שלב ארבע - השידוך יציב:
נניח בשלילה כי קיים זוג המעוניין לערער על השידוך שיצרנו, נניח דני ודנה.
כלומר, בהכרח בשידוך שלנו דני ודנה לא משודכים זה לזה.
נניח : דני - אביבה, אבי - דנה.
אז מתקיים: דני : דנה > אביבה.
דנה : דני > אבי.
אבל מצב זה אינו ייתכן.
אם דני : דנה > אביבה , אז דני ביקר אצל דנה לפני שביקר אצל אביבה ונדחה על ידי דנה (לפי תכונת כל הנשים העדיפות - בעבר).
אבל תכונת כל הגברים העדיפים - בעתיד תכתיב לנו כי דנה : אבי > דני, וזו סתירה לכך שדנה רוצה לערער עם דני על השידוך.
ומסתירה זו נקבל כי השידוך יציב.
המקור
_________________
תוקן על ידי כמעט_חדשה ב- 20/08/2010 16:05:03
"כולם מבחינים איך אתם נראים, אך רק חלק יודעים באמת מי אתם"
תוקן על ידי אסיק_good ב- 20/08/2010 16:11:46
)
