تقسیم بدون رشک کیک
تقسیم بدونِ رشک کیک (به انگلیسی:Envy-free cake cutting) نوعی مسئلهٔ تقسیم کیک منصفانه (به انگلیسی:) است که خود زیرمجموعه‌ای از مسائل تقسیم منصفانه (به انگلیسی:) محسوب می‌شود. در این نوع تقسیم معیار برای منصفانه بودن آن، عدم رشک‌ورزی هر عامل به دیگران است. تقسیم منصفانه به دسته‌ای از مسائل اطلاق می‌شود که هدف آن‌ها تقسیم منصفانه منابع مشترک بین تعدای عامل است. تقسیم کیک زیرمجموعه‌ای از این دستهٔ مسائل است به‌طوری‌که منبع مشترک مورد بحث یک کیک (یا هر منبع پیوسته‌ای) است که ارزش قسمت‌های مختلف آن از دید افراد مختلف، متفاوت است. هر فرد می‌تواند تابع ارزش مختص به خود را برای قسمت‌های مختلف کیک داشته باشد و ما به دنبال این هستیم که با حداقل تعداد برش‌ها کیک را بین نفرات با روشی عادلانه تقسیم کنیم. برای این تقسیم‌بندی به دنبال یافتن الگوریتم یا پروتکلی هستیم که به ازای هر تعدادی از افراد و توابع ارزش‌های مختلف بتواند کیک را با شرایط مطلوب تقسیم نماید. ممکن است مطلوب بودن تقسیم‌بندی بر اساس معیارهای مختلف، مشخص شود. یکی از این معیارها، بدون رشک بودن است که بیانگر بیشتر بودن ارزش سهم اختصاص داده شده به هر فرد نسبت به سایرین از دیدگاه خودش (برحسب تابع ارزش او) است و روشی که این معیار را مدنظر داشته باشد، تخصیصی را به ارمغان خواهد آورد که بدون رشک است.
در سال 1995 "Brams" " Steven"و "Alan Taylor" با ارائه روشی برای برش کیک بدون رشک به ازای هر تعداد عامل، تحولی ایجاد کردند که تضمین می‌کرد در زمان متناهی تقسیم‌بندی را انجام می‌دهد اما حتی برای مسئله‌ای با ۴ عامل تعداد برش‌ها می‌توانست نامحدود باشد از طرفی نیز زمان اجرای الگوریتم مذکور می‌توانست نامحدود باشد. در راستای مشکلات موجود در الگوریتم پیشنهاد شده "Claudia Linder" و Jörg "Rothe" بعدها در مقاله‌ای نوشتند:"توسعه پروتکل متناهی و محدود برای تقسیم کیک بدون رشک هم‌چنان دور از دسترس به نظر می‌رسد و چالشی بزرگ برای تحقیق‌های آتی است."
هم‌چنان پاسخ بهینه‌ای برای این مسئله با مشخصات مطلوب پیدا نشده و مسئله بازمانده‌است. مقالات زیادی نیز به بررسی آن پرداخته‌اند (من جمله: Edmonds & Pruhs) در مقاله‌ای دیگر Saberi & Wang اظهار داشته‌اند که این مسئله یکی از مهم‌ترین مسائل باز در زمینهٔ خود، یعنی تقسیم منصفانه، است. اخیراً روشی محدود و گسسته برای تقسیم بدون رشک کیک برای ۴ نفر توسط Aziz & Mackenzie ارائه شده‌است اما با وجود این پیشرفت‌ها مسئلهٔ کلی برای هر تعداد از نفرات، حل‌نشده باقی مانده‌است.
مسئله برش کیک اولین بار توسط ""، ریاضی‌دان لهستانی، در خلال جنگ جهانی دوم مطرح شد. الگوریتمی که بتواند راه‌حل مطلوبی برای این مسئله ارائه دهد می‌تواند برای حل مسائل واقعی مطرح در علوم کامپیوتر، اقتصاد، علوم سیاسی و علوم اجتماعی مورد استفاده قرار گیرد از این رو تقسیم کیک بدون رشک و انواع مختلف دیگر تقسیم کیک سال‌ها مورد توجه فراوان دانشمندان فعال در این علوم بوده و هستند. به عنوان مثال برای نشان دادن یک مورد از کاربرد این مسئله در مشکلات مرتبط با کامپیوتر و فناوری اطلاعات می‌توان مسئله زیر را مورد توجه قرار داد:یک شرکت محاسباتی برزگ ابر پردازشی خود را به n شرکت دیگر برون‌سپاری می‌کند. بنا به دلایل امنیتی ابر در آن واحد می‌تواند عملیات پردازشی مربوط به تنها یک شرکت را انجام دهد. هر شرکت برای استفاده از بازه زمانی formula_1 ترجیحات مختص به خود را دارد و برخی زیر بازه‌ها را به برخی دیگر ترجیح می‌دهد. چگونه توان پردازشی ابر را در بازه‌های زمانی مختلف بین n شرکت تقسیم کنیم تا همگی راضی باشند؟اگر الگوریتمی که در پاسخ بدین مسئله ارائه می‌شود بدون رشک باشد، هر شرکت زمان اختصاص داده شده به خود را به زمان‌های مختصِ سایر شرکت‌ها ترجیح خواهد داد لکن از تخصیص صورت گرفته راضی خواهد بود.
تقسیم کیک بدون رشک یکی از انواع دسته مسایل تقسیم منصفانه کیک است. در این مسایل کیک استعاره‌ای از یک منبع ناهمگن بخش‌پذیر است و به صورت بازه‌ای از formula_2 مدل می‌شود. برش کیک نمادی برای اجتماع زیر بازه‌هایی از formula_2 می‌باشد که برقراری شرط پیوستگی برای آن‌ها الزامی نیست. هر شخص برای هر زیر میجموعه‌ای از formula_2 تابع ارزش خود را دارد که باید دارای سه شرط زیر باشد: اگر یک تقسیم بندی به نفر formula_12ام بازه formula_13را اختصاص دهد، برای بدون رشک بودن تقسیم‌بندی بایستی شرط زیر برقرار باشد: formula_14 formula_15به عبارتی برقراری این شرط متضمن حسادت نکردن هر فرد به سهم دیگری و ترجیح دادن سهم خود بر سهم سایرین است.
در چندین دهه اخیر تلاش‌های فراوانی برای ارائه دادن الگوریتمی کلی با پیچیدگی زمانی پایین برای تقسیم بدون رشک کیک صورت گرفته‌است. حد پایینی که برای حل این مسئله در قرن بیست و یکم ارائه شده‌است از این قرار است: پس از سال ۲۰۱۰ مقالات زیادی مرتبط با روش‌های تقریبی یا روش‌هایی برای مواردِ خاص از این مسئله ارائه شده‌است اما هم‌چنان روش محدودی که در زمان متناهی به پایان برسد برای حالت کلی این مسئله ارائه نشده بود تا این که در سال ۲۰۱۶ در مقالهٔ Aziz & Mackenzie روشی گسسته و کلی با پیچیدگی محاسباتی formula_17 ارائه شد.