# Fair Active Ranking from Pairwise Preferences

Sruthi Gorantla  Indian Institute of Science, Bengaluru, India.
<EMAIL_ADDRESS>Sara Ahmadian  Google Research<EMAIL_ADDRESS>
###### Abstract

We investigate the problem of probably approximately correct and fair (PACF)
ranking of items by adaptively evoking pairwise comparisons. Given a set of
$n$ items that belong to disjoint groups, our goal is to find an
$(\epsilon,\delta)$-PACF-Ranking according to a fair objective function that
we propose. We assume access to an oracle, wherein, for each query, the
learner can choose a pair of items and receive stochastic winner feedback from
the oracle. Our proposed objective function asks to minimize the $\ell_{q}$
norm of the error of the groups, where the error of a group is the $\ell_{p}$
norm of the error of all the items within that group, for $p,q\geq 1$. This
generalizes the objective function of $\epsilon$-Best-Ranking, proposed by
Saha and Gopalan,  (2019).

By adopting our objective function, we gain the flexibility to explore
fundamental fairness concepts like equal or proportionate errors within a
unified framework. Adjusting parameters $p$ and $q$ allows tailoring to
specific fairness preferences. We present both group-blind and group-aware
algorithms and analyze their sample complexity. We provide matching lower
bounds up to certain logarithmic factors for group-blind algorithms. For a
restricted class of group-aware algorithms, we show that we can get reasonable
lower bounds. We conduct comprehensive experiments on both real-world and
synthetic datasets to complement our theoretical findings.

##  1 Introduction

Ranking is a fundamental problem in data mining and machine learning that
arises in a wide range of applications, such as search engines, recommender
systems, and information retrieval. The simplest and most extensively studied
version of ranking uses noisy pairwise comparisons, as initiated by Feige et
al.,  (1994). Recently, it has also been studied with dueling bandits (Busa-
Fekete and Hüllermeier, , 2014).

Ranking problems have been studied under fairness constraints to mitigate or
eliminate the bias and discrimination in the solutions constructed by the
existing algorithms. The primary focus of these works is on generating
rankings with respect to socially salient attributes (Zehlike et al., 2022a, ;
Zehlike et al., 2022b, ; Pitoura et al., , 2022) that asks for equal or
proportional representation within every prefix of the ranking. Although such
fairness constraints are especially useful in human-centric applications, such
as hiring, credit allocation, recidivism prediction, and college admissions,
they may still produce adverse outcomes for particular groups of individuals.
This is primarily because the error in ranking is measured as an aggregate of
errors over all the items. The resulting ranking may systematically
discriminate against minority groups in terms of error, even after applying
representation fairness constraints. The error function does not take into
account biases in the data or differences in the data distributions for
different demographic groups.

We introduce a fair ranking inspired by social fairness concepts, which
focuses on generating rankings that fairly distribute error across groups. Our
metric is versatile in the definition of the error within each group and in
the aggregation of the errors over different groups. This yields a metric that
generalizes several well-known notions of fairness.

In this paper, we study active, PAC ranking of $n$ items using pairwise
comparisons. In this setting, the learner receives preference feedback, for
requested pairwise comparisons, according to the well-known Plackett-Luce (PL)
probability model. The learner’s goal is to find a near-optimal ranking, with
respect to tolerance parameter $\epsilon$, with high probability $(1-\delta)$,
using as few pairwise comparison rounds as possible. Overall, our
contributions can be summarized as follows:

  1. 1.

We introduce a fair variant of the error metric for rankings based on social
fairness concepts (Definition 1). To this end, we also discuss the limitations
of previous fair ranking definitions (Section 3), and how algorithms optimized
for our proposed objective function overcome these limitations.

  2. 2.

We study two classes of algorithms depending on whether they have access to
the group labels of the items or not. We call the algorithms without access
group-blind and those with access group-aware. We design efficient algorithms
output probably approximately correct rankings for our fair objective function
and analyse their sample complexity bounds. We provide matching lower bounds
up to certain logarithmic factors for group-blind algorithms. For a restricted
class of group-aware algorithms, we show that we can get reasonable lower
bounds.

  3. 3.

We empirically evaluate our algorithms on real-world and synthetic datasets
and show that our group-aware algorithm has significantly lower sample
complexity than the group-blind. We also show that our group-aware algorithm
achieves lower overall error as well as lower error on all the groups than
group-blind algorithm.

In Section 2, we discuss several related works. In Section 3, we introduce our
metric and define PAC ranking for our metric. In Sections 4 and 5, we show our
main theoretical and experimental results respectively.

##  2 Related Works

##### Fairness in ranking.

Group fairness notions ask for groups to be treated equally, such as asking
for equality of opportunity in supervised learning (Hardt et al., , 2016),
equitable clustering costs across groups in clustering (Ghadiri et al., ,
2021; Abbasi et al., , 2021; Chlamtac et al., , 2022; Gorantla et al., ,
2023), and equal representation of the groups in ranking (Celis et al., ,
2018) or subset selection (Kleinberg and Raghavan, , 2018). On the contrary,
individual fairness treats fairness at the individual level and not as some
aggregate function of groups. It asks for similar individuals to be treated
similarly for the task at hand (Dwork et al., , 2012). Particularly in
ranking, the group fairness notions include ensuring sufficient representation
of all the groups in each prefix of the top $k$ ranking (Celis et al., , 2018;
Zehlike et al., , 2017; Zehlike et al., 2022a, ) or every $k$ consecutive
ranks (Gorantla et al., , 2021). Other works ask for equality of exposure of
the groups (Singh and Joachims, , 2018), fair ranking under uncertain merit
scores (Singh et al., , 2021), fair ranking with noisy sensitive attributes
(Mehrotra and Vishnoi, , 2022), fair ranking in the presence of implicit bias
(Celis et al., , 2020), etc. However, these are all algorithmic solutions that
assume access to the merit (or relevance) scores of the items and maximize
some objective function such as NDCG, Precision@$k$. In contrast, we assume
that we only have oracle access to pairwise preferences of the items and study
the problem of inferring a ranking with a minimal number of queries with high
confidence $1-\delta$, and up to an error $\epsilon$, while ensuring fairness
in errors incurred by the groups. Even though previous works such as (Saha and
Gopalan, , 2019) studied non-fair variant of the problem in the pairwise
preference model, to the best of our knowledge, we are the first to study this
with fairness consideration.

##### Cascaded norms for fairness.

Cascaded norm objectives have been used in generalizing the cost-based
objective functions to account for different costs borne by different groups.
Metric space clustering objective asks for minimizing the $\ell_{p}$-norm of
the distances between points in a cluster and their center. Most interesting
cases are when $p\in\\{1,2,\infty\\}$ as they correspond to the well studied
$k$-median, $k$-means, and $k$-center, respectively. Chlamtac et al.,  (2022)
later generalized this further to account for group fairness. They ask to
minimize the $\ell_{q}$-norm of the cost of the groups, where cost of a group
is the $\ell_{p}$-norm of the distances between the points in a cluster from
that group and their cluster center. This generalizes the fair clustering
notions such as Socially Fair $k$-means and $k$-medians clustering. This
objective function allows us to treat many problems under one umbrella. Taking
inspiration from this, we propose the notion of $\epsilon$-Best-Fair-Ranking,
using norms of errors in a cascaded fashion, first within the groups and then
across the groups.

##### Active ranking from pairwise comparisons.

Pairwise comparisons are well-motivated for the sake of ranking as they
provide an easier way of collecting peoples’ preferences; it is easier to
compare two candidates for a job rather than assign an absolute score to them
independently and compare the scores to get relative preferences. Even
mathematically speaking, pairwise preferences enforce a weaker constraint on
the data collection process than asking for exact scores because the former
need not satisfy transitivity in the pairwise preferences of the items while
the latter induces transitivity on the items. The passive sample complexity
for ranking with pairwise comparisons has been resolved under different model
assumptions in recent works (Gleich and Lim, , 2011; Rajkumar and Agarwal, ,
2016). The exact sample complexity depends on the objective function defined
to measure the “goodness” of the ranking. However, collecting pairwise
preference labels might be expensive. Active learning has become a prevailing
technique for designing efficient supervised learning algorithms, where one
only needs to query labels that are most “informative”. In many settings,
active learning gives an exponential improvement in the sample complexity
compared to its passive counterparts under some weak distributional
assumptions (Balcan and Long, , 2013). Recent works have studied ranking in
the active or adaptive setting (Ailon, , 2012; Jamieson and Nowak, , 2011;
Saha and Gopalan, , 2019; Ren et al., , 2021), among which Ren et al.,
(2021); Saha and Gopalan,  (2019) studied PAC sample complexity bounds in a
multi-wise comparisons feedback model. There have also been works on
estimating the parameters of the pairwise preference model that generates the
rankings Khetan and Oh,  (2016).

##  3 Preliminaries

##### Notation.

For any positive integer $t$, we use $[t]$ to denote the set of integers
$\\{1,2,\ldots,t\\}$. Let ${\mathcal{I}}$ represent the set of items and the
set $\Sigma_{\mathcal{I}}$ to contain all possible permutations of the items
in ${\mathcal{I}}$. Then for any permutation
$\boldsymbol{\sigma}\in\Sigma_{\mathcal{I}}$, $\boldsymbol{\sigma}(j)$
represents the index of item in $j$-th position of the permutation. We use
$\boldsymbol{\sigma}^{-1}(i)$ to represent the position item $i$ is assigned
to in the permutation. We assume that the set of items can be partitioned into
$\gamma$ disjoint groups based on socially salient features such as age, race,
gender, etc, denoted as $G_{1},G_{2},\ldots,G_{\gamma}$. Let
$n_{h}:=|G_{h}|,\forall h\in[\gamma]$ and $n:=|{\mathcal{I}}|$. Therefore,
$n=\sum_{h\in[\gamma]}n_{h}$.

##### The active ranking problem.

Given a set ${\mathcal{I}}$ of items, a ranking $\boldsymbol{\sigma}$ defines
a total ordering of the items. Let us assume that each item
$i\in{\mathcal{I}}$ is associated with a true relevance score
$\theta_{i}\in{\mathbb{R}}$, where the higher the value of $\theta_{i}$, the
better to rank it at the top. There is only one ranking that is consistent
with the true scores – the one that ranks the items in the descending order of
their true scores. However, we consider the setup where the true scores are
not directly available, but any pair of items can be compared via an oracle,
which has access to their true scores. Depending on the type of feedback from
the oracle, the goal is to find a ranking of the items by actively querying
for pairwise comparisons of the items one after the other. It is useful to
note that sorting $n$ items based on pairwise comparisons fits in this problem
setup, which needs $\Theta(n\log n)$ actively chosen pairwise comparison
queries. Note that the pairwise comparison queries are fixed up front in the
passive setup; hence, the output of one query does not affect what other
queries are made by the algorithm, unlike the active setup.

##### Plackett-Luce (PL) feedback oracle.

PL model is extensively used in generating stochastic rankings Rajkumar and
Agarwal,  (2016); Saha and Gopalan,  (2019); Singh et al.,  (2021). The
probability of sampling a ranking in the PL model is given by,

$\Pr[\boldsymbol{\sigma}|\theta_{1},\ldots,\theta_{n}]=\prod_{i\in[n]}\frac{\theta_{\sigma^{-1}(i)}}{\sum_{j=i}^{n}\theta_{\sigma^{-1}(j)}}.$

An appealing property of the PL model is that the pairwise winner
probabilities for a pair of items $\\{i,i^{\prime}\\}\in{\mathcal{I}}$ are
very easy to calculate. That is,

$\Pr[i\mid\\{i,i^{\prime}\\}]=\frac{\theta_{i}}{\theta_{i}+\theta_{i^{\prime}}}~{}~{}\text{and}~{}~{}\Pr[i^{\prime}\mid\\{i,i^{\prime}\\}]=\frac{\theta_{i^{\prime}}}{\theta_{i}+\theta_{i^{\prime}}}.$

Saha and Gopalan,  (2019) also studied the PAC sample complexity bounds under
the PL model to leverage the property of independence of irrelevant attributes
satisfied by the PL model, which helps in consistently aggregating pairwise
preferences to find a total ordering. Hence, we also study our problem under
the PL model.

##### Ranking performance.

In a ranking $\boldsymbol{\sigma}$, each item $i$ suffers an error based on
the items incorrectly ordered above $i$. One way of quantifying this error is
as follows,

$d_{i}(\boldsymbol{\sigma};\theta):=\max_{\begin{subarray}{c}i^{\prime}\in[n]~{}\text{s.t.}\\\
\theta_{i}>\theta_{i^{\prime}}\land\boldsymbol{\sigma}^{-1}(i)>\boldsymbol{\sigma}^{-1}(i^{\prime})\end{subarray}}\theta_{i}-\theta_{i^{\prime}}.$

If there are no items with higher scores ranked after $i$, we define the error
for $i$ to be zero. Then, the performance of a candidate ranking
$\boldsymbol{\sigma}\in\Sigma_{{\mathcal{I}}}$ can be measured as an aggregate
of the errors of the items. One such metric proposed by Saha and Gopalan,
(2019) is the $\ell_{\infty}$ norm of the errors of the items. Using this,
Saha and Gopalan,  (2019) define a ranking
$\boldsymbol{\sigma}\in\Sigma_{{\mathcal{I}}}$ to be an $\epsilon$-Best-
Ranking iff,

$\text{err}(\boldsymbol{\sigma};\theta):=\max_{i\in{\mathcal{I}}}~{}~{}d_{i}(\boldsymbol{\sigma};\theta)<\epsilon.$
(1)

A $0$-Best-Ranking is called a Best-Ranking or optimal ranking of the PL
model.

Figure 1: Example of different $\epsilon$-Best-Rankings.

We will now illustrate the shortcomings of this metric with an example (see
Figure 1). Let there be a set of $9$ items such that $6$ items belong to
group-A (let us call this the majority group) and $3$ items belong to group-B
(minority group). Let their true scores be $\theta_{i}=1-((i-1)*0.09)$ for
each $i=1,2,\ldots,10$. Then, their optimal PL ranking is as shown in Figure
1. We use $A_{t}$ and $B_{t}$ to represent $t$-th item from group-$A$ and
group-$B$, respectively, in the order in which they appear in the optimal PL
ranking. For $\epsilon=0.09$ all of
$\boldsymbol{\sigma}_{1},\boldsymbol{\sigma}_{2},$ and
$\boldsymbol{\sigma}_{3}$ are $\epsilon$-Best-Rankings. However, in
$\boldsymbol{\sigma}_{1}$, all the error is borne by group-$B$, and in
$\boldsymbol{\sigma}_{2}$, even though both the groups incur errors, the
errors are unequal. Hence, $\epsilon$-Best-Ranking does not guarantee a fair
distribution of error across different groups of items.
$\boldsymbol{\sigma}_{3}$ is a good solution as both the groups incur an error
of $\epsilon$. Hence, we need to optimize the algorithms for an objective
function that distributes error fairly across groups. We also note here that
$\boldsymbol{\sigma}_{1}$ also satisfies the notion of proportional
representation of the groups proposed in (Gorantla et al., , 2021) since in
every $3$ consecutive ranks, there are $2$ items from group-$A$ and $1$ item
from group-$B$. Hence, achieving a proportional representation of groups in
ranking may not be sufficient to ensure a fair distribution of error across
groups.

##### Proposed metric.

We propose to use a parameterized variant of the error, namely, using the
$\ell_{q}$ norm of the group-wise error, where the group-wise error is nothing
but the $\ell_{p}$-norm of the errors of the items within the group. Then, a
good ranking can be characterized as follows,

######  Definition 1 ($\epsilon$-Best-Fair-Ranking).

For numbers $p,q\in[1,\infty)$ and a non-negative weight function
$w:[\gamma]\rightarrow{\mathbb{R}}_{\geq 0}$ that assigns weights to groups,
$\boldsymbol{\sigma}\in\Sigma_{{\mathcal{I}}}$ is an $\epsilon$-Best-Fair-
Ranking iff

$\displaystyle\text{err}^{\texttt{fair}}(\boldsymbol{\sigma};\theta):=\bigg{(}\sum_{h\in[\gamma]}w(h)\cdot\text{err}_{h}(\boldsymbol{\sigma};\theta)^{q}\bigg{)}^{\frac{1}{q}}<\epsilon,$
(2) $\displaystyle\text{where,}~{}~{}\forall
h\in[\gamma],\text{err}_{h}(\boldsymbol{\sigma};\theta):=\left(\sum_{i\in
G_{h}}d_{i}(\boldsymbol{\sigma};\theta)^{p}\right)^{\frac{1}{p}}.$ (3)

