Diversity in Approval-Based Committee Elections under Incomplete or Inaccurate Information

Speaker(s)

Davide Grossi

Affiliation

University of Groningen

Language of the talk

English

Date

May 8, 2025, 12:15 p.m.

Room

room 4050

Title in Polish

Diversity in Approval-Based Committee Elections under Incomplete or Inaccurate Information

Seminar

Seminar Games, Mechanisms, and Social Networks

---

We study diversity in approval-based committee elections with incomplete and/or inaccurate information. As standard in the literature on approval-based multi-winner voting, we define diversity according to the maximum coverage problem, which is known to be NP-complete, with a best attainable polynomial time approximation ratio of 1−1/e. In the incomplete information model, voters vote on only a small portion of the candidates. We suggest a greedy algorithm and a local search algorithm that query voters and use the query responses to approximate the total population’s opinion. For both algorithms, we prove an upper bound on the number of queries required to get a close to (1−1/e)-approximate solution with high probability. We also provide a lower bound for the query complexity of non-adaptive algorithms in this setting in general. In the inaccurate information setting, voters’ responses are corrupted with a probability p∈(0,0.5). We provide both an upper and a lower bound for the number of queries required to attain a (1−1/e)-approximate solution with high probability. Finally, using suitably augmented real data from Polis, we see that our algorithms perform remarkably better than the (worst-case) analysis suggests, both with incomplete and inaccurate information.

 

This is joint work with: Feline Lindeboom (University of Groningen), Martijn Brehm (University of Amsterdam), Pradeep Murukannaiah (TU Delft).

---