حراج وی‌سی‌جی

در نظریهٔ حراج، ویکری–کلارک–گروز (وی‌سی‌جی) یک مدل از حراج‌های مهر و موم شده (بی اطلاع از قیمت دیگران) برای چندین کالا است. متقاضیان قیمت‌ها را طبق ارزش گذاری خود برای هر کالا می‌نویسند بدون این که از قیمت‌های دیگر افراد مناقصه خبری داشته باشند. بعد از آن سیستم حراجی کالاها را به صورتی که بهینهٔ اجتماعی باشد توزیع می‌کند. این شیوه باعث می‌شود هر کس به اندازه اثرات جانبی ای که روی بقیه افراد می‌گذارد پرداخت یا دریافت می‌کند.^[۱] این بدین معنی است که فرد برنده باید مطلوبیتی را که در صورت نبودنش به وجود می‌آمد بپردازد. یعنی اگر نفر اول نبود نفر دوم برنده می‌شد و به میزان قیمتی که نوشته بود مطلوبیت کسب می‌کرد پس نفر اول باید هزینه این مطلوبیت از دست رفته را بپردازد. این مدل همچنین به مناقصه گران انگیز می‌دهد تا ارزش واقعی خود را به عنوان قیمت اعلام کنند و تضمین می‌کند که بهترین استراتژی برای مناقصه گران این است که برای هر کالا ارزش واقعی خود را به عنوان قیمت اعلام کنند. این مدل یک مدل تعمیم یافته از مزایده ویکری برای چندین کالا است.^[۲]

این مدل حراج نامش را از ویلیام ویکری،^[۳] ادوارد اچ. کلارک^[۴]و تئودور گروز^[۵] گرفته‌است. آن هم برای مقاله ای که با موفقیت این ایده را گسترش داد.

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

مزایا و معایب

مزایا:

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

معایب:

پیچیدگی: این مکانیز پیچیده‌است و توضیح دادن آن برای شرکت کنندگان به آسانی میسر نیست.
ضرر فروشنده: در این حراج فروشنده به سود بیشینه خود دست نمی‌یابد
امکان تبانی: افراد با تبانی کردند می‌توانند ساختار این حراج را تغییر دهند

توصیف بصری

یک حراجی را در نظر بگیرید که در آن دسته ای از محصولات یکسان در صف فروش هستند (مانند بلیط کنسرت). متقاضیان شرکت کننده در حراج با اعلام کردن قیمت خود برای دریافت N عدد کالا در حراج شرکت می‌کنند. هر فرد می‌تواند قیمت‌های متفاوتی را برای درخواست بیش از یک کالا اعلام کند چون مطلوبیتش(امید مقبولیت) می‌تواند با زیاد شدن آن کالا تغییر کند (مثلاً فردی دو بلیط می‌خواهد و برای بلیط اول حاضر است ۱۰۰ تومان بدهد اما برای بلیط دوم بیشتر از ۸۰ تومان نمی‌دهد). شرکت کنندگان نمی‌توانند قیمت بقیهٔ متقاضیات را ببینند چون این حراج مهر و موم شده‌است (تنها سامانهٔ حراجی به قیمت هی اعلام شده دسترسی دارد) زمانی که تمام قیمت‌ها اعلام شد، حراج بسته می‌شود.

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

ضرر وارد شده به بقیه افراد (که میزان پرداختی افراد برنده شده حراج نیز هست) بدین صورت محاسبه می‌شود: میزان پرداختی نفر iام = (کل رفاه بهینه سایرین در صورت نبودن نفر iام) - (کل رفاه بهینه کنونی سایرین که نفر iام شرکت کرده‌است) مثلاً در صورتی که حراجی تنها یک برنده داشته باشد واضح است که کل رفاه سایرین در صورت شرکت نفر iام (که فرد بنده است) صفر می‌شود چون چیزی به آن‌ها نرسیده پس نفر iام باید به اندازه قیمت پیشنهادی نفر بعدی اش پرداخت کند.

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

سازگار با انگیزه‌ها

