# Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated
Rankings

Phuong Dinh Mai<EMAIL_ADDRESS>College of Engineering & Computer
Science,
VinUniversityHanoiVietnam ,  Duc-Trong Le<EMAIL_ADDRESS>University of
Engineering and Technology,
Vietnam National UniversityHanoiVietnam ,  Tuan-Anh Hoang<EMAIL_ADDRESS>School of Science, Engineering & Technology
RMIT University VietnamHanoiVietnam and  Dung D. Le<EMAIL_ADDRESS>College of Engineering & Computer Science,
VinUniversityHanoiVietnam

###### Abstract.

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.

##  1\. Introduction

In the ever-expanding digital landscape, recommender systems play an essential
role in shaping user experiences, influencing choices, and connecting
individuals with numberless products and content. As these systems continue to
evolve and proliferate, there is a growing recognition of the ethical
considerations surrounding their design and impact. One of such considerations
is _producer fairness_ , which arises from the desire to create trustworthy
recommendation experiences for users while fostering a certain level playing
field for service providers or content producers.

Challenge. Striking an optimal balance between the producer fairness and the
user utility becomes a nuanced challenge, where the system aims not only to
enhance the relevance and satisfaction of the users, but also to minimize
disparities and ensure unbiased treatment across diverse item groups.

In addressing this complex landscape, some studies advocate for constraint
handling as a strategic approach, introducing specific fairness criteria to
guide and control the optimization process. Sinan Seymen (Seymen et al., 2021)
has proposed a comprehensive framework based on a bi-stochastic probability
matrix, offering a structured methodology for tackling the intricate interplay
between user utility and fairness considerations. Alternative methodologies,
such as reinforcement learning, have gained prominent attention (Ge et al.,
2021), (Ge et al., 2022), (Fu et al., 2021), among others. Despite the diverse
array of approaches, profiling the Pareto front (Pareto, 2014) emerges as a
preferred strategy for decision makers. Representing a set of non-dominated
solutions, where enhancing one objective comes at the expense of another, the
Pareto front provides decision-makers with the ability to explore and extract
solutions that epitomize the optimal compromise between user utility and
fairness. This is important for decision-makers navigating the intricate
landscape of recommender system optimization, offering a practical and
effective means to address the inherent trade-offs between user-centric
utility and the imperative of fairness.

Scalarization techniques, such as weighted sum of objective functions, are
commonly used to obtain the Pareto front. They enable the exploration of
different trade-offs by adjusting the scalarization parameters. However, in
repeated ranking, these techniques usually depend on a bi-stochastic
probability matrix followed by an expensive Birkhoff-von Neumann (BvN)
(Dufossé and Uçar, 2016) decomposition to get a distribution of item orders.
This decomposition algorithm does not scale well (Geyik et al., 2019) when it
involves a graph matching algorithm. Using state-of-the-art linear programming
solvers adapted to our problem, the total complexity of such an approach is
then $O(n^{5})$.

Approach. Inspired by the Expohedon concept introduced in (Kletti et al.,
2022), our solution contributes to the ongoing exploration of geometric
solutions for the fairness-utility problem in recommendation systems. In this
work, we profile the entire Pareto-optimal solution spaces in the context of
the producer fairness—user satisfaction problem on the Expohedron facets. We
leverage this exploration with the concept of geodesic paths within a
hypersphere to approximate this frontier. While previous endeavors have
explored the use of geometry for this purpose, to the best of our knowledge,
we are pioneering an approach to approximate the exact Pareto set using the
geodesic of a hypersphere (Gotoh, 1994). This innovative perspective aims to
advance the field’s understanding and computational efficiency in resolving
the intricate trade-offs between producer fairness and user satisfaction
within recommender systems. This approximation provides a notable advantage by
significantly reducing the computational time required and employing
Carathéodory decomposition in (Kletti et al., 2022), which is more efficient
and resource-conserving compared to the BvN approach, for the distribution of
orders. An additional benefit of this approximation is the ability to control
the trade-off between the accuracy of the approximation and the overall
running time which will be essential for limited resources scenarios.

Our main technical contributions are:

  1. (1)

We profile the Pareto-optimal solutions space for the producer fairness and
user utility in repeated rankings’ problem on the Expohedron polytope. We
consolidate our theory by perform an experiment in a small synthetic dataset.

  2. (2)

With the aforementioned profiling, we introduce an approximate solution based
on the geodesic of a hypersphere. This approach not only offers a time-
efficient alternative but also enables us to exchange algorithmic accuracy for
enhanced runtime efficiency.

  3. (3)

We perform experiments in two real-world dataset: TREC Fair Ranking dataset
(Biega et al., 2021) and MSLR (Qin and Liu, 2013) to compare our methods to
quadratic programming and learning to rank baselines in terms of Pareto-
optimality and efficiency.

##  2\. Related Work

In this section, we review closely related work and provide some detailed
background that will be used throughout the paper.

Fairness in ranking. Fairness in recommender systems is a crucial
consideration aimed at addressing biases and ensuring equitable treatment
among users and content producers. As these systems shape user choices,
there’s a growing emphasis on mitigating algorithmic discrimination and
promoting transparency. Methods for addressing biases in recommender systems
are categorized into three types: pre-processing, in-processing, and post-
processing. Pre-processing methods, exemplified by (Salimi et al., 2019) and
(Zafar et al., 2019), focus on manipulating data before it enters the ranking
model to remove sensitive information and mitigate biases. In-processing
methods, such as (Wang et al., 2020), involve modifying the ranking within the
learning-to-rank framework. Post-processing methods, like those described in
(Zerveas, 2022), are popular for their flexibility and adaptability, involving
re-ranking strategies after the initial recommendations. The presented work
follows a post-processing approach in addressing bias in recommender systems.

Fairness considerations in recommender systems can be approached from various
perspectives, including the standpoint of consumers, as discussed in (Do et
al., 2022), or from the viewpoint of item producers, as explored in (Kletti et
al., 2022) and (Wang et al., 2020). The focus of our work lies specifically in
the context of item producers, offering insights and solutions that address
fairness concerns from the producers’ standpoint.

We adhere to the premise that the item positioned at the top of a list garners
more attention from consumers. Consequently, popular items consistently
occupying the top positions may perpetuate the ’Rich Gets Richer’ phenomenon,
leaving a long tail of less-attended or newly-released items behind (Naghiaei
et al., 2022). This trend is commonly observed in large e-commerce recommender
systems (RS). In response, there is a growing interest in addressing the
fairness of exposure. Rather than ensuring all items in the system receive a
uniform level of exposure (Biega et al., 2018), our objective is to ensure
that all groups of items receive a predetermined level of exposure—focusing on
fairness at the group level. This aligns with the approach taken by Singh and
Joachims (Singh and Joachims, 2018).

Position Based Model (PBM). In fairness of exposure approach, re-ranking
models depend on the amount of exposure each item received at a certain
ranking position. With PBM (Chuklin et al., 2015), the amount of exposure only
depends on the ranking itself. Other models might have the ranking depending
on items at higher ranks (i.e. Dynamic Bayesian Network (Chuklin et al.,
2015)). Our work is applicable to PBMs.

Pareto optimal. In the realm of recommendation algorithms, Pareto’s optimality
(Pareto, 2014) holds significance within the business market in general and
the recommender systems in particular, serving as a cornerstone in the pursuit
of optimal trade-offs between competing objectives. This concept is pivotal as
it allows recommender systems to navigate the intricate balance between
conflicting objectives such as user satisfaction and system efficiency.
Furthermore, Pareto optimality facilitates the exploration of complex decision
spaces, enabling recommender systems to adapt dynamically to evolving user
preferences and system constraints. The integration of Pareto optimal
solutions empowers recommender systems to deliver personalized and equitable
recommendations that enhance user experience and drive overall system
performance. However, we believe that this field have not received enough
attention from other researchers. Recent studies surrounding this trade-off
curve in recommendation include (Jin et al., 2023), (Aysha and Tarun, 2022),
(Paparella, 2022), etc.

Doubly bi-stochastic matrix. Singh and Joachims (Singh and Joachims, 2018)
formulate the ranking distribution as a doubly bi-stochastic matrix whose
elements represent the probabilities of each items’ appearance in each ranking
position. In PBMs, user’s utility could be formulated as a linear objective,
such as Discounted Cumulative Gain (DCG) (Järvelin and Kekäläinen, 2002) or
the Rank-biased precision (Moffat and Zobel, 2008). The fairness could be
formulated as a linear constraint, so the problem is solved using Linear
Programming (LP) (Horen, 1985). The probability matrix is then decomposed by
Birkhoff–von Neumann (BvN) decomposition (Dufossé and Uçar, 2016) to form an
expected value of a distribution over permutations. The same approach could be
seen in later research such as (Su et al., 2021), (Wang and Joachims, 2021).
The limitation of this approach is it could only generate one single point in
the Pareto optimal set—the point at the fairness target level.

Nevertheless, using a scalarization technique, fairness could be formulated
into a second quadratic/linear objective combining with user’s utility
function by trade-off hyperparameter $\alpha$. By changing the hyperparameter
$\alpha\in[0,1]$, we are able to generate a full set of Pareto solution set.
This method is compatible with our proposed method and will be used as a
baseline.

Controller. This is a heuristic approach using a greedy algorithm. Whenever a
query is repeated, an error terms is added to the relevance scores, which will
be arranged in the next ranking. It starts with the PBM, reduces the empirical
unfairness at every time-step by giving adequate bonuses to disadvantaged
items and after $T$ repeated time, the expected exposure of all groups might
be equal. The static setting (Thonet and Renders, 2020) will also be used as a
baseline for our work.

