چهار نفر به نام‌های 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) و اهمیت این که پیشنهاد ازدواج از طرف خانم‌ها باشد یا آقایان می‌نویسم. این مطالب برگرفته از یک سخن‌رانی از «نیکول ایمورلیکا» بود.