Weighted Fairness Notions for Indivisible Items Revisited
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909307627372544 |
|---|---|
| author | Chakraborty, Mithun Segal-Halevi, Erel Suksompong, Warut |
| author_facet | Chakraborty, Mithun Segal-Halevi, Erel Suksompong, Warut |
| contents | We revisit the setting of fairly allocating indivisible items when agents have different weights representing their entitlements. First, we propose a parameterized family of relaxations for weighted envy-freeness and the same for weighted proportionality; the parameters indicate whether smaller-weight or larger-weight agents should be given a higher priority. We show that each notion in these families can always be satisfied, but any two cannot necessarily be fulfilled simultaneously. We then introduce an intuitive weighted generalization of maximin share fairness and establish the optimal approximation of it that can be guaranteed. Furthermore, we characterize the implication relations between the various weighted fairness notions introduced in this and prior work, and relate them to the lower and upper quota axioms from apportionment. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2112_04166 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Weighted Fairness Notions for Indivisible Items Revisited Chakraborty, Mithun Segal-Halevi, Erel Suksompong, Warut Computer Science and Game Theory Theoretical Economics We revisit the setting of fairly allocating indivisible items when agents have different weights representing their entitlements. First, we propose a parameterized family of relaxations for weighted envy-freeness and the same for weighted proportionality; the parameters indicate whether smaller-weight or larger-weight agents should be given a higher priority. We show that each notion in these families can always be satisfied, but any two cannot necessarily be fulfilled simultaneously. We then introduce an intuitive weighted generalization of maximin share fairness and establish the optimal approximation of it that can be guaranteed. Furthermore, we characterize the implication relations between the various weighted fairness notions introduced in this and prior work, and relate them to the lower and upper quota axioms from apportionment. |
| title | Weighted Fairness Notions for Indivisible Items Revisited |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2112.04166 |