Welfare maximization
কল্যাণ সর্বাধিককরণ সমস্যা হল অর্থনীতি এবং কম্পিউটার বিজ্ঞানে অধ্যয়নরত একটি অনুকূলকরণ সমস্যা। এর লক্ষ্য হল বিভিন্ন ইউটিলিটি ফাংশন সহ এজেন্টদের মধ্যে আইটেমগুলির একটি সেট ভাগ করা, যাতে কল্যাণ-এজেন্টদের উপযোগিতার সমষ্টি হিসাবে সংজ্ঞায়িত-যতটা সম্ভব বেশি হয়। অন্য কথায়, লক্ষ্য হল উপযোগবাদী নিয়মকে সন্তুষ্ট করে এমন একটি আইটেম বরাদ্দ খুঁজে বের করা। যৌথ নিলামের প্রেক্ষাপটে একটি সমতুল্য সমস্যাকে বিজয়ী নির্ধারণ সমস্যা বলা হয়। এই প্রসঙ্গে, প্রতিটি প্রতিনিধি পণ্যের সেটগুলিতে দরপত্রের একটি তালিকা জমা দেয় এবং লক্ষ্য হল কোন দরপত্র বা দরপত্র জিততে হবে তা নির্ধারণ করা, যাতে বিজয়ী দরপত্রের সমষ্টি সর্বাধিক হয়। সংজ্ঞা এম আইটেমের একটি সেট এম এবং এন এজেন্টের একটি সেট এন রয়েছে। N-এ প্রতিটি এজেন্ট i-এর একটি ইউটিলিটি ফাংশন রয়েছে। ফাংশনটি আইটেমের প্রতিটি সম্ভাব্য উপসেটকে একটি বাস্তব মান বরাদ্দ করে। এটি সাধারণত ধরে নেওয়া হয় যে ইউটিলিটি ফাংশনগুলি মনোটোন সেট ফাংশন, অর্থাৎ, বোঝায়। এটাও অনুমান করা হয়। একঘেয়েমি সহ, এটি বোঝায় যে সমস্ত উপযোগিতা অ-নেতিবাচক। বরাদ্দ হ 'ল আইটেমগুলিকে এন বিচ্ছিন্ন উপসেটে বিভক্ত করা, প্রতি এজেন্টের একটি উপসেট, এমনভাবে চিহ্নিত করা হয়, যাতে বরাদ্দের কল্যাণ হ' ল এজেন্টদের উপযোগিতার সমষ্টিঃ কল্যাণ সর্বাধিককরণ সমস্যাটি হলঃ একটি বরাদ্দ এক্স খুঁজে বের করুন যা ডাব্লু (এক্স) কে সর্বাধিক করে। ওয়েলফেয়ার ম্যাক্সিমাইজেশন সমস্যার অনেকগুলি রূপ রয়েছে, যা নির্ভর করে অনুমোদিত ইউটিলিটি ফাংশনগুলির ধরন, অ্যালগরিদম যেভাবে ইউটিলিটি ফাংশনগুলি অ্যাক্সেস করতে পারে এবং অনুমোদিত বরাদ্দের উপর অতিরিক্ত সীমাবদ্ধতা রয়েছে কিনা তার উপর। অ্যাডিটিভ এজেন্ট একটি অ্যাডিটিভ এজেন্টের একটি ইউটিলিটি ফাংশন থাকে যা একটি অ্যাডিটিভ সেট ফাংশনঃ প্রতিটি অ্যাডিটিভ এজেন্ট i এবং আইটেম j-এর জন্য একটি মান থাকে, যেমন প্রতিটি সেট Z আইটেমের জন্য। যখন সমস্ত এজেন্ট যোগাত্মক হয়, তখন একটি সাধারণ পলিনোমিয়াল-টাইম অ্যালগরিদম দ্বারা কল্যাণ সর্বাধিককরণ করা যেতে পারেঃ প্রতিটি আইটেমকে এমন একটি এজেন্টকে দিন যার জন্য সর্বাধিক (নির্বিচারে বন্ধন ভাঙা)। বরাদ্দের ক্ষেত্রে অতিরিক্ত সীমাবদ্ধতা থাকলে সমস্যাটি আরও চ্যালেঞ্জিং হয়ে ওঠে। ন্যায্যতার সীমাবদ্ধতাগুলি ন্যায্য সমস্ত বরাদ্দের মধ্যে কল্যাণকে সর্বাধিকতর করতে চাইতে পারে, উদাহরণস্বরূপ, একটি আইটেম (ইএফ 1) পর্যন্ত হিংসা-মুক্ত, একটি আইটেম (পিআরওপি 1) পর্যন্ত আনুপাতিক, বা একটি আইটেম (ইক্যু 1) পর্যন্ত ন্যায়সঙ্গত। এই সমস্যাটি দৃঢ়ভাবে এন. পি-হার্ড হয় যখন এন পরিবর্তনশীল হয়। যে কোনও স্থির n ≤ 2-এর জন্য, সমস্যাটি দুর্বলভাবে NP-কঠিন, এবং গতিশীল প্রোগ্রামিংয়ের উপর ভিত্তি করে একটি ছদ্ম-বহুপদী সময় অ্যালগরিদম রয়েছে। n = 2-এর জন্য, সমস্যার একটি সম্পূর্ণ বহুপদী-সময় আনুমানিক বিন্যাস রয়েছে। বহুপদী সময়ে এই সমস্যা সমাধানের জন্য অ্যালগরিদম রয়েছে যখন কয়েকটি এজেন্টের প্রকার, কয়েকটি আইটেমের প্রকার বা ছোট মানের স্তর থাকে। সমস্যাটি বহুপদী সময়েও সমাধান করা যেতে পারে যখন এজেন্টগুলির যোগাত্মক উপযোগগুলি বাইনারি হয় (প্রতিটি আইটেমের মান হয় 0 বা 1), পাশাপাশি সাধারণীকৃত বাইনারি নামে পরিচিত আরও সাধারণ শ্রেণীর উপযোগগুলির জন্য। ম্যাট্রয়েডের সীমাবদ্ধতা বরাদ্দের আরেকটি সীমাবদ্ধতা হল যে বান্ডিলগুলি অবশ্যই ম্যাট্রয়েডের স্বাধীন সেট হতে হবে। উদাহরণস্বরূপ, প্রতিটি বান্ডিলে সর্বাধিক কে আইটেম থাকতে হবে, যেখানে কে একটি নির্দিষ্ট পূর্ণসংখ্যা (এটি একটি অভিন্ন ম্যাট্রয়েডের সাথে মিলে যায়)। অথবা, আইটেমগুলি বিভাগগুলিতে বিভক্ত করা যেতে পারে এবং প্রতিটি বান্ডেলে প্রতিটি বিভাগ সি থেকে সর্বাধিক কে. সি আইটেম থাকতে হবে (এটি একটি পার্টিশন ম্যাট্রয়েডের সাথে মিলে যায়)। সাধারণভাবে, প্রতিটি এজেন্টের জন্য একটি আলাদা ম্যাট্রয়েড থাকতে পারে এবং বরাদ্দ অবশ্যই প্রতিটি এজেন্টকে একটি উপসেট জি দিতে হবে যা তাদের নিজস্ব ম্যাট্রয়েডের একটি স্বাধীন সেট। হেটেরোজিনিয়াস ম্যাট্রয়েড সীমাবদ্ধতার অধীনে অ্যাডিটিভ ইউটিলিটিগুলির সাথে কল্যাণ সর্বাধিককরণ বহুপদী সময়ে করা যেতে পারে, ওজনযুক্ত ম্যাট্রয়েড ছেদ সমস্যা হ্রাস করে। গ্রস-বিকল্প এজেন্ট গ্রস-বিকল্প ইউটিলিটিগুলি অ্যাডিটিভ ইউটিলিটিগুলির চেয়ে বেশি সাধারণ। পলিনোমিয়াল সময়ে মোট-বিকল্প এজেন্টগুলির সাথে কল্যাণ সর্বাধিককরণ করা যেতে পারে। এর কারণ হল, মোট-বিকল্প এজেন্টের সাথে, একটি ওয়ালরাসিয়ান ভারসাম্য সর্বদা বিদ্যমান থাকে এবং এটি উপযোগিতার যোগফলকে সর্বাধিক করে তোলে। বহুপদী সময়ে একটি ওয়ালরাসিয়ান ভারসাম্য পাওয়া যায়। সাব-মডুলার এজেন্ট একটি সাব-মডুলার এজেন্টের একটি ইউটিলিটি ফাংশন থাকে যা একটি সাব-মডুলার সেট ফাংশন। এর মানে হল যে এজেন্টের উপযোগিতা হ্রাস পেয়েছে। মোট-বিকল্প ইউটিলিটিগুলির তুলনায় সাব-মডুলার ইউটিলিটিগুলি বেশি সাধারণ। সাব-মডুলার এজেন্টগুলির সাথে কঠোরতা কল্যাণ সর্বাধিককরণ এনপি-হার্ড। উপরন্তু, এটি (1-1/ই) ≈ 0.632 এর চেয়ে ভাল একটি ফ্যাক্টরের সাথে আনুমানিক হতে পারে না যদি না পি = এনপি হয়। উপরন্তু, পি = এনপি যাই হোক না কেন, (1-1/ই) অনুমানের চেয়ে ভাল একটি মান ওরাকলে একটি সূচকীয় সংখ্যক প্রশ্নের প্রয়োজন হবে। লোভী অ্যালগরিদম সর্বাধিক কল্যাণকে নিম্নলিখিত বহুপদী-সময় লোভী অ্যালগরিদম দ্বারা আনুমানিক করা যেতে পারেঃ X1 = X2 = = Xn = খালি শুরু করুন। প্রতিটি আইটেমের জন্য জি (একটি নির্বিচারে ক্রমে): গণনা করুন, প্রতিটি এজেনের জন্য আই, জি-এর জন্য তার প্রান্তিক উপযোগিতা, হিসাবে সংজ্ঞায়িত করা হয়েছেঃ ইউআই (এক্সআই + জি)-ইউআই (এক্সআই)। সবচেয়ে বড় প্রান্তিক উপযোগিতা সহ কোনও এজেন্টকে আইটেম জি দিন। লেহম্যান, লেহম্যান এবং নিসান প্রমাণ করেছেন যে লোভী অ্যালগরিদম একটি 1/2-ফ্যাক্টর আনুমানিক খুঁজে পায় (তারা লক্ষ্য করেছেন যে এই ফলাফলটি ফিশার, নেমহাউসার এবং ওলসির একটি ম্যাট্রয়েডের উপর একক সাব-মডুলার মূল্যায়নের সর্বাধিককরণের ফলাফল থেকে অনুসরণ করে)। প্রমাণ ধারণাটি নিম্নরূপ। ধরুন অ্যালগরিদমটি কোনও এজেন্টকে একটি আইটেম জি বরাদ্দ করে। এটি কল্যাণে কিছু পরিমাণ v অবদান রাখে, যা সেই সময়ে i এর জন্য g এর প্রান্তিক উপযোগিতা। ধরুন, সর্বোত্তম সমাধানে, g অন্য এজেন্টকে দেওয়া উচিত, ধরুন k। বিবেচনা করুন কিভাবে কল্যাণ পরিবর্তিত হয় যদি আমরা g কে i থেকে k এ নিয়ে যাইঃ k এর উপযোগিতা তার প্রান্তিক উপযোগিতা দ্বারা বৃদ্ধি পায়, যা সর্বাধিক v দ্বারা লোভী নির্বাচন। আই-এর অবশিষ্ট বান্ডিলের প্রান্তিক উপযোগিতা সর্বাধিক ভি দ্বারা বৃদ্ধি পায়। এটি সাবমোডুলারিটি থেকে অনুসরণ করেঃ জি-এর প্রান্তিক উপযোগিতা, যখন অবশিষ্ট বান্ডিলের সাথে যোগ করা হয়, যখন অ্যালগরিদম এটি প্রক্রিয়া করে তখন তার প্রান্তিক উপযোগের চেয়ে বেশি হতে পারে না। সুতরাং, অ্যালগরিদম কল্যাণে v-এর প্রতিটি অবদানের জন্য, সর্বোত্তম কল্যাণে সম্ভাব্য অবদান সর্বাধিক 2v হতে পারে। অতএব, সর্বোত্তম কল্যাণ হল অ্যালগরিদম কল্যাণের সর্বাধিক 2 গুণ। লোভী অ্যালগরিদমের জন্য 2-এর ফ্যাক্টর শক্ত। উদাহরণস্বরূপ, ধরুন দুটি আইটেম x, y রয়েছে এবং মূল্যায়নগুলি হলঃ সর্বোত্তম বরাদ্দ হল অ্যালিসঃ {y}, জর্জঃ {x}, কল্যাণ 2 সহ। কিন্তু লোভী অ্যালগরিদম যদি প্রথমে x বরাদ্দ করে, তবে এটি অ্যালিসকে বরাদ্দ করতে পারে। তারপর, কিভাবে y বরাদ্দ করা হয় তা নির্বিশেষে, কল্যাণ শুধুমাত্র 1। একটি মান ওরাকল ব্যবহার করে অ্যালগরিদম একটি মান ওরাকল হল একটি ওরাকল যা, আইটেমগুলির একটি সেট দেওয়া হলে, এই সেটে এজেন্টের মান প্রদান করে। এই মডেলেঃ ডবজিনস্কি এবং শাপিরা একটি পলিটাইম-অ্যাপ্রোক্সিমেশন অ্যালগরিদম এবং বিশেষ ক্ষেত্রে একটি (1-1/ই) ≈ 0.632-approximation অ্যালগরিদম উপস্থাপন করেন যেখানে এজেন্টদের ইউটিলিটিগুলি সেট-কভারেজ ফাংশন। ভন্ড্রাক এবং ক্যালিনেস্কু, চেকুরি, পাল এবং ভন্ড্রাক একটি র্যান্ডমাইজড পলিটাইম অ্যালগরিদম উপস্থাপন করে যা উচ্চ সম্ভাবনার সাথে একটি (1-1/ই)-অনুমোদন খুঁজে পায়। তাদের অ্যালগরিদম একটি অবিচ্ছিন্ন-লোভী অ্যালগরিদম ব্যবহার করে-একটি অ্যালগরিদম যা একটি লোভী দিকে (গ্রেডিয়েন্ট ডিসেন্টের মতো) একটি ভগ্নাংশ বান্ডিল (একটি বান্ডিল যা প্রতিটি আইটেম জে-এর একটি ভগ্নাংশ পিজে ধারণ করে) প্রসারিত করে। তাদের অ্যালগরিদমকে ভগ্নাংশ বান্ডিলগুলির মান গণনা করতে হবে, প্রতিটি আইটেম জে সম্ভাব্যতা পিজে দিয়ে স্বাধীনভাবে নির্বাচিত হলে প্রাপ্ত বান্ডিলের প্রত্যাশিত মান হিসাবে সংজ্ঞায়িত করা হয়। সাধারণভাবে, একটি ভগ্নাংশ বান্ডিলের মান গণনা করার জন্য একটি মান ওরাকলে 2 মি কলের প্রয়োজন হতে পারে; তবে, র্যান্ডম স্যাম্পলিং দ্বারা এটি প্রায় উচ্চ সম্ভাবনার সাথে গণনা করা যেতে পারে। এটি একটি র্যান্ডমাইজড অ্যালগরিদমের দিকে পরিচালিত করে যা উচ্চ সম্ভাবনার সাথে একটি (1-1/ই)-অনুমোদন অর্জন করে। যখন ভগ্নাংশ বান্ডিলগুলি দক্ষতার সাথে মূল্যায়ন করা যেতে পারে (যেমন। যখন ইউটিলিটি ফাংশনগুলি সেট-কভারেজ ফাংশন হয়), তখন অ্যালগরিদমকে নির্ধারণমূলক করা যেতে পারে। তারা একটি উন্মুক্ত সমস্যা হিসাবে উল্লেখ করে, সাধারণ সাব-মডুলার ফাংশনের জন্য একটি নির্ধারক পলিটাইম (1-1/ই)-অ্যাপ্রোক্সিমেশন অ্যালগরিদম আছে কিনা। কল্যাণ সর্বাধিককরণ সমস্যা (বিভিন্ন উপ-মডুলার ফাংশন সহ) একটি ম্যাট্রয়েড সীমাবদ্ধতা সাপেক্ষে একটি একক উপ-মডুলার সেট ফাংশন সর্বাধিককরণের সমস্যায় হ্রাস করা যেতে পারেঃ এম আইটেম এবং এন এজেন্টের সাথে একটি উদাহরণ দেওয়া হলে, এম * এন (এজেন্ট, আইটেম) জোড়ার সাথে একটি উদাহরণ তৈরি করুন, যেখানে প্রতিটি জোড়া একটি এজেন্টকে একটি আইটেমের বরাদ্দকে উপস্থাপন করে। একটি একক ফাংশন তৈরি করুন যা জোড়ার প্রতিটি সেটকে সংশ্লিষ্ট বরাদ্দের মোট কল্যাণ নির্ধারণ করে। এটি দেখানো যেতে পারে যে, যদি সমস্ত ইউটিলিটিগুলি সাব-মডুলার হয়, তবে এই কল্যাণ ফাংশনটিও সাব-মডুলার। এই ফাংশনটি একটি পার্টিশন ম্যাট্রয়েড সীমাবদ্ধতা সাপেক্ষে সর্বাধিক করা উচিত, এটি নিশ্চিত করে যে প্রতিটি আইটেম সর্বাধিক একটি এজেন্টকে বরাদ্দ করা হয়েছে। ডিমান্ড ওরাকল ব্যবহার করে অ্যালগরিদম এজেন্টদের উপযোগিতা অ্যাক্সেস করার আরেকটি উপায় হল ডিমান্ড ওরাকল ব্যবহার করা (একটি ওরাকল যা, একটি মূল্য-ভেক্টর দেওয়া, এজেন্টের সবচেয়ে পছন্দসই বান্ডিল ফেরত দেয়)। এই মডেলেঃ ডবজিনস্কি এবং শাপিরা একটি পলিটাইম (1-1/ই)-অ্যাপ্রোক্সিমেশন অ্যালগরিদম উপস্থাপন করেন। কিছু ছোট ধনাত্মক ε-এর জন্য ফাইজি এবং ভন্ড্রাক এটিকে (1-1/e + ε)-এ উন্নত করে (এটি উপরের কঠোরতার ফলাফলের বিরোধিতা করে না, কারণ কঠোরতার ফলাফল শুধুমাত্র একটি মান ওরাকল ব্যবহার করে; কঠোরতার উদাহরণে, চাহিদা ওরাকলের নিজেই তাত্পর্যপূর্ণভাবে অনেক প্রশ্নের প্রয়োজন হবে)। যখন এজেন্টদের ইউটিলিটিগুলি সাব-অ্যাডিটিভ সেট ফাংশন (সাব-মডুলার থেকে বেশি সাধারণ) হয়, তখন একটি আনুমানিক মূল্য প্রশ্নের একটি সূচকীয় সংখ্যার প্রয়োজন হবে। ফাইজি এই সমস্যার একটি এলপি শিথিলকরণের যে কোনও ভগ্নাংশ সমাধানকে কমপক্ষে ভগ্নাংশ সমাধানের মূল্যের সাথে একটি সম্ভাব্য সমাধানের জন্য বৃত্তাকার করার একটি উপায় উপস্থাপন করে। এটি সাধারণ সাবঅ্যাডিটিভ এজেন্টদের জন্য 1/2-অ্যাপ্রোক্সিমেশন দেয় এবং ভগ্নাংশ-সাবঅ্যাডিটিভ মূল্যায়নের বিশেষ ক্ষেত্রে (1-1/ই)-অ্যাপ্রোক্সিমেশন দেয়। সুপারঅ্যাডিটিভ এজেন্ট যখন এজেন্টদের ইউটিলিটিগুলি সুপারঅ্যাডিটিভ সেট ফাংশন হয় (সুপারমডুলার থেকে বেশি সাধারণ), তখন একটি আনুমানিকতার জন্য একটি সুপার-পলিনোমিয়াল সংখ্যক মান প্রশ্নের প্রয়োজন হবে। একক-মনের এজেন্ট একজন একক-মনের এজেন্ট শুধুমাত্র একটি নির্দিষ্ট সেট আইটেম চায়। প্রতিটি একক-মনের এজেন্টের জন্য, একটি ডিমান্ডেড সেট ডি এবং একটি মান ভি> 0 রয়েছে, যেমন। অর্থাৎ, এজেন্ট একটি নির্দিষ্ট পজিটিভ ইউটিলিটি পায় যদি এবং শুধুমাত্র যদি তাদের বান্ডিলটিতে তাদের দাবি করা সেট থাকে। একক-মনের এজেন্টদের সাথে কল্যাণ সর্বাধিককরণ এনপি-হার্ড এমনকি যখন সকলের জন্য। এই ক্ষেত্রে, সমস্যাটি সেট প্যাকিংয়ের সমতুল্য, যা এনপি হার্ড হিসাবে পরিচিত। উপরন্তু, এটি কোনও ধ্রুবক ফ্যাক্টরের মধ্যে আনুমানিক করা যায় না (সাবমডুলার এজেন্টের ক্ষেত্রে বিপরীত)। সর্বাধিক পরিচিত অ্যালগরিদম এটিকে একটি ফ্যাক্টরের মধ্যে আনুমানিক করে। সাধারণ এজেন্ট যখন এজেন্টদের নির্বিচারে মনোটোন ইউটিলিটি ফাংশন (পরিপূরক আইটেম সহ) থাকতে পারে, তখন কল্যাণ সর্বাধিককরণ কোনওটির জন্য একটি ফ্যাক্টরের মধ্যে আনুমানিক অনুমান করা কঠিন। যাইহোক, রাষ্ট্রীয় স্থান অনুসন্ধানের উপর ভিত্তি করে অ্যালগরিদম রয়েছে যা অনুশীলনে খুব ভাল কাজ করে। আরও দেখুন ইউটিলিটি ম্যাক্সিমাইজেশন সমস্যা রেফারেন্স অপ্টিমাইজেশন অ্যালগরিদম এবং পদ্ধতি