In our example in Figure 1, if we compute the $\ell_{p}$ norm of the error
incurred by the items within the group for smaller values of $p$ (say $p=1$),
we get that group $B$ incurs an error of $3\epsilon$ and $2\epsilon$ with
$\boldsymbol{\sigma}_{1}$ and $\boldsymbol{\sigma}_{2}$ respectively. Whereas,
group $A$ incurs an error of $0$ and $\epsilon$ in $\boldsymbol{\sigma}_{1}$
and $\boldsymbol{\sigma}_{2}$ respectively. Further, $\ell_{q}$ norm of the
errors across the groups, with $q=1$ and $w(A)=w(B)=1$, gives us that the
overall $(\ell_{p},\ell_{q})$ error is $3\epsilon$ for both
$\boldsymbol{\sigma}_{1}$ and $\boldsymbol{\sigma}_{2}$. But the
$(\ell_{p},\ell_{q})$ error for $\boldsymbol{\sigma}_{3}$ is still $\epsilon$.
Therefore, algorithms designed for our objective have $(\ell_{p},\ell_{q})$
error less than $\epsilon$, with high probability.

In this paper, we study the problem with the weight functions of the form
$w(h):=\frac{\phi_{h}}{n_{h}}$ for each group $h\in[\gamma]$, where
$1\leq\phi_{h}\leq n_{h}$. This is already a rich class of weight functions
since setting $\phi_{h}=1$ measures the average of the errors of the group’s
items, allowing us to achieve proportional errors across groups. Setting
$\phi_{h}=n_{h}$ counts the number of items from the group on which the
algorithm makes an error, achieving equal errors across groups.

Note that $\epsilon$-Best-Fair-Ranking is a generalization of $\epsilon$-Best-
Ranking as shown in the following theorem, the proof of which appears in
Appendix A. thmequivalence A ranking
$\boldsymbol{\sigma}\in\Sigma_{{\mathcal{I}}}$ is an $\epsilon$-Best-Fair-
Ranking for $p,q\rightarrow\infty$ and any non-negative weight function $w$,
if and only if it is an $\epsilon$-Best-Ranking.

######  Remark.

When $q\rightarrow\infty$, Definition 1 asks for the maximum group-wise
$\ell_{p}$ norm error to be less than $\epsilon$. This is similar to asking
for egalitarian fairness while ranking items belonging to socially salient
groups. Such a notion has also been studied as socially fair clustering, first
introduced in Ghadiri et al.,  (2021) and later generalized in a way similar
to Definition 1 in Chlamtac et al.,  (2022).

A Probably-Approximately-Correct (PAC) ranker is a ranking algorithm that, for
any problem instance including two parameters $\epsilon,\delta\in(0,1)$,
sequentially makes a finite number of oracle calls and outputs a ranking
$\boldsymbol{\sigma}$ of the items such that the error $err$ is less than
$\epsilon$ with probability greater than $1-\delta$. Saha and Gopalan,  (2019)
studied the PAC ranking problem in the Plackett-Luce feedback oracle setup
with subset-wise preferences. They give an optimal sample complexity bound for
error defined as Equation 1.

##### Probably-Approximately-Correct and fair ranker.

We study a group-fair variant of the PAC ranking problem, where the only
difference is that we measure the error using Equation 2. Then an algorithm
that satisfies this can be defined as follows,

######  Definition 2 ($(\epsilon,\delta)$-PACF-Ranker).

A sequential algorithm that outputs a ranking is called
$(\epsilon,\delta)$-PACF-Ranker if it always outputs a ranking after a finite
number of oracle calls, and the ranking output is an $\epsilon$-Best-Fair-
Ranking with probability at least $1-\delta$ for given parameters $p$, $q$ and
a weight function $w$.

We refer to the number of oracle calls as sample complexity interchangeably
throughout this paper. In conclusion, this paper aims to answer two questions:

  1. 1.

What is the worst case minimum expected sample complexity required to learn an
$\epsilon$-Best-Fair-Ranking?

  2. 2.

Is there an $(\epsilon,\delta)$-PACF-Ranker with matching sample complexity?

######  Remark.

(Group-Aware vs. Group-Blind). Note that the group membership of the items may
not always be available to the algorithm due to legal restrictions or simply
because of the unavailability of the labeling. We call the algorithms with
access to group information group-aware algorithms and those without access to
group information group-blind. In this paper, we answer the questions above
for both types of algorithms.

Further, we consider the class of algorithms that satisfy symmetry defined in
Saha and Gopalan,  (2019), additionally conditioning on appropriate mapping of
the group membership. Roughly speaking, the algorithms should be insensitive
to the specific labeling of the items. This property is needed to get tighter
lower bounds. For a formal definition, see Definition 3 in Section B.1.

##  4 Theoretical Results

For the group-blind case, we show that using Beat-the-Pivot from Saha and
Gopalan,  (2019) with appropriately adjusted error parameter $\epsilon$ and
confidence parameter $\delta$ already gives us an efficient
$(\epsilon,\delta)$-PACF-Ranker. However, our key contribution is the lower
bound on the sample complexity. Formally, we prove the following theorem.
[group-blind sample complexity]thmblindbound Given an error parameter
$\epsilon\in(0,1)$, a confidence parameter $\delta\in[0,1]$, and a class of
group-blind and symmetric $(\epsilon,\delta)$-PACF-Rankers, ${\mathcal{A}}$,
for PL feedback, there exists an instance $\nu$ such that any algorithm in
${\mathcal{A}}$ on $\nu$ needs
$\Omega\left(\frac{n^{1+\max\left\\{\frac{2}{q},\frac{2}{p}\right\\}}}{\epsilon^{2}}\right)$
samples.

Further, $\exists$ $(\epsilon,\delta)$-PACF-Ranker with sample complexity
$O\left(\frac{n^{1+\max\left\\{\frac{2}{q},\frac{2}{p}\right\\}}}{\epsilon^{2}}\log\frac{n}{\delta}\right)$.
Proving the lower bound on the sample complexity involves defining a true
instance, i.e., the scores of the items, and defining a class of alternative
instances with the scores modified from the true scores. The crucial step here
is to define an event carefully so that the event being satisfied is a
necessary condition for any $(\epsilon,\delta)$-PACF-Ranker algorithm on the
true instance. Moreover, we need the complement of the event to be a necessary
condition on the $(\epsilon,\delta)$-PACF-Ranker algorithms for any of the
alternative instances.

######  Remark.

The set of hard instances in Saha and Gopalan,  (2019) only give a loose lower
bound of $\Omega\left(\frac{n}{\epsilon^{2}}\log\frac{n}{\delta}\right)$.
Hence, we need a more creative construction of the class of hard instances and
the event, that takes into account that the errors of the items may accumulate
in $\text{err}^{\texttt{fair}}$ (Equation 2), rather than solely focusing on
the maximum error, as done in err (Equation 1).

Below, we give a proof sketch where we focus on the design of our hard class
of instances and the definition of a suitable event. The full proof can be
found in Section B.2.

###### Proof Sketch.

For a given set of items ${\mathcal{I}}$ with input parameters
$\epsilon,\delta,p,q$, and $\phi_{h},\forall h\in[\gamma]$, we fix a subset of
$T\subset{\mathcal{I}}$ of size $n/4$. Let
${\tilde{\epsilon}}=\epsilon\cdot\left(\frac{4}{n}\right)^{1/p}$. Then, an
instance of the problem is denoted by a subset
$S\subseteq{\mathcal{I}}{\setminus}T$ such that the scores of the items for
this instance are,

$\displaystyle\forall i\in
S,~{}~{}\theta_{i}=\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2},\quad\forall
i\in
T,~{}~{}\theta_{i}=\theta\left(\frac{1}{4}-{\tilde{\epsilon}}^{2}\right),\text{and}\quad\forall
i\not\in S\cup
T,~{}~{}\theta_{i}=\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}.$

We then fix a set ${S^{*}}\subseteq{\mathcal{I}}{\setminus}T$ of size
$|{S^{*}}|=n/4$ to be the true instance and any set
${\tilde{S}}^{*}={S^{*}}\cup({\mathcal{I}}{\setminus}({S^{*}}\cup T))$ of size
$|{\tilde{S}}^{*}|=n/2$ to be an alternative instance. Note that there will be
${{n/2}\choose{n/4}}$ such alternative instances for every true instance
${S^{*}}$. Then, we define the event to be,

${\mathcal{E}}(S):=\left\\{\left|(S\cup
T)\cap\boldsymbol{\sigma}_{{\mathcal{A}}}\left(\frac{n}{4}+2:n\right)\right|<\frac{n}{4}\right\\}.$

That is, for any ranking $\boldsymbol{\sigma}_{\mathcal{A}}$ output by any
symmetric $(\epsilon,\delta)$-PACF-Ranker on an instance $S$, the ranks
$\frac{n}{4}+2$ to $n$ contain less than $\frac{n}{4}$ items from ${S^{*}}\cup
T$. This is a high probability ($>1-\delta$) event for ${S^{*}}$ because,
otherwise, at least $n/4$ items suffer an error such that the errors add up to
more than $\epsilon$. On the contrary, this event is a low probability
($<\delta$) event for alternative instances because unless all the items in
$T$ appear in the ranks $\frac{n}{4}+2$ to $n$, the ranking can not have an
error less than $\epsilon$. But $|T|=n/4$. Hence, if the event is satisfied,
the error is greater than $\epsilon$. Hence, we apply the change-of-measure
inequality by Kaufmann et al.,  (2014) to get a lower bound tight up to $\log$
factors.
Upper bound. Follows from the sample complexity guarantees of Beat-the-Pivot
proved in Saha and Gopalan,  (2019), because we run it with error parameter
${\tilde{\epsilon}}:=\epsilon/n^{\max\\{1/p,1/q\\}}$ and confidence parameter
$\delta$. ∎

Next, we show the sample complexity bounds for group-aware algorithms. We
design an algorithm that uses the additional “group” information in an
adaptive fashion. The key idea in our algorithm design is ensuring that we
efficiently balance our queries between inter-group and intra-group pairwise
comparisons and in the right order. Its sample complexity is as stated below.
[group-aware upper bound]thmawareupper Algorithm 1 is a group-aware
$(\epsilon,\delta)$-PACF-Ranker
with sample complexity
${\mathcal{O}}\left(\left(\left(\sum_{h=1}^{\gamma}\frac{n_{h}^{1+\frac{2}{p}}}{\epsilon_{h}^{2}}\right)+\frac{n\cdot
n_{g}^{2/p}\log\gamma}{\epsilon_{g}^{2}}\right)\log\frac{n}{\delta}\right)$,
where
$\epsilon_{h}=\epsilon\cdot\left(\frac{n_{h}}{\phi_{h}\gamma}\right)^{1/q}$
and
$g=\arg\min\limits_{h\in[\gamma]}\frac{\epsilon_{h}}{2}\cdot\left(\frac{2}{n_{h}}\right)^{1/p}$.

###### Proof Sketch.

Briefly, Algorithm 1 proceeds in two steps:
Step 1) The algorithm finds group-wise rankings of the groups separately, by
calling Beat-the-Pivot on each group with a group-dependent error parameter
${\tilde{\epsilon}}_{h}/2$ and a confidence parameter
$\frac{\delta}{2n\gamma}$. Beat-the-Pivot outputs a ranking of the items from
the group such that between any two items from the group, the error is at most
${\tilde{\epsilon}}_{h}/2$. This steps makes
${\mathcal{O}}\left(\left(\sum_{h=1}^{\gamma}n_{h}^{1+\frac{2}{p}}/\epsilon_{h}^{2}\right)\log\frac{n}{\delta}\right)$
queries.
Step 2) The algorithm then merges the group-wise rankings, two at a time as
shown in the while loop in Lines 6 to 12. The merging subroutine simply calls
Beat-the-Pivot with error parameter corresponding to the lower
${\tilde{\epsilon}}_{h}$ amongst the two lists and confidence parameter
$\frac{\delta}{2n\gamma}$ on pairs of items to get a pairwise winner. Using
this, it merges the lists, similar to the merge step in the merge sort
algorithm. Since we merge two lists at a time, after at most $\log\gamma$ many
iterations, we will have one final sorted list, labeled as
$\boldsymbol{\sigma}_{1}$. Note that merging two lists of size $l_{1}$ and
$l_{2}$ needs $O(l_{1}+l_{2})T_{q}$ many queries, where $T_{q}$ is the
pairwise query complexity. For the error and confidence parameters mentioned
above, Beat-the-Pivot returns pairwise ranking after
$T_{q}=O\left(\frac{1}{\epsilon_{g}^{2}}\log\frac{n}{\delta}\right)$ many
queries. Therefore, each iteration of the $\log\gamma$ iterations of the while
loop in Lines 6 to 12 makes
$O\left(\left((l_{1}+l_{2})+(l_{3}+l_{4})+\cdots+(l_{\gamma-1}+l_{\gamma})\right)/\epsilon_{g}^{2}\log\frac{n}{\delta}\right)$
$=O\left(\frac{n}{\epsilon_{g}^{2}}\log\frac{n}{\delta}\right)$ many queries,
concluding the proof. ∎

We complement our result with a lower bound, but for a restricted class of
algorithms that only compare items from the same group (in-group algorithms
$\widetilde{{\mathcal{A}}}$). [group-aware lower bound for
$\widetilde{{\mathcal{A}}}$]thmawarelower Given an error parameter
$\epsilon\in(0,1)$, a confidence parameter $\delta\in[0,1]$, and a class of
group-aware, symmetric, and in-group $(\epsilon,\delta)$-PACF-Rankers,
$\widetilde{{\mathcal{A}}}$, for PL feedback, there exists an instance $\nu$
such that any algorithm in $\widetilde{{\mathcal{A}}}$ on $\nu$ needs
$\Omega\left(\sum_{h=1}^{\gamma}n_{h}^{1+\frac{2}{p}}/\epsilon_{h}^{2}\right)$
samples, where
$\epsilon_{h}=\epsilon\cdot\left(\frac{n_{h}}{\phi_{h}\gamma}\right)^{1/q}$.

Algorithm 1 Our “group-aware” Algorithm

0:
$\epsilon,\delta,p,q,\gamma,G_{1},G_{2},\ldots,G_{\gamma},\phi_{h},n_{h},\forall
h\in[\gamma]$.

0: $\epsilon$-Best-Fair-Ranking of items $\bigcup_{h\in[\gamma]}G_{h}$.

1: main Find-Ranking

2: for $h=1,2,\ldots,\gamma$ do

3:
$\epsilon_{h}\leftarrow\epsilon\cdot\left(\frac{n_{h}}{\phi_{h}\gamma}\right)^{1/q}$,
${\tilde{\epsilon}}_{h}\leftarrow\epsilon_{h}\cdot\left(\frac{2}{n_{h}}\right)^{1/p}$

4: $\boldsymbol{\sigma}_{h}\leftarrow$ Beat-the-Pivot
$\left(G_{h},\frac{{\tilde{\epsilon}}_{h}}{2},\frac{\delta}{2n\gamma}\right)$

5: end for

6: while $\gamma>1$ do

7: for $h=1,3,5,\ldots,\gamma-1$ do

8: $\boldsymbol{\sigma}_{h}\leftarrow$
Merge$\left(\boldsymbol{\sigma}_{h},\boldsymbol{\sigma}_{h+1},\min\\{\epsilon_{h},\epsilon_{h^{\prime}}\\},\frac{\delta}{2n^{2}\gamma}\right)$

9: $\epsilon_{h}\leftarrow\min\\{\epsilon_{h},\epsilon_{h^{\prime}}\\}$

10: end for

11: $\gamma\leftarrow\gamma/2$

12: end while

13: return $\boldsymbol{\sigma}_{1}$

14: end main

15: function Beat-the-Pivot$\left(S,\epsilon,\delta\right)$

16: Run Beat-the-Pivot from Saha and Gopalan,  (2019) on items in $S$ to get
an $\epsilon$-Best-Ranking.

17: end function

18: function
Merge$\left(\boldsymbol{\sigma},\boldsymbol{\sigma}^{\prime},\epsilon,\delta\right)$

