# Discovery of Scalar Mixed With SM Higgs Via Diboson Excess at the LHC

Sibo Zheng<EMAIL_ADDRESS>Department of Physics, Chongqing
University, Chongqing 401331, P. R. China

###### Abstract

The prospect for the discovery of scalar weakly mixed with the SM Higgs is
studied through the diboson signal excess at the Large Hadron Collider. Such
scalar usually exists in scalar singlet extended SM. For illustration to the
broad application of our scenario, the next-to-minimal supersymmetric model
and a real scalar singlet extened SM are stuided as two interesting examples.

##  I Introduction

The scalar with mass around $125$ GeV discovered at the Large Hadron Collider
(LHC) Higgs  establishes the Standard Model (SM) as the effective field theory
below the electroweak scale. Unfortunately, SM cannot be considered as a self-
consistent theory. One reason is that it stands at the critical point to
guarantee the electroweak vacuum stability higgscosm  for the observed Higgs
mass, which is further challenged by large quantum fluctuations vacuum  in the
early Universe. Another more obvious reason is that it doesn’t provide
reasonable candidate of dark matter, the relic density of which has been
measured in high precision by the Plank and WIMP 9-year data 1303.5076 .

Among new physics models proposed to address the problems above, there is
usually scalar $H$ of the same spin, parity, and quantum numbers as the SM-
like Higgs. Without no doubt they may mix with each other in various ways. The
magnitude of this mixing effect has been bounded above 1303.1812  in the light
of precise measurement on the SM Higgs couplings performed at the LHC.

Motived by the recent ATLAS experiment about the SM diboson excess 1506.00962
, we study the prospect for the discovery of scalar which weakly mixes with
the SM-like Higgs through the SM diboson excesses at the LHC. The main reason
for searching such scalar decaying into diboson channels is based on the fact
that through the mixing effect $H$ couples to the SM fermions and bosons
similarly to the SM-like Higgs, except that there is an universal scaling
factor smaller than unity. As a result, diboson decays $V_{i}V_{i}$ with
$V_{i}=\\{W,~{}Z\\}$ dominate others in the mass range $m_{H}\geq 200$ GeV.

The paper is organizied as follows. In Section II and III we address the
production cross section for $\sigma(pp\rightarrow H\rightarrow VV)$ at the 8
TeV and 14 TeV LHC for the mass range $100$ GeV $\leq m_{H}\leq$ $1000$ GeV in
model-independent way. This is achieved in terms of the measured production
cross section production ; 1101.0593  and decay HDECAY  for the SM-like Higgs.
While the background for SM diboson signal is reconstructed by using the data
of 20.3 $fb^{-1}$ at the 8 TeV LHC 111Similar analysis can be directly
performed once the background for SM diboson signal at the 14 TeV LHC is
measured.. Given different integrated luminosity the mass ranges for $5\sigma$
discovery at 8 TeV LHC will be explicitly work out for small, moderate and
large mixing effect, respectively.

Section IV is devoted to the application to new physics models. We show that
in two interesting examples, i.e., the next-to-minimal supersymmetric model
(NMSSM) and the scalar singlet extension of SM, some part of the parameter
space is exactly covered by the phenomenological study of Sec. II and III.
Finally, we conclude in Sec.V.

Figure 1: Production cross section for scalar $H$ at the LHC with $\sqrt{s}=8$
TeV (black color) and $14$ TeV (red color) respectively for three
representative values $\sin^{2}\alpha=\\{0.01,0.02,0.04\\}$.

##  II Production Cross Section at the LHC

When there is a new scalar state $H$ which has the same spin, parity and
quantum numbers as the SM-like Higgs $h$ they probably mix with each other. In
this section we discuss the production and decay of such scalar in the case of
weak mixing as allowed by the precise measurement on the SM Higgs couplings.
We focus on the discovery of this scalar through the SM diboson excess at the
LHC, which will shed light on the $WW$ and $ZZ$ excesses at $\sim 3\sigma$
level reported by the ATLAS collaboration.

Let us define the mass squared matrix for state vector $(H,h)$ in the
decoupling limit as,

$\displaystyle{}\left(\begin{array}[]{cc}m^{2}_{H}&0\\\ 0&m^{2}_{h}\\\
\end{array}\right)$ (3)

If the mixing between the SM Higgs $h$ and $H$ scalar can be ignored, in the
same spirit of what occurs in scalar dark matter model, there is no chance for
the discovery of $H$ at the LHC. Conversely, if the mixing is significant, $H$
would have been excluded by the LHC searches such as dijet, diphoton and four
lepton signals, etc. In other words, there is room only for a small mixing
effect, which can be realized by introducing an small off-diagonal element
$\Delta m^{2}$ into the mass squared matrix in Eq.(3),

$\displaystyle{}\left(\begin{array}[]{cc}m^{2}_{H}&\Delta m^{2}\\\ \Delta
m^{2}&m^{2}_{h}\\\ \end{array}\right)$ (6)

In the next section such realization will be shown to cover much of parameter
space of new physics models. Because of small $\Delta m^{2}$ the mass
eigenvalues will be slightly modified as,

$\displaystyle{}m^{2}_{H}$ $\displaystyle\rightarrow$ $\displaystyle
m^{2}_{H}+\frac{(\Delta m^{2})^{2}}{m^{2}_{H}-m^{2}_{h}},$ $\displaystyle
m^{2}_{h}$ $\displaystyle\rightarrow$ $\displaystyle m^{2}_{h}-\frac{(\Delta
m^{2})^{2}}{m^{2}_{H}-m^{2}_{h}}.$ (7)

Remarkably, the strengths of SM-like couplings $h-X_{i}-X_{i}$, where $X_{i}$
refers to the SM vector bosons and fermions, are reduced in compared with the
SM expectation, and conversely those of couplings $H-X_{i}-X_{i}$ are
enhanced. Note that their tree-level values are zero in the decoupling limit.
In the presence of the mixing effect these couplings are given by in
normalized to what the SM expects,

$\displaystyle{}\frac{g^{2}_{hXX}}{g^{2}_{h_{\text{SM}}XX}}=\cos^{2}\alpha,~{}~{}~{}~{}~{}~{}~{}~{}\frac{g^{2}_{HXX}}{g^{2}_{h_{\text{SM}}XX}}=\sin^{2}\alpha,$
(8)

where

$\displaystyle{}\tan(2\alpha)=\frac{2\Delta m^{2}}{m^{2}_{H}-m^{2}_{h}}.$ (9)

The present LHC experiments on the precise measurement of SM-like Higgs
coupling leads to an upper bound on the small quantity $\sin^{2}\alpha\leq
0.04$ 1303.1812 .

Figure 2: The production cross sections for SM diboson at the LHC with
$\sqrt{s}=8$ TeV. The three lines in the same color corresonds to
$\sin^{2}\alpha=\\{0.04,0.02,0.01\\}$ from top to bottom, respectively.
Figure 3: Same as Fig.2 but with $\sqrt{s}=14$ TeV instead.

The production cross section $\sigma\left(pp\rightarrow H\right)$ can be
obtained through that of the SM-like Higgs,

$\displaystyle{}\sigma\left(pp\rightarrow
H\right)=\tan^{2}\alpha\times\sigma\left(pp\rightarrow h_{\text{SM}}\right)$
(10)

This is true when $H$ couples to the SM fermions and vector bosons similar to
the SM-like Higgs expect an universal scaling factor $\sin\alpha$. The main
contribution to $\sigma\left(pp\rightarrow H\right)$ arises from the gluon
fusion and vector boson fusion processes. Adopt $m_{h}$ as a free parameter
instead of $125$ GeV, Fig.1 shows $\sigma\left(pp\rightarrow H\right)$ at the
LHC with the energy of mass center $\sqrt{s}=\\{8,14\\}$ TeV, respectively. In
Eq.(10) we have used $\sigma\left(pp\rightarrow h_{\text{SM}}\right)$ which
has been measured in terms of the reported data in production ; 1101.0593 . We
have chosen three representative values $\sin^{2}\alpha=\\{0.01,0.02,0.04\\}$
for comparison.

