Egalitarian cake-cutting
مساوی کیک کاٹنے کی ایک قسم منصفانہ کیک کاٹنے کی ہے جس میں انصاف کا معیار مساویانہ اصول ہے۔ کیک ایک مسلسل وسائل (جیسے زمین یا وقت) کی نمائندگی کرتا ہے، جسے وسائل کے کچھ حصوں پر مختلف قیمتوں والے لوگوں کے درمیان مختص کرنا ہوتا ہے۔ مساوی کیک کاٹنے کا مقصد ایجنٹ کی سب سے چھوٹی قیمت کو زیادہ سے زیادہ کرنا ہے ؛ اس کے تابع، اگلی سب سے چھوٹی قیمت کو زیادہ سے زیادہ کرنا ؛ اور اسی طرح۔ اسے لیکسیمین کیک کاٹنے بھی کہا جاتا ہے، کیونکہ افادیت کے ویکٹر پر لیکسیمین آرڈر کا استعمال کرتے ہوئے اصلاح کی جاتی ہے۔ مساوی کیک کاٹنے کے تصور کو سب سے پہلے ڈبنس اور اسپینیر نے بیان کیا تھا، جنہوں نے اسے "بہترین تقسیم" کہا تھا۔ جب بھی مختص کا مجموعہ ایک کمپیکٹ جگہ ہوتا ہے تو وجود لیکسمین-بہترین مختص موجود ہوتا ہے۔ یہ ہمیشہ ایسا ہی ہوتا ہے جب متفرق اشیاء مختص کی جاتی ہیں، اور مسلسل یکساں وسائل کی ایک محدود تعداد مختص کرتے وقت ثابت کرنا آسان ہوتا ہے۔ ڈوبنز اور اسپینیر نے ثابت کیا کہ، ایک مسلسل متنوع وسائل ("کیک") کے ساتھ، مختص کا مجموعہ کمپیکٹ ہے۔ لہذا، لیکسیمین-بہترین کیک کی تقسیم ہمیشہ موجود رہتی ہے۔ اس وجہ سے، لیکسیمین کیک مختص کرنے کے اصول کو بعض اوقات ڈوبنس-اسپینر اصول کہا جاتا ہے۔ متغیرات جب ایجنٹوں کی قیمتوں کو معمول پر نہیں لایا جاتا ہے (یعنی، مختلف ایجنٹ پورے کیک کو ایک مختلف قیمت تفویض کر سکتے ہیں)، تو مختص کی مطلق افادیت پروفائل (جہاں عنصر i صرف ایجنٹ i کی افادیت ہے)، اور اس کے متعلقہ افادیت پروفائل (جہاں عنصر i ایجنٹ کی افادیت ہے جسے ایجنٹ i کی کل قیمت سے تقسیم کیا جاتا ہے) کے درمیان فرق ہوتا ہے۔ مطلق لیکسیمین قاعدہ ایک مختص کا انتخاب کرتا ہے جس میں مطلق افادیت پروفائل لیکسیمین-زیادہ سے زیادہ ہے، اور رشتہ دار لیکسیمین قاعدہ ایک مختص کا انتخاب کرتا ہے جس میں رشتہ دار افادیت پروفائل لیکسیمین-زیادہ سے زیادہ ہے۔ خصوصیات لیکسیمین اصول کی دونوں قسمیں پیریٹو-آپٹیمل اور آبادی مونوٹونک ہیں۔ تاہم، وہ دیگر خصوصیات میں مختلف ہیں: مطلق-لیکسیمین قاعدہ وسائل یکسانیت ہے لیکن متناسب نہیں ہے۔ رشتہ دار-لیکسیمین قاعدہ متناسب ہے لیکن وسائل یکسانیت نہیں ہے۔ حسد کی آزادی سے تعلق لیکسیمین اصول کی دونوں شکلیں ایسی مختصیاں حاصل کر سکتی ہیں جو حسد سے پاک نہیں ہیں۔ مثال کے طور پر، فرض کریں کہ 5 ایجنٹ ہیں، کیک 3 خطوں کے ساتھ ٹکڑے ٹکڑے میں یکساں ہے، اور ایجنٹوں کی قیمتیں ہیں (گمشدہ اقدار صفر ہیں): تمام ایجنٹ پورے کیک کی قدر 15 پر کرتے ہیں، لہذا مطلق-لیکسمین اور رشتہ دار-لیکسمین مساوی ہیں۔ سب سے بڑی ممکنہ کم از کم قیمت 5 ہے، لہذا ایک لیکسیمین الاٹمنٹ میں تمام ایجنٹوں کو کم از کم 5 دینا ضروری ہے۔ اس کا مطلب یہ ہے کہ حق کو ایجنٹوں سی، ڈی، ای کے درمیان یکساں طور پر تقسیم کیا جانا چاہیے، اور درمیانی حصہ مکمل طور پر ایجنٹ بی کو دیا جانا چاہیے۔ لیکن پھر اے حسد بی ڈوبنس اور اسپینیر نے ثابت کیا کہ، جب تمام قدر کے اقدامات سختی سے مثبت ہوتے ہیں، تو ہر رشتہ دار الیکسیمین مختص حسد سے پاک ہوتا ہے۔ ویلر نے ایک حسد سے پاک اور موثر کیک مختص کیا جو رشتہ دار-لیکسیمین نہیں ہے۔ کیک ہے [0,1]، تین ایجنٹ ہیں، اور ان کی قیمت کے اقدامات مثلث تقسیم ہیں جو بالترتیب 1/4، 1/2 اور 3/4 پر مرکوز ہیں۔ الاٹمنٹ ([0,3/8]، [3/8,5 8]، [5/8,1]) میں یوٹیلیٹی پروفائل (3/8,7 16,7/16) ہے۔ یہ حسد سے پاک اور مفید بہترین ہے، اس لیے پیریٹو موثر ہے۔ تاہم، لیکسیمین بہتر یوٹیلیٹی پروفائل کے ساتھ ایک اور الاٹمنٹ ([0,5/16]، [5/16,11 16]، [11/16,1]) ہے۔ کمپیوٹیشن Dall 'aglio ایک leximin-بہترین وسائل مختص کرنے کے حساب کے لیے ایک الگورتھم پیش کرتا ہے۔ مساوی کیک کاٹنے کو بھی دیکھیں-ایک مختص رقم جو ہر ایجنٹ کو مساوی افادیت دیتی ہے۔ اکثر، مساویانہ الاٹمنٹ مساوی الاٹمنٹ کے ساتھ موافق ہوتی ہے، کیونکہ اگر یوٹیلیٹیز مختلف ہیں، تو بڑی یوٹیلیٹی والے ایجنٹ سے کچھ کیک منتقل کرکے چھوٹی یوٹیلیٹی کو بہتر بنایا جا سکتا ہے۔ مساویانہ مساوات-یکساں وسائل کی تقسیم کے تناظر میں اسی طرح کا تصور۔ حوالہ جات مساوات کیک کاٹنے