Expohedron. Our work is strongly relied on in the notion of Expohedron in
(Kletti et al., 2022). Based on the definition of the Permutahedron (Bowman,
1972), an Expohedron is a convex polytope whose vertices represent all
attainable exposure vector with one ranking in PBMs. With this, our feasible
solution region reduces its dimension from $\mathbb{R}^{n\times n}$ in the
Birkhoff polytope to $\mathbb{R}^{n}$ with $n$ is the number of items need to
re-rank. A point inside this polytope represents an expected exposure vector
of distribution over all ranking. Kletti et al. (Kletti et al., 2022) also
proposed Carathéodory decomposition — an algorithm allows an Expohedron
internal point to be factorized into a distribution over vertices, which
implies permutations.

##  3\. Problem and Preliminary

###  3.1. Problem and formulation

Settings. In our analysis, each query is treated as an independent entity.
Consider a specific query, denoted as $q$, which corresponds to a collection
of $n$ items indexed by $i$. A specialized black-box search and scoring
mechanism provides us with a column vector $\rho$, residing within the
interval $[0,1]^{n}$. This vector elucidates the extent of relevance each item
possesses in relation to the query. Notably, each item is categorized into one
specific group. Given the potential repetition of each query, we seek to
discern the anticipated trade-off curve between user satisfaction and the
disparity between the item categories. It is pertinent to mention that the
binary matrix indicator $G\in\mathbbm{R}^{n\times g}$ denotes whether the item
$i$ is affiliated with a group $j$, with the constraint $\sum_{i}G_{ij}=1$
ensuring exclusive membership to a single group.

Ranking matrix. Let $S_{n}\in\mathbbm{R}^{n\times n}$ be a matrix representing
permutations, where $||S_{n}||=n!=N$ denotes the total number of permutation
matrices. Within this set, let $\pi\in S_{n}$ represent a specific permutation
matrix. The entry, $\pi_{ij}=1$ if and only if the item $i$ occupies rank $j$.
Let $\mathbbm{1}$ be a column vector of 1, the bi-stochastic matrix $\pi$ is
formulated as:

$\begin{split}\pi&\in\\{0,1\\}^{n\times n}\\\
st&\;\mathbbm{1}_{n}^{T}\pi=\mathbbm{1}_{n}^{T}\\\
&\;\pi\mathbbm{1}_{n}=\mathbbm{1}_{n}\end{split}$

PBMs. In our empirical analyses, we employ the Position Based Model (Chuklin
et al., 2015), represented by a column vector $\gamma\in\mathbbm{R}^{n}_{+}$
whereas the $k^{th}$ value denote the exposure associated with the ranking
$k$. Without compromising the generality of our analysis, we posit that the
vector $\gamma$ exhibits a decreasing trend as the rank increases.

With this model, the item’ exposure score at ranking $\pi$ is represented by
$E(\pi)=\pi\gamma$ whereas the $k^{th}$ element of $E(\pi)$ denotes the
exposure value of the item $k$.

Since the query is repeated, assume the distribution $\mathbbm{D}$ of $N$
rankings $\pi_{1},\pi_{2},\cdots,\pi_{N}$ in $S_{n}$ is delivered with
proportion $p_{1},p_{2},\cdots,p_{N}$. The expected exposure score vector
associated with items is:

(1)
$\begin{split}E(\mathcal{D})&=\sum_{i}^{N}p_{i}E(\pi_{i})=\sum_{i}^{N}p_{i}\pi_{i}\gamma\\\
st&\sum_{i}^{N}p_{i}=1;\;0<=p_{i}=<1\end{split}$

Utility. The user’ satisfaction score or the utility of a ranking $\pi$ is
denoted as $U(\pi)=E(\pi)\rho=\pi\gamma\rho$. Relatively, the expected utility
function of the distribution $\mathbbm{D}$ is:

(2)
$\begin{split}U(\mathcal{D})&=\sum_{i}^{N}p_{i}U(\pi)=\sum_{i}^{N}p_{i}\pi\gamma\rho\\\
&=E(\mathcal{D})\rho\end{split}$

When $\gamma_{k}=\frac{1}{\log_{2}{k+1}}$ for position $k$ in the list,
$U(\pi)$ denotes the Discounted Cumulative Gain (Moffat and Zobel, 2008).
Alternatively, when $\gamma_{k}=(1-r)r^{k-1}$ with $r\in(0,1)$, $U(\pi)$
becomes the Rank-biased precision (Moffat and Zobel, 2008) metric.

Unfairness. In addressing the multifaceted nature of fairness, we operate
under the premise that a decision-maker has delineated what constitutes fair
exposures. Specifically, a target exposure is established for each group,
drawing inspiration from works such as (Diaz et al., 2020), wherein the target
exposure is conceptualized as an affine function of the relevance vector
$\rho$, embodying a form of meritocratic fairness. This target quantifies the
exposure a group is deemed deserving every time the query is invoked. Meeting
this predetermined exposure threshold signifies system fairness by definition.
Conversely, to quantify the degree of unfairness within a system, we
necessitate a metric that gauges the deviation from this target exposure. In
this paper we proceed as in (Diaz et al., 2020) in adopting the standard
Euclidean norm:

(3) $F(\mathcal{D},\epsilon^{*})=||GE(\mathcal{D})-\epsilon^{*}||_{2}$

This measurement allows us to trade off utility with the fairness.

Objectives. Both $U$ and $F$ are contingent on $\mathcal{D}$ solely through
its expectation. Thus, we can express them as $U(\mathcal{D})$ and
$F(\mathcal{D},\epsilon^{*})$ instead of $U(E(\mathcal{D}))$ and
$F(E(\mathcal{D}),\epsilon^{*})$ for short. Our objective is to address a
Multi-Objective Optimization (MOO) challenge with dual goals: maximizing
utility and simultaneously minimizing unfairness, particularly after
processing an extensive array of rankings.

(4)
$\max_{\mathcal{D}}\;U(\mathcal{D}),\;\min_{\mathcal{D}}\;F(\mathcal{D},\epsilon^{*})$

###  3.2. Expohedron

The permutation simplex. A naive way to solve problem (4) is to calculate the
distribution vector $p$ representing $\mathcal{D}$. In this method, our
variable is a vector $p\in\mathbbm{R}^{n!}$, which is infeasible in reality
due to the high dimensionality of the space $\mathbbm{R}^{n!}$.

Birkhoff polytope. In the PBMs, we can work in a smaller, more tractable
space: the space of bi-stochastic matrices as known as the Birkhoff polytope
(Singh and Joachims, 2018). The expected exposure in 1 could be represented
as:

(5)
$\begin{split}E(\mathcal{D})&=\sum_{i}^{N}p_{i}\pi_{i}\gamma\;=\;(\sum_{i}^{N}p_{i}\pi_{i})\gamma\\\
&=B\gamma\\\ st&\;\mathbbm{1}_{n}^{T}B=\mathbbm{1}_{n}^{T}\\\
&\;B\mathbbm{1}_{n}=\mathbbm{1}_{n}\end{split}$

The bi-stochastic property of the matrix $B$ could be easily proved by
calculating the sum of each column/row so we defer the proof of this property
to interested readers. Our problem is rewritten into:

(6) $\begin{split}\max_{B}&\;U(\mathfrak{D})=B\gamma\rho\\\
\min_{B}&\;F(\mathfrak{D})=||GB\gamma-\epsilon^{*}||_{2}\\\
st&\;\mathbbm{1}_{n}^{T}B=\mathbbm{1}_{n}^{T}\\\
&\;B\mathbbm{1}_{n}=\mathbbm{1}_{n}\end{split}$

The Birkhoff polytope is synonymous with the convex hull delineated by all
permutations, each of which is represented by a permutation matrix. A notable
algorithm, termed the Birkhoff-von Neumann (BvN) decomposition (Dufossé and
Uçar, 2016), facilitates the representation of any bi-stochastic matrix of
dimensions $n\times n$ as a convex combination comprising a maximum of
$(n-1)^{2}+1$ permutation matrices. The complexity of the BvN is
$O(max(n^{d+2},n^{4}))\approx O(n^{5})$ with $O(n^{d})$ is the complexity of
the algorithm for finding a matching in graphs on $n$ vertices (number of
items), plus $O(n^{2})$ to manipulate the doubly bi-stochastic matrix.

Expohedron. Geir Dahl (Dahl, 2010) showed that the feasible region of
$E(\mathcal{D})$ is a majorization permutation (Marshall et al., 1980). Let
the expected exposure $E(\mathcal{D})$ is the vector variable $x$, our problem
is formulated as:

(7) $\begin{split}\max_{x}&\;U(x)=x\rho\\\
\min_{x}&\;F(x)=||Gx-\epsilon^{*}||_{2}\\\ st&\;x\preceq\gamma\end{split}$

This polytope is also known as the Expohedron which Till Kletti et al. (Kletti
et al., 2022) used to solve the individual fairness in repeated ranking
problem. In the settings of PBMs, the Expohedron inherits multiple properties
of the permutahedron (Bowman, 1972) which we will discuss further when solving
our group fairness for repeated ranking problem.

Moreover, Till Kletti et al.(Kletti et al., 2022) also showed that the
decomposition algorithm using Carathéodory’s theorem (Carathéodory, 1907) can
express any point $x$ inside the Expohedron over at most $n$ rankings in the
$O(n^{2}\log n)$ running time.