The property among the couplings $H-X-X$ may be violated in some specific
situation, e.g., in the parameter space of minimal supersymmetric SM model
with $\tan\beta\neq 1$. As in the large $\tan\beta$-region the b-quark fusion
process will dominate the production cross section for $H$ instead of gluon
fusion bfusion , as a result of enhanced $H-b-b$ and suppressed $H-t-t$
couplings.

Since the mixing effect is rather small, the branching ratio
$\text{Br}(H\rightarrow V_{i}V_{i})$ is mildly dependent on the mixing effect
through the possible decay $H\rightarrow hh$. Take the approximation in which
this channel is ignored, we show in Fig.2 and Fig.3 the production cross
sections of SM dibosons through the intermediate scalar $H$. We have not shown
the bi-quark and bi-lepton channels, as they are so tiny in compared with the
$WW$ and $ZZ$ channels. We refer the reader to HEDCAY HDECAY  for more details
about the branching ratios for each $H$ decay channel. See also 1101.0593 .

Among diboson decay chanels, $H\rightarrow gg$ and $H\rightarrow\gamma\gamma$
are bounded by the LHC Run I searches on dijet dijet  and $\gamma\gamma$
twogamma  signal, respectively,

$\displaystyle{}\sigma\left(pp\rightarrow
H\right)\times\text{Br}(H\rightarrow\text{gg})$ $\displaystyle\leq$
$\displaystyle 200~{}\text{fb},$ $\displaystyle\sigma\left(pp\rightarrow
H\right)\times\text{Br}(H\rightarrow\gamma\gamma)$ $\displaystyle\leq$
$\displaystyle 0.5~{}\text{fb}.$ (11)

In the light of Fig.2, we find that $H$ with mass below $\sim 200$ GeV has
been excluded. In what follows, we mainly focus on the range $300$ GeV $\leq
m_{H}\leq 1000$ GeV.

Very recently, the ATLAS collaboration reported both $WW$ and $ZZ$ excesses at
$3\sigma$ level 1506.00962  at the $8$ TeV LHC. Fig.2 clearly shows that
$\sigma\left(pp\rightarrow H\right)$ is far beneath $1$ fb for $m_{H}\sim 2$
TeV, therefore scalar $H$ in our scenario cannot serve as the origin of
observed excess. If this excess is further verified at the Run II of LHC, it
will imply that for scalar explanation its couplings to the SM fermions and
bosons are rather different from those in our scenario.

Figure 4: The contours for $5\sigma$ discovery through $ZZ$ decay at the $8$
TeV LHC for different integrated luminosities $\mathcal{L}=\\{10,50,200\\}$
$\text{fb}^{-1}$. Figure 5: Same as Fig.4 but $WW$ decay instead.

##  III Prospect for Discovery

In order to discuss the prospect for $5\sigma$ discovery for $H$, the SM
background for diboson production at the LHC should be reconstructed. In terms
of the data of 20.3 $\text{fb}^{-1}$ collected by the LHC Run I data for $ZZ$
production 1409.6190  and $WW$ production 1503.04677 , the production cross
sections $\sigma_{\text{SM}}\left(pp\rightarrow ZZ\right)$ and
$\sigma_{\text{SM}}\left(pp\rightarrow WW\right)$ can be reproduced
accordingly. See 1405.3447 ; 1405.1994  for other diboson channels.

By combining Fig.2 we show in Fig.4 and Fig.5 the mass ranges for the
$5\sigma$ discovery given different integrated luminositites
$\mathcal{L}=\\{10,50,200\\}$ $\text{fb}^{-1}$ at the $8$ TeV LHC. These
figures clearly indicate that

  * •

for the maximal mixing effect $\sin^{2}\alpha\simeq 0.04$, $m_{H}$ below $850$
($700$) GeV can be excluded with data of $20$ $\text{fb}^{-1}$ through the
$ZZ$ ($WW$) decay.

  * •

for moderate mixing $0.02\leq\sin^{2}\alpha<0.04$, $m_{H}$ below $1$ TeV can
be fully detected with data of $200$ $\text{fb}^{-1}$ through the $ZZ$ decay.

  * •

for small mixing effect $\sin^{2}\alpha<0.01$, there is no chance for the
discovery in the whole mass range $100$ GeV $\leq m_{H}\leq$ $1000$ GeV except
that we have significantly larger integrated luminosity.

The analysis can be performed for the 14 TeV LHC similarly. Once
$\sigma_{\text{SM}}\left(pp\rightarrow ZZ\right)$ and
$\sigma_{\text{SM}}\left(pp\rightarrow WW\right)$ are measured at the 14 TeV
LHC, it can be completed in terms of Fig.3.

##  IV Examples

In this section we apply the phenomenological insights in the previous two
sections to two interesting example, i.e., NMSSM and a real scalar singlet
extended SM. We show that either the NMSSM with Peccei-Quinn (PQ) symmetry
(IV.A), or the scalar singlet extension of SM with only quartic coupling
between singlet and Higgs (IV.B), is covered by our scenario in some part of
parameter space. These examples indicate that scalar weakly mixed with the SM-
like Higgs is the main signal at the LHC.

###  IV.1 NMSSM with PQ symmetry

The first example is the NMSSM with an approximate $U(1)$ PQ symmetry. The
parameter space of such model is composed of only five model parameters
$\\{\lambda,\kappa,A_{\lambda},\tan\beta,m^{2}_{s}\\}$ 222We follow the
conventions and notation in 0712.2903 . See also 1405.6907 ., in which
$\lambda$ and $\kappa$ appear in the Lagrangian as $\mathcal{L}\sim\lambda
SH_{\mu}H_{d}+\frac{\kappa}{3}S^{3}+\cdots$, and $A_{\lambda}$ refers to the
A-term. Under the decomposition,

$\displaystyle{}H_{u}^{0}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(h_{1}+i\pi_{1}),$ $\displaystyle H_{d}^{0}$
$\displaystyle=$ $\displaystyle\frac{1}{\sqrt{2}}(h_{2}+i\pi_{2}),$
$\displaystyle S$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(s+i\pi_{s}),$

we obtain the $3\times 3$ squared mass matrix of CP-even neutral scalars

$\displaystyle{}\mathcal{M}^{2}=\left(\begin{array}[]{ccccc}\frac{A_{\lambda}^{2}}{1+x}+(M^{2}_{Z}-\lambda^{2}\upsilon^{2})\sin^{2}2\beta+\cdots&-\frac{1}{2}(m^{2}_{Z}-\lambda^{2}\upsilon^{2})\sin
4\beta+\cdots&-A_{\lambda}\lambda\upsilon\cos 2\beta+\cdots\\\
\times&M^{2}_{Z}\cos^{2}2\beta+\lambda^{2}\upsilon^{2}\sin^{2}2\beta+\cdots&-A_{\lambda}\lambda\upsilon\sin
2\beta\frac{x}{1+x}+\cdots\\\
\times&\times&\lambda^{2}\upsilon^{2}(1+x)+\cdots\\\ \end{array}\right)$ (15)

in the basis $(H,h,s)$, where

$\displaystyle H$ $\displaystyle=$ $\displaystyle\cos\beta h_{2}-\sin\beta
h_{1},$ $\displaystyle h$ $\displaystyle=$ $\displaystyle\cos\beta
h_{1}+\sin\beta h_{2},$

and $x\equiv m^{2}_{S}/(\lambda\upsilon)^{2}$, with $\upsilon=174$ GeV. Terms
ignored in Eq.(15) vanish in the PQ limit, $\kappa\rightarrow 0$.

