【CS Peer Talk #4】Stability in Committee Selection

Time: 2020-5-13 16:00

Venue: Online Talk 
Speaker: Zhihao Jiang, Yao Class (Class of 2016)
Registration: https://www.wjx.cn/m/76528427.aspx

 

Abstract:

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.