Algorithmically Fair Maximization of Multiple Submodular Objective Functions
Rattachement africain : gr, gb, kr, it, nl. Niveau de preuve : code pays fourni par la source.
Le résumé fourni par la source
Constrained maximization of submodular functions poses a central problem in combinatorial optimization. In many realistic scenarios, a number of agents need to maximize multiple submodular objectives over the same ground set. We study such a setting, where the different solutions must be disjoint, and thus, questions of algorithmic fairness arise. Inspired from the fair division literature, we suggest a simple round-robin protocol, where agents are allowed to build their solutions one item at a time by taking turns. Unlike what is typical in fair division, however, the prime goal here is to provide a fair algorithmic environment; each agent is allowed to use any algorithm for constructing their respective solutions. We show that just by following simple greedy policies, agents have solid guarantees for both monotone and non-monotone objectives, and for combinatorial constraints as general as p-systems (which capture cardinality and matroid intersection constraints). In the monotone case, our results include the first approximate EF1-type guarantees under such general constraints. Further, although following a greedy policy may not be generally optimal, we show that consistently performing better than that is computationally hard.
Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.
Le contrôle bibliographique ouvert
DOI retrouvé dans Crossref DOI retrouvé ; titre concordant.
- Titre Crossref
- Algorithmically Fair Maximization of Multiple Submodular Objective Functions
- Date Crossref
- 28/05/2025
- Éditeur
- IEEE Computer Society
- Type
- proceedings-article
Ce recoupement confirme des métadonnées liées au DOI. Il ne confirme ni la méthode ni les conclusions de l’étude, et il ne compte pas comme une seconde source scientifique indépendante.
Où se fait cette recherche
-
Athena Research and Innovation Center In Information Communication & Knowledge Technologies pays non établi dans la noticeStructure de recherche
-
Athens University of Economics and Business pays non établi dans la noticeUniversité ou école supérieure
-
University of Liverpool pays non établi dans la noticeUniversité ou école supérieure
-
Daiseung Medics (South Korea) pays non établi dans la noticeEntreprise
-
Sapienza University of Rome pays non établi dans la noticeUniversité ou école supérieure
-
Amsterdam University of the Arts pays non établi dans la noticeUniversité ou école supérieure
-
University of Amsterdam pays non établi dans la noticeUniversité ou école supérieure
-
Jump Trading pays non établi dans la noticeInstitution
Athena Research and Innovation Center In Information Communication & Knowledge Technologies, Athens University of Economics and Business et University of Liverpool, avec 5 autres affiliations.
Une affiliation ne permet pas de déduire la nationalité d’un auteur.