Let us show which scalar is the SM-like Higgs and which one plays the role of
$H$ in Sec.II. Impose the limit $\lambda\rightarrow 0$ and $\kappa\rightarrow
0$, all three scalars decouple and the mass for $h$ reads as
$\mathcal{M}^{2}_{22}\simeq M^{2}_{Z}\cos^{2}2\beta$, which reproduces the
well-known result in the case of MSSM. So $h$ serves as the SM-like Higgs, $H$
and $S$ mix with $h$ through the mixing terms $\mathcal{M}^{2}_{12}$ and
$\mathcal{M}^{2}_{23}$ in Eq.(15), and the magnitude of these mixing effects
is determined by $\lambda$, $\kappa$, etc. With the PQ symmetry the
requirement from the decoupling limit

$\displaystyle{}\mathcal{M}^{2}_{12}=0,~{}~{}~{}~{}\mathcal{M}^{2}_{23}=0$
(17)

can be satisfied in various situations.

  * •

Case I: $\sin 4\beta=0$, and $\lambda=0$. In this case the NMSSM is actually
not well defined.

  * •

Case II: $\sin 4\beta=0$, and $\sin 2\beta=0$. In this case effective $\mu$
term as given by $\mu_{\text{eff}}=A_{\lambda}\sin(2\beta)/2(1+x)$ vanishes.

  * •

Case III: $\sin 4\beta=0$, and $x=0$. This case is reasonable for small soft
mass $m_{s}$, which is true in some specific model buildings, e.g.,
conventional gauge mediation. The decoupling limit in this case correspond to
$\kappa=0$, $x=0$ and $\beta_{c}=\pi/4$.

Introduce a small deviation $\beta=\beta_{c}+\delta$, where
$\mid\delta\mid<<1$, it gives rise to small mixing between $h$ and $H$ through
non-zero $\mathcal{M}^{2}_{12}$, in which the mass matrix in Eq.(15) is
reduced to

$\displaystyle{}\mathcal{M}^{2}\simeq\left(\begin{array}[]{ccccc}A_{\lambda}^{2}&2\delta(m^{2}_{Z}-\lambda^{2}\upsilon^{2})&2\delta
A_{\lambda}\lambda\upsilon\\\ \times&M^{2}_{Z}&0\\\
\times&\times&\lambda^{2}\upsilon^{2}\\\ \end{array}\right)$ (21)

From Eq.(21) we obtain the mass eigenvalues,

$\displaystyle{}m^{2}_{H}$ $\displaystyle\simeq$ $\displaystyle
A^{2}_{\lambda}+\mathcal{O}(\delta^{4}),$ $\displaystyle m^{2}_{s}$
$\displaystyle\simeq$
$\displaystyle\lambda^{2}\upsilon^{2}+\mathcal{O}(\delta^{4}),$ $\displaystyle
m^{2}_{h}$ $\displaystyle=$ $\displaystyle
m^{2}_{Z}+\frac{3m^{4}_{t}}{4\pi^{2}\upsilon^{2}}\log\left(\frac{m^{2}_{\tilde{t}}}{m^{2}_{t}}\right).$
(22)

Here $m_{\tilde{t}}$ denotes the stop scalar mass. The non-zero matrix element
$\mathcal{M}^{2}_{13}$ contributes to order $\delta^{4}$ correction to masses
$m^{2}_{H}$ and $m^{2}_{s}$. For completeness, we outline mass eigenvalues for
CP-odd and charged scalars,

$\displaystyle{}m^{2}_{A_{1}}$ $\displaystyle\simeq$ $\displaystyle
m^{2}_{H}+m^{2}_{s},$ $\displaystyle m^{2}_{H^{\pm}}$ $\displaystyle\simeq$
$\displaystyle m^{2}_{W}+m^{2}_{H}-m^{2}_{s}.$ (23)

For the PQ Goldstone mode $m_{A_{2}}\sim 0$, and
$\mu_{\text{eff}}=A_{\lambda}/2$.

Through $\mathcal{M}^{2}_{13}$ scalar $s$ indirectly mixes with $h$ through
mixing with scalar $H$. Therefore, the mixing effect between $h$ and $s$ can
be ignored in compared with that of $h$ and $H$. This implies that NMSSM with
parameter choices in the case III, is effectively covered by the new physics
model discussed in Sec. II and III. In order to explain the observed Higgs
mass $m_{h}\simeq 125.5$ GeV Higgs  $m_{\tilde{t}}>1$ TeV is required similar
to the MSSM. Take these points into account scalar $H$ might be the main
signal at the LHC.

###  IV.2 SM With Scalar Singlet

Consider the scalar singlet extension of SM with a real scalar $s$. As a SM
singlet, $s$ can directly couple to the SM Higgs. We employ a $Z_{2}$ parity
333 It was firstly employed to keep $s$ stable, then used to construct the
minimal dark matter model MDM . Note that in this case no mixing between $s$
and $h$ occurs. under which $s$ is odd for simplifying the potential $V$,

$\displaystyle{}V(s,H)=\frac{\mu^{2}}{2}H^{2}+\frac{\lambda}{2}H^{4}+\frac{\mu^{2}_{s}}{2}s^{2}+\frac{\lambda_{s}}{2}s^{4}+\frac{\kappa}{2}s^{2}\mid
H\mid^{2}.$ (24)

For simplicity, we assume that all dimensionless couplings in Eq.(24) are
positive.

Figure 6: Contour of invisible branching ratio $h\rightarrow ss$ in the
parameter space of $m_{s}-\kappa$. The solid line corresponds to the present
bound $\text{Br}_{\text{inv}}\leq 0.29$.

Whether the mixing between $s$ and $h$ happens depends on the signs of
$\mu^{2}_{s}$, which corresponds to different vacuum structures. Write the
vacuum expectation values (vevs) as $\left<s\right>=\upsilon_{s}$ and
$\left<H\right>=\upsilon$, they must satisfy,

$\displaystyle{}\mu^{2}_{s}+\kappa\upsilon^{2}+2\lambda_{s}\upsilon^{2}_{s}$
$\displaystyle=$ $\displaystyle 0,$
$\displaystyle\mu^{2}+\kappa\upsilon^{2}_{s}+2\lambda\upsilon^{2}$
$\displaystyle=$ $\displaystyle 0.$ (25)

Expand the fields as $s=\upsilon_{s}+s$ and $H=(\upsilon+h/\sqrt{2},0)$, we
obtain the mass squared matrix for the basis $(h,~{}s)^{T}$,

$\displaystyle{}\mathcal{M}^{2}=\left(\begin{array}[]{cccc}2\lambda\upsilon^{2}&\frac{\kappa}{\sqrt{2}}\upsilon\upsilon_{s}\\\
\times&4\lambda_{s}\upsilon_{s}^{2}\end{array}\right)$ (28)

Eq.(28) and Eq.(IV.2) imply that mixing effect occurs only when the signs of
$\mu^{2}_{s}$ and $\mu^{2}$ are both negative. If so, the magnitude of mixing
effect between $h$ and $s$ is controlled by parameter $\kappa$.

For small $\kappa$ the LHC phenomenology of this model is totally covered by
the previous discussions in Sec. II and III. If $\lambda_{s}$ is also small,
$s$ can be further constrained by the decay $h\rightarrow ss$ for
$m_{s}<m_{h}/2$ ssm . Fig.6 shows the value of $\kappa$ consistent with the
present measurement on the Higgs invisible decay branching ratio
$\text{Br}_{\text{inv}}\leq 0.29$ invdecay  .

##  V Conclusion

In this paper we have considered the prospect for the discovery of SM singlet
which weakly mixes with the SM Higgs. Take into account the allowed magnitude
of the mixing effect by the precise measurement on the Higgs couplings, we
have shown the mass ranges for $5\sigma$ discovery at the 8 TeV LHC for
different integrated luminosities. This scenario can be applied to many
interesting new physics models. For illustration, we explicitly consider the
NMSSM and scalar singlet extension of SM, in which we show that our scenario
covers much of the parameter space for each case.

###### Acknowledgements.

This work is supported in part by the National Natural Science Foundation of
China under grant No.11247031 and 11405015.

