# A noise-limiting quantum algorithm using mid-circuit measurements
for dynamical correlations at infinite temperature

Etienne Granet and Henrik Dreyer  Quantinuum, Leopoldstrasse 180, 80804
Munich, Germany

###### Abstract

It is generally considered that the signal output by a quantum circuit is
attenuated exponentially fast in the number of gates. This letter explores how
algorithms using mid-circuit measurements and classical conditioning as
_computational tools_ (and not as error mitigation or correction subroutines)
can be naturally resilient to complete decoherence, and maintain quantum
states with useful properties even for infinitely deep noisy circuits.
Specifically, we introduce a quantum channel built out of mid-circuit
measurements and feed-forward, that can be used to compute dynamical
correlations at infinite temperature and canonical ensemble expectation values
for any Hamiltonian. The unusual property of this algorithm is that in the
presence of a depolarizing channel it still displays a meaningful, non-zero
signal in the large depth limit. We showcase the noise resilience of this
quantum channel on Quantinuum’s H1-1 ion-trap quantum computer.

_Introduction._ — The main obstacle to large-scale quantum computing is the
imperfect realization of quantum operations Preskill (2018); Knill (2005). In
the presence of noise, the signal output by a quantum circuit is generically
exponentially attenuated with the number of gates Emerson  _et al._ (2005);
Moses  _et al._ (2023); Mayer  _et al._ (2021); Proctor  _et al._ (2022);
Baldwin  _et al._ (2022), causing exponential overheads which threaten the
prospects of the utility of quantum computers. Quantum error correcting codes
are particular circuits fundamentally relying on mid-circuit measurements and
classical conditioning on the measurement outcomes (also called _feed-
forward_) that delay this complete depolarizing for very deep circuits Shor
(1995); Knill  _et al._ (1998); Calderbank and Shor (1996); Steane (1996);
Kitaev (2003); Nielsen and Chuang (2010). However, these circuits only serve
as subroutines within unitary circuits and do not perform a computational task
themselves. The purpose of this work is to investigate whether algorithms that
use mid-circuit measurements and feed-forward directly as computational tools
(rather than error correcting subroutines) are naturally _noise-resilient_ in
the sense that in the limit of an infinitely deep circuit there remains a non-
zero signal that contains information on the task fulfilled by the algorithm.

In this Letter, we answer this question in the affirmative. Specifically, we
introduce a simple “shuffling” quantum channel based on mid-circuit
measurements and feed-forward that outputs a non-zero signal when repeated an
arbitrary number of times, even in the presence of noise. Crucially, this non-
zero signal also carries non-trivial, physically interesting information: We
show that this quantum channel can be used to compute finite temperature
expectation values for any Hamiltonian $H$, as well as dynamical correlations
at infinite temperature ${\rm tr}\,[Se^{iHt}Se^{-iHt}]$ where $S$ is any Pauli
string. We also show that it can prepare certain density matrices in a noise-
resilient way as fixed points of a quantum channel.

The use of mid-circuit measurements to perform non-unitary operations is well
known, for example as a means of post-selecting particular measurement
outcomes Kitaev (1995); Harrow  _et al._ (2009); Childs and Wiebe (2012);
Berry  _et al._ (2015a, b); Ge  _et al._ (2019); Schlimgen  _et al._ (2022);
Lee  _et al._ (2020); Choi  _et al._ (2021); Aaronson (2005), to prepare
specific, analytically tractable quantum states more efficiently Iqbal  _et
al._ (2023a); Tantivasadakarn  _et al._ (2022, 2021, 2023); Foss-Feig  _et
al._ (2023); Iqbal  _et al._ (2023b), or on top of another algorithm to
mitigate the effect of noise McArdle  _et al._ (2019); Botelho  _et al._
(2022); Bonet-Monroig  _et al._ (2018). Some algorithms use a weak form of
feed-forward where measurement outcomes are used as a stopping criterion or to
partially reset the state Cubitt (2023); Verstraete  _et al._ (2009); Kraus
_et al._ (2008); Xu  _et al._ (2014); DeCross  _et al._ (2022); Haghshenas
_et al._ (2023). The novelty in the present approach is the use of mid-circuit
measurement and feed-forward as _computational_ primitives to obtain non-
trivial physical properties which, as we will show, endows the computation
with a natural noise-limiting property. This noise-limiting behaviour is
demonstrated analytically with specific noise models, numerically with noisy
simulations, and experimentally on Quantinuum ion-trap quantum computers.

_The shuffling quantum channel._ — Let us start with introducing the main
quantum channel that we will study in this Letter. The effect of the channel
on expectation values is given by Eq (2) below, and we will show that it can
be used to compute dynamical correlations at infinite temperature. As we will
explain, the surprising property of this channel is that when repeated several
times in the presence of noise, it still outputs meaningful non-zero signal.

For a generic Hamiltonian $H$ on $L$ qubits, we define the quantum channel
Shuffle$(H)$ by the three following steps.

  1. 1.

Pick a Pauli matrix at each site, i.e. $M_{1},...,M_{L}\in\\{I,X,Y,Z\\}$
uniformly at random.

  2. 2.

Prepare an ancilla in state $|0\rangle_{a}$. On the $L$ qubits and the
ancilla, apply $e^{iH_{M_{1}...M_{L}}X_{a}}$ where we defined

$H_{M_{1}...M_{L}}=M_{1}...M_{L}HM_{L}...M_{1}\,.$ (1)

  3. 3.

Measure the ancilla. Only if the measurement outcome is $0$, apply
$M_{1}...M_{L}$ on the $L$ qubits.

Let us denote $\rho$ the initial density matrix of the $L$ qubits, and
$\rho^{\prime}$ the new density matrix after running Shuffle$(H)$. We are
going to show that for any Pauli string operator
$S=M^{\prime}_{1}...M^{\prime}_{L}$ with $M^{\prime}_{i}\in\\{I,X,Y,Z\\}$, we
have

${\rm tr}\,[S\rho^{\prime}]=A{\rm tr}\,[S\rho]+B\,,$ (2)

with

$A=\frac{{\rm tr}\,[S\sin(H)S\sin(H)]}{2^{L}}\,,\qquad B=\frac{{\rm
tr}\,[S\cos^{2}(H)]}{2^{L}}\,.$ (3)

Moreover, the probability $p$ of measuring $0$ in the ancilla is

$p=\frac{{\rm tr}\,[\cos^{2}(H)]}{2^{L}}\,.$ (4)

_Proof._ — From step (1), we fix some Pauli matrices at each site
$M_{1},...,M_{L}\in\\{I,X,Y,Z\\}$. We will denote
$\boldsymbol{M}=M_{1}...M_{L}$ and $\mathcal{M}$ the set of all the $4^{L}$
Pauli strings. The operator $U=e^{iH_{\boldsymbol{M}}X_{a}}$ is diagonal in
the eigenbasis of $H_{\boldsymbol{M}}$, with matrix elements $U_{n}$ that are
operators on the ancilla and that read

$U_{n}=\left(\begin{matrix}\cos E_{n}&i\sin E_{n}\\\ i\sin E_{n}&\cos
E_{n}\end{matrix}\right)\,,$ (5)

with $E_{n}$ the corresponding eigenvalue of $H_{\boldsymbol{M}}$. By
preparing the ancilla in the state $|0\rangle$, applying $U$ and measuring the
ancilla, we act on the $L$ qubits with the operator $\langle
0|U|0\rangle=\cos(H_{\boldsymbol{M}})$ if we measure $0$, and with $\langle
1|U|0\rangle=i\sin(H_{\boldsymbol{M}})$ if we measure $1$. It follows that the
density matrix $\rho^{\prime}_{\boldsymbol{M}}$ that we obtain after the steps
(2) and (3), assuming $M_{1},...,M_{L}$ have been picked at step (1), is

$\displaystyle\rho^{\prime}_{\boldsymbol{M}}$
$\displaystyle=\sin(H_{\boldsymbol{M}})\rho\sin(H_{\boldsymbol{M}})+\boldsymbol{M}\cos(H_{\boldsymbol{M}})\rho\cos(H_{\boldsymbol{M}})\boldsymbol{M}$
(6)
$\displaystyle=\sin(H_{\boldsymbol{M}})\rho\sin(H_{\boldsymbol{M}})+\cos(H)\boldsymbol{M}\rho\boldsymbol{M}\cos(H)\,.$

Taking into account all the $4^{L}$ possibilities of $M_{1},...,M_{L}$ at step
(1), the density matrix $\rho^{\prime}$ after one run of Shuffle$(H)$ is the
sum of all the $\rho^{\prime}_{\boldsymbol{M}}$’s divided by $4^{L}$. We now
note that on the second term of $\rho^{\prime}_{\boldsymbol{M}}$, this sum
precisely implements a completely depolarizing channel Nielsen and Chuang
(2010). Namely, for any density matrix $\rho$ we have

$\frac{1}{4^{L}}\sum_{\boldsymbol{M}\in\mathcal{M}}\boldsymbol{M}\rho\boldsymbol{M}=\frac{1}{2^{L}}\,.$
(7)

It follows

$\displaystyle\rho^{\prime}=$
$\displaystyle\frac{1}{4^{L}}\sum_{\begin{subarray}{c}\boldsymbol{M}\in\mathcal{M}\end{subarray}}\sin(H_{\boldsymbol{M}})\rho\sin(H_{\boldsymbol{M}})+\frac{\cos^{2}(H)}{2^{L}}\,.$
(8)

We note that the feed-forward in step (3) is crucial to obtain a non-trivial
density matrix. Had we always applied $\boldsymbol{M}$ on the qubits
independently of the measurement outcome of step (3), the density matrix
$\rho^{\prime}$ would have been the completely depolarized state $1/2^{L}$.

Let us now consider a given Pauli string operator
$\boldsymbol{M^{\prime}}\in\mathcal{M}$, and denote the expectation values

$m={\rm tr}\,[\boldsymbol{M^{\prime}}\rho]\,,\qquad m^{\prime}={\rm
tr}\,[\boldsymbol{M^{\prime}}\rho^{\prime}]\,.$ (9)

Multiplying (8) by $\boldsymbol{M^{\prime}}$ and taking the trace, we make
appear in the sum the terms ${\rm
tr}\,[\boldsymbol{M^{\prime}}\sin(H_{\boldsymbol{M}})\rho\sin(H_{\boldsymbol{M}})]$.
Decomposing $\rho$ in the basis of Pauli strings

$\rho=\sum_{\boldsymbol{M^{\prime\prime}}\in\mathcal{M}}c_{\boldsymbol{M^{\prime\prime}}}\boldsymbol{M^{\prime\prime}}\,,$
(10)

we write

$\displaystyle{\rm
tr}\,[\boldsymbol{M^{\prime}}\sin(H_{\boldsymbol{M}})\rho\sin(H_{\boldsymbol{M}})]$
(11)
$\displaystyle=\sum_{\boldsymbol{M^{\prime\prime}}\in\mathcal{M}}c_{\boldsymbol{M^{\prime\prime}}}{\rm
tr}\,[\boldsymbol{M}\boldsymbol{M^{\prime}}\boldsymbol{M}\sin(H)\boldsymbol{M}\boldsymbol{M^{\prime\prime}}\boldsymbol{M}\sin(H)]\,.$

Let us perform first the sum over $M_{i}\in\\{I,X,Y,Z\\}$ appearing in (8). We
note that $M_{i}M_{i}^{\prime}M_{i}$ is either $M_{i}^{\prime}$ (if $M_{i}=I$,
or $M_{i}^{\prime}=I$, or $M_{i}=M_{i}^{\prime}$), or $-M_{i}^{\prime}$ (in
the remaining cases). If $M_{i}^{\prime}\neq M_{i}^{\prime\prime}$, then at
least one of the two is not $I$, say $M_{i}^{\prime}\neq I$. If
$M_{i}^{\prime\prime}=I$, then one sees that one gets an amplitude ${\rm
tr}\,[\boldsymbol{M^{\prime}}\sin(H)\boldsymbol{M^{\prime\prime}}\sin(H)]$
with a $+$ sign when $M_{i}=I$ and $M_{i}=M_{i}^{\prime}$, and with a $-$ sign
in the two remaining cases. Hence this term vanishes once summed over $M_{i}$.
If $M_{i}^{\prime}=I$ and $M^{\prime\prime}_{i}\neq I$, the same reasoning
applies. If both $M^{\prime}_{i},M_{i}^{\prime\prime}\neq I$, one sees that
one gets a $+$ sign when $M_{i}=I$ and $M_{i}\neq
M_{i}^{\prime},M_{i}^{\prime\prime}$, and a $-$ sign in the two remaining
cases. Hence this term also vanishes once summed over $M_{i}$. It follows that
once we sum over all the $M_{i}$, only the terms where
$M_{i}^{\prime}=M_{i}^{\prime\prime}$ give a non-zero contribution. This
yields

$\displaystyle\sum_{\begin{subarray}{c}\boldsymbol{M}\in\mathcal{M}\end{subarray}}{\rm
tr}\,[\boldsymbol{M}\boldsymbol{M^{\prime}}\boldsymbol{M}\sin(H)\boldsymbol{M}\boldsymbol{M^{\prime\prime}}\boldsymbol{M}\sin(H)]$
(12) $\displaystyle=4^{L}{\rm
tr}\,[\boldsymbol{M^{\prime}}\sin(H)\boldsymbol{M^{\prime\prime}}\sin(H)]\prod_{i=1}^{L}\delta_{M_{i}^{\prime},M_{i}^{\prime\prime}}\,.$

Noting that we have $m=c_{\boldsymbol{M^{\prime}}}2^{L}$, we obtain thus