19: Set $\boldsymbol{\sigma}_{\text{merged}}$ to an empty ranking

20: while neither $\boldsymbol{\sigma}$ nor $\boldsymbol{\sigma}^{\prime}$ is
empty do

21: $i\leftarrow\textsc{Pop}(\boldsymbol{\sigma})$,
$i^{\prime}\leftarrow\textsc{Pop}(\boldsymbol{\sigma}^{\prime})$

22: $\boldsymbol{\sigma}_{\text{pair}}\leftarrow$ Beat-the-
Pivot$(\\{i,i^{\prime}\\},\epsilon,\delta)$

23: if $i$ is ranked lower in $\boldsymbol{\sigma}_{\text{pair}}$ then

24: Append $i$ to $\boldsymbol{\sigma}_{\text{merged}}$

25: else

26: Append $i^{\prime}$ to $\boldsymbol{\sigma}_{\text{merged}}$

27: end if

28: end while

29: if $\boldsymbol{\sigma}$ is empty then

30: Append the rest of $\boldsymbol{\sigma}^{\prime}$ to
$\boldsymbol{\sigma}_{\text{merged}}$

31: else if $\boldsymbol{\sigma}^{\prime}$ is empty then

32: Append the rest of $\boldsymbol{\sigma}$ to
$\boldsymbol{\sigma}_{\text{merged}}$

33: end if

34: return $\boldsymbol{\sigma}_{\text{merged}}$

35: end function

###### Proof Sketch.

The set of instances we construct are those where finding a group-wise ranking
is hard. Since the error metric $\text{err}^{\texttt{fair}}$ aggregates errors
across groups, we now define the event that depends on errors from at least
half of the groups. Showing that such an event is good enough to differentiate
sufficiently the true instance from the alternative instances is crucial,
after which the proof follows from the lower bound proof for the group-blind
case applied on the groups separately (see Section B.3). ∎

##### Addressing the restriction on algorithms.

For the algorithms that are allowed to make pairwise comparisons of items from
different groups, it becomes challenging to bound the KL divergence between
true and alternative instances for some of the pairwise comparisons. Hence,
techniques other than using the change-of-measure argument by Kaufmann et al.,
(2014) may be needed to prove lower bounds for the entire class of group-aware
and symmetric $(\epsilon,\delta)$-PACF-Rankers.

##### Addressing the gap.

The gap in our lower and upper bound for the group-aware case is mainly in
terms of the sample complexity to merge the ranked lists of groups. We believe
that our upper bound is optimal because it holds true under exact pairwise
comparisons111see this for a short proof on the lower bound on pairwise
comparisons to merge $k$ sorted lists rather than comparisons drawn from the
PL model. However, a little thought will convince the reader that the
techniques used to prove lower bound for the exact comparisons case do not
readily extend to the stochastic feedback case, which is also seen in the
problem of finding a sorted list of $n$ items. In the exact case, the sample
complexity is $\Omega(n\log n)$. However, for the stochastic feedback case in
the PAC learning setup studied in Saha and Gopalan,  (2019), the lower bound
is $\Omega\left(\frac{n}{\epsilon^{2}}\log\frac{n}{\delta}\right)$, which
needed several non-trivial ideas that diverge from the approaches employed in
the exact sorting case.

We would also like to stress that the sample complexity needed to find group-
wise rankings dominates the sample complexity to merge sorted group-wise
rankings in some problem instances, ignoring the $\log\gamma$ factor. For
example, let $\phi_{h}=1$ and $q>p$. Then, $\epsilon_{h}=c_{1}n_{h}^{1/q}$ and
${\tilde{\epsilon}}_{h}=c_{2}n_{h}^{1/q-1/p}$ for some constants $c_{1}$ and
$c_{2}$. Since $1/p>1/q$, ${\tilde{\epsilon}}_{h}$ is inversely proportional
to the size of the group, whereas $\epsilon_{h}$ is directly proportional to
the size of the group. W.l.o.g., let $n_{1}\geq n_{2}\geq\cdots\geq
n_{\gamma}$. Then, $g=\gamma$, and hence,
$\epsilon_{h}\leq\epsilon_{g},\forall h\in[\gamma]$. Therefore, the first term
in the sample complexity is,

$\displaystyle\sum_{h\in[\gamma]}\frac{n_{h}^{1+\frac{2}{p}}}{\epsilon_{h}^{2}}\geq\sum_{h\in[\gamma]}\frac{n_{h}\cdot
n_{g}^{\frac{2}{p}}}{\epsilon_{g}^{2}}=\frac{n\cdot
n_{g}^{\frac{2}{p}}}{\epsilon_{g}^{2}},$

which is the second term without the $\log\gamma$ factor. Therefore, our lower
bound is reasonable as it is tight up to $\log$ factors for many parameter
regimes.

##  5 Experimental Results

In this section, we present an empirical analysis of our algorithms. Section 4
gives us that Beat-the-Pivot has almost optimal sample complexity as an
$(\epsilon,\delta)$-PACF-Ranker. Hence, we use it as our group-blind baseline.
We use Algorithm 1 as the group-aware algorithm. We observe that group-aware
almost always has strictly lower sample complexity on both real-world and
synthetic datasets than group-blind.

We use the datasets where the true scores of the candidates are available and
use these scores to implement the Plackett-Luce sampling. For clarity, we kept
few experimental results here and moved some of the plots on the real-world
datasets, and all the plots on the synthetic datasets to Appendix C. The
experiments were run on an Intel(R) Xeon(R) Silver 4110 CPU (8 cores, 2.1 GHz,
and DRAM of 128GB).

Figure 2: Group-Aware Ranking on German Credit with Age defining two groups
age $<25$ (minority) and age $\geq 25$. Figure 3: Group-wise errors (for
$n=25,p=q=1$) for $g-0$ (majority group) and $g-1$, $g-2$ (minority groups).

##### Real-World Datasets.

(R1) COMPAS. It has been shown that the COMPAS tool disproportionately
predicts higher recidivism scores for African-American defendants compared to
others (Angwin et al., , 2016). This leads to lower representation of African-
Americans in the ranking based on $\neg$recidivism score in the top few ranks.
Since the size of the groups affects the accuracy of the ranking for the
groups, we use race as the protected attribute and run experiments for two
groups based on African-American or not (COMPAS-race). It is also observed
that the $\neg$recidivism score is biased based on gender. Therefore, we ran
experiments for two groups based on gender (COMPAS-gender).
(R2) German Credit. In this dataset taken from Dua and Graff,  (2017), German
adults are assigned a Schufa score indicating their creditworthiness, which
have been observed to be discriminative towards younger adults (those of age
$<25$) (Castillo, , 2019). Therefore, the resultant ranking based on these
scores is also expected to be biased towards young adults hence reducing their
representation in the top few ranks. We run experiments with (i) two groups
based on age split at $25$, (ii) two groups based on age split at $35$, and
(iii) three groups based on age split at $25$ and $35$. We call these datasets
German-age25, German-age35, and German-age, respectively. The exact
proportions of the items according to the true scores are shown in Table 1;
Appendix C.
Reading the plots. In Figure 2, a point in the plot $(x,y)$ denotes the
overall error $y$ of the ranking output by the algorithm after making $x$ many
oracle queries, where the error is as defined in Definition 1. In Figure 3, a
point in the plot $(x,y)$ represents the group-wise error $y$ for a particular
group, for the ranking output by the algorithm after making $x$ many oracle
queries, where the group-wise error is as defined in Equation 3. We show the
mean and one standard deviation of $20$ runs of each algorithm. The results
are shown for $\phi_{h}=1$ setting, however, we observe similar trends for
$\phi_{h}=n_{h}$ case (see Figures 11 and 12 in Appendix C.

Figure 4: Experiments on the real-world datasets for different values of $n$
(for $p=q=1$).

We list our key observations below:

##### 1) Sample Complexity with different values of $p$ and $q$.

Our experimental results clearly show that the group-aware algorithm has lower
sample complexity than the group-blind one, for both lower and higher values
of $p$ and $q$ as seen in Figure 2. Notably, with smaller values of $p$ and
$q$, the gap between the sample complexities for group-blind and group-aware
algorithms is significantly large compared to the higher values of $p$ and
$q$, because in the former case, say $p=q=1$, the error for each point gets
counted in the overall error whereas for higher values, only the top few
errors across the points within the group (top 1 as $p\rightarrow\infty$ case)
and top few group-wise errors (top 1 as $q\rightarrow\infty$ case) count.
Since in this case $\epsilon$-Best-Fair-Ranking is nothing but the
$\epsilon$-Best-Ranking (as shown in Definition 1), both group-blind and
group-aware algorithms have almost similar sample complexities.
2) Group-wise errors. We also plot for each group, $\ell_{p}$ norm of the
errors of the items in the groups appropriately normalized by the size of the
group (see Figure 3). We see a clear trend that for any group in any of these
datasets, the group-aware algorithm has almost the same or smaller sample
complexity than the group-blind one. Especially for minority groups, group-
aware achieves much less error with fewer samples. This is because for a fixed
number of queries, group-aware
surely samples some labels for items in the minority group while finding the
group-wise rankings. However, a group-blind algorithm may end up making very
few queries for items from the minority groups (especially if they are much
smaller in proportion in the dataset) and, hence, has a very high error.
3) Effect of $n$. The number of items we want to rank significantly changes
the dynamics of the algorithms since the number of groups, their proportions
and score distributions in the top $n$ ranking change significantly with $n$.
Figure 4 shows these variations on several real-world datasets. On all of
them, we observe that the group-aware has smaller sample complexity than
group-blind, with the gap more apparent for smaller values $p$ and $q$. This
is consistent with Observation 1.

##  6 Conclusion

We study the Probably Approximately Correct (PAC) version of the problem of
adaptively fair ranking $n$ items from pairwise comparisons in the Plackett-
Luce (PL) preference model. We propose a fair metric for measuring the quality
of rankings for different groups that generalizes ranking metrics that do not
consider group fairness requirements. We study the problem under two settings:
(i) where the ranking algorithm has access to group membership of items
(group-aware), and (ii) where the ranking algorithm does not have access to
group membership of items (group-blind). For the first setting, we show how
the algorithm of Saha and Gopalan,  (2019) can be adjusted to find a fair
ranking with optimal sample complexity, and we prove a matching lower bound on
the sample complexity up to some $\log$ factors. For the second setting, we
design an algorithm and prove its sample complexity. We also provide a
reasonable lower bound for a restricted class of algorithms.

The main open question is to close the gap between the lower and upper bounds
for both types of algorithms. It would also be interesting to study the
problem under alternative choice models, such as the multinomial probit,
Mallows, nested logit, generalized extreme-value models, etc.

## Acknowledgements

SG was supported by a Goolge PhD Fellowship.

## References

  * Abbasi et al., (2021) Abbasi, M., Bhaskara, A., and Venkatasubramanian, S. (2021).  Fair clustering via equitable group representations.  FAccT.
  * Ailon, (2012) Ailon, N. (2012).  An active learning algorithm for ranking from pairwise preferences with an almost optimal query complexity.  J. Mach. Learn. Res., 13:137–164.
  * Angwin et al., (2016) Angwin, J., Larson, J., Mattu, S., and Kirchner, L. (2016).  Machine bias.  Technical report, ProPublica.
  * Balcan and Long, (2013) Balcan, M.-F. and Long, P. (2013).  Active and passive learning of linear separators under log-concave distributions.  In Shalev-Shwartz, S. and Steinwart, I., editors, Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 288–316, Princeton, NJ, USA. PMLR.
  * Busa-Fekete and Hüllermeier, (2014) Busa-Fekete, R. and Hüllermeier, E. (2014).  A survey of preference-based online learning with bandit algorithms.  In Auer, P., Clark, A., Zeugmann, T., and Zilles, S., editors, Algorithmic Learning Theory, pages 18–39, Cham. Springer International Publishing.
  * Castillo, (2019) Castillo, C. (2019).  Fairness and transparency in ranking.  SIGIR Forum, 52(2):64–71.
  * Celis et al., (2020) Celis, L. E., Mehrotra, A., and Vishnoi, N. K. (2020).  Interventions for ranking in the presence of implicit bias.  In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, page 369–380. Association for Computing Machinery.
  * Celis et al., (2018) Celis, L. E., Straszak, D., and Vishnoi, N. K. (2018).  Ranking with fairness constraints.  In ICALP.
  * Chlamtac et al., (2022) Chlamtac, E., Makarychev, Y., and Vakilian, A. (2022).  Approximating Fair Clustering with Cascaded Norm Objectives, pages 2664–2683.
  * Dua and Graff, (2017) Dua, D. and Graff, C. (2017).  UCI machine learning repository.
  * Dwork et al., (2012) Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012).  Fairness through awareness.  In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 214–226, New York, NY, USA. Association for Computing Machinery.
  * Feige et al., (1994) Feige, U., Raghavan, P., Peleg, D., and Upfal, E. (1994).  Computing with noisy information.  SIAM Journal on Computing, 23(5):1001–1018.
  * Ghadiri et al., (2021) Ghadiri, M., Samadi, S., and Vempala, S. (2021).  Socially fair k-means clustering.  In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’21, page 438–448, New York, NY, USA. Association for Computing Machinery.
  * Gleich and Lim, (2011) Gleich, D. F. and Lim, L.-h. (2011).  Rank aggregation via nuclear norm minimization.  In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’11, page 60–68, New York, NY, USA. Association for Computing Machinery.
  * Gorantla et al., (2021) Gorantla, S., Deshpande, A., and Louis, A. (2021).  On the problem of underranking in group-fair ranking.  In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3777–3787. PMLR.
  * Gorantla et al., (2023) Gorantla, S., Gowda, K. N., Deshpande, A., and Louis, A. (2023).  Socially fair center-based and linear subspace clustering.  In Koutra, D., Plant, C., Gomez Rodriguez, M., Baralis, E., and Bonchi, F., editors, Machine Learning and Knowledge Discovery in Databases: Research Track, pages 727–742, Cham. Springer Nature Switzerland.
  * Hardt et al., (2016) Hardt, M., Price, E., Price, E., and Srebro, N. (2016).  Equality of opportunity in supervised learning.  In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc.
  * Jamieson and Nowak, (2011) Jamieson, K. G. and Nowak, R. D. (2011).  Active ranking using pairwise comparisons.  In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS’11, page 2240–2248, Red Hook, NY, USA. Curran Associates Inc.
  * Kalyanakrishnan et al., (2012) Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. (2012).  Pac subset selection in stochastic multi-armed bandits.  Proceedings of the 29th International Conference on Machine Learning, ICML 2012, 1.
  * Kaufmann et al., (2014) Kaufmann, E., Cappé, O., and Garivier, A. (2014).  On the complexity of best-arm identification in multi-armed bandit models.  J. Mach. Learn. Res., 17:1:1–1:42.
  * Khetan and Oh, (2016) Khetan, A. and Oh, S. (2016).  Data-driven rank breaking for efficient rank aggregation.  In Balcan, M. F. and Weinberger, K. Q., editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 89–98, New York, New York, USA. PMLR.
  * Kleinberg and Raghavan, (2018) Kleinberg, J. and Raghavan, M. (2018).  Selection Problems in the Presence of Implicit Bias.  In Karlin, A. R., editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:17, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * Mehrotra and Vishnoi, (2022) Mehrotra, A. and Vishnoi, N. (2022).  Fair ranking with noisy protected attributes.  In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems, volume 35, pages 31711–31725. Curran Associates, Inc.
  * Pitoura et al., (2022) Pitoura, E., Stefanidis, K., and Koutrika, G. (2022).  Fairness in rankings and recommendations: an overview.  The VLDB Journal, pages 1–28.
  * Popescu et al., (2016) Popescu, P., Dragomir, S. S., Slusanschi, E., and Stanasila, O. (2016).  Bounds for kullback-leibler divergence.  Electronic Journal of Differential Equations, 2016.
  * Rajkumar and Agarwal, (2016) Rajkumar, A. and Agarwal, S. (2016).  When can we rank well from comparisons of $o(n\log(n))$ non-actively chosen pairs?  In Feldman, V., Rakhlin, A., and Shamir, O., editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1376–1401, Columbia University, New York, New York, USA. PMLR.
  * Ren et al., (2021) Ren, W., Liu, J., and Shroff, N. (2021).  Sample complexity bounds for active ranking from multi-wise comparisons.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 4290–4300. Curran Associates, Inc.
  * Saha and Gopalan, (2019) Saha, A. and Gopalan, A. (2019).  Active ranking with subset-wise preferences.  In Chaudhuri, K. and Sugiyama, M., editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 3312–3321. PMLR.
  * Singh and Joachims, (2018) Singh, A. and Joachims, T. (2018).  Fairness of exposure in rankings.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 2219–2228.
  * Singh et al., (2021) Singh, A., Kempe, D., and Joachims, T. (2021).  Fairness in ranking under uncertainty.  In NeurIPS 2021, December 6-14, 2021, pages 11896–11908.
  * Zehlike et al., (2017) Zehlike, M., Bonchi, F., Castillo, C., Hajian, S., Megahed, M., and Baeza-Yates, R. (2017).  Fa*ir: A fair top-k ranking algorithm.  In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM ’17, page 1569–1578, New York, NY, USA. Association for Computing Machinery.
  * (32) Zehlike, M., Yang, K., and Stoyanovich, J. (2022a).  Fairness in ranking, part i: Score-based ranking.  ACM Computing Surveys, 55(6):1–36.
  * (33) Zehlike, M., Yang, K., and Stoyanovich, J. (2022b).  Fairness in ranking, part ii: Learning-to-rank and recommender systems.  ACM Computing Surveys, 55(6):1–41.

