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

נניח, למשל, שיש באי רק שני גברים שנקרא להם "חתיכי", ו"סתם" ושתי נשים "יפה" ו"ככה". הגברים מדרגים את "יפה" מעל "ככה", והנשים את "חתיכי" מעל "סתם".

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

אולם אם נבחר באפשרות השנייה, "חתיכי" ו"יפה"  יבגדו בבני זוגם ויתחברו ביניהם. האפשרות הראשונה היא יציבה (למרות ש"סתם", ו"ככה" יהיו מאוכזבים) והשנייה לא (ראו איור 1).

מה יקרה אם יהיה מספר גדול של גברים ונשים באי, ולכן יהיו הרבה אפשרויות לשידוכים? האם ישנה אפשרות שתבטיח יציבות? נושא זה נדון כחלק מ"תורת המשחקים", שהיא ענף של מתמטיקה המשולב גם בתחומי הכלכלה, הפסיכולוגיה, האקולוגיה ועוד.  בשנת 1962 פרסמו שני המתמטיקאים דייוויד גייל ולויד שייפלי מאמר, בו הוכיחו כי לכל בעיית שידוכים כזאת ניתן למצוא שידוך יציב [1]. בשנת 2012 זכה לויד שייפלי בפרס נובל לכלכלה,  בין היתר על תרומה זו (דייוויד גייל נפטר בשנת 2008).

ההוכחה הייתה באמצעות תיאור אלגוריתם פשוט, הפועל בשלבים. בהתחלה, כל אישה נמצאת באוהל נפרד משלה. בכל שלב קורים הדברים הבאים: 

1. כל גבר ניגש אל אוהלה של האישה המועדפת עליו, מבין הנשים שלא דחו אותו עד כה.
2. כל אישה שמספר גברים צובאים ליד פתח אוהלה, משאירה את הגבר המועדף מביניהם לעמוד ליד האוהל, ואת השאר שולחת לנסות את מזלם באוהלים אחרים.
3. שלבים 1 ו-2 חוזרים על עצמם עד אשר כל אחד מהגברים נמצא בגפו ליד אוהלה של אישה שלא דחתה אותו (איור 2). זהו סיומו של האלגוריתם.

ניתן להוכיח די בקלות שהשיטה עובדת [1] (אפילו אם נחליף בין תפקידי הנשים והגברים...). הכלכלן היהודי אמריקאי אלווין רות הראה שלאלגוריתם זה יש יישומים רבים, כמו למשל שיבוץ מתמחים לרפואה בבתי חולים [2].

דוגמאות והרחבות רבות לאלגוריתם, כמו גם שלל חומרים נוספים תוכלו למצוא בלשונית "הבזקי חדשות במתמטיקה" באתר "רמזור למורה" [3]. הבזקי החדשות ממתמטיקה הם מפעל עתיר השקעה של צוות בראשותה של פרופ' נצה מובשוביץ-הדר, מפעל שמטרתו להציג את הנעשה במתמטיקה בת זמננו בפני תלמידי תיכון כדי להראות להם את הרלוונטיות וגם את היופי של המתמטיקה. המצגת על שידוכים, כמו גם אחרות, בנויות בצורה פשוטה המותאמת במיוחד להצגה לתלמידים, ומורים עוברים השתלמויות לקראת הצגתם. אנו מתכוונים להביא דוגמאות נוספות כדי לשדך את נפלאות המתמטיקה לכול-לם.

תודות לפרופ' נצה מובשוביץ-הדר על הייעוץ בהכנת הכתבה

קומיקס: דניאל הלטובסקי

מקורות קריאה נוספת

[1] שידוך יציב 

[2]  שידוכים ברפואה - ציטוט מתוך ספרו של פרופ' אייל וינטר "רגשות רציונליים"

[3] הבזקי מתמטיקה