Median mechanism
میڈین میکانزم ووٹنگ کا ایک قاعدہ ہے جو لوگوں کو یک جہتی ڈومین میں قدر کا فیصلہ کرنے کی اجازت دیتا ہے۔ ہر شخص اپنی مثالی قدر لکھ کر ووٹ دیتا ہے، اور قاعدہ ایک واحد قدر کا انتخاب کرتا ہے جو (بنیادی طریقہ کار میں) تمام ووٹوں کا میڈین ہے۔ میڈین میکانزم کا استعمال کیا جا سکتا ہے، مثال کے طور پر، ملک کے بجٹ کے سائز کا فیصلہ کرنے کے لیے: ہر شخص کہتا ہے کہ مثالی بجٹ کا سائز کیا ہونا چاہیے، اور منتخب کردہ سائز اعلان کردہ اقدار کا میڈین ہے۔ ایک اور ممکنہ درخواست یہ فیصلہ کرنا ہے کہ سالانہ اسکول کی تعطیلات کتنی لمبی ہونی چاہئیں: ہر شخص دنوں میں مثالی لمبائی کہتا ہے، اور میڈین کا انتخاب کیا جاتا ہے۔ تیسری مثال یہ ہے کہ یہ فیصلہ کرنا کہ دفتر میں ایئر کنڈیشنر کو کس درجہ حرارت پر سیٹ کیا جانا چاہیے۔ چوتھی مثال ایک جہت میں سہولت کے مقام کا مسئلہ ہے۔ میڈین میکانزم کی ایک اہم خصوصیت یہ ہے کہ یہ سچا ہے: اگر ہر ووٹر کی افادیت زیادہ ہے جب بھی منتخب کردہ قیمت اس کی مثالی قیمت کے قریب ہے، تو ہر ووٹر کے لیے ایک بہترین حکمت عملی یہ ہے کہ وہ اپنی حقیقی مثالی قیمت کا اعلان کرے، اس سے قطع نظر کہ دوسرے ووٹر کیا کہتے ہیں۔ یہ دیگر قدرتی میکانزم کے برعکس ہے، جیسے اوسط میکانزم۔ اوسط میکانزم کے ساتھ، اگر موجودہ اوسط ووٹر کی مثالی قیمت سے کم ہے، تو ووٹر کے لیے زیادہ قیمت (اور اس کے برعکس) کا اعلان کرنا بہتر ہو سکتا ہے، تاکہ منتخب کردہ قیمت کو اس کی مثالی قیمت کی طرف "کھینچا" جا سکے۔ میڈین میکانزم اس طرح کی ہیرا پھیری سے محفوظ ہے۔ مزید برآں، ہر ایسا میکانزم جو سچا اور گمنام ہو، ایک عام میڈین میکانزم ہے-ایک ایسا میکانزم جو کچھ مقررہ "سوسائٹی ووٹوں" کو داخل کرتا ہے اور پھر میڈین کا انتخاب کرتا ہے (نیچے دیکھیں)۔ مفروضے سوسائٹی ایک جہتی سیٹ میں سے ایک قدر کا انتخاب کرنا چاہتی ہے، جسے حقیقی لکیر کے ذیلی سیٹ کے طور پر بیان کیا جا سکتا ہے، جیسے۔ حقیقی وقفہ [0,1]۔ کچھ این ووٹرز ہیں۔ ہر ووٹر i کی ایک مثالی قدر پائی ہوتی ہے، جسے i کی چوٹی بھی کہا جاتا ہے۔ ووٹر I کی افادیت منتخب کردہ قیمت پر منحصر ہے: اگر منتخب کردہ قیمت پائی کے قریب ہو تو ووٹر زیادہ خوش ہوتا ہے۔ رسمی طور پر، یوٹیلیٹیز ہر دو متبادلات x، y کے لیے واحد چوٹی کی شرط کو پورا کرتی ہیں: اگر x> y ± پائی، یا اگر x <y ≤ پائی، تو ایجنٹ y سے x کو ترجیح دیتا ہے۔ ایک یوٹیلیٹی فنکشن جو اس شرط کو پورا کرتا ہے وہ ہے: ui (x) =-|x-Pi | ؛ لہذا چوٹی کی افادیت 0 ہے، اور دیگر متبادلات کی افادیت منفی ہے، اور ہم چوٹی سے جتنا دور ہوں گے اتنا ہی زیادہ منفی ہو جاتا ہے۔ طریقہ کار 1،.، n میں ہر ایجنٹ i سے کہا جاتا ہے کہ وہ پائی کی قیمت کی اطلاع دے۔ اقدار کو چڑھتے ہوئے ترتیب p1 ≤. ≤ pn میں ترتیب دیا جاتا ہے۔ بنیادی میکانزم میں، جب n عجیب ہو تو منتخب کردہ ویلیو p (n + 1)/2 ہوتی ہے، جو ویلیوز کے میڈین کے برابر ہوتی ہے (جب n ایون ہوتا ہے، تو منتخب کردہ ویلیو pn/2 ہوتی ہے): چوائس = میڈین (p1,., pn)۔ جنرلائزڈ میڈین میکانزم (جی ایم ایم) میں، کچھ کے پہلے سے طے شدہ سوسائٹی کے ووٹ ہوتے ہیں (جنہیں فینٹم ووٹ بھی کہا جاتا ہے)، ایس 1،.، ایس کے۔ منتخب کردہ قیمت یہ ہے: انتخاب = میڈین (p1,., pn, s1,., sk)۔ سوسائٹی کے ووٹوں کے ہر انتخاب کے لیے ایس 1،.، ایس کے، جی ایم ایم گمنام، اسٹریٹجی پروف، اور گروپ اسٹریٹجی پروف ہے۔ مزید برآں، اگر سوسائٹی کے ووٹوں کی تعداد زیادہ سے زیادہ n-1 ہے، تو GMM بھی پیریٹو ایفیشنٹ ہے۔ خاص طور پر، جی ایم ایم اتفاق رائے کی خاصیت کو مطمئن کرتا ہے: اگر تمام این ووٹرز کسی قدر پر متفق ہیں، تو اس قدر کا انتخاب کیا جاتا ہے۔ خصوصیات ہر گمنام اور اسٹریٹجی پروف میکانزم کے لیے، کچھ این + 1 سوسائٹی ووٹ ایسے ہوتے ہیں کہ میکانزم ان سوسائٹی ووٹوں کے ساتھ جی ایم ایم کے برابر ہوتا ہے۔ نوٹ کریں کہ اس میں این-1 سوسائٹی کے ووٹوں کے ساتھ تمام جی ایم ایم-ایس شامل ہیں: کچھ این-1 سوسائٹی کے ووٹوں کو دیکھتے ہوئے، کوئی بھی سوسائٹی کا ووٹ-ν پر (یا سب سے چھوٹی ممکنہ قیمت) اور سوسائٹی کا ووٹ + ν پر (یا سب سے بڑی ممکنہ قیمت) شامل کر سکتا ہے۔ ان این + 1 سوسائٹی کے ووٹوں کے ساتھ میڈین اصل این-1 سوسائٹی کے ووٹوں کے ساتھ میڈین سے ملتا جلتا ہے۔ اسی طرح، اس طبقے میں این-3 سوسائٹی کے ووٹوں، این-5 سوسائٹی کے ووٹوں وغیرہ کے ساتھ تمام جی ایم ایم شامل ہیں۔ ہر گمنام، حکمت عملی سے محفوظ اور موثر طریقہ کار کو این-1 سوسائٹی کے ووٹوں کے ساتھ ایک عمومی میڈین طریقہ کار کے طور پر پیش کیا جا سکتا ہے۔ خاص صورتوں میں اگر تمام n-1 سوسائٹی کے ووٹ-φ (یا سب سے چھوٹی ممکنہ قیمت) ہیں، تو GMM Min (p1,., pn) = p1 کا انتخاب کرتا ہے۔ اسی طرح، اگر تمام n-1 سوسائٹی کے ووٹ + ν (یا سب سے بڑی ممکنہ قیمت) ہیں، تو GMM زیادہ سے زیادہ (p1,., pn) = pn کا انتخاب کرتا ہے۔ عام طور پر، اگر k سوسائٹی کے ووٹ + ν اور n-1-k-ν ہیں، تو GMM pk + 1-(k + 1)-th سب سے زیادہ قیمت کا انتخاب کرتا ہے۔ یہ تمام میکانزم سچے ہیں۔ بجٹ جمع کرنے کے لیے درخواست بجٹ تجاویز کو صحیح طریقے سے جمع کرنے کے لیے ایک طریقہ کار کی تعمیر کے لیے عمومی میڈین میکانزم کا استعمال کیا گیا ہے۔ متعلقہ تصورات اسی طرح کی خصوصیت چنگ نے دی ہے۔ میڈین میکانزم میں، ہر ایجنٹ اپنی مثالی قدر ("چوٹی") کی اطلاع دیتا ہے۔ میڈین ووٹر تھیوریم درجہ بند ووٹنگ میکانزم سے متعلق ہے، جس میں ہر ایجنٹ متبادلات پر اپنی مکمل درجہ بندی کی اطلاع دیتا ہے۔ تھیوریم کا کہنا ہے کہ، اگر ایجنٹوں کی ترجیحات ایک چوٹی پر ہیں، تو ہر کونڈورسیٹ طریقہ ہمیشہ میڈین ووٹر کے پسندیدہ امیدوار کا انتخاب کرتا ہے۔ حوالہ جات واحد فاتح انتخابی نظام میکانزم ڈیزائن