##  Appendix A Missing Proof from Section 3

###### Proof.

Let $d^{(h)}(\sigma;\theta):=\max_{i\in G_{h}}d_{i}(\sigma;\theta)$. When
$p\rightarrow\infty$ we have that

$\displaystyle\lim_{p\rightarrow\infty}\text{err}_{h}(\sigma;\theta)$
$\displaystyle=\lim_{p\rightarrow\infty}\left(\sum_{i\in
G_{h}}d_{i}(\sigma;\theta)^{p}\right)^{1/p}$
$\displaystyle=\lim_{p\rightarrow\infty}d^{(h)}(\sigma;\theta)\left(\sum_{i\in
G_{h}}\left(\frac{d_{i}(\sigma;\theta)}{d^{(h)}(\sigma;\theta)}\right)^{p}\right)^{1/p}$
$\displaystyle=d^{(h)}(\sigma;\theta)\lim_{p\rightarrow\infty}\left(\sum_{i\in
G_{h}}\left(\frac{d_{i}(\sigma;\theta)}{d^{(h)}(\sigma;\theta)}\right)^{p}\right)^{1/p}.$

Notice that for $\frac{d_{i}(\sigma;\theta)}{d^{(h)}(\sigma;\theta)}\leq
1,\forall i\in G_{h}$, the equality occurs at least once for one point and at
most for all the points in $G_{h}$. Since $p>0$ and $d_{i}(\sigma;\theta)\geq
0,\forall i\in G_{h}$, we have that

$\displaystyle 1\leq\sum_{i\in
G_{h}}\left(\frac{d_{i}(\sigma;\theta)}{d^{(h)}(\sigma;\theta)}\right)^{p}\leq
n_{h}.$

Therefore,

$\displaystyle\lim_{p\rightarrow\infty}1^{1/p}$
$\displaystyle\leq\lim_{p\rightarrow\infty}\left(\sum_{i\in
G_{h}}\left(\frac{d_{i}(\sigma;\theta)}{d^{(h)}(\sigma;\theta)}\right)^{p}\right)^{1/p}\leq\lim_{p\rightarrow\infty}n_{h}^{1/p}.$

But $\lim_{p\rightarrow\infty}1^{1/p}=1$ and
$\lim_{p\rightarrow\infty}n_{h}^{1/p}=1$, which gives us that,

$\displaystyle\lim_{p\rightarrow\infty}\left(\sum_{i\in
G_{h}}\left(\frac{d_{i}(\sigma;\theta)}{d^{(h)}(\sigma;\theta)}\right)^{p}\right)^{1/p}=1.$

Therefore,

$\displaystyle\lim_{p\rightarrow\infty}\text{err}_{h}(\sigma;\theta)$
$\displaystyle=d^{(h)}(\sigma;\theta)=\max_{i\in
G_{h}}\left(\max_{\begin{subarray}{c}j\in[n]~{}\text{s.t.}\\\
\theta_{i}>\theta_{j}\land\sigma(i)>\sigma(j)\end{subarray}}\theta_{i}-\theta_{j}\right).$
(4)

Let
$\text{err}_{h^{*}}(\sigma;\theta):=\max_{h\in[\gamma]}\text{err}_{h}(\sigma;\theta)$.
When $q\rightarrow\infty$ we have that

$\displaystyle\lim_{q\rightarrow\infty}\text{err}^{\texttt{fair}}(\sigma;\theta)$
$\displaystyle=\lim_{q\rightarrow\infty}\left(\sum_{h\in[\gamma]}w(h)\cdot\text{err}_{h}(\sigma;\theta)^{q}\right)^{1/q}$
$\displaystyle=\lim_{q\rightarrow\infty}\text{err}_{h}(\sigma;\theta)\left(\sum_{h\in[\gamma]}w(h)\cdot\left(\frac{\text{err}_{h}(\sigma;\theta)}{\text{err}_{h^{*}}(\sigma;\theta)}\right)^{q}\right)^{1/q}$
$\displaystyle=\text{err}_{h}(\sigma;\theta)\lim_{q\rightarrow\infty}\left(\sum_{h\in[\gamma]}w(h)\cdot\left(\frac{\text{err}_{h}(\sigma;\theta)}{\text{err}_{h^{*}}(\sigma;\theta)}\right)^{q}\right)^{1/q}.$

Notice that for
$\frac{\text{err}_{h}(\sigma;\theta)}{\text{err}_{h^{*}}(\sigma;\theta)}\leq
1,\forall h\in[\gamma]$, the equality occurs at least once for one group and
at most for all the groups. Since $q>0$, $w(\cdot)\geq 0$, and
$\text{err}_{h}(\sigma;\theta)\geq 0,\forall h\in[\gamma]$, we have that

$\displaystyle\min_{h\in[\gamma]}w(h)\leq\sum_{h\in[\gamma]}w(h)\cdot\left(\frac{\text{err}_{h}(\sigma;\theta)}{\text{err}_{h^{*}}(\sigma;\theta)}\right)^{q}\leq\sum_{h\in[\gamma]}w(h).$

Therefore,

$\displaystyle\lim_{q\rightarrow\infty}\left(\min_{h\in[\gamma]}w(h)\right)^{1/q}$
$\displaystyle\leq\lim_{q\rightarrow\infty}\left(\sum_{h\in[\gamma]}w(h)\cdot\left(\frac{\text{err}_{h}(\sigma;\theta)}{\text{err}_{h^{*}}(\sigma;\theta)}\right)^{q}\right)^{1/q}\leq\lim_{q\rightarrow\infty}\left(\sum_{h\in[\gamma]}w(h)\right)^{1/q}.$

But $\lim_{q\rightarrow\infty}\left(\min_{h\in[\gamma]}w(h)\right)^{1/q}=1$
and $\lim_{q\rightarrow\infty}\left(\sum_{h\in[\gamma]}w(h)\right)^{1/q}=1$,
which gives us that,

$\displaystyle\lim_{q\rightarrow\infty}\left(\sum_{h\in[\gamma]}w(h)\cdot\left(\frac{\text{err}_{h}(\sigma;\theta)}{\text{err}_{h^{*}}(\sigma;\theta)}\right)^{q}\right)^{1/q}=1.$

Therefore,

$\displaystyle\lim_{q\rightarrow\infty}\text{err}^{\texttt{fair}}(\sigma;\theta)$
$\displaystyle=\max_{h\in[\gamma]}\text{err}_{h}(\sigma;\theta)=\max_{h\in[\gamma]}\max_{i\in
G_{h}}\left(\max_{\begin{subarray}{c}j\in[n]~{}\text{s.t.}\\\
\theta_{i}>\theta_{j}\land\sigma(i)>\sigma(j)\end{subarray}}\theta_{i}-\theta_{j}\right).$
(5)

Therefore, an $(\epsilon,\infty,\infty)$-Best-Ranking is the one that
satisfies

$\displaystyle\max_{h\in[\gamma]}\quad$ $\displaystyle\max_{i\in
G_{h}}\quad\left(\max_{\begin{subarray}{c}j\in[n]~{}\text{s.t.}\\\
\theta_{i}>\theta_{j}\land\sigma(i)>\sigma(j)\end{subarray}}\theta_{i}-\theta_{j}\right)$
$\displaystyle<\epsilon$ $\displaystyle\implies$
$\displaystyle\max_{i\in[n]}\quad\left(\max_{\begin{subarray}{c}j\in[n]~{}\text{s.t.}\\\
\theta_{i}>\theta_{j}\land\sigma(i)>\sigma(j)\end{subarray}}\theta_{i}-\theta_{j}\right)$
$\displaystyle<\epsilon.$ (6)

Therefore, an $(\epsilon,\infty,\infty)$-Best-Ranking is any ranking that
satisfies Equation 6. Let $\sigma\in\Sigma_{[n]}$ be a ranking satisfying
Equation 6. Let $i,j\in[n]$ be a pair of distinct items such that
$\theta_{i}\geq\theta_{j}+\epsilon$. Then, $\sigma(i)<\sigma(j)$. Therefore,
$\not\exists i,j\in[n]$ such that $\sigma(i)>\sigma(j)$ and
$\theta_{i}\geq\theta_{j}+\epsilon$. Therefore, $\sigma$ is also an
$\epsilon$-Best-Ranking according to Equation 1.

Now let $\sigma\in\Sigma_{[n]}$ be an $\epsilon$-Best-Ranking according to
Equation 1. Fix any $i\in[n]$. Then for any $j\in[n]$ such that
$\sigma(i)>\sigma(j)$, $\theta_{i}<\theta_{j}+\epsilon$. Therefore, for the
item $i$,

$\max_{\begin{subarray}{c}j\in[n]~{}\text{s.t.}\\\
\theta_{i}>\theta_{j}\land\sigma(i)>\sigma(j)\end{subarray}}\theta_{i}-\theta_{j}<\epsilon.$

Therefore, $\sigma$ is also an $(\epsilon,\infty,\infty)$-Best-Ranking. ∎

##  Appendix B Missing Proof from Section 4

###  B.1 Additional notation

We use $\mathbb{I}\\{{\mathcal{E}}\\}$ to denote the indicator function of the
event ${\mathcal{E}}$. For any $a,b\in[0,1]$, $Ber(a)$ and $Geo(a)$ represent
the Bernoulli and the Geometric distributions respectively, and $kl(a,b)$
represents the Kullback Leibler divergence between $Ber(a)$ and $Ber(b)$.

######  Definition 3 (Symmetric Algorithm).

A group-blind PAC algorithm ${\mathcal{A}}$ is said to be symmetric if its
output is insensitive to the specific labeling of items, i.e., if for any PL
model $(\theta_{1},\ldots,\theta_{n})$, with group memberships
$(g_{1},\ldots,g_{n})$, bijection $\phi:[n]\rightarrow[n]$ and ranking
$\boldsymbol{\sigma}:[n]\rightarrow[n]$, it holds that

