# The HYENAS project: a prediction for the X-ray undetected galaxy groups

Weiguang Cui,1,2,3 Fred Jennings,3 Romeel Dave,3,4 Arif Babul5,6,7 and Ghassem
Gozaliasl8,9
1 Departamento de Física Teórica, M-8, Universidad Autónoma de Madrid,
Cantoblanco 28049, Madrid, Spain
2 Centro de Investigación Avanzada en Física Fundamental,(CIAFF), Universidad
Autónoma de Madrid, Cantoblanco, 28049 Madrid, Spain
3 Institute for Astronomy, University of Edinburgh, Royal Observatory,
Blackford Hill, Edinburgh EH9 3HJ, UK.
4 Department of Physics and Astronomy, University of the Western Cape, Robert
Sobukwe Rd, Cape Town 7460, South Africa
5 Department of Physics and Astronomy, University of Victoria, 3800 Finnerty
Road, Victoria, V8P 1A1, BC, Canada
6 Infosys Visiting Chair Professor, Indian Institute of Science, Bangalore,
560012, India
7 Leverhulme Visiting Professor, Institute for Astronomy, University of
Edinburgh, Blackford Hill, Edinburgh, EH9 3HJ, Scotland, UK
8 Department of Computer Science, Aalto University, P. O. Box 15400, Espoo,
FI-00076, Uusimaa, Finland
9 Department of Physics, University of Helsinki, P. O. Box 64, Helsinki,
FI-00014, Uusimaa, Finland E-mail<EMAIL_ADDRESS>Talento-CM fellow

(Accepted XXX. Received YYY; in original form ZZZ)

###### Abstract

Galaxy groups contain the majority of bound mass with a significant portion of
baryons due to the combination of halo mass and abundance (Cui, 2024). Hence
they serve as a crucial missing piece in the puzzle of galaxy formation and
the evolution of large-scale structures in the Universe. In observations,
mass-complete group catalogues are normally derived from galaxy redshift
surveys detected through various three-dimensional group-finding algorithms.
Confirming the reality of such groups, particularly in the X-rays, is critical
for ensuring robust studies of galaxy evolution in these environments. Recent
works have reported numerous optical groups that are X-ray undetected (see,
e.g., Popesso et al., 2024), sparking debates regarding the reasons for the
unexpectedly low hot gas fraction in galaxy groups. To address this issue, we
utilise zoomed-in simulations of galaxy groups from the novel Hyenas project
to explore the range of hot gas fractions within galaxy groups and investigate
the intrinsic factors behind the observed variability in X-ray emission. We
find that the halo formation time can play a critical role – we see that
groups in halos that formed earlier exhibit up to an order of magnitude
brighter X-ray luminosities compared to those formed later. This suggests that
undetected X-ray groups are preferentially late-formed halos and highlights
the connection between gas fraction and halo formation time in galaxy groups.
Accounting for these biases in galaxy group identification is essential for
advancing our understanding of galaxy formation and achieving precision in
cosmological studies.

###### keywords:

keyword1 – keyword2 – keyword3

††pubyear: xxxx††pagerange: The HYENAS project: a prediction for the X-ray
undetected galaxy groups–D

##  1 Introduction

Galaxy groups, typically with a halo mass in the range of $\sim
10^{13}-10^{14}M_{\odot}$ (Liang et al., 2016), contain the majority of
galaxies in the Universe and serve as the primary environment for key galaxy
evolution processes such as galaxy transformation driven by the interplay
between galaxies and their surrounding gaseous halos (O’Sullivan et al.,
2017). Galaxy groups offer valuable insights into fundamental physical
processes such as galaxy quenching via active galactic nuclei (AGN) feedback
(see, e.g., Bahar et al., 2024; Yang et al., 2024; Eckert et al., 2024),
heating and cooling of the intragroup medium (Oppenheimer et al., 2021), the
diverse kinematical and morphological properties of their central galaxies
(e.g., Loubser et al., 2018; Jung et al., 2022), and the departure from self-
similarity observed in clusters (see, e.g., Yang et al., 2022). Furthermore,
galaxy groups offer constraints on galaxy formation, cosmological parameters,
black hole–galaxy co-evolution, and environmental transformation (see, e.g.,
Lovisari et al., 2021; Eckert et al., 2021; Oppenheimer et al., 2021, for
recent reviews).

Despite their importance, galaxy groups have not received as much attention as
galaxy clusters, mainly due to the difficulty in their detection. They are
faint in the X-rays, with the temperature of the diffuse gas typically ranging
from approximately 0.3 keV to 2 keV (e.g., Mulchaey, 2000; Liang et al.,
2016), resulting in X-ray luminosities typically ranging from $\sim
10^{40}-10^{43}$ erg/s which is several orders of magnitude lower than
clusters (Lovisari et al., 2021, and references therein). Additionally, they
contain far fewer member galaxies than clusters, typically ranging from a few
to several dozen (George et al., 2011), which makes them more challenging to
identify robustly via group-finding algorithms. This can further lead to false
identifications due to chance projections (see, e.g., Pearson et al., 2017; Li
et al., 2022). Detecting hot gas in low-mass galaxy groups (i.e., $M_{h}\in
10^{12.5-13.5}M_{\odot}$) is often regarded as the gold-standard for
validation, but their X-ray faintness limits the number of verified low-mass
groups and biases them towards lower redshifts ($z<0.4$) (see, e.g.,
O’Sullivan et al., 2017; Gozaliasl et al., 2019). Although optical and X-ray
surveys continue to improve, it is critical to understand any biases
introduced by group selection in order to interpret observations properly.

As an example, the scatter in their properties can introduce Malmquist biases
in the inferred physical characteristics (Gozaliasl et al., 2020). Damsted et
al. (2023) noted a significant increase in the scatter of $L_{X}$ compared to
other mass proxies below a redshift of 0.15, primarily in low-mass clusters,
which hampers the effectiveness of X-ray observations in providing a
comprehensive understanding of these groups. Recent studies Khalil et al.
(2024) corroborated these findings using the AXES-2MRS galaxy groups, which
combined data from the ROSAT All-Sky Survey (RASS) with the Two Micron
Redshift Survey (2MRS) Bayesian Group Catalogue. They further suggested that
both feedback mechanisms and halo concentration are the reasons for the
substantial scatter in the properties of X-ray groups, emphasising that the
scatter of scaling relations offers valuable insights into the underlying
physics of galaxy groups.

The large variations in the X-ray brightness among galaxy groups can result in
legitimately significant groups remaining undetected in X-ray surveys. It has
been proposed that only galaxy groups with a central elliptical galaxy tend to
exhibit diffused X-ray emission (e.g., Mulchaey et al., 2003, and references
therein), a phenomenon contingent upon the detection limits of X-ray
telescopes. Utilising the Chandra X-ray Observatory, Pearson et al. (2017)
investigated 10 relaxed galaxy groups carefully selected from the GAMA optical
galaxy catalogue to mitigate spurious and projection effects. They observed
that nine out of ten groups were underluminous in X-rays by a mean factor of
approximately 4 compared to typical X-ray-selected samples. Hence, the
converse practice of identifying X-ray samples and then seeking their
counterparts in optically selected group catalogues may also introduce biases.
Recent work by Damsted et al. (2024) expanded the findings of Manolopoulou et
al. (2021) from galaxy clusters to galaxy groups – galaxy clusters/groups in
overdense environments tend to have higher X-ray luminosities, which they
hypothesised is driven by halo assembly bias. Another recent work by Popesso
et al. (2024) directly combined data from eROSITA with the updated GAMA
catalogue, revealing that 157 out of 189 systems with $M_{200}\geq
10^{13}M_{\odot}$ and $z<0.2$ remained undetected in X-rays. Hence, there are
significant biases introduced either when selecting groups in the optical or
the X-ray (see recent findings, e.g., O’Sullivan et al., 2017; Popesso et al.,
2024). Quantifying these biases and understanding their physical origin is
essential for groups to be leveraged for galaxy formation and cosmological
studies.

In this work, we examine the physical origin of the scatter in properties of
galaxy groups using the Hyenas suite of group-scale zoom simulations (see §2
for details). Hyenas is a new suite that re-simulates 120 group-size halos
drawn from a large-volume cosmological simulation employing the successful
Simba galaxy formation model (Davé et al., 2019). Its novelty lies in its
selection, which is based on bins in both halo mass and halo formation time.
The latter is often implicated as a key driver in the scatter in galaxy group
properties (see, e.g. Cui et al., 2021). Here we investigate what implications
the variations in group halo formation times can have on their detectability
in X-ray and optical surveys, and thereby quantify associated selection
biases.

##  2 The Hyenas project

The Hyenas project is a branch of the Simba with its focus on galaxy groups
using the zoom re-simulation technique. While there have been many cluster-
scale zoom projects, for example, the 300 project (Cui et al., 2018), group-
scale zooms are less common. One reason is that large-volume cosmological
simulations already contain many groups. However, when selected carefully,
zooms can sample outliers in the distribution that are not well represented in
a random sample. Also, zooms offer the opportunity to achieve higher
resolution at a modest computational cost, enabling resolution convergence
studies, though, in this introductory work, we do not employ that aspect of
Hyenas.

Besides selecting zoom halos in the group mass regime, Hyenas further selects
objects with a wide range in halo formation times. This is motivated by Cui et
al. (2021) who argued that halo formation time is the key determinant of the
scatter in the stellar-to-halo mass relation, as well as the cold vs. hot gas
content of halos. This will presumably also impact the X-ray properties of
these systems, which is relevant for this work. Next, we describe the sample
selection and X-ray analysis of the Hyenas zoom suite.

###  2.1 The Hyenas sample and IC generation

Table 1: The cosmology parameters used in the Simbasimulations. H0 [$km/s/Mpc$] | $\Omega_{\Lambda}$ | $\Omega_{m}$ | $\Omega_{b}$ | $\sigma_{8}$ | $n_{s}$
---|---|---|---|---|---
68 | 0.7 | 0.3 | 0.048 | 0.82 | 0.97
Figure 1: The halo mass – formation time relation from the parent dark-matter-
only simulation with illustrations of the selected Hyenas sample. The vertical
blue dashed lines mark the 5 halo mass bins, while the horizontal green dotted
lines indicate the $z_{form}$ percentile bins. The inset images are the
blended gas and star distributions around the central galaxy of the selected
Hyenas samples using the Py-SPHViewer package.

The simulation code and parameter choices used are identical to that in the
Simba simulation, described in Davé et al. (2019) and many subsequent papers.
For brevity, we do not repeat these here but focus on the aspects novel to the
Hyenas zoom suite.

