Subset Selection Based On Multiple Rankings in the Presence of Bias:
  Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions
Niclas Boehmer L. Elisa Celis Lingxiao Huang Anay Mehrotra Nisheeth K. Vishnoi
We consider the problem of subset selection where one is given multiple
rankings of items and the goal is to select the highest ``quality'' subset.
Score functions from the multiwinner voting literature have been used to
aggregate rankings into quality scores for subsets. We study this setting of
subset selection problems when, in addition, rankings may contain systemic or
unconscious biases toward a group of items. For a general model of input
rankings and biases, we show that requiring the selected subset to satisfy
group fairness constraints can improve the quality of the selection with
respect to unbiased rankings. Importantly, we show that for fairness
constraints to be effective, different multiwinner score functions may require
a drastically different number of rankings: While for some functions, fairness
constraints need an exponential number of rankings to recover a
close-to-optimal solution, for others, this dependency is only polynomial. This
result relies on a novel notion of ``smoothness'' of submodular functions in
this setting that quantifies how well a function can ``correctly'' assess the
quality of items in the presence of bias. The results in this paper can be used
to guide the choice of multiwinner score functions for the subset selection
setting considered here; we additionally provide a tool to empirically enable
this.