##  4\. Profiling the Pareto-optimal solutions space

###  4.1. Theoretical analysis

In this section, we show how to find the exact solution for the multi-
objectives problem (7) in section 3. We will start will the most important
notion of our proof.

Theorem 1: The Pareto optimal solutions of the problem (7) lie on Expohedron
facets. These facets have a dimension of at most $(n-g-1)$.

Proof:

Considerate the level of fairness $F(x)=||\epsilon||_{2}=f_{0}$, the Pareto
solution associated with this level of fairness is the solution of this
optimal problem:

(8) $\begin{split}\max_{x}&\;U(x)=x\rho\\\ st&\;Gx-\epsilon^{*}=\epsilon\\\
st&\;x\preceq\gamma\end{split}$

Assume that problem (8) has at least one optimal solution. The fact that the
majorization condition “$\preceq$” could be written in the form sum of largest
elements in an array makes this condition is completely linear. Overall, both
conditions and the optimal function are linear. Therefore, the problem (8) is
a typical linear programming (LP) problem.

The theorem 3.3 in (Horen, 1985) states that if the objective function has a
maximum/minimum value on the feasible region, then it has this value on (at
least) one of the extreme points. The feasible region of (8) is an
intersection of a sub-plane with a convex polytope A which is also a convex
polytope B. Consequently, There is an optimal solution to be the vertex of B
and laid on the facet of A.

Since $G$ is a binary matrix, $R^{g}=Gx-\epsilon^{*}$ must be parallel with at
least 2 facets of the Expohedron (facets of the Expohedron could be written in
form of binary matrix multiplication equals to sum of some largest elements in
an array). Therefore, the vertex where $R^{g}$ intersecting with the
Expohedron boundary lie on the facet with the dimension of at most $n-g-1$.

Before delving into the optimal Pareto solution, we will establish several
lemmas utilizing our self-defined geometric objects.

Lemma 1: The $L_{2}$ norm fairness level in group-fairness setting are “hyper-
cylinders” formulated by $S^{n-g-1}\times R^{g}$ ($g$ is the number of
groups).

Proof.: The feasible space for the linear problem
$C=\\{x\;\mid\;Gx=\epsilon^{*}\\}$ is the subspace $\mathbbm{G}$ dimension $g$
of the $\mathbbm{R}^{n}$. Assume $\widebar{\mathbbm{G}}$ is the orthogonal
subspace of $\mathbbm{G}$ dimension $n-g$ of the $\mathbbm{R}^{n}$. Projecting
all $\mathbbm{G}$ onto $\widebar{\mathbbm{G}}$ creates a point $\bar{C}$ in
$\widebar{\mathbbm{G}}$.

Furthermore, the set of points which have equidistant in $\mathit{L_{2}}$ from
$\bar{C}$ form a hypersphere in $\widebar{\mathbbm{G}}$ or so-called the
$(n-g-1)$-sphere $S^{n-g-1}$ (Hilton, 1964).

Therefore, the $L_{2}$ norm fairness level in group-fairness setting are
“hyper-cylinders” formulated by $S^{n-g-1}\times R^{g}$ ($g$ is the number of
groups).

Lemma 2: An intersection of the ”hyper-cylinder” $H=S^{n-g-1}\times R^{g}$
with a subplane $\alpha$ in $\mathbbm{R}^{n}$ returns:

  1. (1)

A ”hyper-cylinder” $\widehat{H}=S^{n-g-2}\times R^{g}$ if $\alpha$ is a
hyperplane containing the sub-plane $R^{g}=\\{x\;\mid\;Gx=\epsilon^{*}\\}$

  2. (2)

A ”hyper-ellipsoid” if a sub-plane $\alpha$ dimension $(n-g)$ intersects with
the sub-plane $C=\\{x\;\mid\;Gx=\epsilon^{*}\\}$

Proof:

  1. (1)

Since $\alpha$ is a hyperplane containing $R^{g}$, $\alpha$ is orthogonal with
$\widebar{\mathbbm{G}}$, we could write $\alpha=R^{n-g-1}\times R^{g}$. It is
easy to prove that the intersection of a d-dimensional sphere and a hyperplane
is a d-1 dimensional sphere using the Pythagorean theorem. Therefore, the
intersection of $\alpha$ with $H$ could be written in the form of:

(9) $\begin{split}I&=(S^{n-g-1}\cap R^{n-g-1})\times R^{g}\\\
&=S^{n-g-2}\times R^{g}\\\ \end{split}$

  2. (2)

Assume $P_{0}$ is a $(n-g-1)$-sphere representing the intersection of $H$ with
$\widebar{\mathbbm{G}}$. Since $\alpha$ has the same dimension with
$\widebar{\mathbbm{G}}$ and intersect $C$, we could rewrite
$\alpha=\\{\widebar{\mathbbm{G}}A$ with A is a transformation full rank
matrix. Therefore, the intersection of $H$ and $\alpha$ could be written as:

(10) $\begin{split}P&=P_{0}A\\\ &=S^{n-g-1}A\end{split}$

The image of an n-sphere under an invertible affine transformation defines a
hyper-ellipsoid. This theorem could be proved using the Spherical coordinates
(Arfken et al., 1985).

Figure 1 is an example of the optimal Pareto solutions when n=3 and g=2.

Figure 1. An example of utility and fairness level set when n=3 and g=2. While
the blue line is the utility level set, the target fairness level is the red
ones and one set of fairness level are red dashed line. The green line
segments form the Pareto-curve in the Expohedron

Theorem 2: Let $P_{1}$ and $P_{2}$ be an optimal Pareto solution at facet $F$
having dimension $(n-g)$. The segment between $P_{0}$ and $P_{1}$ is part of
the Pareto optimal solution.

Proof: Using all aforementioned Lemma, let point $P_{0}$ be the intersection
of the hyperplane
$P=\\{\textbf{x}\mid\sum_{i}^{n}x_{i}=\sum_{j}^{n}\gamma_{j}\\}$ and the
target fairness level $U_{0}$ and the facet $F$. The unfairness level $U_{1}$
containing $P_{1}$ intersects with the hyperplane $P$ at the hyper-cylinder
$H_{1}$ and this hyper-cylinder $H_{1}$ intersects with the facet $F$ having
dimension $(n-g)$ at the hyper-ellipsoid $E_{1}$. The same notion with
$P_{2}$.

Considerate to hyper-ellipsoid $E_{1}$ containing $P_{1}$. If $P_{1}$ is a
Pareto-optimal points, $P_{1}$ must have the largest utility value amongst
$E$. This means the tangent vector at $P_{1}$ of $E$ must be parallel with the
relevance vector $\rho$ \- which is equal to the orthogonal to the hyperplanes
of utility level. Furthermore, $E_{1}$ and $E_{2}$ have similar center as well
as affine transformation matrix (in the same cutting facet $F$). Therefore,
$E_{2}=sE_{2}$ with $s$ is a scaling scalar. So without the loss of
generality, the vector $\vec{P_{0}P_{1}}=s\vec{P_{0}P_{2}}$ defines the
optimal utility-unfairness trade-off solution direction in $F$.

Moreover, the Theorem 1 shows that, without others facets restriction, the
optimal solution $P_{i}$ always lies on $F$. It’s apparent that segment
$P_{1}P_{2}$ is a part of optimal Pareto solution.

With the establishment of Theorem 1 and the Theorem 2, its inevitable
consequence is the following corollary.

Corollary: The optimal Pareto solution for our problem is a set of consecutive
segments across Expohedron facets. These segments connected by a ”break” point
laid on the boundary of the facet. At these points, our optimal direction
changes the direction to go to another facets.

Figure 2. An example of utility and fairness level set when n=4. The green
line segments form the Pareto-curve in the Expohedron. The red points are
“break” points in Pareto set curve

###  4.2. Finding the Pareto curve

The analysis presented above provides a straightforward solution: Begin at the
point of optimal utility on the target fairness level and move along the
optimal direction of $\theta$ on that facet until intersecting the boundary of
the Expohedron. This intersection denotes a ’break’ point. The subsequent
facet to enter will offer the optimal trade-off between utility and unfairness
for each unit increase. By iteratively repeating this process, we ensure
reaching a point that maximizes utility, serving as the endpoint of the Pareto
curve.

Algorithm 1 The P-Expo for profiling the Pareto-optimal solutions space on the
Expohedron

1:

2:$\rho\in(0,1)$: vector of relevance

3:$G\in\mathbb{R}^{n\times n\\_group},\>G_{ij}\in\\{0,1\\}$: item masking
group

4:$\varepsilon\in\mathbb{R}^{n\\_group}$: the target group fairness

5:$\gamma$: the position based exposure

6:

7:Pareto Set - $P$

8:

9:$G_{k}\leftarrow\sum_{i=1}^{k}\gamma_{i}^{\uparrow}$

10:$opt_{F}=point\leftarrow\text{Solve (\ref{optimal_at_fairness}) for
}\epsilon^{*}$

11:$P\leftarrow\\{opt_{F}\\}$

12:while True do

13: $s\leftarrow\sum_{i=1}^{k}point_{i}^{\uparrow}$

14: $S\leftarrow\\{k_{1},k_{2},...\\}\leftarrow$ which $G_{k}==s_{k}$

15: $face\\_orth\leftarrow$ binary matrix from invert permutation of $S_{k}$

16: $slope\leftarrow 0$

17: $\theta\leftarrow(0,0,...,0)$

18: for each $vec\in face\\_orth$ or $vec=\emptyset$ do

19: $adj\\_face\leftarrow\\{face\\_orth\setminus vec\\}$

20: $\theta_{f}\;slope_{f}\leftarrow$ Find the optimal direction and its
trade-off in $adj\\_face$

21: if $slope<slope_{f}$ then

22: $slope=slope_{p}$

23: $\theta=\theta_{f}$

24: end if

25: end for

26: $next\\_point\leftarrow\text{Expohedron.intersect(}point,\theta\text{)}$

27: $P$.append($next\\_point$)

28: $point\leftarrow next\\_point$

29:end while

To determine the value of $\theta$ at the facet $F$, let’s assume the
existence of an optimal point $P_{1}$. According to Theorem 2, we can identify
another optimal point $P$ situated on $F$ or at the intersection of the target
fairness level and the facet $F$. We then define $\theta$ as the vector
$\vec{PP_{1}}$.

##  5\. Approximation of the Pareto curve

The PBMs’ Expohedron has a very appealing feature. It is an inscribing
polytope, a polytope in which all its vertex lies on an n-sphere. Considering
the hyperplane dimension $n-1$ $\sum_{i}^{n}x_{1}i=\sum_{i}^{n}\gamma$, it is
easy to see that all vertices are equidistant from the center point
coordinator $(c,c,...,c)\in\mathbb{R}^{n}:\;c=\frac{\sum\gamma}{n}$).