در این روش افراد استراتژی غلبه خود را در صداقت در اعلام ارزش‌های خود می‌بینند. برای نشان دادن این مسئله کافی است در دو حالت «برنده» و «بازنده» انگیزه دروغ گفتن را بررسی کنیم در هر حالت فرد می‌تواند قیمت بیشتر یا کمتری را اعلام کند:

برنده:

قیمت بیشتری اعلام کند: در این حالت هیچ تفاوتی برای فرد نمی‌کند پس انگیزه ای برای این کار ندارد
قیمت کمتری اعلام کند: اگر قیمتش بیشتر از بیشینه بازنده‌ها شود که فرقی برای فرد نمی‌کند اگر هم کمتر از آن شود، فرد کالا را نمی‌برد و ضرر می‌کند پس در هر حالت منطقی نیست که قیمتی کمتر اعلام کند

بازنده:

قیمت بیشتر اعلام کند: اگر قیمت اعلام شده کمتر از کمینهٔ برنده‌ها باشد که فرقی نمی‌کند اما اگر بیشتر از آن باشد فرد مجبور است کالا را با قیمت کمینه برنده‌های واقعی بخرد که بیشتر از ارزش واقعی خود اوست پس ضرر می‌کند در نتیجه منطقی نیست که قیمت بیشتری اعلام کند
قیمت کمتری اعلام کند: در این حالت هیچ تفاوتی برای فرد نمی‌کند پس انگیزه ای برای این کار ندارد

شرح رسمی

نشانه‌ها

برای تمام کالاهای حراجی $M=\{t_{1},\ldots ,t_{m}\}$ و تمام مجموعه متقاضیان $N=\{b_{1},\ldots ,b_{n}\}$ ، اجازه دهید $V_{N}^{M}$ مطلوبیت اجتماعی ای باشد که از VCG در یک ترکیب حراجی به دست می‌آید. مطلوبیت اجتماعی یعنی جمع ارزش‌هایی که افراد برنده به اجناسی که خواسته بودند نسبت داده‌اند. اگر کسی کالایی را به دست نیاورده باشد مطلوبیت کسب کرده از آن صفر است. برای متقاضی $b_{i}$ و کالای $t_{j}$ ، فرض می‌کنیم ارزش قیمت اعلام شده برای آن کالا $v_{i}(t_{j})$ باشد. نشانهٔ $A\setminus B$ یعنی عناصری از A که جز عناصر B نیستند.^[۶]

وظیفه

متقاضی $b_{i}$ که برای کالای $t_{j}$ تقاضا کرده و برنده شده. به اسم $v_{i}(t_{j})$ ، برنده می‌شود اما ملغ پرداختی $V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}$ خواهد بود که همان ضرر اجتماعی ای است که این متقاضی با برنده شدن خود به بقیه جامعه وارد کرده.

توضیح

در حقیقت، مجموعهٔ افراد بدون $b_{i}$ مجموعه $N\setminus \{b_{i}\}$ است. وقتی کالای $t_{j}$ موجود بود جامعه می‌توانست مطلوبیت $V_{N\setminus \{b_{i}\}}^{M}$ را به دست آورد. پس برنده شدن این کالا به وسیلهٔ $b_{i}$ مجموعهٔ کالاهای موجود را به $M\setminus \{t_{j}\}$ کوچک کرد. در هر صورت مطلوبیتی که اکنون قالب دست یابی است $V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}$ . است. تفریق این دو مقدار تفاوت سطح مطلوبیت‌ها و ضرری که این فرد با شرکت خود به مطلوبیت جامعه زده را نشان می‌دهد و این فرد به همین اندازه باید بپردازد.

مطلوبیت برنده

فرد بنده که ارزش واقعی $A$ را برای کالای $t_{j}$ ، $v_{i}(t_{j})=A,$ اعلام کرده بود. مطلوبیتی که به دست می‌آورد به این اندازه است $A-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right).$

مثال‌ها

مثال #۱

فرض کنید که دو سیب برای سه خریدار در صف فروش هستند.

