موضوع مقاله: مکانیزم وی‌سی‌جی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مکانیزم وی‌سی‌جی | مقدمه: در طراحی سازوکار، سازوکار VCG یک سازوکار کلی است که در آن افراد راست می‌گویند و نتیجه آن بهینه اجتماعی است. | ## بخش 1: مکانیزم وی‌سی‌جی | این سازوکار تعمیمی از حراج VCG است که در آن کالاها به طریقی بین افراد تقسیم می‌شود. اما سازوکار VCG برای انتخاب هر خروجی دلخواه از بین حالات ممکن قابل استفاده است و جامعیت بیشتری دارد. در این مکانیزم افراد بایستی به اندازه اثر خارجی که بر روی دیگران می‌گذارند، پرداخت یا دریافت کنند. ارزش فرد i تابعی به صورت زیر است که ارزش را به واحد پول بیان می‌کند: با فرض شبه‌خطی بودن تابع مطلوبیت و دریافت pi واحد پول توسط فرد i داریم: هدف در این مسئله بیشینه‌سازی مطلوبیت اجتماعی (مجموع مطلوبیت‌های فردی) است. پیاده‌سازی دریافت تابع ارزش هر فرد بر حسب نوع خروجی محاسبه خروجی متناسب با بهینه اجتماعی (یعنی ماکسیمم‌کننده مجموع توابع ارزش) میزان پرداختی به هر فرد برابر با مجموع توابع ارزش بقیه افراد می‌باشد. برای مثال بانکی که برای دریافت کمک مالی از دولت وضعیت خود را ورشکسته و بد نشان دهد یا خریداری که ارزش کالا را کمتر از ارزش واقعی بیان کند تا بتواند کالا را با قیمتی ارزان‌تر خریداری کند. هر سازوکاری از خانواده VCG یک سازوکار حقیقت‌گرا هست یعنی راست گفتن افراد در ارتباط با ارزش کالا یک راهبرد غالب محسوب می‌شود. چون در مرحله سوم به هر فرد مجموع ارزش‌های سایرین را می‌دهند، بنابراین رفاه کل هر فرد با رفاه کل جامعه هم جهت می‌شود؛ بنابراین انگیزه هر فرد در جهت جامعه و راست گفتن وی خواهد بود. یکتایی مطابق با نظریه رابرت، در صورتی که توابع ارزش افراد نامحدود و حداقل سه نوع خروجی برای مسئله وجود داشته باشد، تنها سازوکار VCG است که می‌تواند خروجی راستگویی را اجرا کند؛ بنابراین این سازوکار تنها سازوکار حقیقت‌گرایی است که خروجی آن بهینه اجتماعی خواهد بود. مطابق با این قاعده میزان پرداختی هر نفر برابر با رفاه اجتماعی زمانی که فرد غائب باشد، منهای رفاه اجتماعی سایرین در هنگام حضور فرد که در واقع به معنای اثر خارجی ناشی از حضور هر فرد است. در صورتی که ارزش اعلامی افراد منفی نباشد، دو خاصیت عقلانی و مثبت نبودن پرداختی برای این قاعده وجود خواهد داشت. خاصیت دوم بدین معناست که در این سازوکار نیازی نیست به افراد پول پرداخته شود بلکه است؛ بنابراین سازوکار VCG یک قاعده بردبرد است. یعنی افراد خروجی دلخواه خود را دریافت کرده و به میزان کمتری از ارزش خروجی پرداخت خواهند کرد. | ## بخش 2: مکانیزم وی‌سی‌جی | مکانیزم VCG وزن‌دار می‌توان به جای بیشینه کردن مجموع ارزش‌های افراد، مجموع وزنی ارزش‌ها را بیشینه کرد یعنی : همچنین میزان پرداختی به هر فرد به صورت زیر خواهد شد. حداقل‌سازی هزینه‌ها سازوکار VCG را می‌توان برای کمینه‌سازی هزینه‌ها نیز استفاده نمود. زمانی که pi برای هر فرد منفی باشد، یعنی برابر با مجموع هزینه تحمیل شده به بقیه افراد هنگام حضور وی است. برای اینکه شرط عقلانی بودن هر فرد برقرار باشد، بایستی به هر فرد مبلغی معادل مجموع هزینه ناشی از بقیه افراد بدون حضور فرد مذکور پرداخت شود. اگر مقدار دریافتی افراد را به صورت تعریف شود، مقدار pi همواره منفی خواهد بود زیرا قسمت دوم معادله همواره بیشتر از قسمت اول آن می‌شود (چون بخش دوم ماکسیمم عبارت است). معایب در مواقع غیرخطی بودن مطلوبیت، افراد بایستی منحنی مطلوبیت خود را دقیقاً اعلام کنند. این مکانیزم اطلاعات بسیاری زیادی را از افراد آشکار می‌کند که شاید تمایل آن‌ها را به شرکت در مکانیزم کاهش دهد. عدم تراز بودن بودجه: یعنی میزان پولی که افراد می‌دهند با میزان پولی که سایرین می‌گیرند، یکی نیست؛ بنابراین پیاده‌سازی این مکانیزم نیازمند بودجه نامحدودی است. امکان تبانی و در نتیجه آن عدم رسیدن به خروجی کارا انگیزه تقلب افراد کاربردها حراج در این نوع حراج‌ها یک کالا وجود دارد و افراد متناسب با تمایلات خود برای آن ارزش قائل می‌شوند. وضعیت هر کالا در هر لحظه n+1 حالت دارد که به n طریق کالا فروخته شده و به یک طریق فروش نخواهد رفت. در این نوع حراج‌ها، برنده در مرحله سوم هیچ پولی دریافت نخواهد کرد و سایرین به اندازه ارزش اظهار شده توسط برنده پول دریافت خواهند کرد. در مرحله چهارم، برنده دومین بیشترین قیمت را پرداخت می‌کند و سایرین ارزش اظهار شده توسط فرد برنده را خواهند پرداخت (حراج نوع دوم). کالای عمومی عموماً شهروندان بایستی در ساخت و ایجاد یک پروژه عمومی همکاری داشته باشند و پروژه زمانی اجرا خواهد شد که ارزش ایجاد شده برای افراد بیشتر از هزینه تأسیس آن باشد. | ## بخش 3: مکانیزم وی‌سی‌جی | مطابق با مکانیزم مطرح شده، هر فرد در صورت pivotal بودنش بایستی مالیاتی به اندازه اختلاف دو حالت مشارکت و عدم مشارکتش پرداخت کند. با وجود عقلایی بودن، در این روش تراز تجاری برقرار نیست یعنی مخارج بیشتر از هزینه‌ها خواهد بود. سریع‌ترین مسیر این مسئله یک مسئله کمینه‌سازی هزینه است که هدف در آن انتقال پیغام از نقطه‌ای به دیگری در یک شبکه ارتباطی است. هزینه در این انتقال به معنای مدت زمانی است که طول می‌کشد این پیغام انتقال داده شود؛ بنابراین یافتن سریعترین مسیر به معنای یافتن مسیر با کمترین هزینه است. در صورتی که زمان انتقال هر کامپیوتر در شبکه را بدانیم، می‌توان از طریق الگوریتم کوتاه‌ترین مسیر، جواب دلخواه را پیدا کرد. اما مشکل اینجاست که این اطلاعات در دسترس نیست و کامپیوترها برای انگیزه‌های شخصی ممکن است این اطلاعات را اشتباه گزارش کنند. برای حل این مسئله می‌توان از مکانیزم VCGاستفاده کرد که در آن X مجموعه‌ای شامل تمام مسیرهای ممکن رسیدن به هدف است. یعنی هر فرد بایستی به اندازه مجموع زمان انتقال سایر افراد در مسیر انتخابی پول پرداخت کند؛ بنابراین با در نظر گرفتن زمان انتقال خود فرد و با فرض قابل تبدیل بودن زمان به پول، هر فرد به اندازه ارزش کل زمان انقال پیغام در مسیر، هزینه از دست می‌دهد که به معنای یکسو شدن انگیزه‌های فرد و مکانیزم است. به گونه‌ای که هر فرد به اندازه کل زمان انتقال پیام هنگامی که فرد در شبکه حضور نداشت، پول دریافت می‌کند که این مقدار بزرگتر مساوی زمان کل هنگام حضور فرد است؛ بنابراین مطلوبیت هر فرد حداقل به خوبی شرکت نکردن در مکانیزم خواهد بود. تجارت دوجانبه زمانی که یک خریدار و یک فروشنده داشته باشیم و ارزش کالا برای فروشنده و خریدار متفاوت باشد، نیز می‌توان از طریق مکانیزم VCG تجارت یا عدم تجارت را شکل داد و میزان پرداختی توسط هر کدام از طرفین را محاسبه نمود. البته ممکن است تراز بودجه حاصل نشود و جهت پیاده‌سازی مکانیزم مجبور به دادن یارانه شویم. مسائل دیگری مربوط به گراف، برای مثال درخت فراگیر مینیمم یا جورسازی ماکسیمم نیز به طریقی مشابه حل می‌شوند. ارزش این دستگاه برای هر کدام به اندازه ۳۰۰ دلار است اما قیمت دستگاه ۴۰۰ دلار می‌باشد. | ## جمع‌بندی | خواهیم داشت: با توجه به مکانیزم VCGدستگاه خریداری شده و میزان پرداختی توسط هر یک از فرد ۱ و ۲ به اندازه ۱۰۰ واحد می‌باشد.