Skip to content
بازگشت به نتایج جست‌وجو

مکانیزم VCG

معرفی‌شده توسط
William Vickrey, Edward Clarke, Theodore Groves
سال
1961
نوع
algorithm
خانواده
Game-theoretic

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

مکانیزم ویکری-کلارک-گرووز (VCG) یک راهکار طراحی سازوکار صادقانه است که منابع را تخصیص می‌دهد و پرداخت‌ها را تعیین می‌کند تا مشارکت‌کنندگان را به افشای ارزش‌گذاری‌های واقعی خود تشویق کند. این مکانیزم با تکیه بر کار ویلیام ویکری در سال ۱۹۶۱ در مورد حراج پیشنهادهای بسته و گسترش یافته توسط کلارک و گرووز، تضمین می‌کند که گزارش حقیقت یک استراتژی غالب برای همه مشارکت‌کنندگان است، که منجر به کارایی تخصیص و حداکثر کردن مازاد کل می‌شود.

شهود پشت روش

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

تاریخ

ویلیام ویکری حراج پیشنهاد بسته قیمت دوم (حراج ویکری) را در سال ۱۹۶۱ معرفی کرد و اثبات کرد که پیشنهاد صادقانه را استخراج می‌کند. ادوارد کلارک و تئودور گرووز به طور مستقل این اصل را به سازوکارهای تخصیص عمومی‌تر با پرداخت‌های مبتنی بر اثرات خارجی گسترش دادند. مشارکت‌های آن‌ها اساس نظریه مدرن طراحی سازوکار را تشکیل داد، که باعث شد ویکری جایزه نوبل اقتصاد را در سال ۱۹۹۶ (پس از مرگ) دریافت کند و تأثیر عمیقی بر طراحی حراج در عمل، به ویژه حراج‌های طیف و بازارهای تبلیغات آنلاین گذاشت.

چه زمانی استفاده شود

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

محدودیت‌ها و ملاحظات

  • از نظر محاسباتی برای تعداد زیادی قلم یا مشارکت‌کننده غیرقابل حل است، که تعیین برنده را NP-hard می‌کند.
  • اغلب منجر به کسری می‌شود (پرداخت‌ها از درآمد فراتر می‌رود)، که در برخی کاربردها به یارانه نیاز دارد.
  • در برابر تبانی یا ورود/خروج پیشنهاددهنده آسیب‌پذیر است اگر به دقت نظارت نشود.
  • ممکن است برای مشارکت‌کنندگان غیرقابل درک باشد، که باعث کاهش پذیرش در محیط‌های عملی می‌شود.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

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

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

درخواست پیشنهادهای بسته یا ارزش‌گذاری از همه مشارکت‌کنندگان بدون افشای اطلاعات به سایر مشارکت‌کنندگان.

2

تعیین تخصیص کارآمد با انتخاب نتیجه‌ای که مازاد کل (مجموع ارزش‌گذاری‌های همه مشارکت‌کنندگان) را به حداکثر می‌رساند.

3

تعیین پرداخت هر مشارکت‌کننده برابر با ضرری که به دیگران تحمیل می‌کند: یعنی آنچه دیگران در صورت عدم حضور مشارکت‌کننده به دست می‌آوردند.

4

تأیید اینکه هیچ مشارکت‌کننده‌ای نمی‌تواند مازاد خود را با گزارش نادرست ارزش‌گذاری خود، با فرض گزارش‌های صادقانه دیگران، افزایش دهد.

دام‌های رایج

  • فرض قابلیت حل محاسباتی برای مسائل پیچیده تخصیص؛ یافتن تخصیص‌های کارآمد برای حراج‌های ترکیبی NP-hard است.
  • اشتباه گرفتن VCG با حراج‌های قیمت اول؛ VCG از قیمت‌گذاری مبتنی بر سود استفاده می‌کند، نه قیمت‌گذاری مبتنی بر پیشنهاد.
  • نادیده گرفتن اینکه VCG به حقیقت در ارزش‌گذاری‌ها انگیزه می‌دهد اما نه به ابعاد استراتژیک دیگر (ورود، تبانی).
  • فراموش کردن اینکه کارایی جهانی است، نه محلی؛ اگر پیشنهادات منعکس‌کننده ارزش‌گذاری‌های واقعی نباشند، تخصیص نادرست رخ می‌دهد.

پرسش‌های متداول

چرا مکانیزم VCG در حراج‌های تک قلمی، قیمت ویکری (قیمت دوم) را دریافت می‌کند؟

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

چه زمانی مکانیزم VCG درآمد-بیشینه‌ساز نیست؟

VCG کارایی تخصیص و صداقت را بر حداکثر کردن درآمد اولویت می‌دهد. در برخی موارد، کسری ایجاد می‌کند. حراج‌های قیمت اول ممکن است درآمد بیشتری ایجاد کنند، اما به قیمت پیشنهاد غیرصادقانه.

VCG چگونه حراج‌های ترکیبی با اقلام زیاد را مدیریت می‌کند؟

VCG بسته‌ها را برای حداکثر کردن مازاد کل تخصیص می‌دهد، اما محاسبه تخصیص‌های بهینه NP-hard است. پیاده‌سازی‌های عملی از الگوریتم‌های تقریبی استفاده می‌کنند یا پیچیدگی پیشنهادات مجاز را محدود می‌کنند (به عنوان مثال، تعیین محدودیت برای اندازه‌های بسته).

روش‌های مرتبط

منابع

  1. Vickrey, W. (1961). Counterspeculation, auctions, and competitive sealed bids. The Journal of Finance, 16(1), 8-37.

    باز کردن مرجع DOI
    کپی شد.
  2. Clarke, E. H. (1971). Multipart pricing of public goods. Public Choice, 11(1), 17-33.

    باز کردن مرجع DOI
    کپی شد.