Skip to content
بازگشت به نتایج جست‌وجو

چرخه‌های مبادله برتر

معرفی‌شده توسط
Lloyd Shapley, Herbert Scarf
سال
1974
نوع
algorithm
خانواده
Game-theoretic

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

چرخه‌های مبادله برتر (TTC) الگوریتمی برای تخصیص کالا‌های تجزیه‌ناپذیر به عامل‌ها است به گونه‌ای که تخصیص از نظر پارِتو کارا و از نظر فردی عقلانی باشد. این الگوریتم که در سال ۱۹۷۴ توسط لوید شاپلی و هربرت اسکارف توسعه یافت، چرخه‌های مبادله را در یک گراف جهت‌دار اولویت شناسایی کرده، آن مبادلات را اجرا می‌کند و به طور مکرر تکرار می‌کند تا زمانی که هیچ مبادله‌ی سودمند دیگری باقی نماند.

TTC به دلیل کارایی و سادگی پیاده‌سازی در تبادل کلیه و تخصیص مسکن کاربرد فراوانی دارد.

شهود پشت روش

گروهی از افراد را تصور کنید که هر کدام صاحب یک خانه هستند و هر فرد تمام خانه‌ها را بر اساس اولویت رتبه‌بندی می‌کند. الگوریتم TTC می‌پرسد: محبوب‌ترین فرد من کیست؟ به او اشاره کن. اکنون ببین چه کسی به تو اشاره کرده است. اگر یک چرخه وجود داشته باشد (الف به ب اشاره می‌کند، ب به ج اشاره می‌کند، ج به الف اشاره می‌کند)، آن مبادلات را اجرا کنید—الف خانه‌ی ب را می‌گیرد، ب خانه‌ی ج را می‌گیرد، ج خانه‌ی الف را می‌گیرد. همه در چرخه خوشحال هستند زیرا خانه‌ای را گرفته‌اند که به خانه‌ی فعلی خود ترجیح می‌دهند. چرخه را حذف کرده و تکرار کنید تا زمانی که چرخه‌ی دیگری باقی نماند. نتیجه کارا است زیرا تمام مبادلات سودمند انجام شده است.

تاریخ

لوید شاپلی و هربرت اسکارف الگوریتم چرخه‌های مبادله برتر را در سال ۱۹۷۴ به عنوان راه‌حلی برای مسئله بازار مسکن معرفی کردند و اثبات کردند که تخصیص‌های منحصر به فرد پارِتو کارا را ارائه می‌دهد. این الگوریتم از طریق کار آلوین راث در زمینه تبادل کلیه، که در آن تطبیق اهداکنندگان و گیرندگان در آن مرکزی شد، اهمیت عملی پیدا کرد. جایزه نوبل سال ۲۰۱۲ به راث، اهمیت TTC را برای طراحی بازار در دنیای واقعی، به ویژه در پیوند اعضا، تأیید کرد.

چه زمانی استفاده شود

هنگام تخصیص کالا‌های تجزیه‌ناپذیر (خانه‌ها، اندام‌ها، صندلی‌های مدرسه) به عامل‌ها با اولویت‌های اکید بر روی بسته‌ها، از TTC استفاده کنید. زمانی که کارایی پارِتو ضروری است و هیچ‌گونه انتقال پولی در دسترس یا مطلوب نیست، از آن استفاده کنید. TTC برای بازارهای غیرمتمرکز که در آن عامل‌ها می‌توانند مبادلات سودمند را به صورت محلی شناسایی کنند، ایده‌آل است. زمانی که عامل‌ها اطلاعات اولویت کامل و بدون چرخه دارند، بهترین عملکرد را دارد.

محدودیت‌ها و ملاحظات

  • نیاز به ترتیب اولویت اکید بدون بی‌تفاوتی؛ بسط‌ها برای اولویت‌های ضعیف پیچیده هستند
  • مقاوم در برابر ائتلاف نیست: ائتلاف‌های عامل‌ها می‌توانند اولویت‌ها را برای بهبود نتیجه جمعی به نادرستی گزارش دهند
  • حساسیت به چرخه‌های اولویت: عدم وجود چرخه‌ها می‌تواند برخی از عامل‌ها را بدون مبادله باقی بگذارد
  • محدود به تطبیق بدون انتقال پولی؛ ناکارآمد برای ارزش‌گذاری‌های ناهمگن

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • کارای پارِتو: هیچ بهبود بدون مبادله‌ای وجود ندارد؛ تمام مبادلات سودمند متقابل اجرا می‌شوند
  • عقلانی از نظر فردی: هر عامل تخصیص نهایی را به موقتی اولیه‌ی خود ترجیح ضعیفی می‌دهد
  • استراتژی-مقاوم در برخی تنظیمات: عامل‌ها نمی‌توانند با گزارش نادرست اولویت‌ها خود را بهبود بخشند
  • کارایی محاسباتی: زمان چندجمله‌ای با پیاده‌سازی ساده
  • شفاف: عامل‌ها درک می‌کنند که چگونه انتخاب اشاره شده آن‌ها منجر به تخصیص می‌شود