$\displaystyle m^{\prime}=$ $\displaystyle m\frac{{\rm
tr}\,[\boldsymbol{M^{\prime}}\sin(H)\boldsymbol{M^{\prime}}\sin(H)]}{2^{L}}+\frac{{\rm
tr}\,[\boldsymbol{M^{\prime}}\cos^{2}(H)]}{2^{L}}\,,$ (13)

which is precisely (2). To compute the probability $p$ of measuring $0$ in the
ancilla, we note that if $M_{1},...,M_{L}$ has been picked at step (1), then
this probability $p_{\boldsymbol{M}}$ is

$p_{\boldsymbol{M}}={\rm tr}\,[\rho\cos^{2}(H_{\boldsymbol{M}})]\,.$ (14)

Summing over $M_{1},...,M_{L}$, this yields

$\displaystyle p=$ $\displaystyle\frac{{\rm
tr}\,[\cos^{2}(H)]}{4^{L}}\times\sum_{\begin{subarray}{c}\boldsymbol{M}\in\mathcal{M}\end{subarray}}{\rm
tr}\,[\rho\boldsymbol{M}\frac{\cos^{2}(H)}{{\rm
tr}\,[\cos^{2}(H)]}\boldsymbol{M}]\,.$ (15)

Using in this equation the relation (7) for the density matrix
$\frac{\cos^{2}(H)}{{\rm tr}\,[\cos^{2}(H)]}$ we obtain (4) indeed.

_Dynamical correlations at infinite temperature._ — Let us show how the
shuffling quantum channel can be used to compute dynamical correlations of
Pauli strings $S=M_{1}...M_{L}$ at infinite temperature, defined as

$C_{S}(t)=\frac{{\rm tr}\,[e^{-iHt}Se^{iHt}S]}{2^{L}}\,.$ (16)

These quantities are relevant for transport properties and have attracted
particular interest recently Rosenberg  _et al._ (2023); Gopalakrishnan  _et
al._ (2019); De Nardis  _et al._ (2020); Kanász-Nagy  _et al._ (2017); Scheie
_et al._ (2021); Granet and Essler (2020); Granet  _et al._ (2022); Rakovszky
_et al._ (2022); Žnidarič (2011); Dupont and Moore (2020); Parker  _et al._
(2019). To compute this quantity with the shuffling quantum channel, we write

$C_{S}(t)=\frac{{\rm tr}\,[S\cos(Ht)S\cos(Ht)]}{2^{L}}+\frac{{\rm
tr}\,[S\sin(Ht)S\sin(Ht)]}{2^{L}}\,.$ (17)

Let us consider $\rho$ an arbitrary initial density matrix for which we know
${\rm tr}\,[\rho S]$. We then apply on $\rho$ either Shuffle$(Ht)$ with
probability $1/2$, or Shuffle$(Ht+\tfrac{\pi}{2})$ with probability $1/2$. We
measure the Pauli string $S$ and denote ${\rm tr}\,[\rho^{\prime}S]$ the
average outcome. Using formula (2), we have thus

${\rm tr}\,[\rho^{\prime}S]=\frac{A_{0}+A_{\pi/2}}{2}{\rm tr}\,[\rho
S]+\frac{B_{0}+B_{\pi/2}}{2}\,,$ (18)

with $A_{x},B_{x}$ the coefficients (3) corresponding to the Hamiltonian
$Ht+x$. From (3) we find thus for $S\neq I$

${\rm tr}\,[\rho^{\prime}S]=\frac{C_{S}(t){\rm tr}\,[\rho S]}{2}\,.$ (19)

Hence, one can directly compute the value of $C_{S}(t)$ provided we chose
$\rho$ such that ${\rm tr}\,[\rho S]\neq 0$. We note there are other similar
ways of extracting $C_{S}(t)$ from this quantum channel sup .

This algorithm for dynamical correlations at infinite temperature presents
advantages compared to previously existing techniques. Computing the trace
over the Hilbert space through a purification requires to double the number of
qubits, whereas here there is only one ancilla qubit overhead. Implementing
the trace through a Haar random state preparation Summer  _et al._ (2023) has
a gate overhead to prepare the Haar random state, and also a shot overhead
because it computes the square of the dynamical correlations and can only
treat one site at a time, which increases considerably the variance. Finally,
for $S$ single Pauli matrices, evaluating the trace as a sum over product
states in the basis of $S$ can have a large statistical sampling overhead if
dynamical correlations are small in this basis, whereas our algorithm is
basis-independent.

_Mixed state preparation._ — The density matrix constructed previously in (19)
contains information about the physics of the system through $C_{S}(t)$, but
also on the initial density matrix through ${\rm tr}\,[\rho S]$. This can be
problematic for strings $S$ involving different Pauli matrices at different
sites, since the preparation of $\rho$ such that ${\rm tr}\,[\rho S]\neq 0$
for multiple such $S$ would become non-trivial.

The shuffling quantum channel through the relation (2) actually enables one to
prepare non-trivial density matrices independently of the initial density
matrix. Let us repeat $n$ times the channel Shuffle$(H)$ on an initial density
matrix $\rho_{0}$, denoting $\rho_{n}$ the resulting density matrix. Eq (2)
yields a geometric series for any string $S$

${\rm tr}\,[S\rho_{n}]=A^{n}{\rm tr}\,[S\rho_{0}]+\frac{1-A^{n}}{1-A}B\,,$
(20)

with $A,B$ given in (3). In particular, since $|A|<1$ (except for very
specific choices of $H,S$ where we would have $|A|=1$) when $n\to\infty$ we
obtain

$\underset{n\to\infty}{\lim}\,{\rm tr}\,[S\rho_{n}]=\frac{B}{1-A}\,,$ (21)

which does not depend on the initial density matrix. Moreover the convergence
is exponentially fast in $n$ with rate $\log 1/|A|$. We thus prepare a non-
trivial density matrix whose expectation values contain physical information
about the system studied.

_Noise-limiting behaviour: analytics._ — We now argue that the algorithms
based on the repetition of the shuffling quantum channel are to some extent
resilient to noise. Let us consider a noise model where a global depolarizing
channel with amplitude $\lambda$ is applied on the $L$ qubits every time we
apply the Shuffle$(H)$ channel. This depolarizing channel transforms a density
matrix $\rho$ into

$\rho\mapsto(1-\lambda)\rho+\frac{\lambda}{2^{L}}\,.$ (22)

Hence, using (2), the (noisy) density matrix $\rho^{\prime}_{\rm noisy}$ that
describes the $L$ qubits after one round of Shuffle$(H)$ and one global
depolarizing channel satisfies for $S\neq I$

${\rm tr}\,[S\rho^{\prime}_{\rm noisy}]=(1-\lambda)(A{\rm tr}\,[S\rho]+B)\,.$
(23)

Denoting $\rho_{{\rm noisy},n}$ the density matrix obtained after $n$ noisy
applications of Shuffle$(H)$, the limiting value reached in the limit of an
infinite number of applications is

$\underset{n\to\infty}{\lim}{\rm tr}\,[S\rho_{{\rm
noisy},n}]=\frac{(1-\lambda)B}{1-(1-\lambda)A}\,,$ (24)

which is _finite_ , even if an infinite number of gates and noise channels
have been applied. One notes that none of the $L$ qubits are ever measured or
re-initialized. This shows the noise resilience of the preparation of density
matrices through the shuffling quantum channel.

Let us explain why this noise-limiting behaviour is directly related to the
use of mid-circuit measurements and feed-forward. A circuit involving only
unitary operations and measurements without feed-forward can always be written
as the composition of density matrix maps $T(\rho)=U\rho U^{\dagger}$ with $U$
unitary or $T(\rho)=\sum_{m}P_{m}\rho P_{m}^{\dagger}$ with
$\sum_{m}P_{m}P_{m}^{\dagger}={\rm Id}$. These maps both satisfy $T({\rm
Id})={\rm Id}$ (also called “unital” maps), so the completely mixed state
$\frac{{\rm Id}}{2^{L}}$ is always a fixed point of such circuits. However,
with feed-forward these density matrix maps are in general
$T(\rho)=\sum_{m}U_{m}P_{m}\rho P_{m}^{\dagger}U_{m}^{\dagger}$ with $U_{m}$
unitary, for which the identity is (generically) not a fixed point. This
prevents thus the completely depolarized state to be reached in the limit of
large number of gates.

This explanation yields the following nice interpretation of the noise
resilience of our algorithm. The resulting density matrix after a large number
of rounds converges to the fixed point of the quantum channel. Because of the
presence of mid-circuit measurements and feed-forward, this fixed point cannot
be (in general) the completely depolarized channel. Now, incorporating noise
in the process (under any form) will only smoothly change the quantum channel,
and so only smoothly change the fixed point, instead of sending it to the
completely depolarized state. The noise-resilience of the prepared density
matrix is thus built into the algorithm itself.

Figure 1: _Noise-limiting property of the shuffling quantum channel_.
Expectation value $ZZ\equiv\frac{1}{L}\sum_{i=1}^{L}\langle
Z_{i}Z_{i+1}\rangle$ as a function of the number $n$ of calls to Shuffle$(H)$,
with $H$ given by (25), and using $5$ Trotter steps to implement $e^{iH}$.
There are $1000$ shots per circuit for simulations, and $500$ shots per
circuit for hardware. The errors bars indicate $\pm$ one standard deviation.
After compilation, there are $185n$ two-qubit gates and $782n$ one-qubit gates
as a function of $n$. Figure 2: _Dynamical correlations at infinite
temperature_. Expectation values ${\rm tr}\,[Z_{1}(0)Z_{1}(t)]/2^{L}$ (left
panel) and ${\rm tr}\,[X_{1}(0)X_{1}(t)]/2^{L}$ (right panel) computed with
the shuffling quantum channel with the technique described in the Supplemental
Material (SM) sup , as a function of $t$, with $G(t)=e^{iHt}Ge^{-itH}$ where
$H=H_{\rm Ising}$ on $L=8$ sites: noiseless simulations (teal), noisy emulator
H1 series (orange) and exact value (black, continuous line). We use Trotter
steps $dt=0.1$ to implement the time evolution. There are $1000$ shots per
circuit. No noise mitigation technique is used.

_Noise-limiting behaviour: experiments and simulations._ — We now present
numerical and experimental evidence of the noise resilience of our algorithm.
We consider the 1D Ising model in a transverse field $h=1$ and $t=0.1$ on
$L=8$ sites with periodic boundary conditions

$H=\frac{\pi}{3}+tH_{\rm Ising}\,,\quad H_{\rm
Ising}=-\sum_{j=1}^{L}Z_{j}Z_{j+1}-h\sum_{j=1}^{L}X_{j}\,.$ (25)

We first focus on the shuffling quantum channel Shuffle$(H)$. We initialize
the $L$ qubits in $|0\rangle$ and measure
$\frac{1}{L}\sum_{i=1}^{L}Z_{i}Z_{i+1}$ after $n$ rounds of Shuffle$(H)$. We
chose this observable as $\frac{1}{L}\sum_{i=1}^{L}X_{i}$ or
$\frac{1}{L}\sum_{i=1}^{L}Z_{i}$ would have a zero expectation value at either
small or large number of rounds. We report in Fig 1 the results of noiseless
simulations, noisy simulations with the H1 emulator, and actual hardware
implementation with the H1-1 machine of Quantinuum for number of rounds $n=1$
($185$ two-qubit gates and $782$ one-qubit gates) and $n=10$ ($1850$ two-qubit
gates and $7820$ one-qubit gates). It is known that noise on quantum computers
can be well accounted for, in a first approximation, by attenuating the signal
with a factor equal to the product of the fidelities of the gates entering the
circuit. We evaluate the effect of the noise by measuring the signal after one
round $n=1$ on the emulator with a large number of shots, and comparing it to
the exact value. From this, we obtain an attenuation per round $1-\lambda$. We
plot then in Fig 1 the effect of the noise assuming it can be modelled by an
attenuation factor $(1-\lambda)^{n}$ at round $n$ times the exact result,
which is labelled by “standard noise model”.

We observe that the results from the hardware agree very well with the
emulator data. In particular the measured value at $n=10$ is incompatible with
the standard noise model by around $3$ standard deviations. If we used the
hardware data at $n=1$ to calibrate the standard noise model instead of the
emulator data, the incompatibility would be even larger.

Secondly, in Fig 2 we implement our algorithm for dynamical correlations at
infinite temperature, comparing the exact values, the noiseless simulations
and the results of the Quantinuum hardware emulator, without doing any noise
mitigation. This emulator implements in particular a two-qubit gate fidelity
of around $0.998$. We observe that the noisy values agree very well with the
noiseless, despite the circuits containing several hundreds of two-qubit
gates, showing a noise-resilience.

_Canonical ensemble expectation values._ — Finally, we show that using a
shuffling quantum channel with multiple ancillas, one can compute expectation
values at finite temperature. Although this application is not of practical
interest (as we will show, it is exponential in system size runtime), it shows
the versatility of our channel in extracting physical information about a
system. Let us consider a Hamiltonian $H$ on $L$ qubits, an observable $O$ and
an inverse temperature $\beta$. We define

$H^{\prime}=\arctan\theta+\frac{\beta H-\epsilon Z_{v}O}{2\theta N}\,,$ (26)

on the system of $L$ qubits plus one “virtual” qubit $v$, where $Z_{v}$
denotes the Pauli matrix $Z$ applied on the virtual qubit $v$, and where we
introduced parameters $\epsilon>0$ and $\theta>0$, as well as an integer $N$.
As shown in the SM sup , the shuffling quantum channel can be generalized into
a channel Shuffle$(H,N)$ that uses $N$ ancillas as follows: one applies step
(2) to each of the $N$ ancillas, and then in step (3) one applies
$M_{1}...M_{L}$ on the $L$ qubits only if _all_ the $N$ ancillas have been
measured to be in state $0$. An identical relation to (2) follows then with
precise coefficients $A$ and $B$ sup . In the particular case of $H^{\prime}$
in (26), because $Z_{v}$ commutes with $H^{\prime}$, we have

