مقاله ازدواج پایدار با اولویت یک طرفه

چکیده

Many countries around the world, including Korea, use the school choice lottery system. However, this method has a problem in that many students are assigned to less-preferred schools based on the lottery results. In addition, the task of finding a good assignment with ties often has a time complexity of NP, making it a very difficult problem to improve the quality of the assignment. In this paper, we prove that the problem of finding a stable matching that maximizes the student-oriented preference utility in a two-sided market with one-sided preference can be solved in polynomial time, and we verify through experiments that the quality of assignment is improved. The main contributions of this paper are as follows. We found that stable student-oriented allocation in a two-sided market with one-sided preferences is the same as stable allocation in a two-sided market with symmetric preferences. In addition, we defined a method to quantify the quality of allocation from a preference utilitarian perspective. Based on the above two, it was proven that the problem of finding a stable match that maximizes the preference utility in a two-sided market with homogeneous preferences can be reduced to an allocation problem. In this paper, through an experiment, we quantitatively verified that optimal student assignment assigns more students to schools of higher preference, even in situations where many students are assigned to schools of low preference using the existing assignment method.

چکیده به فارسی (ترجمه ماشینی)

بسیاری از کشورها در سراسر جهان ، از جمله کره ، از سیستم قرعه کشی انتخاب مدرسه استفاده می کنند.با این حال ، این روش مشکلی دارد که بسیاری از دانش آموزان بر اساس نتایج قرعه کشی به مدارس کمتر ترجیح داده می شوند.علاوه بر این ، وظیفه یافتن یک تکلیف خوب با روابط ، اغلب پیچیدگی زمانی NP دارد و این امر باعث می شود تا کیفیت تکالیف بهبود یابد.در این مقاله ، ما ثابت می کنیم که مشکل پیدا کردن یک تطبیق پایدار که به حداکثر رساندن ابزار اولویت دانش آموزان محور در یک بازار دو طرفه با اولویت یک طرفه می تواند در زمان چند جمله ای حل شود ، و ما از طریق آزمایشات تأیید می کنیم که کیفیت تکالیفبهبود یافته استسهم اصلی این مقاله به شرح زیر است.ما دریافتیم که تخصیص پایدار دانشجویی گرا در یک بازار دو طرفه با ترجیحات یک طرفه همان تخصیص پایدار در یک بازار دو طرفه با ترجیحات متقارن است.علاوه بر این ، ما روشی را برای تعیین کمیت کیفیت تخصیص از دیدگاه سودمند ترجیح دادیم.بر اساس دو مورد فوق ، ثابت شد که مشکل پیدا کردن یک مسابقه پایدار که حداکثر کاربرد اولویت را در یک بازار دو طرفه با ترجیحات همگن به حداکثر می رساند ، می تواند به یک مشکل تخصیص کاهش یابد.در این مقاله ، از طریق یک آزمایش ، ما از نظر کمی تأیید کردیم که تکالیف بهینه دانش آموزان دانش آموزان بیشتری را به مدارس با ترجیح بالاتر اختصاص می دهد ، حتی در شرایطی که بسیاری از دانش آموزان با استفاده از روش تکلیف موجود به مدارس با ترجیح کم اختصاص می یابند.