To increase the sample of galaxy groups, we first run a $200{{\,h^{-1}{\rm
Mpc}}}$ dark-matter-only simulation ($8\times$ Simba’s volume), with the same
dark matter particle mass resolution and Planck-concordant cosmology (see
Table 1) as Simbausing Gadget-4 (Springel et al., 2021). From this we select
120 (out of $\sim$10k) halos with $M_{200c}\in
10^{12.5}-10^{14}\,\rm{M_{\odot}}$ (where ‘200c’ denotes 200 times the
critical density). However, these are not selected randomly; rather, within
each 0.5-dex mass bin, we select the galaxies covering a spread halo formation
times in percentile bins. The formation time is calculated as the time when
half the $z=0$ halo mass has assembled within the halo’s main progenitor.
Gadget-4’s on-the-fly merger tree generation makes this calculation
straightforward.

Figure 1 shows the sample selected in 5 halo mass bins and 8 formation time
bins, with the latter chosen with percentiles bounds of
0-2-5-20-50-80-95-98-100 within each mass bin, and are marked as green dotted
horizontal lines in Figure 1. Inside each region in this space, we randomly
select three halos to re-simulate. The central galaxy’s density map of one
example within each region is shown as an inset image. Note that this is only
for illustration, as the image covers 4 times the galaxy’s half-mass radii by
blending both stars and dark matter with arbitrary normalisation using the Py-
SPHViewer.

The large N-body volume’s random initial conditions are generated using MUSIC
(Hahn & Abel, 2011), which conveniently allows us to generate these zoomed-in
ICs for the Hyenas sample using the same underlying white noise file. For each
selected halo, we track all these dark matter particles within the halo at
$z=0$ to their initial condition positions. To precisely identify the centre
of the resimulation region in the IC, we also track these particles lying in
the centre (minimum potential positions) of the halo ($5{{\,h^{-1}{\rm
kpc}}}$) and use the mean position of these central particles within the IC as
the ‘ref_center’ parameter for MUSIC. Then, we calculate the distances from
the IC central position to all the halo particle positions. The 2 times
maximum distance rescaled to the simulation boxsize is used for the
‘ref_extent’ parameter for MUSIC to make sure the interested central halo is
out of contamination.

Each zoomed-in halo has its ICs generated with three different levels of
resolution: Level 0 cuts out the zoomed-in region in the IC, adds gas
particles, and decreases the resolution outside of the zoomed-in region, which
is controlled by the MUSIC code. This results in a dark matter particle mass
of $6.513\times 10^{7}{{\,h^{-1}{\rm{M_{\odot}}}}}$ and gas element mass of
$1.241\times 10^{7}{{\,h^{-1}{\rm{M_{\odot}}}}}$, and a minimum gravitational
softening of 0.5 ${{\,h^{-1}{\rm kpc}}}$. Level 1 increases the zoomed-in
region’s resolution by 1 level higher with a new white noise at this
resolution level. The white noise is consistent as Level0 for these low-
resolution levels decreased outside the zoomed-in region. The Level 1 suite
has $8\times$ lower particle masses and $2\times$ lower minimum softening.
Level 2 has a resolution that is higher than Level 1, with the outside low-
resolution region being consistent with Level 1. Thus, each of the 120
selected Hyenas halo has 3 ICs with different resolutions. Though all the 120
Hyenas halos have both dark-matter-only and hydro ICs, we only run the
hydrodynamic for the 40 selected ‘elite’ halo for Level 1 and Level 2, which
is still not fully finished due to their very high computation cost. The
‘elite’ sample is the one out of the three random samples with the smallest
number of high-resolution particles.

###  2.2 The HYENAS catalogue and analysis

We output 151 snapshots for each simulation run from $z=20$ to $z=0$. Besides
the on-fly FoF catalogue from Gizmo and the Caesar catalogue based on it, we
also run the AHF halo finder (Knollmann & Knebe, 2009) to identify the halos
within $R_{200c}$ and produce an AHF-Caesar catalogue following Chen et al.
(2024).

Although there are other (uncontaminated) halos inside the high-resolution
zoomed-in regions, we only focus on these originally selected Hyenas halos in
this paper. It is also recommended for all papers using the Hyenas data. As
such, we need to identify these selected halos properly. Unfortunately, the
particle IDs of these halos chosen from the parent dark-matter-only simulation
are scrambled within these zoom ICs generated by MUSIC. Thus, we adopted
another method to cross-match these halos based on the particle IDs of these
zoom ICs. Since we know the exact halo centre position in these ICs, we use
the IDs of dark matter particles within 300 ${{\,h^{-1}{\rm kpc}}}$ (more-or-
less corresponding to the $5{{\,h^{-1}{\rm kpc}}}$ radius of halos central
regions at $z=0$) and track them down to $z=0$ to get their median positions.
This position’s distances to the $z=0$ halo centres are used to select the
closest halo. If the halo mass difference from the original N-body one is less
than 1.5 times, the halo is matched. If not, we choose the halo within the
distance of R200c with the closest mass as the matched halo. Only seldom does
this happen for these late-formed halos due to the slight evolution difference
between dark matter and hydro runs. After finding the matched halos for both
FoF and AHF catalogues, we compared the matched halo masses, which basically
agree with previous findings (for example Cui et al., 2012, 2014, minor
effects due to the baryons). We further calculate the formation redshifts
using both FoF and AHF halo catalogues, which are compared to the original
halo formation redshift. There is a slightly larger scatter compared to the
halo mass differences, primarily coming from the $z_{form}\lesssim 0.3$
sample.

###  2.3 X-ray luminosities

X-ray properties are calculated using MOXHApackage (Jennings & Davé, 2023),
which combines the yT-based PyXSIM (Biffi et al., 2012, 2013; ZuHone et al.,
2014) and Caesar (Turk et al., 2011) software packages with the XSPEC spectral
fitting package to provide an end-to-end pipeline for creating mock X-ray
photon maps and analysing them to obtain mock observations such as X-ray
luminosities, temperatures, and metallicities. First, we make a cut on the
cold gas to remove ISM particles, which are artificially pressurised to
resolve the Jeans mass (Davé et al., 2019). We use a cut such that only gas
particles with a density $\rho<0.1$ m${}_{\text{p}}$ cm-3 and temperature
$T>2\times 10^{5}$ K are included. Furthermore, we remove all wind particles
and all particles with a non-zero star formation rate. We then use PyXSIM to
generate X-ray emission fields in the source band of $0.5-2.0$ keV, using a
CIE APEC model (Smith et al., 2001) and using the Simba-tracked particle mass
fractions for He, C, N, O, Ne, Mg, Si, S, Ca, Fe scaled to the Anders &
Grevesse (1989) solar abundances table. The other elements are fixed at their
solar abundance ratios. We finally sum the luminosity of the hot gas particles
within a radius of $R_{500}$ to give our value of $L_{X,0.5-2.0}$. For more
details, we refer to Jennings et al. 2024 in prep.

##  3 Results

###  3.1 Hot gas fraction

Figure 2: The hot gas fraction as a function of halo mass with colours coding
to the halo formation time. The Simba simulation results are shown as small
dots with the median values in solid thin red and cyan lines for early-formed
($z_{form}>1$) and late-formed groups ($z_{form}\leq 1$), respectively. The
error bars present the $16^{th}-84^{th}$ percentile. While the Hyenas sample
at Level0 is indicated by stars with the medians in thick dashed lines. The
observational results from Sun et al. 2009; Laganá et al. 2013; Lovisari et
al. 2015; Akino et al. 2022 are shown in grey symbols with error bars and a
dotted-dashed line with a shadow region as indicated in the legend.

Since the X-ray is coming from hot gas, we first investigate the hot gas mass
fraction in both the galaxy groups from both Hyenas (large stars) and Simba
(small points) simulations and compare them to recent observations from Sun et
al. (2009); Laganá et al. (2013); Akino et al. (2022) in Figure 2. First, in
agreement with observation, there is a decreasing trend for the $f_{hot\ gas}$
with decreased halo mass. The simulations agree better to the observation data
points from Sun et al. (2009); Laganá et al. (2013) (as well as Liang et al.,
2016) than those of Akino et al. (2022) at $M_{500}\gtrsim
10^{13.5}\,\rm{M_{\odot}}$. Note that the gas fraction in the massive halo
seems to agree better with Akino et al. (2022) as shown in Cui et al. (2018),
which could be due to the different AGN feedback strengths. While in the
intermediate halo mass range, the simulation data tends to agree with Akino et
al. (2022) instead of others (see also Robson & Davé, 2020). The disagreements
between these observations’ results at the galaxy group scale have been
discussed in Eckert et al. (2021). Here we would like to add an additional
potential cause: Akino et al. (2022) and Eckert et al. (2016) (which also has
a lower gas fraction compared to the others) are both based on the XXL survey
(Pierre et al., 2016), which is a volume complete survey, while the others
mostly preferentially selected the X-ray bright objects. At lower halo mass
with $M_{500}\lesssim 10^{13}$, this trend flattens.

Secondly, there is a large scatter of the data points in Figure 2. It is worth
noting that the Hyenas sample generally covers the distribution of Simba data
points well at $M_{500}\gtrsim 10^{13}\,\rm{M_{\odot}}$. These outliers from
Simba with $f_{hot\ gas}\gtrsim 0.04$ at $M_{500}\lesssim
10^{13}\,\rm{M_{\odot}}$ could be due to the fact that they are close to a
massive cluster, as discussed in Cui et al. (2022); in contrast, Hyenas groups
are selected to be isolated halos by design. Nevertheless, the agreement of
overall distributions between Simba and Hyenas suggests that our Hyenas
selection criteria are unbiased with respect to halo gas fractions.

The colours of Hyenas points indicate the halo formation redshift as shown by
the colourbar in Figure 2. This shows an interesting trend – the gas fraction
at a given halo mass correlates with its halo formation time. Late-formed
halos tend to have a smaller gas fraction. To statistically show this trend,
we separate the data points into $z_{form}>1$ (red lines) and $z_{form}\leq 1$
(cyan lines). There is quite good agreement between the thick (Hyenas) and
thin (Simba) lines, and both have a clear separation between early-formed and
late-formed halos.

The halo formation time dependence, we speculate, owes to accumulated heating
processes from both AGN feedback and shock heating from structure formation.
For early-formed halos, it will not only have an early accretion of more cold
gas at very high redshift (Cui et al., 2021), experience shock heating earlier
and longer but also form its central galaxy earlier with a massive black hole
according to the $M_{*}-M_{\cdot}$ relation, which leads to an earlier jet
mode feedback in the Simba model.

