Online Approval Committee Elections
Authors: Virginie Do, Matthieu Hervouin, Jérôme Lang, Piotr Skowron
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our contribution is twofold. (1) We assess to what extent the committees that are computed online can proportionally represent the voters. (2) If a prior probability over candidate approvals is available, we show how to compute committees with maximal expected score. ... Yet, our first contribution lies in designing optimal algorithms for the case, where a prior distribution over candidate approvals is available. The goal becomes to design algorithms that maximize the expected score of the selected committees. We show that for selected scoring functions f-sc or under some assumptions, this can be done in polynomial time. ... We give a polynomial-time computable online selection policy that satisfies the axiom of proportional justified representation [S anchez-Fern andez et al., 2017]. We further show that the stronger axiom of extended justified representation is not satisfiable in the online setting, but it can be approximated. We give two such approximation algorithms, one which gives the best possible approximation but is computationally inefficient, and the other one, which can be computed in polynomial time. ... Our main message is that online approval-based committee elections are easier than we might have thought. First, for Thiele rules with submodular score functions we have a constant-factor approximation algorithm (obtained as a corollary of a known result), and a dynamic programming algorithm for maximizing the expected score, which runs in polynomial time for some rules or under some assumptions. Second, we have an algorithm that returns a committee satisfying PJR, and two that return an approximate EJR committee: one with an optimal ratio, the other one running in polynomial-time. |
| Researcher Affiliation | Collaboration | Virginie Do1,2 , Matthieu Hervouin2 , J erˆome Lang3 and Piotr Skowron4 1Meta AI Research, Paris, France 2Universit e Paris Dauphine, PSL, CNRS, LAMSADE, France 3CNRS, Universit e Paris Dauphine, PSL, LAMSADE, France 4University of Warsaw, Poland |
| Pseudocode | No | The paper describes algorithms verbally (e.g., "Greedy Budgeting Rule", "Online Greedy Cohesive algorithm (OGCA)") and provides mathematical formulations, but it does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with a dataset. It discusses a "prior distribution over candidate approvals" as a theoretical assumption, not a concrete dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments; therefore, there are no mentions of validation splits or processes. |
| Hardware Specification | No | The paper is theoretical and does not describe any empirical experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any empirical experiments, thus no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experiments, thus no specific experimental setup details like hyperparameters or training configurations are provided. |