A Lower Bound for Local Search Proportional Approval Voting

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 $\sum_{j=1}^t\frac{1}{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 by Aziz et al. It proceeds by starting with an arbitrary size-$k$ set $W$ and, at each step, checking if there is a pair of candidates $a\in W$, $b\not\in W$ such that swapping $a$ and $b$ increases the total welfare by at least $\varepsilon$; if yes, it performs the swap. Aziz et al.~show that setting $\varepsilon=\frac{n}{k^2}$ ensures both the desired fairness guarantees and polynomial running time. However, they leave it open whether the algorithm converges in polynomial time if $\varepsilon$ 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 $\varepsilon$ can be arbitrarily small, the running time of this algorithm may be super-polynomial. Specifically, we prove a lower bound of~$\Omega(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.
Comment: 26 pages including appendix, accepted to ESA 2024