view in publisher's site

How to Fairly Allocate Indivisible Resources Among Agents Having Lexicographic Subadditive Utilities

How can one fairly assign a finite set of m indivisible items between n agents? This question has been extensively studied last few decades with a focus on structure of utility functions representing the agent’s preferences over subsets of items. This paper considers a scenario where all agents’ utility functions are lexicographic and subadditive. In this setting, each agent has a linear order over single items, and this order is then extended to a total order over all subsets of items using the lexicographic order. Every agent is equipped with a utility function consistent with her lexicographic preference, which is either additive or, more general, subadditive. Our task is to determine a fair allocation in the sense that the minimum utility over all agents or the product of individual utilities is maximized. As a result, we obtain 1/2-approximation algorithms for both problems with lexicographic subadditive functions. In addition, we show that the factor of 1/2 is tight for the former problem, but is not for the latter one.

چگونه می توان منابع Indivisible را در میان نمایندگان ایجاد کرد.

ترجمه شده با

Download PDF سفارش ترجمه این مقاله این مقاله را خودتان با کمک ترجمه کنید
سفارش ترجمه مقاله و کتاب - شروع کنید

95/12/18 - با استفاده از افزونه دانلود فایرفاکس و کروم٬ چکیده مقالات به صورت خودکار تشخیص داده شده و دکمه دانلود فری‌پیپر در صفحه چکیده نمایش داده می شود.