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

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

انواع مختلفی از مسائل تقسیم منصفانه بسته به طبیعت کالاهای مورد بحث، معیارهای عدالت، طبیعت بازی‌کنان و ترجیحات آن‌ها، و معیارهای دیگری برای ارزیابی کیفیت تقسیم، مطرح می‌شود.

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

تعریف

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

X= X₁

چه چیزی تقسیم می‌شود؟

مجموعهٔ X می‌تواند از چندین جنس باشد:

X می‌تواند مجموعه‌ای متناهی از اقلام غیرقابل تقسیم باشد، برای مثال:X= {پیانو، ماشین، آپارتمان}، به‌طوری‌که هر قلم باید به‌طور کامل به یک نفر تخصیص داده شود.
X می‌تواند مجموعه‌ای نامتناهی از یک منبع قابل تقسیم باشد، برای نمونه: پول، یا یک کیک. از لحاظ ریاضیاتی یک منبع قابل تقسیم به صورت زیرمجموعه‌ای از فضای حقیقی مدل می‌شود؛ برای مثال بازهٔ]۰٬۱[ می‌تواند نمایانگر یک کیک باریک و طویل بوده که می‌بایست به بخش‌های موازی تقسیم گردد. دایرهٔ واحد می‌تواند نمایانگر یک پای سیب باشد.

علاوه بر این، مجموعهٔ مورد نظر می‌تواند:

همگون باشد – مانند پول، که مقدارش مهم است - یا
ناهمگون باشد – مانند یک کیک که ممکن است محتویات متفاوتی داشته باشد.

در نهایت، متداول است که فرض شود که اقلام مورد تقسیم:

مطلوب هستند، مانند ماشین یا کیک، و یا
نامطلوب هستند، مانند وظایف خانه.

مسئلهٔ تقسیم مجموعه‌ای از اقلام غیرقابل تقسیم و ناهمگون را واگذاری منصفانهٔ اقلام می‌نامند.

مسئلهٔ تقسیم مجموعه‌ای از اقلام قابل تقسیم و همگون را تخصیص منصفانهٔ منابع می‌نامند. یک مورد به خصوص تقسیم منصفانهٔ یک منبع همگون می‌باشد.

مسئلهٔ تقسیم یک منبع قابل تقسیم، ناهمگون و مطلوب را تقسیم کیک منصفانه نیز می‌نامند.

مسئلهٔ تقسیم مجموعه‌ای از اقلام ناهمگون و نامطلوب را تقسیم منصفانهٔ کارهای روزمره (در صورت قابل تقسیم بودن وظایف) و یا واگذاری کارهای روزمره (در صورت غیرقابل تقسیم بودن وظایف) می‌نامند.

ترکیب این حالات نیز امکان‌پذیر است، برای مثال:

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

منصفانه به چه معنی‌ست؟

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

بر اساس تئوری ذهنی ارزش نمی‌توان برای ارزش هر قلم معیار عینی داشت. از همین رو انصاف عینی ممکن نیست، چرا که افراد مختلف ممکن است ارزش‌گذاری‌های متفاوتی برای هر قلم داشته باشند. آزمایش‌های تجربی در زمینهٔ تعریف مردم از انصاف به نتایج غیر قاطعی ختم می‌شود.

به همین سبب، بیش‌تر تحقیقات فعلی در مورد انصاف بر مفاهیم انصاف ذهنی تکیه دارند. فرض می‌شود که هر کدام از n نفر یک تابع مطلوبیت یا تابع ارزش شخصی و ذهنی دارند، V_i، که به هر زیرمجموعه از X یک ارزش عددی اختصاص می‌دهد. معمولاً این توابع نرمال شده به‌طوری‌که هر نفر به مجموعهٔ تهی ارزش صفر (V_i(Ø)=۰)، و به کل مجموعهٔ اقلام ارزش یک (V_i(X)=۱)، اگر تمام اقلام مطلوب بوده و ارزش ۱- اگر تمامی اقلام نامطلوب باشند، را اختصاص دهد. به عنوان نمونه:

اگر X مجموعه‌ای از اقلام غیرقابل تقسیم {پیانو، ماشین، آپارتمان} باشد، «آلیس» ممکن است به هر کدام ارزش ۳/۱ را بدهد، بدین معنا که هر قلم دقیقاً به اندازهٔ هر کدام از اقلام دیگر برای او ارزش دارد و مهم است. «باب» ممکن است تنها به زیرمجموعهٔ {ماشین، آپارتمان} ارزش یک را اختصاص بدهد، بدین معنا او می‌خواهد ماشین و آپارتمان را با هم به دست آورد، ماشین به تنهایی یا آپارتمان به تنهایی، یا هر کدام آن‌ها به همراه پیانو، برایش ارزشی ندارد.
اگر X یک کیک باریک دراز باشد (که بر بازهٔ [۰٬۱] مدل می‌شود)، ممکن است «آلیس» به هر زیرمجموعه متناسب با طولش ارزش دهد، که بدان معنی‌ست که او می‌خواهد کیک بیش‌تری نصیبش شود، بدون توجه به محتویات. «باب» ممکن است تنها به زیرمجموعه‌های بازهٔ [۰٫۶، ۰٫۴] ارزش اختصاص دهد، چرا که برای مثال این قطعه محتوی گیلاس است و «باب» تنها به گیلاس ارزش می‌دهد.

بر اساس این توابع ارزش ذهنی تعدادی معیار مورد استفاده برای یک تقسیم منصفانه وجود دارد. برخی از این معیارها با هم تناقض دارند اما اکثراً می‌توان آن‌ها را با یکدیگر ترکیب نمود. معیارهایی که در اینجا توضیح داده می‌شوند تنها برای زمانی قابل استفاده‌اند که هر فرد به مقدار مساوی حق داشته باشد:

یک تقسیم متناسب، که تقسیم منصفانهٔ ساده نیز نامیده می‌شود، بدین معنی‌ست که هر فرد حداقل سهم مقتضی خود را بر اساس تابع ارزش خود دریافت می‌کند. برای مثال اگر سه نفر یک کیک را تقسیم کنند، هر نفر با توجه به ارزش‌گذاری خود مقدار ۳/۱ را دریافت خواهد کرد، بدان معنا که هر کدام از n نفر زیرمجموعه‌ای از X را دریافت می‌کند که به آن حداقل ارزش 1/n را اختصاص می‌دهد:

برای هر i

V_i(X_i) ≥ 1/n

' یک تقسیم بدون رشک تضمین می‌کند که هیچ‌کس سهم فرد دیگری را بیش‌تر از سهم خود نمی‌خواهد، بدان معنا که هر فرد سهمی را به دست می‌آورد که حداقل به اندازهٔ سهم هر فرد دیگری به آن ارزش اختصاص می‌دهد:

به ازای هر i و j

(V_i(X_i) >= V_i(X_j

' یک تقسیم exact تقسیمی‌ست که تمامی افراد بر سر ارزش هر سهم اتفاق نظر دارند:

(V_i(X_i) = V_j(X_i

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

' (V_i(X_i) = V_j(X_j

زمانی که دریافت‌کنندگان معیارهای متفاوتی برای ارزش‌گذاری بخش‌های منبع داشته باشند، این امکان وجود دارد که به یک تقسیم «فوق منصفانه» (super fair) (تقسیمی که در آن هر نفر بیش از سهم مقتضی خود را دریافت می‌نماید) دست یابیم. برای مثال، در مسئلهٔ بریدن کیک، ممکن است کسی بیش‌تر به مارزیپان علاقه داشته باشد، کسی به گیلاس، و به همین ترتیب. در این صورت، و تنها در این صورت، امکان دارد هر کدام از n دریافت‌کننده حتی بیش از آنچه از نظرشان بر اساس ارزش‌گذاری شخصی‌شان 1/n ارزش کل کیک باشد را دریافت نمایند. از سوی دیگر، حضور معیارهای متفاوت پتانسیل زیادی را برای طرح سؤالات چالش‌برانگیز و مطالعات گسترده‌تر فراهم می‌آورد.

علاوه بر انصاف، بعضاً مطلوب است که تقسیم بهینهٔ پرتو باشد، بدان معنا که هیچ تخصیص دیگری وجود نداشته باشد که، بدون نامطلوب‌تر کردن سهم یک نفر، سهم فردی را مطلوب‌تر کند. مفهوم کارایی از ایدهٔ بازار کارا در اقتصاد می‌آید.

معیارها و ضوابط یک تقسیم منصفانه بر اساس ارزش‌گذاری هر بازی‌کن، میزان حق مالکیت او، و نتیجهٔ یک فرایند تقسیم منصفانه تعیین می‌گردند. توجه کنید که ارزش‌گذاری سایر بازی‌کنان در این معیارها نقشی ندارند. حق مالکیت‌های متفاوت را می‌توان با استفاده از تعداد بازی‌کنان نمایندهٔ متفاوت برای هر بازی‌کن نشان داد، اما بعضاً ضوابط چیز دیگری را مشخص می‌نمایند.

بعضی اوقات در دنیای واقعی بازی‌کنان دید دقیقی از ارزش‌گذاری سایر بازی‌کنان دارند و بسیار به آن اهمیت می‌دهند. در صورت وجود دانش مطلق مسئله را می‌توان با کمک نظریهٔ الگوریتمی بازی‌ها مدل کرد. مدل کردن دانش نسبی بسیار دشوار است.

فرایندها

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

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

· بر سر معیارها و ضوابط یک تقسیم منصفانه توافق کنند.

· یک فرایند معتبر را برگزیده و قوانین آن را پی بگیرند.

فرض می‌شود که هدف هر بازی‌کن بیشینه کردن مقدار کمینه‌ای‌ست که ممکن است به دست آورند (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 معتقد است که مسئلهٔ تقسیم منصفانه با بهره‌گیری از تکنیک‌های بهینه‌سازی غیرخطی قابل حل است. با این وجود، همچنان جای سؤال است که آیا الگوریتم‌های کاراتری برای زیرمجموعه‌های به‌خصوصی از توابع مطلوبیت غیر افزایشی وجود دارد یا خیر.

انواع

برخی از فرآیندهای برش کیک گسسته‌اند، که در آن‌ها بازی‌کنان به وسیلهٔ یک چاقو کیک را برش می‌زنند (معمولاً طی گام‌های متوالی). از سوی دیگر، فرآیندهای چاقوی متحرک امکان حرکت پیوسته را فراهم کرده و بازی‌کنان می‌توانند در هر نقطه‌ای از کیک فرمان «ایست» بدهند.

نوع دیگری از مسئلهٔ تقسیم منصفانه، تقسیم کارهای روزمره است؛ این مسئله دوگان مسئلهٔ برش کیک است که در آن یک وظیفهٔ غیرمطلوب باید مابین بازی‌کنان تقسیم گردد. مثال کانونی برای این مسئله دسته‌ای از کارهای روزمرهٔ خانه می‌باشد که بازی‌کنان باید انجام دهند. دقت کنید که روش تقسیم کن و برگزین برای تقسیم کار نیز قابل استفاده می‌باشد.

یک تئوری پایه‌ای برای مسائل چند بازی‌کنی، تئوری توازن اجاره (Rental Harmony Theorem) بوده که توسط فرانسیس سو ارائه گشته‌است. خانه‌ای را در نظر بگیرید که به تعداد هم‌خانه‌ها اتاق داشته و باید تصمیم گرفته شود چه اتاقی به چه کسی تعلق گرفته و در نتیجه چه سهمی از اجارهٔ کل را باید بپردازد. همچنین تصور کنید که شرایط زیر برقرار باشد:

خانهٔ خوب: با هر سهمی از اجاره، هر مستأجر یک اتاق را قابل قبول می‌یابد.
مستأجران مقتصد: هر نفر همواره یک اتاق رایگان را به اتاقی که باید برای آن اجاره بپردازد ترجیح می‌دهد.
مجموعه ترجیحات بسته: کسی که یک اتاق را با یک دنبالهٔ همگرا از قیمت‌ها ترجیح می‌دهد، آن اتاق را به قیمت محدودکننده ترجیح می‌دهد.

با توجه به این موارد، تقسیمی از اجاره وجود دارد که به واسطهٔ آن هر نفر یک اتاق متفاوت را ترجیح بدهد. کاربرد جالبی از این تئوری در تئوری تجارت بین‌الملل مشهود است.

با استفاده از لم اسپرنر (Sperner’s Lemma) می‌توان با تقریب مطلوبی به راه حل بدون رشک برای مسائل چند بازی‌کنی دست یافت. این الگوریتم راهی سریع و کاربردی برای حل برخی مسائل تقسیم منصفانه ارائه می‌دهد.

تقسیم ملک و املاک، همان‌طور که برای مثال به هنگام طلاق یا تقسیم ارثیه رخ می‌دهد، معمولاً شامل اقلام غیرقابل تقسیم شده که باید به‌طور منصفانه مابین بازی‌کنان تقسیم گردند. این تقسیم ممکن است با تعدیل نقدی صورت گیرد (چنین بخش‌هایی «اتم» خوانده می‌شوند).

تقسیم شهر برلین در کنفرانس پوتسدام

یک الزام معمول برای تقسیم زمین این است که قطعات به هم متصل باشند. برای مثال، تقسیم برلین پس از جنگ جهانی دوم این شهر را به چهار قسمت متصل تقسیم کرد.

یک تقسیم با وفاق عام تقسیمی‌ست که در آن افراد متعددی بر برابر بودن دو نیمه از یک منبع توافق دارند؛ این مسئله در مبحث تقسیم دقیق بررسی می‌گردد.

مسئلهٔ خاص تقسیم منصفانه برای آب‌های روان در یک رودخانهٔ بین‌المللی در مبحث اشتراک منصفانهٔ رودخانه با جزئیات توصیف شده‌است.

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

"

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

«کیک» تنها یک استعاره است. روش برش عادلانه کیک را می‌توان برای تقسیم انواع منابع، مانند املاک زمین، فضای تبلیغاتی و … استفاده کرد.

مسئله برش منصفانه کیک توسط Hugo Steinhaus پس از جنگ جهانی دوم معرفی شد و هنوز هم موضوع تحقیقات زیادی در ریاضیات، علوم کامپیوتر، اقتصاد و علوم سیاسی است.

تاریخچه

به گفتهٔ سول گارفانکل (Sol Garfunkel) مسئلهٔ برش کیک از مهم‌ترین مسائل حل‌نشدهٔ ریاضی در قرن بیستم میلادی بوده که مهم‌ترین نوع آن در سال ۱۹۹۵ به وسیلهٔ فرایند برامز-تیلور توسط استیون برامز و آلن تیلور حل شد.

ریشه‌های روش تقسیم کن و برگزین ثبت نشده‌اند. فعالیت‌های مرتبط مذاکره و تهاتر نیز بسیار قدیمی هستند. مذاکراتی که بیش از دو نفر را شامل شوند نیز متداول هستند، نمونهٔ اخیری از این موضوع کنفرانس پاتسدم (Potsdam Conference) می‌باشد.

تئوری تقسیم منصفانه تنها از سال‌های پایانی جنگ جهانی دوم شکل گرفت. گروهی از ریاضی‌دانان لهستانی به نام‌های هوگو استاینهاوس (Hugo Steinhaus), برانیسلاو کناستر (Bronislow Knaster)، و استفان باناخ (Stefan Banach) آن را پایه‌گذاری نمودند. یک تقسیم (منصفانه) نسبی برای هر تعداد بازی‌کن به نام last-diminisher در سال ۱۹۴۴ کشف شد. این روش توسط استاینهاوس به باناخ و کناستر نسبت داده شد هنگامی که در سال ۱۹۴۷ در جلسهٔ econometric society در واشینگتن دی. سی. برای نخستین بار از این مسئله پرده برداشت. در این جلسه او همچنین مسئلهٔ یافتن کم‌ترین تعداد برش برای رسیدن به چنین تقسیمی را نیز مطرح نمود.

تقسیم بدون رشک برای اولین بار برای سه بازی‌کن در سال ۱۹۶۰ به‌طور جداگانه توسط جان سلفریج از دانشگاه ایلینوی شمالی و جان هورتون کانوی از دانشگاه کمبریج حل شده و در ستون «بازی‌های ریاضیاتی» توسط مارتین گاردنر در نشریهٔ Scientific American چاپ شد.

تقسیم بدون رشک برای چهار بازی‌کن یا بیش‌تر مسئلهٔ باز دشواری در قرن بیستم میلادی بود. نخستین فرایند برش کیکی که برای هر تعداد بازی‌کن یک تقسیم بدون رشک ارائه داد برای اولین بار در سال ۱۹۹۵ توسط استیون برامز و آلن تیلور منتشر گردید.

در سال ۲۰۶۶ میلادی پیشرفت چشمگیری در زمینهٔ تقسیم equitable توسط استیون ج. برامز، مایکل اِی. جونز و کریستیان کلاملر صورت گرفت.

جستارهای وابسته

منابع

Steven J. Brams and Alan D. Taylor (1996). Fair Division - From cake-cutting to dispute resolution Cambridge University Press.
T.P. Hill (2000). "Mathematical devices for getting a fair share", American Scientist, Vol. 88.
Steinhaus, Hugo (1948). "The problem of fair division". Econometrica.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.