$Pr({\mathcal{A}}\text{ outputs
}\boldsymbol{\sigma}\mid(\theta_{1},\ldots,\theta_{n}),(g_{1},g_{2},\ldots,g_{n}))\\\
=Pr({\mathcal{A}}\text{ outputs
}\boldsymbol{\sigma}\circ\phi\mid((\theta_{\phi^{-1}(1)},\ldots,\theta_{\phi^{-1}(n)}),(g_{\phi^{-1}(1)},\ldots,g_{\phi^{-1}(n)})),$
(7)

where $Pr(\cdot\mid(\alpha_{1},\ldots,\alpha_{n}))$ denotes the probability
distribution on the trajectory of ${\mathcal{A}}$ induced by the PL model
$(\alpha_{1},\ldots,\alpha_{n})$.

###  B.2 Sample Complexity Bounds for group-blind Algorithms

####  B.2.1 Upper bound

Below we give our group-blind algorithm that outputs an $\epsilon$-Best-Fair-
Ranking with optimal query complexity.

Algorithm 2 Group-blind algorithm for single group

Run Beat-the-Pivot with error parameter
${\tilde{\epsilon}}=\frac{\epsilon}{n^{\max\left\\{\frac{1}{p},\frac{1}{q}\right\\}}}$
and confidence parameter $\delta$.

######  Lemma 4.

Algorithm 2 is an $(\epsilon,\delta)$-PACF-Ranker with sample complexity
${\mathcal{O}}\left(\frac{n^{1+\max\left\\{\frac{2}{p},\frac{2}{q}\right\\}}}{\epsilon^{2}}\log\frac{n}{\delta}\right)$.

###### Proof.

Let $\boldsymbol{\sigma}$ be the ranking returned by Algorithm 2. From Theorem
8 in Saha and Gopalan,  (2019) we know that $\boldsymbol{\sigma}$ is an
${\tilde{\epsilon}}$-Best-Ranking with probability at least $1-\delta$. Using
this, correctness of Algorithm 2 can be shown as follows,

$\displaystyle\text{err}^{\texttt{fair}}(\boldsymbol{\sigma};\theta)$
$\displaystyle=\left(\sum_{h\in[\gamma]}\frac{\phi_{h}}{|G_{h}|}\text{err}_{h,p}{(\boldsymbol{\sigma};\theta)^{q}}\right)^{1/q}=\left(\sum_{h\in[\gamma]}\frac{\phi_{h}}{|G_{h}|}\left(\sum_{i\in
G_{h}}{\tilde{\epsilon}}^{p}\right)^{q/p}\right)^{1/q}$
$\displaystyle=\left(\sum_{h\in[\gamma]}\frac{\phi_{h}}{|G_{h}|}\left(|G_{h}|^{q/p}{\tilde{\epsilon}}^{q}\right)\right)^{1/q}={\tilde{\epsilon}}\left(\sum_{h\in[\gamma]}\frac{\phi_{h}}{|G_{h}|^{1-q/p}}\right)^{1/q}$
$\displaystyle\leq{\tilde{\epsilon}}\left(\sum_{h\in[\gamma]}|G_{h}|^{q/p}\right)^{1/q}$
$\displaystyle\because\phi_{h}\leq|G_{h}|$
$\displaystyle=\frac{\epsilon}{n^{\max\\{1/q,1/p\\}}}\left(\sum_{h\in[\gamma]}|G_{h}|^{q/p}\right)^{1/q}.$
(8)

When $q\leq p$, we have that $1/q\geq 1/p$ and $|G_{h}|^{q/p}\leq|G_{h}|$.
Therefore,

$\displaystyle\text{err}^{\texttt{fair}}(\boldsymbol{\sigma};\theta)$
$\displaystyle\leq\frac{\epsilon}{n^{1/q}}\left(\sum_{h\in[\gamma]}|G_{h}|\right)^{1/q}\leq\frac{\epsilon}{n^{1/q}}\cdot
n^{1/q}=\epsilon.$ (9)

When $q>p$, we have that $1/q<1/p$. We need to upper bound the term in the
summation in Equation 8. Since the number of groups can be between $1$ and
$n$, and the total number of items needs to be exactly $n$, we can write the
following optimization problem where $x_{h}$ represents the number of items
from group $h$,

$\displaystyle\max_{x\in{\mathbb{R}}^{n}}~{}~{}~{}$
$\displaystyle\left(\sum_{h\in[n]}x_{h}^{q/p}\right)^{1/q}$ (10) such that
$\displaystyle\sum_{h\in[n]}x_{h}=n$ (11) and $\displaystyle
x_{h}\in\\{0,1,2,\ldots,n\\},~{}~{}\forall h\in[n].$ (12)

Consider the following relaxation of the program above,

$\displaystyle\max_{x\in{\mathbb{R}}^{n}}~{}~{}~{}$
$\displaystyle\left(\sum_{h\in[n]}x_{h}^{q/p}\right)^{1/q}$ (13) such that
$\displaystyle\sum_{h\in[n]}x_{h}=n$ (14) and $\displaystyle 0\leq x_{h}\leq
n,~{}~{}\forall h\in[n].$ (15)

It is easy to see that the all ones vector, $\mathbbm{1}$, is the minimizer of
$\sum_{i\in[n]}x_{i}^{q/p}$ inside the convex polytope formed by the
constraints (14) and (15). Therefore, the maximum value of this convex
function is achieved at a vertex of the convex polytope. Since the polytope
lives in an $n$ dimensional space, any vertex is formed by at least $n$
equality constraints, one of which has to be (14). Amongst the constraints in
(15), at least $n-1$ coordinates of $x$ have to be $0$, and exactly one has to
be $n$. There is no other way to satisfy at least $n$ constraints with
equality. Moreover, $(\cdot)^{1/q}$ is a non-decreasing function. Hence, the
maximum of the objective function in Equation 13 also occurs at a vertex of
the convex polytope. Note that this is also a feasible point for the program
defined by Equations 10, 11 and 12. Therefore, the maximum value of the
objective function is $n^{1/p}$, which gives us that,

$\displaystyle\text{err}^{\texttt{fair}}(\boldsymbol{\sigma};\theta)$
$\displaystyle\leq\frac{\epsilon}{n^{1/p}}\cdot n^{1/p}=\epsilon.$ (16)

From Equations 9 and 16 we can conclude that Algorithm 2 returns an
$\epsilon$-Best-Fair-Ranking with probability at least $1-\delta$.

From Theorem 8 in Saha and Gopalan,  (2019), we know that Beat-the-Pivot with
error parameter $\epsilon$ and confidence parameter $\delta$ has sample
complexity
${\mathcal{O}}\left(\frac{n}{\epsilon^{2}}\log\frac{n}{\delta}\right)$.
Therefore, the sample complexity of Algorithm 2 is
${\mathcal{O}}\left(\frac{n}{{\tilde{\epsilon}}^{2}}\log\frac{n}{\delta}\right)={\mathcal{O}}\left(\frac{n^{1+\max\left\\{\frac{2}{q},\frac{2}{p}\right\\}}}{\epsilon^{2}}\log\frac{n}{\delta}\right)$.

∎

####  B.2.2 Lower bound

######  Lemma 5 (Lower bound on Sample Complexity).

Given an error parameter $\epsilon\in(0,1)$, a confidence parameter
$\delta\in(0,1)$, and a symmetric $(\epsilon,\delta)$-PAC-Ranker algorithm
${\mathcal{A}}$ for WI feedback, there exists a PL instance $\nu$ such that
the sample complexity of ${\mathcal{A}}$ on $\nu$ is at least
$\Omega\bigg{(}\frac{n^{1+\max\left\\{\frac{2}{p},\frac{2}{q}\right\\}}}{\epsilon^{2}}\bigg{)}.$

Similarly to (Saha and Gopalan, , 2019), we construct a hard class of
instances and use the Lemma on multi-armed bandits given by Kaufmann et al.,
(2014) that gives a change-of-measure argument to lower bound the sample
complexity. We restate the lemma below,

######  Lemma 6 (Lemma $1$, Kaufmann et al.,  (2014)).

Let $\eta$ and $\eta^{\prime}$ be two bandit models for $N$ arms (assignments
of reward distributions to arms), such that
$\eta_{i}~{}(\text{resp.}\,\eta^{\prime}_{i})$ is the reward distribution of
any arm $i\in[N]$ under the bandit model
$\eta~{}(\text{resp.}\,\eta^{\prime})$, and such that for all such arms $i$,
$\eta_{i}$ and $\eta^{\prime}_{i}$ are mutually absolutely continuous. Then
for any almost-surely finite stopping time $\tau$ with respect to
$({\mathcal{F}}_{t})_{t}$,

$\displaystyle\sum_{i=1}^{N}{\mathbf{E}}_{\eta}[N_{i}(\tau)]KL(\eta_{i},\eta_{i}^{\prime})\geq\sup_{{\mathcal{E}}\in{\mathcal{F}}_{\tau}}kl(Pr_{\eta}({\mathcal{E}}),Pr_{\eta^{\prime}}({\mathcal{E}})),$

where $kl(x,y):=x\log(\frac{x}{y})+(1-x)\log(\frac{1-x}{1-y})$ is the binary
relative entropy, $N_{i}(\tau)$ denotes the number of times arm $i$ is played
in $\tau$ rounds, and $Pr_{\eta}({\mathcal{E}})$ and
$Pr_{\eta^{\prime}}({\mathcal{E}})$ denote the probability of any event
${\mathcal{E}}\in{\mathcal{F}}_{\tau}$ under bandit models $\eta$ and
$\eta^{\prime}$, respectively.

###### Proof of Lemma 5.

Let us assume that the items belong to exactly one group. This result will be
useful in proving sample complexity for multiple-group case. Note that when
there is only one group, both group-blind and group-aware algorithms should
incur the same minimum sample complexity to learn a ranking. Also, the
parameter $q$ and the weight function do not matter. For simplicity, let us
assume that $n$ is a multiple of $4$.

##### Class of instances.

Let ${\tilde{\epsilon}}=\epsilon\cdot\left(\frac{4}{n}\right)^{1/p}$. Let
$n^{\prime}:=3n/4$. Let $T:=\\{n^{\prime}+1,n^{\prime}+2,\ldots,n\\}$. Now
consider the class of instances ${\boldsymbol{\nu}}_{[m]}$ for any
$m\in[n^{\prime}]$, where for any $S\subseteq[n^{\prime}]$ such that $|S|=m$,
$\nu_{S}$ represents the instance where

$\forall i\in
S,~{}~{}\theta_{i}=\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2},\quad\forall
i\in
T,~{}~{}\theta_{i}=\theta\left(\frac{1}{4}-{\tilde{\epsilon}}^{2}\right),\quad\text{and}\quad\forall
i\not\in S\cup
T,~{}~{}\theta_{i}=\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}.$

######  Remark.

Note that $S$ uniquely represents an instance
$\nu_{S}\in{\boldsymbol{\nu}}_{[m]}$ for any fixed $m\in[n^{\prime}]$.

######  Lemma 7.

For any $\theta>\frac{1}{1-2{\tilde{\epsilon}}}$ and for any problem instance
$\nu_{S}\in{\boldsymbol{\nu}}_{[n/4]}$, any $\epsilon$-Best-Fair-Ranking, say
$\boldsymbol{\sigma}_{S}$, has to satisfy the following: the number of items
from $S\cup T$ in ranks $\frac{n}{4}+2$ to $n$ should be strictly less than
$\frac{n}{4}$.

###### Proof.

Note that when $\theta>\frac{1}{1-2{\tilde{\epsilon}}}$, for any $i\in
S,i^{\prime}\in T$ and $i^{\prime\prime}\notin S\cup T$,

$\theta_{i}-\theta_{i^{\prime}}>{\tilde{\epsilon}},~{}~{}\theta_{i^{\prime}}-\theta_{i^{\prime\prime}}>{\tilde{\epsilon}},~{}~{}\text{and}~{}~{}\theta_{i}-\theta_{i^{\prime\prime}}>{\tilde{\epsilon}}.$

Let us assume that there exists an $\epsilon$-Best-Fair-Ranking for $\nu_{S}$,
say $\boldsymbol{\sigma}_{S}$, such that the ranks $\frac{n}{4}+2$ to $n$ have
$\geq\frac{n}{4}$ items from $S\cup T$. Then, $\leq\frac{n}{4}$ items from
$S\cup T$ are in the ranks $1$ to $\frac{n}{4}+1$, since $|S\cup
T|=\frac{n}{2}$. So there will be at least one item from
$[n^{\prime}]{\setminus}S$ in ranks $1$ to $\frac{n}{4}+1$, which implies that
at least $\frac{n}{4}$ items in $S\cup T$ incur an error
$>{\tilde{\epsilon}}$. Therefore, the overall error will be,

$\displaystyle\text{err}^{\texttt{fair}}(\boldsymbol{\sigma}_{S};\theta_{S})$
$\displaystyle=\left(\sum_{i\in[n]}d_{i}(\boldsymbol{\sigma}_{S};\theta_{S})^{p}\right)^{1/p}>\left(\frac{n}{4}\cdot{\tilde{\epsilon}}^{p}\right)^{1/p}=\left(\frac{n}{4}\cdot\left(\epsilon\cdot\left(\frac{4}{n}\right)^{1/p}\right)^{p}\right)^{1/p}$
$\displaystyle=\left(\epsilon^{p}\right)^{1/p}=\epsilon,$

which contradicts our assumption that $\boldsymbol{\sigma}_{S}$ is an
$\epsilon$-Best-Fair-Ranking. ∎

##### The alternative instances.

We now fix any set $S^{*}\subset[n^{\prime}]$ such that $|S^{*}|=\frac{n}{4}$.
Lower bound on the sample complexity is now obtained by applying Lemma 6 on a
pair of instances $(\nu_{S^{*}},\nu_{{\tilde{S}}^{*}})$, for all possible
choices of ${\tilde{S}}^{*}={S^{*}}\cup S^{\prime}$, where
$S^{\prime}\subset[n^{\prime}]{\setminus}{S^{*}}$ and
$|S^{\prime}|=\frac{n}{4}$. Note that there will be $n/2\choose n/4$ choices
of ${\tilde{S}}^{*}$.

##### Describing the event.

For any ranking $\boldsymbol{\sigma}\in\Sigma_{n}$, we denote by
$\boldsymbol{\sigma}(r:r^{\prime})$ the set of items in the ranking,
$\boldsymbol{\sigma}$, from rank $r$ to rank $r^{\prime}$, for any $1\leq
r\leq r^{\prime}\leq n$. Consider the event ${\mathcal{E}}$ for an instance
$S$ that the algorithm ${\mathcal{A}}$ outputs a ranking such that the number
of items from $S\cup T$ in the ranks $n/4+2$ to $n$ is $<n/4$. That is,

${\mathcal{E}}(S):=\left\\{\left|(S\cup
T)\cap\boldsymbol{\sigma}_{{\mathcal{A}}}\left(\frac{n}{4}+2:n\right)\right|<\frac{n}{4}\right\\}.$

This is a high probability event for $S^{*}$ because otherwise, the error will
be more than $\epsilon$, from Lemma 7. On the contrary, for the alternative
instances with ${\tilde{S}}^{*}$, this is a low probability event because all
the items from $T$ have to appear in the ranks $n/4+2$ to $n$ or otherwise,
$\geq n/4$ items from ${\tilde{S}}^{*}\cup T$ will be in ranks $n/4+2$ to $n$
and they all incur an error $>{\tilde{\epsilon}}$ due to an item from $T$ in
the ranks $1$ to $n/4+1$; therefore the total error will be more than
$\epsilon$.

It is easy to note that as ${\mathcal{A}}$ is an $(\epsilon,\delta)$-PAC-
Ranker , obviously

$Pr_{S^{*}}({\mathcal{E}}({S^{*}}))>Pr_{S^{*}}(\boldsymbol{\sigma}_{{\mathcal{A}}}\text{
is an {\bf$\epsilon$-Best-Ranking}})>1-\delta,$ (17)

and

$Pr_{{\tilde{S}}^{*}}({\mathcal{E}}({S^{*}}))<\delta,$ (18)

for any alternative instance ${\tilde{S}}^{*}$.

We can further tighten Equation 18 using _symmetric property_ of
${\mathcal{A}}$ as follows,

######  Lemma 8.

For any symmetric $(\epsilon,\delta)$-PAC-Ranker , ${\mathcal{A}}$, and any
problem instance $\nu_{S}\in{\boldsymbol{\nu}}_{[n^{\prime}]}$ such that
$|S|=\frac{n}{2}$,
$Pr_{S}\left({\mathcal{E}}(S)\right)<\frac{\delta}{{n/2\choose n/4}},$ where
$Pr_{S}(\cdot)$ denotes the probability of an event under the underlying
problem instance $\nu_{S}$ and the internal randomness of the algorithm
${\mathcal{A}}$ (if any).

###### Proof.

Let us first fix an $m=n/2$ and $m^{\prime}=n/4$. Consider a problem instance
$\nu_{S}\in{\boldsymbol{\nu}}_{[m]}$. Recall from Remark Remark that we use
the notation $S\in{\boldsymbol{\nu}}_{[m]}$ to denote a problem instance in
${\boldsymbol{\nu}}_{[m]}$. Then the probability of making an error over all
possible choices of $S\in{\boldsymbol{\nu}}_{[m]}$:

$\sum_{S\in{\boldsymbol{\nu}}_{[m]}}Pr_{S}\Big{(}{\mathcal{A}}~{}\text{makes
an error $>\epsilon$ on
}S\Big{)}\geq\sum_{S_{1}\in{\boldsymbol{\nu}}_{[m^{\prime}]}}\sum_{\begin{subarray}{c}S_{2}\in[n^{\prime}]{\setminus}S\\\
\text{s.t.}|S_{2}|=\frac{n}{4}\end{subarray}}Pr_{S_{1}\cup
S_{2}}\Big{(}{\mathcal{E}}(S_{1}))\Big{)}$ (19)

where the above analysis follows from a similar result proved by
Kalyanakrishnan et al.,  (2012) to derive sample complexity lower bound for
classical multi-armed bandit setting towards recovering top-$q$ items (see
Theorem $8$, Kalyanakrishnan et al.,  (2012)).

Clearly the possible number of instances in ${\boldsymbol{\nu}}_{[m]}$, i.e.
$|{\boldsymbol{\nu}}_{[m]}|={{n^{\prime}}\choose{m}}$, as any set
$S\subset[n^{\prime}]$ of size $m$ can be chosen from $[n^{\prime}]$ in
${{n^{\prime}}\choose{m}}$ ways.

Now from _symmetry_ of algorithm ${\mathcal{A}}$ and by construction of the
class of our problem instances ${\boldsymbol{\nu}}_{[m]}$, for any two
instances $S_{1}$ and $\hat{S}_{1}$ in ${\boldsymbol{\nu}}_{[m^{\prime}]}$,
and for any choices of $S_{2}\in[n^{\prime}]\setminus S^{\prime}_{1}$ and
$\hat{S}_{2}\in[n^{\prime}]\setminus S^{\prime}_{2}$ such that
$|\hat{S}_{1}|=|\hat{S}_{2}|=n/4$ we have that:

$Pr_{S_{1}\cup
S_{2}}\Big{(}{\mathcal{E}}(S_{1})\Big{)}=Pr_{\hat{S}_{1}\cup\hat{S}_{2}}\Big{(}{\mathcal{E}}(\hat{S}_{1})\Big{)}.$

Then the above equivalently implies that for all
$S_{1}\in{\boldsymbol{\nu}}_{[m^{\prime}]}$ and any
$S_{2}\in[n^{\prime}]\setminus S$ such that $|S_{2}|=\frac{n}{4}$, $\exists
p\in[0,1]$

$Pr_{S_{1}\cup S_{2}}({\mathcal{E}}(S_{1}))=p.$

Then using above in Equation 19 we can further derive,

$\displaystyle\sum_{S\in{\boldsymbol{\nu}}_{[m]}}Pr_{S}\Big{(}{\mathcal{A}}~{}\text{makes
an error $>\epsilon$ on }S\Big{)}$
$\displaystyle\geq\sum_{S_{1}\in{\boldsymbol{\nu}}_{[m^{\prime}]}}\sum_{S_{2}\in[n^{\prime}]{\setminus}S_{1}:|S_{2}|=n/4}Pr_{S_{1}\cup
S_{2}}\Big{(}{\mathcal{E}}(S_{1}))\Big{)}$ $\displaystyle={n^{\prime}\choose
m^{\prime}}{n^{\prime}-m^{\prime}\choose n/4}p$ $\displaystyle={3n/4\choose
n/4}{n/2\choose n/4}p.$

On the L.H.S. there are ${3n/4\choose n/2}={3n/4\choose n/4}$ choices of $S$.
Therefore, if $p>\frac{\delta}{{n/2\choose n/4}}$, we get that,

$\displaystyle\sum_{S\in{\boldsymbol{\nu}}_{[m]}}Pr_{S}\Big{(}{\mathcal{A}}~{}\text{makes
an error $>\epsilon$ on }S\Big{)}$
$\displaystyle>{\frac{3n}{4}\choose\frac{n}{4}}\delta.$

