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

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

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

• קבוצת אוניברסיטאות X וקבוצת תלמידים Y

• לכל אוניברסיטה x מכסה $q_{x}$ של מספר התלמידים המקסימלי שהיא מתכוונת לקבל.

• לכל תלמיד, יחס העדפות על הקבוצה X.

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

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

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

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

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

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

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

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