Authors
Georgios Amanatidis
Georgios Birmpas
Philip Lazos
Stefano Leonardi
Rebecca Reiffenhäuser
Date (dd-mm-yyyy)
2025
Title
Algorithmically Fair Maximization of Multiple Submodular Objective Functions
Publication Year
2025
Number of pages
9
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Document type
Conference contribution
Abstract

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.

Permalink
https://hdl.handle.net/11245.1/73a8a198-b71c-452e-828c-8dc68e7c1b32