Snyder’s research (Snyder, 2012) showed that geodesic on hypersphere
transforming to straight lines via the central projection, so-called gnomonic
projection in 2-dimension. With the use of the corollary in section 1, the
Pareto-optimal solutions space could be mapped to a set of consecutive
geodesic on the $(n-2)$-sphere. Although the 2 consecutive geodesics
$\widearc{AB}$ and $\widearc{BC}$ could not be summed up to make the geodesic
$\widearc{AC}$, all segments in the Pareto-optimal solutions set are linear
transformations from the item relevance vector. Therefore, we assume that the
geodesic $\widearc{AC}$ could be used to approximate the 2 consecutive
geodesics $\widearc{AB}$ and $\widearc{BC}$. Though the tangent vector of this
approximation is not exactly matched with those two, it still shows the same
trend with the optimal solutions in the trade-off curve. Figure (3) is an
example. Since the function for the hypersphere geodesic is proven in (Bishop,
2013), the cost for the sampling process on the geodesic is $\mathcal{O}(1)$.

Figure 3. An example of how a set of connected segment could be approximate
with set of geodesics. The dash is the approximate geodesic curve and its
projection on Expohedron, while the line is the exact solution.

In order to make the approximation more accurate, we could use some marked
points to split the geodesic curve into multiple ones. And when the number of
marked points is large enough, each projection of the geodesic will be a
segment in one hyperplane and contains no “break” point, which means it is
part of the Pareto set. A marked point could be found by solving a QP problem:

(11) $\begin{split}\min_{x}&\;||Gx-\epsilon^{*}||_{2}\\\ st&\;U(x)=x\rho\\\
st&\;x\preceq\gamma\end{split}$

Algorithm 2 Sphere-Expo for approximating the Pareto-optimal solution space
with hypersphere geodesic

1:

2:$\rho\in(0,1)$: vector of relevance

3:$G\in\mathbb{R}^{n\times 2},\>G_{ij}\in\\{0,1\\}$: item masking group

4:$\varepsilon\in\mathbb{R}^{2}$: the target group fairness

5:$\gamma$: the position based exposure

6:$n\\_sample$: number of sample points in each geodesic curve

7:$K$: number of marked points in logarithm of 2

8:

9:Pareto Set - $P$

10:

11:$S\leftarrow HyperSphere(dim=n-2)$

12:$start\\_point\leftarrow\text{Solve (\ref{optimal_at_fairness}) for
}\epsilon^{*}$

13:$end\\_point\leftarrow\gamma^{argsort(\rho)}$

14:$q\leftarrow[(start\\_point,end\\_point)]$

15:$P\leftarrow[]$

16:while $K>0$ do

17: for each $(s,e)\in q$ do

18: $geo\leftarrow S.geodesic\\_func(s\rightarrow e)$

19: $mid\\_point\leftarrow geo.getMidPoint()$

20: $mid\\_util\leftarrow utils(midpoint)$

21: $fixed\\_mid\leftarrow\text{Solve (\ref{optimal_at_utils}) for
}mid\\_util$

22: $next\\_q.append((s,fixed\\_mid),(fixed\\_mid,e))$

23: end for

24: $q\leftarrow next\\_q$

25: $K\leftarrow K-1$

26:end while

27:for each $(s,e)\in q$ do $\triangleleft$ Sample point in geodesic

28: $geo\leftarrow S.geodesic\\_func(s\rightarrow e)$

29: $points\leftarrow geo.sample(n\\_sample)$

30: $P.add(points)$

31:end for

Theoretical complexity.  It is easily to see that the running time complexity
of the Sphere-Expo algorithm mostly comes from solving (8) for initiate point
and solving (11) for marked points. Since the (11) is a constrained least
squares problems, it could be solved in $\mathcal{O}(n^{3}\sqrt{n})$ (Nesterov
and Todd, 1997) running time. The complexity for the LP problems (8) might
vary between solver methods but not larger than $\mathcal{O}(n^{3}\sqrt{n})$
(Illés and Terlaky, 2002). Therefore, the total complexity for the Sphere-Expo
to approximate the whole Pareto-optimal space is $\mathcal{O}(Kn^{3}\sqrt{n})$
with K is the number of marked points and n is the number of items.

##  6\. Experiments

In order to solidify our empirical analysis of the Pareto-optimal solution
space, we perform experiments on a small synthetic dataset. After that, we
answer 2 question about the effectiveness and scalability of the Sphere-Expo
approximation:

  1. (1)

How far is the approximation from complete Pareto optimality?

  2. (2)

How efficient is the approximation comparing to other baselines?

###  6.1. Experimental Settings

####  6.1.1. Datasets

We perform experiments on two _synthetic_ datasets to answer the
aforementioned questions and consolidate the efficiency of the Sphere-Expo
approximation using two _real-world_ datasets.

All _synthetic_ datasets are uniformly independently generated. For each
number of items $n$, we sample the number of group $g$ and $n$ random
relevance vectors whose elements are in the range $[0,1]$. Each item is
randomly assigned to a group using a binary matrix $G$.

For the small _synthetic_ dataset $D_{s}$, the number of items $n$ is randomly
sampled from the range of $n\in[8\dots 20]$ with the number of groups of items
being random. For the large _synthetic_ dataset $D_{l}$, the number of items
$n$ is large $n\in{5\dots 100}$ with the number of item-groups is random.

For _real-world_ datasets, we use _TREC2020_ Fair Ranking Dataset (Biega et
al., 2021) and the _MRLR_ dataset (Qin and Liu, 2013). Documents in TREC are
divided into different groups based on some criteria like released year,
number of citations (divided in bins), etc. The documents in the MSLR dataset
are divided into different groups based on the $132^{th}$ feature representing
the quality score of a web page according to their documents. For TREC, we
compute relevance probabilities ourselves, but for MSLR, we use the ground
truth relevance scores graded from 0 (worst grade) to 4 (best grade), in order
to check the influence of having discrete-valued relevance value (their
relevance scores are normalized to the range [0, 1] by dividing them by 4).

Queries with more than 100 documents are discarded due to the implementation
problem: floating point error in the projection and cvxpy solver. We also
eliminate uninteresting queries: queries having only one document, queries in
which all relevance values are equal or queries having all the items belong to
one group. The special cases when each item belongs to a different group: the
item’s individual fairness is discarded either. This leaves 183 queries in the
TREC dataset and 861 queries in the MRLS dataset.

####  6.1.2. Baseline methods

We evaluate our proposed methods and 3 baselines, in their ability to solve
our MOO problem, both in terms of effectiveness and efficiency:

  1. (1)

A Quadratic Program (QP) that finds bi-stochastic matrices maximizing, for
varying $\alpha$, the scalarized multi-objective function:

(12) $\begin{split}\max_{B}\alpha\rho^{T}B\gamma+(1-\alpha)||B\gamma\times
G-\epsilon^{*}||_{2}\\\
st\;\mathbbm{1}B=\mathbbm{1},\>B\mathbbm{1}^{T}=\mathbbm{1}\end{split}$

  2. (2)

A static Controller (Ctrl) as proposed by (Thonet and Renders, 2020). This is
a heuristic approach when each time a query is repeated, the disadvantaged
items are compensated with a small amount of relevance scores so in the
future, it will have higher chance to be at the top of the list. We customized
the author’s objectives to be suitable with our objectives’ settings.

  3. (3)

Our proposed path based on our theoretical profiling on the Expohedron facets:
the P-Expo.

  4. (4)

Our approximate Pareto front using the geodesic in the hypersphere: the
Sphere-Expo.

While the QP baseline needs a Birkhoff a Neumann decomposition to generate the
distribution of item orders before sampling, the P-Expo and Sphere-Expo could
be combined with the Carathéodory algorithm proposed by (Kletti et al., 2022).

The package cvxpy (Agrawal et al., 2018) is used for all linear and quadratic
programming problems and the package geomstats (team, [n. d.]) is used to
generate the geodesic function on hypersphere. For all experiments, we use the
DCG exposure vector for $\gamma$ whose elements at ranking $i^{th}$ is
$\frac{1}{\log_{2}(i+2)}$ but any other PBMs should work.

Hyperparameters For the Ctrl, hyperparameter $K$ controls the balance between
the efficiency (small $K$) and effectiveness (large K) is set to 1. By varying
the gain $\lambda$ within $[0,100]$, we expect the Ctrl could produce the
Pareto front for each query. The gain $\alpha$ of the QP is also varied in the
range $[0,1]$ to find the optimal points. Results with the same gain are
aggregated over queries to compute the final performances.

While the P-Expo does not need any hyperparameter, the QP hyperparameter
$\alpha$ in 12 varies between 0 and 1. Different hyperparameters $K$ in the
Sphere-Expo representing the number of marked points will create different
approximation curves for the Pareto front. We will analyze how this
hyperparameter affects our approximation in the next experiments.

Among our baselines, QP is guaranteed to produce Pareto-optimal points,
provided that the associated QP solver has sufficient precision. The
performances corresponding to the same hyperparameter $\alpha$ are aggregated
over the different queries with the aggregation method. We will check whether
QP solutions exist in our Expo-derived Pareto-front (P-Expo and Sphere-Expo)
and associate the corresponding $\alpha$ to the latter. We are then able to
aggregate the performances over the different queries, by considering the
solutions associated with the same $\alpha$.

###  6.2. Experimental results

For each of the queries, we compute the full Pareto-front in the Expohedron
using P-Expo. We also use Ctrl, QP and Sphere-Expo to find 20 Pareto optimal
solutions.

The experiment in the small synthetic dataset $D_{s}$ not only consolidates
our corollary but also shows the drawback of the P-Expo. The aggregations of
the Pareto front and their running time are reported in Figure [4].

Figure 4. Aggregated Pareto fronts in small synthetic dataset $D_{s}$ showing
the drawback of the P-Expo

It appears without surprise that both QP and P-Expo perform identically.
However, the total running of the P-Expo grows rapidly due to the fact that
the number of segments (or facets it crosses) is unknown and incalculable.
Therefore, it is not suitable to be scaled up and deployed in reality and is
only used to verify our theoretical claims. On the other hand, the
experimental results also show the potential of the approximation with Sphere-
Expo. The red dash curve representing the Sphere-Expo with 7 marked is very
close to the true Pareto-front. Therefore, in the next experiments, we will
focus on analyzing the approximation using Sphere-Expo.

How far is the approximation from complete Pareto optimality? We perform
experiments on the 2 real-world datasets TREC and MSLR to examine the
performance of our proposed method in comparison with the baselines.

Figure 5. Aggregated Pareto fronts 2 real-world datasets. The more marked
points, the closer the approximation to the true Pareto front.

Objectives | TREC | MSLR
---|---|---
Normalized Utility (nDCG) | 0.995 | 0.94
Normalized Unfairness | 0.132 | 0.93

Table 1. The normalized objectives in Ctrl baseline

The experiments in the two real-world datasets show that the fronts produced
by our proposed method are moving forward to the true Pareto front when the
number of marked points increases. Therefore, the Sphere-Expo could be used to
approximate the true Pareto front. In the MSLR dataset, when the relevance
scores are discrete values, the relevance vector tends to be orthogonal with
some facets. Due to the asymmetric nature of the Expohedron, there will be
more than one optimal solution, and the approximation is exactly matched with
the true Pareto-front with one marked point.

By varying the gain $\lambda$ in the Ctrl, we hope to find approximately
Pareto-optimal solutions. However, after $T=1000$, the aggregate results in
both dataset always converge into one point. These points are denoted by green
markers in the Figure [5] and Table [1]. In the MSLR dataset, the unfairness
is extremely high in comparison with other methods. This might be due to the
average number of items in the MSLR dataset is larger compared to the TREC
dataset and the duplication in relevance score makes it hard to find an
appropriate permutation in a limited time.

How efficient is the approximation comparing to other baselines?

Process | Algo | TREC | MSLR
---|---|---|---
Pareto front | QP (20 points) | 1.23 | 4.45
Sphere-Expo (K=1) | 0.28 | 0.56
Sphere-Expo (K=3) | 0.47 | 0.99
Decomposition | Carathéodory | 0.07 | 0.54
| BvN | 2.25 | 29.56
Full process (target fairness) | Ctrl | 0.47 | 1.39

Table 2. The average running time over queries to generate the Pareto front
for $T=1000$ in 2 real-world datasets

In Table [2] we report the average time it takes to deliver $T=1000$ rankings
for each query, for both datasets. Although the Ctrl algorithm does not need
any initial cost, it needs to save and search history deliveries for the next
ranking. Therefore, the Ctrl is faster for short time horizons T, and its
running time will increase over time. Whereas for the Sphere-Expo and the QP
methods, the computation of the Pareto-front and the decomposition need to be
performed but once. Then, once a solution is found, it can be delivered very
quickly using any sampling strategy. Therefore, for larger time horizons, the
Sphere-Expo will be faster in total running time.

Figure 6. Aggregated Pareto fronts in large synthetic dataset $D_{l}$.
Hyperparameter K denotes the number of marked points we sample in the
approximation.

We also investigate how the number of items affects the total running time for
the QP baseline and the Sphere-Expo. In Figure [6], we reported the accuracy
and the total running time to generate 20 points in the Pareto front of the
large synthetic dataset using QP and Sphere-Expo with different numbers of
marked points. Obviously, the Sphere-Expo is asymptotic to the true Pareto-
front when the number of marked points increases. The cost for this is the
increase in the total running time. By varying the number of marked points
sampling in the Sphere-Expo, we could control the trade-off between the
accuracy and the time resources when approximating the Pareto front. Although
our proposed method involves solving some quadratic programming for marked
points, our problems have fewer variables and take fewer resources compared to
the QP methods. Therefore, it is more controllable and could be adaptive to
limited resource scenarios.

##  7\. Conclusion

Our novel geometrical algorithms allow us to approximate the true solutions
space in Pareto-optimal utility-fairness among groups in repeated rankings’
problem. Not only able to recover the Pareto frontier, our proposed methods
are proved to be more efficient in two term: controllability and scalability.
In the future work, we aim to expand our approximation method to other
exposure models beyond PBMs such as Dynamic Bayesian Networks (Chuklin and
Markov, 2015).

###### Acknowledgements.

This research was funded by Vingroup Innovation Foundation (VINIF) under
project code VINIF.2022.DA00087

