שידוך רב-ערכי

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

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

בעיית שידוכים רב-ערכית נתונה על ידי:

  • קבוצת אוניברסיטאות X וקבוצת תלמידים Y
  • לכל אוניברסיטה x מכסה של מספר התלמידים המקסימלי שהיא מתכוונת לקבל.
  • לכל תלמיד, יחס העדפות על הקבוצה X.
  • לכל אוניברסיטה, יחס העדפות על הקבוצה Y.

הגדרה: שידוך הוא התאמה המתאימה לכל אוניברסיטה x תת-קבוצה (אולי ריקה) של Y שבה יש לכל היותר איברים, כך שלכל תלמיד מותאמת לכל היותר אוניברסיטה אחת.

הגדרה: נאמר כי אוניברסיטה x ותלמיד y מערערים על שידוך, אם שני התנאים הבאים מתקיימים:

- התלמיד y מעדיף את האוניברסיטה x על פני האוניברסיטה שהותאמה לו.

- לאוניברסיטה x הותאמו פחות מ- תלמידים, או שהותאמו לה תלמידים אך היא מעדיפה את y על פני אחד התלמידים שהותאמו לה.

שידוך נקרא יציב אם אין אף אוניברסיטה ותלמיד המערערים עליו.

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

קישורים חיצונייםעריכה