## References

  * (1) G. Aad et al. [ATLAS Collaboration], “Combined search for the Standard Model Higgs boson using up to 4.9 fb-1 of $pp$ collision data at $\sqrt{s}=7$ TeV with the ATLAS detector at the LHC,” Phys. Lett. B 710, 49 (2012), arXiv:1202.1408 [hep-ex];
S. Chatrchyan et al. [CMS Collaboration], “Combined results of searches for
the standard model Higgs boson in $pp$ collisions at $\sqrt{s}=7$ TeV,” Phys.
Lett. B 710, 26 (2012), arXiv:1202.1488 [hep-ex].

  * (2) D. Buttazzo, G. Degrassi, P. P. Giardino, G. F. Giudice, F. Sala, A. Salvio and A. Strumia, “Investigating the near-criticality of the Higgs boson,” JHEP 1312, 089 (2013), arXiv:1307.3536 [hep-ph].
  * (3) A. Kobakhidze and A. Spencer-Smith, “Electroweak Vacuum (In)Stability in an Inflationary Universe,” Phys. Lett. B 722, 130 (2013), arXiv:1301.2846 [hep-ph];
A. Hook, J. Kearney, B. Shakya and K. M. Zurek, “Probable or Improbable
Universe? Correlating Electroweak Vacuum Instability with the Scale of
Inflation,” JHEP 1501, 061 (2015), arXiv:1404.5953 [hep-ph];
J. R. Espinosa, G. F. Giudice, E. Morgante, A. Riotto, L. Senatore, A. Strumia
and N. Tetradis, “The cosmological Higgstory of the vacuum instability,”
arXiv:1505.04825 [hep-ph].

  * (4) Planck Collaboration, “Planck 2013 results. XVI. Cosmological parameters,” Astron. Astrophys. 571, A16 (2014), arXiv:1303.5076 [astro-ph.CO].
  * (5) See, e.g., A. Falkowski, F. Riva and A. Urbano, “Higgs at last,” JHEP 1311, 111 (2013). arXiv:1303.1812 [hep-ph].
  * (6) G. Aad et al. [ATLAS Collaboration], “Search for high-mass diboson resonances with boson-tagged jets in proton-proton collisions at $\sqrt{s}$ = 8 TeV with the ATLAS detector,” arXiv:1506.00962 [hep-ex].
  * (7) https://twiki.cern.ch/twiki/bin/view/LHCPhysics/CERNYellowReportPageAt8TeV.
  * (8) S. Dittmaier et al. [LHC Higgs Cross Section Working Group Collaboration], “Handbook of LHC Higgs Cross Sections: 1. Inclusive Observables,” arXiv:1101.0593 [hep-ph].
  * (9) A. Djouadi, J. Kalinowski and M. Spira, “HDECAY: A Program for Higgs boson decays in the standard model and its supersymmetric extension,” Comput. Phys. Commun. 108, 56 (1998), [hep-ph/9704448].
  * (10) D. A. Dicus and S. Willenbrock, “Higgs Boson Production from Heavy Quark Fusion,” Phys. Rev. D 39, 751 (1989);
A. Arbey, M. Battaglia and F. Mahmoudi, “Supersymmetric Heavy Higgs Bosons at
the LHC,” Phys. Rev. D 88, no. 1, 015007 (2013), arXiv:1303.7450 [hep-ph].

  * (11) G. Aad et al. [ATLAS Collaboration], “Search for new phenomena in the dijet mass distribution using $p-p$ collision data at $\sqrt{s}=8$ TeV with the ATLAS detector,” Phys. Rev. D 91, no. 5, 052007 (2015), arXiv:1407.1376 [hep-ex];
V. Khachatryan et al. [CMS Collaboration], “Search for resonances and quantum
black holes using dijet mass spectra in proton-proton collisions at
$\sqrt{s}=$ 8 TeV,” Phys. Rev. D 91, no. 5, 052009 (2015), arXiv:1501.04198
[hep-ex].

  * (12) G. Aad et al. [ATLAS Collaboration], “Search for high-mass diphoton resonances in $pp$ collisions at $\sqrt{s}=8$ TeV with the ATLAS detector,” arXiv:1504.05511 [hep-ex].
  * (13) G. Aad et al. [ATLAS Collaboration], “Search for resonant diboson production in the $\mathrm{\ell\ell}q\bar{q}$ final state in $pp$ collisions at $\sqrt{s}=8$ TeV with the ATLAS detector,” Eur. Phys. J. C 75, no. 2, 69 (2015), arXiv:1409.6190 [hep-ex].
  * (14) G. Aad et al. [ATLAS Collaboration], “Search for production of $WW/WZ$ resonances decaying to a lepton, neutrino and jets in $pp$ collisions at $\sqrt{s}=8$ TeV with the ATLAS detector,” Eur. Phys. J. C 75, no. 5, 209 (2015), arXiv:1503.04677 [hep-ex].
  * (15) V. Khachatryan et al. [CMS Collaboration], “Search for massive resonances decaying into pairs of boosted bosons in semi-leptonic final states at $\sqrt{s}=$ 8 TeV,” JHEP 1408, 174 (2014), arXiv:1405.3447 [hep-ex].
  * (16) V. Khachatryan et al. [CMS Collaboration], “Search for massive resonances in dijet systems containing jets tagged as W or Z boson decays in pp collisions at $\sqrt{s}$ = 8 TeV,” JHEP 1408, 173 (2014), arXiv:1405.1994 [hep-ex].
  * (17) R. Barbieri, L. J. Hall, A. Y. Papaioannou, D. Pappadopulo and V. S. Rychkov, “An Alternative NMSSM phenomenology with manifest perturbative unification,” JHEP 0803, 005 (2008), arXiv:0712.2903 [hep-ph].
  * (18) S. Zheng, “Perturbative $\lambda$-Supersymmetry and Small $\kappa$-Phenomenology,” Eur. Phys. J. C 75, no. 5, 195 (2015), arXiv:1405.6907 [hep-ph].
  * (19) V. Silveira and A. Zee, “Scalar Phantoms,” Phys. Lett. B 161, 136 (1985) ;
J. McDonald, “ Gauge singlet scalars as cold dark matter,” Phys. Rev. D 50,
3637 (1994), [hep-ph/0702143];
C. Burgess, M. Pospelov, and T. ter Veldhuis, “ The Minimal model of
nonbaryonic dark matter: A Singlet scalar,” Nucl. Phys. B 619, 709 (2001),
[hep-ph/0011335].

  * (20) D. O’Connell, M. J. Ramsey-Musolf and M. B. Wise, “Minimal Extension of the Standard Model Scalar Sector,” Phys. Rev. D 75, 037701 (2007), [hep-ph/0611014];
V. Barger, P. Langacker, M. McCaskey, M. J. Ramsey-Musolf and G. Shaughnessy,
“LHC Phenomenology of an Extended Standard Model with a Real Scalar Singlet,”
Phys. Rev. D 77, 035005 (2008), arXiv:0706.4311 [hep-ph].

  * (21) G. Aad et al. [ATLAS Collaboration], “Search for an Invisibly Decaying Higgs Boson Produced via Vector Boson Fusion in pp Collisions at $\sqrt{s}=8$ TeV using the ATLAS detector at the LHC,” ATLAS-CONF-2015-004.


11institutetext: Queen’s University Belfast, UK
11email<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>11email:
<EMAIL_ADDRESS>
# Exploring Rawlsian Fairness for
K-Means Clustering

Stanley Simoes Deepak P Muiris MacCarthaigh

###### Abstract

