تقسیم منصفانه

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

تعریف

مجموعه‌ای به نام X و گروهی متشکل از n بازی‌کن وجود دارد. یک «تقسیم» افرازی از مجموعهٔ X به n زیرمجموعه است، به‌طوری‌که هر زیرمجموعه سهم یک بازی‌کن شود:
X= X₁

فرایندها

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

دو بازی‌کن

برای دو نفر راه حل ساده‌ای وجود دارد که معمولاً مورد استفاده قرار می‌گیرد. به این روش تقسیم کن و برگزین (divide and choose) نیز می‌گویند. یک نفر منبع را دو قسمتی که از نظر خودش دو نیمهٔ برابر هستند تقسیم می‌کند، و نفر دیگر نیمه‌ای را که ترجیح می‌دهد برمی‌گزیند. به همین سبب شخص تقسیم‌کننده انگیزهٔ زیادی برای تقسیم منصفانه دارد، چرا که اگر این‌چنین تقسیم نکند احتمالاً قسمت نامطلوبی نصیبش می‌گردد. این راه حل یک تقسیم بدون رشک را تضمین می‌نماید. اگر ارزش‌گذاری‌های بازی‌کنان sigma additive باشند، در آن صورت تقسیم بدون رشک، متناسب نیز خواهد بود. مقاله‌ای در مورد روش تقسیم کن و برگزین توضیح می‌دهد که چرا این روش equitable نیست.
فرآیندهای پیچیده‌تری همچون فرایند برندهٔ سازگار (adjusted winner procedure) برای کالاهای غیرقابل تقسیم طراحی شده و در موارد کاربردی equitableتر هستند.
فرایند چاقوی متحرک آستین (Austin’s moving knife procedure) تقسیمی دقیق را برای دو بازی‌کن را ارائه می‌دهد. اولین بازی‌کن چاقویی را از طرف چپ روی کیک حرکت داده و هر زمان هر کدام از بازی‌کنان بگوید «ایست»، قسمت سمت چپ چاقو را می‌گیرد. این فرایند یک تقسیم بدون رشک را موجب می‌شود.
فرایند مازاد (surplus procedure) به نوعی از equitability دست می‌یابد که آن را equitability نسبی می‌نامند. این فرایند strategy proof بوده و می‌توان آن را به بیش از دو بازی‌کن نیز تعمیم داد.

چندین بازی‌کن

تقسیم منصفانه برای سه بازی‌کن یا بیش‌تر بسیار پیچیده‌تر از دو بازی‌کن است.
تقسیم نسبی راحت‌ترین راه است و مقاله برخی از فرآیندهایی را که برای هرتعداد بازی‌کن قابل استفاده است را ارائه می‌دهد. یافتن تعداد کمینهٔ برش‌های مورد نیاز یک مسئلهٔ ریاضی جالب است.
تقسیم بدون رشک برای سه بازی‌کن برای بار اول در سال ۱۹۶۰ به‌طور جداگانه توسط جان سلفریج در دانشگاه ایلینوی شمالی و جان هورتون کانوی در دانشگاه کمبریج حل شد. بهترین الگوریتم (فرایند گسستهٔ سلفریج-کانوی) حداکثر پنج برش دارد.
در سال ۱۹۹۵ فرایند برامز-تیلور توسط استیون برامز و آلن تیلور منتشر شد. این فرایند اولین فرایند برش کیک برای چهار بازی‌کن یا بیش‌تر است که تقسیمی بدون رشک را برای هرتعداد بازی‌کن موجب می‌شود. تعداد برش‌های لازم برای این فرایند بدون محدودیت است. یک فرایند چاقوی متحرک با تعداد برش‌های محدود در سال ۱۹۹۷ برای چهار بازی‌کن یافت شد.
هیچ الگوریتم گسسته‌ای برای یک تقسیم دقیق حتی برای دو بازی‌کن وجود ندارد. یک فرایند چاقوی متحرک بهترین فرایند دست‌یافتنی‌ست. هیچ الگوریتم تقسیم دقیقی برای سه بازی‌کن و بیش‌تر وجود ندارد، اما الگوریتم‌های «تقریباً دقیق» که بدون رشک نیز باشند و بتوانند به هر درجهٔ دلخواه از دقت دست یابند، موجود است.
تعمیمی از فرایند مازاد به نام فرایند equitable به نوعی از equitability دست می‌یابد. Equitability و بی‌رشکی برای سه بازی‌کن و بیش‌تر با یکدیگر ناسازگارند.

مطلوبیت غیر افزایشی

