مکانیزم وی‌سی‌جی کیست؟ توضیح بده.
در طراحی سازوکار، سازوکار VCG یک سازوکار کلی است که در آن افراد راست می‌گویند و نتیجه آن بهینه اجتماعی است. این سازوکار تعمیمی از است که در آن کالاها به طریقی بین افراد تقسیم می‌شود. اما سازوکار VCG برای انتخاب هر خروجی دلخواه از بین حالات ممکن قابل استفاده است و جامعیت بیشتری دارد. در این مکانیزم افراد بایستی به اندازه اثر خارجی که بر روی دیگران می‌گذارند، پرداخت یا دریافت کنند.نمادگذاری.مجموعه X شامل تمام خروجی‌های ممکن مسئله است. همچنین n تعداد نفر با ارزش‌های مختلف نسبت به هر خروجی داریم. ارزش فرد i تابعی به صورت زیر است که ارزش را به واحد پول بیان می‌کند:formula_1با فرض بودن تابع مطلوبیت و دریافت pi واحد پول توسط فرد i داریم:formula_2هدف در این مسئله بیشینه‌سازی مطلوبیت اجتماعی (مجموع مطلوبیت‌های فردی) است.حقیقت‌گرایی.به‌طور عمده افراد تمایل به دروغ گفتن دارند. برای مثال بانکی که برای دریافت کمک مالی از دولت وضعیت خود را ورشکسته و بد نشان دهد یا خریداری که ارزش کالا را کمتر از ارزش واقعی بیان کند تا بتواند کالا را با قیمتی ارزان‌تر خریداری کند. هر سازوکاری از خانواده VCG یک سازوکار حقیقت‌گرا هست یعنی راست گفتن افراد در ارتباط با ارزش کالا یک راهبرد غالب محسوب می‌شود. چون در مرحله سوم به هر فرد مجموع ارزش‌های سایرین را می‌دهند، بنابراین رفاه کل هر فرد با رفاه کل جامعه هم جهت می‌شود؛ بنابراین انگیزه هر فرد در جهت جامعه و راست گفتن وی خواهد بود.یکتایی.مطابق با نظریه رابرت، در صورتی که توابع ارزش افراد نامحدود و حداقل سه نوع خروجی برای مسئله وجود داشته باشد، تنها سازوکار VCG است که می‌تواند خروجی راستگویی را اجرا کند؛ بنابراین این سازوکار تنها سازوکار حقیقت‌گرایی است که خروجی آن بهینه اجتماعی خواهد بود.قاعده Clarke pivot.با تعاریف مختلف برای تابع hi می‌توان سازوکارهای مختلفی را به دست آورد. برای مثالformula_5 یعنی بایستی به افراد برای شرکت در حراج پول پرداخته شود. تعریف دیگری از این تابع که به نام قاعده clarke pivot است به صورت زیر می‌باشد.formula_6مطابق با این قاعده میزان پرداختی هر نفر برابر با رفاه اجتماعی زمانی که فرد غائب باشد، منهای رفاه اجتماعی سایرین در هنگام حضور فرد که در واقع به معنای اثر خارجی ناشی از حضور هر فرد است. در صورتی که ارزش اعلامی افراد منفی نباشد، دو خاصیت عقلانی و مثبت نبودن پرداختی برای این قاعده وجود خواهد داشت. اولین خاصیت به معنای این است که هر بازیکن با شرکت در حراج ضرر نخواهد کرد(formula_7). خاصیت دوم بدین معناست که در این سازوکار نیازی نیست به افراد پول پرداخته شود بلکهformula_8 است؛ بنابراین سازوکار VCG یک قاعده بردبرد است. یعنی افراد خروجی دلخواه خود را دریافت کرده و به میزان کمتری از ارزش خروجی پرداخت خواهند کرد. در نتیجه سود هر فرد مثبت و سود اجتماعی نیز مثبت خواهد شد.مکانیزم VCG وزن‌دار.می‌توان به جای بیشینه کردن مجموع ارزش‌های افراد، مجموع وزنی ارزش‌ها را بیشینه کرد یعنی :formula_9همچنین میزان پرداختی به هر فرد به صورت زیر خواهد شد.formula_10حداقل‌سازی هزینه‌ها.سازوکار VCG را می‌توان برای کمینه‌سازی هزینه‌ها نیز استفاده نمود. زمانی که pi برای هر فرد منفی باشد، یعنی برابر با مجموع هزینه تحمیل شده به بقیه افراد هنگام حضور وی است. برای اینکه شرط عقلانی بودن هر فرد برقرار باشد، بایستی به هر فرد مبلغی معادل مجموع هزینه ناشی از بقیه افراد بدون حضور فرد مذکور پرداخت شود. در نتیجه پرداختی خالص به هر فرد برابر با سهم وی در کاهش هزینه‌های کل است.مزایا.formula_11تعریف شود، مقدار pi همواره منفی خواهد بود زیرا قسمت دوم معادله همواره بیشتر از قسمت اول آن می‌شود (چون بخش دوم ماکسیمم عبارت است). بنابراین همواره افراد بایستی پرداخت کننند و هیچ دریافت مثبتی نخواهند داشت.formula_12 . در نتیجه انگیزه افراد برای شرکت در مکانیزم عقلانی خواهد بود.کاربردها.حراج.در این نوع حراج‌ها یک کالا وجود دارد و افراد متناسب با تمایلات خود برای آن ارزش قائل می‌شوند. وضعیت هر کالا در هر لحظه n+1 حالت دارد که به n طریق کالا فروخته شده و به یک طریق فروش نخواهد رفت. در این نوع حراج‌ها، برنده در مرحله سوم هیچ پولی دریافت نخواهد کرد و سایرین به اندازه ارزش اظهار شده توسط برنده پول دریافت خواهند کرد. در مرحله چهارم، برنده دومین بیشترین قیمت را پرداخت می‌کند و سایرین ارزش اظهار شده توسط فرد برنده را خواهند پرداخت (حراج نوع دوم).کالای عمومی.عموماً شهروندان بایستی در ساخت و ایجاد یک پروژه عمومی همکاری داشته باشند و پروژه زمانی اجرا خواهد شد که ارزش ایجاد شده برای افراد بیشتر از هزینه تأسیس آن باشد. مطابق با مکانیزم مطرح شده، هر فرد در صورت pivotal بودنش بایستی مالیاتی به اندازه اختلاف دو حالت مشارکت و عدم مشارکتش پرداخت کند. Pivotal یعنی با حذف فرد، پروژه اجرایی نخواهد شد. با وجود عقلایی بودن، در این روش تراز تجاری برقرار نیست یعنی مخارج بیشتر از هزینه‌ها خواهد بود.سریع‌ترین مسیر.این مسئله یک مسئله کمینه‌سازی هزینه است که هدف در آن انتقال پیغام از نقطه‌ای به دیگری در یک شبکه ارتباطی است. هزینه در این انتقال به معنای مدت زمانی است که طول می‌کشد این پیغام انتقال داده شود؛ بنابراین یافتن سریعترین مسیر به معنای یافتن مسیر با کمترین هزینه است. در صورتی که زمان انتقال هر کامپیوتر در شبکه را بدانیم، می‌توان از طریق الگوریتم کوتاه‌ترین مسیر، جواب دلخواه را پیدا کرد. اما مشکل اینجاست که این اطلاعات در دسترس نیست و کامپیوترها برای انگیزه‌های شخصی ممکن است این اطلاعات را اشتباه گزارش کنند.برای حل این مسئله می‌توان از مکانیزم VCGاستفاده کرد که در آن X مجموعه‌ای شامل تمام مسیرهای ممکن رسیدن به هدف است. ارزش هر فرد(کامپیوتر) در این مسئله منفی مقدار زمان انتقال پیغام توسط فرد استformula_13. میزان دریافتی هر فرد در مرحله سوم مقداری منفی است. یعنی هر فرد بایستی به اندازه مجموع زمان انتقال سایر افراد در مسیر انتخابی پول پرداخت کند؛ بنابراین با در نظر گرفتن زمان انتقال خود فرد و با فرض قابل تبدیل بودن زمان به پول، هر فرد به اندازه ارزش کل زمان انقال پیغام در مسیر، هزینه از دست می‌دهد که به معنای یکسو شدن انگیزه‌های فرد و مکانیزم است.قاعده clarke pivot برای عقلایی کردن مکانیزم به کار می‌رود. به گونه‌ای که هر فرد به اندازه کل زمان انتقال پیام هنگامی که فرد در شبکه حضور نداشت، پول دریافت می‌کند که این مقدار بزرگتر مساوی زمان کل هنگام حضور فرد است؛ بنابراین مطلوبیت هر فرد حداقل به خوبی شرکت نکردن در مکانیزم خواهد بود.تجارت دوجانبه.زمانی که یک خریدار و یک فروشنده داشته باشیم و ارزش کالا برای فروشنده و خریدار متفاوت باشد، نیز می‌توان از طریق مکانیزم VCG تجارت یا عدم تجارت را شکل داد و میزان پرداختی توسط هر کدام از طرفین را محاسبه نمود. البته ممکن است تراز بودجه حاصل نشود و جهت پیاده‌سازی مکانیزم مجبور به دادن یارانه شویم.مسائل دیگری مربوط به گراف، برای مثال درخت فراگیر مینیمم یا جورسازی ماکسیمم نیز به طریقی مشابه حل می‌شوند. برنامه‌ریزی شغل نیز مثالی دیگر از کاربرد تقریبی این مکانیزم است.مثال.دو هم‌خانه‌ای می‌خواهند یک دستگاه پلی استیشن برای خود خریداری کنند. ارزش این دستگاه برای هر کدام به اندازه ۳۰۰ دلار است اما قیمت دستگاه ۴۰۰ دلار می‌باشد. یعنی formula_14. اگر x را متغیری صفر و یک به صورت زیر نمایش دهیم.formula_15خواهیم داشت:formula_16با توجه به مکانیزم VCGدستگاه خریداری شده و میزان پرداختی توسط هر یک از فرد ۱ و ۲ به اندازه ۱۰۰ واحد می‌باشد. (با توجه به راست‌گویی افراد در این مکانیزم)formula_17