موضوع مقاله: تقسیم بدون رشک کیک | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تقسیم بدون رشک کیک | مقدمه: در این نوع تقسیم معیار برای منصفانه بودن آن، عدم رشک‌ورزی هر عامل به دیگران است. | ## بخش 1: تقسیم بدون رشک کیک | تقسیم کیک زیرمجموعه‌ای از این دستهٔ مسائل است به‌طوری‌که منبع مشترک مورد بحث یک کیک (یا هر منبع پیوسته‌ای) است که ارزش قسمت‌های مختلف آن از دید افراد مختلف، متفاوت است. هر فرد می‌تواند تابع ارزش مختص به خود را برای قسمت‌های مختلف کیک داشته باشد و ما به دنبال این هستیم که با حداقل تعداد برش‌ها کیک را بین نفرات با روشی عادلانه تقسیم کنیم. برای این تقسیم‌بندی به دنبال یافتن الگوریتم یا پروتکلی هستیم که به ازای هر تعدادی از افراد و توابع ارزش‌های مختلف بتواند کیک را با شرایط مطلوب تقسیم نماید. یکی از این معیارها، بدون رشک بودن است که بیانگر بیشتر بودن ارزش سهم اختصاص داده شده به هر فرد نسبت به سایرین از دیدگاه خودش (برحسب تابع ارزش او) است و روشی که این معیار را مدنظر داشته باشد، تخصیصی را به ارمغان خواهد آورد که بدون رشک است. تاریخچه در سال 1995 Brams Stevenو Alan Taylor با ارائه روشی برای برش کیک بدون رشک به ازای هر تعداد عامل، تحولی ایجاد کردند که تضمین می‌کرد در زمان متناهی تقسیم‌بندی را انجام می‌دهد اما حتی برای مسئله‌ای با ۴ عامل تعداد برش‌ها می‌توانست نامحدود باشد از طرفی نیز زمان اجرای الگوریتم مذکور می‌توانست نامحدود باشد. در راستای مشکلات موجود در الگوریتم پیشنهاد شده Claudia Linder و Jörg Rothe بعدها در مقاله‌ای نوشتند:"توسعه پروتکل متناهی و محدود برای تقسیم کیک بدون رشک هم‌چنان دور از دسترس به نظر می‌رسد و چالشی بزرگ برای تحقیق‌های آتی است." هم‌چنان پاسخ بهینه‌ای برای این مسئله با مشخصات مطلوب پیدا نشده و مسئله بازمانده‌است. | ## بخش 2: تقسیم بدون رشک کیک | اخیراً روشی محدود و گسسته برای تقسیم بدون رشک کیک برای ۴ نفر توسط Aziz & Mackenzie ارائه شده‌است اما با وجود این پیشرفت‌ها مسئلهٔ کلی برای هر تعداد از نفرات، حل‌نشده باقی مانده‌است. الگوریتمی که بتواند راه‌حل مطلوبی برای این مسئله ارائه دهد می‌تواند برای حل مسائل واقعی مطرح در علوم کامپیوتر، اقتصاد، علوم سیاسی و علوم اجتماعی مورد استفاده قرار گیرد از این رو تقسیم کیک بدون رشک و انواع مختلف دیگر تقسیم کیک سال‌ها مورد توجه فراوان دانشمندان فعال در این علوم بوده و هستند. به عنوان مثال برای نشان دادن یک مورد از کاربرد این مسئله در مشکلات مرتبط با کامپیوتر و فناوری اطلاعات می‌توان مسئله زیر را مورد توجه قرار داد:یک شرکت محاسباتی برزگ ابر پردازشی خود را به n شرکت دیگر برون‌سپاری می‌کند. بنا به دلایل امنیتی ابر در آن واحد می‌تواند عملیات پردازشی مربوط به تنها یک شرکت را انجام دهد. هر شرکت برای استفاده از بازه زمانی ترجیحات مختص به خود را دارد و برخی زیر بازه‌ها را به برخی دیگر ترجیح می‌دهد. چگونه توان پردازشی ابر را در بازه‌های زمانی مختلف بین n شرکت تقسیم کنیم تا همگی راضی باشند؟اگر الگوریتمی که در پاسخ بدین مسئله ارائه می‌شود بدون رشک باشد، هر شرکت زمان اختصاص داده شده به خود را به زمان‌های مختصِ سایر شرکت‌ها ترجیح خواهد داد لکن از تخصیص صورت گرفته راضی خواهد بود. | ## بخش 3: تقسیم بدون رشک کیک | در این مسایل کیک استعاره‌ای از یک منبع ناهمگن بخش‌پذیر است و به صورت بازه‌ای از مدل می‌شود. برش کیک نمادی برای اجتماع زیر بازه‌هایی از می‌باشد که برقراری شرط پیوستگی برای آن‌ها الزامی نیست. هر شخص برای هر زیر میجموعه‌ای از تابع ارزش خود را دارد که باید دارای سه شرط زیر باشد: نامنفی باشد: جمع پذیر باشد: برای هر دو مجموعه جدا از هم داریم : قابل تقسیم باشد: برای هر و مجموعه وجود خواهد داشت که : اگر یک تقسیم بندی به نفر ام بازه را اختصاص دهد، برای بدون رشک بودن تقسیم‌بندی بایستی شرط زیر برقرار باشد: به عبارتی برقراری این شرط متضمن حسادت نکردن هر فرد به سهم دیگری و ترجیح دادن سهم خود بر سهم سایرین است. پیچیدگی محاسباتی در چندین دهه اخیر تلاش‌های فراوانی برای ارائه دادن الگوریتمی کلی با پیچیدگی زمانی پایین برای تقسیم بدون رشک کیک صورت گرفته‌است. حد پایینی که برای حل این مسئله در قرن بیست و یکم ارائه شده‌است از این قرار است: برای تخصیص قطعه دلخواه (لزومی برای پیوسته بودن قطعه تخصیص داده شده به هر فرد وجود ندارد)، حد پایین پیچیدگی زمانی است. برای تخصیص قطعات پیوسته حد پایین پیچیدگی محاسباتی بی‌نهایت و قابل اثبات است که هیچ پروتکل متناهی برای ۳ نفر و تعداد بیشتر وجود ندارد. | ## جمع‌بندی | پس از سال ۲۰۱۰ مقالات زیادی مرتبط با روش‌های تقریبی یا روش‌هایی برای مواردِ خاص از این مسئله ارائه شده‌است اما هم‌چنان روش محدودی که در زمان متناهی به پایان برسد برای حالت کلی این مسئله ارائه نشده بود تا این که در سال ۲۰۱۶ در مقالهٔ Aziz & Mackenzie روشی گسسته و کلی با پیچیدگی محاسباتی ارائه شد.