Πλοήγηση ανά Συγγραφέα "Ntokos, Apostolos"

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Α Β Γ Δ Ε Ζ Η Θ Ι Κ Λ Μ Ν Ξ Ο Π Ρ Σ Τ Υ Φ Χ Ψ Ω

Τώρα δείχνει 1 - 1 από 1

Algorithms for fair division with indivisible items
(2019-07-01) Ντόκος, Απόστολος; Ntokos, Apostolos; Athens University of Economics and Business, Department of Informatics; Κουτσόπουλος, Ιορδάνης; Τελέλης, Ορέστης; Μαρκάκης, Ευάγγελος
The theory of fair division addresses the fundamental problem of allocating goods, items,tasks or chores among agents in a fair and efficient manner. Such problems arise in many real-world settings such as government auctions or divorce settlements. To model such allocationproblems, one needs to specify the preferences of the agents, and the fairness criterion. Forthe preferences, the usual assumption is to associate each agent with an additive valuationfunction on a set of goods. As for fairness criteria, two of the classic notions that have beenproposed are:• proportionality: A proportional division is a division of a resource among n agents suchthat each agent receives a part worth for him at least a 1/n fraction of the whole, wheren is the number of the agents.• envy-freeness: Envy-freeness requires that each agent prefers her own allocation overthat of any other agent.The envy-freeness notion is stronger than proportionality. For the divisible setting of the prob-lem, it has been proved that there always exists an allocation that is envy-free. Unfortunately,these results do not extend to the setting of indivisible goods. In fact, many of the classicalsolution concepts and algorithms that have been developed for divisible goods are not directlyapplicable to indivisible goods. Existence of envy-free allocations cannot be guaranteed andthe relevant algorithmic and approximability questions are also computationally hard. Theseconsiderations have motivated recent work in theoretical computer science on developing rel-evant relaxed notions of fairness. Four such notions are: envy-freeness up to one good (EF1),envy-freeness up to any good (EFX), maximin share fairness (MMS) and pairwise maximinshare fairness (PMMS). These relaxations of envy-freeness seem more appropriate for settingswith indivisible items. All these capture different ways of allowing envy in an allocation. Inthis work, we will mainly focus on the EFX relaxation and we investigate further the issuesof existence and computation. We show that in some special cases an EFX allocation can befound using polynomial time algorithms. We also examine experimentally how often an EFXallocation is also envy-free and how often an EF1 allocation is EFX, too. Finally, we examinehow the number of agents and items affects the existence of EFX allocations.