${\rm tr}\,[\rho^{\prime}Z_{v}]=A{\rm tr}\,[\rho Z_{v}]+B\,,$ (27)

with

$A=1-\frac{{\rm Tr}\,[\cos^{2N}(H^{\prime})]}{2^{L+1}}\,,\quad B=\frac{{\rm
Tr}\,[Z_{v}\cos^{2N}(H^{\prime})]}{2^{L+1}}\,,$ (28)

where ${\rm Tr}\,$ denotes the trace on the $L$ qubits and the virtual ancilla
$v$. Hence, by repeating this generalized channel we obtain

$\underset{n\to\infty}{\lim}{\rm Tr}\,[Z_{v}\rho_{n}]=\frac{{\rm
Tr}\,[Z_{v}\cos^{2N}(H^{\prime})]}{{\rm Tr}\,[\cos^{2N}(H^{\prime})]}\,.$ (29)

This prepares the virtual qubit in an ensemble that is close to a canonical
ensemble. Indeed, for $N$ larger than the norm of $\beta H/\theta$, we have Lu
_et al._ (2021)

$\cos^{2N}(H^{\prime})\sim\frac{e^{-\beta H+\epsilon
Z_{v}O}}{(1+\theta^{2})^{N}}\,.$ (30)

Hence, performing the trace over the virtual qubit $v$ we obtain in this
regime

$\underset{n\to\infty}{\lim}{\rm Tr}\,[Z_{v}\rho_{n}]=\epsilon\frac{{\rm
tr}\,[Oe^{-\beta H}]}{{\rm tr}\,[e^{-\beta
H}]}+\mathcal{O}(\epsilon^{2},\tfrac{\beta||H||}{N\theta})\,,$ (31)

where we now use ${\rm tr}\,$ to denote the trace over the $L$ qubits, without
the virtual qubit $v$. Interestingly, the algorithm automatically computes the
_ratio_ of traces ${\rm tr}\,[Oe^{-\beta H}]/2^{L}$ and ${\rm tr}\,[e^{-\beta
H}]/2^{L}$ that can each of them be exponentially small. Using (28) and (30),
the number of rounds $n$ required to reach this limit is $1/\log(1-\frac{{\rm
tr}\,[e^{-\beta H}]}{2^{L}(1+\theta^{2})^{N}})$. The time complexity is thus
exponential in the system size $L$, which is the expected scaling for a
finite-temperature algorithm that applies to generic Hamiltonians.

_Discussion._ — In this Letter we have provided a first example of how non-
error-corrected algorithms can avoid total depolarisation in the infinite-
depth limit. This proof of principle opens up a number of possible future
directions. For example, the algorithms presented here for finite temperature
expectation values have an exponential time complexity, which is unavoidable
without further assumption on $H$. It would be very valuable to investigate
whether these features can be improved for local Hamiltonians $H$.

We acknowledge helpful discussions with Eli Chertkov, Matthew DeCross, Kevin
Hemery, Michael Foss-Feig, Ramil Nigmatullin, Reza Hagshenas and Charlie
Baldwin. E.G. acknowledges support by the Bavarian Ministry of Economic
Affairs, Regional Development and Energy (StMWi) under project Bench-QC
(DIK0425/01). The emulator data in this work was produced in June-July 2023.
The experimental data in this work was produced by the Quantinuum H1-1 trapped
ion quantum computer, Powered by Honeywell, in July 2023.

## References

  * Preskill (2018) J. Preskill, Quantum 2, 79 (2018).
  * Knill (2005) E. Knill, Nature 434, 39 (2005).
  * Emerson  _et al._ (2005) J. Emerson, R. Alicki, and K. Życzkowski, Journal of Optics B: Quantum and Semiclassical Optics 7, S347 (2005).
  * Moses  _et al._ (2023) S. Moses, C. Baldwin, M. Allman, R. Ancona, L. Ascarrunz, C. Barnes, J. Bartolotta, B. Bjork, P. Blanchard, M. Bohn, _et al._ , arXiv preprint arXiv:2305.03828 (2023), 10.48550/arXiv.2305.03828.
  * Mayer  _et al._ (2021) K. Mayer, A. Hall, T. Gatterman, S. K. Halit, K. Lee, J. Bohnet, D. Gresh, A. Hankin, K. Gilmore, and J. Gaebler, arXiv preprint arXiv:2108.10431 (2021), 10.48550/arXiv.2108.10431.
  * Proctor  _et al._ (2022) T. Proctor, K. Rudinger, K. Young, E. Nielsen, and R. Blume-Kohout, Nature Physics 18, 75 (2022).
  * Baldwin  _et al._ (2022) C. H. Baldwin, K. Mayer, N. C. Brown, C. Ryan-Anderson, and D. Hayes, Quantum 6, 707 (2022).
  * Shor (1995) P. W. Shor, Physical review A 52, R2493 (1995).
  * Knill  _et al._ (1998) E. Knill, R. Laflamme, and W. H. Zurek, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 365 (1998).
  * Calderbank and Shor (1996) A. R. Calderbank and P. W. Shor, Physical Review A 54, 1098 (1996).
  * Steane (1996) A. M. Steane, Physical Review Letters 77, 793 (1996).
  * Kitaev (2003) A. Y. Kitaev, Annals of physics 303, 2 (2003).
  * Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang,  _Quantum computation and quantum information_ (Cambridge university press, 2010).
  * Kitaev (1995) A. Y. Kitaev, arXiv preprint quant-ph/9511026 (1995), 10.48550/arXiv.quant-ph/9511026.
  * Harrow  _et al._ (2009) A. W. Harrow, A. Hassidim, and S. Lloyd, Physical review letters 103, 150502 (2009).
  * Childs and Wiebe (2012) A. M. Childs and N. Wiebe, arXiv preprint arXiv:1202.5822 (2012), 10.26421/QIC12.11-12.
  * Berry  _et al._ (2015a) D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Physical review letters 114, 090502 (2015a).
  * Berry  _et al._ (2015b) D. W. Berry, A. M. Childs, and R. Kothari, in  _2015 IEEE 56th annual symposium on foundations of computer science_ (IEEE, 2015) pp. 792–809.
  * Ge  _et al._ (2019) Y. Ge, J. Tura, and J. I. Cirac, Journal of Mathematical Physics 60 (2019), 10.1063/1.5027484.
  * Schlimgen  _et al._ (2022) A. W. Schlimgen, K. Head-Marsden, L. M. Sager-Smith, P. Narang, and D. A. Mazziotti, Physical Review A 106, 022414 (2022).
  * Lee  _et al._ (2020) D. Lee, J. Bonitati, G. Given, C. Hicks, N. Li, B.-N. Lu, A. Rai, A. Sarkar, and J. Watkins, Physics Letters B 807, 135536 (2020).
  * Choi  _et al._ (2021) K. Choi, D. Lee, J. Bonitati, Z. Qian, and J. Watkins, Physical Review Letters 127, 040505 (2021).
  * Aaronson (2005) S. Aaronson, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 461, 3473 (2005).
  * Iqbal  _et al._ (2023a) M. Iqbal, N. Tantivasadakarn, R. Verresen, S. L. Campbell, J. M. Dreiling, C. Figgatt, J. P. Gaebler, J. Johansen, M. Mills, S. A. Moses, _et al._ , arXiv preprint arXiv:2305.03766 (2023a), 10.48550/arXiv.2305.03766.
  * Tantivasadakarn  _et al._ (2022) N. Tantivasadakarn, R. Verresen, and A. Vishwanath, arXiv preprint arXiv:2209.03964 (2022), 10.48550/arXiv.2209.03964.
  * Tantivasadakarn  _et al._ (2021) N. Tantivasadakarn, R. Thorngren, A. Vishwanath, and R. Verresen, arXiv preprint arXiv:2112.01519 (2021), 10.48550/arXiv.2112.01519.
  * Tantivasadakarn  _et al._ (2023) N. Tantivasadakarn, A. Vishwanath, and R. Verresen, PRX Quantum 4, 020339 (2023).
  * Foss-Feig  _et al._ (2023) M. Foss-Feig, A. Tikku, T.-C. Lu, K. Mayer, M. Iqbal, T. M. Gatterman, D. Gresh, A. Hankin, N. Hewitt, C. V. Horst, _et al._ , arXiv preprint arXiv:2302.03029 (2023), 10.48550/arXiv.2302.03029.
  * Iqbal  _et al._ (2023b) M. Iqbal, N. Tantivasadakarn, T. M. Gatterman, K. Gilmore, D. Gresh, A. Hankin, N. Hewitt, C. V. Horst, M. Matheny, T. Mengle, _et al._ , arXiv preprint arXiv:2302.01917 (2023b), 10.48550/arXiv.2302.01917.
  * McArdle  _et al._ (2019) S. McArdle, X. Yuan, and S. Benjamin, Physical review letters 122, 180501 (2019).
  * Botelho  _et al._ (2022) L. Botelho, A. Glos, A. Kundu, J. A. Miszczak, Ö. Salehi, and Z. Zimborás, Physical Review A 105, 022441 (2022).
  * Bonet-Monroig  _et al._ (2018) X. Bonet-Monroig, R. Sagastizabal, M. Singh, and T. O’Brien, Physical Review A 98, 062339 (2018).
  * Cubitt (2023) T. S. Cubitt, arXiv preprint arXiv:2303.11962 (2023), 10.48550/arXiv.2303.11962.
  * Verstraete  _et al._ (2009) F. Verstraete, M. M. Wolf, and J. Ignacio Cirac, Nature physics 5, 633 (2009).
  * Kraus  _et al._ (2008) B. Kraus, H. P. Büchler, S. Diehl, A. Kantian, A. Micheli, and P. Zoller, Physical Review A 78, 042307 (2008).
  * Xu  _et al._ (2014) J.-S. Xu, M.-H. Yung, X.-Y. Xu, S. Boixo, Z.-W. Zhou, C.-F. Li, A. Aspuru-Guzik, and G.-C. Guo, Nature Photonics 8, 113 (2014).
  * DeCross  _et al._ (2022) M. DeCross, E. Chertkov, M. Kohagen, and M. Foss-Feig, arXiv preprint arXiv:2210.08039 (2022), 10.48550/arXiv.2210.08039.
  * Haghshenas  _et al._ (2023) R. Haghshenas, E. Chertkov, M. DeCross, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V. Horst, M. Matheny, _et al._ , arXiv preprint arXiv:2305.01650 (2023), 10.48550/arXiv.2305.01650.
  * Rosenberg  _et al._ (2023) E. Rosenberg, T. Andersen, R. Samajdar, A. Petukhov, J. Hoke, D. Abanin, A. Bengtsson, I. Drozdov, C. Erickson, P. Klimov, _et al._ , arXiv preprint arXiv:2306.09333 (2023), 10.48550/arXiv.2306.09333.
  * Gopalakrishnan  _et al._ (2019) S. Gopalakrishnan, R. Vasseur, and B. Ware, Proceedings of the National Academy of Sciences 116, 16250 (2019).
  * De Nardis  _et al._ (2020) J. De Nardis, S. Gopalakrishnan, E. Ilievski, and R. Vasseur, Physical review letters 125, 070601 (2020).
  * Kanász-Nagy  _et al._ (2017) M. Kanász-Nagy, I. Lovas, F. Grusdt, D. Greif, M. Greiner, and E. A. Demler, Physical Review B 96, 014303 (2017).
  * Scheie  _et al._ (2021) A. Scheie, N. Sherman, M. Dupont, S. Nagler, M. Stone, G. Granroth, J. Moore, and D. Tennant, Nature Physics 17, 726 (2021).
  * Granet and Essler (2020) E. Granet and F. Essler, SciPost Physics 9, 082 (2020).
  * Granet  _et al._ (2022) E. Granet, H. Dreyer, and F. Essler, SciPost Physics 12, 019 (2022).
  * Rakovszky  _et al._ (2022) T. Rakovszky, C. von Keyserlingk, and F. Pollmann, Physical Review B 105, 075131 (2022).
  * Žnidarič (2011) M. Žnidarič, Physical Review Letters 106, 220601 (2011).
  * Dupont and Moore (2020) M. Dupont and J. E. Moore, Physical Review B 101, 121106 (2020).
  * Parker  _et al._ (2019) D. E. Parker, X. Cao, A. Avdoshkin, T. Scaffidi, and E. Altman, Physical Review X 9, 041017 (2019).
  * (50) See supplemental materials for details.
  * Summer  _et al._ (2023) A. Summer, C. Chiaracane, M. T. Mitchison, and J. Goold, arXiv preprint arXiv:2303.13476 (2023), 10.48550/arXiv.2303.13476.
  * Lu  _et al._ (2021) S. Lu, M. C. Banuls, and J. I. Cirac, PRX Quantum 2, 020321 (2021).

##  I -SUPPLEMENTAL MATERIAL-

##  II Generalization of the channel to multiple ancillas.

In this Section we generalize the shuffling quantum channel to multiple
ancillas. Namely, for an integer $N$ we define Shuffle$(H,N)$ through the
following steps.

  1. 1.

Pick a Pauli matrix at each site, i.e. $M_{1},...,M_{L}\in\\{I,X,Y,Z\\}$
uniformly at random.

  2. 2.