At lower halo mass $M_{500}\lesssim 10^{13}\,\rm{M_{\odot}}$, the late-formed
halos tend to have a higher gas fraction than early-formed halos, i.e., a
reversed trend, albeit a large error bar for the Simba simulation. In
comparison, the cross point is at a relatively lower halo mass,
$M_{500}\approx 10^{12.5}\,\rm{M_{\odot}}$, for Hyenas, which could be due to
the limited number of objects. At this lower halo mass, the jet mode AGN
feedback will not turn on because the BH mass (see Cui et al., 2022, for the
halo mass – BH mass relation) is lower than the threshold set in Simba which
is around $10^{8}\,\rm{M_{\odot}}$. Thus, the heating process should be
dominated by the supernovae feedback, which can be more dominant in these
late-formed halos with higher star formation. We will return to these
explanations in the discussion part in detail.

###  3.2 X-ray luminosities

Figure 3: Similar to Figure 2, but for the groups X-ray luminosity. Magenta
lines and symbols show the result from Anderson et al. 2015 with the X-ray
luminosity estimated at the same energy band – 0.5 - 2.0 keV. Blue error bars
are the results from Zhang et al. 2024 using the latest eROSITA survey
catalogue. We remind here again that the errorbars are different in simulation
($16^{th}-84^{th}$ percentiles) from observations.

In Figure 3, we show the Hyenas groups’ X-ray luminosity within the soft band,
[0.5, 2] keV, which has been adopted by many surveys for detecting X-ray
galaxy groups. Similar to the hot gas fraction shown in the previous section,
the late-formed halos have a lower X-ray luminosity than early-formed ones.
The differences between the two families at the same halo mass can be an order
of magnitude. Separating the sample by their $z_{form}$ with the arbitrarily
selected threshold of $z=1$, we observe the same trend as shown in Figure 2
with slightly larger separation at $M_{500}\approx 10^{13}$, then a reversed
trend at lower halo mass $M_{500}\approx 10^{12.5}\,\rm{M_{\odot}}$. As
indicated by Bulbul et al. (2024), the detection limit of eRosita at $z\approx
0.2$ (the upper redshift limit in (Popesso et al., 2024)) is around $5\times
10^{42}$ ergs/s, which is indicated by the top horizontal dotted line in
Figure 3. If we naively use that as the detection limit of eROSITA at $z=0.1$,
it is clear that some of our simulated halos, even with $M_{500}\sim 5\times
10^{13}\,\rm{M_{\odot}}$ can not be seen.

In comparison, we include the observation results from Anderson et al. (2015),
which are based on stacking X-ray emission from the ROSAT All-Sky Survey
around the local brightest galaxies. The halo mass in Anderson et al. (2015)
is computed using the simulated catalogue of these local brightest galaxies.
It is clear that the magenta line is lying in between the Hyenas samples at
$M_{500}\gtrsim 10^{13.2}\,\rm{M_{\odot}}$, roughly crossing the detection
limit, and consistently lying on the top boundary of the Hyenas low mass
sample. Similarly, Zhang et al. (2024) stack the X-ray luminosities of the
CENhalo sample, which is binned in halo mass $M_{200m}$ based on the group
finder algorithm (Tinker, 2021). We used the corresponding $M_{500c}$ in
Figure 3, which is derived considering the concentration model from Ishiyama
et al. (2021). Note that the uncertainty on $L_{X}$ is estimated from the
quadratic sum of the Poisson error, which is not the same as what we are
showing in Hyenas. Instead of stacking the galaxy groups, Chiu et al. (2022)
removed these contaminated systems due to a random superposition. With these
remaining 434 groups and clusters, which are cross-confirmed via their weak
lensing masses from the HSC survey, they did an MCMC fitting and yielded a
similar result to Zhang et al. (2024) as shown in Figure 3. In conclusion,
these observation results in the galaxy group scale basically lie on the upper
end of the Hyenas result, which could be explained if the observations are
missing these X-ray faint groups.

Table 2: Predicted X-ray detection limits and fractions

redshift | min mass1 | max mass2 | mean mass3 | fraction4
---|---|---|---|---
z | $\log M_{500}$ | $\log M_{500}$ | $\log M_{500}$ | 100%
$0.2$ | 13.676 | 13.874 | 13.775 | 15.4
$0.1$ | 13.444 | 13.751 | 13.597 | 71.4
$0.04$ | 13.118 | 13.495 | 13.307 | 70.0

  * 1

The minimum halo mass in $\,\rm{M_{\odot}}$ above the X-ray luminosity limit
at a given redshift, corresponds to 0 per cent detection if the halo mass is
smaller than this one.

  * 2

The maximum halo mass above the X-ray luminosity limit at a given redshift,
corresponds to 100 per cent detection if the halo mass is larger than this
one.

  * 3

The mean of columns 2 and 3 for calculating the detection fraction in column
4.

  * 4

The fraction of X-ray detected groups within the halo mass bin, column 3 $\pm
0.1$.

Based on Hyenas data in Figure 3, we further list the roughly predicted limits
for eROSITA in Table 2. At each of the three redshifts, we first select all
Hyenas halos within $\pm$ 10 per cent of the X-ray detection limit. The
minimum and maximum halo masses within that $L_{x}$ limit are listed in the
second and third columns of Table 2, respectively. Using the mean (column 4)
of columns 2 and 3, we select all halos within a halo mass bin of $\pm 0.1$,
then give the detection fraction in the fifth column of Table 2 as
$N_{L_{x}>L_{x,\ lim}}/N_{total\ in\ bin}$. We note here that the Hyenas
sample is not a mass-complete one. Therefore, these limits and fractions only
serve as a rough prediction. The clear drop of the fraction at $z=0.2$
presents a good agreement to Popesso et al. (2024). However, we will need a
larger sample to confirm this.

##  4 Discussion and conclusion

As we have presented before, it is clear that the X-ray-detected galaxy groups
are biased toward these gas-rich ones, which are closely linked to their early
halo formation time. Although it is easy to understand that – early halo
formation will bring more cold gas at high redshift as shown in Cui et al.
(2021), those gases will be heated up by either shock heating in structure
formation or feedback in the process of galaxy formation – it is unclear how
this fits into the picture of general expectations from galaxy formation. We
further break this down into three aspects:

  * $\bullet$

[Connection to the central galaxy] Observations have suggested that early-type
elliptical galaxies in galaxy groups tend to be associated with diffuse X-ray
emission, while late-type disk galaxies do not (Mulchaey et al., 2003). This
is especially interesting because Cui et al. (2021) studied the connection
between the central galaxy stellar mass and the halo mass and revealed the
scatter in that relation is intrinsically driven by halo formation time. In
their Supplementary Figure 2, it is clear that early-formed halos tend to host
massive quenched galaxies at the same halo mass when
$M_{halo}>10^{13}\,\rm{M_{\odot}}$, reversed from the low mass halos in which
the red/quenched galaxies with lower stellar mass tend to live in late-formed
halos. This is further confirmed by the galaxy age (see Figure 7) if we note
that the early-type galaxies are older. We understand that this issue is still
in debate; see Scholz-Díaz et al. (2024) for the most recent discussions on
that. We argue here that our results (including Cui et al. (2021)) are
consistent with their claim that higher stellar mass galaxies at a given halo
mass have characteristics of old, red, and passive systems at halo mass larger
than $10^{13}\,\rm{M_{\odot}}$. While there is less data in Scholz-Díaz et al.
(2024) at low halo/stellar mass range to make a solid conclusion, and their
total mass is only calculated within 3$R_{e}$.

Due to being driven by halo formation time in both relations, we expect a
positive connection between the gas fraction and central galaxy stellar mass
at group halo mass scales – more massive galaxies tend to be surrounded by
more hot gas. This is proved in Figure 5. As suggested by Correa & Schaye
(2020), disc galaxies are less massive than elliptical galaxies in same-mass
haloes when the halo mass is larger than $10^{13}\,\rm{M_{\odot}}$, which
confirms the previous suggestion that elliptical galaxies tend to associate
with X-ray emissions.

We further find a positive correlation between the central galaxy mass-
weighted age and halo formation time, as shown in Figure 7. This again
confirms our results at $M_{500}\gtrsim 10^{13}\,\rm{M_{\odot}}$ are
consistent with Scholz-Díaz et al. (2024) and lead to a positive correlation
with the scatter in central galaxy stellar mass. This is contrary to the
findings of Kulier et al. (2019), which could be because they used all
galaxies within the EAGLE simulation, so low-mass halos dominate the sample.
At low halo masses $M_{halo}\lesssim 10^{13}\,\rm{M_{\odot}}$, such an anti-
correlation is also found in Cui et al. (2021). We also note that a crossing
point is shown in Figure 2, which should be consistent with the reversed trend
at low halo mass, though at slightly different halo masses when comparing
Simba and Hyenas.

  * $\bullet$

[The abundance of cold gas] In previous figures, we only focus on the hot gas
mass fraction; it is unclear how the cold gas abundance will contribute to the
full picture, i.e. whether the low hot gas fraction is due to a high cold gas
fraction or not. This is because galaxy groups, unlike galaxy clusters, tend
to host a noticeable fraction of gas mass in cold as well. Investigating that
will help us to form a full picture of how they are formed. As expected, the
cold gas gradually contributes more to the total gas mass with the halo mass
reduced after $M_{500}\lesssim 10^{13.4}\,\rm{M_{\odot}}$, see Figure 4. It is
further interesting to see that there is more cold gas in late-formed halos
than in early-formed ones in that figure, which we will discuss the reasons
for in the following section. That reveals that the history of halo formation
also affects the history of gas thermalization.

  * $\bullet$

[Connection to central BH] Although there is more gas in early-formed halos,
the gas must be hot to be seen in the X-ray band. Therefore, the heating
processes are key to understanding why there is more hot gas in these early-
formed halos than in late-formed ones. As shown in the previous section, the
early-formed halos not only have more gas but also more hot gas than these
late-formed halos (see Figure 4). Thus, early-formed halos should have more
heating sources/energies than late-formed ones. One possible reason is shock
heating, which should happen earlier in early-formed halos, yielding a hot gas
fraction. The other reason is AGN feedback. For example, Liang et al. (2016)
suggested that the winds ejected from the group galaxies interact with and
heat the hot halo gas, which not only reduces the rate at which the halo gas
cools and accumulates in the group’s central galaxies but also causes its
distribution to remain more extended. More importantly, we found that the
massive galaxies tend to host a more massive BH at the same halo mass (see
Davies et al., 2019, 2020, at the more massive halo mass end; see also Ma et
al. in prep.). This is not surprising since the early-formed halos tend to
form the central galaxy earlier, and as such, the central BH mass grows faster
and earlier. For the case of Simba model, it enters the jet mode earlier to
quench the central galaxy (Cui et al., 2021) with the higher hot gas mass as a
by-product. This picture is supported by Figure 6. We are currently working on
another paper to record the heating energy from different sources to determine
which is more important for gas heating in galaxy groups.