متقاضی اول یک سیب می‌خواهد و حاضر است ۵ تومان برای آن بپردازد.
متقاضی دوم یک سیب می‌خواهد و حاضر است ۲ تومان برای آن بپردازد.
متقاضی سوم دو سیب می‌خواهد و حاضر است برای جفت آن‌ها ۶ تومان بپردازد اما به هیچ وجه نمی‌خواهد یک دانه سیب بخرد و حتماً دو عدد می‌خواهد.

اول، بیشینه مطلوبیت‌ها را حساب می‌کنیم: اگر سیب اول را به A و سیب دوم را به B بدهیم مطلوبیت ۵ + ۲ = ۷ تومان می‌شود اما اگر همین دو سیب را به C بدهیم مطلوبیت ۶ را به دست می‌آوردیم که کمتر از ۷ است. پس برنده این حراجی A و B می‌شوند. مطلوبیت هر فرد می‌شود: A با مطلوبیت ۵ و B با مطلوبیت ۲ و C با مطلوبیت ۰ چون هیچ چیزی نسیبش نشده. دقت کنید که این مسئله نوعی مسئلهٔ کوله پشتی است.

بعد، ما مبلغ پرداختی هر فرد را محاسبه می‌کنیم:

برای A داریم: اگر در حال حاضر مطلوبیت بقیه را بدون A در نظر بگیم می‌شود (۲ + ۰ = ۲ تومان) زیرا B مطلوبیت ۲ تومان دارد و C مطلوبیت ۰ تومان. حال اگر A را حذف کنیم و مطلوبیت را در حالی که A وجود نداشت محاسبه کنیم داریم: «اگر A نبود دو سیب به C می‌رسید پس مطلوبیت ۶ تومان می‌شد» حل مبلغ پرداختی A می‌شود ۲–۶ = ۴ تومان.
برای B داریم: اگر در حال حاضر مطلوبیت بقیه را بدون B در نظر بگیم می‌شود (۵ + ۰ = ۲۵ تومان) زیرا A مطلوبیت ۲ تومان دارد و C مطلوبیت ۰ تومان. حال اگر A را حذف کنیم و مطلوبیت را در حالی که B وجود نداشت محاسبه کنیم داریم: «اگر B نبود دو سیب به C می‌رسید پس مطلوبیت ۶ تومان می‌شد» حل مبلغ پرداختی B می‌شود ۵–۶ = ۱ تومان.
برای C داریم: حذف C هیچ فرقی در مطلوبیت نمی‌کند چون چیزی برنده نشده‌است. پس به وضوح صفر تومان می‌باشد.

بعد از این حراج A یک تومان سود کرده (جای ۵ تومان تنها ۴ تومان پول داده) و B هم یک تومان سود کرده (جای ۲ تومان تنها ۱ تومان پول داده) و C هم هیچ فرقی برایش نداشته‌است.

مثال #۲

فرض کنید که دو متقاضی داریم $b_{1}$ و $b_{2}$ ، دو کالا، $t_{1}$ و $t_{2}$ ، و هر متقاضی بتواند تنها یک کالا را صاحب شود. فرض کنید $v_{i,j}$ ارزش متقاضی $b_{i}$ برای کالای $t_{j}$ باشد. فرض کنید: $v_{1,1}=10$ ، $v_{1,2}=5$ ، $v_{2,1}=5$ ، و $v_{2,2}=3$ می‌تواند دید که هر دو متقاضی $b_{1}$ و $b_{2}$ کالای $t_{1}$ را بیشتر می‌خواهند، در هر صورت با بیشینه کردن مطلوبیت اجتماعی داریم که کالای $t_{1}$ به متقاضی $b_{1}$ تعلق می‌گیرد (چون مطلوبیتش ۱۰ است) و کالای $t_{2}$ به متقاضی $b_{2}$ تعلق می‌گیرد (چون مطلوبیتش ۳ است). پس مطلوبیت نهایی ۱۰ + ۳ = ۱۳ می‌شود که بیشینه است.

اگر متقاضی $b_{2}$ در این حراج نبود، متقاضی $b_{1}$ باز هم کالای $t_{1}$ را به دست می‌آورد و نفر $b_{1}$ چیزی به دست نمی‌آورد. مطلوبیت فعلی $10$ است و چون بود و نبود $b_{2}$ تفاوتی ایجاد نمی‌کند. مقدار پرداختی این فرد $10-10=0$ است.