Prepare $N$ ancillas in state $|0\rangle_{a_{1}}...|0\rangle_{a_{N}}$. For
$\ell=1,...,N$, apply $e^{iH_{M_{1}...M_{L}}X_{a_{\ell}}}$.

  3. 3.

Measure the $N$ ancillas. Only if the measurement outcome is $0$ for all the
$N$ ancillas, apply $M_{1}...M_{L}$ on the $L$ qubits.

The analysis of Shuffle$(H)$ is straightforwardly generalized to the case
$N>1$. For any Pauli string operator $S=M^{\prime}_{1}...M^{\prime}_{L}$ with
$M^{\prime}_{i}\in\\{I,X,Y,Z\\}$, we have

${\rm tr}\,[S\rho^{\prime}]=A{\rm tr}\,[S\rho]+B\,,$ (32)

with

$\displaystyle A=\frac{1}{2^{L}}\sum_{p=0}^{N-1}\binom{N}{p}{\rm tr}\,[$
$\displaystyle S\cos^{p}(H)\sin^{N-p}(H)$ (33) $\displaystyle\times
S\cos^{p}(H)\sin^{N-p}(H)]\,,$

and

$B=\frac{{\rm tr}\,[S\cos^{2N}(H)]}{2^{L}}\,.$ (34)

Moreover, the probability $p$ of measuring $0$ in all the $N$ ancillas is

$p=\frac{{\rm tr}\,[\cos^{2N}(H)]}{2^{L}}\,.$ (35)

When $S$ commutes with $H$, we obtain

$A=1-\frac{{\rm tr}\,[\cos^{2N}(H)]}{2^{L}}\,.$ (36)

In the main text, the system on which we apply this quantum channel contains
$L$ qubits and one extra ancilla $v$. It is thus a system with $L+1$ qubits.
Moreover the Hamiltonian $H^{\prime}$ commutes with the particular choice of
Pauli string $S=Z_{v}$ that we consider. This yields thus formula (28) in the
main text.

##  III Alternative way of extracting the coefficients $A$ and $B$.

In this Section we present an alternative way of computing coefficients $A$
and $B$ appearing in the shuffling quantum channel output in Eq (2) of the
main text. By applying twice Shuffle$(H)$ on a density matrix $\rho$, and
denoting $\rho^{\prime\prime}$ the output density matrix, we have for any
Pauli string $S$

${\rm tr}\,[\rho^{\prime\prime}S]=A^{2}{\rm tr}\,[\rho S]+AB+B\,.$ (37)

It follows thus that we can extract $A$ from the ratio

$A=\frac{{\rm tr}\,[\rho^{\prime\prime}S]-{\rm tr}\,[\rho^{\prime}S]}{{\rm
tr}\,[\rho^{\prime}S]-{\rm tr}\,[\rho S]}\,,$ (38)

where we recall that $\rho^{\prime}$ denotes the density matrix after one
single run of Shuffle$(H)$. Then, $B$ is given by

$B={\rm tr}\,[\rho^{\prime}S]-A{\rm tr}\,[\rho S]\,.$ (39)

Applying this process to the Hamiltonians $Ht$ and $Ht+\tfrac{\pi}{2}$, one
can then sum the resulting $A$’s and obtain the dynamical correlation
$C_{S}(t)$. This is the technique we used in Fig 2 of the main text to compute
dynamical correlations at infinite temperature.

This way of computing $C_{S}(t)$ presents sometimes a lower variance compared
to the one quoted in the main text, although more involved. Let us indeed
compute the variance $\Delta$ in the estimation of $A$. The variance in
estimating ${\rm tr}\,[\rho^{\prime}S]$ using $K$ shots is $\frac{1-{\rm
tr}\,[\rho^{\prime}S]^{2}}{K}$. Hence, using Gaussian error propagation, at
large $K$ the variance $\Delta$ in estimating $A$ through formula (38) is

$\displaystyle\Delta=$ $\displaystyle\frac{1-{\rm
tr}\,[\rho^{\prime}S]^{2}}{K}\frac{1}{({\rm tr}\,[\rho S]-{\rm
tr}\,[\rho^{\prime}S])^{2}}+\frac{1-{\rm
tr}\,[\rho^{\prime\prime}S]^{2}}{K}\frac{1}{({\rm tr}\,[\rho S]-{\rm
tr}\,[\rho^{\prime}S])^{2}}$ (40) $\displaystyle+\frac{1-{\rm tr}\,[\rho
S]^{2}}{K}\left(\frac{{\rm tr}\,[\rho^{\prime}S]-{\rm
tr}\,[\rho^{\prime\prime}S]}{({\rm tr}\,[\rho S]-{\rm
tr}\,[\rho^{\prime}S])^{2}}\right)^{2}+\frac{1-{\rm
tr}\,[\rho^{\prime}S]^{2}}{K}\left(\frac{{\rm tr}\,[\rho^{\prime}S]-{\rm
tr}\,[\rho^{\prime\prime}S]}{({\rm tr}\,[\rho S]-{\rm
tr}\,[\rho^{\prime}S])^{2}}\right)^{2}\,.$

Expressed in terms of $m\equiv{\rm tr}\,[\rho S]$ and $A,B$, this is

$\displaystyle\Delta=\frac{1}{K(m(A-1)+B)^{2}}\left[2+2A^{2}-(mA+B)^{2}-(mA^{2}+AB+B)^{2}-m^{2}A^{2}-(mA+B)^{2}A^{2}\right]\,.$
(41)

Dynamical correlations typically become small as $t$ increases, meaning that
$A$ is typically small, whereas $B$ remains of order $1$ since the two $B$’s
obtained from $Ht$ and $Ht+\tfrac{\pi}{2}$ have to add up to $1$. When $A\to
0$ and $B\to 1$, we see that we have $\Delta\to 0$ at fixed $K$. When $A\to 0$
for $B=1/2$ we have $\Delta=\frac{2}{3K}$ if we choose $m=-1$. For the method
stated in the text, the variance in estimating $C_{S}(t)$ is $\frac{4}{K}$
when $C_{S}(t)\to 0$. This approach yields thus typically a lower variance in
these situations.


# Optimizing Group-Fair Plackett-Luce Ranking Models for Relevance and Ex-Post
Fairness

