کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
376883 658329 2014 22 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Better redistribution with inefficient allocation in multi-unit auctions
ترجمه فارسی عنوان
توزیع مجدد بهتر با تخصیص ناکارآمد در مزایده های چند واحد
کلمات کلیدی
طراحی مکانیسم، مکانیزم ویکری-کلارک-گروس، توزیع مجدد پرداخت
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی

For the problem of allocating one or more items among a group of competing agents, the Vickrey–Clarke–Groves (VCG) mechanism is strategy-proof and efficient. However, the VCG mechanism is not strongly budget balanced: in general, value flows out of the system of agents in the form of VCG payments, which reduces the agents' utilities. In many settings, the objective is to maximize the sum of the agents' utilities (taking payments into account). For this purpose, several VCG redistribution mechanisms have been proposed that redistribute a large fraction of the VCG payments back to the agents, in a way that maintains strategy-proofness and the non-deficit property. Unfortunately, sometimes even the best VCG redistribution mechanism fails to redistribute a substantial fraction of the VCG payments. This results in a low total utility for the agents, even though the items are allocated efficiently. In this paper, we study strategy-proof allocation mechanisms that do not always allocate the items efficiently. It turns out that by allocating inefficiently, more payment can sometimes be redistributed, so that the net effect is an increase in the sum of the agents' utilities.Our objective is to design mechanisms that are competitive against the first-best mechanism in terms of the agents' total utility. We first study multi-unit auctions with unit demand. We characterize the family of linear allocation mechanisms. We propose an optimization technique for simultaneously finding a linear allocation mechanism and a payment redistribution rule, which together are optimal. With the help of this technique, we also analytically characterize several competitive mechanisms, which are based on burning units and partitioning the agents into groups. Finally, we extend the definition of linear allocation mechanisms and the optimization technique to general multi-unit auctions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 216, November 2014, Pages 287–308
نویسندگان
, ,