We conduct an exploratory study that looks at incorporating John Rawls’ ideas
on fairness into existing unsupervised machine learning algorithms. Our focus
is on the task of _clustering_ , specifically the _k-means clustering_
algorithm. To the best of our knowledge, this is the first work that uses
Rawlsian ideas in clustering. Towards this, we attempt to develop a
_postprocessing_ technique _i.e._ , one that operates on the cluster
assignment generated by the standard k-means clustering algorithm. Our
technique perturbs this assignment over a number of iterations to make it
fairer according to Rawls’ _difference principle_ while minimally affecting
the overall utility. As the first step, we consider two simple perturbation
operators – $\mathbf{R_{1}}$ and $\mathbf{R_{2}}$ – that reassign examples in
a given cluster assignment to new clusters; $\mathbf{R_{1}}$ assigning a
single example to a new cluster, and $\mathbf{R_{2}}$ a pair of examples to
new clusters. Our experiments on a sample of the Adult dataset demonstrate
that both operators make meaningful perturbations in the cluster assignment
towards incorporating Rawls’ difference principle, with $\mathbf{R_{2}}$ being
more efficient than $\mathbf{R_{1}}$ in terms of the number of iterations.
However, we observe that there is still a need to design operators that make
significantly better perturbations. Nevertheless, both operators provide good
baselines for designing and comparing any future operator, and we hope our
findings would aid future work in this direction.

###### Keywords:

fairness unsupervised machine learning clustering.

##  1 Introduction