Our findings in this work are based only on the Simba baryon model. However,
we also investigated the TNG-300 simulation, which shows the same gas fraction
trend with a clear separation between early- and late-formed halos, albeit
with a little systematically higher values than what is shown in Figure 2 (see
also Davies et al., 2020, for the higher gas fraction in TNG than EAGLE).
Recent observation work by Popesso et al. (2024), which compared the X-ray
detected and undetected groups, also suggested a similar conclusion, i.e.,
halo assembly bias is the cause. Furthermore, Andreon et al. (2022) showed
that under X-ray luminous clusters populate the low concentration of dark
matter end of the distribution for a given mass, suggesting that they are
late-formed as well. However, the halo formation redshift is very hard to
measure in observations. There are ways to approximate it, such as the galaxy
magnitude/stellar mass difference in fossil groups (e.g. Jones et al., 2003;
Gozaliasl et al., 2014) and the connection between galaxy/gas dynamical state
and halo formation time (e.g. Mostoghiu et al., 2019), but all have a
substantial uncertainty. Though there are claims that the fossil groups show
no difference to normal groups in X-ray scaling relations (e.g. Kundert et
al., 2015; Girardi et al., 2014), their lowest X-ray is still above $\sim
10^{42}$, which is much higher compared to the limit shown in this study. In
this theoretical investigation, we don’t probe into details but suggest these
connections to galaxy and BH properties can be tested in observations as
discussed in previous paragraphs.

Another possible explanation for these X-ray faint or undetected galaxy groups
is the projection effect when they are generally identified through the galaxy
catalogues (see Hernquist et al., 1995, for example). If two small halos are
lying along the same line of sight but have a large separation, neither will
have large enough hot gas to shine in X-ray, see Figure 3 for how quickly the
X-ray luminosity drops with halo mass. However, this projection issue may be
solved by highly accurate spectroscopic redshift measurement with proper
galaxy velocity distribution modelling.

Lastly, the role that baryonic physics models play in this result is not very
clear, especially the AGN feedback, which may affect the X-ray luminosity. For
example, Kar Chowdhury et al. (2022) showed that the different versions of
Simba run turning on and off different Simba’ models, especially the X-ray AGN
feedback and radiative mode, result in different surface brightness profiles
at different radii. However, we argue that this will only systematically shift
our result, while the effect of halo formation time on the X-ray luminosity
will be unchanged, which we have confirmed with the TNG-300 result. On the
other hand, many studies with the EAGLE simulation show consistent
predictions, as we have discussed before.

## Acknowledgements

WC is supported by the STFC AGP Grant ST/V000594/1, the Atracción de Talento
Contract no. 2020-T1/TIC-19882 was granted by the Comunidad de Madrid in
Spain, and the science research grants were from the China Manned Space
Project. He also thanks the Ministerio de Ciencia e Innovación (Spain) for
financial support under Project grant PID2021-122603NB-C21 and HORIZON EUROPE
Marie Sklodowska-Curie Actions for supporting the LACEGAL-III project with
grant number 101086388.

FJ would like to acknowledge the support of the Science and Technology
Facilities Council (STFC).

AB acknowledges support from the Natural Sciences and Engineering Research
Council of Canada (NSERC) through its Discovery Grant program, the Infosys
Foundation, via an endowed Infosys Visiting Chair Professorship at the Indian
Institute of Science and the Leverhulme Trust.

These Hyenas simulations were performed using the DiRAC@Durham facility
managed by the Institute for Computational Cosmology on behalf of the STFC
DiRAC HPC Facility (www.dirac.ac.uk) with the DiRAC Project: ACSP252, titled
Simba Zoom Simulations of Galaxy Groups. The equipment was funded by BEIS
capital funding via STFC capital grants ST/P002293/1, ST/R002371/1 and
ST/S002502/1, Durham University, and STFC operations grant ST/R000832/1. DiRAC
is part of the National e-Infrastructure. The analysis reported in this paper
was also partly enabled by WestGrid and the Digital Research Alliance of
Canada (alliancecan.ca).

## Data Availability

The data output of this paper is available on GitHub: The Hyenas simulation is
currently available upon request, but it will become publicly available very
soon.

## References

  * Akino et al. (2022) Akino D., et al., 2022, PASJ, 74, 175
  * Anders & Grevesse (1989) Anders E., Grevesse N., 1989, Geochimica Cosmochimica Acta, 53, 197
  * Anderson et al. (2015) Anderson M. E., Gaspari M., White S. D. M., Wang W., Dai X., 2015, MNRAS, 449, 3806
  * Andreon et al. (2022) Andreon S., Trinchieri G., Moretti A., 2022, Monthly Notices of the Royal Astronomical Society, 511, 4991
  * Bahar et al. (2024) Bahar Y. E., et al., 2024, arXiv e-prints, p. arXiv:2401.17276
  * Biffi et al. (2012) Biffi V., Dolag K., Böhringer H., Lemson G., 2012, MNRAS, 420, 3545
  * Biffi et al. (2013) Biffi V., Dolag K., Böhringer H., 2013, MNRAS, 428, 1395
  * Bulbul et al. (2024) Bulbul E., et al., 2024, arXiv e-prints, p. arXiv:2402.08452
  * Chen et al. (2024) Chen M., Cui W., Fang W., Wen Z., 2024, ApJ, 966, 227
  * Chiu et al. (2022) Chiu I. N., et al., 2022, A&A, 661, A11
  * Correa & Schaye (2020) Correa C. A., Schaye J., 2020, Monthly Notices of the Royal Astronomical Society, 499, 3578
  * Cui (2024) Cui W., 2024, arXiv e-prints, p. arXiv:2406.03829
  * Cui et al. (2012) Cui W., Borgani S., Dolag K., Murante G., Tornatore L., 2012, MNRAS, 423, 2279
  * Cui et al. (2014) Cui W., Borgani S., Murante G., 2014, MNRAS, 441, 1769
  * Cui et al. (2018) Cui W., et al., 2018, MNRAS, 480, 2898
  * Cui et al. (2021) Cui W., Davé R., Peacock J. A., Anglés-Alcázar D., Yang X., 2021, Nature Astronomy, 5, 1069
  * Cui et al. (2022) Cui W., et al., 2022, MNRAS, 514, 977
  * Damsted et al. (2023) Damsted S., et al., 2023, A&A, 676, A127
  * Damsted et al. (2024) Damsted S., et al., 2024, arXiv e-prints, p. arXiv:2403.17055
  * Davé et al. (2019) Davé R., Anglés-Alcázar D., Narayanan D., Li Q., Rafieferantsoa M. H., Appleby S., 2019, MNRAS, 486, 2827
  * Davies et al. (2019) Davies J. J., Crain R. A., McCarthy I. G., Oppenheimer B. D., Schaye J., Schaller M., McAlpine S., 2019, MNRAS, 485, 3783
  * Davies et al. (2020) Davies J. J., Crain R. A., Oppenheimer B. D., Schaye J., 2020, Monthly Notices of the Royal Astronomical Society, 491, 4462
  * Eckert et al. (2016) Eckert D., et al., 2016, Astronomy and Astrophysics, 592, A12
  * Eckert et al. (2021) Eckert D., Gaspari M., Gastaldelo F., Brun A. M. C. L., O’Sullivan E., 2021, Universe, 7, 142
  * Eckert et al. (2024) Eckert D., Gastaldello F., O’Sullivan E., Finoguenov A., Brienza M., the X-GAP collaboration 2024, arXiv e-prints, p. arXiv:2403.17145
  * George et al. (2011) George M. R., et al., 2011, ApJ, 742, 125
  * Girardi et al. (2014) Girardi M., et al., 2014, Astronomy and Astrophysics, 565, A115
  * Gozaliasl et al. (2014) Gozaliasl G., Khosroshahi H. G., Dariush A. A., Finoguenov A., Jassur D. M. Z., Molaeinezhad A., 2014, A&A, 571, A49
  * Gozaliasl et al. (2019) Gozaliasl G., et al., 2019, MNRAS, 483, 3545
  * Gozaliasl et al. (2020) Gozaliasl G., et al., 2020, A&A, 635, A36
  * Hahn & Abel (2011) Hahn O., Abel T., 2011, MNRAS, 415, 2101
  * Hernquist et al. (1995) Hernquist L., Katz N., Weinberg D. H., 1995, ApJ, 442, 57
  * Ishiyama et al. (2021) Ishiyama T., et al., 2021, MNRAS, 506, 4210
  * Jennings & Davé (2023) Jennings F., Davé R., 2023, MNRAS, 526, 1367
  * Jones et al. (2003) Jones L. R., Ponman T. J., Horton A., Babul A., Ebeling H., Burke D. J., 2003, Monthly Notices of the Royal Astronomical Society, 343, 627
  * Jung et al. (2022) Jung S. L., et al., 2022, Monthly Notices of the Royal Astronomical Society, 515, 22
  * Kar Chowdhury et al. (2022) Kar Chowdhury R., Chatterjee S., Paul A., Sarazin C. L., Dai J. L., 2022, ApJ, 940, 47
  * Khalil et al. (2024) Khalil H., Finoguenov A., Tempel E., Mamon G. A., 2024, arXiv e-prints, p. arXiv:2403.17061
  * Knollmann & Knebe (2009) Knollmann S. R., Knebe A., 2009, The Astrophysical Journal Supplement Series, 182, 608
  * Kulier et al. (2019) Kulier A., Padilla N., Schaye J., Crain R. A., Schaller M., Bower R. G., Theuns T., Paillas E., 2019, Monthly Notices of the Royal Astronomical Society, 482, 3261
  * Kundert et al. (2015) Kundert A., et al., 2015, Monthly Notices of the Royal Astronomical Society, 454, 161
  * Laganá et al. (2013) Laganá T. F., Martinet N., Durret F., Lima Neto G. B., Maughan B., Zhang Y. Y., 2013, Astronomy and Astrophysics, 555, A66
  * Li et al. (2022) Li Q., et al., 2022, ApJ, 933, 9
  * Liang et al. (2016) Liang L., Durier F., Babul A., Davé R., Oppenheimer B. D., Katz N., Fardal M., Quinn T., 2016, Monthly Notices of the Royal Astronomical Society, 456, 4266
  * Loubser et al. (2018) Loubser S. I., Hoekstra H., Babul A., O’Sullivan E., 2018, Monthly Notices of the Royal Astronomical Society, 477, 335
  * Lovisari et al. (2015) Lovisari L., Reiprich T. H., Schellenberger G., 2015, Astronomy and Astrophysics, 573, A118
  * Lovisari et al. (2021) Lovisari L., Ettori S., Gaspari M., Giles P. A., 2021, Universe, 7, 139
  * Manolopoulou et al. (2021) Manolopoulou M., Hoyle B., Mann R. G., Sahlén M., Nadathur S., 2021, Monthly Notices of the Royal Astronomical Society, 500, 1953
  * Mostoghiu et al. (2019) Mostoghiu R., Knebe A., Cui W., Pearce F. R., Yepes G., Power C., Dave R., Arth A., 2019, MNRAS, 483, 3390
  * Mulchaey (2000) Mulchaey J. S., 2000, Annual Review of Astronomy and Astrophysics, 38, 289
  * Mulchaey et al. (2003) Mulchaey J. S., Davis D. S., Mushotzky R. F., Burstein D., 2003, The Astrophysical Journal Supplement Series, 145, 39
  * O’Sullivan et al. (2017) O’Sullivan E., et al., 2017, Monthly Notices of the Royal Astronomical Society, 472, 1482
  * Oppenheimer et al. (2021) Oppenheimer B. D., Babul A., Bahé Y., Butsky I. S., McCarthy I. G., 2021, Universe, 7, 209
  * Pearson et al. (2017) Pearson R. J., et al., 2017, MNRAS, 469, 3489
  * Pierre et al. (2016) Pierre M., et al., 2016, Astronomy and Astrophysics, 592, A1
  * Popesso et al. (2024) Popesso P., et al., 2024, MNRAS, 527, 895
  * Robson & Davé (2020) Robson D., Davé R., 2020, MNRAS, 498, 3061
  * Scholz-Díaz et al. (2024) Scholz-Díaz L., Martín-Navarro I., Falcón-Barroso J., Lyubenova M., van de Ven G., 2024, Nature Astronomy,
  * Smith et al. (2001) Smith R. K., Brickhouse N. S., Liedahl D. A., Raymond J. C., 2001, ApJ, 556, L91
  * Springel et al. (2021) Springel V., Pakmor R., Zier O., Reinecke M., 2021, MNRAS, 506, 2871
  * Sun et al. (2009) Sun M., Voit G. M., Donahue M., Jones C., Forman W., Vikhlinin A., 2009, The Astrophysical Journal, 693, 1142
  * Tinker (2021) Tinker J. L., 2021, ApJ, 923, 154
  * Turk et al. (2011) Turk M. J., Smith B. D., Oishi J. S., Skory S., Skillman S. W., Abel T., Norman M. L., 2011, The Astrophysical Journal Supplement Series, 192, 9
  * Yang et al. (2022) Yang T., Cai Y.-C., Cui W., Davé R., Peacock J. A., Sorini D., 2022, MNRAS, 516, 4084
  * Yang et al. (2024) Yang T., Davé R., Cui W., Cai Y.-C., Peacock J. A., Sorini D., 2024, MNRAS, 527, 1612
  * Zhang et al. (2024) Zhang Y., et al., 2024, arXiv e-prints, p. arXiv:2401.17309
  * ZuHone et al. (2014) ZuHone J. A., Biffi V., Hallman E. J., Randall S. W., Foster A. R., Schmid C., 2014, arXiv e-prints, p. arXiv:1407.1783

