تقسیم بدون رشک کیک

تقسیم بدونِ رشک کیک (به انگلیسی:Envy-free cake cutting) نوعی مسئلهٔ تقسیم کیک منصفانه (به انگلیسی:fair cake-cutting) است که خود زیرمجموعه‌ای از مسائل تقسیم منصفانه (به انگلیسی:fair division) محسوب می‌شود. در این نوع تقسیم معیار برای منصفانه بودن آن، عدم رشک‌ورزی هر عامل به دیگران است. تقسیم منصفانه به دسته‌ای از مسائل اطلاق می‌شود که هدف آن‌ها تقسیم منصفانه منابع مشترک بین تعدای عامل است. تقسیم کیک زیرمجموعه‌ای از این دستهٔ مسائل است به‌طوری‌که منبع مشترک مورد بحث یک کیک (یا هر منبع پیوسته‌ای) است که ارزش قسمت‌های مختلف آن از دید افراد مختلف، متفاوت است. هر فرد می‌تواند تابع ارزش مختص به خود را برای قسمت‌های مختلف کیک داشته باشد و ما به دنبال این هستیم که با حداقل تعداد برش‌ها کیک را بین نفرات با روشی عادلانه تقسیم کنیم. برای این تقسیم‌بندی به دنبال یافتن الگوریتم یا پروتکلی هستیم که به ازای هر تعدادی از افراد و توابع ارزش‌های مختلف بتواند کیک را با شرایط مطلوب تقسیم نماید. ممکن است مطلوب بودن تقسیم‌بندی بر اساس معیارهای مختلف، مشخص شود. یکی از این معیارها، بدون رشک بودن است که بیانگر بیشتر بودن ارزش سهم اختصاص داده شده به هر فرد نسبت به سایرین از دیدگاه خودش (برحسب تابع ارزش او) است و روشی که این معیار را مدنظر داشته باشد، تخصیصی را به ارمغان خواهد آورد که بدون رشک است.

تاریخچه

در سال 1995 Brams  Stevenو Alan Taylor با ارائه روشی برای برش کیک بدون رشک به ازای هر تعداد عامل، تحولی ایجاد کردند که تضمین می‌کرد در زمان متناهی تقسیم‌بندی را انجام می‌دهد اما حتی برای مسئله‌ای با ۴ عامل تعداد برش‌ها می‌توانست نامحدود باشد از طرفی نیز زمان اجرای الگوریتم مذکور می‌توانست نامحدود باشد. در راستای مشکلات موجود در الگوریتم پیشنهاد شده Claudia Linder و Jörg Rothe بعدها در مقاله‌ای نوشتند:"توسعه پروتکل متناهی و محدود برای تقسیم کیک بدون رشک هم‌چنان دور از دسترس به نظر می‌رسد و چالشی بزرگ برای تحقیق‌های آتی است."
هم‌چنان پاسخ بهینه‌ای برای این مسئله با مشخصات مطلوب پیدا نشده و مسئله بازمانده‌است. مقالات زیادی نیز به بررسی آن پرداخته‌اند (من جمله: Edmonds & Pruhs) در مقاله‌ای دیگر Saberi & Wang اظهار داشته‌اند که این مسئله یکی از مهم‌ترین مسائل باز در زمینهٔ خود، یعنی تقسیم منصفانه، است. اخیراً روشی محدود و گسسته برای تقسیم بدون رشک کیک برای ۴ نفر توسط Aziz & Mackenzie ارائه شده‌است اما با وجود این پیشرفت‌ها مسئلهٔ کلی برای هر تعداد از نفرات، حل‌نشده باقی مانده‌است.

کاربرد

مسئله برش کیک اولین بار توسط Hugo Steinhaus، ریاضی‌دان لهستانی، در خلال جنگ جهانی دوم مطرح شد. الگوریتمی که بتواند راه‌حل مطلوبی برای این مسئله ارائه دهد می‌تواند برای حل مسائل واقعی مطرح در علوم کامپیوتر، اقتصاد، علوم سیاسی و علوم اجتماعی مورد استفاده قرار گیرد از این رو تقسیم کیک بدون رشک و انواع مختلف دیگر تقسیم کیک سال‌ها مورد توجه فراوان دانشمندان فعال در این علوم بوده و هستند. به عنوان مثال برای نشان دادن یک مورد از کاربرد این مسئله در مشکلات مرتبط با کامپیوتر و فناوری اطلاعات می‌توان مسئله زیر را مورد توجه قرار داد:
یک شرکت محاسباتی برزگ ابر پردازشی خود را به n شرکت دیگر برون‌سپاری می‌کند. بنا به دلایل امنیتی ابر در آن واحد می‌تواند عملیات پردازشی مربوط به تنها یک شرکت را انجام دهد. هر شرکت برای استفاده از بازه زمانی  ترجیحات مختص به خود را دارد و برخی زیر بازه‌ها را به برخی دیگر ترجیح می‌دهد. چگونه توان پردازشی ابر را در بازه‌های زمانی مختلف بین n شرکت تقسیم کنیم تا همگی راضی باشند؟
اگر الگوریتمی که در پاسخ بدین مسئله ارائه می‌شود بدون رشک باشد، هر شرکت زمان اختصاص داده شده به خود را به زمان‌های مختصِ سایر شرکت‌ها ترجیح خواهد داد لکن از تخصیص صورت گرفته راضی خواهد بود.