  In this paper, we study fairness in committee selection problems. We consider
a general notion of fairness via stability: A committee is stable if no
coalition of voters can deviate and choose a committee of proportional size, so
that all these voters strictly prefer the new committee to the existing one.
Our main contribution is to extend this definition to stability of a
distribution (or lottery) over committees. We consider two canonical voter
preference models: the Approval Set setting where each voter approves a set of
candidates and prefers committees with larger intersection with this set; and
the Ranking setting where each voter ranks committees based on how much she
likes her favorite candidate in a committee. Our main result is to show that
stable lotteries always exist for these canonical preference models.
Interestingly, given preferences of voters over committees, the procedure for
computing an approximately stable lottery is the same for both models and
therefore extends to the setting where some voters have the former preference
structure and others have the latter. Our existence proof uses the
probabilistic method and a new large deviation inequality that may be of
independent interest.