## References

  * (1)
  * Agrawal et al. (2018) Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. 2018.  A rewriting system for convex optimization problems.  _Journal of Control and Decision_ 5, 1 (2018), 42–60.
  * Arfken et al. (1985) George B. Arfken, Hans J. Weber, and Frank E. Harris. 1985.  Chapter 2.  In _Mathematical Methods for Physicists (Third Edition)_ (third edition ed.), George B. Arfken, Hans J. Weber, and Frank E. Harris (Eds.). Academic Press, Orlando, 102–111.  https://doi.org/10.1016/B978-0-12-384654-9.00002-5
  * Aysha and Tarun (2022) Saima Aysha and Shrimali Tarun. 2022.  A Pareto Dominance Approach to Multi-criteria Recommender System Using PSO Algorithm. In _International Conference on Innovative Computing and Communications_ , Ashish Khanna, Deepak Gupta, Siddhartha Bhattacharyya, Aboul Ella Hassanien, Sameer Anand, and Ajay Jaiswal (Eds.). Springer Singapore, Singapore, 737–755.
  * Biega et al. (2021) Asia J. Biega, Fernando Diaz, Michael D. Ekstrand, Sergey Feldman, and Sebastian Kohlmeier. 2021.  Overview of the TREC 2020 Fair Ranking Track.  arXiv:2108.05135 [cs.IR]
  * Biega et al. (2018) Asia J. Biega, Krishna P. Gummadi, and Gerhard Weikum. 2018.  Equity of Attention. In _The 41st International ACM SIGIR Conference on Research and Development in Information Retrieval_. ACM.  https://doi.org/10.1145/3209978.3210063
  * Bishop (2013) Richard L. Bishop. 2013.  Riemannian Geometry.  arXiv:1303.5390 [math.DG]
  * Bowman (1972) V. J. Bowman. 1972.  Permutation Polyhedra.  _SIAM J. Appl. Math._ 22, 4 (1972), 580–589.  https://doi.org/10.1137/0122054 arXiv:https://doi.org/10.1137/0122054
  * Carathéodory (1907) Constantin Carathéodory. 1907.  Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen.  _Math. Ann._ 64 (1907), 95–115.  https://api.semanticscholar.org/CorpusID:116695038
  * Chuklin and Markov (2015) Aleksandr Chuklin and Ilya Markov. 2015.  Click Models for Web Search Authors ’ version *.  https://api.semanticscholar.org/CorpusID:12961209
  * Chuklin et al. (2015) Aleksandr Chuklin, Ilya Markov, and Maarten Rijke. 2015.  _Click Models for Web Search_. Vol. 7.  1–115 pages.  https://doi.org/10.2200/S00654ED1V01Y201507ICR043
  * Dahl (2010) Geir Dahl. 2010.  Majorization permutahedra and (0,1)-matrices.  _Linear Algebra Appl._ 432, 12 (2010), 3265–3271.  https://doi.org/10.1016/j.laa.2010.01.024
  * Diaz et al. (2020) Fernando Diaz, Bhaskar Mitra, Michael D. Ekstrand, Asia J. Biega, and Ben Carterette. 2020.  Evaluating Stochastic Rankings with Expected Exposure. In _Proceedings of the 29th ACM International Conference on Information and Knowledge Management_ _(CIKM ’20)_. ACM.  https://doi.org/10.1145/3340531.3411962
  * Do et al. (2022) Virginie Do, Sam Corbett-Davies, Jamal Atif, and Nicolas Usunier. 2022.  Online Certification of Preference-Based Fairness for Personalized Recommender Systems.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 36, 6 (Jun. 2022), 6532–6540.  https://doi.org/10.1609/aaai.v36i6.20606
  * Dufossé and Uçar (2016) Fanny Dufossé and Bora Uçar. 2016.  Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices.  _Linear Algebra Appl._ 497 (2016), 108–115.  https://doi.org/10.1016/j.laa.2016.02.023
  * Fu et al. (2021) Zuohui Fu, Yikun Xian, Shijie Geng, Gerard de Melo, and Yongfeng Zhang. 2021.  Popcorn: Human-in-the-Loop Popularity Debiasing in Conversational Recommender Systems. In _Proceedings of the 30th ACM International Conference on Information and Knowledge Management_ (Virtual Event, Queensland, Australia) _(CIKM ’21)_. Association for Computing Machinery, New York, NY, USA, 494–503.  https://doi.org/10.1145/3459637.3482461
  * Ge et al. (2021) Yingqiang Ge, Shuchang Liu, Ruoyuan Gao, Yikun Xian, Yunqi Li, Xiangyu Zhao, Changhua Pei, Fei Sun, Junfeng Ge, Wenwu Ou, and Yongfeng Zhang. 2021.  Towards Long-term Fairness in Recommendation. In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ _(WSDM ’21)_. ACM.  https://doi.org/10.1145/3437963.3441824
  * Ge et al. (2022) Yingqiang Ge, Xiaoting Zhao, Lucia Yu, Saurabh Paul, Diane Hu, Chu-Cheng Hsieh, and Yongfeng Zhang. 2022.  Toward Pareto Efficient Fairness-Utility Trade-off in Recommendation through Reinforcement Learning. In _Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining_ _(WSDM ’22)_. ACM.  https://doi.org/10.1145/3488560.3498487
  * Geyik et al. (2019) Sahin Cem Geyik, Stuart Ambler, and Krishnaram Kenthapadi. 2019.  Fairness-Aware Ranking in Search Recommendation Systems with Application to LinkedIn Talent Search. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM.  https://doi.org/10.1145/3292500.3330691
  * Gotoh (1994) Tohru Gotoh. 1994.  GEODESIC HYPERSPHERES IN COMPLEX PROJECTIVE SPACE.  _Tsukuba Journal of Mathematics_ 18, 1 (1994), 207–215.  http://www.jstor.org/stable/43685888
  * Hilton (1964) P. J. Hilton. 1964.  Topology. By John G. Hocking and Gail S. Young. Pp. 382. 74s. 1961. (Addison-Wesley).  _The Mathematical Gazette_ 48, 363 (1964), 122–123.  https://doi.org/10.2307/3614368
  * Horen (1985) Jeff Horen. 1985.  Linear programming, by Katta G. Murty, John Wiley and Sons, New York, 1983, 482 pp.  _Networks_ 15, 2 (1985), 273–274.  http://dblp.uni-trier.de/db/journals/networks/networks15.html#Horen85
  * Illés and Terlaky (2002) Tibor Illés and Tamás Terlaky. 2002.  Pivot versus interior point methods: Pros and cons.  _European Journal of Operational Research_ 140, 2 (2002), 170–190.  https://doi.org/10.1016/S0377-2217(02)00061-9
  * Järvelin and Kekäläinen (2002) Kalervo Järvelin and Jaana Kekäläinen. 2002.  Cumulated Gain-Based Evaluation of IR Techniques.  _ACM Trans. Inf. Syst._ 20, 4 (oct 2002), 422–446.  https://doi.org/10.1145/582415.582418
  * Jin et al. (2023) Jipeng Jin, Zhaoxiang Zhang, Zhiheng Li, Xiaofeng Gao, Xiongwei Yang, Lei Xiao, and Jie Jiang. 2023.  Pareto-based Multi-Objective Recommender System with Forgetting Curve.  _ArXiv_ abs/2312.16868 (2023).  https://api.semanticscholar.org/CorpusID:266573337
  * Kletti et al. (2022) Till Kletti, Jean-Michel Renders, and Patrick Loiseau. 2022.  Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings. In _Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining_. ACM.  https://doi.org/10.1145/3488560.3498490
  * Marshall et al. (1980) Albert W. Marshall, Ingram Olkin, and Barry C. Arnold. 1980.  Inequalities: Theory of Majorization and Its Applications.  https://api.semanticscholar.org/CorpusID:37387169
  * Moffat and Zobel (2008) Alistair Moffat and Justin Zobel. 2008.  Rank-Biased Precision for Measurement of Retrieval Effectiveness.  _ACM Trans. Inf. Syst._ 27, 1, Article 2 (dec 2008), 27 pages.  https://doi.org/10.1145/1416950.1416952
  * Naghiaei et al. (2022) Mohammadmehdi Naghiaei, Hossein A. Rahmani, and Mahdi Dehghan. 2022.  The Unfairness of Popularity Bias in Book Recommendation. In _International Workshop on Algorithmic Bias in Search and Recommendation_.  https://api.semanticscholar.org/CorpusID:247158125
  * Nesterov and Todd (1997) Yu. E. Nesterov and M. J. Todd. 1997.  Self-Scaled Barriers and Interior-Point Methods for Convex Programming.  _Mathematics of Operations Research_ 22, 1 (1997), 1–42.  https://doi.org/10.1287/moor.22.1.1 arXiv:https://doi.org/10.1287/moor.22.1.1
  * Paparella (2022) Vincenzo Paparella. 2022.  Pursuing Optimal Trade-Off Solutions in Multi-Objective Recommender Systems.  _Proceedings of the 16th ACM Conference on Recommender Systems_ (2022).  https://api.semanticscholar.org/CorpusID:252216518
  * Pareto (2014) Vilfredo Pareto. 2014.  _Manual of Political Economy: A Critical and Variorum Edition_.  Number 9780199607952 in OUP Catalogue. Oxford University Press.  https://ideas.repec.org/b/oxp/obooks/9780199607952.html
  * Qin and Liu (2013) Tao Qin and Tie-Yan Liu. 2013.  Introducing LETOR 4.0 Datasets.  _CoRR_ abs/1306.2597 (2013).  http://arxiv.org/abs/1306.2597
  * Salimi et al. (2019) Babak Salimi, Luke Rodriguez, Bill Howe, and Dan Suciu. 2019.  Capuchin: Causal Database Repair for Algorithmic Fairness.  arXiv:1902.08283 [cs.DB]
  * Seymen et al. (2021) Sinan Seymen, Himan Abdollahpouri, and Edward C. Malthouse. 2021.  A Unified Optimization Toolbox for Solving Popularity Bias, Fairness, and Diversity in Recommender Systems. In _Proceedings of the 1st Workshop on Multi-Objective Recommender Systems (MORS 2021) co-located with 15th ACM Conference on Recommender Systems (RecSys 2021), Amsterdam, The Netherlands, September 25, 2021_ _(CEUR Workshop Proceedings, Vol. 2959)_ , Himan Abdollahpouri, Mehdi Elahi, Masoud Mansoury, Shaghayegh Sahebi, Zahra Nazari, Allison Chaney, and Babak Loni (Eds.). CEUR-WS.org.  http://ceur-ws.org/Vol-2959/paper5.pdf
  * Singh and Joachims (2018) Ashudeep Singh and Thorsten Joachims. 2018.  Fairness of Exposure in Rankings. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM.  https://doi.org/10.1145/3219819.3220088
  * Snyder (2012) John P. Snyder. 2012.  Map Projections: A Working Manual.  https://api.semanticscholar.org/CorpusID:60447053
  * Su et al. (2021) Yi Su, Magd Bayoumi, and Thorsten Joachims. 2021.  Optimizing Rankings for Recommendation in Matching Markets.  arXiv:2106.01941 [cs.IR]
  * team ([n. d.]) Geomstats team. [n. d.].  _https://geomstats.github.io/_.  https://geomstats.github.io/
  * Thonet and Renders (2020) Thibaut Thonet and Jean-Michel Renders. 2020.  Multi-Grouping Robust Fair Ranking. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ (Virtual Event, China) _(SIGIR ’20)_. Association for Computing Machinery, New York, NY, USA, 2077–2080.  https://doi.org/10.1145/3397271.3401292
  * Wang and Joachims (2021) Lequn Wang and Thorsten Joachims. 2021.  User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets. In _Proceedings of the 2021 ACM SIGIR International Conference on Theory of Information Retrieval_ _(ICTIR ’21)_. ACM.  https://doi.org/10.1145/3471158.3472260
  * Wang et al. (2020) Ruoxi Wang, Rakesh Shivanna, Derek Zhiyuan Cheng, Sagar Jain, Dong Lin, Lichan Hong, and Ed H. Chi. 2020.  DCN V2: Improved Deep and Cross Network and Practical Lessons for Web-scale Learning to Rank Systems.  _Proceedings of the Web Conference 2021_ (2020).  https://api.semanticscholar.org/CorpusID:224845398
  * Zafar et al. (2019) Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. 2019.  Fairness Constraints: A Flexible Approach for Fair Classification.  _J. Mach. Learn. Res._ 20, 1 (jan 2019), 2737–2778.
  * Zerveas (2022) George Zerveas. 2022.  Mitigating Bias in Search Results Through Contextual Document Reranking and Neutrality Regularization.  _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_ (2022).  https://api.semanticscholar.org/CorpusID:248837769


