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

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

قاعده Clarke pivot

فرضیات

• هر فرد ارزش کالا برای خود را می‌داند.
• ترجیحات افراد بر روی خروجی مسئله است نه بر روی فرایند آن.
• ترجیحات نسبت به پول شبه خطی است.
• هیچ محدودیتی در انتقال پول بین افراد نیست.

نمادگذاری

مجموعه X شامل تمام خروجی‌های ممکن مسئله است. همچنین n تعداد نفر با ارزش‌های مختلف نسبت به هر خروجی داریم. ارزش فرد i تابعی به صورت زیر است که ارزش را به واحد پول بیان می‌کند: $v_{i}:x\rightarrow \;R+$ با فرض شبه‌خطی بودن تابع مطلوبیت و دریافت pi واحد پول توسط فرد i داریم: $u_{i}=v_{i}(x^{*})+p_{i}$ هدف در این مسئله بیشینه‌سازی مطلوبیت اجتماعی (مجموع مطلوبیت‌های فردی) است.

پیاده‌سازی

1. دریافت تابع ارزش هر فرد بر حسب نوع خروجی
2. محاسبه خروجی متناسب با بهینه اجتماعی (یعنی ماکسیمم‌کننده مجموع توابع ارزش)
3. میزان پرداختی به هر فرد برابر با مجموع توابع ارزش بقیه افراد می‌باشد.$p_{i}=\sum _{j\neq \;i}v_{j}(x^{*})$
4. همچنین به اندازه یک تابع دلخواه از مابقی ارزش‌ها نیز به هر فرد پرداخت خواهد شد.$p_{i}^{+}=h_{i}(v_{-i})$

حقیقت‌گرایی

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

یکتایی

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

قاعده Clarke pivot

با تعاریف مختلف برای تابع hi می‌توان مکانیزم‌های مختلفی را به دست آورد. برای مثال $h_{i}(v_{-i})=0$ یعنی بایستی به افراد برای شرکت در حراج پول پرداخته شود. تعریف دیگری از این تابع که به نام قاعده clarke pivot است به صورت زیر می‌باشد. $h_{i}(v_{-i})=-\max _{x}\sum _{j\neq \;i}v_{j}(x)$ مطابق با این قاعده میزان پرداختی هر نفر برابر با رفاه اجتماعی زمانی که فرد غائب باشد، منهای رفاه اجتماعی سایرین در هنگام حضور فرد که در واقع به معنای اثر خارجی ناشی از حضور هر فرد است. در صورتی که ارزش اعلامی افراد منفی نباشد، دو خاصیت عقلانی و مثبت نبودن پرداختی برای این قاعده وجود خواهد داشت. اولین خاصیت به معنای این است که هر بازیکن با شرکت در حراج ضرر نخواهد کرد($v_{i}(x)+p_{i}\geq 0$). خاصیت دوم بدین معناست که در این مکانیزم نیازی نیست به افراد پول پرداخته شود بلکه$p_{i}\leq 0$ است؛ بنابراین مکانیزم VCG یک قاعده بردبرد است. یعنی افراد خروجی دلخواه خود را دریافت کرده و به میزان کمتری از ارزش خروجی پرداخت خواهند کرد. در نتیجه سود هر فرد مثبت و سود اجتماعی نیز مثبت خواهد شد.

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

می‌توان به جای ماکسیمم کردن مجموع ارزش‌های افراد، مجموع وزنی ارزش‌ها را بیشینه کرد یعنی : $x^{opt}(v)=\arg \max _{x}\sum _{i=1}^{n}w_{i}v_{i}(x)$ همچنین میزان پرداختی به هر فرد به صورت زیر خواهد شد. $p_{i}={\frac {1}{w_{i}}}\sum _{j\neq \;i}w_{j}v_{j}(x^{*})$

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

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

مزایا

• سازگار با انگیزه‌ها(Incentive Compatible): در این مکانیزم افراد همواره ارزش واقعی را مستقل از نظر سایر افراد اعلام می‌کنند زیرا مطلوبیت هر فرد حاصل از مطلوبیت تمام افراد است و تنها حاصل از ارزش اعلامی خود فرد نیست. در واقع راست گفتن افراد نسبت به هر استراتژی دیگری غالب است.
• بهینه اجتماعی (کارایی): خروجی این مکانیزم ماکسیمم‌کننده تابع رفاه اجتماعی است.
• نیازی نیست که به افراد پول داده شود. اگر مقدار دریافتی افراد را به صورت