##  Appendix A hot gas abundance

Figure 4: The hot gas mass fraction with respect to the total gas mass. The
symbols and lines share the same meanings as Figure 2. The hot gas dominates
($\gtrsim 0.95$) the total gas mass in halos with $M_{500}\gtrsim
10^{13.4}\,\rm{M_{\odot}}$. Cold gas starts to contribute more mass as the
halo mass drops. It is also interesting to see that the hot gas fraction is
higher in these early-formed halos than in later-formed ones at the same halo
mass, which is clearer at the lower halo mass.

As the halo mass decreases, gas heating becomes weak for various reasons. As
such, galaxy groups, unlike clusters, may contain a certain fraction of cold
gas, which doesn’t emit X-ray photons. As such, it would be interesting to
understand the cold gas content in galaxy groups. In Figure 4, we show the hot
gas mass fraction with respect to the total gas mass. Furthermore, the
simulation data is coloured and split by their halo formation time. Although
hot gas still occupies the most mass in galaxy groups, the decreasing fraction
is very clear along halo mass, and late-formed halos have systematically more
cold gas than early-formed halos.

##  Appendix B gas fraction separated by central galaxy fraction

Figure 5: Similar to Figure 2 but color coding to the central galaxy mass
fraction. Due to the stellar mass fraction depending on halo mass, we used its
median value in the $M_{*}/M_{halo}$ \- $M_{halo}$ to separate the two
families. At $M_{500}$ above $10^{13}\,\rm{M_{\odot}}$, More massive central
galaxies tend to have higher hot gas fractions than less massive galaxies at
the same halo mass.

Instead of halo formation time, which directly affects the central galaxy
properties (e.g. Cui et al., 2021), we investigate the central galaxy (or
brightest group galaxy in observation, BGG) stellar mass fraction’s influence
on the hot gas fraction in Figure 5. The symbol colours of simulated objects
are with respect to the BGG’s stellar mass fraction – $M_{*}/M_{500}$. To
clearly show its effects, we first estimate the median line in the $M_{500}$
\- $M_{*}/M_{500}$ relation. Then, separate these symbols in Figure 5 into two
groups: above the median line or below the median line in the $M_{500}$ \-
$M_{*}/M_{500}$ relation. After that, we show the median values of the two
groups in red and blue, respectively. The high gas fraction is generally
associated with a massive BGG.

##  Appendix C gas fraction separated by central BH mass

Figure 6: Similar to Figure 5 but colour coding to the BH mass in the central
galaxy. Again, we use the median line in the $M_{\bullet}-M_{halo}$ relation
to split the massive and low mass BH families. A more massive central BH tends
to have a higher gas fraction at the same halo mass range when $M_{500}\gtrsim
10^{1}3\,\rm{M_{\odot}}$.

Similar to Figure 5, we highlight the effect of black hole mass in Figure 6.
It is not surprising to see the halo with a higher black hole mass tends to
have more hot gas. This is because we know that the black hole mass is
primarily scaling with its host galaxy’s stellar mass. On the other hand, this
hints the AGN feedback may play a role in the higher hot gas fraction.

##  Appendix D gas fraction separated by central galaxy age

Figure 7: Similar to Figure 5 but colour coding to the stellar age of the
central galaxy. Again, we use the median line in the $age-M_{halo}$ relation
to split the sample into two galaxy age families. At the same halo mass range
with $M_{500}\gtrsim 10^{1}3\,\rm{M_{\odot}}$, an older galaxy tends to have a
higher gas fraction.

Instead of BGG’s stellar mass fraction, we show the connection to BGG’s mass-
weighted stellar age in Figure 7. Again, this fits into the consistent picture
of BGGs formed earlier with older age to have more mass in the early-formed
halos.


# Fair Matching in Dynamic Kidney Exchange

Irena Gao
Illinois Mathematics and Science Academy (IMSA)
<EMAIL_ADDRESS>
###### Abstract

Kidney transplants are sharply overdemanded in the United States. A recent
innovation to address organ shortages is a kidney exchange, in which willing
but medically incompatible patient-donor pairs swap donors so that two
successful transplants occur. Proposed rules for matching such pairs include
static fair matching rules, which improve matching for a particular group,
such as highly-sensitized patients. However, in dynamic environments, it seems
intuitively fair to prioritize time-critical pairs. We consider the tradeoff
between established sensitization fairness and time fairness in dynamic
environments. We design two algorithms, SENS and TIME, and study their patient
loss. We show that the there is a theoretical advantage to prioritizing time-
critical patients (around 9.18% tradeoff on U.S. data) rather than sensitized
patients. Our results suggest that time fairness needs to be considered in
kidney exchange. We then propose a batching algorithm for current branch-and-
price solvers that balances both fairness needs.

##  1 Introduction

Kidney disease has consistently been a leading health problem in the United
States; in 2016, there were 44,193 nephritis mortalities, making it the 9th
leading cause of death. In the general American population, poor kidney health
is incredibly prevalent; an estimated 31 million people, or 10% of the adult
population, have chronic kidney disease (CKD), which may progress to end-stage
renal disease (ESRD) or high risk for outright kidney failure.

It is vital that ESRD patients are promptly treated with either of two
options: dialysis or transplantation. A transplant is significantly more
affordable ($32,000 followed by $25,000 annually vs. dialysis’s $89,000
annually) and effective (80% five-year survival rate vs. dialysis’s 35%) U.S.
Renal Data System et al. (2014); however, there has long been a severe—and
increasing—organ supply shortage. In 2016, 54,261 patients were added to the
kidney transplant waiting list, but only 19,060 transplants were performed
with median wait times of well over two years Procurement et al. (2017).

While there is a definite lack of donors, the kidney shortage is exacerbated
by patients who may have willing, but medically incompatible live donors—who
then must then join a kidney waitlist. To safely transplant, patients and
potential donors must show positive crossmatch (compatibility) in blood type.
However, even if their donor’s blood type matches, patients may be further
limited by their tissue sensitization, or probability of tissue crossmatch
failure, as measured by a Calculated Panel Reactive Antibodies (CPRA) score
between 0 (0% probability of tissue crossmatch failure) and 100 (100%
probability of crossmatch failure). In our work, we refer to sensitization
scores between $[0,1]$, or the CRPA score divided by 100. Highly sensitized
patients (CPRA score $\geq$ 80) are at a much higher risk of death, currently
waiting three times longer for transplantation Dickerson et al. (2014).

A promising innovation to address the patient-donor mismatch problem—and the
general kidney shortage—is a kidney exchange. A kidney exchange allows
medically incompatible patients to swap donors with other such patients,
resulting in two successful transplantations where there would have been none.
Swaps can be generalized as k-cycles, where $k$ patients give their donors to
each other, resulting in $k$ transplantations. An altruistic donor, with no
attached patient, can also start a chain, where patients pay forward their
donor beginning with the altruistic donor’s recipient. Because no currency is
involved, organ exchanges do not violate the National Organ Transplant Act of
1984 Abecassis et al. (2000). Kidney exchanges present an interesting problem,
approachable from both the economics and theoretical computer science angles:
given a set of incompatible patient-donor pairs, how might we solve for the
”optimal” set of cycles and chains?

