Pareto Optimization for Fair Subset Selection: A Case Study on Personalized Recommendation
提出一种帕累托优化算法POFSS，通过公平性平衡翻转算子处理分组公平约束，理论证明其近似比，并在个性化推荐任务中优于现有方法。
Subset selection is a fundamental problem across a wide range of applications. In this study, we explore scenarios where the variables within the original dataset are divided into distinct groups. Subsequently, we investigate an optimization problem that includes extra fairness constraints (i.e., partition matroid constraints), restricting the selection of a specified number of variables from each group, which is known as the fair subset selection (FSS) problem. First, for the case where the existing Pareto optimization algorithms do not have the ability to well handle the fairness constraints, due to they do not consider fairness constraints in the process of solutions generation. In this article, a Pareto Optimization algorithm named POFSS is proposed for FSS, by introducing a designed fairness balance flip operator. Also, we prove that POFSS has the approximation ability of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\max \{ {}[{\alpha }/{l}](1-e^{-\gamma }), {}({\gamma }/{k}), 1-e^{-r\overline {k}/k } \}$ </tex-math></inline-formula> in polynomial time when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ l \lt \log _{2}{n}$ </tex-math></inline-formula> and the probability of mutation is constant <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$c/n~(c\lt 2)$ </tex-math></inline-formula> and this approximation ratio is no worse than the previous theoretical result (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula> represent two submodular ratios, and l is the number of disjoint groups). In addition, we apply POFSS to one typical FSS task named personalized recommendation (PR), where an acceleration strategy is designed and the acceleration ratio is strictly proved. Finally, the experimental results on the PR task show the proposed POFSS outperforms the state-of-the-art methods in addressing the FSS.