Sruthi Gorantla  Indian Institute of Science, Bengaluru, India. {gorantlas,
<EMAIL_ADDRESS>Eshaan Bhansali Work partially done while the author was a
research intern at Microsoft Research, Bengaluru, India. University of
California, Berkeley, USA<EMAIL_ADDRESS>Amit Deshpande Equal Contribution
Microsoft Research, Bengaluru, India<EMAIL_ADDRESS>Anand
Louis††footnotemark:  Indian Institute of Science, Bengaluru, India.
{gorantlas<EMAIL_ADDRESS>
###### Abstract

In learning-to-rank (LTR), optimizing only the relevance (or the expected
ranking utility) can cause representational harm to certain categories of
items. Moreover, if there is implicit bias in the relevance scores, LTR models
may fail to optimize for true relevance. Previous works have proposed
efficient algorithms to train stochastic ranking models that achieve fairness
of exposure to the groups ex-ante (or, in expectation), which may not
guarantee representation fairness to the groups ex-post, that is, after
realizing a ranking from the stochastic ranking model. Typically, ex-post
fairness is achieved by post-processing, but previous work does not train
stochastic ranking models that are aware of this post-processing.

In this paper, we propose a novel objective that maximizes expected relevance
only over those rankings that satisfy given representation constraints to
ensure ex-post fairness. Building upon recent work on an efficient sampler for
ex-post group-fair rankings, we propose a group-fair Plackett-Luce model and
show that it can be efficiently optimized for our objective in the LTR
framework.

Experiments on three real-world datasets show that our group-fair algorithm
guarantees fairness alongside usually having better relevance compared to the
LTR baselines. In addition, our algorithm also achieves better relevance than
post-processing baselines, which also ensures ex-post fairness. Further, when
implicit bias is injected into the training data, our algorithm typically
outperforms existing LTR baselines in relevance.

##  1 Introduction

Rankings of people, places, news, and products have critical real-world
applications that influence our worldview. Ranking systems that optimize for
relevance alone can amplify societal biases learned from their training data
and reinforce certain stereotypes Castillo (2019); Zehlike et al. (2022a, b).
Thus, the field of fairness in learning-to-rank (LTR) has emerged as a
response to these concerns, aiming to develop methodologies that ensure
equitable and unbiased ranking outcomes.

Stochastic ranking models have gained popularity in LTR Cao et al. (2007); Xia
et al. (2008); Oosterhuis and de Rijke (2018), primarily due to off-the-shelf
gradient-based methods that can be used to optimize these models efficiently.
Further, they provide fairness guarantees that deterministic rankings for LTR
cannot, e.g., ensuring that multiple items or groups have an equal (or some
guaranteed minimum) probability of appearing at the top.

There are two types of fairness guarantees one could ask for in a stochastic
ranking: ex-ante and ex-post. Ex-ante fairness asks for satisfying fairness in
expectation, i.e., before the stochastic ranking model realizes a ranking. In
contrast, ex-post fairness, often referred to as outcome fairness, requires
fairness of the actual ranking after one is generated by the stochastic
ranking model111The choice between ex-post and ex-ante fairness depends on the
context, available data, and additional ethical considerations.. To the best
of our knowledge, recent works can guarantee ex-post fairness only by
deterministic or randomized post-processing of the stochastic ranking model.
But, in-processing for ex-post fairness has not been studied before this work.

We consider the well-known Plackett-Luce (PL) model as our stochastic ranking
model. PL model has been used in many fields, such as statistics Plackett
(1975); Gormley and Murphy (2009), psychology Luce (1959), social choice
theory Soufiani et al. (2012), econometrics Beggs et al. (1981), amongst
others. Recent work has increased the popularity, scope, and efficiency of the
PL model in LTR Singh and Joachims (2019); Diaz et al. (2020); Oosterhuis
(2022). It is also shown to be robust Bruch et al. (2020) and effective for
exploration in online LTR Oosterhuis and de Rijke (2018, 2021).

Faster and practical algorithms for novel and unbiased estimators of the
gradient of the expected ranking utility–for the PL model–have been proposed
recently Oosterhuis (2021, 2022). These algorithms can efficiently optimize PL
models for not just relevance (e.g., discounted cumulative gain) but also
certain fairness notions that can be expressed as an expectation over the
stochastic rankings (e.g., fair exposure). Due to the inherent randomization
in the PL model, ex-post fairness guarantees are more challenging to
incorporate in the training process such that the resultant model can be
optimized efficiently.

###  1.1 Motivating Example for Ex-Post Fairness

We start by demonstrating the importance of ex-post fairness in real-world
ranking systems. Consider a job recommendation platform such as LinkedIn
Talent Search222https://business.linkedin.com/talent-solutions, where a
stochastic ranking algorithm determines the order in which potential interview
candidates from different demographic groups are recommended to recruiters.
Let us say there are candidates from two groups – $G_{1}$, a majority group
with high merit scores, and $G_{2}$, a minority group (usually
underprivileged) whose merit scores are underestimated due to biases present
in the training data used for LTR. These biases may originate from historical
imbalances, social prejudices, or systemic inequalities in the data.

The stochastic ranking model must output the top-$10$ candidates every time a
recruiter queries for a list of suitable candidates. Consider a particular
stochastic ranking that (1) chooses a group $G_{1}$ or $G_{2}$ with
probability $0.5$ each, and (2) shows the top $10$ candidates from the group
chosen in Step 1. This ensures equal representation of both the groups ex-ante
because there will be $5$ candidates in the top $10$ from each group, in
expectation. However, none of the rankings output by the stochastic ranking
satisfies equal representation ex-post. Such rankings may not be aligned with
the ethical and diversity hiring policies of the recruiters (or companies).

###  1.2 Our Contributions

The main contribution of our work is a novel objective that maximizes
relevance for a Group-Fair-PL model, where the relevance (or the expected
ranking utility) is taken over only those rankings that satisfy given
representation constraints for certain sensitive categories or groups of
items. We show that a recent post-processing sampler for ex-post group-fair
rankings Gorantla et al. (2022) combined with recent ideas to optimize the
group-wise PL model Oosterhuis (2021, 2022) can be used to optimize this model
efficiently. As a result, we get the best of both worlds: the efficiency of
optimization in a fairness-aware in-processing objective and the ex-post
fairness guarantees of post-processing methods.

Our experiments on three real-world datasets, HMDA, German Credit, and
MovieLens, show that our model guarantees ex-post fairness and achieves higher
relevance compared to the baselines. Implicit bias in training data can often
negatively affect ranking models optimized for relevance Celis et al. (2020).
When implicit bias is injected into the training data as a stress test or
audit for fair ranking algorithms, our algorithm outperforms existing
baselines in fairness and relevance.

The rest of the paper is organized as follows: In Section 2, we discuss
closely related work in fair ranking to point out the significance and novelty
of our results. Section 3 defines our novel relevance objective with ex-post
fairness guarantees. In Section 4, we show how to optimize the Group-Fair-PL
model for our objective. Section 5 contains an experimental validation of our
relevance and fairness guarantees.

##  2 Related Work

Stochastic ranking models have been widely studied in LTR, as they can be
differentiable, and thus one can compute the gradient of a ranking utility to
be optimized (e.g., discounted cumulative gain). In particular, the PL ranking
model has been a popular model in recent work for optimizing relevance and
fairness Oosterhuis (2021, 2022); Singh and Joachims (2019). Recent work has
proposed efficient and practical algorithms, namely, PL-Rank and its variants,
for optimizing PL ranking models using estimates of the gradient Oosterhuis
(2021). In addition to optimizing ranking utility, the PL-Rank algorithm also
optimizes fairness of exposure – an ex-ante fairness metric Singh and Joachims
(2019). Yadav et al. (2021) also optimize a PL ranking model for both utility
and fairness of exposure in the presence of position bias, where items that
are ranked higher receive more positive relevance feedback. Similar to these
works, we too study the PL ranking model for LTR. However, we propose a
variant that incorporates ex-post fairness rather than just ex-ante fairness.

Broadly, the fair ranking algorithms can be divided into two groups: post-
processing and in-processing. Post-processing algorithms process the output of
a given ranking model to incorporate group-fairness guarantees about
sufficient representation of every group (especially, underprivileged
demographic groups) in the top positions or top prefixes Celis et al. (2018);
Geyik et al. (2019); Asudeh et al. (2019). As a result, the underlying ranking
model may not be optimized in anticipation of the post-processing. In-
processing algorithms, on the other hand, incorporate fairness controls to
modify the objective in learning-to-rank Singh and Joachims (2018, 2019);
Oosterhuis (2021). As a consequence, previous work on post-processing
algorithms in fair ranking can provide ex-post (actual) guarantees on the
group-wise representation in the top ranks Celis et al. (2018); Geyik et al.
(2019), whereas in-processing algorithms can only provide ex-ante (expected)
guarantees on group-wise exposure Singh and Joachims (2018) or amortized
individual fairness Biega et al. (2018). The major drawback of the existing
LTR algorithms is that none of them optimize relevance while ensuring that
every output ranking satisfies group-wise representation guarantees in the top
ranks. Our work aims to address this gap.

Recently Gorantla et al. (2022) proposed a randomized post-processing
algorithm that gives ex-post group-fairness guarantees. Their algorithm works
in two steps, the first step generates a random group-fair allocation of the
top-$k$ positions that satisfy given group-wise representation constraints,
and the second step fills these positions consistent with the intra-group
ranking within each group. Their algorithm only requires the ordinal ranking
with each group as input, not the individual scores for items or across-group
comparisons. Their motivation to study this was unreliable comparisons,
implicit bias and incomplete information in ranking. However, their first step
of sampling a group-fair allocation is closely related to our work and we
apply it in the optimization of ex-post group-fair Plackett-Luce model.
Therefore, it is also the most relevant post-processing baseline chosen in our
experiments.

##  3 Ex-Post Fairness in Ranking

#### Preliminaries.

Let $\mathcal{I}$ denote the set of items (or documents). Let
$\textsf{S}_{k}(\mathcal{I})$ be the set of all $k$ sized permutations of the
items in $\mathcal{I}$. In the learning-to-rank setup, for any query $q$, the
goal is to output the top-$k$ ranking of relevant items. Let $R_{q,d}$ be an
indicator random variable that takes the value of $1$ if item $d$ is relevant
to $q$ and $0$ otherwise. The probability of $d$ being relevant to $q$ is
represented as $\rho_{d}:=P(R_{q,d}=1)$. Let
$\sigma\in\textsf{S}_{k}(\mathcal{I})$ represent a ranking and let $\sigma(i)$
represent the item in rank $i$. We use $\sigma(i:i^{\prime})$ for any
$1\leqslant i<i^{\prime}\leqslant k$ to represent the set of items in ranks
$i$ to $i^{\prime}$ included in ranking $\sigma$, that is,
$\sigma(i:i^{\prime}):=\left\\{\sigma(i),\sigma(i+1),\ldots,\sigma(i^{\prime})\right\\}$.
Note that $\sigma(1:k)$ represents the items in the ranking as a set, whereas
$\sigma$ itself is an ordered representation of this set of items. In the
following, we drop $q$ from the notation since, in the rest of the paper, we
will be working with a fixed query $q$.

Previous works have considered stochastic ranking models since they offer
equity in attention distribution across items Singh and Joachims (2019). They
are preferred over deterministic rankings for diversity Xia et al. (2017) and
robustness Bruch et al. (2020). We also study stochastic ranking models. We
use $\pi$ to denote a stochastic ranking model (or policy) and $\Pi$ to denote
the set of all stochastic ranking policies. The expected relevance metric for
$\pi\in\Pi$ is defined as follows,

$\mathcal{R}(\pi):=\sum_{\sigma\in\textsf{S}_{k}(\mathcal{I})}\pi[\sigma]\sum_{i\in[k]}\theta_{i}\rho_{\sigma(i)},$
(1)

where $\theta_{i}\in\mathbb{R}_{\geqslant 0}$ are the position discounts
associated with each rank $i\in[k]$ and $\pi[\sigma]$ represents the
probability of sampling $\sigma$ according to $\pi$.

#### Policy Gradients for Placket-Luce.

We use $\pi^{\text{PL}}$ to represent the Plackett-Luce (PL) model. This is a
popular stochastic ranking model that, given a prediction model $m$ that
predicts log scores $m(d)$ for each item $d$, samples a ranking from the
distribution defined based on the individual scores of the items as follows,

$\displaystyle\forall\sigma\in\textsf{S}_{k}(\mathcal{I}),\qquad\pi^{\text{PL}}[\sigma]:=\prod_{i=1}^{k}\frac{e^{m(\sigma(i))}}{\sum\limits_{d\in\mathcal{I}\setminus\sigma(1:i-1)}e^{m(d)}}.$

Singh and Joachims (2019) have proposed using policy gradients to train a PL
ranking model to maximize expected relevance. They utilize the famous log
trick from the REINFORCE algorithm Williams (2004) to compute the gradients of
the expected relevance metric and use stochastic gradient descent to update
the parameters of the PL model. Oosterhuis (2022) has developed a
computationally efficient way to compute the gradients of the expected
relevance metric for the PL model. As a result, PL models can now be trained
efficiently to maximize the expected relevance.

#### Group-Fair Ranking.

Suppose that the set of items $\mathcal{I}$ can be partitioned into $\ell$
groups $\mathcal{I}_{1},\mathcal{I}_{2},\ldots,\mathcal{I}_{\ell}$ based on
the group membership (based on age, race, gender, etc.). For any integer $t$,
we use $[t]$ to denote the set $\\{1,2,\ldots,t\\}$. We consider the
representation-based group fairness constraints in the top-$k$ rankings,
where, for each group $j\in[\ell]$, we are given a lower bound $L_{j}$ and an
upper bound $U_{j}$ on the number of items that can appear in the top-$k$
ranking from that group. Let $\textsf{S}^{\text{fair}}_{k}(\mathcal{I})$
represent all possible group-fair top-$k$ rankings. That is,

$\displaystyle\textsf{S}^{\text{fair}}_{k}(\mathcal{I}):=\left\\{\sigma\in\textsf{S}_{k}(\mathcal{I}):L_{j}\leqslant|\sigma(1:k)\cap\mathcal{I}_{j}|\leqslant
U_{j},\forall j\in[\ell]\right\\}.$

Let $\textsf{G}_{k}(\ell)$ represent the set of all group assignments of the
top-$k$ rankings for $\ell$ groups. That is, for any element
$\gamma\in\textsf{G}_{k}(\ell)$, $\gamma(i)$ represents the group of the item
in rank $i$.

$\textsf{G}_{k}(\ell):=\left\\{\gamma\in[\ell]^{k}\right\\},~{}~{}\text{or
equivalently,}~{}~{}\textsf{G}_{k}(\ell):=[\ell]^{k}.$

Let $g:\mathcal{I}\rightarrow[\ell]$ be the group membership function for the
items. For an item $d$, $g(d)$ represents its group membership. We use
$g(\sigma)$ to represent the vector of group memberships of the items in the
ranking $\sigma$. Note that for any $\sigma$,
$g(\sigma)\in\textsf{G}_{k}(\ell)$. We can then define
$\textsf{G}^{\text{fair}}_{k}(\ell)$ as the set of group assignments that
satisfy the group fairness constraints.

$\textsf{G}^{\text{fair}}_{k}(\ell):=\left\\{g(\sigma)\in[\ell]^{k}:\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})\right\\}.$

Then for any $\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})$,
$g(\sigma)\in\textsf{G}^{\text{fair}}_{k}(\ell)$. There is a many-to-one
correspondence between $\textsf{S}^{\text{fair}}_{k}(\mathcal{I})$ and
$\textsf{G}^{\text{fair}}_{k}(\ell)$.

######  Definition 3.1 (Ex-Post Fair Policy).

A policy $\pi\in\Pi$ is ex-post fair if each ranking $\sigma$ sampled by the
policy $\pi$ satisfies representation-based fairness constraints. That is,

$\forall\sigma\sim\pi,~{}~{}g(\sigma)\not\in\textsf{G}^{\text{fair}}_{k}(\ell)~{}\implies~{}\pi[\sigma]=0.$

#### Limitations of Plackett-Luce.

There have been two significant contributions toward fair ranking with PL
models. We list them and point out their limitations below.

  1. 1.

In-processing. Asudeh et al. (2019) and Oosterhuis (2021) have proposed policy
gradients-based optimization for expected relevance and equity of expected
exposure of groups of items for PL models. The major drawback of these methods
is that fairness is measured in expectation. Therefore, the trained PL model
may not satisfy ex-post fairness.

  2. 2.

Post-processing. Singh and Joachims (2018); Celis et al. (2018); Gorantla et
al. (2022); Geyik et al. (2019) and many other previous works have proposed
algorithms to post-process the scores or the ranking output by any LTR model
(or specifically PL) to satisfy fairness. Ex-post fairness is satisfied in
this case, but the trained LTR model is unaware of the post-processing that is
going to be applied on the scores. Hence, it may end up learning a bad
solution.

We overcome these limitations by incorporating ex-post fairness during the
training process of the PL-based LTR. Towards this end, we propose to use a
different objective function for the stochastic ranking models.

#### Proposed Optimization Objective.

We ask for maximizing expected relevance over ex-post group-fair rankings.
Then the fair expected relevance can be written as follows,

$\mathcal{R}^{\text{fair}}(\pi):=\begin{cases}\sum\limits_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}\pi[\sigma]\sum\limits_{i\in[k]}\theta_{i}\rho_{\sigma(i)},&\text{if
}\pi\text{ is ex-post fair}\\\ 0&\text{otherwise}.\end{cases}$ (2)

In general, the PL model may not satisfy ex-post fairness. Consider the case
where the predicted scores of all the items by model $m$ are non-zero. Then
every ranking in $\textsf{S}_{k}(\mathcal{I})$ is sampled with a non-zero
probability in the PL model based on these scores. Therefore, even if an
optimal PL model that maximizes $\mathcal{R}^{\text{fair}}$ is ex-post fair,
the intermediate PL models during the training process may not be ex-post
fair. Then $\mathcal{R}^{\text{fair}}$ for intermediate PL models will be
evaluated to $0$, resulting in all the gradients being set to $0$. Hence, we
can not train the PL model with $\mathcal{R}^{\text{fair}}$. In fact, the only
way to train a model for $\mathcal{R}^{\text{fair}}$ is to make sure that the
model always samples fair rankings.

#### Other approaches.

We could also optimize a different relevance metric $\widehat{\mathcal{R}}$
defined over $\textsf{S}^{\text{fair}}_{k}(\mathcal{I})$,

$\widehat{\mathcal{R}}(\pi):=\sum\limits_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}\pi[\sigma]\sum\limits_{i\in[k]}\theta_{i}\rho_{\sigma(i)}.$

For any ex-post fair policy $\pi$,
$\widehat{\mathcal{R}}(\pi)=\mathcal{R}^{\text{fair}}(\pi)$. Moreover, if the
fairness constraints are vacuous, that is, $L_{j}=0$ and $U_{j}=k$, for all
$j\in[\ell]$, then,
$\widehat{\mathcal{R}}(\pi)=\mathcal{R}^{\text{fair}}(\pi)=\mathcal{R}(\pi)$.
Note that $\widehat{\mathcal{R}}$ does not strictly enforce ex-post fairness
while training. Hence PL model can be trained for optimizing
$\widehat{\mathcal{R}}$. One could use rejection sampling to enforce ex-post
fairness during and after training. That is, to output a ranking from this
model, we need to sample rankings from this model until we see a fair ranking.
However, in general, the probability of seeing a fair ranking may be very
small. For example, if the fairness constraints are such that $L_{j}=U_{j}$
for all but a constant number of groups in $[\ell]$, and the predicted scores
of the items are such that from each group $j\in[\ell]$, $k$ items have a
score of $1$ and others have score $0$, then the probability of seeing a fair
ranking is $\frac{k^{c}}{k^{\ell}}$, where $c$ is a constant. This means that,
in the PL model, one needs to sample $O(k^{\ell})$ many rankings in
expectation before seeing a fair ranking333This follows from the fact that the
expected value of a geometric random variable with parameter
$p:=\frac{k^{c}}{k^{\ell}}$ is $1/p$., which is computationally inefficient.
This also affects the training process since the estimate of the gradient only
makes sense if we have enough samples that are fair rankings.

For these reasons, asking for stochastic ranking models that can be trained
with $\mathcal{R}^{\text{fair}}$ as an objective is well-motivated. In the
next section we describe our model that satisfies ex-post fairness, from which
we can sample group-fair rankings efficiently. As a result, we get an
efficient algorithm to compute gradients of our proposed model for optimizing
$\mathcal{R}^{\text{fair}}$. We can then use the stochastic gradient descent
method to train our model.

##  4 Group-Fair Placektt-Luce Model

Let $\pi^{\text{fair}}$ represent the Group-Fair-PL model we propose. In
$\pi^{\text{fair}}$, we have a two-step process to sample ex-post group-fair
rankings,

  1. 1.

Sample a top-$k$ group assignment
$\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)$.

  2. 2.

Sample a top-$k$ ranking $\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})$
such that $g(\sigma)=\gamma$.

Then the Group-Fair-PL model can be written as,

$\displaystyle\pi^{\text{fair}}[\sigma]=\mu[g(\sigma)]\pi^{\text{fair}}[\sigma\mid
g(\sigma)],$ (3)

where $\mu[\cdot]$ is the distribution over
$\\{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)\\}$, and
$\pi^{\text{fair}}[\cdot\mid\gamma]$ is a conditional distribution over
$\\{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I}):g(\sigma)=\gamma\\}$.
It is clear that, to achieve ex-post fairness, we can only sample group-fair
group assignments in Step 1. For Step 2, we use PL model for items within the
group for the ranks assigned to that group according to $\gamma$. Therefore,
in the Group-Fair-PL model, any group-fair ranking
$\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})$ is sampled with
probability,

$\displaystyle\pi^{\text{fair}}[\sigma]:=\mu[g(\sigma)]\prod_{i=1}^{k}\frac{e^{m(\sigma(i))}}{\sum\limits_{d\in\underbrace{\mathcal{I}_{g(\sigma(i))}}_{\text{items
from group}}\setminus\sigma(1:i-1)}e^{m(d)}},$ (4)

and any non-group-fair ranking is sampled with probability $0$. Therefore,
$\mathcal{R}^{\text{fair}}$ defined in (2) is always evaluated in the if case
for our Group-Fair-PL model. Let $\sigma_{j}$ be the (sub-) ranking of items
from group $j$ in $\sigma$. We use $\pi^{\text{PL}}_{j}$ to represent the
group-wise PL model for group $j$. Note that for any $j,j^{\prime}\in[\ell]$,
$\sigma_{j}$ and $\sigma_{j^{\prime}}$ are sampled independently from
$\pi^{\text{PL}}_{j}$ and $\pi^{\text{PL}}_{j^{\prime}}$ respectively. Given a
group assignment $\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)$, let
$\psi_{j}(\gamma)\subseteq[k]$ be the subset of the ranks assigned to group
$j$ according to $\gamma$. Since $\mathcal{I}_{1},\ldots,\mathcal{I}_{\ell}$
form a partition of $\mathcal{I}$,
$\psi_{1}(\gamma),\ldots,\psi_{\ell}(\gamma)$ form a partition of $[k]$.
Therefore, Equation 4 can be written as,

$\displaystyle\pi^{\text{fair}}[\sigma]:$
$\displaystyle=\mu[g(\sigma)]\prod_{j=1}^{\ell}\prod_{i\in\psi_{j}(g(\sigma))}\frac{e^{m(\sigma(i))}}{\sum\limits_{d\in\mathcal{I}_{g(\sigma(i))}\setminus\sigma(1:i-1)}e^{m(d)}}$
$\displaystyle=\mu[g(\sigma)]\prod_{j=1}^{\ell}\pi^{\text{PL}}_{j}[\sigma_{j}].$
(5)

######  Lemma 4.1.

$\pi^{\text{fair}}$ is a valid probability distribution over
$\textsf{S}^{\text{fair}}_{k}(\mathcal{I})$.

###### Proof.

It is clear that $\pi^{\text{fair}}[\sigma]\geqslant 0$ for each
$\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})$. Moreover, non-group-fair
rankings are sampled from $\mu$ with probability $0$. Therefore,
$\pi^{\text{fair}}[\sigma]=0$, for every
$\sigma\not\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})$. Further,

$\displaystyle\sum_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}$
$\displaystyle\pi^{\text{fair}}[\sigma]$
$\displaystyle=\sum_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}\mu[g(\sigma)]\prod_{j\in[\ell]}\pi^{\text{PL}}_{j}[\sigma_{j}\mid
g(\sigma)]$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\sum_{\begin{subarray}{c}\sigma\in\textsf{S}_{k}(\mathcal{I})\\\
\text{ s.t.
}g(\sigma)=\gamma\end{subarray}}\prod_{j\in[\ell]}\pi^{\text{PL}}_{j}[\sigma_{j}\mid\gamma]$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{\sigma_{1}\in\textsf{S}_{\left\lvert\psi_{1}(\gamma)\right\rvert}(\mathcal{I}_{1})}\left(\sum_{\sigma_{2}\in\textsf{S}_{\left\lvert\psi_{2}(\gamma)\right\rvert}(\mathcal{I}_{2})}\cdots\left(\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\prod_{j\in[\ell]}\pi^{\text{PL}}_{j}[\sigma_{j}\mid\gamma]\right)\right)\right)$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{\sigma_{1}\in\textsf{S}_{\left\lvert\psi_{1}(\gamma)\right\rvert}(\mathcal{I}_{1})}\pi^{\text{PL}}_{1}[\sigma_{1}\mid\gamma]\left(\sum_{\sigma_{2}\in\textsf{S}_{\left\lvert\psi_{2}(\gamma)\right\rvert}(\mathcal{I}_{2})}\pi^{\text{PL}}_{2}[\sigma_{2}\mid\gamma]\right.\right.\cdots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.\left.\cdots\left(\sum_{\sigma_{\ell-1}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\right)\right)\right)$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{\sigma_{1}\in\textsf{S}_{\left\lvert\psi_{1}(\gamma)\right\rvert}(\mathcal{I}_{1})}\pi^{\text{PL}}_{1}[\sigma_{1}\mid\gamma]\right)\left(\sum_{\sigma_{2}\in\textsf{S}_{\left\lvert\psi_{2}(\gamma)\right\rvert}(\mathcal{I}_{2})}\pi^{\text{PL}}_{2}[\sigma_{2}\mid\gamma]\right)\cdots$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\cdots\left(\sum_{\sigma_{\ell-1}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\right)$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\prod_{j\in[\ell]}\sum_{\sigma_{j}\in\textsf{S}_{\left\lvert\psi_{j}(\gamma)\right\rvert}(\mathcal{I}_{j})}\pi^{\text{PL}}_{j}[\sigma_{j}\mid\gamma]$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\prod_{j\in[\ell]}1$
$\displaystyle=1.$

∎

It remains to understand what should be the distribution over the group
assignments $\mu[\cdot]$. First, we need that $\mu$ is efficiently samplable.
It means that even if there are exponentially-many group assignments that are
fair, we need to able to sample one group assignment from $\mu$ in polynomial
time. Moreover, the gradients of this policy should be efficiently computable,
meaning that the gradient of the expected relevance metric can be computed in
polynomial time.

Algorithm 1 Group-Fair-PL

Input: items: $\mathcal{I}$, relevance scores: $\rho$, ranking metric weights:
$\theta$, prediction model: $m$, number of samples: $M$, groups:
$\mathcal{I}_{1},\mathcal{I}_{2},\ldots,\mathcal{I}_{\ell}$, bounds: $L,U$,
ranking model: $\pi^{\text{fair}}$
Output: Gradients $\frac{\delta}{\delta
m}\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$.

1: Sample $M$ group assignments
$\gamma^{(1)},\gamma^{(2)},\ldots,\gamma^{(M)}$ from Gorantla et al. (2022)
with fairness constraints $L,U$.

2: for each group $j=1,2,\ldots,\ell$ do

3: for $t=1,2,\ldots,M$ do

4: Sample $\sigma^{(t)}_{j}$ from $\pi^{\text{PL}}_{j}$ for ranks
$\psi_{j}(\gamma)$.

5: end for

6: For all $d\in\mathcal{I}$, estimate the gradient $\frac{\delta}{\delta
m(d)}\mathcal{R}_{j}(\pi^{\text{PL}}_{j})$ with $M$ samples
$\sigma_{j}^{(1)},\sigma_{j}^{(2)},\ldots,\sigma_{j}^{(M)}$ using PL-Rank-3
from Oosterhuis (2022) and call it $\zeta_{j}(d)$.

7: end for

8: return gradient estimated for each $d\in\mathcal{I}$ as follows,
$\frac{\delta}{\delta
m(d)}\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})=\sum_{j\in[\ell]}\zeta_{j}(d).$

The distribution from Gorantla et al. (2022) to sample the fair group
assignment $\gamma$ is efficiently samplable and the gradients in this model
are efficiently computable. In fact, the distribution does not depend on the
predicted scores of the items. Hence, the computation of the gradients boils
down to computation of the gradients for each of the group-wise PL models,
which we can do efficiently owing to the PL-Rank-3 algorithm in Oosterhuis
(2022).

The distribution $\mu$ from Gorantla et al. (2022) samples a fair group
assignment $\gamma$ in two steps:

  1. 1.

First, it samples a tuple from the set
$\\{(x_{1},x_{2},\ldots,x_{\ell})\in[k]^{\ell}:L_{j}\leqslant x_{j}\leqslant
U_{j}\land x_{1}+x_{2}+\cdots+x_{\ell}=k\\}$, uniformly at random. In this
tuple, $x_{j}$ gives the number of items from group $j$ to be sampled in the
top-$k$ ranking.

  2. 2.

Then it samples a group assignment
$\gamma=(\gamma_{1},\gamma_{2},\ldots,\gamma_{k})$ to be a uniform random
permutation of the vector $(\underbrace{1,1,\ldots,1}_{x_{1}\text{
times}},\underbrace{2,2,\ldots,2}_{x_{2}\text{
times}},\ldots,\underbrace{\ell,\ell,\ldots,\ell}_{x_{\ell}\text{ times}})$.

Below, we re-state their theorem about the time taken to sample a fair group
assignment from this distribution.

######  Theorem 4.2 (Theorem 4.1 in Gorantla et al. (2022)).

There is a dynamic programming-based algorithm that samples a group assignment
$\gamma$ in time $O(k^{2}\ell)$.

Therefore, this distribution is efficiently samplable. Moreover, this
distribution also satisfies additional desirable properties, which we will
discuss further in Section 5. Our following result then shows that using the
distribution given by Gorantla et al. (2022) for $\mu$ in our Group-Fair-PL
model gives us an efficient algorithm to compute gradient of
$\mathcal{R}^{\text{fair}}$ with respect to the predicted scores $m$.

######  Theorem 4.3.

Algorithm 1 estimates the gradient of the relevance metric
$\mathcal{R}^{\text{fair}}$ in the Group-Fair-PL model in time
$O\left(Mk^{2}\ell+M\left(\left\lvert\mathcal{I}\right\rvert+k\ell\log{\left\lvert\mathcal{I}\right\rvert}\right)\right)$.

###### Proof of Theorem 4.3.

Note that given a group assignment $\gamma$, the probability of sampling an
item $d$ at rank $i$ depends only on the items from group $\gamma(i)$ that
appear in ranks $1$ to $i-1$. In our Group-Fair PL model, only items from
group $\gamma(i)$ are sampled in rank $i$. Let $\psi_{j}(\gamma)$ represent
the set of ranks assigned to group $j$ according to the group assignment
$\gamma$, for each $j\in[\ell]$. Then,

$\displaystyle\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$
$\displaystyle=\sum_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}\pi^{\text{fair}}[\sigma]\left(\sum_{i\in[k]}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle=\sum_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\pi^{\text{fair}}[\gamma,\sigma]\left(\sum_{i\in[k]}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle=\sum_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\cdot\pi^{\text{fair}}[\sigma\mid\gamma]\left(\sum_{i\in[k]}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\sum_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}\pi^{\text{fair}}[\sigma\mid\gamma]\left(\sum_{i\in[k]}\theta_{i}\rho_{\sigma(i)}\right).$

Equation 5 gives us,

$\displaystyle\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}\left(\prod_{j\in[\ell]}\pi^{\text{PL}}_{j}[\sigma_{j}\mid\gamma]\right)\left(\sum_{i\in[k]]}\theta_{i}\rho_{\sigma(i)}\right)\right).$

Now since $\psi_{1}(\gamma),\psi_{2}(\gamma),\ldots,\psi_{\ell}(\gamma)$ form
a partition of $[k]$ we can rearrange the terms to get the following,

$\displaystyle\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{\sigma\in\textsf{S}^{\text{fair}}_{k}(\mathcal{I})}\left(\prod_{j\in[\ell]}\pi^{\text{PL}}_{j}[\sigma_{j}\mid\gamma]\right)\left(\sum_{j\in[\ell]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)\right)$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{\sigma_{1}\in\textsf{S}_{\left\lvert\psi_{1}(\gamma)\right\rvert}(\mathcal{I}_{1})}\sum_{\sigma_{2}\in\textsf{S}_{\left\lvert\psi_{2}(\gamma)\right\rvert}(\mathcal{I}_{2})}\cdots\right.$
$\displaystyle\left.\qquad\qquad\qquad\cdots\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\left(\prod_{j\in[\ell]}\pi^{\text{PL}}_{j}[\sigma_{j}\mid\gamma]\right)\left(\sum_{j\in[\ell]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)\right)$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{\sigma_{1}\in\textsf{S}_{\left\lvert\psi_{1}(\gamma)\right\rvert}(\mathcal{I}_{1})}\pi^{\text{PL}}_{1}[\sigma_{1}\mid\gamma]\sum_{\sigma_{2}\in\textsf{S}_{\left\lvert\psi_{2}(\gamma)\right\rvert}(\mathcal{I}_{2})}\pi^{\text{PL}}_{2}[\sigma_{2}\mid\gamma]\cdots\right.$
$\displaystyle\left.\qquad\qquad\qquad\qquad\qquad\cdots\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{j\in[\ell]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)\right).$

Now the last term can be written as,

