مسأله ی تقسیم عادلانه

مسأله ی تقسیم عادلانه معمولاً در مورد تقسیم یک کیک یا نوشابه بین n نفر مطرح می‌شود، با این شرط که هر یک از افراد قانع شود که حداقل از کیک یا نوشابه نصیب او می شود .

توجه کنید داور بی طرفی که بتواند کیک یا نوشابه را با توجه به وزن آن به طور مساوی تقسیم کند، وجود ندارد و تقسیم باید توسط خود n نفر که هر کدام سعی می‌کنند سهم بیش تری به دست آورند، انجام شود. در ضمن ممکن است ملاکی که هر کدام از افراد برای اندازه گرفتن کیک استفاده می‌کنند، متفاوت باشد. به طور مثال یک نفر بر اساس مقدار خامه و دیگری بر اساس مقدار مربای کیک ( که ممکن است به صورت متقارن هم پخش نشده باشند )، تصمیم می‌گیرد.

برای سه نفر این مسأله را می‌توان به شکل زیر حل کرد:

یکی از افراد یک چاقوی بزرگ را به آرامی روی کیک حرکت می دهد ( یا در مورد نوشابه، به آرامی نوشابه را در لیوان خالی می‌کند ). زمانی که یکی از سه نفر به این نتیجه رسیدند که مقدار کیک گذشته از زیر چاقو ( یا نوشابه داخل لیوان ) همان مقداری است که او را راضی می‌کند، دستش را بالا می‌برد و همان مقدار کیک یا نوشابه به او تعلق می‌گیرد، اگر دو یا سه نفر هم زمان دستان خود را بالا ببرند، مقدار مورد اشاره به صورت تصادفی به یکی از افراد تعلق می‌گیرد. واضح است که دو نفر باقی مانده معتقدند که حداقل 3/2 کیک باقی مانده است. بنابراین مسأله به حالت دو نفره تبدیل می‌شود و دو نفر باقی مانده می‌توانند از روش صفحه ی قبل استفاده کنند. ( یعنی یک نفر کیک را تقسیم می‌کند و نفر دیگر یکی از قطعات را انتخاب می‌کند )

به وضوح می‌توان همین روش را برای n نفر به کار گرفت. اولین کسی که دستش را بالا می‌برد، صاحب اولین قطعه است، دوباره همین روش را برای -n نفر باقی مانده تکرار می‌کنند و این کار را تا جایی ادامه می‌دهند که دو نفر باقی بمانند. حال این دو نفر می‌توانند باقی مانده ی کیک را با استفاده از همین روش یا روش صفحه ی قبل تقسیم کنند. کسانی که با استقرا آشنایی دارند، می دانند که این روش کلی، مثال خوبی از اثبات درستی یک الگوریتم به وسیله ی استقرا است.

آیا این راه حل به راه حلی که شما در نظر داشتید، شبیه است؟ اگر راه حل متفاوتی پیدا کرده اید یا توضیح خاصی در مورد این مسأله دارید، آن را برای ما میل بزنید.

حال علاوه بر شرایط قبلی، این شرط را در نظر بگیرید که هر یک از افراد بپذیرند که سهم هیچ یک از افراد بیش تر از او نبوده است، به عبارت دیگر هیچ کس حاضر نباشد سهم خود را با دیگری عوض کند. این شرط برای جلوگیری از تبانی تعدادی از افراد بر علیه تعدادی دیگر است. (چرا؟)

روش بالا فقط هنگامی که برای 2 نفر به کار گرفته شود، شرط عدم تبانی را برآورده می‌کند. اما وقتی برای بیش از 2 نفر به کار گرفته شود، این شرط را برآورده نمی کند. (چرا؟) سعی کنید با اصلاح این روش یا راه حلی که خود یافته اید، روشی به دست آورید که این شرط را برای سه نفر هم برآورده کند؛ و آن را برای ما ارسال نمایید.

این مسأله که اولین بار در سال 1940 مطرح شد، در هر جا که تقسیم منابع و تزاحم منافع وجود داشته باشد ( مثلاً در شبکه های کامپیوتری ) به کار می‌آید. روشی که در ابتدای متن پیشنهاد شد ( برای سه نفر )، در طول جنگ جهانی دوم به وسیله ی Steinhaus و برای n نفر، چند سال بعد توسط Banach ابداع شد. جالب است بدانید کسی که این مسأله را در کلی ترین شکل در سال 1995 حل کرد، Steven J. Brams استاد علوم سیاسی دانشگاه نیویرک بود. در صفحه ی بعد می‌توانید مطالبی در مورد این راه حل بیاموزید.