מעגלי סחר עליונים
מעגלי סחר עליונים (באנגלית: Top Trading Cycle; TTC) הוא אלגוריתם להקצאת פריטים ללא שימוש בכסף. האלגוריתם פותח על ידי דייוויד גייל ופורסם על ידי הרברט סקרף ולויד שפלי.[1]
דוגמה לאלגוריתם
עקרונות אלגוריתם ה- TTC מוצגים על ידי הדוגמה להלן משוק הדיור. ישנם סטודנטים המתגוררים במעונות הסטודנטים. כל תלמיד גר לבדו בבית יחיד. לכל תלמיד יש יחס העדפה לגבי כל הבתים, ומספר תלמידים מעדיפים את הבתים שהוקצו לתלמידים אחרים על פני אלו שברשותם. כלומר ההקצאת הבתים אינה בהכרח יעילה. מצב זה עשוי להוביל לחילופים הדדים שיועילו לשני הצדדים. לדוגמה, אם תלמיד א' מעדיף את הבית שהוקצה לתלמיד ב' ולהפך, שניהם יפיקו תועלת מהחלפת הבתים ביניהם. אם כך, מטרת האלגוריתם היא למצוא הקצאה חדשה של בתים לתלמידים, כך שכל החילופים ההדדיים שמועילים לשני הצדדים יתממשו. כלומר, מצב בו תלמידים לא יוכלו לשפר יחד את מצבם על ידי החלפת הבתים ביניהם.
האלגוריתם פועל באופן הבא:
- לשאול כל סוכן מהי הבחירה המועדפת עליו - מהו הבית המועדף.
- לצייר חץ מהסוכן לסוכן המכונה , שמחזיק את הבית המועדף על סוכן .
- יש לפחות מעגל אחד בתרשים (ייתכן מעגל באורך 1, אם סוכן כלשהו מחזיק בבית המועדף עליו).
- ליישם את המעגל שנוצר. כלומר, להקצות מחדש כל בית לסוכן שמצביע עליו.
- להסיר מהתרשים את הסוכנים שמוערבים במעגל שנוצר.
- אם נותרו סוכנים בתרשים, חוזרים לשלב 1.
האלגוריתם הוא סופי, מכיוון שבכל שלב אנו מסירים לפחות סוכן אחד.
לדוגמה,[2] נניח העדפות סוכנים כדלקמן (רק ארבע העדפות העליונות רלוונטיות להדגמה):
| סוכן: | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| בחירה ראשונה: | 3 | 3 | 3 | 2 | 1 | 2 |
| בחירה שנייה: |
2 | 5 | 1 | 5 | 3 | 4 |
| בחירה שלישית: |
4 | 6 | . . . | 6 | 2 | 5 |
| בחירה רביעית: |
1 | . . . | . . . | 4 | . . . | 6 |
| . . . | . . . | . . . | . . . | . . . | . . . | . . . |
בשלב הראשון, קיים רק מעגל סחר אחד והוא של סוכן 3 אשר מעדיף לשמור על ביתו הנוכחי. אם כך סוכן 3 עוזב את השוק וכן בית מספר 3.
בשלב השני, מכיוון שבית 3 יצא מהשוק, הבית המועדף על סוכן 1 הוא בית 2, הבית המועדף על סוכן 2 הוא בית 5 ושל סוכן 5 הוא בית 1. לפיכך, נוצר מעגל סחר עליון {1,2,5} כך שכל השלושה מקבלים את העדפתם העליונה ועוזבים את השוק.
בשלב השלישי, נוצר מעגל סחר עליון {4,6} והסוכנים 4 ו-6 מחליפים ביניהם בתים.
אם כך, לא נותרו סוכנים והמשחק נגמר. ההקצאה הסופית היא:
| סוכן: | 1 | 2 | 3 | 4 | 5 | 6 |
| בית: | 2 | 5 | 3 | 6 | 1 | 4 |
הקצאה זו היא יציבה, מכיוון שאף קואליציה (כלומר קבוצת סוכנים) לא יכולה לשפר את מצבה על ידי מסחר הדדי.
דוגמה נוספת לשימוש באלגוריתם: נניח 7 רופאים שהוקצו למשמרות ערב; כל רופא מוקצה למשמרת אחת בשבוע. חלק מהרופאים מעדיפים משמרות שניתנו לרופאים אחרים. גם בדוגמה זו האלגוריתם יכול להשיג רווחה חברתית מרבית.
אמינות
TTC הוא מנגנון אמין כך שאמירת העדפות אמיתיות היא אסטרטגיה דומיננטית.[3]
הרחבות
זהו המנגנון היחיד שעונה על דרישות הרציונליות של הפרט, יעילות פארטו ואמירת אמת, דבר ההופך אותו לכלי הקצאה מרכזי בבעיות רלוונטיות.
להלן הרחבות חשובות של המנגנון:
1. השימוש במנגנון הורחב למצבים בהם יש תחלופת סטודנטים - ישנם סטודנטים בעלי בית, סטודנטים חדשים וחדרים שהתפנו.[4]
2. השימוש במנגנון הורחב לשיבוץ בתי ספר.[5] המנגנון אומץ בשנת 2012 בניו אורלינס בבתי הספר המחוזיים.[6]
3. השימוש במנגנון הורחב לשיבוץ השתלות כליה. המנגנון המורחב נקרא שרשאות ומעגלי סחר עליונים (TTCC).[7]
הערות שוליים
- ^ Shapley, Lloyd; Scarf, Herbert (1974). "On cores and indivisibility". Journal of Mathematical Economics. 1: 23. doi:10.1016/0304-4068(74)90033-0.
- ^ Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
- ^ "Incentive compatibility in a market with indivisible goods". Economics Letters (באנגלית). 9 (2): 127–132. 1982-01-01. doi:10.1016/0165-1765(82)90003-9. ISSN 0165-1765.
- ^ Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999). "House Allocation with Existing Tenants". Journal of Economic Theory. 88 (2): 233–260. doi:10.1006/jeth.1999.2553.. See also Presentation by Katharina Schaar.
- ^ Abdulkadiroğlu, Atila; Sönmez, Tayfun (2003). "School Choice: A Mechanism Design Approach". American Economic Review. 93 (3): 729–747. doi:10.1257/000282803322157061.
- ^ Vanacore, Andres (16 באפריל 2012). "Centralized enrollment in Recovery School District gets first tryout". The Times-Picayune. New Orleans. נבדק ב-4 באפריל 2016.
{{cite news}}: (עזרה) - ^ Roth, Alvin; Sönmez, Tayfun; Unver, M. Utku (2004). "Kidney Exchange". Quarterly Journal of Economics. 119 (2): 457–488. doi:10.1162/0033553041382157.
27803861מעגלי סחר עליונים