Prophet inequality
آن لائن الگورتھم اور زیادہ سے زیادہ روک تھام کے نظریہ میں، ایک نبی عدم مساوات فیصلہ سازی کے عمل کی متوقع قیمت کا پابند ہے جو معلوم امکانات کی تقسیم سے بے ترتیب ان پٹ کے سلسلے کو سنبھالتی ہے، جو کہ متوقع قیمت سے متعلق ہے جو ایک "نبی" کے ذریعہ حاصل کی جا سکتی ہے جو وقت سے پہلے تمام ان پٹ (اور نہ صرف ان کی تقسیم) کو جانتا ہے۔ ان عدم مساوات کا اطلاق نظریہ الگورتھمک میکانزم ڈیزائن اور ریاضیاتی مالیات میں ہوتا ہے۔ واحد آئٹم کلاسیکی واحد آئٹم نبی عدم مساوات کو ڈی جے ایچ (بین) گارلنگ کو اس کی سخت شکل کا سہرا دیتے ہوئے شائع کیا گیا تھا۔ یہ ایک ایسے عمل سے متعلق ہے جس میں بے ترتیب متغیرات کا ایک سلسلہ معروف تقسیم سے آتا ہے۔ جب ہر ایک آتا ہے، فیصلہ سازی کے عمل کو یہ فیصلہ کرنا ہوگا کہ اسے قبول کرنا ہے اور عمل کو روکنا ہے، یا اسے مسترد کرنا ہے اور ترتیب میں اگلے متغیر پر جانا ہے۔ عمل کی قیمت واحد قبول شدہ متغیر ہے، اگر کوئی ہے، یا بصورت دیگر صفر ہے۔ یہ فرض کیا جا سکتا ہے کہ تمام متغیرات غیر منفی ہیں ؛ بصورت دیگر، منفی اقدار کو صفر سے تبدیل کرنے سے نتیجہ تبدیل نہیں ہوتا ہے۔ مثال کے طور پر، یہ مالیاتی حالات کا نمونہ بن سکتا ہے جس میں متغیرات ایک مخصوص قیمت پر کچھ ناقابل تقسیم چیز خریدنے کی پیشکش کرتے ہیں، اور بیچنے والے کو فیصلہ کرنا ہوگا کہ کون سی (اگر کوئی ہو) پیشکش قبول کرنا ہے۔ ایک نبی، متغیرات کی پوری ترتیب کو جان کر، ظاہر ہے کہ ان میں سے سب سے بڑا منتخب کر سکتا ہے، اس عمل کی کسی بھی مخصوص مثال کے لیے قدر حاصل کر سکتا ہے، اور متوقع قدر نبی عدم مساوات اس عمل کے لیے ایک آن لائن الگورتھم کے وجود کو بیان کرتی ہے جس کی متوقع قیمت نبی کی کم از کم نصف ہے: کوئی الگورتھم تمام تقسیمات کے لیے زیادہ متوقع قدر حاصل نہیں کر سکتا۔ واحد آئٹم نبی کی عدم مساوات کو ثابت کرنے کے لیے ایک طریقہ "دہلیز الگورتھم" کا استعمال کرنا ہے جو ایک پیرامیٹر طے کرتا ہے اور پھر پہلے بے ترتیب متغیر کو قبول کرتا ہے جو کم از کم اتنا ہی بڑا ہوتا ہے۔ اگر اس عمل سے کسی آئٹم کو قبول کرنے کا امکان ہے، تو اس کی متوقع قیمت اس منتخب متغیر (اگر کوئی ہے) کے مقابلے میں متوقع اضافی ہے۔ ہر متغیر پر کم از کم امکان کے ساتھ حد الگورتھم کے ذریعہ غور کیا جائے گا اور اگر اس پر غور کیا جائے تو یہ اضافی میں حصہ ڈالے گا، لہذا توقع کی لکیری سے متوقع اضافی کم از کم کی تقسیم کے میڈین پر سیٹ کرنا ہے تاکہ اور اس حد میں متوقع اضافی کو شامل کرنا، اور اصطلاحات کو ایک دوسرے کو منسوخ کرنے کا سبب بنتا ہے، جس سے یہ ظاہر ہوتا ہے کہ حد الگورتھم کی اس ترتیب کے لیے کم از کم ایک مختلف حد کی متوقع قیمت حاصل ہوتی ہے، کم از کم اسی متوقع قیمت کو بھی حاصل کرتی ہے۔ عامیاں دیگر آن لائن منظرناموں میں واحد آئٹم نبی کی عدم مساوات کی مختلف عامیاں معلوم ہیں، اور انہیں نبی کی عدم مساوات بھی کہا جاتا ہے۔ مسابقتی تجزیہ سے موازنہ نبی عدم مساوات کا تعلق آن لائن الگورتھم کے مسابقتی تجزیہ سے ہے، لیکن یہ دو طریقوں سے مختلف ہے۔ سب سے پہلے، زیادہ تر مسابقتی تجزیہ بدترین کیس ان پٹ کو فرض کرتا ہے، جس کا انتخاب کمپیوٹڈ ویلیو اور بہترین ویلیو کے درمیان تناسب کو زیادہ سے زیادہ کرنے کے لیے کیا جاتا ہے جو مستقبل کے علم کے ساتھ حاصل کیا جا سکتا تھا، جبکہ نبی عدم مساوات کے لیے ان پٹ، اس کی تقسیم کے بارے میں کچھ علم سمجھا جاتا ہے۔ جانا جاتا ہے۔ اور دوسرا، ایک مخصوص مسابقتی تناسب حاصل کرنے کے لیے، ایک آن لائن الگورتھم کو تمام ان پٹ پر بہترین کارکردگی کے اس تناسب کے اندر کارکردگی کا مظاہرہ کرنا چاہیے۔ اس کے بجائے، ایک نبی عدم مساوات صرف توقع میں کارکردگی کو محدود کرتی ہے، جس سے کچھ ان پٹ ترتیبات کو بدتر کارکردگی پیدا کرنے کی اجازت ملتی ہے جب تک کہ اوسط اچھی ہو۔ حوالہ جات بیرونی روابط میٹرائڈ نبی عدم مساوات اور میکانزم ڈیزائن، میٹرائڈ یونین نبی عدم مساوات کا ایک اقتصادی نظریہ آن لائن الگورتھم ترتیب وار تجربات میکانزم ڈیزائن