Before this NP-hard problem can be approximated, the first step for the field
is to articulate the problem; i.e. define, justify, and theoretically solve
for ”optimality” Abraham et al. (2007). The standard definition is the
earliest; it focuses on maximizing the number of patients matched at the time
the problem is considered Roth et al. (2004). This definition of ”optimality”
as maximizing the cardinality of patients matched is utilitarian, while its
simple consideration of only the present time period is called myopic. Later
work proposed dynamic utilitarian methods, which emphasize maximizing the
number of patients matched over an extended or infinite time period Dickerson
et al. (2012)Unver (2010). Considering multiple time periods allows the
central clearinghouse to strategically save valuable pairs for a later time
period, where they might result in more overall matchings than if matched
immediately. Ashlagi and Roth Ashlagi and Roth (2011) and Hajaj, et al. Hajaj
et al. (2015) also consider strategyproof utilitarian methods, which ensure
hospitals have no incentives to misreport their mismatched pairs to maximize
personal gain at the cost of overall utilitarianism.

Recently, several authors have also considered the question of fairness.
Dickerson Dickerson et al. (2014) defines a sensitization fairness as
prioritizing highly-sensitized patients, who, by definition, are harder to
match and may remain unmatched while easier-to-match pairs are cleared.
Dickerson quantifies the theoretical loss in matched patient cardinality
compared to the myopic utilitarian algorithm as $\frac{2}{33}$ using United
States averages. Separately, work by Kahng (2016), Anderson et al. (2014), and
Akbarpour et al. (2014) raise the question of time fairness, a natural concern
in emerging dynamic problem formulations, which minimizes wait time for
patients and may prioritize critically ill patients with higher mortality
rates due to limited lifespan. As patients are diagnosed with ESRD at varying
eGFR levels, we consider a pre-dialysis eGFR level of 5 mL/min/1.73
$m^{2}$/year as critical. Intuitively, it seems that strict sensitization
fairness may come at the cost of time fairness, and vice versa. Especially as
kidney exchange models shift from static to dynamic and time fairness becomes
an increasing concern, the kidney exchange clearing problem faces a major
question: how should pairs be prioritized, and at what cost?

We explore the cost of prioritizing highly-sensitized patients over time-
sensitive patients. Theoretically, we show that there is an advantage to
prioritizing time-critical patients over highly-sensitized patients on the
standard kidney exchange model. We then quantify our results using United
State data, and finally, we propose a mechanism to consider both highly-
sensitized and time-critical patients in sparse graphs.

##  2 Model

###  2.1 Kidney Exchange

We consider the standard discrete-time kidney exchange model as established in
Dickerson et al. (2014), Ashlagi and Roth (2011), Roth et al. (2004), and
Unver (2010) using the ABO blood model and two levels of sensitization. The
kidney exchange pool at time $t$ is a set $V_{t}$ of patient-donor pairs
$v=(p,d)$. Pairs enter the market at some time $t\geq 0$; the average quantity
of incoming pairs per time step is $n$. Pairs leave the pool either when
matched with another pair $w\in V_{t}$ or when $v$ perishes. A pair is denoted
as critical if its patient has an eGFR $\leq$ 5 mL/min/1.73 $m^{2}$/year.
Critical pairs have a perishing rate of $\rho_{C}$ and non-critical pairs have
a perishing rate of $\rho_{NC}$, where $\rho_{C}\gg\rho_{NC}$. A non-critical
pair that is not matched has probability $\eta_{C}$ of becoming critical the
next time step.

There are 32 types of pairs, categorized by the CPRA score $p_{s}$ of $p$ and
the blood types $X$ and $Y$ of $p$ and $d$, respectively. Begin by
partitioning $V_{t}$ by blood type into 16 subsets $V_{X-Y}$. Next, as we
consider only two levels of sensitization, consider a sensitization thershold
dividing highly- and lowly-sensitized patient, $\sigma\in[0,1]$; in practice,
$\sigma=0.8$. Highly-sensitized pairs have sensitization level $\gamma_{H}$;
lowly-sensitized pairs have $\gamma_{L}$. The average sensitization level
$\bar{\gamma}=\mu_{H}\cdot\gamma_{H}+(1-\mu_{H})\cdot\gamma_{L}$. Further
partition each subset $V_{X-Y}$ into $\\{V^{L}_{X-Y}\cup V^{H}_{X-Y}\\}$, such
that:

  * •

$V^{L}_{X-Y}$ is of patient-donor blood types $X-Y$ and not highly-sensitized:
$\\{v|v\in V_{X-Y},p_{s}<\eta\\}$

  * •

$V^{H}_{X-Y}$ is of patient-donor blood types $X-Y$ and highly-sensitized:
$\\{v|v\in V_{X-Y},p_{s}\geq\eta\\}$

A future pair incoming at some time $\tau>t$ has an arrival probability
$\mu_{H}$ of being highly-sensitized and arrival probability $1-\mu_{H}$ of
being not highly-sensitized. The average proportion of the entering pool that
is critical is $\mu_{C}$. The probability of an individual (patient or donor)
arriving with blood type $X$ is $\mu_{X}$. Therefore, at $\tau$,

$\displaystyle\mathbf{E}(|V^{H}_{X-Y}|)$ $\displaystyle\leq
n\cdot\mu_{X}\cdot\mu_{Y}\cdot\mu_{H}$ (1)
$\displaystyle\mathbf{E}(|V^{L}_{X-Y}|)$ $\displaystyle\leq
n\cdot\mu_{X}\cdot\mu_{Y}\cdot(1-\mu_{H})$ (2)

$V_{t}$ induces a compatability graph $G_{t}={V_{t},E(V_{t})}$, in which the
nodes are pairs, and $v$ forms an edge with another pair $w\in V_{t}$ only if
the donor of $w$ is compatible with the patient of $v$. A cycle $c$ in $G$
represents a kidney exchange where each vertex in $c$ obtains the kidney of
the previous vertex. Cycles may be of length $k$. We limit our cycles to
$k=3$, as Ashlagi and Roth Ashlagi and Roth (2011) prove that this length is
sufficient for a perfect matching. For simplicity, we do not consider
altruistic chains. A matching $m$ is a collection of vertex-disjoint cycles in
$G$. The set of all legal matchings on G is $M$.

###  2.2 Tradeoff Between Two Algorithms

We study the tradeoff between prioritizing sensitization fairness over time
fairness through two algorithms: SENS and TIME. Consider the set of all
highly-sensitized pairs $H_{t}\subseteq V_{t}$ and the set of all critical
pairs $C_{t}\subseteq V_{t}$. SENS maximizes the highly-sensitized pairs
matched, while TIME maximizes the critical pairs matched. Formally:

$\displaystyle SENS(G_{t})=\underset{m\in
M}{\operatorname{arg}\,\operatorname{max}}\;|\\{v\in m\land v\in H_{t}\\}|$
(3) $\displaystyle TIME(G_{t})=\underset{m\in
M}{\operatorname{arg}\,\operatorname{max}}\;|\\{v\in m\land v\in C_{t}\\}|$
(4)

As these algorithms will always match their target pairs over another similar
pair when possible, we argue that SENS and TIME upper bound the potential
losses due to pursuing each brand of fairness. An algorithm’s loss at $t$ is
defined as the number of agents who perish after the clearinghouse acts during
$t$. Formally:

$L^{t}(ALG)=\rho_{C}|\\{v\notin m_{ALG}\land v\in
C_{t}\\}|+\rho_{NC}|\\{v\notin m_{ALG}\land v\notin C_{t}\\}|$ (5)

We study the loss, rather than the utility, of algorithms. We make two
arguments for this approach. First, the very nature of time fairness, concern
over critically ill patients with a higher perishing rate, prioritizes the
question of how many might we lose? rather than how many might we not match?
Second, choosing algorithms that minimize loss, rather than maximizing
utility, may be fairer. Lost pairs are lost forever, but unmatched, unperished
pairs may actually improve their matchability when new pairs enter the pool in
later rounds. Since these pairs lose much less than pairs who perish during
the time step, we study our algorithms through their losses.

The tradeoff between SENS and TIME is defined similarly to Dickerson’s price
of fairness Dickerson et al. (2014):

$TRDOFF(SENS,TIME)=\lim_{\tau\to\infty}\frac{L^{\tau}(SENS)-L^{\tau}(TIME)}{L^{\tau}(SENS)}$
(6)

Note that we study this tradeoff in a dynamic environment (i.e. we consider
the tradeoff as $t\to\infty$, rather than just at $t=0$); as of this writing,
only Ashlagi et al. (2013) has also studied fairness in dynamic matching, and
then only sensitization fairness.

##  3 Theory

In this section, we upper bound the tradeoff between SENS and TIME on dense
graphs. We show that, with high probability, the theoretical tradeoff is upper
bounded by 2.385.

###  3.1 Setup

We begin by partitioning $V_{t}$ into $\\{V^{O}\cup V^{U}\cup V^{S}\cup
V^{R}\\}$ based on the ease of finding another blood-compatible pair. We
define a universal binary relation $\vartriangleleft$ over the four blood
types. Blood type $X\vartriangleleft$ blood type $Y$ if $X$ can receive a
kidney from donor of blood type $Y$. We then create four subsets of $V_{t}$:

  * •

$V^{O}=\\{V_{X-Y}:X\vartriangleleft Y\land X\neq Y\\}$ (i.e. the patient is
offering a donor more valuble than the one they seek. These pairs may still be
in $V_{t}$ due to tissue incompatability with probability $\bar{\gamma}$)

  * •

$V^{U}=\\{V_{X-Y}:Y\vartriangleleft X\land X\neq Y\\}$ (i.e. the patient is
seeking a donor more valuble than the one they offer)

  * •

$V^{S}=\\{V_{X-X}\\}$ (i.e. the patient and donor have the same blood type)

  * •

$V^{R}=\\{V_{X-Y}:Y\ntriangleleft X\land X\ntriangleleft Y\\}$ (i.e. pairs A-B
or B-A)

We make the same assumptions as Ashlagi and Roth Ashlagi and Roth (2011),
which are supported by United States data (see below).

######  Assumption 3.1 (Average sensitization of incoming patient)

$\mu{H}<\bar{\gamma}<\frac{1}{2}$ since, in practice, $\mu{H}$ is
$\frac{1}{3}$ Center (2017) and $\gamma_{H}\in[0.8,1.0)$.

######  Assumption 3.2 (Blood type frequency)

$\mu_{O}<1.5\mu_{A}$ Dickerson et al. (2014)

