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