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 مطالعه کنید. این مطلب هم برداشتی بود از صحبت‌های «نیکول ایمورلیکا».

چهار نفر به نام‌های a و b و c و d قصد دارند هم‌اتاقی پیدا کنند. هر اتاق ظرفیت دو نفر دارد و در نتیجه دو نفر در یک اتاق خواهند بود و دو نفر در یک اتاق دیگر. سوال این است که به چه شکلی دو اتاق را به این چهار نفر اختصاص بدهیم. ترجیح‌های هرکدام از این چهار نفر به شکل زیر است (از چپ به راست):

p(a) = b, c, d
p(b) = c, a, d
p(c) = a, b, d
p(d) = arbitrary

یعنی اولین ترجیح a این است که با b هم‌اتاقی شود. اگر نشد با c بشود و اگر آن هم نشد، با d هم‌اتاقی بشود. برای b و c هم ترجیح‌ها به شکلی است که نوشته شده (از چپ به راست) و برای d هم فرقی نمی‌کند که چه ترجیحی داشته باشد (و در واقع برای این مساله هم فرقی نمی‌کند که d چه ترجیحی دارد).

برای مشخص‌کردن هم‌اتاقی‌ها، فرض کنید به عنوان اولین فرض، a و b با هم و c و d هم با هم هم‌اتاقی بشوند:

{a, b}
{c, d}

در این حالت مشکل پیدا می‌شود: b ترجیح می‌دهد به جای a با c هم اتاقی باشد (به لیست ترجیح‌ها نگاه کنید). همین‌طور c هم ترجیح می‌دهد به جای d با b هم اتاقی باشد. پس b و c با رضایت کامل تصمیم می‌گیرند هم‌اتاقی‌های‌شان را عوض کنند و با هم هم‌اتاقی بشوند. نتیجه این می‌شود:

{a, d}
{b, c}

اما مشکل هنوز حل نشده. با این ترتیب جدید، a ترجیح می‌دهد به جای هم اتاقی بودن با d، با c هم‌اتاقی باشد. اتفاقن c هم ترجیح می‌دهد هم‌اتاقی‌اش را عوض کند، چرا که برایش a ترجیح بیش‌تری دارد تا b. بعد از این تغییر داوطلبانه، هم‌اتاقی‌ها به این شکل در می‌آیند:

{a, c}
{b, d}

مشکل ادامه دارد. b هم اتاقی بودن با a را به وضعیت فعلی ترجیح می‌دهد و اتفاقن a هم ترجیح می‌دهد که هم‌اتاق b باشد. پس این دو هم با رضایت هم‌اتاقی‌ها را عوض می‌کنند و به ناچار c و d با هم هم‌اتاق می‌شوند. برگشتیم به خانه‌ی اول!

{a, b}
{c, d}

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