  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.
