طراحی مکانیزم‌های توزیع شده

http://theory.ce.sharif.edu/images/pdf/MrAsgharian.pdf

ٰVickrey auction: همان حراج دومین قیمت است که هیچ کس پیشنهاد بقیه را نمی‌بیند و کسی که بیشترین پیشنهاد را داده برنده می‌شود ولی قیمت نفر قبل از خودش را می‌پردازد.

Vickrey-Clarke-Groves (VCG): حراج دومین قیمت برای یک جنس تعریف شده است. اگر بخواهیم چند جنس را بفروشیم از این مدل استفاده می‌شود. uniform price auction یا حراج با قیمت یکنواخت، جمع سود و زیان خرید هر جنس را برای هر نفر ملاک قرار می‌دهد و هر جنس را مثل حراج دومین قیمت می‌فروشد.

هر دوی این روشها تضمین راستگویی را دارند، یعنی اگر کسی قیمت نادرست بگوید ضرر می‌کند.

http://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves_auction

مکانیزم توزیع شده‌ی VCG: توی این مقاله انگار هر کسی یک توان پردازشی دارد و می‌خواهد یک سری کار را اختصاص بدهد.

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

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

(حالا کاری که ملت می‌کنند این است که در مورد توان پردازشی‌شان راست نمی‌گویند و مثلاً می‌توانند باعث شوند یک نفر که کمتر از بقیه گفته است کلاً حذف شود.)

http://www.eecs.harvard.edu/econcs/pubs/distr_vcg.pdf

انگار ثابت کرده است که برای مجموع سود افراد (VCG) بهترین کار راستگوییه. :)