EUVIMEDEUVIMED entdecken
Crossref

On Fair Division under Heterogeneous Matroid Constraints

Amitay Dror, Michal Feldman, Erel Segal-Halevi

Journal of Artificial Intelligence Research · 11.03.2023 · 76

DOI: 10.1613/jair.1.13779 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 11.03.2023. Verfasst von Amitay Dror und 2 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study fair allocation of indivisible goods among additive agents with feasibility constraints. In these settings, every agent is restricted to get a bundle among a specified set of feasible bundles. Such scenarios have been of great interest to the AI community due to their applicability to real-world problems. Following some impossibility results, we restrict attention to matroid feasibility constraints that capture natural scenarios, such as the allocation of shifts to medical doctors and the allocation of conference papers to referees. We focus on the common fairness notion of envy-freeness up to one good (EF1). Previous algorithms for finding EF1 allocations are either restricted to agents with identical feasibility constraints or allow free disposal of items. An open problem is the existence of EF1 complete allocations among agents who differ both in their valuations and in their feasibility constraints. In this work, we make progress on this problem by providing positive and negative results for several matroid and valuation types. Among other results, we devise polynomial-time algorithms for finding EF1 allocations in the following settings: (i) n agents with heterogeneous (non-identical) binary valuations and partition matroids with heterogeneous capacities; (ii) two agents with heterogeneous additive valuations and partition matroids with heterogeneous capacities; and (iii) three agents with heterogeneous binary valuations and identical base-orderable matroid constraints.

Zitieren

APA

Dror, A., Feldman, M., & Segal-Halevi, E. (2023). On Fair Division under Heterogeneous Matroid Constraints. Journal of Artificial Intelligence Research, 76. https://doi.org/10.1613/jair.1.13779

Vancouver

Dror A, Feldman M, Segal-Halevi E. On Fair Division under Heterogeneous Matroid Constraints. Journal of Artificial Intelligence Research. 2023;76. doi:10.1613/jair.1.13779

BibTeX
@article{Dror2023,
  author = {Dror, Amitay and Feldman, Michal and Segal-Halevi, Erel},
  title = {On Fair Division under Heterogeneous Matroid Constraints},
  journal = {Journal of Artificial Intelligence Research},
  year = {2023},
  volume = {76},
  doi = {10.1613/jair.1.13779}
}
Kostenlos starten →