Algorithmics of Egalitarian versus Equitable Sequences of Committees

Algorithmics of Egalitarian versus Equitable Sequences of Committees

Eva Michelle Deltl, Till Fluschnik, Robert Bredereck

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2651-2658. https://doi.org/10.24963/ijcai.2023/295

We study the election of sequences of committees, where in each of tau levels (e.g. modeling points in time) a committee consisting of k candidates from a common set of m candidates is selected. For each level, each of n agents (voters) may nominate one candidate whose selection would satisfy her. We are interested in committees which are good with respect to the satisfaction per day and per agent. More precisely, we look for egalitarian or equitable committee sequences. While both guarantee that at least x agents per day are satisfied, egalitarian committee sequences ensure that each agent is satisfied in at least y levels while equitable committee sequences ensure that each agent is satisfied in exactly y levels. We analyze the parameterized complexity of finding such committees for the parameters n, m, k, tau, x, and y, as well as combinations thereof.
Keywords:
Game Theory and Economic Paradigms: GTEP: Computational social choice
AI Ethics, Trust, Fairness: ETF: Fairness and diversity
Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning