Ranking algorithms are deployed widely to order a set of items in
applications such as search engines, news feeds, and recommendation systems.
Recent studies, however, have shown that, left unchecked, the output of ranking
algorithms can result in decreased diversity in the type of content presented,
promote stereotypes, and polarize opinions. In order to address such issues, we
study the following variant of the traditional ranking problem when, in
addition, there are fairness or diversity constraints. Given a collection of
items along with 1) the value of placing an item in a particular position in
the ranking, 2) the collection of sensitive attributes (such as gender, race,
political opinion) of each item and 3) a collection of constraints that, for
each k, bound the number of items with each attribute that are allowed to
appear in the top k positions of the ranking, the goal is to output a ranking
that maximizes the value with respect to the original rank quality metric while
respecting the constraints. This problem encapsulates various well-studied
problems related to bipartite and hypergraph matching as special cases and
turns out to be hard to approximate even with simple constraints. Our main
technical contributions are fast exact and approximation algorithms along with
complementary hardness results that, together, come close to settling the
approximability of this constrained ranking maximization problem. Unlike prior
work on the constrained matching problems, our algorithm runs in linear time,
even when the number of constraints is large, its approximation ratio does not
depend on the number of constraints, and it produces solutions with small
constraint violations. Our results rely on insights about the constrained
matching problem when the objective satisfies properties that appear in common
ranking metrics such as Discounted Cumulative Gain, Spearman's rho or
Bradley-Terry.

本研究致力于解决在电子商务中，为了使商品推荐更具多样性和公正性，提出的带约束排序优化问题，通过提出的快速精确和近似算法，得出结论：即使当约束条件很大时，我们的算法仍然可以在线性时间内运行，并且产生具有小约束违规的解决方案。