70 / 148
עורכי דין
דרך הקבלה להתמחות ותורת המשחקים
- אך בפועל הוא השתנה אך מעט מאז שנות ה־05.
כדי להבין את הרעיון שבבסיס האלגוריתם, נסביר
בקצרה את מה שמקובל לקרוא לו בספרות "בעיית
השידוכים", ולאחר מכן נראה כיצד מיושם רעיון זה
בקלות במקרה שלפנינו.
בעיית השידוכים
בדוגמה של שלושה זוגות בלבד
מהי בעיית השידוכים? הבה נניח כי יש לנו מספר
) ואותו מספר של נשים
N
כלשהו של גברים (נאמר
(לשם הפשטות נניח כי מספרם זהה). כל אחד מה
־
גברים מעדיף נשים אחרות, אך ייתכן כי כמה מהם
מעדיפים את אותה אישה, וייתכן כי יש נשים הנמ
־
צאות בעדיפות אחרונה. כמובן גם ההפך נכון, ולכל
אישה יש העדפות משלה. פורמלית, בעיית השי
־
דוכים מוגדרת כהתאמה בין אלמנטים שלכל אחד
מהם העדפות משלו (הרחבה זו מאפשרת הכללת
בעיות רבות ושונות, אך נוח
להבינה בצורה שהסברנו ולכן
התמקדנו בדוגמת נשים־גב
־
רים בלבד).
הבה נוסיף ונניח כי שידכנו
בין כל הגברים לכל הנשים
י
�
זוגות (ש
N
כך שיש לנו
דוכים). כיצד נוכל להבטיח
שגבר ואישה לא יזנחו את
בני זוגם ויקימו זוג חדש?
לצורך כך נגדיר את המונח
"שידוך יציב"; זהו שידוך שבו
אין סיבה למי מהצדדים להיפרד מבן זוגו ולהצטרף
לבני זוג אחרים. למשל, ייתכן שאחת הנשים הייתה
מעדיפה בן זוג אחר, אולם אותו בן זוג אינו רוצה בה.
שידוך לא יציב הוא שידוך שבו אחד הצדדים מעדיף
לעזוב את השידוך ולהצטרף לבן זוג אחר שגם הוא
מעדיף לעזוב את בן זוגו.
השאלה המתמטית היא זו: האם נוכל לבנות אל
־
גוריתם המחשב את כל העדיפויות כך שנוכל לבנות
שידוכים יציבים בין כל הזוגות, ולא ישתלם לשום
N
זוג לפרק את המסגרת שבה הוא נמצא וליצור מסג
־
רת אחרת? התשובה היא שאפשר לעשות זאת, ויש
אלגוריתם כזה.
האלגוריתם פשוט, ואלה הגדרותיו:
כל גבר וכל אישה יסדרו את בני הזוג האפשריים
על פי העדפותיהם. למשל, אם אברהם מעדיף את
שרה על פני בת שבע, שרה תהיה הראשונה בתור
ואחריה בת שבע וכן הלאה.
בסיבוב הראשון ילך כל גבר ויתייצב על פתח
ביתה של האישה שהוא מעדיף בראשונה.
בסיבוב השני תשאיר כל אישה על פתח ביתה את
הגבר שהיא מעדיפה מהאפשרויות שיש לה ות
־
שלח את האחרים לדרכם. אם יש בפתח ביתה רק
גבר אחד, הוא יישאר כמובן. העודפים, אם נותרו,
ימשיכו לעדיפותם השנייה; שם ייתכן שכבר יהיה
מישהו, וייתכן שלא.
בסיבוב השלישי שוב יישאר הגבר המועדף יחיד
והשאר יישלחו אחרי כבוד לבתים אחרים.
אפשר להוכיח (בצורה לא מסובכת במיוחד) כי
סיבובים.
N
יש פתרון שיושג אחרי
הפתרון הזה ישיג את כל מה שביקשנו; כל הזוגות
יהיו יציבים משום שאין כל בן
זוג שכדאי לו לעזוב את בן זוגו
הנוכחי כדי ליצור זוג חדש.
כדי שהדברים לא ייראו
תאורטיים מדי, ניתן דוגמה
פשוטה ובה שלושה גברים
ושלוש נשים. הגברים הם
אוריה, אמנון ואדם; והנשים
הן בת שבע, תמר וחווה. סדר
העדיפויות של כל אחד מהם
נראה כך:
אוריה - תמר, חווה, בת שבע;
אמנון - תמר, חווה, בת שבע;
אדם - חווה, בת שבע, תמר;
בת שבע - אמנון, אוריה, אדם;
תמר - אדם, אמנון, אוריה;
חווה - אדם, אוריה, אמנון.
ללא האלגוריתם ואילו נתנו לשוק החופשי לפעול
עצמאית, היו יכולים להיווצר הרבה מאוד שידוכים לא
יציבים, למשל:
בת שבע - אדם;
תמר - אמנון;
אוריה - חווה.
מדוע? משום שלפי רשימת ההעדפות שלעיל, אדם
מעדיף את חווה על פני בת שבע, וחווה מעדיפה את
בגלל מיעוט האפשרויות
התפתח מצב שבו מתמחים
התקבלו להתמחות ואישרו
את בואם, אך כשקיבלו
הצעה טובה יותר נטשו את
המקום שהתחייבו לו ועברו
למקום אחר. אותן תופעות
אירעו גם בכיוון ההפוך
אפריל 5102
עורך הדין
׀
70