کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418683 681709 2014 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods
ترجمه فارسی عنوان
کم کردن حسادت و به حداکثر رساندن رفاه عمومی اجتماعی نها در تخصیص کالاهای تقسیم شده
کلمات کلیدی
تخصیص منابع، عوامل اقتصادی انگیزه، تقریب پذیری
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Envy-freeness is a desirable criterion when one wishes to fairly distribute a finite set of goods among two or more agents. Unfortunately, allocations satisfying this criterion may not exist in the setting where the goods are assumed to be indivisible. In this case, it is useful to settle for allocations with envy as small as possible. Adapting the framework of Chevaleyre et al. (2007), we propose a multiplicative form of the degree of envy of a given allocation and then study the approximability of the corresponding envy minimization problems. We show that these problems are APX-hard to approximate in general, but admit an FPTAS for a fixed number of agents with additive utility functions. We also present a polynomial-time algorithm for the case when the number of agents is equal to the number of goods to be distributed. In addition, we study the problem of maximizing social welfare by the average Nash product. We provide a fast greedy approximation algorithm for this problem when the agents’ utility functions are (sub)additive, and we design a PTAS for the case when all agents have the same additive utility function.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 179, 31 December 2014, Pages 54–68
نویسندگان
, ,