EUVIMEDEUVIMED entdecken
Crossref

Weighted Envy-freeness in Indivisible Item Allocation

Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, Yair Zick

ACM Transactions on Economics and Computation · 30.09.2021 · 9 (3) · 1-39

DOI: 10.1145/3457166 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, online erschienen am 16.08.2021. Verfasst von Mithun Chakraborty und 3 weiteren Autor:innen. Die Arbeit wurde bisher 37-mal zitiert (Crossref) und nennt 50 Literaturangaben. Gefördert von: Singapore NRF Research Fellowship, European Research Council, KAKENHI Grant-in-Aid for JSPS Fellows.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1): strong , where envy can be eliminated by removing an item from the envied agent’s bundle, and weak , where envy can be eliminated either by removing an item (as in the strong version) or by replicating an item from the envied agent’s bundle in the envying agent’s bundle. We show that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists and can be computed in pseudo-polynomial time; moreover, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1, but it always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence algorithm produces in polynomial time a strongly WEF1 allocation for an arbitrary number of agents; for two agents, we can efficiently achieve both strong WEF1 and Pareto optimality by adapting the adjusted winner procedure. Our work highlights several aspects in which weighted fair division is richer and more challenging than its unweighted counterpart.

Förderung

  • Singapore NRF Research Fellowship
  • European Research Council
  • KAKENHI Grant-in-Aid for JSPS Fellows
  • JST, ACT-X
  • Singapore Ministry of Education

Zitieren

APA

Chakraborty, M., Igarashi, A., Suksompong, W., & Zick, Y. (2021). Weighted Envy-freeness in Indivisible Item Allocation. ACM Transactions on Economics and Computation, 9(3), 1-39. https://doi.org/10.1145/3457166

Vancouver

Chakraborty M, Igarashi A, Suksompong W, Zick Y. Weighted Envy-freeness in Indivisible Item Allocation. ACM Transactions on Economics and Computation. 2021;9(3):1-39. doi:10.1145/3457166

BibTeX
@article{Chakraborty2021,
  author = {Chakraborty, Mithun and Igarashi, Ayumi and Suksompong, Warut and Zick, Yair},
  title = {Weighted Envy-freeness in Indivisible Item Allocation},
  journal = {ACM Transactions on Economics and Computation},
  year = {2021},
  volume = {9},
  number = {3},
  pages = {1--39},
  doi = {10.1145/3457166}
}
Kostenlos starten →