$\displaystyle\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}$
$\displaystyle\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{j\in[\ell]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle=\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{i\in\psi_{\ell}(\gamma)}\theta_{i}\rho_{\sigma(i)}+\sum_{j\in[\ell-1]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle=\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{i\in\psi_{\ell}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle\qquad\qquad\qquad\qquad+\sum_{j\in[\ell-1]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\underbrace{\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]}_{=1}$
$\displaystyle=\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{i\in\psi_{\ell}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)+\sum_{j\in[\ell-1]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}.$

Taking the summation
$\sum_{\sigma_{\ell-1}\in\textsf{S}_{\left\lvert\psi_{\ell-1}(\gamma)\right\rvert}(\mathcal{I}_{\ell-1})}\pi^{\text{PL}}_{\ell-1}[\sigma_{\ell-1}\mid\gamma]$
on both sides we get,

$\displaystyle\sum_{\sigma_{\ell-1}\in\textsf{S}_{\left\lvert\psi_{\ell-1}(\gamma)\right\rvert}(\mathcal{I}_{\ell-1})}\pi^{\text{PL}}_{\ell-1}[\sigma_{\ell-1}\mid\gamma]\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{j\in[\ell]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle=\sum_{\sigma_{\ell-1}\in\textsf{S}_{\left\lvert\psi_{\ell-1}(\gamma)\right\rvert}(\mathcal{I}_{\ell-1})}\pi^{\text{PL}}_{\ell-1}[\sigma_{\ell-1}\mid\gamma]\left(\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{i\in\psi_{\ell}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)\right.$
$\displaystyle\left.\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{j\in[\ell-1]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle=\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{i\in\psi_{\ell}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)\underbrace{\sum_{\sigma_{\ell-1}\in\textsf{S}_{\left\lvert\psi_{\ell-1}(\gamma)\right\rvert}(\mathcal{I}_{\ell-1})}\pi^{\text{PL}}_{\ell-1}[\sigma_{\ell-1}\mid\gamma]}_{=1}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{\sigma_{\ell-1}\in\textsf{S}_{\left\lvert\psi_{\ell-1}(\gamma)\right\rvert}(\mathcal{I}_{\ell-1})}\pi^{\text{PL}}_{\ell-1}[\sigma_{\ell-1}\mid\gamma]\sum_{j\in[\ell-1]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}$
$\displaystyle=\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert}(\mathcal{I}_{\ell})}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{i\in\psi_{\ell}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{\sigma_{\ell-1}\in\textsf{S}_{\left\lvert\psi_{\ell-1}(\gamma)\right\rvert}(\mathcal{I}_{\ell-1})}\pi^{\text{PL}}_{\ell-1}[\sigma_{\ell-1}\mid\gamma]\left(\sum_{i\in\psi_{\ell-1}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{j\in[\ell-2]}\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}.$

Repeating the above until we reach $j\in[1]$ in the last term, we get,

$\displaystyle\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{\sigma_{1}\in\textsf{S}_{\left\lvert\psi_{1}(\gamma)\right\rvert}(\mathcal{I}_{1})}\pi^{\text{PL}}_{1}[\sigma_{1}\mid\gamma]\left(\sum_{i\in\psi_{1}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)+\cdots\right.$
$\displaystyle\left.\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\cdots+\sum_{\sigma_{\ell}\in\textsf{S}_{\left\lvert\psi_{\ell}(\gamma)\right\rvert(\mathcal{I}_{\ell})}}\pi^{\text{PL}}_{\ell}[\sigma_{\ell}\mid\gamma]\left(\sum_{i\in\psi_{\ell}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)\right)$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{j\in[\ell]}\sum_{\sigma_{j}\in\textsf{S}_{\left\lvert\psi_{j}(\gamma)\right\rvert}(\mathcal{I}_{j})}\pi^{\text{PL}}_{j}[\sigma_{j}\mid\gamma]\left(\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right)\right)$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\left(\sum_{j\in[\ell]}\mathcal{R}_{j}(\pi^{\text{PL}}_{j})\right),$
(6)

where $R_{j}(\gamma)$ is the reward obtained from the group-wise Plackett-Luce
model $\pi^{\text{PL}}_{j}$ for the ranks assigned to group $j$ according to
the group assignment $\gamma$. That is,

$\mathcal{R}_{j}(\pi^{\text{PL}}_{j}):=\sum_{\sigma_{j}\in\textsf{S}_{\left\lvert\psi_{j}(\gamma)\right\rvert}(\mathcal{I}_{j})}\pi^{\text{PL}}_{j}[\sigma_{j}\mid\gamma]\left(\sum_{i\in\psi_{j}(\gamma)}\theta_{i}\rho_{\sigma(i)}\right).$

Now for a fixed an item $d$, the derivative with respect to the score of $d$
will be,

$\displaystyle\frac{\delta}{\delta
m(d)}\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$
$\displaystyle=\frac{\delta}{\delta
m(d)}\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\Bigg{(}\sum_{j\in[\ell]}\mathcal{R}_{j}(\pi^{\text{PL}}_{j})\Bigg{)}.$

Since in our group-fair PL model, the group assignment $\gamma$ is sampled
independently of the score $m(d)$, we have

$\displaystyle\frac{\delta}{\delta
m(d)}\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$
$\displaystyle=\sum_{\gamma\in\textsf{G}^{\text{fair}}_{k}(\ell)}\mu[\gamma]\Bigg{(}\sum_{j\in[\ell]}\frac{\delta}{\delta
m(d)}\mathcal{R}_{j}(\pi^{\text{PL}}_{j})\Bigg{)}=\mathbb{E}_{\gamma\sim\mu}\left[\sum_{j\in[\ell]}\frac{\delta}{\delta
m(d)}\mathcal{R}_{j}(\pi^{\text{PL}}_{j})\right].$ (7)

#### Naïvely applying PL-Rank-3.

PL-Rank-3 with $N$ samples can estimation the gradient $\frac{\delta}{\delta
m(d)}\mathcal{R}_{j}(\pi^{\text{PL}}_{j})$, for a fixed $\gamma$, in time
$O\left(N\left(\left\lvert\mathcal{I}_{j}\right\rvert+k\log\left\lvert\mathcal{I}_{j}\right\rvert\right)\right)$
for group $j\in[\ell]$. Let us say we take $M$ samples to estimate the outer
expectation. From Theorem 4.2 we have that the time taken to sample one group
assignment $\gamma$ is $O\left(k^{2}\ell\right)$. Therefore, to sample $M$
group assignments, it takes time $O\left(Mk^{2}\ell\right)$. Then, the total
time taken to compute $\frac{\delta}{\delta
m(d)}\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$ will be

$\displaystyle
O\left(M\left(k^{2}\ell+\sum_{j\in[\ell]}N\left(\left\lvert\mathcal{I}_{j}\right\rvert+k\log\left\lvert\mathcal{I}_{j}\right\rvert\right)\right)\right)=O\left(Mk^{2}\ell+MN\left(\left\lvert\mathcal{I}\right\rvert+k\ell\log{\left\lvert\mathcal{I}\right\rvert}\right)\right).$
(8)

#### Correctness for $N=1$.

Let $\text{rank}(\sigma,d)$ represent the rank assigned to item $d$ in
$\sigma$. Then from PL-Rank-3 algorithm in Oosterhuis (2022) we know that

$\displaystyle\frac{\delta}{\delta
m(d)}\mathcal{R}_{j}(\pi^{\text{PL}}_{j})=\mathbb{E}_{\sigma_{j}\mid\gamma}\left[PR^{(j)}_{\sigma,d}+e^{m(d)}\left(\rho_{d}DR^{(j)}_{\sigma,d}-RI^{(j)}_{\sigma,d}\right)\right],$
(9)

where

$\displaystyle
PR^{(j)}_{\sigma,i}=\sum_{i^{\prime}=[i+1,k]\cap\psi_{j}(\gamma)}\theta_{i^{\prime}}\rho_{\sigma(i^{\prime})}~{}~{}~{}~{}$
$\displaystyle\text{and}~{}~{}~{}~{}PR^{(j)}_{\sigma,d}=PR^{(j)}_{\sigma,\text{rank}(\sigma,d)},$
$\displaystyle
RI^{(j)}_{\sigma,i}=\sum_{i^{\prime}=[i+1,k]\cap\psi_{j}(\gamma)}\frac{PR^{(j)}_{\sigma,i}}{\sum_{d^{\prime}\in\mathcal{I}_{j}\setminus\sigma(1:i-1)}e^{m(d^{\prime})}}~{}~{}~{}~{}$
$\displaystyle\text{and}~{}~{}~{}~{}RI^{(j)}_{\sigma,d}=RI^{(j)}_{\sigma,\text{rank}(\sigma,d)},$
$\displaystyle
DR^{(j)}_{\sigma,i}=\sum_{i^{\prime}=[i+1,k]\cap\psi_{j}(\gamma)}\frac{\theta_{\sigma,i}}{\sum_{d^{\prime}\in\mathcal{I}_{j}\setminus\sigma(1:i-1)}e^{m(d^{\prime})}}~{}~{}~{}~{}$
$\displaystyle\text{and}~{}~{}~{}~{}DR^{(j)}_{\sigma,d}=DR^{(j)}_{\sigma,\text{rank}(\sigma,d)}.$

Note that for a fixed ranking $\sigma$, PL-Rank-3 computes the term inside the
expectation efficiently in time
$O(\left\lvert\mathcal{I}_{j}\right\rvert+k\log\left\lvert\mathcal{I}_{j}\right\rvert)$.
Hence, even if the position discount values vary between different samples, or
if the length of the ranking $\left\lvert\psi_{j}(\gamma)\right\rvert$ changes
between different samples, we can still use PL-Rank-3 algorithm to compute the
term inside the expectation for each sample independently and efficiently.
Therefore, substituting Equation 9 in Equation 7 we get,

$\displaystyle\frac{\delta}{\delta
m(d)}\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$
$\displaystyle=\mathbb{E}_{\gamma\sim\mu}\left[\sum_{j\in[\ell]}\frac{\delta}{\delta
m(d)}\mathcal{R}_{j}(\pi^{\text{PL}}_{j})\right]$
$\displaystyle=\mathbb{E}_{\gamma\sim\mu}\left[\sum_{j\in[\ell]}\mathbb{E}_{\sigma_{j}\mid\gamma\sim\pi^{\text{PL}}_{j}}\left[PR^{(j)}_{\sigma,d}+e^{m(d)}\left(\rho_{d}DR^{(j)}_{\sigma,d}-RI^{(j)}_{\sigma,d}\right)\right]\right].$

By linearity of expectation,

$\displaystyle\frac{\delta}{\delta
m(d)}\mathcal{R}^{\text{fair}}(\pi^{\text{fair}})$
$\displaystyle=\sum_{j\in[\ell]}\mathbb{E}_{\gamma\sim\mu}\left[\mathbb{E}_{\sigma_{j}\mid\gamma\sim\pi^{\text{PL}}_{j}}\left[PR^{(j)}_{\sigma,d}+e^{m(d)}\left(\rho_{d}DR^{(j)}_{\sigma,d}-RI^{(j)}_{\sigma,d}\right)\right]\right]$
$\displaystyle=\sum_{j\in[\ell]}\mathbb{E}_{\gamma,\sigma_{j}\sim\pi^{\text{fair}}}\left[PR^{(j)}_{\sigma,d}+e^{m(d)}\left(\rho_{d}DR^{(j)}_{\sigma,d}-RI^{(j)}_{\sigma,d}\right)\right].$
(10)

Hence, we can estimate each term in Equation 10 by taking an empirical average
of $M$ samples of each group-wise rankings. For this, we can take $M$ samples
of $\gamma$ and $1$ sample each of $\sigma_{j}$. From Oosterhuis (2022) we
know that for group $j$ we can compute the corresponding term in the summation
in time $O(|\mathcal{I}_{j}|+k\log|\mathcal{I}_{j}|)$, resulting in a total
time complexity of $O(Mk^{2}\ell+M(|\mathcal{I}|+k\ell\log|\mathcal{I}|))$.
Note that this is same as replacing $N=1$ in Equation 8. ∎ Note that PL-Rank-3
takes time
$O\left(M\left(\left\lvert\mathcal{I}\right\rvert+k\log{\left\lvert\mathcal{I}\right\rvert}\right)\right)$
to compute the gradients.

##  5 Experiments

We conduct experiments on real-world datasets to evaluate our algorithm
empirically. First, we compare Group-Fair-PL against the unconstrained PL
model and observe that Group-Fair-PL is competitive in optimizing relevance.
Second, we use bias-injected data to verify that Group-Fair-PL can mitigate
bias by ensuring ex-post fairness, while achieving higher true utility than
the PL model. Finally, we also compare our algorithm with post-processing
baselines for relevance and ex-post fairness.

#### Metrics.

We use NDCG as the ranking utility metric, with position discounts
$\theta_{i}=\frac{1}{\log_{2}(i+1)}$ for all $i\in[k]$ (first row in all the
figures). The second row in the figures shows the fraction of rankings sampled
from the stochastic ranking models, where an item from the minority group is
placed at rank $i$ for each rank $i\in[k]$. The minority group is as mentioned
in Table 1. The lower and upper bound lines in the figures show
$(p\pm\delta)k$, where $p$ is the proportion of the minority group in the
dataset and $\delta$ is a small number (see Table 1).

#### Baselines.

Apart from PL-Rank-3, we consider PL-Rank-3 + GDL22 and PL-Rank-3 + GAK19 as
baselines to compare our fair in-processing algorithm Group-Fair-PL with post-
processing baselines by Gorantla et al. (2022) and Geyik et al. (2019),
respectively. GAK19 is a fairness post-processing method that also
simultaneously optimizes for relevance, unlike GDL23, which only optimizes for
relevance within the groups but completely ignores the inter-group
comparisons. We also compare results with PL-Rank-3 (true) which is the PL
model trained with PL-Rank-3 on the unbiased (or true) relevance scores. For
more details regarding the parameter choices, see Table 1.

Table 1: Parameters and results of the experiments on various datasets.

Dataset | Experiment
---|---
Name | #queries |  max #items per query |  Relevance Labels |  Sensitive feature | Groups | Minority |  $M$ (Alg. 1) | $k$ | $\delta$ |  Avg. running time (sec.) (Group-Fair-PL) |  Avg. running time (sec.) (PL-Rank-3) | Reference
MovieLens | $2290$ | $588$ |  $1,2,3,$ $4,5$ | Genre |  Action($33\%$), Crime($12\%$), Romance($30\%$), Musical($9\%$), Sci-Fi($16\%$) | Crime | 10 | 10 | 0.02 | 4285 | 118 | Figure 1
German Credit | $500$ | $25$ | $0,1$ | Gender |  Male($74\%$), Female($26\%$) | Female | 50 | 20 | 0.05 | 3008 | 59 | Figure 2
HMDA (AK) | $75$ | $25$ | $0,1$ | Gender |  Male($71\%$), Female($29\%)$ | Female | 100 | 25 | 0.06 | 1528 | 50 | Figure 3
HMDA (CT) | $731$ | $100$ | $0,1$ | Gender |  Male($67\%$), Female($33\%$) | Female | 10 | 25 | 0.06 | 7850 | 673 | Figure 4

Figure 1: Results on the MovieLens dataset.

#### Hyperparameters.

We use a two-layered neural network of $32$ hidden units each to predict
relevance scores. We use stochastic gradient descent with a learning rate of
$0.001$ and batch size $512$ to optimize our relevance metric. We report
aggregate results for $10$ runs of each algorithm. We selected other
hyperparameters after searching for $\delta$ in the range $0.01$ to $0.1$, $M$
in the range $10$ to $100$, and $k$ in the range $10$ to $30$. We chose the
final values to be the smallest in the range where implicit bias had a
significant impact on the output.

#### Implementation.

The unconstrained PL model was trained using PL-Rank-3 algorithm from
Oosterhuis (2022). All the experiments were run on an Intel(R) Xeon(R) Silver
4110 CPU (8 cores, 2.1 GHz clock speed, and 128GB DRAM). For reproducibility,
our data and implementation of Group-Fair-PL will be uploaded at
github.com/sruthigorantla/Group-Fair-PL.

Figure 2: Results on the German Credit dataset. Figure 3: Results on the HMDA
(AK) dataset. Figure 4: Results on the HMDA (CT) dataset.

#### Datasets.

We perform experiments on datasets, for which several past works have raised
fairness concerns and demonstrated the performance of their fair ranking
algorithms Singh and Joachims (2019); Yadav et al. (2021); Oosterhuis (2022);
Cooper et al. (2023). The German Credit dataset encodes users’
creditworthiness as a $0/1$ label Hofmann (1994). To put this data into query-
document pairs, we followed preprocessing similar to Singh and Joachims
(2019). The MovieLens dataset consists of user ratings of movies from the
movielens.org website Harper and Konstan (2016). We first performed a singular
value decomposition to generate $50$-dimensional features. We then chose the
largest $5$ genres (see Table 1) and kept users that rated at least $50$
movies. The HMDA dataset consists of data regarding home mortgage loans in the
US Federal Financial Institutions Examination Council (2017). We used the
preprocessed dataset released by Cooper et al. (2023). The HMDA dataset is
available for every year since $2007$, for all $50$ US states. We used the
data for Alaska (AK) from $2017$ and created a train and test split. For a
more rigorous testing of our algorithms, we also used Connecticut’s (CT) data,
using years $2013-2016$ as training data and year $2017$ as test data. We did
a PCA pre-processing to reduce feature dimension to $50$ Ding and He (2004)
and created query-document pairs similar to the German Credit pre-processing
in Singh and Joachims (2019). The details of the datasets are in Table 1.

#### Datasets with implicit bias.

For each dataset, we inject multiplicative implicit bias in the relevance
scores of the items from the minority group as a stress test for ranking
algorithms. In the HMDA dataset, we multiply the relevance scores of the
female candidates by $\beta$, where $\beta$ is varied between $0$ and $1$
across the columns of Figure 3. For datasets with more than two groups, such
as MovieLens, we use different values of bias for different groups. We report
the bias values for all the groups other than Action group. This model of bias
is inspired by Celis et al. (2020), a practical model that gives useful
insights about the correct optimization objective to consider.

###  5.1 Key Observations

#### Group-Fair-PL gets the best of both fairness and NDCG.

In the presence of implicit bias, Group-Fair-PL outperforms PL-Rank-3 in the
NDCG computed on the true scores and achieves almost same NDCG as PL-Rank-3
(true). Compared to just post-processing for ex-post fairness (PL-Rank-3 +
GDL22 and PL-Rank-3 + GAK19), our algorithm almost always achieves better
NDCG, This suggests that by explicitly enforcing ex-post fairness during
training, we are able to overcome implicit bias via eliminating unreliable
comparisons of items from different groups – main motivation of Gorantla et
al. (2022). Even when there is no bias, our Group-Fair-PL still outputs ex-
post-fair rankings while not compromising on the NDCG.

#### Group-Fair-PL preserves the fairness properties of Gorantla et al.
(2022).

Theorem 3.5 of Gorantla et al. (2022) says that with their group assignment
sampling, the probability of each group being ranked at any of the top $k$
ranks is between the lower and the upper bound (see Figure 3 row 2), even
though the constraints are only for the representation of the group in the
whole of top $k$ ranks. This guarantee is achieved by GDL22 post-processing
anyway. But even without further post-processing, Group-Fair-PL preserves this
property. In contrast, PL-Rank-3 and PL-Rank-3 + GAK19 push the protected
group items to the bottom of the top $k$ ranking in the presence of bias (see
Figure 3 row 2), even when the true representation of the minority group is
uniform across the ranks (see PL-Rank-3 (true)).

#### Running time.

The running time of the algorithms is as shown in Table 1. We note that Group-
Fair-PL spent most of the time sampling the group assignments. Finding faster
algorithms for sampling group assignments is an interesting open problem.

##  6 Conclusion

We propose a novel group-fair Plackett-Luce model for stochastic ranking and
show how one can optimize it efficiently to guarantee high relevance along
with guaranteed ex-post group-fairness instead of ex-ante fairness known in
previous literature on fair learning-to-rank. We experimentally validate the
fairness and relevance guarantees of our ranking models on real-world
datasets. Extending our results to more stochastic ranking models in random
utility theory is an important direction for future work.

## Acknowledgements

SG was supported by a Google PhD Fellowship. AL is grateful to Microsoft
Research for supporting this collaboration.

## References

  * Castillo [2019] Carlos Castillo.  Fairness and transparency in ranking.  _SIGIR Forum_ , 52(2):64–71, Jan 2019.
  * Zehlike et al. [2022a] Meike Zehlike, Ke Yang, and Julia Stoyanovich.  Fairness in ranking, part i: Score-based ranking.  _ACM Comput. Surv._ , 55(6), dec 2022a.
  * Zehlike et al. [2022b] Meike Zehlike, Ke Yang, and Julia Stoyanovich.  Fairness in ranking, part ii: Learning-to-rank and recommender systems.  _ACM Comput. Surv._ , 55(6), dec 2022b.
  * Cao et al. [2007] Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li.  Learning to rank: From pairwise approach to listwise approach.  In _Proceedings of the 24th International Conference on Machine Learning_ , page 129–136, 2007.
  * Xia et al. [2008] Fen Xia, Tie-Yan Liu, Jue Wang, Wensheng Zhang, and Hang Li.  Listwise approach to learning to rank: Theory and algorithm.  In _Proceedings of the 25th International Conference on Machine Learning_ , page 1192–1199, 2008.
  * Oosterhuis and de Rijke [2018] Harrie Oosterhuis and Maarten de Rijke.  Differentiable unbiased online learning to rank.  In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM)_ , page 1293–1302, 2018.
  * Plackett [1975] R. L. Plackett.  The analysis of permutations.  _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , 24(2):193–202, 1975.
  * Gormley and Murphy [2009] Isobel Claire Gormley and Thomas Brendan Murphy.  A grade of membership model for rank data.  _Bayesian Analysis_ , 4(2):265 – 295, 2009.
  * Luce [1959] R. Duncan Luce.  _Individual Choice Behavior: A Theoretical analysis_.  Wiley, 1959.
  * Soufiani et al. [2012] Hossein Azari Soufiani, David C. Parkes, and Lirong Xia.  Random utility theory for social choice.  In _Proceedings of the 25th International Conference on Neural Information Processing Systems - Volume 1_ , page 126–134, 2012.
  * Beggs et al. [1981] S Beggs, S Cardell, and J Hausman.  Assessing the potential demand for electric cars.  _Journal of Econometrics_ , 17(1):1–19, 1981\.
  * Singh and Joachims [2019] Ashudeep Singh and Thorsten Joachims.  Policy learning for fairness in ranking.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Diaz et al. [2020] Fernando Diaz, Bhaskar Mitra, Michael D. Ekstrand, Asia J. Biega, and Ben Carterette.  Evaluating stochastic rankings with expected exposure.  In _Proceedings of the 29th ACM International Conference on Information and Knowledge Management_ , page 275–284, 2020.
  * Oosterhuis [2022] Harrie Oosterhuis.  Learning-to-rank at the speed of sampling: Plackett-luce gradient estimation with minimal computational complexity.  In _SIGIR ’22: The 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 2266–2271, 2022\.
  * Bruch et al. [2020] Sebastian Bruch, Shuguang Han, Michael Bendersky, and Marc Najork.  A stochastic treatment of learning to rank scoring functions.  In _Proceedings of the 13th International Conference on Web Search and Data Mining_ , page 61–69, 2020.
  * Oosterhuis and de Rijke [2021] Harrie Oosterhuis and Maarten de Rijke.  Unifying online and counterfactual learning to rank: A novel counterfactual estimator that effectively utilizes online interventions.  In _Proceedings of the 14th ACM International Conference on Web Search and Data Mining_ , page 463–471, 2021.
  * Oosterhuis [2021] Harrie Oosterhuis.  Computationally efficient optimization of plackett-luce ranking models for relevance and fairness.  In _SIGIR ’21: The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 1023–1032, 2021\.
  * Gorantla et al. [2022] Sruthi Gorantla, Amit Deshpande, and Anand Louis.  Sampling random group fair rankings.  _CoRR_ , abs/2203.00887, 2022.
  * Celis et al. [2020] L. Elisa Celis, Anay Mehrotra, and Nisheeth K. Vishnoi.  Interventions for ranking in the presence of implicit bias.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , page 369–380, 2020.
  * Yadav et al. [2021] Himank Yadav, Zhengxiao Du, and Thorsten Joachims.  Policy-gradient training of fair and unbiased ranking functions.  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’21, page 1044–1053, New York, NY, USA, 2021. Association for Computing Machinery.  ISBN 9781450380379.  doi: 10.1145/3404835.3462953.  URL https://doi.org/10.1145/3404835.3462953.
  * Celis et al. [2018] L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi.  Ranking with fairness constraints.  In _45th International Colloquium on Automata, Languages, and Programming, (ICALP)_ , volume 107 of _LIPIcs_ , pages 28:1–28:15, 2018\.
  * Geyik et al. [2019] Sahin Cem Geyik, Stuart Ambler, and Krishnaram Kenthapadi.  Fairness-aware ranking in search and recommendation systems with application to linkedin talent search.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , page 2221–2231, 2019.
  * Asudeh et al. [2019] Abolfazl Asudeh, H. V. Jagadish, Julia Stoyanovich, and Gautam Das.  Designing fair ranking schemes.  In _Proceedings of the 2019 International Conference on Management of Data_ , page 1259–1276, 2019.
  * Singh and Joachims [2018] Ashudeep Singh and Thorsten Joachims.  Fairness of exposure in rankings.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD_ , pages 2219–2228, 2018\.
  * Biega et al. [2018] Asia J. Biega, Krishna P. Gummadi, and Gerhard Weikum.  Equity of attention: Amortizing individual fairness in rankings.  In _The 41st International ACM SIGIR Conference on Research and Development in Information Retrieval_ , page 405–414, 2018.
  * Xia et al. [2017] Long Xia, Jun Xu, Yanyan Lan, Jiafeng Guo, Wei Zeng, and Xueqi Cheng.  Adapting markov decision process for search result diversification.  In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’17, page 535–544, New York, NY, USA, 2017. Association for Computing Machinery.  ISBN 9781450350228.  doi: 10.1145/3077136.3080775.  URL https://doi.org/10.1145/3077136.3080775.
  * Williams [2004] Ronald J. Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine Learning_ , 8:229–256, 2004.  URL https://api.semanticscholar.org/CorpusID:19115634.
  * Cooper et al. [2023] A. Feder Cooper, Solon Barocas, Christopher De Sa, and Siddhartha Sen.  Variance, Self-Consistency, and Arbitrariness in Fair Classification, 2023.
  * Hofmann [1994] Hans Hofmann.  Statlog (German Credit Data).  UCI Machine Learning Repository, 1994.  DOI: https://doi.org/10.24432/C5NC77.
  * Harper and Konstan [2016] F. Maxwell Harper and Joseph A. Konstan.  The movielens datasets: History and context.  _ACM Trans. Interact. Intell. Syst._ , 5(4):19:1–19:19, 2016.
  * Federal Financial Institutions Examination Council [2017] Federal Financial Institutions Examination Council.  HMDA Data Publication, 2017.  URL https://www.consumerfinance.gov/data-research/hmda/historic-data/.  Released due to the Home Mortgage Disclosure Act.
  * Ding and He [2004] Chris Ding and Xiaofeng He.  K-means clustering via principal component analysis.  In _ICML_ , 2004.