Submodular function optimization has numerous applications in machine
learning and data analysis, including data summarization which aims to identify
a concise and diverse set of data points from a large dataset. It is important
to implement fairness-aware algorithms when dealing with data items that may
contain sensitive attributes like race or gender, to prevent biases that could
lead to unequal representation of different groups. With this in mind, we
investigate the problem of maximizing a monotone submodular function while
meeting group fairness constraints. Unlike previous studies in this area, we
allow for randomized solutions, with the objective being to calculate a
distribution over feasible sets such that the expected number of items selected
from each group is subject to constraints in the form of upper and lower
thresholds, ensuring that the representation of each group remains balanced in
the long term. Here a set is considered feasible if its size does not exceed a
constant value of $b$. Our research includes the development of a series of
approximation algorithms for this problem.

通过开发近似算法解决具有组内公平性约束的单调子模函数最大化问题。

通过随机化实现子模函数最大化的长期公平性

Achieving Long-term Fairness in Submodular Maximization through  Randomization

We present a practical and powerful new framework for both unconstrained and
constrained submodular function optimization based on discrete
semidifferentials (sub- and super-differentials). The resulting algorithms,
which repeatedly compute and then efficiently optimize submodular
semigradients, offer new and generalize many old methods for submodular
optimization. Our approach, moreover, takes steps towards providing a unifying
paradigm applicable to both submodular min- imization and maximization,
problems that historically have been treated quite distinctly. The practicality
of our algorithms is important since interest in submodularity, owing to its
natural and wide applicability, has recently been in ascendance within machine
learning. We analyze theoretical properties of our algorithms for minimization
and maximization, and show that many state-of-the-art maximization algorithms
are special cases. Lastly, we complement our theoretical analyses with
supporting empirical experiments.

文章提出了一种基于离散半微分的无约束和有约束子模函数优化的实用强大新框架，旨在为子模最小化和最大化问题提供统一的范例，并为解决这些问题提供了新的算法，该算法能够多次计算和高效率优化子模半梯度。作者还分析了该算法的理论性质，并进行了支撑的经验实验，证明其在最大化问题上的优秀表现。