$p_{i}=\sum _{j\neq \;i}v_{j}(x^{*})-\max _{x}\sum _{j\neq \;i}v_{j}(x)$ تعریف شود، مقدار pi همواره منفی خواهد بود زیرا قسمت دوم معادله همواره بیشتر از قسمت اول آن می‌شود (چون بخش دوم ماکسیمم عبارت است). بنابراین همواره افراد بایستی پرداخت کننند و هیچ دریافت مثبتی نخواهند داشت.

• عقلانیت فردی(Individual Rationality): در صورتی که ارزش اعلامی افراد منفی نباشد، مطلوبیت حاصل برای تمام افراد هیچگاه کمتر از صفر نخواهد شد

$\max _{a}\sum _{j}v_{j}(a)\geq \;\max _{a}\sum _{j\neq \;i}v_{j}(a)$ . در نتیجه انگیزه افراد برای شرکت در مکانیزم عقلانی خواهد بود.

معایب

• در مواقع غیرخطی بودن مطلوبیت، افراد بایستی منحنی مطلوبیت خود را دقیقاً اعلام کنند. این مورد به پیچیدگی‌های مکانیزم اضافه خواهد کرد.
• این مکانیزم اطلاعات بسیاری زیادی را از افراد آشکار می‌کند که شاید تمایل آن‌ها را به شرکت در مکانیزم کاهش دهد.
• عدم تراز بودن بودجه: یعنی میزان پولی که افراد می‌دهند با میزان پولی که سایرین می‌گیرند، یکی نیست؛ بنابراین پیاده‌سازی این مکانیزم نیازمند بودجه نامحدودی است.
• ممکن است خروجی مکانیزم درآمدی بسیار پایین برای افراد باشد. یعنی میزان پرداختی افراد خیلی نزدیک به مطلوبیت حاصل باشد.
• امکان تبانی و در نتیجه آن عدم رسیدن به خروجی کارا
• انگیزه تقلب افراد

کاربردها

حراج

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

کالای عمومی

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

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

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

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

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

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

مثال

دو هم‌خانه‌ای می‌خواهند یک دستگاه پلی استیشن برای خود خریداری کنند. ارزش این دستگاه برای هر کدام به اندازه ۳۰۰ دلار است اما قیمت دستگاه ۴۰۰ دلار می‌باشد. یعنی $v_{1}=v_{2}=300<400,v_{3}=400,v_{1}+v_{2}>400$. اگر x را متغیری صفر و یک به صورت زیر نمایش دهیم. $x={\begin{cases}1,&{\mbox{if }}playstation{\mbox{is sold}}\\0,&{\mbox{if }}playstation{\mbox{is not sold}}\end{cases}}$

خواهیم داشت:$v_{1}(1)=v_{2}(1)=300,v_{1}(0)=v_{2}(0)=0,v_{3}(1)=0,v_{3}(0)=400$ با توجه به مکانیزم VCGدستگاه خریداری شده و میزان پرداختی توسط هر یک از فرد ۱ و ۲ به اندازه ۱۰۰ واحد می‌باشد. (با توجه به راست‌گویی افراد در این مکانیزم) $t_{1}(300)=(v_{2}(1)+v_{3}(1))-(v_{2}(0)+v_{3}(0))=300-400=-100=t_{2}(300)$

منابع

1. Vazirani, Vijay V. ; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
2. Avrim Blum (۲۸ فوریه ۲۰۱۳). "Algorithms, Games, and Networks - Lecture 14" (PDF). Retrieved 28 December 2015.
3. Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". Games and Economic Behavior. 35: 166. doi:10.1006/game.۱۹۹۹٫۰۷۹۰.
4. Board S. , (2011), Lecture Notes.Bolton and Dewatripont, (2005), Contract Theory, MIT Press.
5. www.kellogg.northwestern.edu/faculty/georgiadis/Teaching/Ec515_Module18.pdf
6. www.cs.cmu.edu/~arielpro/15896/docs/notes14.pdf
7. Paul Milgrom."Putting Auction Theory to Work",Cambridge University Press, 1998-Business & Economics - 392 pages