which in turn implies that there exists at least one instance
$\nu_{S}\in{\boldsymbol{\nu}}_{[m]}$ such that
$Pr_{S}\Big{(}{\mathcal{A}}~{}\text{makes an error $>\epsilon$ on
}S\Big{)}\geq\delta$, which violates the $(\epsilon,\delta)$-PAC-Ranker
property of algorithm ${\mathcal{A}}$. Thus it has to be the case that
$p<\frac{\delta}{{n/2\choose n/4}}$, which concludes the proof. ∎

Owing to Lemma 8 we get,

$Pr_{{\tilde{S}}^{*}}\Big{(}{\mathcal{E}}({S^{*}})\Big{)}<\frac{\delta}{{n/2\choose
n/4}}.$ (20)

We will crucially use Equation 17 and Equation 20 in the following lemma.

######  Lemma 9 (Lemma 26, Saha and Gopalan,  (2019)).

For any $\delta\in(0,1)$, and $\alpha\in{\mathbb{R}}_{+}$,
$kl\bigg{(}1-\delta,\dfrac{\delta}{\alpha}\bigg{)}>\ln\dfrac{\alpha}{4\delta}.$

This lemma leads to the desired tighter upper bound for
$kl(Pr_{\nu_{{S^{*}}}}({\mathcal{E}}),Pr_{\nu_{{\tilde{S}}^{*}}}({\mathcal{E}}))\geq
kl(1-\delta,\frac{\delta}{{n/2\choose n/4}})\geq\ln\frac{{n/2\choose
n/4}}{4\delta}$.

Note that for the problem instance $\nu_{S^{*}}\in{\boldsymbol{\nu}}_{[m]}$,
the probability distribution associated with a particular arm
$B\in{\mathcal{B}}$ – a pair of items – is given by:

$\nu^{B}_{S^{*}}\sim Categorical(p_{1},p_{2}),\text{ where
}p_{i}=Pr(i|B),~{}~{}\forall i\in[2],\,\forall B\in{\mathcal{B}},$

where $Pr(i|B)$ is the probability of item $i$ winning in the Plackett-Luce
model for the items in set $B$. Now applying Lemma 6, for some event
${\mathcal{E}}\in{\mathcal{F}}_{\tau}$ we get,

$\displaystyle\sum_{\\{B\in{\mathcal{B}}\\}}{\mathbf{E}}_{\nu^{B}_{S^{*}}}[N_{B}(\tau_{{\mathcal{A}}})]KL(\nu^{B}_{S^{*}},\nu^{B}_{{\tilde{S}}^{*}})\geq
kl(Pr_{\nu_{S^{*}}}({\mathcal{E}}),Pr_{\nu_{{\tilde{S}}^{*}}}({\mathcal{E}})),$
(21)

where $N_{B}(\tau_{{\mathcal{A}}})$ denotes the number of times arm $B$ is
played by ${\mathcal{A}}$ in $\tau$ rounds. Note that whenever $B$ is such
that
$B\subset([n^{\prime}]{\setminus}{\tilde{S}}^{*})\cup{S^{*}},KL(\nu^{B}_{S^{*}},\nu^{B}_{{\tilde{S}}^{*}})=0$.
Therefore, we will only focus on $B$ such that
$B\not\subset([n^{\prime}]{\setminus}{\tilde{S}}^{*})\cup{S^{*}}$.

We simplify the right-hand side of Equation 21 using the following lemma.

######  Lemma 10.

For any $m\in[n^{\prime}]$ and problem instance
$\nu_{S}\in{\boldsymbol{\nu}}_{[m]}$, and any arm $B$,
$KL(\nu^{B}_{S^{*}},\nu^{B}_{{\tilde{S}}^{*}})\leq 64{\tilde{\epsilon}}^{2}$.

###### Proof.

Let $B=\\{a,b\\}$, i.e., the pair of items $a,b$ for which we make the oracle
call. Let

$R=\frac{\frac{1}{2}+{\tilde{\epsilon}}}{\frac{1}{2}-{\tilde{\epsilon}}}.$

##### Case 1: None of the items in $B$ are from $T$.

In this case, we again have four cases.

  1. 1.

Both items are good:
$\nu_{{S^{*}}}^{B}(a)=\nu_{{S^{*}}}^{B}(b)=\frac{\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}}{\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}}=\frac{1}{2}$.

  2. 2.

$a$ is good and $b$ is bad:
$\nu_{{S^{*}}}^{B}(a)=\frac{\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}}{\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}}=\frac{R^{2}}{R^{2}+1}$
and
$\nu_{{S^{*}}}^{B}(b)=\frac{\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}}{\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}}=\frac{1}{R^{2}+1}$.

  3. 3.

$a$ is bad and $b$ is good:
$\nu_{{S^{*}}}^{B}(a)=\frac{\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}}{\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}}=\frac{1}{R^{2}+1}$
and
$\nu_{{S^{*}}}^{B}(b)=\frac{\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}}{\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}}=\frac{R^{2}}{R^{2}+1}$

  4. 4.

Both items are bad:
$\nu_{{S^{*}}}^{B}(a)=\nu_{{S^{*}}}^{B}(b)=\frac{\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}}{\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}}=\frac{1}{2}$.

Now we use the upper bound from Popescu et al.,  (2016),
$KL({\mathbf{p}}_{1},{\mathbf{p}}_{2})\leq\sum_{x\in{\mathcal{X}}}\frac{p_{1}^{2}(x)}{p_{2}(x)}-1$,
for two probability mass functions ${\mathbf{p}}_{1}$ and ${\mathbf{p}}_{2}$
on the discrete random variable ${\mathcal{X}}$. In this case, the KL
divergence is non-zero when there is one item from
$([n^{\prime}]{\setminus}{\tilde{S}}^{*})\cup{S^{*}}$, say $a$, and one item
from ${\tilde{S}}^{*}{\setminus}{S^{*}}$, say $b$. Let ${\tilde{S}}^{*}$ be
such that both $a$ and $b$ are good for that alternative instance. We will
have subcases:

  1. 1.

When $a\in{S^{*}}$:

$\displaystyle KL(\nu^{B}_{S^{*}},\nu^{B}_{{\tilde{S}}^{*}})$
$\displaystyle\leq\left(\frac{R^{2}}{R^{2}+1}\right)^{2}\cdot\frac{2}{1}+\left(\frac{1}{R^{2}+1}\right)^{2}\cdot\frac{2}{1}-1$
$\displaystyle=\frac{2R^{4}+2-(R^{2}+1)^{2}}{(R^{2}+1)^{2}}$
$\displaystyle=\frac{2R^{4}+2-R^{4}-2R^{2}-1}{(R^{2}+1)^{2}}$
$\displaystyle=\frac{R^{4}-2R^{2}+1}{(R^{2}+1)^{2}}$
$\displaystyle=\frac{(R^{2}-1)^{2}}{(R^{2}+1)^{2}}$
$\displaystyle=\left(\frac{\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}-\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}}{\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}+\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}}\right)^{2}$
$\displaystyle=\left(\frac{2{\tilde{\epsilon}}}{\frac{1}{2}+2{\tilde{\epsilon}}^{2}}\right)^{2}$
$\displaystyle\leq\left(\frac{2{\tilde{\epsilon}}}{\frac{1}{2}}\right)^{2}$
$\displaystyle=64{\tilde{\epsilon}}^{2}.$

  2. 2.

When $a\in([n^{\prime}]{\setminus}{\tilde{S}}^{*})$:

$\displaystyle KL(\nu^{B}_{S^{*}},\nu^{B}_{{\tilde{S}}^{*}})$
$\displaystyle\leq\left(\frac{1}{2}\right)^{2}\cdot\frac{R^{2}+1}{1}+\left(\frac{1}{2}\right)^{2}\cdot\frac{R^{2}+1}{R^{2}}-1$
$\displaystyle=\frac{R^{2}+1}{4}+\frac{R^{2}+1}{4R^{2}}-1$
$\displaystyle=\frac{R^{4}+R^{2}+R^{2}+1-4R^{2}}{4R^{2}}$
$\displaystyle=\frac{R^{4}-2R^{2}+1}{4R^{2}}$
$\displaystyle=\frac{(R^{2}-1)^{2}}{4R^{2}}$
$\displaystyle=\frac{1}{4}\left(\frac{R^{2}-1}{R}\right)^{2}$
$\displaystyle=\frac{1}{4}\left(R-\frac{1}{R}\right)^{2}$ $\displaystyle\leq
64{\tilde{\epsilon}}^{2}.$

##### Case 2: Exactly one item in $B$ is from $T$.

Let $b\in T$. Again, we have several cases depending on item $a$.

  1. 1.

$a\in{S^{*}}$:
$\nu_{{S^{*}}}^{B}(a)=\frac{\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}}{\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{4}-{\tilde{\epsilon}}^{2}\right)}=\frac{R}{R+1}$
and
$\nu_{{S^{*}}}^{B}(b)=\frac{\theta\left(\frac{1}{4}-{\tilde{\epsilon}}^{2}\right)}{\theta\left(\frac{1}{2}+{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{4}-{\tilde{\epsilon}}^{2}\right)}=\frac{1}{R+1}$.

  2. 2.

$a\in[n^{\prime}]{\setminus}{S^{*}}$:
$\nu_{{S^{*}}}^{B}(a)=\frac{\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}}{\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{4}-{\tilde{\epsilon}}^{2}\right)}=\frac{1}{R+1}$
and
$\nu_{{S^{*}}}^{B}(b)=\frac{\theta\left(\frac{1}{4}-{\tilde{\epsilon}}^{2}\right)}{\theta\left(\frac{1}{2}-{\tilde{\epsilon}}\right)^{2}+\theta\left(\frac{1}{4}-{\tilde{\epsilon}}^{2}\right)}=\frac{R}{R+1}$.

Note that here we have only one case where $a\not\in T$ is bad in ${S^{*}}$
and good in ${\tilde{S}}^{*}$. Then,

$\displaystyle KL(\nu^{B}_{S^{*}},\nu^{B}_{{\tilde{S}}^{*}})$
$\displaystyle\leq\left(\frac{1}{R+1}\right)^{2}\cdot\frac{R+1}{R}+\left(\frac{R}{R+1}\right)^{2}\cdot\frac{R+1}{1}-1$
$\displaystyle=\frac{1}{R(R+1)}+\frac{R^{2}}{R+1}-1$
$\displaystyle=\frac{1+R^{3}-R^{2}-R}{R(R+1)}$
$\displaystyle=\frac{(1-R)^{2}(1+R)}{R(R+1)}$
$\displaystyle=\frac{(1-R)^{2}}{R}$
$\displaystyle=\left(\frac{\frac{1}{2}-{\tilde{\epsilon}}-\frac{1}{2}-{\tilde{\epsilon}}}{\frac{1}{2}+{\tilde{\epsilon}}}\right)^{2}\cdot\left(\frac{\frac{1}{2}+{\tilde{\epsilon}}}{\frac{1}{2}-{\tilde{\epsilon}}}\right)$
$\displaystyle=\frac{4{\tilde{\epsilon}}^{2}}{\frac{1}{4}-{\tilde{\epsilon}}^{2}}$
$\displaystyle\leq 32{\tilde{\epsilon}}^{2}$
$\displaystyle\because~{}~{}{\tilde{\epsilon}}^{2}>\frac{1}{8}\implies\frac{1}{4}-{\tilde{\epsilon}}^{2}>\frac{1}{8}$
$\displaystyle\leq 64{\tilde{\epsilon}}^{2}.$

∎ Now applying Lemma 6 and Lemma 10 for each altered problem instance
$\nu^{B}_{{\tilde{S}}^{*}}$, each corresponding to any one of the ${n/2\choose
n/4}$ different choices of $S^{\prime}\in[n^{\prime}]\setminus{S^{*}}$ such
that $|S^{\prime}|=n/4$, and summing all the resulting inequalities gives:

$\displaystyle\sum_{S^{\prime}\in[n^{\prime}]\setminus{S^{*}}:|S^{\prime}|=n/4}\sum_{B}{\mathbf{E}}_{\nu^{B}_{S^{*}}}[N_{B}(\tau_{{\mathcal{A}}})]KL(\nu^{B}_{S^{*}},\nu^{B}_{{\tilde{S}}^{*}})\geq{\frac{n}{2}\choose\frac{n}{4}}\ln\frac{{n/2\choose
n/4}}{4\delta}.$ (22)

In the left-hand side of Equation 22 above, the arms $B$ that have KL
divergence $>0$ are those where exactly one item in $B$ is flipped from bad to
a good item in ${S^{*}}$ and ${\tilde{S}}^{*}$ respectively. Therefore, such a
$B$ shows up for exactly ${n/2-1\choose n/4-1}$ many times. Thus, given a
fixed set $B$, the coefficient of the term ${\mathbf{E}}_{\nu^{B}_{S^{*}}}$
becomes ${\frac{n}{2}-1\choose\frac{n}{4}-1}64{\tilde{\epsilon}}^{2}$.

Therefore,

$\displaystyle\sum_{\\{B\in{\mathcal{B}}\\}}{\mathbf{E}}_{\nu^{B}_{S^{*}}}[N_{B}(\tau_{A})]KL(\nu^{B}_{S^{*}},\nu^{B}_{{\tilde{S}}^{*}})\leq\sum_{\\{B\in{\mathcal{B}}\\}}{\mathbf{E}}_{\nu^{B}_{S^{*}}}[N_{B}(\tau_{A})]{\frac{n}{2}-1\choose\frac{n}{4}-1}64{\tilde{\epsilon}}^{2}.$

Finally noting that $\tau_{A}\geq\sum_{B\in{\mathcal{B}}}[N_{B}(\tau_{A})]$,
we get

$\displaystyle{\frac{n}{2}-1\choose\frac{n}{4}-1}64{\tilde{\epsilon}}^{2}{\mathbf{E}}_{\nu^{B}_{S^{*}}}[\tau_{A}]=\sum_{S\in{\mathcal{B}}}{\mathbf{E}}_{\nu^{B}_{S^{*}}}[N_{B}(\tau_{A})]({\frac{n}{2}-1\choose\frac{n}{4}-1}64{\tilde{\epsilon}}^{2})\geq{\frac{n}{2}\choose\frac{n}{4}}\ln\frac{{\frac{n}{2}\choose\frac{n}{4}}}{4\delta}.$

Note that ${n\choose r}={n-1\choose r-1}\frac{n}{r}$. Therefore,

$\displaystyle{\mathbf{E}}[\tau_{A}]\geq\frac{1}{{\tilde{\epsilon}}^{2}}\frac{n/2}{n/4}\ln\frac{{\frac{n}{2}\choose\frac{n}{4}}}{4\delta}=\frac{2}{{\tilde{\epsilon}}^{2}}\ln\frac{{\frac{n}{2}\choose\frac{n}{4}}}{\delta}\geq\frac{2}{{\tilde{\epsilon}}^{2}}\ln\frac{2^{n/2}\sqrt{6}}{\sqrt{\pi\left(3n/2+2\right)}\delta}=\frac{n}{{\tilde{\epsilon}}^{2}}+\frac{1}{{\tilde{\epsilon}}^{2}}\ln\frac{6}{\pi\left(3n/2+2\right)\delta}\geq\frac{n}{{\tilde{\epsilon}}^{2}}.$

When, $p<q$, we consider the instances to be such that all the items are from
the same group. Hence, the above gives the sample complexity. Whereas, when
$p\geq q$, we consider the instances to be such that each item is from a
different group. Even in this case, the objective function is similar to the
one-group case with the parameter $q$ in place of $p$. Therefore, with the
one-group case we are able to compute the lower bound on the sample complexity
as
$\Omega\left(\frac{n^{1+\max\left\\{\frac{2}{p},\frac{2}{q}\right\\}}}{\epsilon^{2}}\right)$.
This is loose by a multiplicative factor of $\ln\frac{n}{\delta}$. ∎

###### Proof.

Follows from Lemma 5 and Lemma 4. ∎

###  B.3 Sample Complexity Bounds for group-aware Algorithms

####  B.3.1 Upper Bound

###### Proof.

Let $\boldsymbol{\sigma}$ be the ranking returned by Algorithm 1, and
$\epsilon_{h}=\epsilon\cdot\left(\frac{n_{h}}{\phi_{h}\gamma}\right)^{1/q},\forall
h\in[\gamma]$. We will first prove the correctness of Algorithm 1.

##### Correctness.

