موضوع مقاله: تقسیم منصفانه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تقسیم منصفانه | مقدمه: این مسئله در موقعیت‌های واقعی متفاوتی مطرح می‌گردد، از جمله حراجی‌ها، توافقات طلاق، تخصیص دامنهٔ الکتریکی و فرکانس، مدیریت ترافیک فرودگاه، یا بهره‌برداری از ماهواره‌های رصد کرهٔ زمین. | ## بخش 1: تقسیم منصفانه | این مبحث یک تحقیقات در حال انجام در ریاضیات، اقتصاد (به ویژه تئوری انتخاب اجتماعی)، تئوری بازی، حل و فصل مشاجرات و بسیاری مباحث دیگر می‌باشد. هستهٔ مرکزی تئوری تقسیم منصفانه این است که چنین تقسیمی باید به وسیلهٔ خود بازی‌کنان صورت گیرد. ممکن است در این تقسیم از یک واسطه کمک گرفته شود، اما هرگز نباید برای این کار یک داور داشت، چرا که تنها خود بازی‌کنان از ارزش واقعی کالاها باخبرند. انواع مختلفی از مسائل تقسیم منصفانه بسته به طبیعت کالاهای مورد بحث، معیارهای عدالت، طبیعت بازی‌کنان و ترجیحات آن‌ها، و معیارهای دیگری برای ارزیابی کیفیت تقسیم، مطرح می‌شود. تئوری تقسیم منصفانه معیارهای صریح و روشنی را برای انواع مختلف عدالت ارائه می‌دهد. هدف این تئوری فراهم نمودن فرآیندهایی (الگوریتم‌هایی) برای دستیابی به یک تقسیم منصفانه، یا اثبات امکان‌ناپذیری آن، و مطالعهٔ ویژگی‌های چنین تقسیماتی هم در تئوری و هم در واقعیت می‌باشد. یک «تقسیم» افرازی از مجموعهٔ X به n زیرمجموعه است، به‌طوری‌که هر زیرمجموعه سهم یک بازی‌کن شود: X= X1 چه چیزی تقسیم می‌شود؟ مجموعهٔ X می‌تواند از چندین جنس باشد: X می‌تواند مجموعه‌ای متناهی از اقلام غیرقابل تقسیم باشد، برای مثال:X= {پیانو، ماشین، آپارتمان}، به‌طوری‌که هر قلم باید به‌طور کامل به یک نفر تخصیص داده شود. X می‌تواند مجموعه‌ای نامتناهی از یک منبع قابل تقسیم باشد، برای نمونه: پول، یا یک کیک. از لحاظ ریاضیاتی یک منبع قابل تقسیم به صورت زیرمجموعه‌ای از فضای حقیقی مدل می‌شود؛ برای مثال بازهٔ]۰٬۱[ می‌تواند نمایانگر یک کیک باریک و طویل بوده که می‌بایست به بخش‌های موازی تقسیم گردد. علاوه بر این، مجموعهٔ مورد نظر می‌تواند: همگون باشد – مانند پول، که مقدارش مهم است - یا ناهمگون باشد – مانند یک کیک که ممکن است محتویات متفاوتی داشته باشد. در نهایت، متداول است که فرض شود که اقلام مورد تقسیم: مطلوب هستند، مانند ماشین یا کیک، و یا نامطلوب هستند، مانند وظایف خانه. مسئلهٔ تقسیم مجموعه‌ای از اقلام غیرقابل تقسیم و ناهمگون را واگذاری منصفانهٔ اقلام می‌نامند. مسئلهٔ تقسیم یک منبع قابل تقسیم، ناهمگون و مطلوب را تقسیم کیک منصفانه نیز می‌نامند. مسئلهٔ تقسیم مجموعه‌ای از اقلام ناهمگون و نامطلوب را تقسیم منصفانهٔ کارهای روزمره (در صورت قابل تقسیم بودن وظایف) و یا واگذاری کارهای روزمره (در صورت غیرقابل تقسیم بودن وظایف) می‌نامند. ترکیب این حالات نیز امکان‌پذیر است، برای مثال: در تقسیم ارثیه یا اثاثیهٔ منزل به هنگام طلاق، معمولاً هم با اقلام مطلوب غیرقابل تقسیم ناهمگون مواجه هستیم، هم املاک مطلوب قابل تقسیم ناهمگون همچون زمین، هم املاک مطلوب قابل تقسیم همگون همچون پول. در مسئلهٔ هم‌خانه، چندین دوست با هم یک خانه را اجاره کرده و هم باید اتاق‌ها را به هر نفر تخصیص دهند (مجموعه‌ای از کالاهای غیرقابل تقسیم ناهمگون مطلوب) و هم مبلغ کرایه خانه را تقسیم نمایند (کالای قابل تقسیم همگون نامطلوب). اکثر آنچه معمولاً منصفانه تلقی می‌شود از لحاظ تئوری به دلیل استفاده از حاکم و داور این چنین نیست. این نوع موقعیت غالباً هنگامی رخ می‌دهد که تئوری‌های ریاضی از روی موقعیت‌های زندگی واقعی نام‌گذاری می‌شوند. تصمیمات درون تلمود در زمینهٔ حق مالکیت زمانی که یک ملک ورشکسته است نظرات پیچیده‌ای در مورد انصاف را بازتاب می‌نماید، و اکثر مردم نیز آن‌ها را منصفانه تلقی می‌کنند. با این حال، این مسائل بیش‌تر حاصل مناظرات قانونی مابین خاخامها هستند تا اختلافات مدعیان بر سر ارزش‌گذاری. از همین رو انصاف عینی ممکن نیست، چرا که افراد مختلف ممکن است ارزش‌گذاری‌های متفاوتی برای هر قلم داشته باشند. فرض می‌شود که هر کدام از n نفر یک تابع مطلوبیت یا تابع ارزش شخصی و ذهنی دارند، Vi، که به هر زیرمجموعه از X یک ارزش عددی اختصاص می‌دهد. معمولاً این توابع نرمال شده به‌طوری‌که هر نفر به مجموعهٔ تهی ارزش صفر (Vi(Ø)=۰)، و به کل مجموعهٔ اقلام ارزش یک (Vi(X)=۱)، اگر تمام اقلام مطلوب بوده و ارزش ۱- اگر تمامی اقلام نامطلوب باشند، را اختصاص دهد. به عنوان نمونه: اگر X مجموعه‌ای از اقلام غیرقابل تقسیم {پیانو، ماشین، آپارتمان} باشد، «آلیس» ممکن است به هر کدام ارزش ۳/۱ را بدهد، بدین معنا که هر قلم دقیقاً به اندازهٔ هر کدام از اقلام دیگر برای او ارزش دارد و مهم است. «باب» ممکن است تنها به زیرمجموعهٔ {ماشین، آپارتمان} ارزش یک را اختصاص بدهد، بدین معنا او می‌خواهد ماشین و آپارتمان را با هم به دست آورد، ماشین به تنهایی یا آپارتمان به تنهایی، یا هر کدام آن‌ها به همراه پیانو، برایش ارزشی ندارد. اگر X یک کیک باریک دراز باشد (که بر بازهٔ [۰٬۱] مدل می‌شود)، ممکن است «آلیس» به هر زیرمجموعه متناسب با طولش ارزش دهد، که بدان معنی‌ست که او می‌خواهد کیک بیش‌تری نصیبش شود، بدون توجه به محتویات. «باب» ممکن است تنها به زیرمجموعه‌های بازهٔ [۰٫۶، ۰٫۴] ارزش اختصاص دهد، چرا که برای مثال این قطعه محتوی گیلاس است و «باب» تنها به گیلاس ارزش می‌دهد. | ## بخش 2: تقسیم منصفانه | بر اساس این توابع ارزش ذهنی تعدادی معیار مورد استفاده برای یک تقسیم منصفانه وجود دارد. برخی از این معیارها با هم تناقض دارند اما اکثراً می‌توان آن‌ها را با یکدیگر ترکیب نمود. معیارهایی که در اینجا توضیح داده می‌شوند تنها برای زمانی قابل استفاده‌اند که هر فرد به مقدار مساوی حق داشته باشد: یک تقسیم متناسب، که تقسیم منصفانهٔ ساده نیز نامیده می‌شود، بدین معنی‌ست که هر فرد حداقل سهم مقتضی خود را بر اساس تابع ارزش خود دریافت می‌کند. برای مثال اگر سه نفر یک کیک را تقسیم کنند، هر نفر با توجه به ارزش‌گذاری خود مقدار ۳/۱ را دریافت خواهد کرد، بدان معنا که هر کدام از n نفر زیرمجموعه‌ای از X را دریافت می‌کند که به آن حداقل ارزش 1/n را اختصاص می‌دهد: برای هر i Vi(Xi) ≥ 1/n ' یک تقسیم بدون رشک تضمین می‌کند که هیچ‌کس سهم فرد دیگری را بیش‌تر از سهم خود نمی‌خواهد، بدان معنا که هر فرد سهمی را به دست می‌آورد که حداقل به اندازهٔ سهم هر فرد دیگری به آن ارزش اختصاص می‌دهد: به ازای هر i و j (Vi(Xi) >= Vi(Xj ' یک تقسیم exact تقسیمی‌ست که تمامی افراد بر سر ارزش هر سهم اتفاق نظر دارند: (Vi(Xi) = Vj(Xi یک تقسیم equitable زمانی صورت می‌پذیرد که تمامی افراد به میزان مساوی احساس رضایت کنند، بدان معنی که میزان کیکی که هر بازی‌کن بر اساس ارزش‌گذاری خود دریافت می‌کند برای تمامی بازی‌کنان برابر است. این هدف مشکلی‌ست چرا که بازی‌کنان می‌بایست در مورد ارزش‌گذاری خود صادق باشند: ' (Vi(Xi) = Vj(Xj زمانی که دریافت‌کنندگان معیارهای متفاوتی برای ارزش‌گذاری بخش‌های منبع داشته باشند، این امکان وجود دارد که به یک تقسیم «فوق منصفانه» (super fair) (تقسیمی که در آن هر نفر بیش از سهم مقتضی خود را دریافت می‌نماید) دست یابیم. برای مثال، در مسئلهٔ بریدن کیک، ممکن است کسی بیش‌تر به مارزیپان علاقه داشته باشد، کسی به گیلاس، و به همین ترتیب. در این صورت، و تنها در این صورت، امکان دارد هر کدام از n دریافت‌کننده حتی بیش از آنچه از نظرشان بر اساس ارزش‌گذاری شخصی‌شان 1/n ارزش کل کیک باشد را دریافت نمایند. از سوی دیگر، حضور معیارهای متفاوت پتانسیل زیادی را برای طرح سؤالات چالش‌برانگیز و مطالعات گسترده‌تر فراهم می‌آورد. علاوه بر انصاف، بعضاً مطلوب است که تقسیم بهینهٔ پرتو باشد، بدان معنا که هیچ تخصیص دیگری وجود نداشته باشد که، بدون نامطلوب‌تر کردن سهم یک نفر، سهم فردی را مطلوب‌تر کند. معیارها و ضوابط یک تقسیم منصفانه بر اساس ارزش‌گذاری هر بازی‌کن، میزان حق مالکیت او، و نتیجهٔ یک فرایند تقسیم منصفانه تعیین می‌گردند. حق مالکیت‌های متفاوت را می‌توان با استفاده از تعداد بازی‌کنان نمایندهٔ متفاوت برای هر بازی‌کن نشان داد، اما بعضاً ضوابط چیز دیگری را مشخص می‌نمایند. بعضی اوقات در دنیای واقعی بازی‌کنان دید دقیقی از ارزش‌گذاری سایر بازی‌کنان دارند و بسیار به آن اهمیت می‌دهند. در صورت وجود دانش مطلق مسئله را می‌توان با کمک نظریهٔ الگوریتمی بازی‌ها مدل کرد. فرایندها یک فرایند تقسیم منصفانه متشکل از فعالیت‌هایی‌ست که بازی‌کنان می‌بایست بر اساس دادهٔ مشهود و ارزش‌گذاری‌های خود انجام دهند. یک فرایند معتبر فرآیندی‌ست که یک تقسیم منصفانه برای هر کسی که بر اساس ارزش‌گذاری خود منطقی عمل کند را تضمین کند. زمانی که یک عمل به ارزش‌گذاری یک بازی‌کن وابسته باشد، فرایند استراتژی را ارائه می‌دهد که یک بازی‌کن منطقی پیش می‌گیرد. یک بازی‌کن ممکن است طوری رفتار کند که انگار یک قطعه ارزشی دیگر دارد، اما باید ثابت قدم باشد. به عنوان نمونه، اگر فرآیندی می‌گوید که بازی‌کن اول کیک را به دو قسمت تقسیم کرده و بازی‌کن دوم یک قسمت را برگزیند، بازی‌کن اول نمی‌تواند ادعا کند که قسمت بازی‌کن دوم بزرگ‌تر است. فرض می‌شود که هدف هر بازی‌کن بیشینه کردن مقدار کمینه‌ای‌ست که ممکن است به دست آورند (maximin). در یک فرایند متناهی برای مثال در هر زمان تنها یک نفر کیک را بریده یا علامت‌گذاری می‌کند. در فرآیندهای پیوسته برای مثال یک بازی‌کن چاقو را روی کیک حرکت داده و بازی‌کن دیگر به او می‌گوید که کجا بایستد. دو بازی‌کن برای دو نفر راه حل ساده‌ای وجود دارد که معمولاً مورد استفاده قرار می‌گیرد. یک نفر منبع را دو قسمتی که از نظر خودش دو نیمهٔ برابر هستند تقسیم می‌کند، و نفر دیگر نیمه‌ای را که ترجیح می‌دهد برمی‌گزیند. به همین سبب شخص تقسیم‌کننده انگیزهٔ زیادی برای تقسیم منصفانه دارد، چرا که اگر این‌چنین تقسیم نکند احتمالاً قسمت نامطلوبی نصیبش می‌گردد. اولین بازی‌کن چاقویی را از طرف چپ روی کیک حرکت داده و هر زمان هر کدام از بازی‌کنان بگوید «ایست»، قسمت سمت چپ چاقو را می‌گیرد. چندین بازی‌کن تقسیم منصفانه برای سه بازی‌کن یا بیش‌تر بسیار پیچیده‌تر از دو بازی‌کن است. تقسیم نسبی راحت‌ترین راه است و مقاله برخی از فرآیندهایی را که برای هرتعداد بازی‌کن قابل استفاده است را ارائه می‌دهد. تقسیم بدون رشک برای سه بازی‌کن برای بار اول در سال ۱۹۶۰ به‌طور جداگانه توسط جان سلفریج در دانشگاه ایلینوی شمالی و جان هورتون کانوی در دانشگاه کمبریج حل شد. | ## بخش 3: تقسیم منصفانه | این فرایند اولین فرایند برش کیک برای چهار بازی‌کن یا بیش‌تر است که تقسیمی بدون رشک را برای هرتعداد بازی‌کن موجب می‌شود. یک فرایند چاقوی متحرک با تعداد برش‌های محدود در سال ۱۹۹۷ برای چهار بازی‌کن یافت شد. هیچ الگوریتم تقسیم دقیقی برای سه بازی‌کن و بیش‌تر وجود ندارد، اما الگوریتم‌های «تقریباً دقیق» که بدون رشک نیز باشند و بتوانند به هر درجهٔ دلخواه از دقت دست یابند، موجود است. مطلوبیت غیر افزایشی اکثر فرآیندهای تقسیم منصفانه که پیش‌تر توضیح داده شد بر این فرض بنا شده‌اند که مطلوبیت بازی‌کنان افزایشی‌ست. به بیان دیگر، اگر بازی‌کنی یک مقدار مطلوبیت از ۲۵ گرم کیک شکلاتی به دست آرود، فرض می‌شود که او از ۵۰ گرم از همین کیک شکلاتی دقیقاً دو برابر این مقدار مطلوبیت را دریافت خواهد کرد. او همچنین ثابت کرد که مواردی از تقسیم منصفانه که در آن‌ها بازی‌کنان توابع مطلوبیت غیر افزایشی داشته‌اند ممکن است هیچ راه حل متناسبی نداشته باشند. با این وجود، همچنان جای سؤال است که آیا الگوریتم‌های کاراتری برای زیرمجموعه‌های به‌خصوصی از توابع مطلوبیت غیر افزایشی وجود دارد یا خیر. انواع برخی از فرآیندهای برش کیک گسسته‌اند، که در آن‌ها بازی‌کنان به وسیلهٔ یک چاقو کیک را برش می‌زنند (معمولاً طی گام‌های متوالی). از سوی دیگر، فرآیندهای چاقوی متحرک امکان حرکت پیوسته را فراهم کرده و بازی‌کنان می‌توانند در هر نقطه‌ای از کیک فرمان «ایست» بدهند. نوع دیگری از مسئلهٔ تقسیم منصفانه، تقسیم کارهای روزمره است؛ این مسئله دوگان مسئلهٔ برش کیک است که در آن یک وظیفهٔ غیرمطلوب باید مابین بازی‌کنان تقسیم گردد. مثال کانونی برای این مسئله دسته‌ای از کارهای روزمرهٔ خانه می‌باشد که بازی‌کنان باید انجام دهند. خانه‌ای را در نظر بگیرید که به تعداد هم‌خانه‌ها اتاق داشته و باید تصمیم گرفته شود چه اتاقی به چه کسی تعلق گرفته و در نتیجه چه سهمی از اجارهٔ کل را باید بپردازد. همچنین تصور کنید که شرایط زیر برقرار باشد: خانهٔ خوب: با هر سهمی از اجاره، هر مستأجر یک اتاق را قابل قبول می‌یابد. مستأجران مقتصد: هر نفر همواره یک اتاق رایگان را به اتاقی که باید برای آن اجاره بپردازد ترجیح می‌دهد. مجموعه ترجیحات بسته: کسی که یک اتاق را با یک دنبالهٔ همگرا از قیمت‌ها ترجیح می‌دهد، آن اتاق را به قیمت محدودکننده ترجیح می‌دهد. با توجه به این موارد، تقسیمی از اجاره وجود دارد که به واسطهٔ آن هر نفر یک اتاق متفاوت را ترجیح بدهد. تقسیم ملک و املاک، همان‌طور که برای مثال به هنگام طلاق یا تقسیم ارثیه رخ می‌دهد، معمولاً شامل اقلام غیرقابل تقسیم شده که باید به‌طور منصفانه مابین بازی‌کنان تقسیم گردند. این تقسیم ممکن است با تعدیل نقدی صورت گیرد (چنین بخش‌هایی «اتم» خوانده می‌شوند). برای مثال، تقسیم برلین پس از جنگ جهانی دوم این شهر را به چهار قسمت متصل تقسیم کرد. یک تقسیم با وفاق عام تقسیمی‌ست که در آن افراد متعددی بر برابر بودن دو نیمه از یک منبع توافق دارند؛ این مسئله در مبحث تقسیم دقیق بررسی می‌گردد. مسئلهٔ خاص تقسیم منصفانه برای آب‌های روان در یک رودخانهٔ بین‌المللی در مبحث اشتراک منصفانهٔ رودخانه با جزئیات توصیف شده‌است. برش منصفانه کیک برش منصفانه کیک''' یک مسئلهٔ تقسیم عادلانه است که منبع ناهمگنی دارد و قسمت‌های مخالف آن می‌تواند تا حدودی متفاوت باشند و همچنین بدیهی است که منبعی تفکیک‌پذیر می‌باشد زیرا با تکه کردن یک کیک ارزش آن تغییری نمی‌کند. منبع باید میان چند نفر که سلایق مختلفی در مورد قسمت‌های مختلف کیک دارند تقسیم شود، به عنوان مثال، برخی از مردم قسمت‌های پر شکلات کیک را ترجیح می‌دهند، برخی گیلاس را ترجیح می‌دهند، برخی نیز فقط ترجیح می‌دهند بزرگترین قطعه کیک نسیب آن‌ها شود. تقسیم باید به‌طور ذهنی عادلانه باشد، بدین صورت که هر فرد باید قطعه کیکی را دریافت کند که از نظرش سهمی عادلانه است. تاریخچه به گفتهٔ سول گارفانکل (Sol Garfunkel) مسئلهٔ برش کیک از مهم‌ترین مسائل حل‌نشدهٔ ریاضی در قرن بیستم میلادی بوده که مهم‌ترین نوع آن در سال ۱۹۹۵ به وسیلهٔ فرایند برامز-تیلور توسط استیون برامز و آلن تیلور حل شد. در این جلسه او همچنین مسئلهٔ یافتن کم‌ترین تعداد برش برای رسیدن به چنین تقسیمی را نیز مطرح نمود. تقسیم بدون رشک برای اولین بار برای سه بازی‌کن در سال ۱۹۶۰ به‌طور جداگانه توسط جان سلفریج از دانشگاه ایلینوی شمالی و جان هورتون کانوی از دانشگاه کمبریج حل شده و در ستون «بازی‌های ریاضیاتی» توسط مارتین گاردنر در نشریهٔ Scientific American چاپ شد. تقسیم بدون رشک برای چهار بازی‌کن یا بیش‌تر مسئلهٔ باز دشواری در قرن بیستم میلادی بود. | ## جمع‌بندی | نخستین فرایند برش کیکی که برای هر تعداد بازی‌کن یک تقسیم بدون رشک ارائه داد برای اولین بار در سال ۱۹۹۵ توسط استیون برامز و آلن تیلور منتشر گردید.