Under these assumptions, Ashlagi and Roth’s Lemma 5.1 proves that, with high
probability in a dense graph, there exists a matching $M^{*}$ that matches all
of $V^{O}$, $V^{S}$, and $V^{R}$, though not all of $V^{U}$ Ashlagi and Roth
(2011). We use this as the foundation for our work.

###  3.2 Loss of SENS

In this section, we solve for the loss of SENS for some time $\tau>0$.

######  Lemma 3.1 (Loss of SENS)

$L^{\tau}(SENS)\leq\rho_{C}\bm{[}\sum_{k=0}^{\tau}\mu_{C}\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{C})^{k}\\\
+\eta_{C}\sum_{k=0}^{\tau}[\sum_{j=0}^{k}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{j}](1-\rho_{C})^{\tau-k}\bm{]}\\\
+\rho_{NC}\bm{[}\sum_{k=0}^{\tau}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{k}\bm{]}$

####  3.2.1 for $t=0$

We first consider the SENS algorithm’s loss on a newly entered pool at t=0;
i.e. there are no pairs in $V_{0}$ before $n$ pairs are added to $V_{0}$.

SENS seeks to match the maximum cardinality of matched and highly sensitized
pairs. By Ashlagi and Roth’s Lemma 5.1, all pairs in $V^{O}$, $V^{S}$, and
$V^{R}$ are matched; trivially, this includes highly-sensitized pairs.
Therefore, the only remaining unmatched highly-sensitized pairs are in
$V^{U}=\\{V_{A-AB},V_{B-AB},\allowbreak V_{O-A},V_{O-B},V_{O-AB}\\}$. We then
exhaustively consider how many pairs in $V^{U}$ remain unmatched, as in
Dickerson’s proof Dickerson et al. (2014).

As many B-AB pairs as possible have been matched in 2-cycles to AB-B pairs.
Note that $|V^{H}_{B-AB}|\leq n\cdot\mu_{B}\cdot\mu_{AB}\cdot\mu_{H}$, while
$|V_{AB-B}|\leq n\cdot\mu_{B}\cdot\mu_{AB}\cdot\bar{\gamma}$. Under assumption
3.1, $|V_{AB-B}|\geq|V^{H}_{B-AB}|$. Therefore, all $v\in V^{H}_{B-AB}$ are
matched. Similarly, all $v\in V^{H}_{A-AB}$ are also matched. Any AB-O pairs
intended to be matched in a 3-cycle with O-A and A-AB can still be matched in
a 2-cycle with e.g. O-A at no loss.

We used 2-cycles to match $V^{H}_{O-A}$ to $V_{A-O}$ and $V^{H}_{O-B}$ to
$V_{B-O}$. Also by assumption 3.1, all of $V^{H}_{O-A}$ and $V^{H}_{O-B}$ will
be matched. However, these 2-cycles may exhaust either the $V_{A-O}$ or
$V_{B-O}$ pairs used to match $V_{A-B}-V_{B-A}$ or $V_{B-A}-V_{A-B}$ in Step 3
of Ashlagi and Roth’s Lemma 5.1, preventing up to $|V^{r}_{B-AorA-B}|$ lowly-
sensitized pairs from being matched. By Lemma 5.1 of Ashlagi and Roth Ashlagi
and Roth (2011), this difference is $o(n)$, smaller than any subgroup and
sublinear in $n$; therefore, this term is insignificant as
$n\rightarrow\infty$.

The only remaining group, $V_{O-AB}$, cannot be matched without replacing
another pair: swapping out an AB-O, O-A, A-AB 3-cycle for an AB-O, O-AB
2-cycle results in loss of one pair, breaking up two AB-B, B-O (or AB-A, A-O)
2-cycles for an AB-B, B-O, O-AB (AB-A, A-O, O-AB) 3-cycle also results in loss
of one pair. Therefore, the overall number of unmatched pairs $\leq
n\cdot\mu_{O}\cdot\mu_{AB}\cdot\mu_{H}$.

Figure 1: The matching proposed in Ashlagi and Roth’s Lemma 5.1 is shown as
the arrows between pair blood type nodes. Highly-sensitized pair blood types
that we exhaustively consider above are shown with a gray background. Losses
due to SENS’s modifications have a black background.

Let $\mu_{O-AB}^{H}=n\cdot\mu_{O}\cdot\mu_{AB}\cdot\mu_{H}$. Of these lowly-
sensitized, unmatched pairs, $\mu_{O-AB}^{H}\cdot\mu_{C}$ are critical, while
$\mu_{O-AB}^{H}\cdot(1-\mu_{C})$ are not. Therefore:

$L^{0}(SENS)_{t=0}\leq\rho_{C}\bm{[}\mu_{C}\cdot\mu_{O-AB}^{H}\bm{]}+\rho_{NC}\bm{[}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\bm{]}$
(7)

####  3.2.2 for $t>0$

Next, we consider SENS’s loss at $t=1$. There are
$|V^{0}_{O-AB}|\leq\mu_{O-AB}^{H}$ lowly-sensitized pairs already in the pool
from $t=0$. The new pairs from $t=1$ are then added to the pool. After the
above steps are run again, there are, at most,

$\underbrace{\textstyle\overbrace{\textstyle\mu_{O-AB}^{H}\cdot\mu_{C}\cdot(1-\rho_{C})}^{\mathclap{\text{unperished,
critical}}}+\overbrace{\textstyle\eta_{C}\cdot(1-\mu_{C})\cdot\mu_{O-AB}^{H}}^{\mathclap{\text{non-
critical who became
critical}}}}_{\mathclap{t=0}}+\underbrace{\textstyle\mu_{O-AB}^{H}\cdot\mu_{C}}_{\mathclap{t=1}}$

critical pairs. Becoming critical and perishing are considered separate
events, so the non-critical pairs who became critical are not multiplied by
$(1-\rho_{NC})$. There are also, at most,

$\underbrace{\textstyle(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})}_{\mathclap{t=0}}+\underbrace{\textstyle(1-\mu_{C})\cdot\mu_{O-AB}^{H}}_{\mathclap{t=1}}$

non-critical pairs. Therefore:

$L^{1}(SENS)\leq\rho_{C}\bm{[}\mu_{O-AB}^{H}\cdot\mu_{C}\cdot(1-\rho_{C})+\eta_{C}\cdot(1-\mu_{C})\cdot\mu_{O-AB}^{H}\\\
+\mu_{O-AB}^{H}\cdot\mu_{C}\bm{]}+\rho_{NC}\bm{[}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})\\\
+(1-\mu_{C})\cdot\mu_{O-AB}^{H}\bm{]}$ (8)

And for $t=2$, there are

$\underbrace{\textstyle\mu_{O-AB}^{H}\cdot\mu_{C}\cdot(1-\rho_{C})^{2}+\eta_{C}\cdot\overbrace{\textstyle(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{C})}^{\mathclap{\text{non-
critical pairs from }t=0\text{, now critical at }t=1}}}_{\mathclap{t=0}}\\\
+\underbrace{\textstyle\mu_{O-AB}^{H}\cdot\mu_{C}\cdot(1-\rho_{C})}_{\mathclap{t=1}}\\\
+\underbrace{\textstyle\eta_{C}\overbrace{\textstyle\bm{[}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})+(1-\mu_{C})\cdot\mu_{O-AB}^{H}\bm{]}}}^{\mathclap{\text{non-
critical pairs from }t=1\text{ (including non-critical, untransformed pairs
from t=0)}}}_{\mathclap{t=1}}\\\
+\underbrace{\textstyle\mu_{C}\cdot\mu_{O-AB}^{H}}_{\mathclap{t=2}}$

critical pairs and

$\underbrace{\textstyle(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{2}}_{\mathclap{t=0}}\\\
+\underbrace{\textstyle(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})}_{\mathclap{t=1}}\\\
+\underbrace{\textstyle(1-\mu_{C})\cdot\mu_{O-AB}^{H}}_{\mathclap{t=2}}$

non-critical pairs. In general, for $t=\tau$ and $\tau>0$, there are

$\sum_{k=0}^{\tau}\mu_{C}\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{C})^{k}\\\
+\eta_{C}\sum_{k=0}^{\tau}[\sum_{j=0}^{k}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{j}](1-\rho_{C})^{\tau-k}$

critical pairs and

$\sum_{k=0}^{\tau}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{k}$

non-critical pairs, making the total loss for $\tau>0$

$L^{\tau}(SENS)\leq\rho_{C}\bm{[}\sum_{k=0}^{\tau}\mu_{C}\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{C})^{k}\\\
+\eta_{C}\sum_{k=0}^{\tau}[\sum_{j=0}^{k}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{j}](1-\rho_{C})^{\tau-k}\bm{]}\\\
+\rho_{NC}\bm{[}\sum_{k=0}^{\tau}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{k}\bm{]}$
(9)

###  3.3 Loss of TIME

In this section, we solve for the loss of algorithm TIME for some time
$\tau>0$.

######  Lemma 3.2 (Loss of TIME)

$L^{\tau}(TIME)\leq\rho_{NC}\bm{[}\sum_{k=0}^{\tau}\mu_{O-AB}^{C}\cdot(1-\rho_{NC})^{k}\bm{]}$

####  3.3.1 for $t=0$

We use a parallel method for algorithm TIME as we did for SENS. In the last
step, the overall number of unmatched pairs $\leq\mu_{O-AB}^{C}$, where
$\mu_{O-AB}^{C}=n\cdot\mu_{O}\cdot\mu_{AB}\cdot\mu_{C}$; all are non-critical
pairs. Therefore, the loss for TIME is:

$L^{0}(TIME)\leq\rho_{NC}\bm{[}\mu_{O-AB}^{C}\bm{]}$ (10)

####  3.3.2 for $t>0$

For $t>0$, no critical pairs carry over from the previous time step;
therefore, there are no critical pairs. However, there are

$\sum_{k=0}^{\tau}\mu_{O-AB}^{C}\cdot(1-\rho_{NC})^{k}$

non-critical pairs. Therefore, for $t=\tau$:

$L^{\tau}(TIME)\leq\rho_{NC}\bm{[}\sum_{k=0}^{\tau}\mu_{O-AB}^{C}\cdot(1-\rho_{NC})^{k}\bm{]}$
(11)

###  3.4 Tradeoff between SENS and TIME

We use our above results to calculate the tradeoff defined by equation (6).