Algorithm 1 computes the ranking in two steps, (1) finding group-wise ranking
using the Beat-the-Pivot algorithm and (2) merging the group-wise rankings to
get an overall ranking. In both the steps, the algorithm ensures that between
any pair of items from groups $h$ and $h^{\prime}$, the error in their
pairwise ranking is at most $\min\\{\epsilon_{h},\epsilon_{h^{\prime}}\\}$. We
will now show that this ensures that the
$\text{err}_{p,q}(\boldsymbol{\sigma};\theta)<\epsilon$. For ease of
exposition, let us define the following intra-group and inter-group errors for
each item,

$d^{(h)}_{i}(\boldsymbol{\sigma};\theta):=\max_{\begin{subarray}{c}i^{\prime}\in
G_{h}~{}\text{s.t.}\\\
\theta_{i}>\theta_{i^{\prime}}\land\boldsymbol{\sigma}^{-1}(i)>\boldsymbol{\sigma}^{-1}(i^{\prime})\end{subarray}}\theta_{i}-\theta_{i^{\prime}}\qquad\text{and}\qquad
d^{(\neg
h)}_{i}(\boldsymbol{\sigma};\theta):=\max_{\begin{subarray}{c}i^{\prime}\in[n]{\setminus}G_{h}~{}\text{s.t.}\\\
\theta_{i}>\theta_{i^{\prime}}\land\boldsymbol{\sigma}^{-1}(i)>\boldsymbol{\sigma}^{-1}(i^{\prime})\end{subarray}}\theta_{i}-\theta_{i^{\prime}}.$

Fix a group $h\in[\gamma]$ and let $n_{h}=|G_{h}|$, the size of the group. Let
${\tilde{\epsilon}}_{h}=\frac{\epsilon_{h}}{2}\cdot\left(\frac{2}{n_{h}}\right)^{1/p}$
and $\delta^{\prime}_{h}=\frac{\delta}{2n\gamma}$. First, Beat-the-Pivot is
run for the items within the group $h$. Therefore, from Lemma 4 we know that
$\boldsymbol{\sigma}$ is an ${\tilde{\epsilon}}_{h}$-Best-Rank with
probability at least $1-\delta^{\prime}_{h}$. Therefore, for any item $i\in
G_{h}$,

$\Pr\left[d_{i}^{(h)}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\right]<\delta^{\prime}_{h}=\frac{\delta}{2n\gamma}.$

For any pair of items $i,i^{\prime}$ from two different groups $h,h^{\prime}$
respectively, their ordering will be decided using Beat-the-Pivot with error
parameter $\min\\{{\tilde{\epsilon}}_{h},{\tilde{\epsilon}}_{h^{\prime}}\\}$
and confidence parameter $\frac{\delta}{2n^{2}\gamma}$. W.l.o.g. let
${\tilde{\epsilon}}_{h}\leq{\tilde{\epsilon}}_{h^{\prime}}$. Then,

$\Pr\left[d_{i}^{(\neg
h)}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\right]<\frac{\delta}{2n^{2}\gamma}~{}~{}\text{and}~{}~{}\Pr\left[d_{i^{\prime}}^{(\neg
h^{\prime})}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h^{\prime}}\right]<\Pr\left[d_{i^{\prime}}^{(\neg
h^{\prime})}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\right]<\frac{\delta}{2n^{2}\gamma}.$

Using this, correctness of Algorithm 1 can be shown as follows,

$\displaystyle\Pr[\text{err}^{\texttt{fair}}(\boldsymbol{\sigma};\theta)>\epsilon]$
$\displaystyle=\Pr\left[\left(\sum_{h\in[\gamma]}\frac{\phi_{h}}{|G_{h}|}\text{err}_{h,p}{(\boldsymbol{\sigma};\theta)^{q}}\right)^{1/q}>\epsilon\right]$
$\displaystyle\leq\Pr\left[\bigvee\limits_{h\in[\gamma]}\bigvee\limits_{i\in
G_{h}}d_{i}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\right].$

Because otherwise, if for all $h\in[\gamma]$, and $\forall i\in G_{h}$,
$d_{i}(\boldsymbol{\sigma};\theta)\leq\epsilon_{h}$, we have that,

$\displaystyle\text{err}_{h}(\boldsymbol{\sigma};\theta)$
$\displaystyle\leq\left(n_{h}\left(\frac{\epsilon_{h}}{2}\left(\frac{2}{n_{h}}\right)^{1/p}\right)^{p}\right)^{1/p}$
$\displaystyle=\left(n_{h}\cdot\frac{\epsilon_{h}^{p}}{2^{p}}\cdot\frac{2}{n_{h}}\right)^{1/p}$
$\displaystyle=\epsilon_{h}\cdot\frac{2^{1/p}}{2}\leq\epsilon_{h}$
$\displaystyle\because~{}~{}p\geq 1\implies 1/p\leq 1$
$\displaystyle\implies\text{err}^{\texttt{fair}}$
$\displaystyle\leq\left(\sum_{h\in[\gamma]}\frac{\phi_{h}}{n_{h}}\left(\epsilon\cdot\left(\frac{n_{h}}{\phi_{h}\gamma}\right)^{1/q}\right)^{q}\right)^{1/q}$
$\displaystyle=\left(\sum_{h\in[\gamma]}\frac{\phi_{h}}{n_{h}}\cdot\epsilon_{q}\cdot\frac{n_{h}}{\phi_{h}\gamma}\right)^{1/q}\leq\epsilon.$

Therefore,

$\displaystyle\Pr[\text{err}^{\texttt{fair}}$
$\displaystyle(\boldsymbol{\sigma};\theta)>\epsilon]$
$\displaystyle\leq\Pr\left[\bigvee\limits_{h\in[\gamma]}\bigvee\limits_{i\in
G_{h}}\left(d_{i}^{(h)}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\lor
d_{i}^{(\neg
h)}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\right)\right]$
$\displaystyle=\Pr\left[\bigvee\limits_{h\in[\gamma]}\bigvee\limits_{i\in
G_{h}}d_{i}^{(h)}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\right]+\Pr\left[\bigvee\limits_{h\in[\gamma]}\bigvee\limits_{i\in
G_{h}}d_{i}^{(\neg
h)}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\right]$
$\displaystyle=\Pr\left[\bigvee\limits_{h\in[\gamma]}\bigvee\limits_{i\in
G_{h}}d_{i}^{(h)}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\right]+\Pr\left[\bigvee\limits_{h\in[\gamma]}\bigvee\limits_{i\in
G_{h}}\max\limits_{\begin{subarray}{c}i^{\prime}\in G_{h^{\prime}}\text{ s.t.
}h>h^{\prime}\land,\\\
\boldsymbol{\sigma}^{-1}(i)>\boldsymbol{\sigma}^{-1}(i^{\prime})\end{subarray}}\theta_{i}-\theta_{i^{\prime}}>{\tilde{\epsilon}}_{h}\right]$
$\displaystyle\leq\Pr\left[\bigvee\limits_{h\in[\gamma]}\bigvee\limits_{i\in
G_{h}}d_{i}^{(h)}(\boldsymbol{\sigma};\theta)>{\tilde{\epsilon}}_{h}\right]+\Pr\left[\bigvee\limits_{h\in[\gamma]}\bigvee\limits_{i\in
G_{h}}\bigvee\limits_{\begin{subarray}{c}i^{\prime}\notin G_{h}\text{ s.t.
}h\neq h^{\prime}\land,\\\
\boldsymbol{\sigma}^{-1}(i)>\boldsymbol{\sigma}^{-1}(i^{\prime})\end{subarray}}\theta_{i}-\theta_{i^{\prime}}>{\tilde{\epsilon}}_{h}\right]$
$\displaystyle<\sum_{h\in[\gamma]}\sum_{i\in
G_{h}}\frac{\delta}{2n\gamma}+\sum_{h\in[\gamma]}\sum_{i\in
G_{h}}\sum_{h^{\prime}>h}\sum_{i^{\prime}\in
G_{h^{\prime}}}\frac{\delta}{2n^{2}\gamma}$
$\displaystyle\leq\sum_{h\in[\gamma]}\frac{\delta}{2\gamma}+\sum_{h\in[\gamma]}\frac{\delta}{2\gamma}$
$\displaystyle=\frac{\delta}{2}+\frac{\delta}{2}$ $\displaystyle=\delta.$

##### Sample Complexity.

  * •

Group-wise rankings. Let $n_{h}=|G_{h}|$. From Lemma 4 we know that the sample
complexity to find a group-wise ranking $\sigma_{h}$ for group $h\in[\gamma]$
is
${\mathcal{O}}\left(\frac{n_{h}}{{\tilde{\epsilon}}_{h}^{2}}\log\frac{n_{h}}{\delta}\right)$.
Therefore, the sum of the sample complexities to find all the group-wise
rankings is
${\mathcal{O}}\left(\sum_{h=1}^{\gamma}\frac{n_{h}}{{\tilde{\epsilon}}_{h}^{2}}\log\frac{n_{h}}{\delta}\right)$.

  * •

Merging group-wise rankings. The algorithm merges two lists at a time. Hence,
it takes $O(\log\gamma)$ iterations of the while loop before the algorithm
terminates. In each iteration of the while loop, we need to find a merged
list, of length $n_{h}+n_{h^{\prime}}$, the sum of the lengths of the two
sorted lists that are being merged. To fill each position in the merged list,
we make
$O\left(\frac{1}{\min\\{{\tilde{\epsilon}}_{h},{\tilde{\epsilon}}_{h^{\prime}}\\}^{2}}\log\frac{2n^{2}\gamma}{\delta}\right)=O\left(\frac{1}{\min\\{{\tilde{\epsilon}}_{h},{\tilde{\epsilon}}_{h^{\prime}}\\}^{2}}\log\frac{2n\gamma}{\delta}\right)$
oracle calls, since $\gamma\leq n$. Note that since the values of
${\tilde{\epsilon}}_{h}$ are different for different groups, merging different
lists takes a different number of Oracle calls, which makes it hard to analyze
the sample complexity. Hence, from now on, we will analyze the sample
complexity using the smallest group-wise error. Let
$g:=\arg\min_{h\in[\gamma]}{\tilde{\epsilon}}_{h}$. Now, the sample complexity
of merging two lists will be
$O\left((n_{h}+n_{h^{\prime}})\cdot\frac{1}{{\tilde{\epsilon}}_{g}^{2}}\log\frac{2n\gamma}{\delta}\right)=O\left((n_{h}+n_{h^{\prime}})\cdot\frac{1}{{\tilde{\epsilon}}_{g}^{2}}\log\frac{n}{\delta}\right)$.
Therefore, the total sample complexity for one iteration of the while loop can
be upper bounded by
$O\left(\left(\sum_{h\in[\gamma]}n_{h}\right)\cdot\frac{1}{{\tilde{\epsilon}}_{g}^{2}}\log\frac{n}{\delta}\right)$
which is
$O\left(\frac{n}{{\tilde{\epsilon}}_{g}^{2}}\log\frac{n}{\delta}\right)$. Note
that this is the sample complexity for every iteration of the while loop.
Therefore, the total sample complexity of the algorithm can be upper bounded
by
$O\left(\frac{n\log\gamma}{{\tilde{\epsilon}}_{g}^{2}}\log\frac{n}{\delta}\right)$.

Therefore, the total sample complexity is,

$\displaystyle{\mathcal{O}}\left(\left(\sum_{h=1}^{\gamma}\frac{n_{h}}{{\tilde{\epsilon}}_{h}^{2}}\log\frac{n}{\delta}\right)+\left(\frac{n\log\gamma}{{\tilde{\epsilon}}_{g}^{2}}\log\frac{n}{\delta}\right)\right)$

Note that neither of these terms strictly dominates the other for all problem
instances. Substituting
${\tilde{\epsilon}}_{h}=\frac{\epsilon_{h}}{2}\cdot\left(\frac{2}{n_{h}}\right)^{1/p}$
we get that the sample complexity is,

$\displaystyle{\mathcal{O}}\left(\left(\sum_{h=1}^{\gamma}\frac{n_{h}^{1+\frac{2}{p}}}{\epsilon_{h}^{2}}\log\frac{n}{\delta}\right)+\left(\frac{n\cdot
n_{g}^{2/p}\cdot\log\gamma}{\epsilon_{g}^{2}}\log\frac{n}{\delta}\right)\right).$

∎

####  B.3.2 Lower Bound

###### Proof.

We begin by constructing the class of hard of instance where the algorithm
needs to get the ordering of the items within the groups entirely correct
according to their true scores, i.e., even one swap within the group will
result in the overall error of $>\epsilon$.

##### Class of instances for group-aware algorithms.

For a fixed group $h\in[\gamma]$, let
$\epsilon_{h}:=\epsilon\cdot\left(\frac{2n_{h}}{\phi_{h}\gamma}\right)^{1/q}$and
${\tilde{\epsilon}}_{h}=\epsilon_{h}\cdot\left(\frac{4}{n_{h}}\right)^{1/p}$,
where $n_{h}=|G_{h}|$. For any $h\in[\gamma]$, let $n_{h}^{\prime}:=3n_{h}/4$.
Let $I_{h}:=\\{i\in G_{h}\\}$ be an ordered index set of the items in group
$h$ such that $I_{h}(j)$ gives the $j$th item in $I_{h}$. We use $I_{h}[t]$ to
represent the first $t$ items in $I_{h}$. Let
$T_{h}:=\\{I_{h}(n_{h}^{\prime}+1),I_{h}(n_{h}^{\prime}+2),\ldots,I_{h}(n_{h})\\}$.
For any ranking $\boldsymbol{\sigma}$, we use $\boldsymbol{\sigma}^{(h)}$ to
represent the sub-ranking corresponding to group $h$, i.e., it gives us a
ranking of the items only from group $h$ in the original ranking
$\boldsymbol{\sigma}$, where $\forall i,i^{\prime}\in
G_{h},\boldsymbol{\sigma}(i)<\boldsymbol{\sigma}(i^{\prime})\iff\boldsymbol{\sigma}^{(h)}(i)<\boldsymbol{\sigma}^{(h)}(i^{\prime})$.
Note that throughout the paper, we are only interested in the relative
ordering of the items, hence, the exact ranks of the items in
$\boldsymbol{\sigma}^{(h)}$ are not of concern. That is, the last $n_{h}/4$
items from group $h$ are put in the set $T_{h}$. Now consider the class of
instances ${\boldsymbol{\nu}}_{[m_{1},m_{2},\ldots,m_{\gamma}]}$ for any
$m_{h}\in[n_{h}^{\prime}]$ which contains instances represented as $\nu_{S}$
where $S:=\bigcup_{h\in[\gamma]}S_{h}$ and $S_{h}\subseteq
I_{h}(n_{h}^{\prime})$ such that $|S_{h}|=m_{h}$ and the scores of the items
for the instance $\nu_{S}$ are

$\forall h\in[\gamma],\forall i\in
S_{h},~{}~{}\theta_{i}=\theta^{(h)}\left(\frac{1}{2}+{\tilde{\epsilon}}_{h}\right)^{2},~{}~{}\forall
i\in
T_{h},~{}~{}\theta_{i}=\theta^{(h)}\left(\frac{1}{4}-{\tilde{\epsilon}}_{h}^{2}\right),\\\
\text{and}\qquad\forall i\not\in S_{h}\cup
T_{h},~{}~{}\theta_{i}=\theta^{(h)}\left(\frac{1}{2}-{\tilde{\epsilon}}_{h}\right)^{2},$

for some numbers $\theta^{(h)}$ for each group $h\in[\gamma]$ to be defined
later.

######  Remark.

Note that $S$ uniquely represents an instance
$\nu_{S}\in{\boldsymbol{\nu}}_{[m_{1},m_{2},\ldots,m_{\gamma}]}$ for any fixed
$m_{h}\in[n_{h}^{\prime}],\forall h\in[\gamma]$.

######  Lemma 11.

For any $\theta^{(h)}>\frac{1}{1-2{\tilde{\epsilon}}_{h}}$ for each group
$h\in[\gamma]$ and for any problem instance
$\nu_{S}\in{\boldsymbol{\nu}}_{[m_{1},m_{2},\ldots,m_{h}]}$ such that for each
group $h\in[\gamma]$, $m_{h}=n_{h}/4$, any $\epsilon$-Best-Fair-Ranking, say
$\boldsymbol{\sigma}_{S}$, has to satisfy the following: for at least half the
number of groups, the number of items from $S_{h}\cup T_{h}$ in ranks
$\frac{n_{h}}{4}+2$ to $n_{h}$ in the sub-ranking of the items only from group
$h$ in $\boldsymbol{\sigma}$ should be strictly less than $\frac{n_{h}}{4}$.

