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

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

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

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

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

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

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

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

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

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