Fair allocation of items and money
اشیا اور رقم کی منصفانہ تقسیم منصفانہ اشیا کی تقسیم کے مسائل کی ایک قسم ہے جس میں، مختص کرنے کے عمل کے دوران، کچھ شرکاء سے رقم دینا یا لینا ممکن ہے۔ پیسے کے بغیر، غیر منقسم اشیاء کو منصفانہ طور پر مختص کرنا ناممکن ہو سکتا ہے۔ مثال کے طور پر، اگر ایک آئٹم اور دو لوگ ہیں، اور آئٹم کو مکمل طور پر ان میں سے ایک کو دیا جانا چاہیے، تو الاٹمنٹ دوسرے کے لیے غیر منصفانہ ہوگی۔ مالیاتی ادائیگیاں انصاف کے حصول کو ممکن بناتی ہیں، جیسا کہ ذیل میں بیان کیا گیا ہے۔ دو ایجنٹ اور ایک آئٹم دو ایجنٹ اور ایک آئٹم کے ساتھ، مندرجہ ذیل سادہ الگورتھم (جو کٹ اینڈ چوائس کا ایک مختلف قسم ہے) کا استعمال کرتے ہوئے انصاف حاصل کرنا ممکن ہے: ایلس ایک قیمت پی کہتی ہے جو وہ آئٹم کے لیے ادا کرنے کو تیار ہے۔ جارج انتخاب کرتا ہے کہ آیا آئٹم لے کر پی ادا کرنا ہے، یا آئٹم کو ایلس پر چھوڑ دینا ہے تاکہ ایلس پی ادا کرے۔ یہ الگورتھم یہ فرض کرتا ہے کہ ایجنٹوں کے پاس کواسیلینئر یوٹیلیٹیز ہیں، یعنی ان کی افادیت آئٹم کی قیمت اور ان کے پاس موجود رقم ہے۔ اگر جارج کو لگتا ہے کہ ایلس کی قیمت کم ہے (وہ پی سے زیادہ ادا کرنے کو تیار ہے)، تو وہ آئٹم لیتا ہے اور پی ادا کرتا ہے، اور اس کی افادیت مثبت ہے، اس لیے اسے ایلس سے حسد نہیں ہوتا۔ ایلس بھی جارج سے حسد نہیں کرتی کیونکہ اس کی افادیت-اس کی نظر میں-0 ہے۔ اسی طرح، اگر جارج کو لگتا ہے کہ ایلس کی قیمت زیادہ ہے (وہ پی یا اس سے زیادہ ادا کرنے کو تیار ہے)، تو وہ اس چیز کو ایلس کے پاس چھوڑ دیتا ہے اور حسد نہیں کرتا، کیونکہ اس کی نظر میں ایلس کی افادیت منفی ہے۔ ادا شدہ رقم p کو بعد میں کھلاڑیوں کے درمیان مساوی طور پر تقسیم کیا جا سکتا ہے، کیونکہ مساوی مالیاتی منتقلی متعلقہ افادیت کو متاثر نہیں کرتی ہے۔ پھر، مؤثر طریقے سے، خریداری کا ایجنٹ فروخت کرنے والے ایجنٹ کو پی/2 ادا کرتا ہے۔ ہر ایجنٹ کی کل افادیت اس شے کے لیے اس کی افادیت کا کم از کم ایک تہائی ہے۔ اگر ایجنٹوں کے مختلف حقوق ہیں، تو ادا شدہ رقم کو شراکت داروں کے درمیان ان کے حقوق کے تناسب سے تقسیم کیا جانا چاہیے۔ اس سادہ خیال کو دو سے زیادہ کھلاڑیوں اور زیادہ پیچیدہ ترتیبات تک بڑھانے کے مختلف کام ہیں۔ ان کاموں میں انصاف کا بنیادی معیار حسد کی آزادی ہے۔ اس کے علاوہ، کچھ کام ایک ایسی ترتیب پر غور کرتے ہیں جس میں ایک خیر خواہ تیسرا فریق مختص رقم کو سبسڈی دینے کے لیے تیار ہوتا ہے، لیکن حسد کی آزادی کے تابع سبسڈی کی رقم کو کم کرنا چاہتا ہے۔ اس مسئلے کو کم از کم سبسڈی حسد سے پاک الاٹمنٹ کہا جاتا ہے۔ یونٹ ڈیمانڈ ایجنٹ زیادہ سے زیادہ ایک آئٹم میں دلچسپی رکھتے ہیں۔ کرایہ کی ہم آہنگی اس ترتیب کا ایک خاص معاملہ یہ ہے کہ جب کسی اپارٹمنٹ میں کمروں کو کرایہ داروں کے درمیان تقسیم کیا جائے۔ اس کی خصوصیت تین تقاضے ہیں: (a) ایجنٹوں کی تعداد اشیاء کی تعداد کے برابر ہے، (b) ہر ایجنٹ کو بالکل ایک آئٹم (کمرہ) ملنا چاہیے، (c) ایجنٹوں کی طرف سے ادا کی جانے والی کل رقم ایک مقررہ مستقل کے برابر ہونی چاہیے، جو اپارٹمنٹ کے کل کرایے کی نمائندگی کرتی ہے۔ اسے رینٹل ہارمنی کا مسئلہ کہا جاتا ہے۔ زیادہ عمومی ترتیبات عام طور پر، معاشیات کے ادب میں، یہ فرض کرنا عام ہے کہ ہر ایجنٹ کا بنڈلوں پر یوٹیلیٹی فنکشن ہوتا ہے (ایک بنڈل کسی شے کا جوڑا اور ایک مخصوص رقم ہوتی ہے)۔ یوٹیلیٹی فنکشن مسلسل اور پیسے میں بڑھتا ہوا ہونا چاہیے۔ یہ پیسے میں لکیری ہونے کی ضرورت نہیں ہے، لیکن "آرکیمیڈین" ہونا ضروری ہے، یعنی، کچھ ویلیو V موجود ہے کہ، ہر دو اشیاء جے اور کے کے لیے، آبجیکٹ جے پلس وی کی افادیت آبجیکٹ کے کی افادیت سے بڑی ہونی چاہیے (متبادل طور پر، آبجیکٹ جے کو مفت میں حاصل کرنے کی افادیت آبجیکٹ کے حاصل کرنے اور وی کی ادائیگی کرنے کی افادیت سے بڑی ہے)۔ کواسیلینئر یوٹیلیٹی آرکیمیڈین یوٹیلیٹی کا ایک خاص معاملہ ہے، جس میں V دو اشیاء کے درمیان (ایک ہی ایجنٹ کے لیے) سب سے بڑا قدر کا فرق ہے۔ سوانسن نے سب سے پہلے ثابت کیا کہ، جب تمام ایجنٹ آرکیمیڈین ہوتے ہیں، تو ایک حسد سے پاک مختص موجود ہوتا ہے اور پیریٹو بہترین ہوتا ہے۔ ڈیمانج، گیل اور سوٹومیئر نے ایک قدرتی چڑھتی ہوئی نیلامی دکھائی جو یونٹ ڈیمانڈ ایجنٹوں کے لیے مالیاتی ادائیگیوں کا استعمال کرتے ہوئے حسد سے پاک مختص کو حاصل کرتی ہے۔ ماسکن نے پیریٹو-بہترین حسد سے پاک مختص رقم کے وجود کو ثابت کیا جب کل رقم (n-1) V سے زیادہ ہوتی ہے۔ ثبوت مسابقتی توازن کا استعمال کرتے ہیں۔ نوٹ کریں کہ (n-1) V کی سبسڈی درکار ہو سکتی ہے: اگر تمام ایجنٹ کسی ایک شے کو V پر اور دوسری اشیاء کو 0 پر اہمیت دیتے ہیں، تو حسد کی آزادی کے لیے ہر اس ایجنٹ کے لیے V کی سبسڈی درکار ہوتی ہے جو شے وصول نہیں کرتا ہے۔ ٹیڈینوما اور تھامسن حسد سے پاک الاٹمنٹ کے قوانین کی کئی مستقل خصوصیات کا مطالعہ کرتے ہیں۔ اراگونز حسد کی آزادی کے لیے درکار سبسڈی کی کم از کم رقم کی خصوصیت رکھتا ہے۔ اس کم از کم سبسڈی کو حاصل کرنے والی مختص رقم تقریبا منفرد ہے: ایجنٹوں کے ساتھ اشیاء کو جوڑنے کا صرف ایک ہی طریقہ ہے، اور تمام ایجنٹ تمام کم از کم سبسڈی کی مختص رقم سے لاتعلق ہیں۔ یہ الکن، ڈیمانج اور گیل کے "منی-راولسی حل" نامی حل کے ساتھ موافق ہے۔ یہ کثیر الجہتی وقت میں پایا جا سکتا ہے، زیادہ سے زیادہ وزن کا ملاپ ڈھونڈ کر اور پھر ایک مخصوص محرک گراف میں مختصر ترین راستے ڈھونڈ کر۔ کلیجن اسی ترتیب کے لیے ایک اور کثیر الجہتی وقت کا الگورتھم پیش کرتا ہے۔ اس کا الگورتھم ضمنی ادائیگیوں کے پولیٹوپ کا استعمال کرتا ہے جو دیئے گئے الاٹمنٹ کو حسد سے پاک بناتا ہے: یہ پولیٹوپ غیر خالی ہے اگر اصل الاٹمنٹ پیریٹو موثر ہے۔ غیر ہدایت شدہ حسد گراف کی کنیکٹیویٹی اس پولیٹوپ کے انتہائی نکات کی خصوصیت رکھتی ہے۔ اس کا مطلب انتہائی حسد سے پاک مختص رقم تلاش کرنے کا ایک طریقہ ہے۔ اضافی ایجنٹوں کے اضافی ایجنٹوں کو کئی اشیاء مل سکتی ہیں، اس لیے مختص کرنے کا مسئلہ زیادہ پیچیدہ ہو جاتا ہے-اور بھی بہت سی ممکنہ مختصیاں ہیں۔ ناسٹر کی نیلامی اشیاء اور رقم کی منصفانہ تقسیم کا پہلا طریقہ کار برونسلا ناسٹر نے ایجاد کیا تھا اور اسے ہیوگو اسٹین ہاؤس نے شائع کیا تھا۔ یہ نیلامی مندرجہ ذیل طریقے سے کام کرتی ہے، ہر آئٹم کے لیے الگ سے: ہر ایجنٹ آئٹم پر بولی جمع کراتا ہے۔ یہ شے سب سے زیادہ بولی لگانے والے کو دی جاتی ہے (من مانی طور پر تعلقات توڑنا)۔ فاتح اپنی بولی کا (n-1)/n ادا کرتا ہے ؛ دوسرے ایجنٹوں میں سے ہر ایک کو اس کی بولی کا 1/n ملتا ہے ؛ چونکہ فاتح سب سے زیادہ بولی لگانے والا ہوتا ہے، اس لیے ایک غیر منفی سرپلس ہوتا ہے ؛ سرپلس کو ایجنٹوں میں مساوی طور پر تقسیم کیا جاتا ہے۔ ہر ایجنٹ کی افادیت اس قدر کا کم از کم 1/n ہے جو وہ اشیاء کے پورے سیٹ سے منسوب کرتا ہے، لہذا مختص متناسب ہے۔ مزید برآں، مختص افادیت کے مجموعے کو زیادہ سے زیادہ کرتا ہے، لہذا یہ پیریٹو موثر ہے۔ نیسٹر کی نیلامی حکمت عملی سے محفوظ نہیں ہے۔ کچھ محققین نے اس کی کارکردگی کا تجزیہ کیا جب ایجنٹ اسٹریٹجک طور پر کھیلتے ہیں: ایسسن ثابت کرتا ہے کہ توازن کی تقسیم اب بھی پیریٹو موثر ہے، لیکن متناسب سابق پوسٹ نہیں ہوسکتی ہے۔ تاہم، اوسطا، ایجنٹوں کو ایک ہی نتیجہ ملتا ہے جیسے کہ ہر کوئی سچا تھا۔ یعنی میکانزم متناسب ہے۔ فریگنیلی اور مرینا یہ ظاہر کرتے ہیں کہ، یہاں تک کہ وہ ایجنٹ جو لامحدود خطرے سے گریزاں ہیں، دوسرے ایجنٹوں کے اعلانات سے قطع نظر، اپنی قیمتوں کی مشترکہ غلط رپورٹنگ کے ذریعے محفوظ فائدہ حاصل کر سکتے ہیں۔ نیسٹر کی نیلامی کو وائرلیس چینلز کی منصفانہ تقسیم کے مطابق ڈھال لیا گیا ہے۔ رائتھ کی نیلامی میتھیاس جی رائتھ نے ناسٹر کی نیلامی پر ایک قسم پیش کی، جسے انہوں نے "ایڈجسٹڈ ناسٹر" کہا۔ جیسا کہ نیسٹر کی نیلامی میں، ہر شے سب سے زیادہ بولی لگانے والے کو دی جاتی ہے۔ تاہم، ادائیگیاں مختلف ہیں۔ ادائیگیوں کا تعین اس طرح کیا جاتا ہے: ایک آئٹم جیتنے والا ہر ایجنٹ اس آئٹم کے لیے اپنی بولی ادا کرتا ہے۔ ایجنٹوں کی طرف سے ادا کی جانے والی کل رقم ان کی بولیوں کے تناسب سے ان کے درمیان تقسیم کی جاتی ہے۔ نیسٹر کی نیلامی اور رائتھ کی نیلامی کے درمیان فرق کو واضح کرنے کے لیے، مندرجہ ذیل اقدار کے ساتھ دو آئٹمز اور دو ایجنٹوں کے ساتھ ایک ترتیب پر غور کریں: دونوں نیلامیوں میں، جارج دونوں آئٹمز جیتتا ہے، لیکن ادائیگیاں مختلف ہیں: نیسٹر کی نیلامی میں، جارج 90 ادا کرتا ہے، ایلس کو 10 ملتا ہے، اور 80 کا فرق یکساں طور پر تقسیم کیا جاتا ہے، لہذا خالص افادیت 50، 130 ہیں۔ رائتھ کی نیلامی میں جارج 180 ادا کرتا ہے اور اسے 20:180 = 1:9 کے تناسب میں تقسیم کیا جاتا ہے، یعنی ایلس کو 18 اور جارج کو 162 ملتا ہے۔ نوٹ کریں کہ ادائیگیوں کا حساب ایک ہی وقت میں تمام آئٹمز پر لگایا جاتا ہے-ہر آئٹم کے لیے الگ سے نہیں۔ انسانی مضامین کے ساتھ تجربات میں، یہ پایا گیا کہ شرکاء رائتھ کی نیلامی (ایڈجسٹڈ نیسٹر) کو ڈیویڈ اینڈ چوز اور پروپورشنل نیسٹر کو ترجیح دیتے ہیں (ایک قسم جس میں ہر فاتح ہر ہارنے والے کو جیتنے والے کا 1/n ادا کرتا ہے ؛ مندرجہ بالا مثال میں، جارج ایلس کو 90 ادا کرتا ہے، اور خالص افادیت 90، 90 ہیں)۔ معاوضے کا طریقہ کار ہاکے، رائتھ اور سو معاوضے کا طریقہ کار پیش کرتے ہیں۔ ان کا طریقہ کار اشیاء کے بنڈلوں پر من مانی رکاوٹوں کی اجازت دیتا ہے، جب تک کہ وہ گمنام ہوں (شراکت داروں کے درمیان ان کی شناخت کی بنیاد پر فرق نہ کریں)۔ مثال کے طور پر، کوئی رکاوٹ بالکل نہیں ہو سکتی، یا کوئی رکاوٹ ہو سکتی ہے جیسے کہ "ہر پارٹنر کو کم از کم ایک مخصوص تعداد میں آئٹمز موصول ہونے چاہئیں"، یا "کچھ آئٹمز کو ایک ساتھ بنڈل کیا جانا چاہیے" (مثال کے طور پر۔ کیونکہ وہ زمینی پلاٹ ہیں جن سے جڑے رہنا ضروری ہے) وغیرہ۔ "آئٹمز" میں مثبت یا منفی دونوں افادیت ہو سکتی ہیں۔ شراکت دار کے لیے "اہلیت کی ضرورت" ہوتی ہے: اس کی بولیوں کا مجموعہ کم از کم کل لاگت ہونا چاہیے۔ یہ طریقہ کار درج ذیل مراحل میں کام کرتا ہے۔ زیادہ سے زیادہ (مفید) مختص رقم تلاش کریں-ایک ایسی مختص رقم جس میں زیادہ سے زیادہ ضروریات ہوں جو اشیاء کے بنڈلوں پر موجود رکاوٹوں کو پورا کرتی ہو۔ اگر کوئی رکاوٹیں نہیں ہیں، تو ایک مختص رقم جو ہر آئٹم کو پارٹنر کو سب سے زیادہ قیمت کے ساتھ دیتی ہے وہ زیادہ سے زیادہ رقم ہے۔ اگر رکاوٹیں ہیں (جیسے کہ "کم از کم ایک آئٹم فی پارٹنر")، تو زیادہ سے زیادہ الاٹمنٹ تلاش کرنا زیادہ مشکل ہو سکتا ہے۔ ہر پارٹنر سے اس کے لیے مختص کردہ بنڈل کی قیمت وصول کریں۔ اس سے پیسے کا ابتدائی ذخیرہ پیدا ہوتا ہے۔ ابتدائی پول سے لاگت ادا کریں۔ اگر تمام شراکت دار اہلیت کی ضرورت کو پورا کرتے ہیں، تو پول میں موجود رقم کافی ہے، اور کچھ اضافی رقم باقی رہ سکتی ہے۔ حسد کرنے والے شراکت داروں کو معاوضہ دے کر حسد کو ختم کریں۔ معاوضے کے زیادہ تر دور ہوتے ہیں۔ طریقہ کار مکمل طور پر وضاحتی ہے اور واضح طور پر بتاتا ہے کہ کون سی تلافی کی جانی چاہیے، اور کس ترتیب میں۔ اس کے علاوہ، یہ کمپیوٹر سپورٹ کے بغیر انجام دینے کے لیے کافی آسان ہے۔ تمام مراحل میں کیے گئے معاوضوں کا مجموعہ سب سے چھوٹی رقم ہے جو حسد کو ختم کرنے کے لیے درکار ہوتی ہے، اور یہ کبھی بھی اضافی رقم سے زیادہ نہیں ہوتی۔ اگر کچھ سرپلس باقی رہتا ہے، تو اسے کسی بھی طرح سے تقسیم کیا جا سکتا ہے جس سے حسد پیدا نہ ہو، مثال کے طور پر، ہر ساتھی کو مساوی رقم دے کر (مقالے میں دوسرے آپشنز پر تبادلہ خیال کیا گیا ہے جنہیں "منصفانہ" سمجھا جا سکتا ہے)۔ جب بہت سی اشیاء اور پیچیدہ رکاوٹیں ہوتی ہیں، تو ابتدائی مرحلہ-زیادہ سے زیادہ الاٹمنٹ تلاش کرنا-کمپیوٹر کے بغیر حساب لگانا مشکل ہو سکتا ہے۔ اس صورت میں، معاوضے کا طریقہ کار من مانی الاٹمنٹ سے شروع ہو سکتا ہے۔ اس صورت میں، طریقہ کار ایک مختص رقم کے ساتھ ختم ہو سکتا ہے جس میں حسد کے چکر ہوتے ہیں۔ ان چکروں کو سائیکل کے ساتھ بنڈلوں کو منتقل کرکے ہٹایا جا سکتا ہے، جیسا کہ حسد گراف کے طریقہ کار میں ہوتا ہے۔ اس سے افادیت کی کل رقم میں سختی سے اضافہ ہوتا ہے۔ لہذا، تکرار کی ایک محدود تعداد کے بعد، ایک زیادہ سے زیادہ مختص رقم مل جائے گی، اور حسد سے پاک مختص کرنے کے لیے طریقہ کار اوپر کی طرح جاری رہ سکتا ہے۔ معاوضے کا طریقہ کار کچھ شراکت داروں سے منفی ادائیگی وصول کر سکتا ہے (یعنی شراکت داروں کو مثبت رقم دینا)۔ مصنفین کا کہنا ہے: "ہم اس امکان کو روکتے نہیں ہیں کہ کسی فرد کو دوسرے سامان کا ایک بنڈل لینے کے لیے ادائیگی کر سکتے ہیں۔ منصفانہ تقسیم کے تناظر میں، ہمیں یہ مسئلہ بالکل نہیں لگتا۔ درحقیقت، اگر کوئی گروپ اپنے کسی بھی ممبر کو خارج نہیں کرنا چاہتا ہے، تو اس کی کوئی وجہ نہیں ہے کہ گروپ کو کسی ممبر کو ناپسندیدہ بنڈل حاصل کرنے کے لیے سبسڈی نہیں دینی چاہیے۔ مزید برآں، اہلیت کی ضرورت اس بات کی ضمانت دیتی ہے کہ سبسڈی دینا کبھی بھی کسی کھلاڑی کی تقسیم کی جانے والی اشیاء کے مکمل سیٹ کی ناکافی تشخیص کا نتیجہ نہیں ہوتا ہے۔ کم از کم سبسڈی کے طریقہ کار کچھ کام یہ فرض کرتے ہیں کہ ایک خیر خواہ تیسرا فریق مختص رقم کو سبسڈی دینے کے لیے تیار ہے، لیکن حسد کی آزادی کے تابع سبسڈی کی رقم کو کم کرنا چاہتا ہے۔ اس مسئلے کو کم از کم سبسڈی حسد سے پاک الاٹمنٹ کہا جاتا ہے۔ ہالپرن اور شاہ عام آئٹم الاٹمنٹ کی ترتیب میں سبسڈی کو کم کرنے کا مطالعہ کرتے ہیں۔ وہ دو معاملات پر غور کرتے ہیں: مختص رقم پیشگی دی جاتی ہے۔ اس صورت میں، یہ "حسد سے پاک" ہے اگر اور صرف اس صورت میں جب یہ ایجنٹوں کو اپنے بنڈلوں کی تمام دوبارہ تفویض میں افادیت کے مجموعے کو زیادہ سے زیادہ کرتا ہے، اگر اور صرف اس صورت میں جب اس کے حسد گراف میں کوئی چکر نہ ہو۔ کم از کم سبسڈی کے ساتھ حسد سے پاک قیمت کا حساب مضبوط کثیر الجہتی وقت میں لگایا جا سکتا ہے، وزن والے حسد گراف کی تعمیر کرکے اور ہر ایجنٹ i کو، i سے نکلنے والے راستے کے زیادہ سے زیادہ وزن کے برابر قیمت دے کر۔ ہر راستے کا وزن زیادہ سے زیادہ m اصطلاحات کا مجموعہ ہوتا ہے، جن میں سے ہر ایک کسی چیز کے لیے کسی ایجنٹ کی قیمت ہوتی ہے۔ خاص طور پر، اگر ہر ایجنٹ کے لیے ہر چیز کی قیمت زیادہ سے زیادہ V ہے، تو ہر راستے کا وزن زیادہ سے زیادہ mV ہے۔ چونکہ ہم ہمیشہ قیمتوں کو اس طرح کم کر سکتے ہیں کہ ایک ایجنٹ کو صفر سبسڈی ملے، اس کے نتیجے میں ہمیشہ زیادہ سے زیادہ (این-1) ایم وی کی سبسڈی کے ساتھ حسد سے پاک مختص ہوتا ہے۔ یہ سبسڈی ضروری ہو سکتی ہے، مثال کے طور پر جب تمام اشیا ایک جیسی ہوں اور ایک ایجنٹ کو وہ سب مل جائیں۔ الاٹمنٹ کا انتخاب کیا جا سکتا ہے۔ اس صورت میں، (n-1) V کی سبسڈی درج ذیل صورتوں میں کافی ہے: جب ایجنٹوں کی قیمت بائنری (0 یا 1) ہو۔ پھر، کسی بھی زیادہ سے زیادہ پروڈکٹ الاٹمنٹ یا لیکسیمین زیادہ سے زیادہ الاٹمنٹ کے لیے زیادہ سے زیادہ (n-1) V سبسڈی کی ضرورت ہوتی ہے، اور یہ کثیر الجہتی وقت میں مل سکتی ہے۔ ای ایف حاصل کرنے کے لیے درکار کم از کم سبسڈی کا حساب لگانا، حسد سے پاک مختص رقم کے وجود کو چیک کرنے کے لیے ٹورنگ کے مساوی ہے، جو کہ غیر فضول مختص رقم تک محدود ہونے پر این پی مشکل ہوتا ہے۔ جب تمام ایجنٹوں کی ایک جیسی اضافی قیمت ہوتی ہے۔ پھر، ہر الاٹمنٹ حسد سے پاک ہوتی ہے۔ ایک مختص رقم جس کے لیے زیادہ سے زیادہ (n-1) V سبسڈی کی ضرورت ہوتی ہے، کثیر الجہتی وقت میں مل سکتی ہے۔ الاٹمنٹ سبسڈی کو کم سے کم کرتی ہے اگر یہ کسی بھی ایجنٹ کے لیے زیادہ سے زیادہ افادیت کو کم سے کم کرتی ہے۔ اس طرح کے الاٹمنٹ کا حساب لگانا این پی-ہارڈ ہے، اور اسے میکس پروڈکٹ الگورتھم کے ذریعے حل کیا جا سکتا ہے۔ جب دو ایجنٹ ہوتے ہیں، تو ایک مخصوص ایجنٹ کے آرڈر کے ساتھ راؤنڈ رابن آئٹم الاٹمنٹ میں ایک ایسی مختص رقم ملتی ہے جو زیادہ سے زیادہ وی پر سبسڈی کے ساتھ حسد سے پاک ہوتی ہے۔ برسٹل، ڈپل، نارائن، سوزوکی اور ویٹا مطلوبہ سبسڈی پر اوپری حدود کو بہتر بناتے ہیں: اضافی قیمتوں کے ساتھ، زیادہ سے زیادہ وی فی ایجنٹ، اور عام طور پر زیادہ سے زیادہ (این-1) وی کی سبسڈی ہمیشہ کافی ہوتی ہے۔ مزید برآں، اس حد کو حاصل کرنے کے لیے ایک مختص رقم ہے جو ای ایف 1 اور متوازن بھی ہے (مختص شدہ بنڈلوں کی بنیادی خصوصیات زیادہ سے زیادہ ایک چیز سے مختلف ہوتی ہیں)۔ اس کا حساب کثیر الجہتی وقت میں ایک سادہ الگورتھم کے ذریعے کیا جا سکتا ہے: بار بار ایجنٹوں-آبجیکٹ کے دو طرفہ گراف میں زیادہ سے زیادہ وزن کا ملاپ تلاش کریں۔ عام مونوٹون ویلیوایشن کے ساتھ، فی ایجنٹ زیادہ سے زیادہ 2 (این-1) وی، اور زیادہ سے زیادہ او (این 2 وی) کی سبسڈی ہمیشہ کافی ہوتی ہے۔ خاص طور پر مطلوبہ سبسڈی کا انحصار اشیاء کی تعداد پر نہیں ہوتا ہے۔ اس حد کو حاصل کرنے والی مختص رقم کو ویلیو سوالات کا استعمال کرتے ہوئے کثیر الجہتی وقت میں شمار کیا جا سکتا ہے۔ کاراجینس اور آئیونیڈس سبسڈی کو کم سے کم کرنے کے کمپیوٹیشنل مسئلے کا مطالعہ کرتے ہیں: ایجنٹوں کی مستقل تعداد کے لیے، وہ ایک الگورتھم پیش کرتے ہیں جو کسی بھی مطلوبہ درستگی کے اندر سبسڈی کی کم سے کم رقم کا تخمینہ لگاتا ہے۔ کسی بھی ε> 0 کے لیے، اسے زیادہ سے زیادہ سبسڈی کے ساتھ مختص ملتا ہے، جہاں S وہ زیادہ سے زیادہ قیمت ہے جو ایک ایجنٹ تمام اشیاء کو تفویض کرتا ہے۔ الگورتھم متحرک پروگرامنگ کا استعمال کرتا ہے اور وقت پر چلتا ہے۔ متغیر تعداد میں ایجنٹوں کے لیے، ایک معمولی تخمینہ الگورتھم حاصل ہوتا ہے۔ تاہم، n سے آزاد ایک تخمینہ عنصر حاصل کرنا مشکل ہے: زیادہ سے زیادہ سبسڈی کے ساتھ مختص رقم کا حساب لگانا NP-مشکل ہے۔ ثبوت زیادہ سے زیادہ 3 جہتی مماثلت کے محدود ورژن سے کمی کے ذریعے ہے، جس میں ہر ورٹیکس بالکل دو بار ظاہر ہوتا ہے۔ نوٹ کریں کہ اگر ہر ایجنٹ سے ایک مقررہ رقم لی جاتی ہے تو سبسڈی کے ساتھ حسد سے پاک مختص رقم حسد سے پاک رہتی ہے۔ لہذا، ایسی مختص رقم کو تلاش کرنے کے لیے اسی طرح کے طریقے استعمال کیے جا سکتے ہیں جن پر سبسڈی نہیں دی جاتی ہے: ہر ایجنٹ سے اوسط ادائیگی وصول کرنے سے حسد سے پاک مختص رقم حاصل ہوتی ہے جو بجٹ میں متوازن بھی ہوتی ہے۔ سبسڈی کو کم کرنا کسی بھی انفرادی ایجنٹ کو ادا کی جانے والی زیادہ سے زیادہ رقم کو کم کرنے کے مترادف ہے۔ منفی سبسڈی (ٹیکس) کا استعمال بھی ممکن ہے، جبکہ تمام ایجنٹوں کو ادا کرنے والی کل رقم کو کم سے کم کیا جائے۔ اضافی طریقہ کار الکن، ڈیمانج اور گیل سے پتہ چلتا ہے کہ جب رقم کافی زیادہ ہوتی ہے تو حسد سے پاک مختص ہمیشہ موجود رہتا ہے۔ یہ تب بھی درست ہے جب اشیاء کی قدر منفی ہو سکتی ہے۔ میرٹنز، پوٹرس اور ریجنیئرز قدروں پر بہت ہلکے مفروضوں کے تحت حسد سے پاک اور پیریٹو بہترین مختص کے وجود کو ثابت کرتے ہیں (ضروری نہیں کہ نیم لکیری ہو)۔ کیوالو حسد کی آزادی، متناسبیت، اور کارکردگی (فلاح و بہبود) کے روایتی بائنری معیار کو 0 اور 1 کے درمیان ڈگری کے اقدامات کے لیے عام کرتا ہے۔ کینونکل فیئر ڈویژن کی ترتیبات میں، کسی بھی مختص طور پر موثر میکانزم کے تحت بدترین صورت میں فلاح و بہبود کی شرح 0 ہے اور عدم تناسب کی شرح 1 ہے ؛ دوسرے الفاظ میں، بدترین صورت میں نتائج ہر ممکن حد تک خراب ہوتے ہیں۔ وہ ایک ایسے طریقہ کار کی تلاش کرتا ہے جو منصفانہ تقسیم کی ترتیبات کے میدان میں اعلی فلاح و بہبود، کم حسد، اور توقع میں کم عدم تناسب حاصل کرے۔ وی سی جی میکانزم ایک تسلی بخش امیدوار نہیں ہے، لیکن بیلی اور کیوالو کا دوبارہ تقسیم کا طریقہ کار ہے۔ متعلقہ مسائل حسد سے پاک قیمتوں کا تعین خریداروں کو اشیاء فروخت کرتے وقت، ادائیگیوں کی رقم پہلے سے طے نہیں کی جاتی ہے، اور اس کا مقصد یا تو بیچنے والے کی آمدنی، یا سماجی بہبود کو زیادہ سے زیادہ کرنا ہے، جو حسد کی آزادی کے تابع ہے۔ مزید برآں، اشیاء کی تعداد ایجنٹوں کی تعداد سے مختلف ہو سکتی ہے، اور کچھ اشیاء کو پھینک دیا جا سکتا ہے۔ اسے حسد سے پاک قیمتوں کا مسئلہ کہا جاتا ہے۔ کثیر جہتی مقاصد اکثر، انصاف کے علاوہ کچھ دوسرے مقاصد حاصل کرنے ہوتے ہیں۔ مثال کے طور پر، ایجنٹوں کو کام تفویض کرتے وقت، حسد سے بچنے اور میک اسپین کو کم سے کم کرنے (-آخری ایجنٹ کا تکمیل کا وقت) دونوں کی ضرورت ہوتی ہے۔ موالم حسد کی آزادی کی ضمانت کے ساتھ اصلاح کے مسائل کے لیے ایک عمومی فریم ورک پیش کرتا ہے جو قدرتی طور پر مالیاتی ادائیگیوں کا استعمال کرتے ہوئے منصفانہ آئٹم کی تقسیم کو بڑھاتا ہے۔ عزیز کا مقصد مالیاتی منتقلی کا استعمال کرتے ہوئے ایک ایسی مختص رقم حاصل کرنا ہے جو حسد سے پاک اور مساوی دونوں ہو۔ وہ نہ صرف اضافی مثبت افادیت کا مطالعہ کرتا ہے، بلکہ کسی بھی اضافی افادیت کے لیے بھی، چاہے وہ مثبت ہو یا منفی: اضافی افادیت کے لیے، ایک کثیر الجہتی وقت کا الگورتھم ہے جو حسد-آزادی، مساوات، اور بجٹ کا توازن حاصل کرتا ہے (سبسڈی کے ساتھ بجٹ توازن کا تبادلہ کرنا آسان ہے)۔ اگر کوئی مختص رقم EFEQ-بدلنے کے قابل ہے، تو اسے EF + EQ بنانے کے لیے درکار کم از کم سبسڈی لکیری وقت میں مل سکتی ہے۔ ایسی مختص رقم تلاش کرنا جو کم از کم سبسڈی کے ساتھ ای ایف ای کیو-کنورٹ ایبل ہو، این پی-ہارڈ ہے، اور کسی مثبت عنصر کے اندر اس کا تخمینہ نہیں لگایا جا سکتا۔ یہ صرف اس وجہ سے ہے کہ ای ایف الاٹمنٹ (جس کے لیے 0 سبسڈی کی ضرورت ہوتی ہے) کے وجود کی جانچ کرنا این پی-ہارڈ ہے۔ زیادہ سے زیادہ (این-1) ایم وی کی سبسڈی ہمیشہ کافی ہوتی ہے، اور ضروری ہو سکتی ہے کہ الاٹمنٹ دی جائے یا نہ دی جائے۔ حسد سے پاک آئٹم الاٹمنٹ-مالیاتی منتقلی کے بغیر ترتیب بھی دیکھیں۔ حوالہ جات منصفانہ آئٹم کی تقسیم