2026-07-20T11:15:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21153 2024-09-23T09:13:18Z ddc:004 open_access

A Lower Bound for Local Search Proportional Approval Voting Kraiczy, Sonja Elkind, Edith Computational Social Choice Committee Elections Local Search Fairness Selecting k out of m items based on the preferences of n heterogeneous agents is a widely studied problem in algorithmic game theory. If agents have approval preferences over individual items and harmonic utility functions over bundles - an agent receives ∑_{j = 1}^t1/j utility if t of her approved items are selected - then welfare optimisation is captured by a voting rule known as Proportional Approval Voting (PAV). PAV also satisfies demanding fairness axioms. However, finding a winning set of items under PAV is NP-hard. In search of a tractable method with strong fairness guarantees, a bounded local search version of PAV was proposed [Aziz et al., 2018]. It proceeds by starting with an arbitrary size-k set W and, at each step, checking if there is a pair of candidates a ∈ W, b ̸ ∈ W such that swapping a and b increases the total welfare by at least ε; if yes, it performs the swap. Aziz et al. show that setting ε = n/(k²) ensures both the desired fairness guarantees and polynomial running time. However, they leave it open whether the algorithm converges in polynomial time if ε is very small (in particular, if we do not stop until there are no welfare-improving swaps). We resolve this open question, by showing that if ε can be arbitrarily small, the running time of this algorithm may be super-polynomial. Specifically, we prove a lower bound of Ω(k^{log k}) if improvements are chosen lexicographically. To complement our lower bound, we provide an empirical comparison of two variants of local search - better-response and best-response - on several real-life data sets and a variety of synthetic data sets. Our experiments indicate that, empirically, better response exhibits faster running time than best response. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sonja Kraiczy and Edith Elkind 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.82 urn:nbn:de:0030-drops-211538 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.82 eng https://creativecommons.org/licenses/by/4.0/legalcode