دانلود مقاله ISI انگلیسی شماره 101705
ترجمه فارسی عنوان مقاله

حقیقت با داوطلبان به حداکثر رساندن ارزش: در حدود تقریبی در بازارهای ترکیبی

عنوان انگلیسی
Truthfulness with value-maximizing bidders: On the limits of approximation in combinatorial markets
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
101705 2017 11 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : European Journal of Operational Research, Volume 260, Issue 2, 16 July 2017, Pages 767-777

ترجمه کلمات کلیدی
مزایده / مزایده، نظریه بازی، مکانیزم تقریبی
کلمات کلیدی انگلیسی
Auctions/bidding; Game theory; Approximation mechanisms;
پیش نمایش مقاله
پیش نمایش مقاله  حقیقت با داوطلبان به حداکثر رساندن ارزش: در حدود تقریبی در بازارهای ترکیبی

چکیده انگلیسی

In some markets bidders want to maximize value subject to a budget constraint rather than payoff. This is different to the quasilinear utility functions typically assumed in auction theory and leads to different strategies and outcomes. We refer to bidders who maximize value as value bidders. While simple single-object auction formats are truthful, standard multi-object auction formats allow for manipulation. It is straightforward to show that there cannot be a truthful and revenue-maximizing deterministic auction mechanism with value bidders and general valuations. Approximation has been used as remedy to achieve truthfulness on other mechanism design problems, and we study which approximation ratios we can get from truthful mechanisms. We show that the approximation ratio that can be achieved with a deterministic and truthful approximation mechanism with n bidders cannot be higher than 1/n for general valuations. For randomized approximation mechanisms there is a framework with a ratio that is tight.