While traditional machine learning (ML) algorithms aim to maximise utility
through discrimination, they are now being increasingly regulated by law so as
to prevent any unjustifiable discrimination in the society, especially when
these algorithms are deployed on a large scale and can heavily influence
people’s life chances. These laws provide the interpretation of fairness
(_e.g._ : the _four-fifths rule_
111https://www.law.cornell.edu/cfr/text/29/1607.4 in the US and the _Equality
Act 2010_ 222https://www.legislation.gov.uk/ukpga/2010/15/contents in the UK)
which existing algorithms are required to comply with. The challenge lies in
translating these legal interpretations of fairness, which are in natural
language, to mathematical formulations that can be incorporated in ML
algorithms with minimal impact on the utility of these algorithms.

Among the many ideas of justice and fairness put forth by political
philosophers and social scientists over time, the ML research community has
looked at the idea of fairness that is computationally easy to model such as
individual fairness [6] and group fairness [14]. However, this idea does not
have enough support from the justice and fairness space. We take a novel and
different route in this paper: we look at the ideas of _John Rawls_
333https://plato.stanford.edu/entries/rawls/ – an influential 20th century
moral and political philosopher in liberal tradition – and attempt to
incorporate his ideas of fairness in unsupervised ML. Compared to other ideas,
the Rawlsian ideas are time-tested, and a good mix of pragmatism and
principledness, but incorporating them into ML algorithms is challenging.

In general, ideas of fairness can be incorporated in existing ML algorithms in
3 ways –  (i) _preprocessing_ : where the input is processed to ensure
fairness before being fed to the ML algorithm,  (ii) _inprocessing_ : where
the ML algorithm is altered to incorporate the fairness criteria (_e.g._ : by
adding fairness constraints to the optimisation criterion), and  (iii)
_postprocessing_ : where the output of the ML algorithm is processed to make
it fairer  . Preprocessing and postprocessing techniques can be used with any
off-the-shelf ML algorithm with no modification, which is not the case with
the inprocessing techniques. Existing ML algorithms can thus be easily
augmented to produce fairer outputs through preprocessing and postprocessing
techniques. On the other hand, the inprocessing techniques are known to have
both better utility and better fairness than the other two.

In this paper, we focus on _clustering_ – an unsupervised ML task. We
specifically look at the _k-means clustering_ algorithm [8], a well-known
unsupervised ML algorithm that is used to partition a collection of examples
into disjoint sets called _clusters_ such that similar examples are assigned
to the same cluster. We look at the k-means clustering algorithm with an
additional constraint of satisfying Rawls’ _difference principle_ [15]. In
other words, we allow the overall utility of the obtained clusters to be sub-
optimal as long as the least-advantaged sensitive group has the greatest
utility. We work towards developing a _postprocessing_ technique that perturbs
the output of the standard k-means clustering algorithm to incorporate the
difference principle. While there has been research on the intersection of
fairness and clustering, to the best of our knowledge, this is the first to
attempt to incorporate Rawlsian ideas in clustering. Although this work is
exploratory, we hope that this report of our experiences would aid future work
in this direction.

##  2 The Difference Principle and Rawlsian Point

In his book _Justice as Fairness: A Restatement_ , John Rawls states the
_difference principle_ as

> “ _Social and economic inequalities are to satisfy two conditions: first,
> they are to be attached to offices and positions open to all under
> conditions of fair equality of opportunity; and second, they are to be to
> the greatest benefit of the least-advantaged members of society._ ” ([15])

We focus on the second condition: “ _they [social and economic inequalities]
are to be to the greatest benefit of the least-advantaged members of society_
”. For the experiments outlined in this paper, we interpret the above
statement as the members of a society belonging to one of two sensitive social
groups (_e.g._ : Male or Female)444We use binary genders for sake of
illustration only., one being the more advantaged group and the other the less
advantaged group.

###  2.1 Terminology

In the context of clustering, we refer to the _Rawlsian point_ as the cluster
assignment where the difference principle is satisfied _i.e._ , the utility to
the least-advantaged members of society is the greatest, and we refer to such
a cluster assignment as the _Rawlsian k-means clusters_. In contrast, the
classical k-means clustering algorithm by design returns a cluster assignment
where the sum of individual utilities is (approximately) maximised; we refer
to this point as the _utilitarian point_ , and the corresponding cluster
assignment as the _utilitarian k-means clusters_. This paper looks at binary
sensitive attributes _i.e._ , we assume that all examples in the dataset
belong to one of two sensitive groups. We refer to the sensitive group with
the lower utility as the less advantaged group (LAG) and the one with the
higher utility as the more advantaged group (MAG). Thus, the LAG and MAG are
defined on the sensitive attribute. Note that the sensitive attribute is _not_
used in the k-means clustering algorithm.

##  3 Problem statement

We attempt to develop a postprocessing technique that operates on the output
of the k-means clustering algorithm, returning a cluster assignment that
corresponds to the Rawlsian point _i.e._ , the Rawlsian k-means clusters. This
requires that the Rawlsian point does indeed exist. This leads us to the
following questions:

  1. 1.

Does there exist a cluster assignment that corresponds to (or is an
approximate of) the Rawlsian point? (Section 5)

  2. 2.

Can we reach this point starting from the utilitarian point _i.e._ , the point
of highest utility achieved by the classical k-means clustering algorithm?
(Section 6)

###  3.1 Notation

Let $\mathcal{X}=[\ldots,x,\ldots]$ be a collection of examples defined over a
set of non-sensitive attributes $\mathcal{N}$ and a single binary sensitive
attribute $S=\\{0,1\\}$. For any example $x$, let $x.n$ denote its values for
the non-sensitive attributes and $x.s$ denote its value for the sensitive
attribute. Also, let $x.n\in[0,1]^{|\mathcal{N}|}$ and $x.s\in\\{0,1\\}$. Note
that the non-sensitive attributes $\mathcal{N}$ are the only attributes used
for clustering; the clustering algorithm does not use the sensitive attribute
$S$.

The k-means clustering algorithm assigns a label to each example based on the
example’s distance from the cluster centroids, thus yielding a cluster
assignment $\mathcal{C}=\\{\ldots,C,\ldots\\}$ with $|\mathcal{C}|=k$, where
each cluster $C$ is a set of examples having the same label and $k$ is the
number of clusters to be generated. We additionally define the _utility_
$u(x)$ of an example $x$ as

$u(x)=\delta-d(x.n,C)$ (1)

where the constant $\delta$ is the maximum possible distance between two
examples, and $d(x.n,C)$ is the distance of example $x$ from the nearest
cluster centroid. Further, the utility of a sensitive group $\alpha$ is
computed as

$U(\alpha)=\frac{1}{|\mathcal{X}_{\alpha}|}\sum_{x\in\mathcal{X}_{\alpha}}u(x)$
(2)

where $\mathcal{X}_{\alpha}$ denotes the set of examples in $\mathcal{X}$
belonging to the sensitive group $\alpha$ _i.e._ ,
$\mathcal{X}_{\alpha}=\\{x|x\in\mathcal{X},x.s=\alpha\\}$. The overall utility
of a cluster assignment is the average utility of all examples in the dataset.

In the next section we describe the Adult dataset which is central to this
exploratory study, and in the subsequent sections we attempt to address the
questions outlined above.

##  4 Dataset

We use the publicly available Adult
dataset555https://archive.ics.uci.edu/ml/datasets/adult from the UCI
repository [5] in our experiments. The Adult dataset has been heavily used in
the fairness literature. It consists of 15 attributes and 30718 examples with
no missing values. We use 8 non-sensitive attributes, 1 sensitive attribute,
and the predictor. Table 1 lists out the attributes from this dataset that are
used for preprocessing, clustering, and evaluation in our experiments.

| type | name
---|---|---
Sensitive | categorical | sex
Non-sensitive | continuous | age
|  | education-num
|  | capital-gain
|  | capital-loss
|  | hours-per-week
| categorical | workclass
|  | education
|  | occupation
Predictor | categorical | annual-income
Table 1: Attributes from the Adult dataset used in our experiments. Only the
non-sensitive attributes are used in the clustering algorithm. The sensitive
attribute is used only for computing the utilities of the sensitive groups.
The predictor attribute is used only when preprocessing the dataset.

#### Preprocessing

We follow the steps in previous work [1] for preprocessing the dataset. The
non-sensitive attributes (used for clustering) are preprocessed as follows:

  * •

continuous: scaled and translated to the range $[0,1]$.

  * •

categorical: one hot encoded. To ensure that the maximum squared distance
between any two examples for this attribute is 1, the value for the ‘hot’
position is set to $\frac{1}{\sqrt{2}}$.

Consequently, the maximum distance between any two values of a single non-
sensitive attribute is 1. As we use 8 non-sensitive attributes, the maximum
possible distance $\delta$ between any two examples is 8. We then undersample
for parity across the predictor attribute. The resulting dataset contains 42
non-sensitive attributes and 1 sensitive attribute. Finally, we sample 500
examples from each predictor class for a total of 1000 examples. Table 2 shows
the distribution of sensitive groups in the sampled dataset.

sex | # of examples | % of examples
---|---|---
Female | 267 | 26.7%
Male | 733 | 73.3%
Table 2: Distribution of sensitive groups (Female, Male) in the sampled
dataset (1000 examples).

##  5 Existence of Rawlsian k-means clusters

Before devising a technique for obtaining the Rawlsian k-means clusters, we
need to determine whether such a cluster assignment indeed exists. Since it is
impractical to enumerate and evaluate the utilities of all possible cluster
assignments, we instead perform several runs of the k-means algorithm on our
dataset with different initial centroids to find an approximate. Note that
either of the sensitive groups may be less (or more) advantaged; in case of
the Adult dataset, we only consider those cluster assignments where the
minority group (_i.e._ , Female) is the less advantaged group. Figure 1 shows
the utilities of these cluster assignments, with the utility of the more
advantaged group (MAG) on the $x$-axis and the less advantaged group (LAG) on
the $y$-axis.

(a) points generated by the 5000 runs

(b) zooming in to the utilitarian point and (approximate) Rawlsian point

Figure 1: Scatter plot of points in the MAG-LAG utility space generated by
5000 runs of the k-means clustering algorithm with different initial
centroids, $k=5$, on our Adult dataset, and majority (Male) as the more
advantaged group (MAG) and minority (Female) as the less advantaged group
(LAG). Each point in this space corresponds to the cluster assignment obtained
from a single run. The hue of a point indicates the overall utility, with
darker being better. Points on the 45° red dashed line are such that the
utilities for MAG and LAG are equal. By design of this experiment _i.e._ , the
minority group (Female) being the less advantaged group, all points are always
south of this 45° line. The horizontal/vertical olive dashed lines intersect
at the point with the highest LAG (Female) utility, but has low overall
utility since Female is a minority group (see Table 2). This olive point is an
approximate for the Rawlsian point. The horizontal/vertical blue dashed lines
intersect at the point with the highest MAG (Male) utility, and is also of the
highest overall utility (_i.e._ , the utilitarian point) since Male is a
majority group. The histograms to the top and right of each scatter plot
indicate the density of the points.

It can be seen in Figure 1 that there is indeed a point (shown as an olive
plus point) corresponding to a k-means clustering that has a better utility
for the less advantaged group than the utilitarian point (shown as a blue plus
point). The olive plus point is thus an approximate for the Rawlsian point.
Note that this point may not be the actual Rawlsian point; we use it as an
approximate for the Rawlsian point in the experiment discussed in Section 6 as
evaluating all possible cluster assignments is not possible.

##  6 Reaching the approximate Rawlsian point

We saw in the previous section there is no mechanism to generate points in the
MAG-LAG utility space other than through the k-means algorithm itself. We thus
performed several runs of the k-means algorithm to see whether doing so can
reveal spaces where the Rawlsian point is likely to be and whether we can
navigate to these spaces. Now, the histograms to the top and right of the
scatter plots in Figure 1, indicate that the generated points are concentrated
near the utilitarian point (the blue plus point). This would suggest that a
k-means algorithm would likely generate a cluster assignment that corresponds
to a point closer to the utilitarian point. Thus, we select the utilitarian
cluster assignment _i.e._ , the one with highest overall utility (shown as a
blue plus point in Figure 1) as the starting point for our postprocessing
technique.

We now outline our postprocessing technique for arriving at the approximate
Rawlsian point starting from the utilitarian point. Our goal is to find a
_reassignment_ of examples to new clusters so that we reach the approximate
Rawlsian point (shown as a olive plus point). To do so, we apply a series of
reassignment operations to the utilitarian cluster assignment such that we
gradually move above the horizontal blue line in the MAG-LAG utility space
toward the Rawlsian point. The general outline of our technique is shown in
Algorithm 1.

Algorithm 1 Traverse

1:$\mathcal{X}$, $\mathcal{C}$

2:$\mathcal{C}$

3:while $\mathcal{C}$ has not changed do

4: $O\leftarrow$ GenerateOperations$(\mathcal{X},\mathcal{C})$
$\triangleright$ Generate operations (Section 7)

5: $o\leftarrow$ select the best operation in $O$ $\triangleright$ (Section
6.1)

6: if $o$ is not $\phi$ then

7: $\mathcal{C}\leftarrow$ apply the selected operation $o$

8: end if

9:end while

We discuss the GenerateOperations algorithm in Section 7, and how the best
operation is selected and applied in Section 6.1.

###  6.1 Selecting and applying the best reassignment operation

We select the best reassignment operation among those generated according to
the following order of preference:

  1. 1.

Among the operations that generate a point in the north-east of the current
point in the MAG-LAG utility space, select the operation that corresponds to
the point with highest overall utility.

  2. 2.

If no such operation exists, among the operations that generate a point in the
_skyline_ of points in the north-west of the current point, select the
operation that corresponds to the point with highest overall utility.

  3. 3.

If no such operation exists, select the null operation $\phi$, which indicates
that no reassignment is done and hence the cluster assignment is unchanged.

The _skyline_ $S$ of a set of points $Q$ is defined as those points in the
MAG-LAG utility space where $\forall q\in$ Q, $\exists s\in S$ such that
either  (i) $q==s$(_i.e._ , $q$ is in the skyline), or  (ii)
$u_{\mathit{LAG}}(q)<u_{\mathit{LAG}}(s)$and
$u_{\mathit{MAG}}(q)<u_{\mathit{MAG}}(s)$ (_i.e._ , $q$ is worse than $s$ for
both LAG and MAG), where $u_{\alpha}(x)$ is the utility of sensitive group
$\alpha$ for the point $x$ . Moving through the skyline ensures that we select
the operation with the least drop in overall utility and maximum gain in LAG
utility.

Applying the selected reassignment operation is straightforward; we change the
current cluster assignment (_i.e._ , current labels of the examples) as
specified by the selected operation, and use the new cluster assignment as the
starting point for the next iteration.

##  7 Reassignment operators

Our goal is to construct an operator that reassigns a number of examples in
the current cluster assignment to new clusters, thus generating a new cluster
assignment – the Rawlsian cluster assignment – having a higher LAG utility
while minimally affecting the overall utility. By applying a series of
instantiations of this operator to the utilitarian cluster assignment, we hope
to reach the approximate Rawlsian point. We explore two simple operators
$\mathbf{R_{1}}$ and $\mathbf{R_{2}}$ which are now detailed.

###  7.1 Reassignment operator $\mathbf{R_{1}}$

The reassignment operator $\mathbf{R_{1}}$ operating on a tuple
$(x,C^{\prime})$ takes a single example $x$ from the current cluster
assignment $\mathcal{C}$ and reassigns it to a different cluster $C^{\prime}$
(_i.e._ , a different label) thus yielding a new cluster assignment. The
number of possible operations666An _operation_ is an instantiated operator.
generated for $\mathbf{R_{1}}$ is thus $n\times(k-1)$. Algorithm 2 outlines
the GenerateOperationsR1 algorithm which is the $\mathbf{R_{1}}$ variant of
the GenerateOperations algorithm.

Algorithm 2 GenerateOperationsR1

1:$\mathcal{X}$, $\mathcal{C}$

2:$O$

3:Initialise $O$ to an empty set

4:for each example-cluster tuple
$(x,C^{\prime})\in\mathcal{X}\times\mathcal{C}$ do

5: Apply $\mathbf{R_{1}}(x,C^{\prime})$ to get a new cluster assignment
$\mathcal{C}^{\prime}$

6: Obtain the corresponding point in the MAG-LAG utility space

7: if the point has a higher LAG utility than the current point then

8: Add $(x,C^{\prime})$ to $O$

9: end if

10: Discard $\mathcal{C}^{\prime}$

11:end for

Figure 2 shows the trajectory of points in the MAG-LAG utility space generated
by employing GenerateOperationsR1 in Algorithm 1. We see that the algorithm
takes small steps (each step corresponds to the application of one
$\mathbf{R_{1}}$ operation) in the correct direction towards the approximate
Rawlsian point but ends up with the LAG and MAG utilities being equal.
Notably, the approximate Rawlsian point (olive plus point in the figure) has a
better LAG (Female) utility than all generated points. There is thus a need
for improvement. Another drawback of $\mathbf{R_{1}}$ is that its repeated
application may be inefficient because the amount of movement towards the
approximate Rawlsian point in each iteration is negligible. Additionally, the
reassignment operation may never be undone.

Figure 2: Trajectory of points (in orange) generated in the MAG-LAG utility
space by Traverse (Algorithm 1) using the $\mathbf{R_{1}}$ operator (Section
7.1). Points on the 45° red dashed line are such that the utilities for MAG
and LAG are equal. The olive plus point corresponds to the approximate
Rawlsian point which we would like the Traverse algorithm to arrive at. Recall
that the Rawlsian point corresponds to the cluster assignment where the
utility of the less advantaged group is the greatest. The algorithm starts
from the utilitarian point (indicated by the blue plus point) and repeatedly
applies a $\mathbf{R_{1}}$ operation thus yielding a new cluster assignment,
with each cluster assignment generating a corresponding point in the utility
space. This figure contains 261 such generated points. The orange line that
connects the generated sequence of points together indicates the trajectory of
the algorithm which is generally moving in the north-west direction, and can
be seen to terminate at the red line _i.e._ , where the utilities for MAG and
LAG are equal.

###  7.2 Pair reassignment operator $\mathbf{R_{2}}$

To overcome the inefficiency limitation of $\mathbf{R_{1}}$, we instead select
pairs of examples to be reassigned. We define the _pair reassignment_ operator
as follows: The pair reassignment operator $\mathbf{R_{2}}$ operating on a
pair of tuples $(x_{1},C^{\prime}_{1}),(x_{2},C^{\prime}_{2})$ takes a pair of
distinct examples $x_{1}$ and $x_{2}$ ($x_{1}\neq x_{2}$) from the current
cluster assignment $\mathcal{C}$ and reassigns them to new clusters
$C^{\prime}_{1}$ and $C^{\prime}_{2}$ thus yielding a new cluster assignment.
One $\mathbf{R_{2}}$ operation is thus equivalent to two $\mathbf{R_{1}}$
operations on two distinct examples $x_{1}$ and $x_{2}$.

Two issues arise when using $\mathbf{R_{2}}$ for navigating the MAG-LAG
utility space:

  1. 1.

The number of possible operations using $\mathbf{R_{2}}$ is ${n\choose
2}(k-1)^{2}$, where $n$ is the number of examples and $k$ is the number of
clusters. In our experiment, this evaluates to nearly 8 million possible
operations; it is impractical to calculate the utilities of all such
operations. In contrast, the number of possible operations using
$\mathbf{R_{1}}$ is $n\times(k-1)$ which is significantly smaller.

  2. 2.

On inspection of a sample of these $\mathbf{R_{2}}$ operations, we found that
a large chunk (around 62%) generate points with lower LAG utilities than the
current point _i.e._ , they move away from the Rawlsian point, and hence are
not useful.

Thus, there is a need to intelligently generate $\mathbf{R_{2}}$ operations
whose corresponding points have higher LAG utilities than the current point.
Algorithm 3 outlines the GenerateOperationsR2 algorithm which is the
$\mathbf{R_{2}}$ variant of the GenerateOperations algorithm. Instead of
generating all possible operations, we use a heuristic for pruning the set of
example-cluster tuples (Lines 1 to 4 in Algorithm 3). This heuristic is based
on the assumption that if $\mathbf{R_{1}}$ does not generate a point with
higher LAG utility for some tuple $(x,C^{\prime})$, then no $\mathbf{R_{2}}$
operation instantiated with $(x,C^{\prime})$ – _i.e._ , neither
$\mathbf{R_{2}}(x,C^{\prime},\cdot,\cdot)$ nor
$\mathbf{R_{2}}(\cdot,\cdot,x,C^{\prime})$ – will generate a point with higher
LAG utility than the current point. Next, the remaining tuples are separately
ranked on LAG utility and overall utility, and only the top reassignments (1%
to 5%) from the two rankings are retained. This yields a set of good example-
cluster tuples $T_{\mathit{good}}\subset\mathcal{X}\times\mathcal{C}$ that can
be later used to instantiate $\mathbf{R_{2}}$. The rest of the algorithm is
similar to Algorithm 2.

Algorithm 3 GenerateOperationsR2

1:$\mathcal{X}$, $\mathcal{C}$

2:$O$

3:$T\leftarrow$ GenerateOperationsR1$(\mathcal{X},\mathcal{C})$

4:$T_{\mathit{LAG}}\leftarrow$ top $p$% of $T$ ranked on LAG utility

5:$T_{\mathit{overall}}\leftarrow$ top $q$% of $T$ ranked on overall utility

6:$T_{\mathit{good}}\leftarrow T_{\mathit{LAG}}\cup T_{\mathit{overall}}$

7:Initialise $O$ to an empty set

8:for each pair of example-cluster tuples
$((x_{1},C^{\prime}_{1}),(x_{2},C^{\prime}_{2}))\in T_{\mathit{good}}\times
T_{\mathit{good}}$ do

9: Apply $\mathbf{R_{2}}(x_{1},C^{\prime}_{1},x_{2},C^{\prime}_{2})$ to get a
new cluster assignment $\mathcal{C}^{\prime}$

10: Obtain the corresponding point in the MAG-LAG utility space

11: if the point has a higher LAG utility than the current point then

12: Add $(x_{1},C^{\prime}_{1},x_{2},C^{\prime}_{2})$ to $O$

13: end if

14: Discard $\mathcal{C}^{\prime}$

15:end for

Figure 3 compares the trajectories of points in the MAG-LAG utility space
generated by employing GenerateOperationsR1 and GenerateOperationsR2 in
Algorithm 1. We can see that while $\mathbf{R_{2}}$ improves upon the
inefficiency limitation of $\mathbf{R_{1}}$ (requiring 152 iterations as
compared to 261 iterations by $\mathbf{R_{1}}$), it follows nearly an
identical trajectory as $\mathbf{R_{1}}$ and hence still suffers from its
other limitations _i.e._ , ends up with the LAG and MAG utilities being equal,
and the operation once applied may never be undone.

Figure 3: Trajectories of points generated in the MAG-LAG utility space by
Traverse (Algorithm 1) using the $\mathbf{R_{1}}$ operator (in orange) and the
$\mathbf{R_{2}}$ operator (in green). Points on the 45° red dashed line are
such that the utilities for MAG and LAG are equal. The olive plus point
corresponds to the approximate Rawlsian point which we would like the Traverse
algorithm to arrive at. Recall that the Rawlsian point corresponds to the
cluster assignment where the utility of the less advantaged group is the
greatest. The algorithm starts from the utilitarian point (indicated by the
blue plus point) and repeatedly applies a $\mathbf{R_{1}}$ (or
$\mathbf{R_{2}}$) operation thus yielding a new cluster assignment, with each
cluster assignment generating a corresponding point in the utility space.
$\mathbf{R_{1}}$’s trajectory consists of 261 such generated points, and
$\mathbf{R_{2}}$’s trajectory consists of 152 such generated points. Similar
to $\mathbf{R_{1}}$’s trajectory, $\mathbf{R_{2}}$ moves in the north-west
direction terminating at the red line _i.e._ , where the utilities for MAG and
LAG are equal.

##  8 Related Work

While there has been significant research on fairness in machine learning in
recent years, we look at those works that are relevant to this paper _i.e._ ,
(i) Rawlsian ideas of fairness in machine learning, and  (ii) fair algorithms
for clustering.  .

Rawlsian ideas of fairness in ML: The few existing works that explore Rawls’
ideas of fairness in ML are in the supervised setting. The hardness of
adapting Rawlsian principles into algorithms is apparent from these works. For
example, Shah et al [16] propose a classifier that minimises the error rate of
the worst-off sensitive group; they call this a Rawls classifier. Hashimoto et
al [7] employ Rawlsian ideas to mitigate the amplification of representation
disparity in empirical risk minimization. We have not come across any work
that explores Rawls’ ideas in the unsupervised setting.

Fair algorithms for clustering: These can be broadly categorised based on the
notion of fairness _i.e._ ,  (i) individual fairness [9, 11, 12], and  (ii)
group fairness [3, 4, 10] . Further, these algorithms differ on how the
fairness criterion is enforced (_i.e._ , preprocessing, inprocessing, or
postprocessing). For example, Chierichetti et al [3] propose a preprocessing
technique that makes the output of a subsequent standard clustering algorithm
fair. Kleindessner et al [10] incorporates the fairness constraint within the
clustering algorithm. Davidson and Ravi [4] look at postprocessing clusters
for fairness; they do so by presenting it as a Minimum Cluster Modification
for Group Fairness (MCMF) optimisation problem which is formulated as an ILP.
Other notions of fairness such as representativity fairness [13] and
proportionality fairness [2] have also been proposed for clustering.

##  9 Conclusion

We proposed a postprocessing framework for making the clusters generated by
the standard k-means clustering algorithm satisfy Rawls’ difference principle
while minimally affecting the overall utility. Within this framework, we
explored two simple operators that perturb a given cluster assignment by
reassigning examples to new clusters; the first operator $\mathbf{R_{1}}$
reassigns a single example to a new cluster at a time, and the second operator
$\mathbf{R_{2}}$ reassigns two examples to new clusters at a time. We observed
that while $\mathbf{R_{2}}$ improves upon the efficiency limitation of
$\mathbf{R_{1}}$, there is still a huge scope for improvement with regards to
arriving at the Rawlsian point. There is a need to design an operator that
reassigns a larger number of examples to other clusters, which will
consequently open up new avenues for exploration in the search space.
Nevertheless, we expect these operators to act as good baselines for any
future operator.

## Acknowledgment

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie grant
agreement No 945231; and the Department of the Economy in Northern Ireland.

## References

  * [1] Abraham, S.S., P, D., Sundaram, S.S.: Fairness in clustering with multiple sensitive attributes. In: Proceedings of the 23rd International Conference on Extending Database Technology. pp. 287–298. OpenProceedings.org (2020), https://openproceedings.org/2020/conf/edbt/paper_148.pdf
  * [2] Chen, X., Fain, B., Lyu, L., Munagala, K.: Proportionally fair clustering. In: Proceedings of the 36th International Conference on Machine Learning. pp. 1032–1041. PMLR (2019), https://proceedings.mlr.press/v97/chen19d.html
  * [3] Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. In: Advances in Neural Information Processing Systems 30. Curran Associates, Inc. (2017), https://proceedings.neurips.cc/paper/2017/hash/978fce5bcc4eccc88ad48ce3914124a2-Abstract.html
  * [4] Davidson, I., Ravi, S.S.: Making existing clusterings fairer: Algorithms, complexity results and insights. In: Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence. pp. 3733–3740 (2020), https://ojs.aaai.org//index.php/AAAI/article/view/5783
  * [5] Dua, D., Graff, C.: UCI machine learning repository (2017), http://archive.ics.uci.edu/ml
  * [6] Dwork, C., Hardt, M., Pitassi, T., Reingold, O., Zemel, R.: Fairness through awareness. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. pp. 214–226. Association for Computing Machinery (2012), https://doi.org/10.1145/2090236.2090255
  * [7] Hashimoto, T., Srivastava, M., Namkoong, H., Liang, P.: Fairness without demographics in repeated loss minimization. In: Proceedings of the 35th International Conference on Machine Learning. pp. 1929–1938. PMLR (2018), https://proceedings.mlr.press/v80/hashimoto18a.html
  * [8] Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction, chap. Unsupervised Learning, pp. 485–585. Springer New York, New York, NY, second edn. (2009). https://doi.org/10.1007/978-0-387-84858-7_14
  * [9] Jung, C., Kannan, S., Lutz, N.: A center in your neighborhood: Fairness in facility location. CoRR (2019), http://arxiv.org/abs/1908.09041
  * [10] Kleindessner, M., Awasthi, P., Morgenstern, J.: Fair k-center clustering for data summarization. In: Proceedings of the 36th International Conference on Machine Learning. pp. 3448–3457. PMLR (2019), https://proceedings.mlr.press/v97/kleindessner19a.html
  * [11] Kleindessner, M., Awasthi, P., Morgenstern, J.: A notion of individual fairness for clustering. CoRR (2020), https://arxiv.org/abs/2006.04960
  * [12] Mahabadi, S., Vakilian, A.: Individual fairness for k-clustering. In: Proceedings of the 37th International Conference on Machine Learning. pp. 6586–6596. PMLR (2020), https://proceedings.mlr.press/v119/mahabadi20a.html
  * [13] P, D., Abraham, S.S.: Representativity fairness in clustering. In: 12th ACM Conference on Web Science. pp. 202–211. Association for Computing Machinery (2020), https://doi.org/10.1145/3394231.3397910
  * [14] Pedreshi, D., Ruggieri, S., Turini, F.: Discrimination-aware data mining. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 560–568. Association for Computing Machinery (2008), https://doi.org/10.1145/1401890.1401959
  * [15] Rawls, J.: Justice as Fairness: A Restatement, chap. Principles of Justice, pp. 39–79. The Belknap Press of Harvard University Press, Cambridge, MA (2001)
  * [16] Shah, K., Gupta, P., Deshpande, A., Bhattacharyya, C.: Rawlsian fair adaptation of deep learning classifiers. In: Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society. pp. 936–945. Association for Computing Machinery (2021), https://doi.org/10.1145/3461702.3462592