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

الگوریتم گیل-شپلی

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

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

اندازه قلم

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

الگوریتم گیل-شپلی مسئله ازدواج پایدار را حل می‌کند: چگونه دو گروه (مثلاً دستیاران پزشکی به بیمارستان‌ها، دانشجویان به مدارس) را با هم تطبیق دهیم به گونه‌ای که هیچ زوجی یکدیگر را به شرکای اختصاص‌یافته خود ترجیح ندهند. این الگوریتم که توسط دیوید گیل و لوید شپلی در سال ۱۹۶۲ معرفی شد، یک تطبیق پایدار را در زمان چندجمله‌ای از طریق یک فرآیند پذیرش تعویقی تضمین می‌کند که در آن یک طرف به صورت متوالی پیشنهاد می‌دهد و طرف دیگر پاسخ می‌دهد و با رسیدن گزینه‌های بهتر، انتخاب‌ها را بازبینی می‌کند.

شهود پشت روش

تطبیق پزشکان با بیمارستان‌ها را تصور کنید. این الگوریتم مانند بازی صندلی‌بازی عمل می‌کند: هر پزشک به بیمارستان مورد علاقه خود پیشنهاد می‌دهد؛ هر بیمارستان به طور موقت بهترین پزشک موجود را می‌پذیرد. با دریافت پیشنهادهای بهتر، بیمارستان‌ها انتخاب‌های خود را بازبینی می‌کنند و احتمالاً پذیرش‌های قبلی را لغو می‌کنند. پزشکانی که رد می‌شوند، به بیمارستان مورد علاقه بعدی خود پیشنهاد می‌دهند. این فرآیند تا زمانی ادامه می‌یابد که هیچ پزشکی تمایل به پیشنهاد بیشتر نداشته باشد و هیچ بیمارستانی تمایل به تغییر تطبیق فعلی خود نداشته باشد. نتیجه پایدار است: هیچ زوج پزشک-بیمارستانی وجود نخواهد داشت که هر دو ترجیح دهند به جای شرکای اختصاص‌یافته خود، با یکدیگر تطبیق داده شوند.

تاریخ

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

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

الگوریتم گیل-شپلی را هنگام تطبیق بازارهای دوطرفه که پایداری در آنها حیاتی است، به کار ببرید: جایابی دستیاران پزشکی، تخصیص دانشجو به مدرسه، تبادل کلیه، تطبیق بازار کار، یا بازارهای دوست‌یابی آنلاین. زمانی از آن استفاده کنید که خطر بی‌ثباتی تطبیق (زوج‌های مسدودکننده) وجود دارد که می‌تواند یک تطبیق را پس از تخصیص از بین ببرد. این الگوریتم زمانی ایده‌آل است که یک طرف می‌تواند با یک مزیت استراتژیک ابتدا حرکت کند.

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

  • بهینه پارتو نیست: تطبیق ممکن است رفاه کل را به حداکثر نرساند؛ ممکن است زوج‌های مسدودشده‌ای وجود داشته باشند که همگی می‌توانند از مبادله شرکا بهره‌مند شوند.
  • آسیب‌پذیری استراتژیک: طرف پیشنهاددهنده می‌تواند با ارائه نادرست ترجیحات سود ببرد، در حالی که طرف پاسخ‌دهنده صادق است.
  • عدم تقارن: نتایج به شدت به این بستگی دارد که کدام طرف ابتدا پیشنهاد می‌دهد.
  • محدودیت‌ها را مدیریت نمی‌کند: گنجاندن ترجیحات پیچیده (مانند زوج‌ها، ترجیحات منطقه‌ای) بدون تغییر الگوریتمی دشوار است.

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

نقاط قوت

  • پایداری تضمین‌شده: هیچ زوج مسدودکننده‌ای در تطبیق نهایی وجود ندارد.
  • زمان چندجمله‌ای: پیچیدگی O(n^2)، که آن را برای جمعیت‌های بزرگ کارآمد می‌کند.
  • پیاده‌سازی ساده: اجرای آن در عمل با جمع‌آوری شفاف ترجیحات آسان است.
  • مشوق‌های استراتژیک: طرف پیشنهاددهنده دارای مزیت استراتژیک است و پیشنهادهای اولیه را به پیشنهادهای بعدی ترجیح می‌دهد.
  • کاربرد جهانی: برای هر نوع پروفایل ترجیحات بدون فرض محدب بودن یا ترایایی کار می‌کند.

کاربردها

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

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

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

1

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

2

در هر دور، هر فرد نامتطابق در سمت پیشنهاددهنده به بالاترین رتبه‌بندی شده در سمت دیگر که هنوز به او پیشنهاد نداده است، پیشنهاد می‌دهد.

3

هر فرد در سمت گیرنده به طور موقت پیشنهاد را می‌پذیرد اگر نامتطابق باشد، یا اگر پیشنهاددهنده رتبه بالاتری نسبت به شریک فعلی او داشته باشد، که در این صورت نامزدی قبلی را لغو می‌کند.

4

الگوریتم زمانی متوقف می‌شود که هر فردی تطبیق داده شده باشد و هیچ پیشنهاد دیگری رخ ندهد، که منجر به یک تطبیق پایدار می‌شود.

دام‌های رایج

  • فرض اینکه پایداری به تنهایی برای انصاف یا رفاه کافی است؛ تطبیق‌های پایدار می‌توانند به شدت به نفع یک طرف باشند.
  • اشتباه گرفتن پایداری با بهینگی؛ یک تطبیق پایدار لزوماً رفاه را به حداکثر نمی‌رساند.
  • نادیده گرفتن مزیت استراتژیک طرف پیشنهاددهنده: اعضای طرف پیشنهاددهنده تمایل دارند با شرکای با رتبه بالاتر تطبیق داده شوند.
  • فراموش کردن اینکه الگوریتم فهرست‌های ترجیحات کامل را فرض می‌کند؛ ترجیحات ناقص نیاز به اصلاح دارند.

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

چرا پایداری در تطبیق مهم است؟

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

آیا الگوریتم گیل-شپلی همیشه یک تطبیق یکسان تولید می‌کند؟

خیر. فهرست‌های ترجیحات یا ترتیب‌های پیشنهاد متفاوت می‌توانند تطبیق‌های پایدار متفاوتی را به همراه داشته باشند. با این حال، همیشه یک تطبیق پایدار «مرد-بهینه» (بهترین برای همه پیشنهاددهندگان) و یک تطبیق پایدار «زن-بهینه» (بهترین برای همه پاسخ‌دهندگان) وجود دارد.

الگوریتم گیل-شپلی چگونه ترجیحات گروه‌ها (مانند زوج‌ها) را مدیریت می‌کند؟

الگوریتم استاندارد مستقیماً زوج‌ها یا سایر محدودیت‌ها را مدیریت نمی‌کند. افزونه‌هایی مانند الگوریتم زوج‌ها وجود دارند اما پیچیده‌تر هستند و ممکن است پایداری را برای همه پروفایل‌های ترجیحات تضمین نکنند.

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

منابع

  1. Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.

    باز کردن مرجع DOI
    کپی شد.
  2. Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.

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