مکانیزم وی‌سی‌جی

در طراحی سازوکار، مکانیزم VCG یک مکانیزم کلی است که در آن افراد راست می‌گویند و نتیجه آن بهینه اجتماعی است. این مکانیزم تعمیمی از حراج VCG است که در آن کالاها به طریقی بین افراد تقسیم می‌شود. اما مکانیزم VCG برای انتخاب هر خروجی دلخواه از بین حالات ممکن قابل استفاده است و جامعیت بیشتری دارد. در این مکانیزم افراد بایستی به اندازه اثر خارجی که بر روی دیگران می‌گذارند، پرداخت یا دریافت کنند.

نمادگذاری

مجموعه X شامل تمام خروجی‌های ممکن مسئله است. همچنین n تعداد نفر با ارزش‌های مختلف نسبت به هر خروجی داریم. ارزش فرد i تابعی به صورت زیر است که ارزش را به واحد پول بیان می‌کند:

با فرض شبه‌خطی بودن تابع مطلوبیت و دریافت pi واحد پول توسط فرد i داریم:

هدف در این مسئله بیشینه‌سازی مطلوبیت اجتماعی (مجموع مطلوبیت‌های فردی) است.

حقیقت‌گرایی

به‌طور عمده افراد تمایل به دروغ گفتن دارند. برای مثال بانکی که برای دریافت کمک مالی از دولت وضعیت خود را ورشکسته و بد نشان دهد یا خریداری که ارزش کالا را کمتر از ارزش واقعی بیان کند تا بتواند کالا را با قیمتی ارزان‌تر خریداری کند. هر مکانیزمی از خانواده VCG یک مکانیزم حقیقت گرا هست یعنی راست گفتن افراد در ارتباط با ارزش کالا یک استراتژی غالب محسوب می‌شود. چون در مرحله سوم به هر فرد مجموع ارزش‌های سایرین را می‌دهند، بنابراین رفاه کل هر فرد با رفاه کل جامعه هم جهت می‌شود؛ بنابراین انگیزه هر فرد در جهت جامعه و راست گفتن وی خواهد بود.

یکتایی

مطابق با نظریه رابرت، در صورتی که توابع ارزش افراد نامحدود و حداقل سه نوع خروجی برای مسئله وجود داشته باشد، تنها مکانیزم VCG است که می‌تواند خروجی راست گویی را اجرا کند؛ بنابراین این مکانیزم تنها مکانیزم حقیقت گرایی است که خروجی آن بهینه اجتماعی خواهد بود.

قاعده Clarke pivot

با تعاریف مختلف برای تابع hi می‌توان مکانیزم‌های مختلفی را به دست آورد. برای مثال
 یعنی بایستی به افراد برای شرکت در حراج پول پرداخته شود. تعریف دیگری از این تابع که به نام قاعده clarke pivot است به صورت زیر می‌باشد.

مطابق با این قاعده میزان پرداختی هر نفر برابر با رفاه اجتماعی زمانی که فرد غائب باشد، منهای رفاه اجتماعی سایرین در هنگام حضور فرد که در واقع به معنای اثر خارجی ناشی از حضور هر فرد است. در صورتی که ارزش اعلامی افراد منفی نباشد، دو خاصیت عقلانی و مثبت نبودن پرداختی برای این قاعده وجود خواهد داشت. اولین خاصیت به معنای این است که هر بازیکن با شرکت در حراج ضرر نخواهد کرد(). خاصیت دوم بدین معناست که در این مکانیزم نیازی نیست به افراد پول پرداخته شود بلکه است؛ بنابراین مکانیزم VCG یک قاعده بردبرد است. یعنی افراد خروجی دلخواه خود را دریافت کرده و به میزان کمتری از ارزش خروجی پرداخت خواهند کرد. در نتیجه سود هر فرد مثبت و سود اجتماعی نیز مثبت خواهد شد.

مکانیزم VCG وزن‌دار

می‌توان به جای ماکسیمم کردن مجموع ارزش‌های افراد، مجموع وزنی ارزش‌ها را بیشینه کرد یعنی :

همچنین میزان پرداختی به هر فرد به صورت زیر خواهد شد.

حداقل‌سازی هزینه‌ها

مکانیزم VCG را می‌توان برای مینیمم‌سازی هزینه‌ها نیز استفاده نمود. زمانی که pi برای هر فرد منفی باشد، یعنی برابر با مجموع هزینه تحمیل شده به بقیه افراد هنگام حضور وی است. برای اینکه شرط عقلانی بودن هر فرد برقرار باشد، بایستی به هر فرد مبلغی معادل مجموع هزینه ناشی از بقیه افراد بدون حضور فرد مذکور پرداخت شود. در نتیجه پرداختی خالص به هر فرد برابر با سهم وی در کاهش هزینه‌های کل است.

حراج

