CS Peer Talks

Stability in Committee Selection

  • Zhihao Jiang, Yao Class
  • Time: 2020-05-13 16:00
  • Host: PKU Turing Class Research Committee
  • Venue: Online Talk


We talk about fairness in the committee selection problem. 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. We extend this definition to stability of a distribution (or lottery) over committees. We show that stable lotteries always exist for two canonical voter preference models: the Approval Set setting and the Ranking setting. We also show that a c-approximately stable committee always exists where c is O(1), only assuming preferences are monotone: if committee S is a subset of committee S', then any voter weakly prefers S' to S.