שידוך יציב, הקצאה אופטימלית ותכנון לינארי
Roth et al., 1993
1. מבוא
בשנים האחרונות התרחשה התקדמות משמעותית בלימוד פתרון של "בעיות התאמה" (matching problems) מפרספקטיבה של תורת המשחקים, גם מבחינה תיאורטית וגם מבחינה מעשית של הבעיות הפרקטיות עבורן רלוונטי ליישם אלגוריתמים של התאמה. בעיות התאמה שונות מבעיות קלאסיות של השמה (assignment) בכך שבבעיות התאמה שני הצדדים הם אנושיים, בעוד בבעיות השמה צד אחד בלבד הוא אנושי (למשל, דוגמא לבעיית השמה – אילו משימות להעביר מבני אדם למכונות). בבעיות התאמה, לשני הצדדים חשובה התוצאה, ולכן בעיות התאמה הן למעשה בעיות השמה, אבל עם יותר מגבלות, מפני ששני הצדדים צריכים להיות מרוצים מהתוצאה. מגבלות אלה נקראות מגבלות "יציבות" (Stability), והמאמר הנוכחי מתמקד במגבלות אלה.
מבחינה טכנית, המאמר מתמקד באופן שבו שיטות מתמטיות שונות, שנמצאות בשימוש ללימוד מודלים של בעיות השמה והתאמה, ניתנות במידה רבה לאיחוד לשיטה אחת, באמצעות טכניקות של אלגברה לינארית. באופן ספציפי, המאמר מתייחס לשני מודלים מוכרים: "מודל הנישואין", שמשמש למציאת התאמה אופטימלית בין שני מערכים של מספרים (לצורך דימוי מערך של "גברים" ומערך של "נשים"), ו"מודל ההשמה", שבו שני מערכים של שחקנים מיושמים לשני מערכים של מספרים (לצורך דימוי למשל של "קונים" ו"מוכרים").
באופן מפתיע, למרות שהפתרון של כל אחד ממודלים אלה מתבסס על שיטות מתמטיות שונות לחלוטין, נמצא שהם מביאים לתוצאות דומות. המטרה של המאמר הנוכחי היא להראות שהסיבה לכך...
לקריאת הסיכום המלא הורד/י את הסיכום באמצעות הטופס לעיל^
