Diverse Committees with Incomplete or Inaccurate Approval Ballots
Researchers show adaptive querying slashes needed votes from O(m²) to O(m)
Selecting a diverse committee is a classic NP-complete Maximum Coverage problem, but real-world elections rarely have complete voter ballots. A new study by Feline Lindeboom, Martijn Brehm, Davide Grossi, and Pradeep Murukannaiah (arXiv:2506.10843) provides tight theoretical bounds on how many voter queries are needed to get close to the optimal (1-1/e) approximation. In the incomplete information setting—where each voter only rates a few candidates—they prove any non‑adaptive algorithm must query Ω(m²) candidates to succeed with high probability.
Adaptive querying, where the algorithm learns from previous responses, drastically lowers this bound to just Ω(m) queries. The authors propose a greedy algorithm that achieves this bound up to log factors. They extend the result to the more general case of Maximum Coverage over a matroid constraint, allowing extra structural requirements like quotas or party balance. For inaccurate (noisy) ballots, they show Θ(nm) queries are needed (n = voters), and all algorithms match these bounds asymptotically.
Using real voting data from Polis and synthetic datasets, the algorithms perform well even in small, practical instances. The work bridges theory and practice for democratic decision‑making tools, showing that efficient diverse committee selection is feasible despite incomplete or noisy input.
- Non‑adaptive querying needs Ω(m²) candidates to guarantee a (1-1/e) approximation for diverse committees.
- Adaptive algorithms reduce the query complexity to Ω(m), matching a lower bound proven in the paper.
- Tested on real Polis data and synthetic scenarios, the greedy and local search methods perform well even on small instances.
Why It Matters
Enables efficient, provably good diversity in committee elections despite incomplete or noisy voter data.