کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10368031 | 873912 | 2005 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximately-strategyproof and tractable multiunit auctions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
سیستم های اطلاعاتی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We present an approximately-efficient and approximately-strategyproof auction mechanism for a single-good multiunit allocation problem. The bidding language allows marginal-decreasing piecewise-constant curves and quantity-based side constraints. We develop a fully polynomial-time approximation scheme for the multiunit allocation problem, which computes a (1+ε) approximation in worst-case time T=O(n3/ε), given n bids each with a constant number of pieces. We integrate this approximation scheme within a Vickrey-Clarke-Groves (VCG) mechanism and compute payments for an asymptotic cost of O(T log n). The maximal possible gain from manipulation to a bidder in the combined scheme is bounded by εV/(1+ε), where V is the total surplus in the efficient outcome.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Decision Support Systems - Volume 39, Issue 1, March 2005, Pages 105-121
Journal: Decision Support Systems - Volume 39, Issue 1, March 2005, Pages 105-121
نویسندگان
Anshul Kothari, David C. Parkes, Subhash Suri,