اکثر فرآیندهای تقسیم منصفانه که پیش‌تر توضیح داده شد بر این فرض بنا شده‌اند که مطلوبیت بازی‌کنان افزایشی‌ست. به بیان دیگر، اگر بازی‌کنی یک مقدار مطلوبیت از ۲۵ گرم کیک شکلاتی به دست آرود، فرض می‌شود که او از ۵۰ گرم از همین کیک شکلاتی دقیقاً دو برابر این مقدار مطلوبیت را دریافت خواهد کرد.
در سال ۲۰۱۳، Rishi S. Mirchandani نشان داد که اکثر الگوریتم‌های تقسیم منصفانهٔ موجود با توابع مطلوبیت غیر افزایشی سازگاری ندارند. او همچنین ثابت کرد که مواردی از تقسیم منصفانه که در آن‌ها بازی‌کنان توابع مطلوبیت غیر افزایشی داشته‌اند ممکن است هیچ راه حل متناسبی نداشته باشند.
Mirchandani معتقد است که مسئلهٔ تقسیم منصفانه با بهره‌گیری از تکنیک‌های بهینه‌سازی غیرخطی قابل حل است. با این وجود، همچنان جای سؤال است که آیا الگوریتم‌های کاراتری برای زیرمجموعه‌های به‌خصوصی از توابع مطلوبیت غیر افزایشی وجود دارد یا خیر.

برش منصفانه کیک

برش منصفانه کیک یک مسئلهٔ تقسیم عادلانه است که منبع ناهمگنی دارد و قسمت‌های مخالف آن می‌تواند تا حدودی متفاوت باشند و همچنین بدیهی است که منبعی تفکیک‌پذیر می‌باشد زیرا با تکه کردن یک کیک ارزش آن تغییری نمی‌کند. منبع باید میان چند نفر که سلایق مختلفی در مورد قسمت‌های مختلف کیک دارند تقسیم شود، به عنوان مثال، برخی از مردم قسمت‌های پر شکلات کیک را ترجیح می‌دهند، برخی گیلاس را ترجیح می‌دهند، برخی نیز فقط ترجیح می‌دهند بزرگترین قطعه کیک نسیب آن‌ها شود. تقسیم باید به‌طور ذهنی عادلانه باشد، بدین صورت که هر فرد باید قطعه کیکی را دریافت کند که از نظرش سهمی عادلانه است.
«کیک» تنها یک استعاره است. روش برش عادلانه کیک را می‌توان برای تقسیم انواع منابع، مانند املاک زمین، فضای تبلیغاتی و … استفاده کرد.
مسئله برش منصفانه کیک توسط Hugo Steinhaus پس از جنگ جهانی دوم معرفی شد و هنوز هم موضوع تحقیقات زیادی در ریاضیات، علوم کامپیوتر، اقتصاد و علوم سیاسی است.

تاریخچه

به گفتهٔ سول گارفانکل (Sol Garfunkel) مسئلهٔ برش کیک از مهم‌ترین مسائل حل‌نشدهٔ ریاضی در قرن بیستم میلادی بوده که مهم‌ترین نوع آن در سال ۱۹۹۵ به وسیلهٔ فرایند برامز-تیلور توسط استیون برامز و آلن تیلور حل شد.
ریشه‌های روش تقسیم کن و برگزین ثبت نشده‌اند. فعالیت‌های مرتبط مذاکره و تهاتر نیز بسیار قدیمی هستند. مذاکراتی که بیش از دو نفر را شامل شوند نیز متداول هستند، نمونهٔ اخیری از این موضوع کنفرانس پاتسدم (Potsdam Conference) می‌باشد.
تئوری تقسیم منصفانه تنها از سال‌های پایانی جنگ جهانی دوم شکل گرفت. گروهی از ریاضی‌دانان لهستانی به نام‌های هوگو استاینهاوس (Hugo Steinhaus), برانیسلاو کناستر (Bronislow Knaster)، و استفان باناخ (Stefan Banach) آن را پایه‌گذاری نمودند. یک تقسیم (منصفانه) نسبی برای هر تعداد بازی‌کن به نام last-diminisher در سال ۱۹۴۴ کشف شد. این روش توسط استاینهاوس به باناخ و کناستر نسبت داده شد هنگامی که در سال ۱۹۴۷ در جلسهٔ econometric society در واشینگتن دی. سی. برای نخستین بار از این مسئله پرده برداشت. در این جلسه او همچنین مسئلهٔ یافتن کم‌ترین تعداد برش برای رسیدن به چنین تقسیمی را نیز مطرح نمود.
تقسیم بدون رشک برای اولین بار برای سه بازی‌کن در سال ۱۹۶۰ به‌طور جداگانه توسط جان سلفریج از دانشگاه ایلینوی شمالی و جان هورتون کانوی از دانشگاه کمبریج حل شده و در ستون «بازی‌های ریاضیاتی» توسط مارتین گاردنر در نشریهٔ Scientific American چاپ شد.
تقسیم بدون رشک برای چهار بازی‌کن یا بیش‌تر مسئلهٔ باز دشواری در قرن بیستم میلادی بود. نخستین فرایند برش کیکی که برای هر تعداد بازی‌کن یک تقسیم بدون رشک ارائه داد برای اولین بار در سال ۱۹۹۵ توسط استیون برامز و آلن تیلور منتشر گردید.
در سال ۲۰۶۶ میلادی پیشرفت چشمگیری در زمینهٔ تقسیم equitable توسط استیون ج. برامز، مایکل اِی. جونز و کریستیان کلاملر صورت گرفت.