  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.
