In this paper, we tackle the problem of computing a sequence of rankings with
the guarantee of the Pareto-optimal balance between (1) maximizing the utility
of the consumers and (2) minimizing unfairness between producers of the items.
Such a multi-objective optimization problem is typically solved using a
combination of a scalarization method and linear programming on bi-stochastic
matrices, representing the distribution of possible rankings of items. However,
the above-mentioned approach relies on Birkhoff-von Neumann (BvN)
decomposition, of which the computational complexity is $\mathcal{O}(n^5)$ with
$n$ being the number of items, making it impractical for large-scale systems.
To address this drawback, we introduce a novel approach to the above problem by
using the Expohedron - a permutahedron whose points represent all achievable
exposures of items. On the Expohedron, we profile the Pareto curve which
captures the trade-off between group fairness and user utility by identifying a
finite number of Pareto optimal solutions. We further propose an efficient
method by relaxing our optimization problem on the Expohedron's circumscribed
$n$-sphere, which significantly improve the running time. Moreover, the
approximate Pareto curve is asymptotically close to the real Pareto optimal
curve as the number of substantial solutions increases. Our methods are
applicable with different ranking merits that are non-decreasing functions of
item relevance. The effectiveness of our methods are validated through
experiments on both synthetic and real-world datasets.

我们介绍了一种使用 Expohedron 解决多目标优化问题的方法，该方法能够在用户效用的最大化和生产者之间的不公平性的最小化之间提供 Pareto 最优平衡，并通过识别有限数量的 Pareto 最优解来捕获组公平性和用户效用之间的权衡。我们还提出了在 Expohedron 的外接 $n$-sphere 上放松优化问题的高效方法，从而显著提高了运行时间。