مسأله ازدواج پایدار و برخی کاربردهای آن

سید رضا موسوی — Tue, 04 Jul 2023 12:14:00 +0330

مسئله ازدواج پایدار یک مسئله در نظریه بازی است که اولین بار توسط گیل و شاپلی در سال 1962 در مقاله‌ای با عنوان «پذیرش‌های دانشگاه و پایداری ازدواج» مورد مطالعه قرار گرفت [2] .بعد از کار اصلی گیل و شاپلی، ازدواج پایدار و مسائل تخصیص پایدار مرتبط برای مسائل بسیاری در دنیای واقعی استفاده شده است. قابل ذکر است که راث و شاپلی در سال 2012 به خاطر کارشان در زمینه تخصیص پایدار برنده جایزه نوبل اقتصاد شدند.آیا شما می‌توانید به یک ریاضی‌دان اعتماد کنید تا شما را در امر ازدواج با یک جنس مخالف در تطابق قرار دهد (یا جفت کند)؟فرض کنید شما یک گروه از مردان و یک گروه از زنان دارید که می خواهند ازدواج کنند. گیل و شاپلی می‌خواستند ببینند که آیا می‌توانند الگوریتمی ارائه کنند تا همه را تا حد امکان با خوشحالی جفت کند.هدف یافتن تطابق پایدار بین دو گروه از افرادی است که اولویت‌ها، ترجیحات و نظرات متفاوتی در مورد اینکه چه کسی بهترین زوج برای آنهاست، دارند. مفهوم اصلی این است که تطابق‌ها باید پایدار باشند. نباید دو نفر وجود داشته باشند که یکدیگر را به زوج‌های واقعی که الگوریتم به آنها نسبت داده است ترجیح دهند.گیل و شاپلی الگوریتم خواستگاری (یا الگوریتم گیل-شاپلی) را پیشنهاد دادند. این الگوریتم سیستمی را ایجاد می‌کند که به وسیله آن همه می توانند شخصی را که بیشتر ترجیح می‌دهند از بین کسانی که آنها را ترجیح می‌دهند پیدا کنند. در این الگوریتم زن و مرد هر کدام ترجیحات و اولویت‌های خود را رتبه‌بندی می‌کند.و سپس تخصیص هر زن به یک مرد با استفاده از الگوریتم خواستگاری گیل-شاپلی انجام می‌شود:برای هر تعداد زوج، صرف نظر از اینکه چگونه یکدیگر را اولویت‌بندی می‌کنند، می‌توان از الگوریتم گیل-شاپلی برای یافتن حداقل یک تطابق پایدار برای هر فرد استفاده کرد. اما شاید متوجه شده باشید که در دنیای واقعی، آشنایی یا ازدواج دقیقاً اینگونه نیست. پس ارزش این نوع تحقیق چیست؟گیل و شیپلی واقعاً در تلاش برای شکستن کدهای عاشقانه نبودند. چیزی که آنها به دنبال آن بودند، رویکردی به بازارهای به اصطلاح تطبیق (matching markets) بود - جایی که عرضه و تقاضا وجود دارد، اما هیچ پولی دست به دست نمی‌شود. ازدواج به سادگی راهی برای نشان دادن این مسأله بود.گیل و شاپلی وقتی شروع کردند، کارشان صرفاً تئوری بود. اما همانطور که اغلب در مورد تحقیقات پایه اتفاق می‌افتد، در نهایت کاربردهایی در مسائل عملی و مهم پیدا کرد.در ادامه به برخی از کاربردهای مهم این مسأله می‌پردازیم. اختصاص پزشکان جدید به بیمارستان هادر دهه 1980، یک اقتصاددان دانشگاه هاروارد به نام آلوین راث علاقه‌مند بود که با کمک از ایده های تئوری و نظری برای بهبود سیستم‌های دنیای واقعی فکر کند. او می‌خواست بازارهای تطبیقی را که کار نمی‌کنند تشخیص دهد و الگوریتم گیل-شپلی را برای کمک به کارآمدتر کردن کارکرد آنها تطبیق دهد.راث، با حمایت بنیاد ملی علوم، شروع به بررسی برنامه تطبیق دستیاری پزشکی ملی (NRMP) کرد، سیستمی که پزشکان جدید را به بیمارستان‌های سراسر کشور تخصیص می‌دهد. در دهه 1990، NRMP با مشکلات بسیاری مواجه بود؛ زیرا پزشکان و بیمارستان‌های جدید اغلب هر دو از کارهای آنان ناراضی بودند.راث از کار گیل و شپلی برای تغییر شکل الگوریتم تطبیق NRMP استفاده کرد تا تخصیص‌هایی را ایجاد کند که پایدارتر باشند.جفت کردن دانش آموزان با مدارس دولتیالگوریتم گیل-شپلی همچنین در کمک به مدارس شهری در مناطق بزرگ برای اختصاص دانش آموزان به مدارس مفید بوده است. در شهر نیویورک، مانند بسیاری از شهرها، دانش‌آموزانمی‌توانند با رتبه‌بندی . اولویت‌بندی خود از میان تمام مدارس شهر، دبیرستانی را انتخاب کنند. قبل از اینکه راث و همکارانش ایده استفاده از الگوریتم ازدواج پایدار را مطرح کنند، فرآیند تخصیص دبیرستان‌ها بسیار بد بود. حدود 30000 دانش‌آموز در سال بدون دبیرستان باقی می‌ماندند و به مدارسی می‌رفتند که حتی آنها را در فهرست ترجیحات خود نیاورده بودند.البته ذکر این نکته بسیار مهم است که فرآیند انطباق پزشکان یا دانش‌آموزان کمی پیچیده‌تر از تطبیق شرکای ازدواج است، زیرا بیمارستان ها و مدارس (بر خلاف اکثر زوج‌ها) پیشنهادات زیادی را می‌پذیرند. اما اصل اساسی الگوریتم خواستگاری که گیل و شپلی معرفی کردند تقریباً مشابه است.کمک به بیماران پیوندی برای یافتن تطبیقدر سال 2004 راث الگوریتم زوج‌یابی را برای کمک به بیماران پیوندی در یافتن اهداکنندگان توسیع داد. در آن زمان، سالانه کمتر از 20 نفر از اهداکنندگان زنده کلیه دریافت می کردند؛ این موضوع در حالتی بود که پیوند از اهداکنندگان زنده نتایج بسیار بهتری را برای بیمار به همراه داشت. فراوانی این مشکل به دلیل یک مشکل ساده و دلخراش ایجاد شده بود. بسیاری از مردم مایل بودند که یک کلیه را به یکی از عزیزانشان اهدا کنند، اما نمی‌توانستند، زیرا گروه خونی و عوامل دیگر آنها را ناسازگار می‌کرد.راث یک سیستم مبادله اعضای پیوندی ابداع کرد تا به جفت‌های اهداکننده و گیرنده ناسازگار کمک کند دیگران را در موقعیت مشابه پیدا کنند. از طریق زنجیره‌های پیچیده مبادله، همه شرکت کنندگان وعده یافتن یک تطبیق مناسب را دارا می‌شدند.توازن بار سرتاسری در شبکه‌های تحویل محتواتوازن بار سرتاسری (Global load balancing) فرآیند نگاشت کلاینت‌ها به کلاسترهای سرور CDN است. به جای تصمیم‌گیری برای توازن بار به صورت خاص و جداگانه برای میلیاردها کلاینت در سرتاسر جهان، تخصیص‌های کلاستری در دانه‌بندی واحدهای نقشه انجام می‌شود. هر واحد نقشه را می‌توان به صورت دوتاییمشاهده کرد، که در آن اولین عنصر مجموعه‌ای از آدرس‌های IP کلاینت‌ها است و عنصر دوم نوع ترافیکی را که توسط آن کلاینت‌ها قابل دسترسی است توصیف می‌کند. آدرس‌های IP یک واحد نقشه خاص به گونه‌ای در نظر گرفته شده‌اند که در اینترنت به یکدیگر از نقطه نظر جغرافیایی نزدیک باشند و می‌توانند به عنوان یک واحد از منظر توازن بار مشاهده شوند. به‌عنوان مثال، زمانی که به آنها یک کلاستر مشابه CDN اختصاص داده می‌شود، احتمالاً عملکرد مشابهی را تجربه می‌کنند. دومین عنصر دوتایی واحد نقشه، کلاس ترافیکی است که مشتریان واحد نقشه به آن دسترسی دارند. یک کلاس ترافیک نوع سرویس محتوایی که کاربران به آن دسترسی دارند را نشان می‌دهد. ده‌ها کلاس ترافیک مانند ویدیو، محتوای وب، برنامه های کاربردی، دانلود نرم افزار و غیره وجود دارد که هر کدام دارای ویژگی‌های متمایزی هستند. به عنوان یک مثال ساده، واحد نقشه <1.2.3.4/24, video> مربوط به مجموعه مشتریانی است که در یک زیرشبکه /24 خاص به درخواست ویدیو دارند. توجه داشته باشید که مجموعه‌ای از کاربرانی که به محتوای وب دسترسی دارند، واحد نقشه متفاوت <1.2.3.4/24, web> را تشکیل می‌دهند. اگر بلوک آدرس‌های IP خیلی درشت باشد، تخصیص واحد نقشه به یک کلاستر ممکن است عملکردی کمتر از حد مطلوب برای برخی از آن آدرس‌ها ایجاد کند. اما اگر دانه‌بندی خیلی خوب باشد، تعداد واحدهای نقشه بسیار زیاد خواهد شد که منجر به مشکلات مقیاس‌پذیری می‌شود. تقسیم سرویس گیرندگان اینترنت جهانی به پیشوندها در سطح مناسبی از جزئیات، به خودی خود یک مشکل پیچیده است، اما فراتر از محدوده این مقاله است. در مجموع، داشتن ده‌ها میلیون واحد نقشه مرسوم است تا همه مشتریان و کلاس‌های ترافیک تریلیون‌ها درخواستی که در روز توسط سرویس‌های تحویل محتوا ارائه می‌شوند را به تصویر بکشد. هدف از توازن بار سرتاسری تخصیص هر واحد نقشه M_i، به یک کلاستر سرور C_j است، به گونه ای که کلاینت‌های مشخص‌شده توسط هر واحد نقشه بتوانند محتوای درخواستی را از کلاستر اختصاص داده شده به آن با دسترسی و عملکرد خوب دریافت کنند. برای هر واحد نقشه، کلاسترهای نامزد به ترتیب اولویت نزولی مرتب می‌شوند که در آن اولویت بالاتر نشان‌دهنده عملکرد پیش‌بینی‌شده بهتر برای مشتریان آن واحد نقشه است. برای مثال، یک کلاستر نامزد با اولویت بالاتر ممکن است کلاستری با تأخیر کمتر، از دست دادن بسته کمتر و توان عملیاتی بالاتر برای مشتریان در واحد نقشه باشد. به همین ترتیب، هر کلاستر سرور C_j در مورد واحدهای نقشه‌ای که می‌خواهد سرویس دهد، اولویت‌هایی دارد. عوامل متعددی ترجیحات یک کلاستر را برای واحدهای نقشه تعیین می‌کنند. از جمله شرایط قراردادی و جغرافیایی که کلاستر در آنجا و تحت آن مستقر شده است و غیره. به عنوان نمونه یک کلاستر مستقر در یک ISP ارائه‌دهنده بالادستی ممکن است ترجیح دهد به مشتریان در ISPهای پایین دست خدمات ارائه دهد.واحدهای نقشه تقاضا می‌کنند در حالی که کلاستر‌ها ظرفیت پاسخگویی به آن تقاضاها را دارند. به هر واحد نقشه M_i یک تقاضای d_i مرتبط شده است، که نشان دهنده میزان دسترسی به محتوایی است که مشتریان متعلق به آن واحد نقشه احتمالاً ایجاد می‌کنند. تقاضاها می‌توانند به در زمان‌های مختلف متفاوت باشند، زیرا مشتریان در زمان‌های مختلف ممکن است محتوای بیشتر (یا کمتری) را درخواست نمایند. هر کلاستر C_j همچنین دارای مفهومی از ظرفیت c_j است که نشان دهنده حداکثر تقاضایی است که کلاستر می‌تواند ارائه دهد. ظرفیت بر اساس قدرت پردازش، ظرفیت حافظه و پهنای باند شبکه که سرورها در کلاستر دارند تعیین می‌شود. هدف توازن بار سرتاسری تخصیص واحدهای نقشه به کلاستر‌ها است به صورتی که اولویت‌ها در نظر گرفته شوند و محدودیت‌های ظرفیت برآورده شوند.تطبیق رانندگان و مسافران در یک پلتفرم اشتراک‌گذاری تاکسیدر پلتفرم‌های اشتراک‌گذاری تاکسی مانند Uber میلیون‌ها ماشین در روز در سراسر جهان درخواست می‌شود. هر بار که مسافر درخواست تاکسی می‌کند، سکو باید راننده‌ای را پیدا کند تا آن مسافر را به مقصد برساند. برای اطمینان از یک انتخاب به موقع، آن راننده در حال حاضر باید تا حد امکان به آن مسافر نزدیک باشد. علاوه بر این، این پلتفرم می‌تواند مقصد مسافر را هنگام انتخاب رانندگان در نظر بگیرد، زیرا برخی از رانندگان ممکن است ترجیح دهند سفرهایی را که آن‌ها را از خانه خیلی دور می‌کند، نپذیرند. به عبارت دیگر، مسافران نسبت به رانندگان ترجیح دارند و رانندگان نیز بر مسافران ترجیح دارند. آیا الگوریتم سریعی وجود دارد که بتواند این انطباق‌ها را انجام دهد؟ الگوریتمی که پلتفرم Uber استفاده می‌کند batched matching نام دارد که تعمیمی از مسأله ازدواج پایدار است.نتیجه‌گیری تمامی این کاربردها و کاربردهای دیگری که در اینجا مجال صحبت در مورد آنها نیست باعث شد شاپلی و راث در سال 2012 جایزه نوبل را دریافت کنند. (دیوید گیل در سال 2008 درگذشت، بنابراین واجد شرایط دریافت این جایزه نبود. شپلی در سال 2016 درگذشت. روحشان شاد و یادشان گرامی.)الگوریتم گیل-شاپلی در حال حاضر نیز برای کاربردهای دیگری مانند کمک به بچه‌های پرورشگاهی در یافتن والدین جدید استفاده می‌شود. حتی در قرن بیست و یکم کاربردهای عاشقانه پیدا کرده است که بر رویکردهای دوستیابی آنلاین و دوستیابی سریع تأثیر می‌گذارد.هر اختراع یا نوآوری مدرن را در نظر بگیرید و در تاریخ آن دهه‌ها (یا حتی قرن‌ها) تحقیقات عجیب و غریب و مبهم که منجر به ایجاد آن شده است را خواهید یافت. یکی از ویژگی های علم این است که راه رسیدن به دانش اغلب غیرمستقیم است. علاوه بر تحقیقات دقیق، اکتشاف غالباً به واسطه دلتنگی و کنجکاوی انسانی شکل می‌گیرد. وقتی گیل و شپلی شروع به کار کردند، کارشان تئوری و انتزاعی بود. تحقیقات آنها ممکن است مبهم یا حتی بی‌معنی به نظر برسد، اما بینش‌هایی که به‌دست آورده‌اند، پایه‌ای برای پیشرفت‌هایی ایجاد کرده است که زندگی افراد بی‌شماری را بهبود بخشیده است. امروزه تقریباً 5500 بیمار پیوندی در ایالات متحده سالانه از اهداکنندگان زنده کلیه دریافت می‌کنند. این انطباق‌ها بدون کار راث، گیل و شپلی امکان پذیر نخواهد بود. مانند عشق، تحقیقات به روش‌های مرموز کار می‌کند. نتایج و تأثیرات گاهی غیرقابل پیش‌بینی و غیرمنتظره هستند و این بخش بزرگی است که آن را بسیار مهم می‌کند.مراجع جهت مطالعه بیشتر [1] https://medium.com/@UofCalifornia/how-a-matchmaking-algorithm-saved-lives-2a65ac448698[2] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69:9--15, 1962.[3] The national resident matching program. Available at: http://www.nrmp.org/.[4] Scottish foundation allocation scheme. Available at: http://www.dcs.gla.ac.uk/pbiro/applications/uk_sfas.html.[6] National Resident Matching Program, Wikipedia,https://en.wikipedia.org/wiki/National\_Resident\_Matching\_Program[7] Canadian resident matching service. Available at: http://www.carms.ca/eng/operations_algorithm_e.shtml.[8] Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, 1989.[9] Kazuo Iwama and Shuichi Miyazaki. A survey of the stable marriage problem and its variants. In Informatics Education and Research for Knowledge-Circulating Society, 2008. ICKS 2008. International Conference on, pages 131–136. IEEE, 2008.[10] Mourad Baıou and Michel Balinski. Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry). Discrete Applied Mathematics, 101(1):1–12, 2000.[11] Roth, Alvin; Peranson, Elliott (September 1999). "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design". The American Economic Review. 89 (4): 748–780.[12] Masso, Jordi. (2015). ”The theory of stable allocations and the practice of market design. The Nobel Prize in Economics 2012 for Alvin E. Roth and Lloyd S. Shapley”. Contributions to Science. 11: 103-112. doi:10.2436/20.7010.01.218[13] Atila Abdulkadiro˘glu, Parag A. Pathak, and Alvin E. Roth. The New York City high school match. American Economic Review, pages 364–367, 2005.[14] Alvin E. Roth, Tayfun Sonmez, and M. Utku Unver. Kidney exchange. The Quarterly Journal of Economics, pages 457–488, 2004.[15] Maggs, Bruce M., and Ramesh K. Sitaraman. "Algorithmic nuggets in content delivery." ACM SIGCOMM Computer Communication Review 45.3 (2015): 52-66.

نوشته های سید رضا موسوی

مسأله ازدواج پایدار و برخی کاربردهای آن