کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5071601 | 1477067 | 2015 | 31 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Limitations of randomized mechanisms for combinatorial auctions
ترجمه فارسی عنوان
محدودیت های مکانیزم های تصادفی برای مزایده های ترکیبی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
علوم انسانی و اجتماعی
اقتصاد، اقتصادسنجی و امور مالی
اقتصاد و اقتصادسنجی
چکیده انگلیسی
We prove that this is not the case: There is a constant γ>0 such that there is no randomized mechanism that is truthful-in-expectation - or even approximately truthful-in-expectation - and guarantees an mâγ-approximation to the optimal social welfare for combinatorial auctions with submodular valuations in the value oracle model. In contrast, a non-truthful (1â1/e)-approximation algorithm is known (Vondrák, 2008), and a truthful-in-expectation (1â1/e)-approximation mechanism was recently developed for the special case of coverage valuations (Dughmi et al., 2011b). We also prove an analogous result for the combinatorial public projects (CPP) problem. Both our results present a significant separation between coverage functions and submodular functions, which does not occur for these problems without strategic considerations.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Games and Economic Behavior - Volume 92, July 2015, Pages 370-400
Journal: Games and Economic Behavior - Volume 92, July 2015, Pages 370-400
نویسندگان
Shaddin Dughmi, Jan Vondrák,