کاربردها

  • تبادل کلیه: تطبیق اهداکنندگان و گیرندگان عضو برای افزایش سازگاری پیوند از طریق مبادلات چندجانبه
  • تخصیص مسکن: تخصیص کارآمد اتاق‌های خوابگاه دانشگاه یا واحدهای مسکن عمومی
  • انتخاب مدرسه: تخصیص دانش‌آموزان به مدارس با محدودیت ظرفیت و تنوع اولویت
  • تبادل لوب کبد: تسهیل مبادلات اهدای جفتی برای پیوند کبد با اهداکننده زنده
  • مبادله مبلمان و کالا: سازماندهی مبادلات پایاپای کارآمد در پلتفرم‌های اشتراک‌گذاری جامعه

چگونه کار می‌کند

چگونه کار می‌کند

1

یک گراف جهت‌دار ایجاد کنید که در آن هر عامل به عامل مورد علاقه‌اش در میان کسانی که هنوز در بازار هستند اشاره کند.

2

تمام چرخه‌ها را در گراف جهت‌دار پیدا کنید (دنباله‌هایی که در آن‌ها الف به ب اشاره می‌کند، ب به ج اشاره می‌کند، ...، بازگشت به الف).

3

برای هر چرخه شناسایی شده، مبادلات را اجرا کنید: هر عامل موقتی را که به آن اشاره کرده است دریافت می‌کند.

4

عامل‌های مبادله شده و موقتی آن‌ها را از بازار حذف کنید. گراف جهت‌دار اولویت را در میان عامل‌های باقی‌مانده بازسازی کنید و تکرار کنید تا زمانی که چرخه‌ی دیگری باقی نماند.

دام‌های رایج

  • اشتباه گرفتن کارایی پارِتو با انصاف یا عدالت؛ TTC کارایی را به حداکثر می‌رساند اما برابری نتایج را نه
  • فرض استراتژی-مقاوم بودن در تمام تنظیمات؛ TTC تنها در زمینه‌های خاصی صادقانه است (مثلاً بازارهای مسکن، نه تبادل کلیه با اولویت‌بندی)
  • نادیده گرفتن اینکه الگوریتم زمانی خاتمه می‌یابد که دیگر چرخه‌های سودآور وجود نداشته باشند، که به طور بالقوه عامل‌ها را بدون تطبیق باقی می‌گذارد
  • فراموش کردن اینکه TTC نیاز به اولویت‌های اکید بدون بی‌تفاوتی دارد؛ اعمال آن با اولویت‌های ضعیف نیاز به بسط دارد

پرسش‌های متداول

چرا کارایی پارِتو در تخصیص منابع مهم است؟

کارایی پارِتو تضمین می‌کند که هیچ عاملی را نمی‌توان بدون بدتر کردن دیگری بهتر کرد. این یک الزام حداقلی برای تخصیص «خوب» است؛ نقض آن به این معنی است که منابع هدر می‌روند و می‌توانند برای منافع کسی دوباره تخصیص یابند.

آیا TTC می‌تواند تخصیص‌های مختلفی تولید کند؟

خیر. الگوریتم TTC، با گراف جهت‌دار اولویت منحصر به فرد خود، یک تخصیص پارِتو کارای منحصر به فرد تولید می‌کند. مسیر رسیدن به آن تخصیص (ترتیب شناسایی چرخه و اجرای مبادله) ممکن است متفاوت باشد، اما نتیجه نهایی همیشه یکسان است.

چگونه TTC برای تبادل کلیه زمانی که همه جفت‌های اهداکننده-گیرنده سازگار نیستند، اصلاح می‌شود؟

در تبادل کلیه، گراف جهت‌دار اولویت فقط بر روی جفت‌های سازگار ساخته می‌شود. سپس الگوریتم چرخه‌ها و زنجیره‌های مبادله را در میان عامل‌های سازگار شناسایی می‌کند و TTC اصلی را برای در نظر گرفتن محدودیت‌های بیولوژیکی بسط می‌دهد.

روش‌های مرتبط

منابع

  1. Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.

    باز کردن مرجع DOI
    کپی شد.
  2. Roth, A. E., Sönmez, T., & Ünver, M. U. (2008). Efficient kidney exchange: Coincidence of wants in markets with compatibility. American Economic Review, 97(3), 828-851.

    باز کردن مرجع DOI
    کپی شد.