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 sumj=1tfrac1j 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∈ W, bnot∈ 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=fracnk2 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(klog 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.