###### Proof.

Note that when $\theta^{(h)}>\frac{1}{1-2{\tilde{\epsilon}}_{h}}$, for any
$i\in S_{h},i^{\prime}\in T_{h}$ and $i^{\prime\prime}\in
G_{h}{\setminus}(S_{h}\cup T_{h})$,

$\theta_{i}-\theta_{i^{\prime}}>{\tilde{\epsilon}},~{}~{}\theta_{i^{\prime}}-\theta_{i^{\prime\prime}}>{\tilde{\epsilon}},~{}~{}\text{and}~{}~{}\theta_{i}-\theta_{i^{\prime\prime}}>{\tilde{\epsilon}}.$

Let us assume that there exists an $\epsilon$-Best-Fair-Ranking for $\nu_{S}$,
say $\boldsymbol{\sigma}_{S}$, such that the ranks $\frac{n_{h}}{4}+2$ to
$n_{h}$ have $\geq\frac{n_{h}}{4}$ items from $S_{h}\cup T_{h}$. Let
$\Gamma\subseteq[\gamma]$ be the set of groups on which this happens. Then for
each such group in $\Gamma$, $\leq\frac{n_{h}}{4}$ items from $S_{h}\cup
T_{h}$ are in the ranks $1$ to $\frac{n_{h}}{4}+1$ in the sub-ranking
$\boldsymbol{\sigma}_{S}^{(h)}$, since $|S_{h}\cup T_{h}|=\frac{n_{h}}{2}$. So
there will be at least one item from $I_{h}[n_{h}^{\prime}]{\setminus}S_{h}$
in ranks $1$ to $\frac{n_{h}}{4}+1$ in $\boldsymbol{\sigma}^{(h)}_{S}$, which
implies that at least $\frac{n_{h}}{4}$ items in $S_{h}\cup T_{h}$ incur an
error $>{\tilde{\epsilon}}_{h}$. Therefore, the overall error for that group
will be,

$\displaystyle\text{err}_{h}(\boldsymbol{\sigma}^{(h)}_{S};\theta_{S})$
$\displaystyle=\left(\sum_{i\in[n]}d_{i}(\boldsymbol{\sigma}^{(h)}_{S};\theta_{S})^{p}\right)^{1/p}>\left(\frac{n}{4}\cdot{\tilde{\epsilon}}^{p}\right)^{1/p}$
$\displaystyle=\left(\frac{n}{4}\cdot\left(\epsilon\cdot\left(\frac{4}{n}\right)^{1/p}\right)^{p}\right)^{1/p}=\left(\epsilon^{p}\right)^{1/p}=\epsilon,$

Then,

$\displaystyle\text{err}^{\texttt{fair}}(\boldsymbol{\sigma}_{S};\theta_{S})$
$\displaystyle=\left(\sum_{h\in[\gamma]}\frac{\phi_{h}}{n_{h}}\cdot\text{err}_{h}(\boldsymbol{\sigma}^{(h)}_{S};\theta_{S})^{q}\right)^{1/q}\geq\left(\sum_{h\in\Gamma}\frac{\phi_{h}}{n_{h}}\cdot\text{err}_{h}(\boldsymbol{\sigma}^{(h)}_{S};\theta_{S})^{q}\right)^{1/q}$
$\displaystyle=\left(\sum_{h\in\Gamma}\frac{\phi_{h}}{n_{h}}\cdot\epsilon_{h}^{q}\right)^{1/q}=\left(\sum_{h\in\Gamma}\frac{\phi_{h}}{n_{h}}\cdot\left(\frac{2n_{h}}{\phi_{h}\gamma}\cdot\epsilon^{q}\right)\right)^{1/q}$
$\displaystyle>\left(\frac{\gamma}{2}\cdot\frac{2\epsilon^{q}}{\gamma}\right)^{1/q}$
$\displaystyle=\epsilon.$

∎

##### The alternative instances.

We now fix any set $S^{*}\subset\bigcup_{h\in[\gamma]}I_{h}[n_{h}^{\prime}]$
such that for half the number of groups $\Gamma\subset[\gamma]$, $|S^{*}\cap
G_{h}|=\frac{n_{h}}{2}$ and for the other half $|S^{*}\cap
G_{h}|=\frac{n_{h}}{4}$. Lower bound on the sample complexity is now obtained
by applying Lemma 6 on a pair of instances
$(\nu_{S^{*}},\nu_{{\tilde{S}}^{*}})$, for all possible choices of
${\tilde{S}}^{*}={S^{*}}\cup S^{\prime}$, where for exactly one group
$h\in[\gamma]{\setminus}\Gamma$,
$S^{\prime}\subset\left(I_{h}[n_{h}^{\prime}]{\setminus}{S^{*}}\right)$ and
$|S^{\prime}\cap G_{h}|=\frac{n_{h}}{4}$. Note that there will be
$\sum_{h\in[\gamma]{\setminus}\Gamma}{n_{h}/2\choose n_{h}/4}$ choices of
${\tilde{S}}^{*}$.

##### Describing the event.

For any ranking $\boldsymbol{\sigma}\in\Sigma_{n}$, we denote by
$\boldsymbol{\sigma}(r:r^{\prime})$ the set of items in the ranking,
$\boldsymbol{\sigma}$, from rank $r$ to rank $r^{\prime}$, for any $1\leq
r\leq r^{\prime}\leq n$. Consider the event ${\mathcal{E}}$ for an instance
$S$ that the algorithm ${\mathcal{A}}$ outputs a ranking such that for at
least half the number of groups the following holds: for the sub-ranking
corresponding to the group $h\in[\gamma]$, the number of items from $S_{h}\cup
T_{h}$ in the ranks $n_{h}/4+2$ to $n_{h}$ is $<n_{h}/4$. That is,

${\mathcal{E}}(S):=\left|\left\\{h\in[\gamma]:\left|(S_{h}\cup
T_{h})\cap\boldsymbol{\sigma}^{(h)}_{{\mathcal{A}}}\left(n_{h}/4+2:n_{h}\right)\right|<n_{h}/4\right\\}\right|\geq\frac{\gamma}{2}.$

This is a high probability for $S^{*}$ because otherwise, the error will be
more than $\epsilon$, from Lemma 7. On the contrary, for the alternative
instances with ${\tilde{S}}^{*}$, this is a low probability event because for
at least half the number of groups all the items from $T_{h}$ have to appear
in the ranks $n_{h}/4+2$ to $n_{h}$ or otherwise, $\geq n_{h}/4$ items from
$S_{h}$ will be in ranks $n_{h}/4+2$ to $n_{h}$ and they all incur an error
$>{\tilde{\epsilon}}_{h}$ due to an item from $T_{h}$ in the ranks $1$ to
$n_{h}/4+1$; therefore the total error will be more than $\epsilon$.

It is easy to note that as ${\mathcal{A}}$ is an $(\epsilon,\delta)$-PAC-
Ranker , obviously

$Pr_{S^{*}}({\mathcal{E}}({S^{*}}))>Pr_{S^{*}}(\boldsymbol{\sigma}_{{\mathcal{A}}}\text{
is an {\bf$\epsilon$-Best-Ranking}})>1-\delta,$ (23)

and

$Pr_{{\tilde{S}}^{*}}({\mathcal{E}}({S^{*}}))<\delta,$ (24)

for any alternative instance ${\tilde{S}}^{*}$.

The way the class of instances is constructed, the algorithms need to satisfy
${\mathcal{E}}_{h}(S_{h})$ for groups $h\in[\gamma]{\setminus}\Gamma$ because
the algorithm making pairwise comparisons in group
$h\in[\gamma]{\setminus}\Gamma$ differentiates between the true instance and a
distinct set of alternative instances, namely those where the scores of the
items from group $h$ are altered, but it can not differentiate between any
other altered instance and the true instance. Therefore,

$\displaystyle
Pr_{{\tilde{S}}^{*}}({\mathcal{E}}(S^{*}))=Pr_{{\tilde{S}}^{*}}\left(\bigcup_{h\in[\gamma]{\setminus}\Gamma}{\mathcal{E}}_{h}(S_{h}^{*})\right)=\sum_{h\in[\gamma]{\setminus}\Gamma}Pr_{{\tilde{S}}_{h}^{*}}({\mathcal{E}}_{h}(S_{h}^{*})).$

Therefore, if there exists even one group $h\in[\gamma]{\setminus}\Gamma$ such
that $Pr_{{\tilde{S}}_{h}^{*}}({\mathcal{E}}_{h}(S_{h}^{*}))>\delta$, it
implies that $Pr_{{\tilde{S}}^{*}}({\mathcal{E}}(S^{*}))>\delta$, which
contradicts that ${\mathcal{A}}$ is an $(\epsilon,\delta)$-PAC-Ranker.
Therefore, for every group $h\in[\gamma]{\setminus}\Gamma$, the algorithm
${\mathcal{A}}$ needs to satisfy that
$Pr_{{\tilde{S}}_{h}^{*}}({\mathcal{E}}_{h}(S_{h}^{*}))<\delta$. Similar
argument gives us that
$Pr_{S_{h}^{*}}({\mathcal{E}}_{h}(S_{h}^{*}))>1-\delta$, for every group
$h\in[\gamma]{\setminus}\Gamma$.

We can further apply Lemma 8 to get

$Pr_{{\tilde{S}}_{h}^{*}}({\mathcal{E}}_{h}(S^{*}_{h}))<\frac{\delta}{{n_{h}/2\choose
n_{h}/4}},\forall h\in[\gamma]{\setminus}\Gamma.$ (25)

From Lemma 10 we then have that,
$KL(\nu^{B}_{S^{*}_{h}}),\nu^{B}_{{\tilde{S}}_{h}^{*}})\leq
64{\tilde{\epsilon}}_{h}^{2}$ for every $h\in[\gamma]{\setminus}\Gamma$ and
for every $B\in{\mathcal{B}}_{h}$. Therefore, applying Lemma 6 for every group
$h\in[\gamma]{\setminus}\Gamma$ we get,

$\displaystyle\sum_{\\{B\in{\mathcal{B}}_{h}\\}}{\mathbf{E}}_{\nu^{B}_{S_{h}^{*}}}[N_{B}(\tau_{A})]KL(\nu^{B}_{S_{h}^{*}},\nu^{B}_{{\tilde{S}}_{h}^{*}})\leq\sum_{\\{B\in{\mathcal{B}}_{h}\\}}{\mathbf{E}}_{\nu^{B}_{S_{h}^{*}}}[N_{B}(\tau_{A})]{\frac{n_{h}}{2}-1\choose\frac{n_{h}}{4}-1}64{\tilde{\epsilon}}^{2}.$

Finally noting that
$\tau_{A}^{(h)}\geq\sum_{B\in{\mathcal{B}}_{h}}[N_{B}(\tau_{A})]$, we get

$\displaystyle{\frac{n_{h}}{2}-1\choose\frac{n_{h}}{4}-1}64{\tilde{\epsilon}}^{2}{\mathbf{E}}_{\nu^{B}_{S_{h}^{*}}}[\tau_{A}^{(h)}]=\sum_{S\in{\mathcal{B}}_{h}}{\mathbf{E}}_{\nu^{B}_{S_{h}^{*}}}[N_{B}(\tau_{A}^{(h)})]({\frac{n_{h}}{2}-1\choose\frac{n_{h}}{4}-1}64{\tilde{\epsilon}}^{2})\geq{\frac{n_{h}}{2}\choose\frac{n_{h}}{4}}\ln\frac{{\frac{n_{h}}{2}\choose\frac{n_{h}}{4}}}{4\delta}.$

Therefore,

$\displaystyle{\mathbf{E}}[\tau_{A}^{(h)}]$
$\displaystyle\geq\frac{1}{{\tilde{\epsilon}}_{h}^{2}}\frac{n_{h}/2}{n_{h}/4}\ln\frac{{\frac{n_{h}}{2}\choose\frac{n_{h}}{4}}}{4\delta}=\frac{2}{{\tilde{\epsilon}}^{2}}\ln\frac{{\frac{n_{h}}{2}\choose\frac{n_{h}}{4}}}{\delta}$
$\displaystyle\geq\frac{2}{{\tilde{\epsilon}}_{h}^{2}}\ln\frac{2^{n_{h}/2}\sqrt{6}}{\sqrt{\pi\left(3n_{h}/2+2\right)}\delta}=\frac{n_{h}}{{\tilde{\epsilon}}_{h}^{2}}+\frac{1}{{\tilde{\epsilon}}_{h}^{2}}\ln\frac{6}{\pi\left(3n_{h}/2+2\right)\delta}\geq\frac{n_{h}}{{\tilde{\epsilon}}_{h}^{2}}.$

Since $\tau_{A}\geq\sum_{h\in[\gamma]{\setminus}\Gamma}\tau_{A}^{(h)}$, we
get,

$\displaystyle{\mathbf{E}}[\tau_{A}]\geq\sum_{h\in[\gamma]{\setminus}\Gamma}{\mathbf{E}}[\tau_{A}^{(h)}]\geq\sum_{h\in[\gamma]{\setminus}\Gamma}\frac{n_{h}}{{\tilde{\epsilon}}_{h}^{2}}\geq\frac{1}{2}\sum_{h\in[\gamma]}\frac{n_{h}}{{\tilde{\epsilon}}_{h}^{2}}.$

Therefore, the sample complexity to figure out the group-wise rankings is
$\Omega\left(\sum_{h\in[\gamma]}\frac{n_{h}}{{\tilde{\epsilon}}_{h}^{2}}\right)$.

∎

##  Appendix C Additional Experimental Results

Following is a summary of the results presented here:

  1. 1.

Table 1 shows the proportions of the groups in the top $n$ items. This helps
visualize that the group-wise errors computed by our group-aware algorithm are
proportional to the sizes of the groups (see Figure 3).

  2. 2.

Figures 6, 7, 8 and 9 show the results on the synthetic datasets whose true
scores are as shown in Figure 5.

  3. 3.

Figure 10 shows the group-wise errors for the synthetic datasets. Again,
group-aware
achieves proportional errors across groups.

  4. 4.

Figures 11 and 12 show the results when we choose $\phi_{h}=n_{h}$ instead of
$\phi_{h}=1$.

Dataset | $n$ | $G_{0}$ | $G_{1}$ | $G_{2}$
---|---|---|---|---
COMPAS-race | 25 | 88% | 12% | -
COMPAS-race | 50 | 88% | 12% | -
COMPAS-race | 100 | 87% | 13% | -
COMPAS-gender | 25 | 92% | 8% | -
COMPAS-gender | 50 | 92% | 8% | -
COMPAS-gender | 100 | 84% | 16% | -
German-age | 25 | 76% | 16% | 8%
German-age | 50 | 76% | 16% | 8%
German-age | 100 | 76% | 15% | 9%
Table 1: Proportion of the groups in the top $n$ items in the real-world
datasets. Figure 5: True scores of the synthetic datasets where in geo the
scores decrease in a geometric progression, in arith the scores decrease in an
arithmetic progression, in steps the scores decrease in an arithmetic
progression but only for every 5 items, and for har the scores decrease in a
harmonic progression. The colors of the bars represent the groups the items
belong to. Figure 6: Group-wise errors (for $n=25$) for geo dataset for $g-0$
(majority group) and $g-1$ (minority group). Figure 7: Group-wise errors (for
$n=25$) for arith dataset for $g-0$ (majority group) and $g-1$ (minority
group). Figure 8: Group-wise errors (for $n=25$) for steps dataset for $g-0$
(majority group) and $g-1$ (minority group). Figure 9: Group-wise errors (for
$n=25$) for har dataset for $g-0$ (majority group) and $g-1$ (minority group).
Figure 10: Group-wise errors (for $n=25,p=q=1$) for $g-0$ (majority group) and
$g-1$ (minority group), for the synthetic datasets (for $\phi_{h}=1$). Figure
11: Group-wise errors (for $n=25$, $p=q=1$) for the synthetic datasets with
$\phi_{h}=n_{h}$. Figure 12: Group-wise errors (for $n=25,p=q=1$) for $g-0$
(majority group) and $g-1$ (minority group), for the synthetic datasets (for
$\phi_{h}=n_{h}$).