Regency woodcut of a proposal scene, United States public domain
سه دختر و سه پسر می‌خواهند که با هم ازدواج کنند (دو به دو). هرکدام از دخترها از بین سه پسر ترجیح‌های خودشان را دارند و هرکدام از پسرها هم همین‌طور. اولیت‌های هرکدام از پسرها (از چپ به راست) به شکل زیر است (اگر با موضوع راحت نیستید، پیشنهاد می‌کنم اول این پست را بخوانید: هم‌خانه‌ای‌هایی که هیچ‌وقت راضی نیستند):
P(m1) = w2, w1, w3
P(m2) = w1, w3, w2
P(m3) = w1, w2, w3
اولیت‌های هرکدام از دخترها هم به شکل زیر است:
P(w1) = m1, m3, m2
P(w2) = m3, m1, m2
P(w3) = m1, m3, m2
برای شروع، فرض کنید بخواهیم دختر شماره یک با پسر شماره یک و به همین ترتیب دو با دو و سه با سه ازدواج کنند. روابط در شکل زیر نشان داده شده‌اند. در ضمن سمت راست نشان داده‌شده که کدام دختر و کدام پسر هردو با هم ترجیح می‌داده‌اند که به جای چیدمان پیشنهادی، با هم باشند و در نتیجه حاضرند چیدمان موجود را به هم بزنند. در هر خط وضعیت ارتباط‌ها بعد از هر تغییر زوج نشان داده شده:
{(m1, w1), (m2, w2), (m3, w3)}, unhappy: (m1, w2)
{(m1, w2), (m2, w1), (m3, w3)}, unhappy: (m3, w2)
{(m1, w3), (m2, w1), (m3, w2)}, unhappy: (m3, w1)
{(m1, w3), (m2, w2), (m3, w1)}, unhappy: (m1, w1)
{(m1, w1), (m2, w2), (m3, w3)}, unhappy: (m1, w2)
با کمال شگفتی برگشتیم به خانه‌ی اول!
با این ترتیب هیچ‌کدام از چیدمان‌ها پایدار نیست و همه در یک حلقه افتاده‌اند: همیشه در هر چیدمانی دو نفر هستند که ترجیح می‌دادند با هم باشند و حاضرند چیدمان فعلی را برای با هم بودن به هم بزنند.
اما این مساله راه حل دارد. این بار الگوریتم زیر را دنبال می‌کنیم.
- تا زمانی که مردی وجود دارد که مجرد است، این مراحل را تکرار کنید:
- یک: هر پسر مجرد به اولین دختر (با بیش‌ترین اولویت) در لیست دختران مورد علاقه‌اش که هنوز به آن‌ها پیشنهادی نداده، پیشنهاد ازدواج می‌دهد
- دو-یک: اگر دختر دریافت کننده‌ی پیشنهاد قبلا به کسی جواب مثبت نداده، به به‌ترین پیشنهاد جواب مثبت می‌دهد
- دو-دو: اگر دختر به کسی جواب مثبت داده بود، اما پیشنهاد جدید را ترجیح می‌داد، از پسر قبلی جدا می‌شود و به پسر جدید جواب مثبت می‌دهد (و پسر قبلی مجرد می‌شود)
- دو-سه: اگر دختر به کسی جواب مثبت داده بود و پیشنهاد جدید را ترجیح نمی‌داد، پیشنهاد فعلی را رد می‌کند
با استفاده از این الگوریتم پیشنهادهای ازدواج و شکل‌گیری زوج‌ها به شکل زیر خواهند بود:
Proposals: {(m1 -> w2), (m2 -> w1), (m3 -> w1)}
Intermediate: {(m1, w2), (m2), (w3), (m3, w1)}
Proposals: {(m2 -> w3)}
Final: {(m1, w2), (m2, w3), (m3, w1)}
این ترکیب پایدار است و به هم نخواهد خورد.
اما اگر به جای پسرها، دخترها پیشنهاد ازدواج بدهند چه طور؟ آیا تغییری ایجاد می‌شود؟
الگوریتم قبلی را در نظر بگیرید با این تفاوت که این بار دخترها پیشنهاد ازدواج می‌دهند و پسرها می‌پذیرند (یا رد می‌کنند). با این الگوریتم جدید پیشنهادهای ازدواج و شکل‌گیری زوج‌ها به شکل زیر خواهند بود:
Proposals: {(w1 -> m1), (w2 -> m3), (w3 -> m1)}
Intermediate: {(m1, w1), (m3, w2), (m2), (w3)}
Proposals: {(w3 -> m3)}
Intermediate: {(m1, w1), (m3, w2) , (m2), (w3)}
Proposals: {(w3 -> m2)}
Final: {(m1, w1), (m3, w2) , (m2, w3)}
این بار هم به یک ترکیب پایدار رسیدیم که به هم نخواهد خورد، اما متفاوت از ترکیب قبلی است.
ترکیب زوج‌ها وقتی پسرها پیشنهاد ازدواج بدهند با ترکیب زوج‌ها وقتی دخترها پیشنهاد ازدواج بدهند، متفاوت هستند:
M = {(m1, w2), (m2, w3), (m3, w1)}
W = {(m1, w1), (m2, w3), (m3, w2)}
نکته‌ی جالب این‌جاست که تمام پسرها ترکیب اول را به ترکیب دوم ترجیح می‌دهند و تمام دخترها ترکیب دوم را به ترکیب اول ترجیح می‌دهند! به عبارت دیگر، وقتی پسرها پیشنهاد ازدواج می‌دهند، از نتیجه راضی‌تر هستند و وقتی دخترها پیشنهاد می‌دهند، از نتیجه‌ی روش راضی‌تر هستند!
نتیجه‌گیری: به نفع دخترهاست که به جای پسرها، آن‌ها پیشنهاد ازدواج بدهند.
کمی هم تحلیل: چرا با وجود منافعی که در پیش‌قدم شدن برای پیشنهاد دادن هست، تا به حال رسم بر این بوده که مردان پیشنهاد ازدواج می‌داده‌اند؟
– جواب اولیه (با برداشت از یکی از دانشجویان کلاس): شاید تا به الان قدرت و توانایی بیش‌تری در اختیار مردان بوده و در نتیجه از این برتری بهره‌مند می‌شده‌اند. اتفاقا الان که برابری بیش‌تری بین خانم‌ها و آقایان شکل گرفته، شاهد این هستیم که خانم‌های بیش‌تری به آقایان پیشنهاد ازدواج می‌دهند.
برای مطالعه‌ی بیش‌تر در این موضوع، در مورد Marriage Market و Stable Marriage Problem مطالعه کنید. این مطلب هم برداشتی بود از صحبت‌های «نیکول ایمورلیکا».