# Discussion of ‘A Gibbs sampler for a class of random convex polytopes’

Persi Diaconis  Department of Statistics, Stanford University, Stanford, CA,
94305<EMAIL_ADDRESS>and  Guanyang Wang  Department of
Statistics, Rutgers University, NJ 08854<EMAIL_ADDRESS>
##  1\. Introduction

This very welcome paper by Jacob, Gong, Edlefsen and Dempster [JGED19] is a
fascinating contribution to an important subject. Persistent questions about
the lower and upper probabilities include:

  1. (1)

What does it do in simple problems?

  2. (2)

What does it do in real problems?

  3. (3)

What do the upper and lower probabilities mean?

  4. (4)

How can the needed computations be carried out?

The paper offers answers to these questions by proposing a Gibbs sampler to
perform statistical inference for categorical distributions using the
Dempster-Shafer approach. To be precise, let
$\boldsymbol{x}=(x_{i})_{i=1}^{N}$ be the observations, each comes from one of
the $K$ categories. The model assumes that there exists a
$\theta=(\theta_{1},\cdots,\theta_{K})$ in the $K-$simplex
$\Delta:=\\{(\theta_{1},\theta_{2},\cdots,\theta_{K}):\theta_{i}\geq
0\text{~{}for every~{}}i,\sum_{i=1}^{K}\theta_{i}=1\\}$ such that
$\mathbb{P}(x_{i}=k)=\theta_{k}$ for every $i,k$. Moreover, it is assumed that
the observations $\boldsymbol{x}$ are generated from the following procedure.

  1. (1)

For each $i\in\\{1,\cdots,N\\}$, sample $u_{i}$ uniformly from the simplex
$\Delta$,

  2. (2)

Since $\theta$ partitions $\Delta$ into $K$ disjoint pieces, we set $x_{i}=k$
if $u_{i}\in\Delta_{k}(\theta)$, where $\Delta_{k}(\theta)$ is the
“subsimplex” which have the same vertices as $\Delta$ except for the $k$-th
vertex replaced by $\theta$.

Since this machinery generates $x_{i}$ through $u_{i}$, it is natural to ask
what are the feasible points $\boldsymbol{u}\in\\{(u_{1},u_{2},\cdots
u_{n})\in\Delta^{N}\\}$ that can generate the observed $\boldsymbol{x}$. For a
fixed $\theta$, the set of feasible points
$\mathcal{R}_{\boldsymbol{x}}(\theta)$ are easy to describe, as it is the
product of $N$ subsimplexes:

$\mathcal{R}_{\boldsymbol{x}}(\theta)=\prod_{i=1}^{N}\Delta_{x_{i}}(\theta),$

and the whole feasible set is then

$\mathcal{R}_{\boldsymbol{x}}:=\cup_{\theta\in\Delta}\mathcal{R}_{\boldsymbol{x}}(\theta).$

From $u\in\mathcal{R}_{\boldsymbol{x}}$ one forms
$\mathcal{F}_{u}:=\\{\theta\in\Delta:u_{n}\in\Delta_{x_{n}}(\theta)\text{~{}
for every~{}}n\\}$ and assigns a lower probability to sets $\Sigma$ in the
parameter space by the chance that $\mathcal{F}(u)$ is in $\Sigma$ (this last
by Monte Carlo).

The paper’s main contribution is a Gibbs sampler that samples from the uniform
distribution of $R_{\boldsymbol{x}}$. The problem is challenging due to the
complicated nature of $R_{\boldsymbol{x}}$. In fact, uniformly sampling from
$\mathcal{R}_{\boldsymbol{x}}(\theta)$ is easy (using Algorithm 1 of
[JGED19]), but uniform sampling from the union is much more difficult. The key
observations in the paper are Proposition 3.1 and Proposition 3.2. They
directly characterize the conditional distribution of $\boldsymbol{u}$ and
make it possible for implementing the Gibbs sampler. We find the algorithm
elegant and insightful.

##  2\. The math problem

The new algorithm is interesting as a mathematics problem. The authors have
translated it into a clever probability problem in the case of two categories.
This gives the Markov chain:

(2.1) $\displaystyle Z^{(t)}=B_{1}^{(t)}(1-B_{2}^{(t)})Z^{(t-1)}+B_{2}^{t},$

where $B_{1}^{t}\sim\operatorname{Beta}(N_{1},1)$ and
$B_{2}^{t}\sim\operatorname{Beta}(1,N_{2})$ are independent Beta random
variables and $N_{1},N_{2}$ are two fixed positive integers.

The chain falls into the well-studied area of iterated random functions
[CL91][DF99]. It has been previously studied in [Let02] who offer higher
dimensional versions which might be relevant to the present paper when $k\geq
3$.

In the $k=2$ case, let $P$ be the Markov transition kernel of the chain and
$\pi$ be its stationary distribution. The authors use coupling techniques to
derive the following convergence bound in terms of the Wasserstein-1 distance

(2.2)
$\displaystyle\mathcal{W}_{1}(P^{t}(z,\cdot),\pi)\leq\bigg{(}\frac{N_{1}}{N_{1}+1}\cdot\frac{N_{2}}{N_{2}+1}\bigg{)}^{t}\cdot
W_{1}(\delta_{z},\pi)$

for every initialization $z$, where $\delta_{z}$ is the delta-mass at $z$. As
a small contribution to the conversation, we derive a lower bound of the
convergence speed. Our results suggest
$\frac{N_{1}}{N_{1}+1}\cdot\frac{N_{2}}{N_{2}+1}$ is the exact convergence
rate for the Markov chain. To start with, we prove the stationary distribution
of the chain is another Beta distribution (this result can also be derived
directly from the original formulation of the problem, see Appendix C of
[JGED19]). The following lemma is well known and helpful:

######  Lemma 2.1.

Let $X\sim\operatorname{Beta}(a,b)$, $Y\sim\operatorname{Beta}(a+b,c)$ be
independent random variables with $a,b,c>0$. Then
$XY\sim\operatorname{Beta}(a,b+c)$.

###### Proof.

We show the $k$-th moment of $XY$ equals the $k$-th moment of a
$\operatorname{Beta}(a,b+c)$ random variable for every $k$. Since both $XY$
and beta distributions are bounded by $[0,1]$, standard results in probability
show that the distribution is characterized by all its moments.

The $k$-th moment for a $\operatorname{Beta}(a_{1},a_{2})$ random variable is
$\frac{\Gamma(a_{1}+k)}{\Gamma(a_{1})}\frac{\Gamma(a_{1}+a_{2})}{\Gamma(a_{1}+a_{2}+k)}$,
therefore,

$\displaystyle\mathbb{E}(XY)^{k}$
$\displaystyle=\frac{\Gamma(a+k)}{\Gamma(a)}\frac{\Gamma(a+b)}{\Gamma(a+b+k)}\times\frac{\Gamma(a+b+k)}{\Gamma(a+b)}\frac{\Gamma(a+b+c)}{\Gamma(a+b+c+k)}$
$\displaystyle=\frac{\Gamma(a+k)}{\Gamma(a)}\frac{\Gamma(a+b+c)}{\Gamma(a+b+c+k)},$

which is the same as the $k$-th moment of $\operatorname{Beta}(a+b,c)$
distribution, as desired. ∎

Now we are ready to show $\operatorname{Beta}(N_{1}+1,N_{2})$ is stable under
the transformation $Z\rightarrow B_{1}(1-B_{2})Z+B_{2}$, and is thus the
stationary distribution of the chain $\\{Z^{(0)},Z^{(1)},\cdots,Z^{(n)}\\}$.

######  Proposition 2.2.

Let
$Z\sim\operatorname{Beta}(N_{1}+1,N_{2}),B_{1}\sim\operatorname{Beta}(N_{1},1),B_{2}\sim\operatorname{Beta}(1,N_{2})$
be independent random variables, then
$B_{1}(1-B_{2})Z+B_{2}\sim\operatorname{Beta}(N_{1}+1,N_{2})$.

###### Proof.

Let $Y:=B_{1}(1-B_{2})Z+B_{2}$, then $1-Y=(1-B_{2})(1-B_{1}Z)$. Lemma 2.1
shows $B_{1}Z$ is a $\operatorname{Beta}(N_{1},N_{2}+1)$ random variable,
which in turn shows $1-B_{1}Z\sim\operatorname{Beta}(N_{2}+1,N_{1})$. Since
$1-B_{2}\sim\operatorname{Beta}(N_{2},1)$, apply Lemma 2.1 again yields
$1-Y\sim\operatorname{Beta}(N_{2},N_{1}+1)$. Therefore $Y$ is a
$\operatorname{Beta}(N_{1}+1,N_{2})$ random variable. ∎

Now we turn to lower bound the convergence rate of the Markov chain. Recall
that for any two probability measure $\mu,\nu$ with bounded support , the
Kantorovich- Rubinstein dual theorem shows:

$\mathcal{W}_{1}(\mu,\nu)=\sup_{\\{f:\text{Lip}(f)\leq 1\\}}\int f(d\mu-d\nu)$

