Welfare maximization
فلاح و بہبود کا زیادہ سے زیادہ مسئلہ ایک اصلاح کا مسئلہ ہے جس کا مطالعہ معاشیات اور کمپیوٹر سائنس میں کیا جاتا ہے۔ اس کا مقصد مختلف یوٹیلیٹی افعال والے ایجنٹوں کے درمیان آئٹمز کے ایک سیٹ کو تقسیم کرنا ہے، جیسے کہ فلاح و بہبود-جسے ایجنٹوں کی افادیت کے مجموعے کے طور پر بیان کیا گیا ہے-جتنا ممکن ہو اتنا زیادہ ہو۔ دوسرے لفظوں میں، مقصد مفید اصول کو مطمئن کرنے والی آئٹم الاٹمنٹ تلاش کرنا ہے۔ مشترکہ نیلامی کے تناظر میں ایک مساوی مسئلہ کو فاتح کے تعین کا مسئلہ کہا جاتا ہے۔ اس تناظر میں، ہر ایجنٹ آئٹمز کے سیٹوں پر بولیوں کی ایک فہرست پیش کرتا ہے، اور مقصد یہ طے کرنا ہے کہ کون سی بولی یا بولیاں جیتنی چاہئیں، اس طرح کہ جیتنے والی بولیوں کا مجموعہ زیادہ سے زیادہ ہو۔ تعریف m آئٹمز کا ایک سیٹ M ہے، اور n ایجنٹوں کا ایک سیٹ N ہے۔ N میں ہر ایجنٹ i کا یوٹیلیٹی فنکشن ہوتا ہے۔ فنکشن آئٹمز کے ہر ممکنہ ذیلی سیٹ کو حقیقی قدر تفویض کرتا ہے۔ عام طور پر یہ فرض کیا جاتا ہے کہ یوٹیلیٹی افعال مونوٹون سیٹ افعال ہیں، یعنی اس کا مطلب ہے۔ یہ بھی فرض کیا جاتا ہے۔ یکسانیت کے ساتھ، اس کا مطلب یہ ہے کہ تمام افادیت غیر منفی ہیں۔ الاٹمنٹ آئٹمز کی n جداگانہ ذیلی سیٹوں میں ایک ترتیب شدہ تقسیم ہے، ایک ذیلی سیٹ فی ایجنٹ، اس طرح ظاہر کیا جاتا ہے کہ۔ مختص کی فلاح و بہبود ایجنٹوں کی افادیت کا مجموعہ ہے: فلاح و بہبود کو زیادہ سے زیادہ کرنے کا مسئلہ یہ ہے کہ: ایک مختص X تلاش کریں جو W (X) کو زیادہ سے زیادہ کرے۔ فلاح و بہبود کے زیادہ سے زیادہ مسئلے کی بہت سی قسمیں ہیں، جو اس بات پر منحصر ہیں کہ یوٹیلیٹی افعال کی اجازت کس قسم کی ہے، الگورتھم کس طرح یوٹیلیٹی افعال تک رسائی حاصل کر سکتا ہے، اور کیا اجازت شدہ مختص پر اضافی رکاوٹیں ہیں۔ اضافی ایجنٹ ایک اضافی ایجنٹ کا ایک یوٹیلیٹی فنکشن ہوتا ہے جو ایک اضافی سیٹ فنکشن ہوتا ہے: ہر اضافی ایجنٹ i اور آئٹم j کے لیے، ایک قدر ہوتی ہے، جیسے کہ آئٹمز کے ہر سیٹ Z کے لیے۔ جب تمام ایجنٹ اضافی ہوتے ہیں، تو فلاح و بہبود کو زیادہ سے زیادہ ایک سادہ کثیر الجہتی وقت کے الگورتھم کے ذریعے کیا جا سکتا ہے: ہر آئٹم جے کو ایک ایسے ایجنٹ کو دیں جس کے لیے زیادہ سے زیادہ ہو (من مانی طور پر تعلقات توڑنا)۔ الاٹمنٹ پر اضافی رکاوٹیں ہونے پر مسئلہ مزید مشکل ہو جاتا ہے۔ انصاف کی رکاوٹیں کوئی بھی ان تمام مختص رقم کے درمیان فلاح و بہبود کو زیادہ سے زیادہ کرنا چاہتا ہے جو منصفانہ ہیں، مثال کے طور پر، ایک آئٹم تک حسد سے پاک (EF1)، ایک آئٹم تک متناسب (PROP1)، یا ایک آئٹم تک مساوی (EQ1)۔ جب n متغیر ہوتا ہے تو یہ مسئلہ مضبوطی سے NP-سخت ہوتا ہے۔ کسی بھی فکسڈ n ≤ 2 کے لیے، مسئلہ کمزور NP-سخت ہوتا ہے، اور اس میں متحرک پروگرامنگ پر مبنی ایک فرضی کثیر الجہتی ٹائم الگورتھم ہوتا ہے۔ n = 2 کے لیے، مسئلہ میں مکمل طور پر کثیر الجہتی وقت کا تخمینہ اسکیم ہے۔ کثیر الجہتی وقت میں اس مسئلے کو حل کرنے کے لیے الگورتھم موجود ہیں جب ایجنٹ کی چند اقسام، آئٹم کی چند اقسام یا قدر کی چھوٹی سطحیں ہوتی ہیں۔ اس مسئلے کو کثیر الجہتی وقت میں بھی حل کیا جاسکتا ہے جب ایجنٹوں کی اضافی افادیت بائنری ہوتی ہے (ہر آئٹم کی قیمت یا تو 0 یا 1 ہوتی ہے)، نیز افادیت کی ایک زیادہ عام کلاس کے لیے جسے عام بائنری کہا جاتا ہے۔ میٹرائڈ کی رکاوٹیں مختص کرنے میں ایک اور رکاوٹ یہ ہے کہ بنڈل میٹرائڈ کے آزاد سیٹ ہونے چاہئیں۔ مثال کے طور پر، ہر بنڈل میں زیادہ سے زیادہ k آئٹمز ہونے چاہئیں، جہاں k ایک فکسڈ انٹیجر ہے (یہ ایک یکساں میٹرائڈ سے مطابقت رکھتا ہے)۔ یا، اشیاء کو زمروں میں تقسیم کیا جا سکتا ہے، اور ہر بنڈل میں ہر زمرہ سی سے زیادہ سے زیادہ کے سی آئٹمز ہونے چاہئیں (یہ پارٹیشن میٹرائڈ سے مطابقت رکھتا ہے)۔ عام طور پر، ہر ایجنٹ کے لیے ایک مختلف میٹرائڈ ہو سکتا ہے، اور الاٹمنٹ میں ہر ایجنٹ کو ایک ذیلی سیٹ Xi دینا چاہیے جو ان کے اپنے میٹرائڈ کا ایک آزاد سیٹ ہے۔ متنوع میٹرائڈ رکاوٹوں کے تحت اضافی افادیت کے ساتھ فلاح و بہبود کو زیادہ سے زیادہ کثیر الجہتی وقت میں کیا جا سکتا ہے، وزن والے میٹرائڈ چوراہے کے مسئلے کو کم کرکے۔ مجموعی متبادل ایجنٹ مجموعی متبادل افادیت اضافی افادیت سے زیادہ عام ہیں۔ مجموعی متبادل ایجنٹوں کے ساتھ فلاح و بہبود کو زیادہ سے زیادہ کثیر الجہتی وقت میں کیا جا سکتا ہے۔ اس کی وجہ یہ ہے کہ، مجموعی متبادل ایجنٹوں کے ساتھ، ایک والراسیئن توازن ہمیشہ موجود رہتا ہے، اور یہ افادیت کے مجموعے کو زیادہ سے زیادہ کرتا ہے۔ والراسیائی توازن کثیر الجہتی وقت میں پایا جا سکتا ہے۔ سب ماڈیولر ایجنٹ ایک سب ماڈیولر ایجنٹ میں ایک یوٹیلیٹی فنکشن ہوتا ہے جو ایک سب ماڈیولر سیٹ فنکشن ہوتا ہے۔ اس کا مطلب یہ ہے کہ ایجنٹ کی افادیت کم ہو رہی ہے۔ سب ماڈیولر یوٹیلیٹیز مجموعی متبادل یوٹیلیٹیز سے زیادہ عام ہیں۔ سب ماڈیولر ایجنٹوں کے ساتھ سختی کی فلاح و بہبود کو زیادہ سے زیادہ کرنا این پی-ہارڈ ہے۔ مزید برآں، اس کا تخمینہ (1-1/e) ≈ 0.632 سے بہتر عنصر سے نہیں لگایا جا سکتا جب تک کہ P = NP نہ ہو۔ مزید برآں، (1-1/e) سے بہتر تخمینہ کے لیے قدر اوریکل کے لیے متغیر تعداد میں سوالات کی ضرورت ہوگی، قطع نظر اس کے کہ P = NP ہے۔ لالچی الگورتھم زیادہ سے زیادہ فلاح و بہبود کا تخمینہ مندرجہ ذیل کثیر الجہتی وقت لالچی الگورتھم سے لگایا جا سکتا ہے: X1 = X2 =. = Xn = خالی شروع کریں۔ ہر آئٹم جی کے لیے (صوابدیدی ترتیب میں): حساب لگائیں، ہر ایجین آئی کے لیے، جی کے لیے اس کی معمولی افادیت، جس کی تعریف اس طرح کی گئی ہے: یو آئی (زی + جی)-یو آئی (زی)۔ آئٹم جی کسی ایسے ایجنٹ کو دیں جس کی سب سے بڑی معمولی افادیت ہو۔ لیمن، لیمن اور نیسان ثابت کرتے ہیں کہ لالچی الگورتھم 1/2 فیکٹر کا تخمینہ ڈھونڈتا ہے (وہ نوٹ کرتے ہیں کہ یہ نتیجہ فشر، نیم ہاؤزر اور وولسی کے نتیجے سے ملتا ہے جو کہ میٹرایڈ پر ایک واحد سب ماڈیولر ویلیوایشن کو زیادہ سے زیادہ کرنے کے حوالے سے ہے)۔ ثبوت کا خیال مندرجہ ذیل ہے۔ فرض کریں کہ الگورتھم کسی آئٹم g کو کسی ایجنٹ i کے لیے مختص کرتا ہے۔ یہ فلاح و بہبود میں کچھ رقم v میں حصہ ڈالتا ہے، جو اس وقت i کے لیے g کی معمولی افادیت ہے۔ فرض کریں کہ، زیادہ سے زیادہ حل میں، g کسی دوسرے ایجنٹ کو دیا جانا چاہیے، جیسے کہ k۔ غور کریں کہ اگر ہم g کو i سے k پر منتقل کرتے ہیں تو فلاح و بہبود کیسے بدلتی ہے: k کی افادیت اس کی g کی معمولی افادیت سے بڑھ جاتی ہے، جو زیادہ سے زیادہ v لالچی انتخاب سے ہوتی ہے۔ i کے بقیہ بنڈل کی معمولی افادیت میں زیادہ سے زیادہ v کا اضافہ ہوتا ہے۔ یہ سب ماڈیولرٹی سے ہوتا ہے: g کی معمولی افادیت، جب باقی بنڈل میں شامل کی جاتی ہے، جب الگورتھم اس پر کارروائی کرتا ہے تو اس کی معمولی افادیت سے زیادہ نہیں ہو سکتی۔ لہذا، الگورتھم کی فلاح و بہبود میں v کی ہر شراکت کے لیے، زیادہ سے زیادہ فلاح و بہبود میں ممکنہ شراکت زیادہ سے زیادہ 2v ہو سکتی ہے۔ لہذا، بہترین فلاح و بہبود الگورتھم کی فلاح و بہبود سے زیادہ سے زیادہ 2 گنا زیادہ ہے۔ لالچی الگورتھم کے لیے 2 کا عنصر سخت ہے۔ مثال کے طور پر، فرض کریں کہ دو آئٹمز x، y ہیں اور ویلیوایشن یہ ہیں: بہترین الاٹمنٹ ایلس: {y}، جارج: {x}، ویلفیئر 2 کے ساتھ ہے۔ لیکن اگر لالچی الگورتھم پہلے x مختص کرتا ہے، تو یہ اسے ایلس کو مختص کر سکتا ہے۔ پھر، اس بات سے قطع نظر کہ Y کیسے مختص کیا گیا ہے، فلاح و بہبود صرف 1 ہے۔ ویلیو اوریکل کا استعمال کرتے ہوئے الگورتھم ایک ویلیو اوریکل ایک اوریکل ہے جو آئٹمز کا ایک سیٹ دیتے ہوئے ایجنٹ کی ویلیو کو اس سیٹ پر واپس کرتا ہے۔ اس ماڈل میں: ڈوبزنسکی اور شیپیرا ایک پولی ٹائم-اپروکسیمیشن الگورتھم پیش کرتے ہیں، اور اس خاص معاملے کے لیے ایک (1-1/e) ≈ 0.632-approximation الگورتھم پیش کرتے ہیں جس میں ایجنٹوں کی افادیت سیٹ کوریج افعال ہیں۔ وانڈرک اور کیلنسکو، چیکوری، پال اور وانڈرک ایک بے ترتیب پولی ٹائم الگورتھم پیش کرتے ہیں جو اعلی امکان کے ساتھ (1-1/ای)-مطابقت تلاش کرتا ہے۔ ان کا الگورتھم ایک مسلسل گریڈی الگورتھم کا استعمال کرتا ہے-ایک الگورتھم جو ایک فریکشنل بنڈل (ایک بنڈل جس میں ہر آئٹم جے کا ایک فریکشن پی جے ہوتا ہے) کو لالچی سمت میں پھیلاتا ہے (گریڈینٹ نزول کی طرح)۔ ان کے الگورتھم کو فریکشنل بنڈلوں کی قیمت کا حساب لگانے کی ضرورت ہے، جس کی تعریف بنڈل کی متوقع قیمت کے طور پر کی گئی ہے جب ہر آئٹم جے کو امکان pj کے ساتھ آزادانہ طور پر منتخب کیا جاتا ہے۔ عام طور پر، فریکشنل بنڈل کی قیمت کا حساب لگانے کے لیے ویلیو اوریکل پر 2m کالز کی ضرورت پڑ سکتی ہے ؛ تاہم، بے ترتیب نمونے لے کر اس کا حساب تقریبا اعلی امکان کے ساتھ لگایا جا سکتا ہے۔ یہ ایک بے ترتیب الگورتھم کی طرف جاتا ہے جو اعلی امکان کے ساتھ (1-1/e)-مطابقت حاصل کرتا ہے۔ ایسے معاملات میں جب فریکشنل بنڈلوں کا مؤثر طریقے سے جائزہ لیا جا سکتا ہے (جیسے۔ جب یوٹیلیٹی فنکشن سیٹ کوریج فنکشن ہوتے ہیں)، تو الگورتھم کو تعیناتی بنایا جا سکتا ہے۔ وہ ایک کھلے مسئلے کے طور پر ذکر کرتے ہیں، چاہے عام سب ماڈیولر افعال کے لیے کوئی تعیناتی پولی ٹائم (1-1/ای)-اپروکسیمیشن الگورتھم ہو۔ فلاحی زیادہ سے زیادہ مسئلہ (n مختلف ذیلی ماڈیولر افعال کے ساتھ) کو ایک واحد ذیلی ماڈیولر سیٹ فنکشن کو زیادہ سے زیادہ کرنے کے مسئلے تک کم کیا جا سکتا ہے جو کہ میٹرائڈ رکاوٹ کے تابع ہے: m آئٹمز اور n ایجنٹس کے ساتھ ایک مثال دی گئی ہے، m * n (ایجنٹ، آئٹم) جوڑوں کے ساتھ ایک مثال بنائیں، جہاں ہر جوڑا کسی ایجنٹ کو کسی آئٹم کی تفویض کی نمائندگی کرتا ہے۔ ایک واحد فنکشن بنائیں جو جوڑوں کے ہر سیٹ کو، متعلقہ مختص کی کل فلاح و بہبود تفویض کرتا ہے۔ یہ دکھایا جا سکتا ہے کہ، اگر تمام افادیت ذیلی ماڈیولر ہیں، تو یہ فلاحی فنکشن بھی ذیلی ماڈیولر ہے۔ اس فنکشن کو پارٹیشن میٹرائڈ رکاوٹ کے تحت زیادہ سے زیادہ کیا جانا چاہیے، اس بات کو یقینی بناتے ہوئے کہ ہر آئٹم کو زیادہ سے زیادہ ایک ایجنٹ کے لیے مختص کیا گیا ہے۔ ڈیمانڈ اوریکل کا استعمال کرتے ہوئے الگورتھم ایجنٹوں کی افادیت تک رسائی حاصل کرنے کا ایک اور طریقہ ڈیمانڈ اوریکل کا استعمال کرنا ہے (ایک اوریکل جو، قیمت ویکٹر کو دیکھتے ہوئے، ایجنٹ کا سب سے مطلوبہ بنڈل واپس کرتا ہے)۔ اس ماڈل میں: ڈوبزنسکی اور شیپیرا ایک پولی ٹائم (1-1/ای)-اپروکسیمیشن الگورتھم پیش کرتے ہیں۔ فیج اور وانڈرک کچھ چھوٹے مثبت ε کے لیے اسے (1-1/e + ε) تک بہتر بناتے ہیں (یہ مندرجہ بالا سختی کے نتیجے سے متصادم نہیں ہے، کیونکہ سختی کا نتیجہ صرف ایک قدر اوریکل کا استعمال کرتا ہے۔ سختی کی مثالوں میں، ڈیمانڈ اوریکل کو خود ہی تیزی سے بہت سے سوالات کی ضرورت ہوگی)۔ ذیلی اضافی ایجنٹ جب ایجنٹوں کی افادیت ذیلی اضافی سیٹ فنکشن ہوتے ہیں (ذیلی ماڈیولر سے زیادہ عام)، تو ایک تخمینہ کے لیے قدر کے سوالات کی ایک متغیر تعداد کی ضرورت ہوگی۔ فیج اس مسئلے کے ایل پی نرمی کے لیے کسی بھی فریکشنل حل کو کم از کم 1/2 فریکشنل حل کی قدر کے ساتھ ایک قابل عمل حل کے لیے گول کرنے کا ایک طریقہ پیش کرتا ہے۔ یہ عام ذیلی اضافی ایجنٹوں کے لیے 1/2-ضمیمہ دیتا ہے، اور (1-1/ای) جزوی طور پر ذیلی اضافی قیمتوں کے خصوصی معاملے کے لیے-ضمیمہ دیتا ہے۔ سپر ایڈیٹیو ایجنٹ جب ایجنٹوں کی افادیت سپر ایڈیٹیو سیٹ فنکشن ہوتے ہیں (سپر ماڈیولر سے زیادہ عام)، تو ایک اندازے کے لیے قدر کے سوالات کی ایک سپر کثیر تعداد کی ضرورت ہوگی۔ ایک ذہن رکھنے والا ایجنٹ ایک ذہن رکھنے والا ایجنٹ صرف اشیاء کا ایک مخصوص مجموعہ چاہتا ہے۔ ہر ایک ذہن رکھنے والے ایجنٹ i کے لیے، ایک ڈیمانڈڈ سیٹ Di ہے، اور ایک ویلیو Vi> 0 ہے، جیسے کہ۔ یعنی ایجنٹ کو ایک فکسڈ پوزیٹیو یوٹیلیٹی صرف اس صورت میں ملتی ہے جب ان کے بنڈل میں ان کا مطلوبہ سیٹ موجود ہو۔ واحد ذہن رکھنے والے ایجنٹوں کے ساتھ فلاح و بہبود کو زیادہ سے زیادہ کرنا این پی-سخت ہے یہاں تک کہ جب سب کے لیے۔ اس صورت میں، مسئلہ سیٹ پیکنگ کے برابر ہے، جسے این پی ہارڈ کہا جاتا ہے۔ مزید برآں، کسی بھی مستقل عنصر کے اندر اس کا تخمینہ نہیں لگایا جا سکتا (سب ماڈیولر ایجنٹوں کے معاملے کے برعکس)۔ سب سے مشہور الگورتھم ایک عنصر کے اندر اس کا تخمینہ لگاتا ہے۔ جنرل ایجنٹ جب ایجنٹوں کے من مانی مونوٹون یوٹیلیٹی افعال (بشمول تکمیلی اشیاء) ہو سکتے ہیں، تو کسی بھی عنصر کے اندر فلاح و بہبود کو زیادہ سے زیادہ کرنا مشکل ہوتا ہے۔ تاہم، ریاستی خلائی تلاش پر مبنی الگورتھم موجود ہیں جو عملی طور پر بہت اچھی طرح سے کام کرتے ہیں۔ یوٹیلیٹی میکسمائزیشن مسئلہ حوالہ جات آپٹیمائزیشن الگورتھم اور طریقے بھی دیکھیں۔