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

Prelegent(ci)

Davide Grossi

Afiliacja

University of Groningen

Język referatu

angielski

Termin

8 maja 2025 12:15

Pokój

p. 4050

Tytuł w języku polskim

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

Seminarium

Seminarium „Gry, mechanizmy i sieci społeczne”

---

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).

---