اگر متقاضی $b_{1}$ در این حراج نبود، کالای $t_{1}$ به دست $b_{2}$ می‌رسید و ارزش $5$ را داشت. مطلوبیت فعلی بدون نفر اول ۳ است پس نفر $b_{1}$ مقدار $5-3=2$ باید پرداخت کند.

اثبات رسمی بهینه بودن صداقت

در زیر اثبات این که بای هر فرد بهتر است ارزش واقعی خود را گزارش کند را می‌بینیم.^[۷]

برای هر متقاضی $b_{i}$ فرض کنید $v_{i}$ ارزش حقیقی او برای کالای $t_{i}$ باشد؛ و فرض کنید $b_{i}$ کالای $t_{i}$ را در صورت نوشتن مقدار حقیقی خود می‌برد. پس برای شبکهٔ مطلوبیت $U_{i}$ داریم:

{\begin{aligned}U_{i}&=v_{i}-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right)\\&=\sum _{j}v_{j}-\sum _{j\neq i}v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}}^{M}\end{aligned}}

.

از آن جا که $V_{N\setminus \{b_{i}\}}^{M}$ مستقل از $v_{i}$ است. بیشینه کردن شبکهٔ مطلوبیت برابر است با بیشینه کردن $\sum _{j}v_{j}$ که تنها قیمت پیشنهادی خود او $v_{i}$ در اختیارش است. اما اگر این قیمت را تغییر دهد در مطلوبیتش تغییری ایجاد نمی‌شود زیرا در محاسبه مطلوبیت، ارزش واقعی آن برایش محاسبه می‌شود نه ارزش تقلبی.

جستارهای وابسته

منابع

↑ von Ahn, Luis (2011-10-13). "Sponsored Search" (PDF). 15–396: Science of the Web Course Notes. Carnegie Mellon University. Archived from the original on 6 March 2015. Retrieved 2015-04-13. {{cite web}}: Cite has empty unknown parameter: |coauthors= (help)نگهداری یادکرد:ربات:وضعیت نامعلوم پیوند اصلی (link)
↑ Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
↑ Vickrey, William (1961). "Counterspeculation, Auctions, and Competitive Sealed Tenders". The Journal of Finance. 16 (1): 8–37. doi:10.1111/j.1540-6261.1961.tb02789.x.
↑ Clarke, E. (1971). "Multipart Pricing of Public Goods". Public Choice. 11 (1): 17–33. doi:10.1007/bf01726210.
↑ Groves, T. (1973). "Incentives in Teams". Econometrica. 41 (4): 617–631. doi:10.2307/1914085.
↑ Avrim Blum (February 28, 2013). "Algorithms, Games, and Networks - Lecture 14" (PDF). Retrieved 28 December 2015.
↑ http://www.cs.cmu.edu/~arielpro/15896/docs/notes14.pdf

[1] von Ahn, Luis (2011-10-13). "Sponsored Search" (PDF). 15–396: Science of the Web Course Notes. Carnegie Mellon University. Archived from the original on 6 March 2015. Retrieved 2015-04-13. {{cite web}}: Cite has empty unknown parameter: |coauthors= (help)نگهداری یادکرد:ربات:وضعیت نامعلوم پیوند اصلی (link)

[AGT07-2] Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.

[3] Vickrey, William (1961). "Counterspeculation, Auctions, and Competitive Sealed Tenders". The Journal of Finance. 16 (1): 8–37. doi:10.1111/j.1540-6261.1961.tb02789.x.

[4] Clarke, E. (1971). "Multipart Pricing of Public Goods". Public Choice. 11 (1): 17–33. doi:10.1007/bf01726210.

[5] Groves, T. (1973). "Incentives in Teams". Econometrica. 41 (4): 617–631. doi:10.2307/1914085.

[6] Avrim Blum (February 28, 2013). "Algorithms, Games, and Networks - Lecture 14" (PDF). Retrieved 28 December 2015.

[7] ttp://www.cs.cmu.edu/~arielpro/15896/docs/notes14.pdf

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]