در این نوع حراج‌ها یک کالا وجود دارد و افراد متناسب با تمایلات خود برای آن ارزش قائل می‌شوند. وضعیت هر کالا در هر لحظه n+1 حالت دارد که به n طریق کالا فروخته شده و به یک طریق فروش نخواهد رفت. در این نوع حراج‌ها، برنده در مرحله سوم هیچ پولی دریافت نخواهد کرد و سایرین به اندازه ارزش اظهار شده توسط برنده پول دریافت خواهند کرد. در مرحله چهارم، برنده دومین بیشترین قیمت را پرداخت می‌کند و سایرین ارزش اظهار شده توسط فرد برنده را خواهند پرداخت (حراج نوع دوم).

کالای عمومی

عموماً شهروندان بایستی در ساخت و ایجاد یک پروژه عمومی همکاری داشته باشند و پروژه زمانی اجرا خواهد شد که ارزش ایجاد شده برای افراد بیشتر از هزینه تأسیس آن باشد. مطابق با مکانیزم مطرح شده، هر فرد در صورت pivotal بودنش بایستی مالیاتی به اندازه اختلاف دو حالت مشارکت و عدم مشارکتش پرداخت کند. Pivotal یعنی با حذف فرد، پروژه اجرایی نخواهد شد. با وجود عقلایی بودن، در این روش تراز تجاری برقرار نیست یعنی مخارج بیشتر از هزینه‌ها خواهد بود.

سریع‌ترین مسیر

این مسئله یک مسئله کمینه‌سازی هزینه است که هدف در آن انتقال پیغام از نقطه‌ای به دیگری در یک شبکه ارتباطی است. هزینه در این انتقال به معنای مدت زمانی است که طول می‌کشد این پیغام انتقال داده شود؛ بنابراین یافتن سریعترین مسیر به معنای یافتن مسیر با کمترین هزینه است. در صورتی که زمان انتقال هر کامپیوتر در شبکه را بدانیم، می‌توان از طریق الگوریتم کوتاه‌ترین مسیر، جواب دلخواه را پیدا کرد. اما مشکل اینجاست که این اطلاعات در دسترس نیست و کامپیوترها برای انگیزه‌های شخصی ممکن است این اطلاعات را اشتباه گزارش کنند.
برای حل این مسئله می‌توان از مکانیزم VCGاستفاده کرد که در آن X مجموعه‌ای شامل تمام مسیرهای ممکن رسیدن به هدف است. ارزش هر فرد(کامپیوتر) در این مسئله منفی مقدار زمان انتقال پیغام توسط فرد است. میزان دریافتی هر فرد در مرحله سوم مقداری منفی است. یعنی هر فرد بایستی به اندازه مجموع زمان انتقال سایر افراد در مسیر انتخابی پول پرداخت کند؛ بنابراین با در نظر گرفتن زمان انتقال خود فرد و با فرض قابل تبدیل بودن زمان به پول، هر فرد به اندازه ارزش کل زمان انقال پیغام در مسیر، هزینه از دست می‌دهد که به معنای یکسو شدن انگیزه‌های فرد و مکانیزم است.
قاعده clarke pivot برای عقلایی کردن مکانیزم به کار می‌رود. به گونه‌ای که هر فرد به اندازه کل زمان انتقال پیام هنگامی که فرد در شبکه حضور نداشت، پول دریافت می‌کند که این مقدار بزرگتر مساوی زمان کل هنگام حضور فرد است؛ بنابراین مطلوبیت هر فرد حداقل به خوبی شرکت نکردن در مکانیزم خواهد بود.

تجارت دوجانبه

زمانی که یک خریدار و یک فروشنده داشته باشیم و ارزش کالا برای فروشنده و خریدار متفاوت باشد، نیز می‌توان از طریق مکانیزم VCG تجارت یا عدم تجارت را شکل داد و میزان پرداختی توسط هر کدام از طرفین را محاسبه نمود. البته ممکن است تراز بودجه حاصل نشود و جهت پیاده‌سازی مکانیزم مجبور به دادن یارانه شویم.
مسائل دیگری مربوط به گراف، برای مثال درخت فراگیر مینیمم یا جورسازی ماکسیمم نیز به طریقی مشابه حل می‌شوند. برنامه‌ریزی شغل نیز مثالی دیگر از کاربرد تقریبی این مکانیزم است.

مثال

دو هم‌خانه‌ای می‌خواهند یک دستگاه پلی استیشن برای خود خریداری کنند. ارزش این دستگاه برای هر کدام به اندازه ۳۰۰ دلار است اما قیمت دستگاه ۴۰۰ دلار می‌باشد. یعنی . اگر x را متغیری صفر و یک به صورت زیر نمایش دهیم.
خواهیم داشت:
با توجه به مکانیزم VCGدستگاه خریداری شده و میزان پرداختی توسط هر یک از فرد ۱ و ۲ به اندازه ۱۰۰ واحد می‌باشد. (با توجه به راست‌گویی افراد در این مکانیزم)