Approximately Stable Committee Selection

In the committee selection problem, we are given $m$ candidates, and $n$ voters. Candidates can have different weights. A committee is a subset of candidates, and its weight is the sum of weights of its candidates. Each voter expresses an ordinal ranking over all possible committees. The only assumption we make on preferences is monotonicity: If $S \subseteq S'$ are two committees, then any voter weakly prefers $S'$ to $S$. We study a general notion of group fairness via stability: A committee of given total weight $K$ is stable if no coalition of voters can deviate and choose a committee of proportional weight, so that all these voters strictly prefer the new committee to the existing one. Extending this notion to approximation, for parameter $c \ge 1$, a committee $S$ of weight $K$ is said to be $c$-approximately stable if for any other committee $S'$ of weight $K'$, the fraction of voters that strictly prefer $S'$ to $S$ is strictly less than $\frac{c K'}{K}$. When $c = 1$, this condition is equivalent to classical core stability. The question we ask is: Does a $c$-approximately stable committee of weight at most any given value $K$ always exist for constant $c$? It is relatively easy to show that there exist monotone preferences for which $c \ge 2$. However, even for simple and widely studied preference structures, a non-trivial upper bound on $c$ has been elusive. In this paper, we show that $c = O(1)$ for all monotone preference structures. Our proof proceeds via showing an existence result for a randomized notion of stability, and iteratively rounding the resulting fractional solution.
Comment: STOC 2020