EUVIMEDEUVIMED entdecken
Crossref

Multivariate algorithmics for eliminating envy by donating goods

Niclas Boehmer, Robert Bredereck, Klaus Heeger, Dušan Knop, Junjie Luo

Autonomous Agents and Multi-Agent Systems · 2024-12 · 38 (2)

DOI: 10.1007/s10458-024-09674-5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Autonomous Agents and Multi-Agent Systems, online erschienen am 09.09.2024. Verfasst von Niclas Boehmer und 4 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 34 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft, OP VVV MEYS, Ministry of Education - Singapore.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary-encoded and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

Förderung

  • Deutsche Forschungsgemeinschaft
  • OP VVV MEYS
  • Ministry of Education - Singapore
  • Talent Fund of Beijing Jiaotong University

Zitieren

APA

Boehmer, N., Bredereck, R., Heeger, K., Knop, D., & Luo, J. (2024). Multivariate algorithmics for eliminating envy by donating goods. Autonomous Agents and Multi-Agent Systems, 38(2). https://doi.org/10.1007/s10458-024-09674-5

Vancouver

Boehmer N, Bredereck R, Heeger K, Knop D, Luo J. Multivariate algorithmics for eliminating envy by donating goods. Autonomous Agents and Multi-Agent Systems. 2024;38(2). doi:10.1007/s10458-024-09674-5

BibTeX
@article{Boehmer2024,
  author = {Boehmer, Niclas and Bredereck, Robert and Heeger, Klaus and Knop, Dušan and Luo, Junjie},
  title = {Multivariate algorithmics for eliminating envy by donating goods},
  journal = {Autonomous Agents and Multi-Agent Systems},
  year = {2024},
  volume = {38},
  number = {2},
  doi = {10.1007/s10458-024-09674-5}
}
Kostenlos starten →