Choosing $f(x)=\pm x$ immediately implies $\mathcal{W}_{1}(\mu,\nu)\geq\lvert
m_{1}(\mu)-m_{1}(\nu)\rvert$, where $m_{1}$ stands for the first moment. Let
$\nu=\pi$ and $Z^{(t)}(z)$ be the Markov chain at time $t$ which starts at
$z$. It is clear that $m_{1}(\nu)=\frac{N_{1}+1}{N_{1}+N_{2}+1}$, and the
evolution equation 2.1 yields

(2.3)
$\displaystyle\mathbb{E}(Z^{t}(z))=\frac{N_{1}N_{2}}{(N_{1}+1)(N_{2}+1)}\mathbb{E}(Z^{t-1}(z))+\frac{1}{N_{2}+1}$

Using the initial condition $\mathbb{E}(Z^{0}(z))=z$, recursion 2.3 can be
solved as:

$\mathbb{E}(Z^{t}(z))=\bigg{(}\frac{N_{1}N_{2}}{(N_{1}+1)(N_{2}+1)}\bigg{)}^{t}\bigg{(}z-\frac{N_{1}+1}{N_{1}+N_{2}+1}\bigg{)}+\frac{N_{1}+1}{N_{1}+N_{2}+1}.$

Thus we immediately have

(2.4)
$\displaystyle\mathcal{W}_{1}(P^{t}(z,\cdot),\pi)\geq\bigg{\lvert}z-\frac{N_{1}+1}{N_{1}+N_{2}+1}\bigg{\rvert}\bigg{(}\frac{N_{1}+1}{N_{1}+N_{2}+1}\bigg{)}^{t}.$

Therefore, unless the chain is not initialized at exactly
$\frac{N_{1}+1}{N_{1}+N_{2}+1}$, the exact convergence rate of the Markov
chain equals $\frac{N_{1}+1}{N_{1}+N_{2}+1}$. Combining 2.2 and 2.4, we have
the following:

######  Proposition 2.3.

(2.5)
$\displaystyle\lvert\mathbb{E}Z-z\rvert\leq\mathcal{W}_{1}(P^{t}(z,\cdot),\pi)\bigg{/}\bigg{(}\frac{N_{1}}{N_{1}+1}\cdot\frac{N_{2}}{N_{2}+1}\bigg{)}^{t}\leq\mathbb{E}\lvert
Z-z\rvert,$

where $Z\sim\operatorname{Beta}(N_{1}+1,N_{2})$.

When $z=0$ or $1$, Formula 2.5 shows the convergence speed can be calculately
exactly as the lower bound matches the upper bound perfectly. Moreover, the
function $u:z\rightarrow\mathbb{E}|Z-z|=\int_{0}^{z}\mathbb{P}(Z\leq
t)dt+\int_{z}^{1}\mathbb{P}(Z\geq t)dt$ has derivative
$u^{\prime}(z)=\mathbb{P}(Z\leq z)-\mathbb{P}(Z\geq z)$ almost everywhere.
Therefore $u$ is first decreasing and then increasing on the unit interval,
thus $\max_{z\in[0,1]}u(z)=\max\\{u(0),u(1)\\}$. This gives us the exact
convergence speed for the chain under the worst-case sceneario:

######  Proposition 2.4.

$\sup_{z\in[0,1]}\mathcal{W}_{1}(P^{t}(z,\cdot),\pi)=\frac{\max\\{N_{1}+1,N_{2}\\}}{N_{1}+N_{2}+1}\bigg{(}\frac{N_{1}N_{2}}{(N_{1}+1)(N_{2}+1)}\bigg{)}^{t}.$

###### Proof.

Since $\mathbb{E}|Z-z|$ is maximized at either $z=1$ or $z=0$, the RHS of
Formula 2.5 is upper bounded by
$\frac{\max\\{N_{1}+1,N_{2}\\}}{N_{1}+N_{2}+1}$. Meanwhile, no matter $z=1$ or
$z=0$, we know $|\mathbb{E}Z-z|=\mathbb{E}|Z-z|$, and thus we conclude

$\sup_{z\in[0,1]}\mathcal{W}_{1}(P^{t}(z,\cdot),\pi)=\frac{\max\\{N_{1}+1,N_{2}\\}}{N_{1}+N_{2}+1}\bigg{(}\frac{N_{1}N_{2}}{(N_{1}+1)(N_{2}+1)}\bigg{)}^{t}.$

∎

######  Question 1.

Can the authors see if their general algorithm can be translated into a
vector-valued version of 2.1 for $k$ greater than or equal to $3$?

##  3\. Hypothesis Testing Problems

The introduction to the paper emphasizes problems where the sample size $N$ is
small compared to the number of categories. We have encountered such problems
in our recent work and we find straightforward Bayesian and frequentist
solutions.

######  Example 1.

In studying the popular ‘wash shuffle’ where a deck of $52$ cards is ‘smushed
around the table for $t$ seconds’ (say $t=60$) one wants to test if the cards
are well mixed. Here the data consists of $100$ permutations of
$X_{1},X_{2},\cdots X_{100}$ in $S_{52}$. The number of categories $k=\lvert
S_{52}\rvert\approx 8.6\times 10^{68}$ is huge. One has some partial prior
information. For example, if the cards are not mixed, it may be because
several cards original together are still together. Or the original top (or
bottom) card may still be close to the top (or bottom). In our analysis, we
found statistics $T_{1},T_{2},\cdots T_{l}$ (e.g., $T_{1}=$ the number of
adjacent pairs, $T_{2}=$ position of the original top card, $T_{3}=$ the
distance from the starting distribution in some natural metric, $\dots$).

The distribution of these features can be obtained under the null
distribution. This allows standard frequentist tests. In our work [DW18], we
provided a Bayesian solution to this problem. We considered an exponential
family through the statistics. For $\sigma\in S_{52}$:

$\mathbb{P}_{\theta}(\sigma)=Z^{-1}(\sigma)\exp(\sum_{i=1}^{l}\theta_{i}T_{i}(\sigma)),$

where $Z(\sigma)=\sum\limits_{\sigma\in
S_{52}}\exp(\sum_{i=1}^{l}\theta_{i}T_{i}(\sigma))$ is the normalization
constant. Thus $\theta=0$ is the uniform distribution. The exchange algorithm
[MGM06] allowed us to compute the posterior in a reasoning fashion.

######  Question 2.

Do the authors think there will be a time for their algorithm can be run for
such $N$ and $k$?

##  4\. Remark

As clearly explained in the paper, the uniform distribution on the $k$-simplex
underlies the basic procedure. It is well to be reminded that it is hard to
understand the properties when $k$ is large. The following two examples are
drawn from [DH02].

######  Example 2 (Bayesian Birthday Problem).

Consider $N$ balls dropped into $k$ boxes, with probability
Multinomial$(N,\boldsymbol{\theta})$. What is the chance that all the balls
are dropped into distinct boxes?

If $k=365$, this is the classical birthday problem. The classical frequentist
answer takes $\boldsymbol{\theta}=(\frac{1}{365},\cdots,\frac{1}{365})$ and
shows that the chance is approximately $0.5$ when $N=23$. A ‘flat prior
Bayesian’ puts a uniform prior on the $k$-simplex. Then the chance of all
balls in distinct boxes is approximately $0.5$ when $N=16$. Here, being a
Bayesian does not change things much.

######  Example 3 (Bayesian Coupon Collectors Problem).

With notation as above, consider the question: How large does $N$ have to be
so that the chance that all boxes are covered is close to $0.5$?

The frequentist solution assumes
$\boldsymbol{\theta}=(\frac{1}{365},\cdots,\frac{1}{365})$ and then shows $N$
should be approximately $2287$. Using a uniform prior for
$\boldsymbol{\theta}$, one finds $N$ has to be $191844$. Here, the uniform
prior makes a huge difference.

######  Question 3.

Is the uniform distribution on the simplex a crucial part of the procedure or
could this be varied?

##  5\. A Bit of History

When P.D. was a beginning graduate student at Harvard (1971), Art Dempster
called him in to suggest a possible thesis topic: ‘Find ways to do the
computations required for upper and lower probabilities’. This did not work
out at the time but triggered a lifetime’s interest. It is inspiring to have
tracked his efforts over a $50$ year period. The present paper is important
progress. We look forward to progress on the problems mentioned in our
introduction.

## References

  * [CL91] Jean-François Chamayou and Gérard Letac.  Explicit stationary distributions for compositions of random functions and products of random matrices.  Journal of Theoretical Probability, 4(1):3–36, 1991.
  * [DF99] Persi Diaconis and David Freedman.  Iterated random functions.  SIAM review, 41(1):45–76, 1999.
  * [DH02] Persi Diaconis and Susan Holmes.  A bayesian peek into feller volume i.  Sankhyā: The Indian Journal of Statistics, Series A, pages 820–841, 2002.
  * [DW18] Persi Diaconis and Guanyang Wang.  Bayesian goodness of fit tests: a conversation for david mumford.  Annals of Mathematical Sciences and Applications, 3(1):287–308, 2018.
  * [JGED19] Pierre E Jacob, Ruobin Gong, Paul T Edlefsen, and Arthur P. Dempster.  A Gibbs sampler for a class of random convex polytopes.  arXiv preprint arXiv:1910.11953, 2019.
  * [Let02] Gérard Letac.  Donkey walk and dirichlet distributions.  Statistics & probability letters, 57(1):17–22, 2002.
  * [MGM06] Iain Murray, Zoubin Ghahramani, and David JC MacKay.  MCMC for doubly-intractable distributions.  In Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence, pages 359–366, 2006.