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

تقسیم بدونِ رشک کیک (به انگلیسی: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 شرکت دیگر برون‌سپاری می‌کند. بنا به دلایل امنیتی ابر در آن واحد می‌تواند عملیات پردازشی مربوط به تنها یک شرکت را انجام دهد. هر شرکت برای استفاده از بازه زمانی $[T,T']$ ترجیحات مختص به خود را دارد و برخی زیر بازه‌ها را به برخی دیگر ترجیح می‌دهد. چگونه توان پردازشی ابر را در بازه‌های زمانی مختلف بین n شرکت تقسیم کنیم تا همگی راضی باشند؟

اگر الگوریتمی که در پاسخ بدین مسئله ارائه می‌شود بدون رشک باشد، هر شرکت زمان اختصاص داده شده به خود را به زمان‌های مختصِ سایر شرکت‌ها ترجیح خواهد داد لکن از تخصیص صورت گرفته راضی خواهد بود.

مدل‌سازی

تقسیم کیک بدون رشک یکی از انواع دسته مسایل تقسیم منصفانه کیک است. در این مسایل کیک استعاره‌ای از یک منبع ناهمگن بخش‌پذیر است و به صورت بازه‌ای از $[0,1]$ مدل می‌شود. برش کیک نمادی برای اجتماع زیر بازه‌هایی از $[0,1]$ می‌باشد که برقراری شرط پیوستگی برای آن‌ها الزامی نیست. هر شخص برای هر زیر میجموعه‌ای از $[0,1]$ تابع ارزش خود را دارد که باید دارای سه شرط زیر باشد:

• نامنفی باشد: $V_{i}(X)\geqslant 0$
• جمع پذیر باشد: برای هر دو مجموعه جدا از هم $X,{X}'$ داریم : $V_{i}(X\cup {X}')=V_{i}(X)+V_{i}({X}')$
• قابل تقسیم باشد: برای هر $X\subseteq [0,1]$و $0\leqslant \lambda \leqslant 1$مجموعه ${X}'\subset X$وجود خواهد داشت که : $V_{i}({X}')=\lambda V_{i}(X)$

اگر یک تقسیم بندی به نفر $i$ام بازه $S_{i}$را اختصاص دهد، برای بدون رشک بودن تقسیم‌بندی بایستی شرط زیر برقرار باشد: $i,j\in \{1,2,...,n\}$ $\forall _{i,j}V_{i}(S_{i})\geqslant V_{j}(S_{j})$به عبارتی برقراری این شرط متضمن حسادت نکردن هر فرد به سهم دیگری و ترجیح دادن سهم خود بر سهم سایرین است.

پیچیدگی محاسباتی

در چندین دهه اخیر تلاش‌های فراوانی برای ارائه دادن الگوریتمی کلی با پیچیدگی زمانی پایین برای تقسیم بدون رشک کیک صورت گرفته‌است. حد پایینی که برای حل این مسئله در قرن بیست و یکم ارائه شده‌است از این قرار است:

• برای تخصیص قطعه دلخواه (لزومی برای پیوسته بودن قطعه تخصیص داده شده به هر فرد وجود ندارد)، حد پایین پیچیدگی زمانی $\Omega (n^{2})$ است.
• برای تخصیص قطعات پیوسته حد پایین پیچیدگی محاسباتی بی‌نهایت و قابل اثبات است که هیچ پروتکل متناهی برای ۳ نفر و تعداد بیشتر وجود ندارد.

پس از سال ۲۰۱۰ مقالات زیادی مرتبط با روش‌های تقریبی یا روش‌هایی برای مواردِ خاص از این مسئله ارائه شده‌است اما هم‌چنان روش محدودی که در زمان متناهی به پایان برسد برای حالت کلی این مسئله ارائه نشده بود تا این که در سال ۲۰۱۶ در مقالهٔ Aziz & Mackenzie روشی گسسته و کلی با پیچیدگی محاسباتی $n^{n^{n^{n^{n^{n}}}}}$ ارائه شد.