$TRDOFF(SENS,TIME)=\\\ \lim_{\tau\to\infty}\frac{\begin{aligned}
\rho_{C}\bm{[}\sum_{k=0}^{\tau}\mu_{C}\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{C})^{k}\\\\[-12.0pt]
+\eta_{C}\sum_{k=0}^{\tau}[\sum_{j=0}^{k}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{j}](1-\rho_{C})^{\tau-k}\bm{]}\\\\[-12.0pt]
+\rho_{NC}\bm{[}\sum_{k=0}^{\tau}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{k}\bm{]}\\\\[-12.0pt]
-\rho_{NC}\bm{[}\sum_{k=0}^{\tau}\mu_{O-AB}^{C}\cdot(1-\rho_{NC})^{k}\bm{]}\end{aligned}}{\begin{aligned}
\rho_{C}\bm{[}\sum_{k=0}^{\tau}\mu_{C}\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{C})^{k}\\\\[-12.0pt]
+\eta_{C}\sum_{k=0}^{\tau}[\sum_{j=0}^{k}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{j}](1-\rho_{C})^{\tau-k}\bm{]}\\\\[-12.0pt]
+\rho_{NC}\bm{[}\sum_{k=0}^{\tau}(1-\mu_{C})\cdot\mu_{O-AB}^{H}\cdot(1-\rho_{NC})^{k}\bm{]}\end{aligned}}$
(12)

In the United States, $\mu_{O}=0.44$, $\mu_{AB}=0.10$, $\mu_{H}=0.3$ Dickerson
et al. (2014), $\mu_{C}=0.14$ (where critical patients are those who begin
treatment with eGFR $<$ 5 mL/min/1.73 $m^{2}$/year) U.S. Renal Data System et
al. (2016), $\rho_{NC}=0.25$, and $\eta_{C}=0.09$ Al-Aly et al. (2010). There
is limited data about the relationship between pre-ESRD eGPR scores and
mortality after dialysis begins; however, based on average mortality increases
of 11% based on a severe eGFR decline in the patient ($<$ -10 mL/min/1.73
$m^{2}$/year) by Sumida et al. (2016), we set $\rho_{C}=0.35$. Using these
numbers, we estimate the tradeoff betwen SENS and TIME in the United States.
However, since the double summation in $LOSS^{\tau}(SENS)$ is not computable,
we estimate the tradeoff at $\tau=10$:

$TRDOFF(SENS,TIME)\approx\frac{0.010496n}{0.114249n}\approx 0.091872$

In other words, the long-term difference between prioritizing sensitized and
prioritizing time-critical patients has an upper bound of around 9.18% of
SENS’s unique loss; theoretically, matching sensitized patients over time-
critical ones results in moderate losses. (We note, of course, that this value
depends on the constants defined above, of which $\eta_{C}$ and $\rho_{NC}$
are still currently under research.) In real-world, sparser graphs, the loss
is likely to be amplified, as Dickerson’s Price of Fairness was amplified
dramatically Dickerson et al. (2014). In sparse graphs, it is much harder to
find a matching that matches all of $V^{O}$, $V^{S}$, and $V^{R}$, so losses
for both functions would likely increase. However, we informally argue that
TIME would maintain its advantage over SENS, as it, by nature, attempts to
minimize chances for losses. But at the very least, we prove that time
fairness is theoretically advantageous to sensitization fairness.

##  4 An Algorithm for Real-World Graphs

Given our results, we propose an algorithm for sparse graphs that emphasizes
matching critical patients while balancing both sensitization- and time-based
fairness. This algorithm simply breaks up the traditional one-batch solution
into four separate runs, so it is simply layered on top of current (or future)
kidney exchange solvers. The technique of layering an algorithm on top of
current solvers has been used by Dickerson et al. (2012), although their
algorithm is completely different (a parameter-learning weighting system for
dynamic matching).

######  Algorithm 4.1 (A batching algorithm for both fairnesses)

  1. 1.

The solver considers only pairs in $C_{t}$ and matches them to each other.
Unmatched pairs are passed down to the pool in Step 2.

  2. 2.

Leftover pairs from $C_{t}$ are matched to pairs in $H_{t}$. Unmatched pairs
in $C_{t}$ are passed down to the pool in Step 4; unmatched pairs in $H_{t}$
are passed down to pairs in Step 3.

  3. 3.

Pairs in $H_{t}$ are matched to other pairs in $H_{t}$. Leftover pairs are
passed down to Step 4.

  4. 4.

All remaining pairs are matched.

Figure 2: Illustration of Algorithm 4.1

In addition to relieving stress on the branch-and-price solver by addressing
smaller groups at a time, this algorithm also avoids a computationally-heavy
weighting function—valid in the future, but not for immediate implementation.

##  5 Conclusion

Before kidney exchanges can run, they must decide on a matching rule. Where
Dickerson Dickerson et al. (2014) showed that utilitarian matching rules
undermine sensitized patients in static settings, we theoretically showed that
sensitization-based matching rules result in patient losses in dynamic
settings. We also present a new definition of fairness, lexicographical time
fairness, which maximizes the matching of critically-ill, time-sensitive
pairs, and we propose a batched algorithm to balance time and sensitization
needs. We contribute by being one of the first to consider dynamics fairness,
uniquely evaluate fairness using losses, and the first to propose a time
fairness.

Our work suggests that time plays a larger role in kidney exchange than
currently acknowledged. Minimizing wait times and quickly clearing critical
patients likely requires more than a modification to current branch-and-price
solvers; they instead require an explicitly dynamic solver. We essentially
justify recent attempts to entirely reformulate static solvers into dynamic
ones, especially theoretical work in the formal Markov Decision Process
environment Akbarpour et al. (2014) Anderson et al. (2014). These solvers
naturally optimize time fairness by weighting matches based on long-term
utility with future-discounting; only sensitization fairness needs to be later
imposed.

In the end, it is important to remember that kidney problems affect over a
tenth of the United States population, making kidney exchange an important,
and so time-pressed, innovation. Yet the care we take to design matching rules
is more than theorizing; they affect the fairness, efficiency, and health of
us all.

## References

  * Abecassis et al. (2000) Michael Abecassis, Mark Adams, Patricia Adams, Robert M Arnold, and Carolyn R. Atkins.  Consensus Statement on the Live Organ Donor.  Journal of the American Medical Association, 284(22), December 2000\.
  * Abraham et al. (2007) David J. Abraham, Avrim Blum, and Tuomas Sandholm.  Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges.  In Proceedings of the 8th ACM Conference on Electronic Commerce, EC ’07, pages 295–304, New York, NY, USA, 2007. ACM.
  * Akbarpour et al. (2014) Mohammad Akbarpour, Shengwu Li, and Shayan Oveis Gharan.  Dynamic Matching Market Design.  arXiv: 1402.3643, February 2014.
  * Al-Aly et al. (2010) Ziyad Al-Aly, Angelique Zeringue, John Fu, Michael I. Rauchman, Jay R. McDonald, Tarek M. El-Achkar, Sumitra Balasubramanian, Diana Nurutdinova, Hong Xian, Kevin Stroupe, Kevin C. Abbott, and Seth Eisen.  Rate of Kidney Function Decline Associates with Mortality.  Journal of the American Society of Nephrology : JASN, 21(11):1961–1969, November 2010.
  * Anderson et al. (2014) R. Anderson, I. Ashlagi, D. Gamarnik, and Y. Kanoria.  A dynamic model of barter exchange.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1925–1933, San Diego, CA, USA, December 2014. Society for Industrial and Applied Mathematics.  DOI: 10.1137/1.9781611973730.129.
  * Ashlagi and Roth (2011) Itai Ashlagi and Alvin E. Roth.  Individual Rationality and Participation in Large Scale, Multi-Hospital Kidney Exchange.  Working Paper 16720, National Bureau of Economic Research, January 2011\.  DOI: 10.3386/w16720.
  * Ashlagi et al. (2013) Itai Ashlagi, Patrick Jaillet, and Vahideh H. Manshadi.  Kidney Exchange in Dynamic Sparse Heterogenous Pools.  arXiv: 1301.3509, January 2013.
  * Center (2017) Cedars-Sinai Kidney & Pancreas Transplant Center.  Highly Sensitized Transplants, 2017.
  * Dickerson et al. (2012) John P Dickerson, Ariel D. Procaccia, and Tuomas Sandholm.  Dynamic Matching via Weighted Myopia with Application to Kidney Exchange.  In Proceedings of the National Conference on Artificial Intelligence, volume 2, pages 1340–1346, Toronto, ON, Canada, 2012.
  * Dickerson et al. (2014) John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm.  Price of Fairness in Kidney Exchange.  In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, AAMAS ’14, pages 1013–1020, Richland, SC, 2014. International Foundation for Autonomous Agents and Multiagent Systems.
  * Hajaj et al. (2015) Chen Hajaj, John P. Dickerson, Avinatan Hassidim, Tuomas Sandholm, and David Sarne.  Strategy-Proof and Efficient Kidney Exchange Using a Credit Mechanism.  In AAAI, pages 921–928, 2015.
  * Kahng (2016) Anson Kahng.  Timing Objectives in Dynamic Kidney Exchange.  PhD thesis, Harvard University, Cambridge, MA, April 2016.
  * Procurement et al. (2017) Organ Procurement, Transplantation Network, US Department of Health, and Human Services.  National data.  Technical report, 2017.
  * Roth et al. (2004) Alvin Roth, Tayfun Sonmez, and M. Utku Unver.  Kidney Exchanges.  Quarterly Journal of Economics, 119(2):457–488, May 2004.
  * Sumida et al. (2016) Keiichi Sumida, Miklos Z. Molnar, Praveen K. Potukuchi, Fridtjof Thomas, Jun Ling Lu, Jennie Jing, Vanessa A. Ravel, Melissa Soohoo, Connie M. Rhee, Elani Streja, Kamyar Kalantar-Zadeh, and Csaba P. Kovesdy.  Association of Slopes of Estimated Glomerular Filtration Rate With Post-End-Stage Renal Disease Mortality in Patients With Advanced Chronic Kidney Disease Transitioning to Dialysis.  Mayo Clinic Proceedings, 91(2):196–207, February 2016.
  * Unver (2010) M. Utku Unver.  Dynamic Kidney Exchange.  Review of Economic Studies, 77, 2010.
  * U.S. Renal Data System et al. (2014) National Institute of Diabetes U.S. Renal Data System, National Institutes of Health, Digestive, and Kidney Diseases.  2013 annual data report: Atlas of end-stage renal disease in the united states.  Technical report, 2014.
  * U.S. Renal Data System et al. (2016) National Institute of Diabetes U.S. Renal Data System, National Institutes of Health, Digestive, and Kidney Diseases.  2016 usrds annual data report.  Technical report, 2016.