تقسیم منصفانه
تقسیم منصفانه مسئلهٔ تقسیم مجموعه‌ای از کالاها یا منابع مابین تعدادی افراد است که نسبت به آن‌ها حقی دارند، به‌طوری‌که هر نفر سهم مقتضی خود را دریافت نمایند. این مسئله در موقعیت‌های واقعی متفاوتی مطرح می‌گردد، از جمله حراجی‌ها، توافقات طلاق، تخصیص دامنهٔ الکتریکی و فرکانس، مدیریت ترافیک فرودگاه، یا بهره‌برداری از ماهواره‌های رصد کرهٔ زمین. این مبحث یک تحقیقات در حال انجام در ریاضیات، اقتصاد (به ویژه تئوری انتخاب اجتماعی)، تئوری بازی، حل و فصل مشاجرات و بسیاری مباحث دیگر می‌باشد. هستهٔ مرکزی تئوری تقسیم منصفانه این است که چنین تقسیمی باید به وسیلهٔ خود بازی‌کنان صورت گیرد. ممکن است در این تقسیم از یک واسطه کمک گرفته شود، اما هرگز نباید برای این کار یک داور داشت، چرا که تنها خود بازی‌کنان از ارزش واقعی کالاها باخبرند.
انواع مختلفی از مسائل تقسیم منصفانه بسته به طبیعت کالاهای مورد بحث، معیارهای عدالت، طبیعت بازی‌کنان و ترجیحات آن‌ها، و معیارهای دیگری برای ارزیابی کیفیت تقسیم، مطرح می‌شود.
مسئلهٔ ریاضی تقسیم منصفانه یک تطابق از این مسائل زندگی واقعی‌ست. تئوری تقسیم منصفانه معیارهای صریح و روشنی را برای انواع مختلف عدالت ارائه می‌دهد. هدف این تئوری فراهم نمودن فرآیندهایی (الگوریتم‌هایی) برای دستیابی به یک تقسیم منصفانه، یا اثبات امکان‌ناپذیری آن، و مطالعهٔ ویژگی‌های چنین تقسیماتی هم در تئوری و هم در واقعیت می‌باشد.
مجموعه‌ای به نام X و گروهی متشکل از n بازی‌کن وجود دارد. یک «تقسیم» افرازی از مجموعهٔ X به n زیرمجموعه است، به‌طوری‌که هر زیرمجموعه سهم یک بازی‌کن شود:
"X= X"
مجموعهٔ X می‌تواند از چندین جنس باشد: علاوه بر این، مجموعهٔ مورد نظر می‌تواند: در نهایت، متداول است که فرض شود که اقلام مورد تقسیم: مسئلهٔ تقسیم مجموعه‌ای از اقلام غیرقابل تقسیم و ناهمگون را واگذاری منصفانهٔ اقلام می‌نامند.
مسئلهٔ تقسیم مجموعه‌ای از اقلام قابل تقسیم و همگون را تخصیص منصفانهٔ منابع می‌نامند. یک مورد به خصوص تقسیم منصفانهٔ یک منبع همگون می‌باشد.
مسئلهٔ تقسیم یک منبع قابل تقسیم، ناهمگون و مطلوب را تقسیم کیک منصفانه نیز می‌نامند.
مسئلهٔ تقسیم مجموعه‌ای از اقلام ناهمگون و نامطلوب را تقسیم منصفانهٔ کارهای روزمره (در صورت قابل تقسیم بودن وظایف) و یا واگذاری کارهای روزمره (در صورت غیرقابل تقسیم بودن وظایف) می‌نامند.
ترکیب این حالات نیز امکان‌پذیر است، برای مثال:
اکثر آنچه معمولاً منصفانه تلقی می‌شود از لحاظ تئوری به دلیل استفاده از حاکم و داور این چنین نیست. این نوع موقعیت غالباً هنگامی رخ می‌دهد که تئوری‌های ریاضی از روی موقعیت‌های زندگی واقعی نام‌گذاری می‌شوند. تصمیمات درون تلمود در زمینهٔ حق مالکیت زمانی که یک ملک ورشکسته است نظرات پیچیده‌ای در مورد انصاف را بازتاب می‌نماید، و اکثر مردم نیز آن‌ها را منصفانه تلقی می‌کنند. با این حال، این مسائل بیش‌تر حاصل مناظرات قانونی مابین خاخامها هستند تا اختلافات مدعیان بر سر ارزش‌گذاری.
بر اساس تئوری ذهنی ارزش نمی‌توان برای ارزش هر قلم معیار عینی داشت. از همین رو انصاف عینی ممکن نیست، چرا که افراد مختلف ممکن است ارزش‌گذاری‌های متفاوتی برای هر قلم داشته باشند. آزمایش‌های تجربی در زمینهٔ تعریف مردم از انصاف به نتایج غیر قاطعی ختم می‌شود.
به همین سبب، بیش‌تر تحقیقات فعلی در مورد انصاف بر مفاهیم انصاف ذهنی تکیه دارند. فرض می‌شود که هر کدام از n نفر یک تابع مطلوبیت یا تابع ارزش شخصی و ذهنی دارند، V، که به هر زیرمجموعه از X یک ارزش عددی اختصاص می‌دهد. معمولاً این توابع نرمال شده به‌طوری‌که هر نفر به مجموعهٔ تهی ارزش صفر ("V(Ø)=۰")، و به کل مجموعهٔ اقلام ارزش یک ("V(X)=۱")، اگر تمام اقلام مطلوب بوده و ارزش ۱- اگر تمامی اقلام نامطلوب باشند، را اختصاص دهد. به عنوان نمونه: بر اساس این توابع ارزش ذهنی تعدادی معیار مورد استفاده برای یک تقسیم منصفانه وجود دارد. برخی از این معیارها با هم تناقض دارند اما اکثراً می‌توان آن‌ها را با یکدیگر ترکیب نمود. معیارهایی که در اینجا توضیح داده می‌شوند تنها برای زمانی قابل استفاده‌اند که هر فرد به مقدار مساوی حق داشته باشد: برای هر i
"V(X) ≥ 1/n" به ازای هر i و j
"(V(X) >= V(X" "(V(X) = V(X"  "(V(X) = V(X"
زمانی که دریافت‌کنندگان معیارهای متفاوتی برای ارزش‌گذاری بخش‌های منبع داشته باشند، این امکان وجود دارد که به یک تقسیم «فوق منصفانه» (super fair) (تقسیمی که در آن هر نفر بیش از سهم مقتضی خود را دریافت می‌نماید) دست یابیم. برای مثال، در مسئلهٔ بریدن کیک، ممکن است کسی بیش‌تر به مارزیپان علاقه داشته باشد، کسی به گیلاس، و به همین ترتیب. در این صورت، و تنها در این صورت، امکان دارد هر کدام از n دریافت‌کننده حتی بیش از آنچه از نظرشان بر اساس ارزش‌گذاری شخصی‌شان 1/n ارزش کل کیک باشد را دریافت نمایند. از سوی دیگر، حضور معیارهای متفاوت پتانسیل زیادی را برای طرح سؤالات چالش‌برانگیز و مطالعات گسترده‌تر فراهم می‌آورد.
علاوه بر انصاف، بعضاً مطلوب است که تقسیم بهینهٔ پرتو باشد، بدان معنا که هیچ تخصیص دیگری وجود نداشته باشد که، بدون نامطلوب‌تر کردن سهم یک نفر، سهم فردی را مطلوب‌تر کند. مفهوم کارایی از ایدهٔ بازار کارا در اقتصاد می‌آید.
معیارها و ضوابط یک تقسیم منصفانه بر اساس ارزش‌گذاری هر بازی‌کن، میزان حق مالکیت او، و نتیجهٔ یک فرایند تقسیم منصفانه تعیین می‌گردند. توجه کنید که ارزش‌گذاری سایر بازی‌کنان در این معیارها نقشی ندارند. حق مالکیت‌های متفاوت را می‌توان با استفاده از تعداد بازی‌کنان نمایندهٔ متفاوت برای هر بازی‌کن نشان داد، اما بعضاً ضوابط چیز دیگری را مشخص می‌نمایند.
بعضی اوقات در دنیای واقعی بازی‌کنان دید دقیقی از ارزش‌گذاری سایر بازی‌کنان دارند و بسیار به آن اهمیت می‌دهند. در صورت وجود دانش مطلق مسئله را می‌توان با کمک نظریهٔ الگوریتمی بازی‌ها مدل کرد. مدل کردن دانش نسبی بسیار دشوار است.
یک فرایند تقسیم منصفانه متشکل از فعالیت‌هایی‌ست که بازی‌کنان می‌بایست بر اساس دادهٔ مشهود و ارزش‌گذاری‌های خود انجام دهند. یک فرایند معتبر فرآیندی‌ست که یک تقسیم منصفانه برای هر کسی که بر اساس ارزش‌گذاری خود منطقی عمل کند را تضمین کند. زمانی که یک عمل به ارزش‌گذاری یک بازی‌کن وابسته باشد، فرایند استراتژی را ارائه می‌دهد که یک بازی‌کن منطقی پیش می‌گیرد. یک بازی‌کن ممکن است طوری رفتار کند که انگار یک قطعه ارزشی دیگر دارد، اما باید ثابت قدم باشد. به عنوان نمونه، اگر فرآیندی می‌گوید که بازی‌کن اول کیک را به دو قسمت تقسیم کرده و بازی‌کن دوم یک قسمت را برگزیند، بازی‌کن اول نمی‌تواند ادعا کند که قسمت بازی‌کن دوم بزرگ‌تر است.
بازی‌کنان باید:
· بر سر معیارها و ضوابط یک تقسیم منصفانه توافق کنند.
· یک فرایند معتبر را برگزیده و قوانین آن را پی بگیرند.
فرض می‌شود که هدف هر بازی‌کن بیشینه کردن مقدار کمینه‌ای‌ست که ممکن است به دست آورند ).
فرایندها را می‌توان به دو دستهٔ متناهی و پیوسته تقسیم نمود. در یک فرایند متناهی برای مثال در هر زمان تنها یک نفر کیک را بریده یا علامت‌گذاری می‌کند. در فرآیندهای پیوسته برای مثال یک بازی‌کن چاقو را روی کیک حرکت داده و بازی‌کن دیگر به او می‌گوید که کجا بایستد. در نوع دیگری از فرایند پیوسته یک نفر به هر قسمت کیک ارزشی را اختصاص می‌دهد.
برای دو نفر راه حل ساده‌ای وجود دارد که معمولاً مورد استفاده قرار می‌گیرد. به این روش تقسیم کن و برگزین () نیز می‌گویند. یک نفر منبع را دو قسمتی که از نظر خودش دو نیمهٔ برابر هستند تقسیم می‌کند، و نفر دیگر نیمه‌ای را که ترجیح می‌دهد برمی‌گزیند. به همین سبب شخص تقسیم‌کننده انگیزهٔ زیادی برای تقسیم منصفانه دارد، چرا که اگر این‌چنین تقسیم نکند احتمالاً قسمت نامطلوبی نصیبش می‌گردد. این راه حل یک تقسیم بدون رشک را تضمین می‌نماید. اگر ارزش‌گذاری‌های بازی‌کنان 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 معتقد است که مسئلهٔ تقسیم منصفانه با بهره‌گیری از تکنیک‌های بهینه‌سازی غیرخطی قابل حل است. با این وجود، همچنان جای سؤال است که آیا الگوریتم‌های کاراتری برای زیرمجموعه‌های به‌خصوصی از توابع مطلوبیت غیر افزایشی وجود دارد یا خیر.
برخی از فرآیندهای برش کیک گسسته‌اند، که در آن‌ها بازی‌کنان به وسیلهٔ یک چاقو کیک را برش می‌زنند (معمولاً طی گام‌های متوالی). از سوی دیگر، فرآیندهای چاقوی متحرک امکان حرکت پیوسته را فراهم کرده و بازی‌کنان می‌توانند در هر نقطه‌ای از کیک فرمان «ایست» بدهند.
نوع دیگری از مسئلهٔ تقسیم منصفانه، تقسیم کارهای روزمره است؛ این مسئله دوگان مسئلهٔ برش کیک است که در آن یک وظیفهٔ غیرمطلوب باید مابین بازی‌کنان تقسیم گردد. مثال کانونی برای این مسئله دسته‌ای از کارهای روزمرهٔ خانه می‌باشد که بازی‌کنان باید انجام دهند. دقت کنید که روش تقسیم کن و برگزین برای تقسیم کار نیز قابل استفاده می‌باشد.
یک تئوری پایه‌ای برای مسائل چند بازی‌کنی، تئوری توازن اجاره (Rental Harmony Theorem) بوده که توسط فرانسیس سو ارائه گشته‌است. خانه‌ای را در نظر بگیرید که به تعداد هم‌خانه‌ها اتاق داشته و باید تصمیم گرفته شود چه اتاقی به چه کسی تعلق گرفته و در نتیجه چه سهمی از اجارهٔ کل را باید بپردازد. همچنین تصور کنید که شرایط زیر برقرار باشد: با توجه به این موارد، تقسیمی از اجاره وجود دارد که به واسطهٔ آن هر نفر یک اتاق متفاوت را ترجیح بدهد. کاربرد جالبی از این تئوری در تئوری تجارت بین‌الملل مشهود است.
با استفاده از (Sperner’s Lemma) می‌توان با تقریب مطلوبی به راه حل بدون رشک برای مسائل چند بازی‌کنی دست یافت. این الگوریتم راهی سریع و کاربردی برای حل برخی مسائل تقسیم منصفانه ارائه می‌دهد.
تقسیم ملک و املاک، همان‌طور که برای مثال به هنگام طلاق یا تقسیم ارثیه رخ می‌دهد، معمولاً شامل اقلام غیرقابل تقسیم شده که باید به‌طور منصفانه مابین بازی‌کنان تقسیم گردند. این تقسیم ممکن است با تعدیل نقدی صورت گیرد (چنین بخش‌هایی «اتم» خوانده می‌شوند).
یک الزام معمول برای تقسیم زمین این است که قطعات به هم متصل باشند. برای مثال، تقسیم برلین پس از جنگ جهانی دوم این شهر را به چهار قسمت متصل تقسیم کرد.
یک تقسیم با وفاق عام تقسیمی‌ست که در آن افراد متعددی بر برابر بودن دو نیمه از یک منبع توافق دارند؛ این مسئله در مبحث تقسیم دقیق بررسی می‌گردد.
مسئلهٔ خاص تقسیم منصفانه برای آب‌های روان در یک رودخانهٔ بین‌المللی در مبحث با جزئیات توصیف شده‌است.
برش منصفانه کیک یک مسئلهٔ تقسیم عادلانه است که منبع ناهمگنی دارد و قسمت‌های مخالف آن می‌تواند تا حدودی متفاوت باشند و همچنین بدیهی است که منبعی تفکیک‌پذیر می‌باشد زیرا با تکه کردن یک کیک ارزش آن تغییری نمی‌کند. منبع باید میان چند نفر که سلایق مختلفی در مورد قسمت‌های مختلف کیک دارند تقسیم شود، به عنوان مثال، برخی از مردم قسمت‌های پر شکلات کیک را ترجیح می‌دهند، برخی گیلاس را ترجیح می‌دهند، برخی نیز فقط ترجیح می‌دهند بزرگترین قطعه کیک نسیب آن‌ها شود. تقسیم باید به‌طور ذهنی عادلانه باشد، بدین صورت که هر فرد باید قطعه کیکی را دریافت کند که از نظرش سهمی عادلانه است.
«کیک» تنها یک استعاره است. روش برش عادلانه کیک را می‌توان برای تقسیم انواع منابع، مانند املاک زمین، فضای تبلیغاتی و … استفاده کرد.
مسئله برش منصفانه کیک توسط Hugo Steinhaus پس از جنگ جهانی دوم معرفی شد و هنوز هم موضوع تحقیقات زیادی در ریاضیات، علوم کامپیوتر، اقتصاد و علوم سیاسی است.
به گفتهٔ سول گارفانکل (Sol Garfunkel) مسئلهٔ برش کیک از مهم‌ترین مسائل حل‌نشدهٔ ریاضی در قرن بیستم میلادی بوده که مهم‌ترین نوع آن در سال ۱۹۹۵ به وسیلهٔ فرایند توسط و حل شد.
ریشه‌های روش تقسیم کن و برگزین ثبت نشده‌اند. فعالیت‌های مرتبط مذاکره و تهاتر نیز بسیار قدیمی هستند. مذاکراتی که بیش از دو نفر را شامل شوند نیز متداول هستند، نمونهٔ اخیری از این موضوع (Potsdam Conference) می‌باشد.
تئوری تقسیم منصفانه تنها از سال‌های پایانی جنگ جهانی دوم شکل گرفت. گروهی از ریاضی‌دانان لهستانی به نام‌های (Hugo Steinhaus), (Bronislow Knaster)، و استفان باناخ (Stefan Banach) آن را پایه‌گذاری نمودند. یک تقسیم (منصفانه) نسبی برای هر تعداد بازی‌کن به نام last-diminisher در سال ۱۹۴۴ کشف شد. این روش توسط استاینهاوس به باناخ و کناستر نسبت داده شد هنگامی که در سال ۱۹۴۷ در جلسهٔ econometric society در واشینگتن دی. سی. برای نخستین بار از این مسئله پرده برداشت. در این جلسه او همچنین مسئلهٔ یافتن کم‌ترین تعداد برش برای رسیدن به چنین تقسیمی را نیز مطرح نمود.
تقسیم بدون رشک برای اولین بار برای سه بازی‌کن در سال ۱۹۶۰ به‌طور جداگانه توسط از دانشگاه ایلینوی شمالی و جان هورتون کانوی از دانشگاه کمبریج حل شده و در ستون «بازی‌های ریاضیاتی» توسط مارتین گاردنر در نشریهٔ چاپ شد.
تقسیم بدون رشک برای چهار بازی‌کن یا بیش‌تر مسئلهٔ باز دشواری در قرن بیستم میلادی بود. نخستین فرایند برش کیکی که برای هر تعداد بازی‌کن یک تقسیم بدون رشک ارائه داد برای اولین بار در سال ۱۹۹۵ توسط استیون برامز و آلن تیلور منتشر گردید.
در سال ۲۰۶۶ میلادی پیشرفت چشمگیری در زمینهٔ تقسیم equitable توسط استیون ج. برامز، مایکل اِی. جونز و کریستیان کلاملر صورت گرفت.