Prophet inequality
অনলাইন অ্যালগরিদম এবং সর্বোত্তম বন্ধের তত্ত্বে, একটি ভাববাদী অসমতা একটি সিদ্ধান্ত গ্রহণের প্রক্রিয়ার প্রত্যাশিত মূল্যের উপর আবদ্ধ যা পরিচিত সম্ভাব্যতা বিতরণ থেকে এলোমেলো ইনপুটগুলির একটি ক্রম পরিচালনা করে, যা প্রত্যাশিত মূল্যের সাথে সম্পর্কিত যা একজন "ভাববাদী" দ্বারা অর্জন করা যেতে পারে যিনি সমস্ত ইনপুট (এবং কেবল তাদের বিতরণ নয়) সময়ের আগে জানেন। অ্যালগরিদমিক মেকানিজম ডিজাইন এবং গাণিতিক অর্থনীতির তত্ত্বে এই বৈষম্যগুলির প্রয়োগ রয়েছে। একক আইটেম ধ্রুপদী একক-আইটেম ভাববাদী বৈষম্য দ্বারা প্রকাশিত হয়েছিল, এর আঁটসাঁট রূপের কৃতিত্ব ডি. জে. এইচ. (বেন) গারলিংকে দেওয়া হয়েছিল। এটি এমন একটি প্রক্রিয়া সম্পর্কিত যেখানে র্যান্ডম ভেরিয়েবলের একটি ক্রম পরিচিত বিতরণ থেকে আসে। যখন প্রত্যেকে আসে, সিদ্ধান্ত গ্রহণের প্রক্রিয়াটিকে অবশ্যই সিদ্ধান্ত নিতে হবে যে এটি গ্রহণ করা হবে এবং প্রক্রিয়াটি বন্ধ করা হবে, বা এটি প্রত্যাখ্যান করা হবে এবং ক্রমানুসারে পরবর্তী পরিবর্তনশীলটিতে যেতে হবে। প্রক্রিয়াটির মান হল একক গৃহীত পরিবর্তনশীল, যদি একটি থাকে, অথবা অন্যথায় শূন্য। এটি ধরে নেওয়া যেতে পারে যে সমস্ত চলক অ-নেতিবাচক; অন্যথায়, শূন্য দ্বারা নেতিবাচক মান প্রতিস্থাপন ফলাফল পরিবর্তন করে না। উদাহরণস্বরূপ, এটি এমন আর্থিক পরিস্থিতির মডেল হতে পারে যেখানে পরিবর্তনশীল পণ্যগুলি একটি নির্দিষ্ট মূল্যে কিছু অবিভাজ্য পণ্য কেনার প্রস্তাব দেয় এবং বিক্রেতাকে অবশ্যই সিদ্ধান্ত নিতে হবে যে কোন (যদি থাকে) প্রস্তাবটি গ্রহণ করতে হবে। একজন নবী, চলকের সম্পূর্ণ ক্রম জেনে, স্পষ্টতই তাদের মধ্যে বৃহত্তম নির্বাচন করতে পারেন, এই প্রক্রিয়ার যে কোনও নির্দিষ্ট উদাহরণের জন্য মূল্য অর্জন করতে পারেন, এবং প্রত্যাশিত মূল্য নবী বৈষম্য এই প্রক্রিয়ার জন্য একটি অনলাইন অ্যালগরিদমের অস্তিত্বকে বর্ণনা করে যার প্রত্যাশিত মান নবীর কমপক্ষে অর্ধেকঃ কোনও অ্যালগরিদম সমস্ত বিতরণের জন্য বৃহত্তর প্রত্যাশিত মান অর্জন করতে পারে না একক-আইটেম নবীর বৈষম্য প্রমাণ করার জন্য একটি পদ্ধতি হল একটি "প্রান্তিক অ্যালগরিদম" ব্যবহার করা যা একটি পরামিতি নির্ধারণ করে এবং তারপরে প্রথম এলোমেলো চলককে গ্রহণ করে যা কমপক্ষে ততটাই বড় যদি এই প্রক্রিয়াটি কোনও আইটেমকে গ্রহণ করার সম্ভাবনা থাকে, তবে তার প্রত্যাশিত মানটি নির্বাচিত চলকের (যদি একটি থাকে) উপর প্রত্যাশিত অতিরিক্ত। প্রতিটি পরিবর্তনশীলকে কমপক্ষে সম্ভাব্যতা সহ প্রান্তিক অ্যালগরিদম দ্বারা বিবেচনা করা হবে এবং যদি এটি বিবেচনা করা হয় তবে অতিরিক্ত অবদান রাখবে, তাই প্রত্যাশার রৈখিকতা দ্বারা প্রত্যাশিত অতিরিক্ত কমপক্ষে বিতরণের মাঝখানে সেটিং করা হয় যাতে এবং প্রত্যাশিত অতিরিক্তের উপর এই বাউন্ডে যোগ করা হয়, এবং পদগুলি একে অপরকে বাতিল করে দেয়, যা দেখায় যে প্রান্তিক অ্যালগরিদমের এই সেটিংয়ের জন্য কমপক্ষে একটি ভিন্ন প্রান্তিকের প্রত্যাশিত মান অর্জন করে, কমপক্ষে এই একই প্রত্যাশিত মানও অর্জন করে। সাধারণীকরণ অন্যান্য অনলাইন প্রেক্ষাপটে একক-বস্তু নবী বৈষম্যের বিভিন্ন সাধারণীকরণ জানা যায় এবং এগুলিকে নবী বৈষম্যও বলা হয়। প্রতিযোগিতামূলক বিশ্লেষণের সাথে তুলনা নবী বৈষম্যগুলি অনলাইন অ্যালগরিদমের প্রতিযোগিতামূলক বিশ্লেষণের সাথে সম্পর্কিত, তবে দুটি উপায়ে পৃথক। প্রথমত, প্রতিযোগিতামূলক বিশ্লেষণের বেশিরভাগই সবচেয়ে খারাপ কেস ইনপুটগুলি ধরে নেয়, গণনা করা মান এবং সর্বোত্তম মানের মধ্যে অনুপাত সর্বাধিক করার জন্য বেছে নেওয়া হয় যা ভবিষ্যতের জ্ঞানের সাথে অর্জন করা যেতে পারে, যেখানে নবীর বৈষম্যের জন্য ইনপুট সম্পর্কে কিছু জ্ঞান, এর বিতরণ, অনুমান করা হয়। এবং দ্বিতীয়ত, একটি নির্দিষ্ট প্রতিযোগিতামূলক অনুপাত অর্জনের জন্য, একটি অনলাইন অ্যালগরিদমকে অবশ্যই সমস্ত ইনপুটগুলিতে সর্বোত্তম পারফরম্যান্সের সেই অনুপাতের মধ্যে সম্পাদন করতে হবে। পরিবর্তে, একটি ভাববাদী বৈষম্য শুধুমাত্র প্রত্যাশার পারফরম্যান্সকে সীমাবদ্ধ করে, কিছু ইনপুট সিকোয়েন্সকে আরও খারাপ পারফরম্যান্স তৈরি করতে দেয় যতক্ষণ গড় ভাল থাকে। রেফারেন্স বাহ্যিক লিঙ্ক ম্যাট্রয়েড প্রফেট ইনইকুয়ালিটিজ অ্যান্ড মেকানিজম ডিজাইন, দ্য ম্যাট্রয়েড ইউনিয়ন অ্যান ইকোনমিক ভিউ অফ প্রফেট ইনইকুয়ালিটিজ অনলাইন অ্যালগরিদম সিকোয়েন্সিয়াল এক্সপেরিমেন্টস মেকানিজম ডিজাইন