Diverse committees with incomplete or inaccurate approval ballots

Abstract: I will talk about my paper titled “Diverse committees with incomplete or inaccurate approval ballots”, that I will present also at AAMAS’26. Committee elections are part of voting theory, a prominent research area within (computational) social choice theory. In committee elections, one question is how to elect multiple winners (a committee) that represent the electorate in a ‘good’ way. We study approval ballots, which means each voter can express approval/disapproval with each of the candidates. Most studied in approval based committee elections are notions of proportionality, which essentially means we want to represent coherent groups of likeminded voters by a number of candidates proportional to their size. Our paper studies not proportionality but diversity for approval based committee elections. As a measure of diversity, we use the Maximum Coverage problem, a well known NP-hard problem in combinatorial optimization. It is, in this setting, also equivalent to the Chamberlin-Courant optimization problem, known more generally in social choice theory. We study two different approximation algorithms that both obtain the optimal approximation ratio of 1-1/e in regular complete information setting, and adapt them to a setting of incomplete information (not ever voter expresses their opinion on all of the candidates) and inaccurate information (voters make mistakes when filling in their ballot). Diverse summaries and adaptations to the settings of incomplete or inaccurate information are especially interesting for applications in deliberation summarization, where the many statements can make it hard to express opinions in a complete and accurate way.