Explore the Axion Dark Matter through the Radio
Signals from Magnetic White Dwarf Stars

Jin-Wei Wanga,b,c,¶ , Xiao-Jun Bid,e,†, Run-Min Yaod,e,‡, Peng-Fei Yind,§

a Scuola Internazionale Superiore di Studi Avanzati (SISSA), via Bonomea 265,
34136 Trieste, Italy
b INFN, Sezione di Trieste, via Valerio 2, 34127 Trieste, Italy
b Institute for Fundamental Physics of the Universe (IFPU), via Beirut 2,
34151 Trieste, Italy
d Key Laboratory of Particle Astrophysics, Institute of High Energy Physics,
Chinese Academy of Sciences, Beijing, China
e School of Physical Sciences, University of Chinese Academy of Sciences,
Beijing, China

> Axion as one of the promising dark matter candidates can be detected through
> narrow radio lines emitted from the magnetic white dwarf stars. Due to the
> existence of the strong magnetic field, the axion may resonantly convert
> into the radio photon (Primakoff effect) when it passes through the corona
> of the magnetic white dwarf, where the photon effective mass is equal to the
> axion mass. We show that for the magnetic white dwarf WD 2010+310, the
> future experiment SKA phase 1 with 100 hours of observation will set an
> upper limit on the axion-photon coupling $g_{a\gamma}$ of $\sim
> 10^{-12}~{}\text{GeV}^{-1}$ for the axion mass range of $0.2\sim
> 3.7~{}\mu$eV.

$\P$<EMAIL_ADDRESS>
$\dagger$<EMAIL_ADDRESS>
$\ddagger$<EMAIL_ADDRESS>
$\S$<EMAIL_ADDRESS>
###### Contents

  1. 1 Introduction
  2. 2 The corona of the magnetic white dwarf and its magnetic field structure
  3. 3 The axion-photon conversion probability in the magnetosphere of the magnetic white dwarf
  4. 4 The radio flux density from the magnetic white dwarf
  5. 5 Conclusions

##  1 Introduction

The existence of dark matter (DM) has been established by solid astrophysical
and cosmological observations[1, 2]. For quite a long time the weakly
interacting massive particles (WIMPs) are regarded as the most promising DM
candidates, because they can naturally explain the DM relic density [3, 4, 5].
However, so far no convincing dark matter signal has been found in the direct
detection, indirect detection, and collider detection experiments.
Furthermore, the limitations on the couplings between the DM particles and
standard model particles are becoming more and more stringent [4, 6, 7]. In
this case, the experimental searches for other DM candidates have thus
attracted increasingly attention in recent years [8, 9].

Among many other alternatives, the QCD axion, a light neutral pseudoscalar
particle associated with the U(1) Peccei-Quinn symmetry [10], is one of the
best options due to several excellent theoretical characteristics: (1) it can
resolve the strong CP problem very well [11, 12, 13]; (2) it can explain the
observed DM abundance [14, 15, 16]. For more details we refer the reader to
the excellent reviews of axion physics [17, 18, 19].

Based on the possible couplings between axion and the electromagnetic sector,
a number of experiments have been set up to search for axion DM signals. These
interactions predict two different phenomena: (1) the conversion between an
axion particle and a photon under magnetic fields (so-called Primakoff effect
[20]), e.g. axion helioscope [21, 22], ”light shining through a wall”
experiments [23, 24], and so on; (2) the photon birefringence under axion
background [25, 26, 27, 28, 29, 30]. In this paper we focus on the former
phenomenon.

The compact stars, e.g. magnetic white dwarf stars (MWDs) and neutron stars,
are very promising probes to search for the axion DM, since these stars host
strong magnetic fields, in which the axion can be converted into detectable
photon signals. For example, there are studies in the literature using the
X-ray observations of MWDs to detect the star-born axions [31] and detecting
the radio signals from axion DM conversion in the magnetospheres of neutron
stars [32, 33, 34, 35, 36].

In this work we focus on the signals of axion DM from MWDs whose magnetic
fields are at order of $10^{7}\sim 10^{8}$ G. With such a strong magnetic
field, the axion DM may be converted into photons within the coronae of these
MWDs. With the number density of plasma at the base of the MWD corona $\sim
10^{10}~{}\text{cm}^{-3}$, the effective photon mass $m_{\gamma}$ in the
corona is $\sim\mu\text{eV}$, which corresponds to a frequency of $\sim$ GHz.
This means that the axion DM with mass of $m_{a}\sim\mu\text{eV}$ could
fulfill the resonant conversion condition $m_{a}\sim m_{\gamma}$ and thus the
conversion probability can be enhanced greatly. The frequency of the
corresponding signal happens to be in the sensitive region of the terrestrial
radio telescopes, such as the Square Kilometer Array (SKA) that partially
covers the $50\sim 1050~{}\text{MHz}$ frequency band [37]. Therefore, we
propose to use the radio telescopes to search for the axion DM in this mass
range. Thus proposal can be regarded as a good supplement to the other axion
detection experiment, such as ADMX [38, 39, 40] and CAST [21, 41, 42].

This paper is outlined as follows. In Sec. 2 we introduce the distribution of
plasma density in the coronae of the MWDs and their magnetic field structure.
In Sec. 3 we give a brief calculation of axion-photon conversion probability
in the magnetic fields of MWDs. In Sec. 4 we calculate the radio flux density
of some MWDs candidates as well as the constraints on the axion-photon
coupling strength $g_{a\gamma}$ at the SKA. Conclusions and further
discussions are given in Sec. 5.

##  2 The corona of the magnetic white dwarf and its magnetic field structure

The X-radiation search can be used to set stringent constraints on the
parameters of the MWDs’ coronae [43, 44], which is suggested by several
theories [45, 46, 47]. For example, the Chandra observation of the single cool
MWD GD 356 sets limits on the plasma density of the hot corona as
$n_{e0}<4.4\times 10^{11}~{}\text{cm}^{-3}$ with the temperature of corona
$T_{\text{cor}}\sim 10^{7}~{}\text{K}$ [44], while in Ref.[43] the upper limit
on the plasma density is $n_{e0}\sim 10^{10}~{}\text{cm}^{-3}$ with
$T_{\text{cor}}\gtrsim 10^{6}~{}\text{K}$ for the MWD G99-47 (WD 0553+053). In
the following sections, we show that the MWDs satisfying these constraints can
be promising probes to detect the axion DM.

In this work, for the properties of the MWDs’ coronae, we adopt the same
assumptions as in Ref.[43]: (1) the corona is composed of fully ionized
hydrogen plasma uniformly covering the entire surface of the white dwarf; (2)
the field-aligned temperature of the electrons $T_{\text{cor}}\sim
10^{6}~{}\text{K}$ is a constant throughout the corona. Under these conditions
the distribution of the electron density at $r$ is described by the barometric
formula [43, 44]

$\displaystyle
n_{e}(r)=n_{e0}~{}\text{exp}\left(-\frac{r-R_{\text{WD}}}{H_{\text{cor}}}\right),$
(1)

where $n_{e0}$ is the density at the base of the corona, $R_{\text{WD}}$ is
the radius of the MWDs, and

$\displaystyle
H_{\text{cor}}=\frac{2k_{\text{B}}T_{\text{cor}}}{m_{\text{p}}g}=21.90\left(\frac{T_{\text{cor}}}{10^{6}~{}\text{K}}\right)\left(\frac{M_{\text{WD}}}{M_{\odot}}\right)\left(\frac{R_{\text{WD}}}{10^{4}~{}\text{km}}\right)^{-2}\text{km}$
(2)

is the scale height of the isothermal corona, $k_{\text{B}}$ is the Boltzmann
constant, $m_{\text{p}}$ is the proton mass, $g$ is the free-fall acceleration
at the surface of MWDs, $M_{\text{WD}}$ is the mass of the MWDs.

Highly MWDs may give a very complex magnetic field structure [48]. In this
work, for simplicity we take the dipole configuration as in Ref. [31]:

$\displaystyle\bm{B}=\frac{B_{0}}{2}\,\frac{R_{\text{WD}}^{3}}{r^{3}}\,\Bigl{(}3(\hat{\bm{m}}\cdot\hat{\bm{r}})\,\hat{\bm{r}}-\hat{\bm{m}}\Bigr{)}\qquad\text{for}\qquad
r>R_{\text{WD}},\,$ (3)

where $B_{0}$ is the value of the magnetic field at the MWDs’ surface in the
direction of the magnetic pole, $\bm{m}=2\pi
B_{0}R_{\text{WD}}^{3}\hat{\bm{m}}$ is the magnetic dipole moment,
$\bm{r}=r\hat{\bm{r}}$ is the spatial coordinate, and $r=|\bm{r}|$ represents
the distance from the center of the MWDs. Furthermore, we simply set
$\theta=\pi/2$ and expect that this assumption would give a satisfactory
estimation. Then eq. (3) can be rewritten as a simpler form

$\displaystyle
B=|\bm{B}|=\frac{B_{0}}{2}\,\frac{R_{\text{WD}}^{3}}{r^{3}}\qquad\text{for}\qquad
r>R_{\text{WD}}.\,$ (4)

##  3 The axion-photon conversion probability in the magnetosphere of the
magnetic white dwarf

In this section we present a more general formalism to calculate the axion-
photon conversion probability in the magnetic fields of MWDs. The general
interactions between axion and photon are given by the following Lagrangian
[31]:

$\displaystyle\mathcal{L}$
$\displaystyle=\frac{1}{2}(\partial_{\mu}a)^{2}-\frac{1}{2}m_{a}^{2}a^{2}-\frac{1}{4}F_{\mu\nu}F^{\mu\nu}+\frac{1}{2}m_{A}^{2}A_{\mu}A^{\mu}$
(5)
$\displaystyle\qquad\qquad\qquad-\frac{1}{4}g_{a\gamma\gamma}\,a\,F_{\mu\nu}\tilde{F}^{\mu\nu}+\frac{\alpha_{\text{em}}^{2}}{90\,m_{e}^{4}}\Bigl{[}\bigl{(}F_{\mu\nu}F^{\mu\nu}\bigr{)}^{2}+\frac{7}{4}\bigl{(}F_{\mu\nu}\tilde{F}^{\mu\nu}\bigr{)}^{2}\Bigr{]}\,,$

where $a$ represents the axion field with the mass $m_{a}$, $F_{\mu\nu}$ is
the electromagnetic field tensor,
$\tilde{F}^{\mu\nu}\equiv\frac{1}{2}\epsilon^{\mu\nu\rho\sigma}F_{\rho\sigma}$
is its dual, $m_{A}$ is the photon’s effective mass111Here we have ignored the
term $A_{\mu}j^{\mu}$, in which $j^{\mu}$ is the electromagnetic current
density, since its physical consequence has been replace by the photon’s
effective mass $m_{A}$ when photon propagates in the plasma [49].,
$g_{a\gamma\gamma}$ is the axion-photon coupling, $\alpha_{\text{em}}$ is the
electromagnetic fine structure constant, and $m_{e}$ is the electron mass. In
the nonrelativistic plasma with nonzero electron density $n_{e}$, the
effective mass of the photon is given by
$m_{A}=\sqrt{4\pi\alpha_{\text{em}}n_{e}/m_{e}}$. The last term in eq. (5) is
the Euler-Heisenberg effective Lagrangian arising from the vacuum
polarizability [50]. It describes the photon’s self-interaction in the limit
where the photon’s frequency is small in comparison with the electron mass
$m_{e}$. Its contribution to the $m_{A}$ is estimated as [51, 34]

$Q_{A}^{\text{EH}}=\frac{7\alpha_{\text{em}}}{45\pi}\omega^{2}\frac{B^{2}}{B_{\text{cri}}^{2}}$
(6)

where $B_{\text{cri}}\equiv m_{e}^{2}/e=4.4\times 10^{13}~{}\text{G}$ is a
critical field strength, $\omega$ is the photon’s frequency. For the MWDs
considered in this work, the strength of the magnetic field is about
$10^{7}\sim 10^{8}$ G (see Table.1), which indicates
$B^{2}/B_{\text{cri}}^{2}\ll 1$. Therefore, we can safely ignore the effects
of the Euler-Heisenberg term.

As shown below, the resonant conversion between the axion and photon occurs
when the photon’s effective mass $m_{A}$ is equal to the axion mass $m_{a}$ as

$\displaystyle m^{2}_{\gamma}(r)=4\pi\alpha\frac{n_{e}(r)}{m_{e}}=m_{a}^{2}.$
(7)

By solving the eq. (1) and eq. (7), the resonant conversion radius $r_{c}$ can
be expressed as

$\displaystyle r_{c}$
$\displaystyle=R_{\text{WD}}+21.90\times\left[2.634+\text{ln}\left(\frac{n_{e0}}{10^{10}~{}\text{cm}^{-3}}\right)+\text{ln}\left(\frac{\mu\text{eV}^{2}}{m_{a}^{2}}\right)\right]$
$\displaystyle\qquad\qquad\qquad~{}~{}~{}\times\left(\frac{T_{\text{cor}}}{10^{6}~{}\text{K}}\right)\left(\frac{M_{\text{WD}}}{M_{\odot}}\right)\left(\frac{R_{\text{WD}}}{10^{4}~{}\text{km}}\right)^{-2}\text{km}.$
(8)

The equation of motion for the axion and photon field can be derived by
applying the variational principle to eq. (5):

$\displaystyle\ddot{a}-\nabla^{2}a+m_{a}^{2}a$ $\displaystyle\ =\
-g_{a\gamma\gamma}\,\dot{{\bm{A}}}\cdot{\bm{B}},$ (9)
$\displaystyle\ddot{{\bm{A}}}-\nabla^{2}{\bm{A}}+m_{A}^{2}{\bm{A}}$
$\displaystyle\ =\
g_{a\gamma\gamma}\,\dot{a}\,{\bm{B}}-g_{a\gamma\gamma}\,{\bm{\nabla}}a\times\dot{{\bm{A}}}.$
(10)

Here we have chosen the temporal gauge $A_{0}=0$ and the Coulomb gauge
${\bm{\nabla}}\cdot{\bm{A}}=0$. Following [33, 51] we adopt the radial plane
wave solution $a(r,t)=ie^{i\omega t-ikr}\tilde{a}(r)$ and
$A_{\parallel}(r,t)=e^{i\omega t-ikr}\tilde{A}_{\parallel}(r)$, where
$k=\sqrt{\omega^{2}-m_{a}^{2}}$ represents the momentum of the axion. Note
that we have temporarily ignored the damping effects of the outgoing photon
wave [33] and will include this effect in the finally answer.

Plugging the above plane wave solutions into the eq. (9)$\sim$(10) and using
the WKB approximation $|\tilde{A}_{\parallel}^{\prime\prime}(r)|\ll
k|\tilde{A}^{\prime}(r)|$ and $|\tilde{a}^{\prime\prime}(r)|\ll
k|a^{\prime}(r)|$ near $r_{c}$, we can rewrite the above mixing equations into
a more compact first-order ordinary differential equation[33, 51]

$\begin{split}\left[-i\frac{d}{dr}+\frac{1}{2k}{\left(\begin{array}[]{cc}m_{a}^{2}-m_{A}^{2}&-\Delta_{B}\\\
-\Delta_{B}&0\end{array}\right)}\right]\left(\begin{array}[]{c}\tilde{A}_{\parallel}\\\
\tilde{a}\end{array}\right)=0,\end{split}$ (11)

where $\Delta_{B}=Bg_{a\gamma\gamma}\omega$,
$\omega=m_{a}/\sqrt{1-v_{c}^{2}}$. Using the successive approximation method
with the initial conditions $\tilde{A}_{\parallel}(R_{\text{WD}})=0$ and
$\tilde{a}(R_{\text{WD}})=a_{0}$, at the first order of $\Delta_{B}$ the eq.
(11) can be solved as [33, 51]

$\begin{split}p_{a\gamma}(r)=\left|i\int_{R_{\text{WD}}}^{r}dr^{\prime}{\omega
B(r^{\prime})g_{a\gamma\gamma}\over 2k}\times e^{{if(r^{\prime})\over
2k}}\right|^{2},\end{split}$ (12)

where

$\begin{split}f(r^{\prime})=\int_{R_{\text{WD}}}^{r^{\prime}}d\tilde{r}\big{[}m_{a}^{2}-m_{A}^{2}(\tilde{r})\big{]}.\end{split}$
(13)

Since $1/2k\ll 1$, we can evaluate eq. (12) by the method of stationary phase.
With the condition $df(r^{\prime})/dr^{\prime}=0$, we get
$m_{a}^{2}-m_{A}^{2}(r_{c})=0$, which exactly is the resonant conversion
condition mentioned in eq. (7). By explicitly performing the integral in eq.
(12) and including the damping effect of the photon wave, the probability of
the axion-photon conversion at finite $r$ is given by [33]

$\begin{split}p_{a\gamma}(r)&\approx\frac{1}{2v_{c}^{2}}\,g_{a\gamma\gamma}^{2}B(r_{c})^{2}L^{2}\times
G\left(\frac{r-r_{c}}{L}\right)\times\begin{cases}1,&r<r_{c}\\\
\frac{m_{a}v_{c}}{D(r)},&r\geq r_{c}\end{cases}\,,\end{split}$ (14)

with $L=\sqrt{2\pi r_{c}v_{c}/(3m_{a})}$ and
$D(r)=\sqrt{\omega^{2}-m_{A}^{2}}$. The function $G(x)$ is defined by

$\begin{split}G(x)={\left(\frac{1}{2}+C(x)\right)^{2}+\left(\frac{1}{2}+S(x)\right)^{2}\over
2}\end{split}$ (15)

in terms of the Fresnel $C$ and $S$ integrals

$\begin{split}C(x)=\int_{0}^{x}dt~{}\text{cos}(\pi t^{2}/2),\qquad
S(x)=\int_{0}^{x}dt~{}\text{sin}(\pi t^{2}/2).\end{split}$ (16)

The last term in eq. (14) represents the damping effect of the photon
wave[33]. Consider that all the astrophysical objects we are considering are
very far away from us, i.e. $\sim$ 0.1 kpc, so eq. (14) can be further
simplified as222We have compared the numerical solutions by solving eq. (11)
with this analytic approximation, and we find that these two results matched
very well.

$\begin{split}p_{a\gamma}^{\infty}=\lim_{r\to\infty}p_{a\gamma}(r)&\approx\frac{1}{2v_{c}}\,g_{a\gamma\gamma}^{2}B(r_{c})^{2}L^{2}.\end{split}$
(17)

Here we have used the fact that $\lim_{x\to\infty}G(x)=1$ and
$\lim_{r\to\infty}{m_{a}v_{c}}/{D(r)}=v_{c}$.

##  4 The radio flux density from the magnetic white dwarf

In this work we consider the following conversion picture: the axion DM
particle starts out non-relativistic ($\sim 10^{-3}~{}c$) far away from the
MWDs and is accelerated as it moves toward the MWDs, then it is converted into
the photon in the MWDs’ coronae with a certain probability
$p_{a\gamma}^{\infty}$. Besides, because of the high density of the MWDs, all
the incident photons that are converted from axons will be totally reflected
back out [33, 52].

Once converted, the outgoing photons can be absorbed or scattered in the MWDs’
coronae, which is characterized by opacity. There are two important processes:
the inverse bremsstrahlung process and Compton scattering. The absorption and
scattering rate are given as [52]

$\displaystyle\Gamma_{\rm inv}$ $\displaystyle\approx$
$\displaystyle\frac{8\pi
n_{e}n_{N}\alpha^{3}}{3\omega^{3}m_{e}^{2}}\left(\frac{2\pi
m_{e}}{T_{\text{cor}}}\right)^{1/2}\log\left(\frac{2T^{2}_{\text{cor}}}{m_{A}^{2}}\right)\left(1-e^{-\omega/T_{\text{cor}}}\right),$
(18) $\displaystyle\Gamma_{\rm Com}=\frac{8\pi\alpha^{2}}{3m_{e}^{2}}n_{e},$
(19)

where $n_{N}$ is the number density of the charged ions333Since the plasma is
electric neutral, so we have $n_{e}=n_{N}$.. Then the probability for the
converted photons to be scattered or absorbed during the propagation can be
expressed as

$\displaystyle
P_{s/a}\simeq\exp\left[-\int_{R_{\text{WD}}}^{\infty}dr\left(\Gamma_{\rm
inv}+\Gamma_{\rm Com}\right)\right].$ (20)

For the MWDs candidates in Table.1 we calculate that the $P_{s/a}$ is $\sim
0.004$, this means that the corona of the MWD is optically thin and the
scattering and absorption of the photons can be safely ignored. The radiated
power $\mathcal{P}$ in a solid angle $d\Omega$ at $r_{c}$ can be estimated as
[33]

$\begin{split}{d\mathcal{P}\over d\Omega}\approx 2\times
p_{a\gamma}^{\infty}\,\rho_{\text{DM}}^{r_{c}}v_{c}r_{c}^{2}\,,\end{split}$
(21)

where $\rho_{\rm DM}^{r_{c}}$ is the DM mass density at $r=r_{c}$. The factor
of two is from the fact that the DM may convert into photons either on its way
in to or out of the resonant layer. In the limit $v_{0}^{2}/(GM_{\rm
WD}/r_{c})\ll 1$, the $\rho_{\rm DM}^{r_{c}}$ can be expressed as

$\begin{split}\rho_{\text{DM}}^{r_{c}}=\rho_{\text{DM}}^{\infty}{2\over\sqrt{\pi}}{1\over
v_{0}}\sqrt{2GM_{\rm WD}\over r_{c}}+\cdots,\end{split}$ (22)

where $\rho_{\text{DM}}^{\infty}$ is the DM density at infinity $\sim
0.3~{}\text{GeV}/\text{cm}^{3}$ and $v_{0}\sim 200~{}\text{km}/\text{s}$ is
the DM virial velocity. The raido flux density at the Earth can be estimated
as

$\displaystyle
S_{a\gamma}=\frac{d\mathcal{P}}{d\Omega}\frac{1}{\mathcal{B}d^{2}},$ (23)

where $d$ represents the distance from the MWD to us,
$\mathcal{B}=\text{max}\\{B_{\text{sig}},B_{\text{res}}\\}$ is the optimized
bandwidth, $B_{\text{sig}}\sim v_{0}^{2}m_{a}/(2\pi)$ is the signal bandwidth,
which is determined by the velocity dispersion in the asymptotic DM
distribution, and $B_{\text{res}}$ is the telescope spectral resolution. It is
worth noting that in general $B_{\text{sig}}$ is smaller than $B_{\text{res}}$
(see Table. 2).

Parameters and expected radio flux density of the MWDs
---
| $M_{\text{WD}}\ [M_{\odot}]$ | $R_{\text{WD}}\ [R_{\odot}]$ | $T_{\mathrm{eff}}\ [\mathrm{K}]$ | $B\ [\mathrm{MG}]$ | $d_{\text{WD}}\ [\mathrm{pc}]$ |  $S_{a\gamma}\ [\mu\mathrm{Jy}$]
RE J0317-853 | $1.32$ | $0.00405$ | $30000$ | $200$ | $29.54$ | $1.13$
WD 2010+310 | $1$ | $0.00643$ | $19750$ | $520$ | $30.77$ | $33.87$
WD 1031+234 | $0.937$ | $0.00872$ | $20000$ | $200$ | $64.09$ | $2.32$
WD 1043-050 | $1.02$ | $0.00787$ | $16250$ | $820$ | $83.33$ | $19.57$
WD 1743-520 | $1.13$ | $0.00681$ | $14500$ | $36$ | $38.93$ | $0.13$
Table 1: MWDs that make good candidates for measurement of the axion-induced
radio flux. The columns correspond to the star’s mass in solar masses, radius
in solar radii, effective temperature in Kelvin, magnetic field strength in
mega-Gauss, distance from Earth in parsecs, and predicted radio flux density
in $\mu\mathrm{Jy}$. Some typical parameters are taken as
$m_{a}=10^{-6}\,\mathrm{eV}$, $g_{a\gamma\gamma}=10^{-12}\ \mathrm{GeV}^{-1}$,
$n_{e0}=10^{10}~{}\text{cm}^{-3}$, $T_{\text{cor}}=10^{6}~{}\text{K}$. With
these parameters we can derive that $\mathcal{B}=1.0~{}\text{kHz}$. The
parameters from observations were obtained by merging the catalogs in Refs.
[53, 48, 54].

Using eq. (17), (21) $\sim$ (23) we can calculate the radio flux density for
specific MWDs. In Table.1 we list the parameters of five MWD candidates as
well as their radio flux densities $S_{a\gamma}$. The following typical
parameters are selected for the calculation: $m_{a}=10^{-6}\,\mathrm{eV}$,
$g_{a\gamma\gamma}=10^{-12}\ \mathrm{GeV}^{-1}$,
$n_{e0}=10^{10}~{}\text{cm}^{-3}$, $T_{\text{cor}}=10^{6}~{}\text{K}$. With
these parameters we can derive that $\mathcal{B}=1.0~{}\text{kHz}$ (see Talbe.
2). All these results should be compared to the minimum detectable flux
density of a radio telescope, such as SKA [37], which can be expressed as

$\displaystyle S_{\min}=\frac{\rm SEFD}{\eta_{s}\sqrt{n_{\rm pol}\,{\cal
B}~{}t_{\rm obs}}}\ ,$ (24)

where

$\displaystyle{\rm SEFD}=2k_{B}\frac{T_{\rm sys}}{A_{\rm eff}}$ (25)

is the system-equivalent flux density, $n_{\rm pol}=2$ is the number of
polarization, $t_{\rm obs}$ is the observation time, $\eta_{s}$ is the system
efficiency, $k_{B}$ is the Boltzmann constant, $T_{\rm sys}$ is the antenna
system temperature, and $A_{\rm eff}$ is the antenna effective area of the
array. In this work, we take $\eta_{s}=0.9$ for SKA [37]. The values of the
telescope spectral resolution $B_{\rm res}$ for SKA are listed in Table.2.

Parameters and sensitivity of the SKA
---
Name |  $f$ [MHz] |  $B_{\rm res}$ [kHz] |  $\langle T_{\rm sys}\rangle$ [K] |  $\langle A_{\rm eff}\rangle$ [${\rm m^{2}}$] | SEFD [Jy] |  $S_{\text{min}}$ [$\mu$Jy]
SKA1-Low | (50, 350) | 1.0 | 680 | $2.2\times 10^{5}$ | 8.54 | 353.42
SKA1-Mid B1 | (350, 1050) | 3.9 | 28 | $2.7\times 10^{4}$ | 2.86 | 60.04
Table 2: The frequency range, telescope spectral resolution $B_{\rm res}$,
averaged system temperature $T_{\rm sys}$, averaged effective area $A_{\rm
eff}$, SEFD, and minimum detectable flux density in the different frequency
bands for SKA1.

Next we propose to use the SKA phase 1 (SKA1) as a benchmark to search for the
radio signals converted from axion DM at MWDs. As shown in Table. 2, it
consists of a low-frequency aperture array (SKA1-Low) and a middle frequency
aperture array (SKA1-Mid) [37]. The SKA1-Low covers the $(50,350)$ MHz
frequency band, while the SKA1-Mid actually covers six frequency bands:
$(350,1050)$ MHz, $(950,1760)$ MHz, $(1650,3050)$ MHz, $(2800,5180)$ MHz,
$(4600,8500)$ MHz, and $(8300,15300)$ MHz. However, considering the
constraints of the resonant conversion condition $m_{A}\sim m_{a}$ as well as
the plasma density $n_{e0}\lesssim 10^{10}~{}\text{cm}^{-3}$, there will be an
upper bound on the frequency of the photon $f_{A}\lesssim$ 903 MHz. Therefore,
we only need to use the first frequency band SKA1-Mid B1 in our analysis. The
specific parameters of the different frequency bands of the SKA are listed in
Table. 2.

Figure 1: The projected sensitivity to $g_{a\gamma}$ as a function of the
axion mass $m_{a}$ for SKA1 telescopes with 100 hours observations of the WD
2010+310 is shown in the blue region. The lower mass cutoff is set by the
lowest available frequency of SKA, while the upper cutoff is set by requiring
the conversion radius to be larger than the MWDs’ radius. The QCD axion is
predicted to lie within the yellow band. The limits set by CAST and ADMX
(current and projected) are indicated by the gray and red regions,
respectively.

In Fig. 1 we show the sensitivity to $g_{a\gamma}$ for the WD 2010+310, which
is the strongest source in Talbe. 1. The blue regions show the physics
potential of SKA1 with 100 hours of observation. Note that the lower mass
cutoff is set by the lowest available frequency of SKA $\sim$ 50 MHz, while
the upper cutoff is set by requiring the conversion radius to be larger than
the MWDs’ radius. We find that the axion DM in the mass range of $0.2\sim
3.7~{}\mu$eV can be probed effectively, and the limitation on $g_{a\gamma}$ is
about $\lesssim 10^{-12}~{}\text{GeV}^{-1}$. For comparison, the limitations
given by the other two experiments, e.g. ADMX and CAST, are also shown in red
and gray regions, respectively.

##  5 Conclusions

In this work we propose to use MWDs as probes to detect the axion DM through
the radio signals. It is known that the MWDs can host very strong magnetic
field (e.g. $10^{7}\sim 10^{8}$ G). If we adopt the corona parameters that
fulfill the X-ray constraints, such as $n_{e0}\sim 10^{10}~{}\text{cm}^{-3}$
and $T_{\text{cor}}\sim 10^{6}~{}\text{K}$, the effective photon mass is given
by $m_{\gamma}\sim\mu\text{eV}$ (corresponding to the frequency $\sim$ GHz).
We find that the resonant conversion may happen when axions pass through the
magnetosphere that is a narrow region around the radius at which the photon
effective mass is equal to the axion mass. Besides, we show that the effects
of the inverse bremsstrahlung process and Compton scattering for the outgoing
photons are negligible ($P_{a/s}\sim 0.004$). Therefore, once converted, the
radio photon can pass unimpededly through the MWDs’ coronae and be detected by
the radio telescope on Earth.

Meanwhile, it is intriguing that for the axion DM with mass
$\sim\mu\text{eV}$, which happens to be in the sensitive region of the
terrestrial radio telescopes, such as SKA. In Sec. 4 we use the MWD WD
2010+310 as a target and show the sensitivity to $g_{a\gamma}$ from the future
experiment SKA phase 1 with 100 hours of observation. We find that the planned
SKA1 will give an upper limit on the axion-photon coupling $g_{a\gamma}$ of
$\sim 10^{-12}~{}\text{GeV}^{-1}$ for axion mass range of $0.2\sim
3.7~{}\mu$eV, and this result may increase by more than one order of magnitude
in the SKA phase 2 (SKA2) [37, 34].

Note that all of the MWDs considered are isolated. In fact, one can consider
another class of MWDs that occupy regions of high DM density and/or low
velocity dispersion, such as the galactic center, dwarf galaxies, and so on.
In these regions, the DM density may be enhanced by a large factor. In
addition, in dwarf galaxies the velocity dispersion of DM can be low as
$v_{0}\sim 10~{}\text{km/s}$. These cases would significantly improve our
results and are left for the future work.

### Acknowledgements

The work of JWW is supported by the research grant ”the Dark Universe: A
Synergic Multi-messenger Approach” number 2017X7X85K under the program PRIN
2017 funded by the Ministero dell’Istruzione, Universit$\grave{a}$ e della
Ricerca (MIUR). The work of XJB, RMY, and PFY is supported by the National Key
R&D Program of China (No. 2016YFA0400200), the National Natural Science
Foundation of China (Nos. U1738209 and 11851303).

## References

  * [1] D. Clowe, M. Bradac, A. H. Gonzalez, M. Markevitch, S. W. Randall, C. Jones, and D. Zaritsky, “A direct empirical proof of the existence of dark matter,” Astrophys. J. Lett. 648 (2006) L109–L113, arXiv:astro-ph/0608407.
  * [2] Planck Collaboration, N. Aghanim et al., “Planck 2018 results. VI. Cosmological parameters,” Astron. Astrophys. 641 (2020) A6, arXiv:1807.06209 [astro-ph.CO].
  * [3] G. Bertone, D. Hooper, and J. Silk, “Particle dark matter: Evidence, candidates and constraints,” Phys. Rept. 405 (2005) 279–390, arXiv:hep-ph/0404175.
  * [4] J. L. Feng, “Dark Matter Candidates from Particle Physics and Methods of Detection,” Ann. Rev. Astron. Astrophys. 48 (2010) 495–545, arXiv:1003.0904 [astro-ph.CO].
  * [5] G. Arcadi, M. Dutra, P. Ghosh, M. Lindner, Y. Mambrini, M. Pierre, S. Profumo, and F. S. Queiroz, “The waning of the WIMP? A review of models, searches, and constraints,” Eur. Phys. J. C 78 (2018) 203, arXiv:1703.07364 [hep-ph].
  * [6] J. Liu, X. Chen, and X. Ji, “Current status of direct dark matter detection experiments,” Nature Phys. 13 (2017) 212–216, arXiv:1709.00688 [astro-ph.CO].
  * [7] L. Zhao and J. Liu, “Experimental search for dark matter in China,” Front. Phys. (Beijing) 15 (2020) 44301, arXiv:2004.04547 [astro-ph.IM].
  * [8] G. Sigl and P. Trivedi, “Axion-like Dark Matter Constraints from CMB Birefringence,” arXiv:1811.07873 [astro-ph.CO].
  * [9] G. Bertone et al., “Gravitational wave probes of dark matter: challenges and opportunities,” arXiv:1907.10610 [astro-ph.CO].
  * [10] R. Peccei and H. R. Quinn, “Constraints Imposed by CP Conservation in the Presence of Instantons,” Phys. Rev. D 16 (1977) 1791–1797.
  * [11] R. D. Peccei and H. R. Quinn, “$\mathrm{CP}$ Conservation in the Presence of Pseudoparticles,” Phys. Rev. Lett. 38 (Jun, 1977) 1440–1443.
  * [12] S. Weinberg, “A New Light Boson?,” Phys. Rev. Lett. 40 (Jan, 1978) 223–226.
  * [13] F. Wilczek, “Problem of Strong $P$ and $T$ Invariance in the Presence of Instantons,” Phys. Rev. Lett. 40 (Jan, 1978) 279–282.
  * [14] J. Preskill, M. B. Wise, and F. Wilczek, “Cosmology of the invisible axion,” Physics Letters B 120 (1983) 127 – 132.
  * [15] L. Abbott and P. Sikivie, “A cosmological bound on the invisible axion,” Physics Letters B 120 (1983) 133 – 136.
  * [16] M. Dine and W. Fischler, “The not-so-harmless axion,” Physics Letters B 120 (1983) 137 – 141.
  * [17] P. W. Graham, I. G. Irastorza, S. K. Lamoreaux, A. Lindner, and K. A. van Bibber, “Experimental Searches for the Axion and Axion-Like Particles,” Ann. Rev. Nucl. Part. Sci. 65 (2015) 485–514, arXiv:1602.00039 [hep-ex].
  * [18] L. Di Luzio, M. Giannotti, E. Nardi, and L. Visinelli, “The landscape of QCD axion models,” Phys. Rept. 870 (2020) 1–117, arXiv:2003.01100 [hep-ph].
  * [19] D. J. E. Marsh, “Axion Cosmology,” Phys. Rept. 643 (2016) 1–79, arXiv:1510.07633 [astro-ph.CO].
  * [20] H. Primakoff, “Photoproduction of neutral mesons in nuclear electric fields and the mean life of the neutral meson,” Phys. Rev. 81 (1951) 899.
  * [21] CAST Collaboration, V. Anastassopoulos et al., “New CAST Limit on the Axion-Photon Interaction,” Nature Phys. 13 (2017) 584–590, arXiv:1705.02290 [hep-ex].
  * [22] E. Armengaud et al., “Conceptual Design of the International Axion Observatory (IAXO),” JINST 9 (2014) T05002, arXiv:1401.3233 [physics.ins-det].
  * [23] K. Ehret et al., “New ALPS Results on Hidden-Sector Lightweights,” Phys. Lett. B 689 (2010) 149–155, arXiv:1004.1313 [hep-ex].
  * [24] R. Bähre et al., “Any light particle search II —Technical Design Report,” JINST 8 (2013) T09001, arXiv:1302.5647 [physics.ins-det].
  * [25] W. DeRocco and A. Hook, “Axion interferometry,” Phys. Rev. D 98 (2018) 035021, arXiv:1802.07273 [hep-ph].
  * [26] I. Obata, T. Fujita, and Y. Michimura, “Optical Ring Cavity Search for Axion Dark Matter,” Phys. Rev. Lett. 121 (2018) 161301, arXiv:1805.11753 [astro-ph.CO].
  * [27] H. Liu, B. D. Elwood, M. Evans, and J. Thaler, “Searching for Axion Dark Matter with Birefringent Cavities,” Phys. Rev. D 100 (2019) 023548, arXiv:1809.01656 [hep-ph].
  * [28] T. Fujita, R. Tazaki, and K. Toma, “Hunting Axion Dark Matter with Protoplanetary Disk Polarimetry,” Phys. Rev. Lett. 122 (2019) 191101, arXiv:1811.03525 [astro-ph.CO].
  * [29] G.-W. Yuan, Z. Xia, C. Tang, Y. Zhao, Y.-F. Cai, Y. Chen, J. Shu, and Q. Yuan, “Testing the ALP-photon coupling with polarization measurements of Sagittarius A*,” arXiv:2008.13662 [astro-ph.HE].
  * [30] T. K. Poddar and S. Mohanty, “Probing the angle of birefringence due to long range axion hair from pulsars,” Phys. Rev. D 102 (2020) 083029, arXiv:2003.11015 [hep-ph].
  * [31] C. Dessert, A. J. Long, and B. R. Safdi, “X-ray signatures of axion conversion in magnetic white dwarf stars,” Phys. Rev. Lett. 123 (2019) 061104, arXiv:1903.05088 [hep-ph].
  * [32] M. Pshirkov and S. Popov, “Conversion of Dark matter axions to photons in magnetospheres of neutron stars,” J. Exp. Theor. Phys. 108 (2009) 384–388, arXiv:0711.1264 [astro-ph].
  * [33] A. Hook, Y. Kahn, B. R. Safdi, and Z. Sun, “Radio Signals from Axion Dark Matter Conversion in Neutron Star Magnetospheres,” Phys. Rev. Lett. 121 (2018) 241102, arXiv:1804.03145 [hep-ph].
  * [34] F. P. Huang, K. Kadota, T. Sekiguchi, and H. Tashiro, “Radio telescope search for the resonant conversion of cold dark matter axions from the magnetized astrophysical sources,” Phys. Rev. D 97 (2018) 123001, arXiv:1803.08230 [hep-ph].
  * [35] J. Darling, “Search for Axionic Dark Matter Using the Magnetar PSR J1745-2900,” Phys. Rev. Lett. 125 (2020) 121103, arXiv:2008.01877 [astro-ph.CO].
  * [36] T. D. Edwards, B. J. Kavanagh, L. Visinelli, and C. Weniger, “Transient Radio Signatures from Neutron Star Encounters with QCD Axion Miniclusters,” arXiv:2011.05378 [hep-ph].
  * [37] S. collaboration, “Ska1 system baseline design,” 2013.  https://www.skatelescope.org/wp-content/uploads/2014/11/SKA-TEL-SKO-0000002-AG-BD-DD-Rev01
-SKA1_System_Baseline_Design.pdf. document number: SKA-TEL-SKO-DD-001.
  * [38] S. Asztalos, E. Daw, H. Peng, L. J. Rosenberg, C. Hagmann, D. Kinion, W. Stoeffl, K. van Bibber, P. Sikivie, N. S. Sullivan, D. B. Tanner, F. Nezrick, M. S. Turner, D. M. Moltz, J. Powell, M.-O. André, J. Clarke, M. Mück, and R. F. Bradley, “Large-scale microwave cavity search for dark-matter axions,” Phys. Rev. D 64 (Oct, 2001) 092003.
  * [39] S. J. Asztalos, G. Carosi, C. Hagmann, D. Kinion, K. van Bibber, M. Hotz, L. J. Rosenberg, G. Rybka, J. Hoskins, J. Hwang, P. Sikivie, D. B. Tanner, R. Bradley, and J. Clarke, “SQUID-Based Microwave Cavity Search for Dark-Matter Axions,” Phys. Rev. Lett. 104 (Jan, 2010) 041301.
  * [40] T. Shokair et al., “Future Directions in the Microwave Cavity Search for Dark Matter Axions,” Int. J. Mod. Phys. A 29 (2014) 1443004, arXiv:1405.3685 [physics.ins-det].
  * [41] CAST Collaboration, M. Arik et al., “Search for Solar Axions by the CERN Axion Solar Telescope with 3He Buffer Gas: Closing the Hot Dark Matter Gap,” Phys. Rev. Lett. 112 (2014) 091302, arXiv:1307.1985 [hep-ex].
  * [42] CAST Collaboration, M. Arik et al., “New solar axion search using the CERN Axion Solar Telescope with 4He filling,” Phys. Rev. D 92 (2015) 021101, arXiv:1503.00610 [hep-ex].
  * [43] V. V. Zheleznyakov, S. A. Koryagin, and A. V. Serber, “Thermal cyclotron radiation by isolated magnetic white dwarfs and constraints on the parameters of their coronas,” Astronomy Reports 48 (2004) 121–135.
  * [44] M. C. Weisskopf, K. Wu, V. Trimble, S. L. O’Dell, R. F. Elsner, V. E. Zavlin, and C. Kouveliotou, “A Chandra Search for Coronal X-Rays from the Cool White Dwarf GD 356,” The Astrophysical Journal 657 (Mar, 2007) 1026–1036.
  * [45] V. V. Zheleznyakov and A. A. Litvinchuk, “On the theory of cyclotron lines in the spectra of magnetic white dwarfs,” Astronomy Reports 105 (1984) 73–84.
  * [46] A. V. Serber, “Transfer of Cyclotron Radiation in a Tenuous Collisional Plasma on a Magnetic White Dwarf,” Soviet Astronomy 34 (June, 1990) 291.
  * [47] J. H. Thomas, J. A. Markiel, and H. M. van Horn, “Dynamo Generation of Magnetic Fields in White Dwarfs,” Astrophysical Journal 453 (Nov., 1995) 403.
  * [48] L. Ferrario, D. de Martino, and B. Gaensicke, “Magnetic White Dwarfs,” Space Sci. Rev. 191 (2015) 111–169, arXiv:1504.08072 [astro-ph.SR].
  * [49] P. Robles and F. Claro, “Can there be massive photons? A pedagogical glance at the origin of mass,” European Journal of Physics 33 (Jul, 2012) 1217–1226.
  * [50] W. Heisenberg and H. Euler, “Dynamo Generation of Magnetic Fields in White Dwarfs,” Zeitschrift für Physik 98 (Nov., 1936) 714–732.
  * [51] G. Raffelt and L. Stodolsky, “Mixing of the photon with low-mass particles,” Phys. Rev. D 37 (Mar, 1988) 1237–1249.
  * [52] H. An, F. P. Huang, J. Liu, and W. Xue, “Radiofrequency Dark Photon Dark Matter across the Sun,” arXiv:2010.15836 [hep-ph].
  * [53] S. Kleinman et al., “SDSS DR7 White Dwarf Catalog,” Astrophys. J. Suppl. 204 (2013) 5, arXiv:1212.1222 [astro-ph.SR].
  * [54] Gaia Collaboration, A. Brown et al., “Gaia Data Release 2: Summary of the contents and survey properties,” Astron. Astrophys. 616 (2018) A1, arXiv:1804.09365 [astro-ph.GA].


# On the Randomized Metric Distortion Conjecture

Haripriya Pulyassary {hpulyassary<EMAIL_ADDRESS>Dept. of
Combinatorics and Optimization, University of Waterloo Chaitanya Swamy∗

###### Abstract

In the single winner determination problem, we have $n$ voters and $m$
candidates and each voter $j$ incurs a cost $c(i,j)$ if candidate $i$ is
chosen. Our objective is to choose a candidate that minimizes the expected
total cost incurred by the voters; however as we only have access to the
agents’ preference rankings over the outcomes, a loss of efficiency is
inevitable. This loss of efficiency is quantified by _distortion_. We give an
instance of the metric single winner determination problem for which any
randomized social choice function has distortion at least 2.063164. This
disproves the long-standing conjecture that there exists a randomized social
choice function that has a worst-case distortion of at most 2.

##  1 Introduction

Social choice theory [5] is concerned with aggregating the preferences of
agents into a single outcome. While it can be convenient to assume that agent
preferences are captured by a _cardinal_ utility function that assigns a
numerical value to each outcome, in many contexts we only have access to
_ordinal_ information, namely the agents’ preference rankings over the
outcomes. There are many reasons why such situations may arise; perhaps the
most prominent is that the agents themselves may find it difficult to place
numerical values on the possible outcomes [2]. As ordinal preference rankings
are not as expressive as cardinal utilities, a loss of efficiency, in terms of
the quality of the outcome computed, is inevitable. Procaccia and Rosenschein
[11] introduced the notion of _distortion_ , which quantifies the worst-case
efficiency loss for a given social choice function.

In the single winner determination problem, we have $n$ voters and $m$
candidates; each voter $j$ incurs a cost $c(i,j)$ if candidate $i$ is chosen.
Our objective is to choose a candidate that minimizes the total cost incurred
by the voters. If no additional assumptions are made regarding the underlying
costs, there exists an instance such that every randomized social choice
function has distortion at least $\Omega(\sqrt{m})$ [4]. However, in many
settings, the costs represent literal or ideological distances, and
consequently must be metric. Under this assumption, there have been a string
of positive results [1, 8, 10] and recently, Gkatzelis et. al [7] proved that
there exists a deterministic social choice function that has a distortion of
3. Moreover, it is known that this bound is tight [1].

It has been shown that, for the metric single winner determination problem,
randomized social choice functions can be strictly more powerful than
deterministic mechanisms [3, 7, 9]. In particular, Gkatzelis et. al [7] give a
randomized social choice function whose distortion is $3-\frac{2}{m}$. A long-
standing conjecture is that there exists a randomized social choice function
that has a worst-case distortion of at most 2.

We develop a linear program that computes an instance-optimal randomized
social choice function; i.e., a distribution that achieves minimum distortion
for any given instance. Using this, we present a simple instance, where the
optimal distortion achievable by randomized SCFs is strictly larger than 2,
roughly 2.063164, thereby disproving the above conjecture. This conjecture has
also been refuted independently by Charikar and Ramakrishnan [6], who also
give a slightly larger lower bound. However, our techniques differ
significantly from theirs and, in particular, the LP for computing an
instance-optimal randomized social choice function may be of independent
interest.

##  2 Preliminaries

The metric single winner determination problem can be stated equivalently as
the 1-median problem where the voters are the set of clients, and the
candidates correspond to the set of facilities. Let $\mathcal{C}$ be a set of
clients and $\mathcal{F}$ be a set of facilities, located in a metric space
$(\mathcal{M},d)$, where $d_{fi}$ is the distance from client $i$ to facility
$f$. We would like to choose a facility that minimizes
$\sum_{j\in\mathcal{C}}d_{fj}$, the total cost incurred by the clients. If the
clients disclose their distance vectors, this optimization problem becomes
quite straightforward, however, in our setting, the system designer is only
provided the clients’ preference rankings over facilities,
$\sigma=[\succeq_{i}]_{i\in\mathcal{C}}$. In this context, one should assume
that the underlying metric $d$ is consistent with $\sigma$ (denoted
$d\triangleleft\sigma$); that is, if a client $i$ prefers facility $a$ over
facility $b$ (denoted $a\succeq_{i}b$, or $a\succeq b$ if the context is
sufficiently clear), $a$ is closer to $i$ than $b$ ($d_{ai}\leq d_{bi}$).

A randomized _social choice function_ (SCF) $f$ maps a preference profile
$\sigma$ to a distribution over the candidates/facilities. As aforementioned,
the notion of _distortion_ can be used to quantify the efficiency-loss in the
worst case. Formally, for a randomized social choice function $f$, we define

$\text{distortion}(f)=\sup_{\sigma}\sup_{d\triangleleft\,\sigma}\frac{\mathbb{E}\left[\sum_{j=1}^{n}d_{f(\sigma)j}\right]}{\min_{o\in\mathcal{F}}\sum_{j=1}^{n}d_{oj}}$

##  3 Computing an instance-optimal randomized SCF

In this section we give a linear program which, given a preference profile
$\sigma$, computes an instance-optimal randomized social choice function. In
order to do so, we first consider the adversary’s problem: Given a preference
profile $\sigma$, randomized SCF $f$, and optimal facility $o$, the adversary
wishes to compute a metric $d$ that is consistent with $\sigma$ and maximizes
$\frac{\mathbb{E}[\sum_{j\in\mathcal{C}}d_{f(\sigma)j}]}{\sum_{j\in\mathcal{C}}d_{oj}}$.
This can be done by solving the linear program ($P_{qo}$), where $q$ is the
distribution over the facilities specified by $f(\sigma)$. In the following,
we use $\text{alt}(k,r)$ to denote the $r$th ranked outcome in $\succeq_{k}$.

$\displaystyle\max$
$\displaystyle~{}~{}\sum_{i\in\mathcal{F}}\sum_{j\in\mathcal{C}}q_{i}d_{ij}$
($P_{qo}$) s.t. $\displaystyle~{}~{}\sum_{j\in\mathcal{C}}d_{oj}\leq 1$ (1)
$\displaystyle~{}~{}d_{\text{alt}(j,r),j}\leq d_{\text{alt}(j,r+1),j}$
$\displaystyle\forall j\in\mathcal{C}\,\forall r\in[m-1]$ (2)
$\displaystyle~{}~{}d_{ij}\leq d_{ik}+d_{jk}$ $\displaystyle\forall
i,j,k\in\mathcal{C}\cup\mathcal{F}$ (3) $\displaystyle~{}~{}d\geq 0$ (4)

Constraint (1) normalizes $\sum_{j\in\mathcal{C}}d_{oj}$ (allowing us to avoid
having a ratio in the objective), constraint (2) ensures that the metric $d$
is consistent with the preference profile $\sigma$, and constraints (3)-(4)
enforce that $d$ is a metric. The optimal solution $d$ is a metric that
maximizes
$\frac{\mathbb{E}[\sum_{j\in\mathcal{C}}d_{f(\sigma)j}]}{\sum_{j\in\mathcal{C}}d_{oj}}=\frac{\sum_{i\in\mathcal{F}}\sum_{j\in\mathcal{C}}q_{i}d_{ij}}{\sum_{j\in\mathcal{C}}d_{oj}}$.

We now return to our original task, which is to compute an instance-optimal
randomized SCF. Equivalently, we wish to compute an optimal distribution
$q\in\Delta_{F}$ that minimizes $\max_{o\in\mathcal{F}}\text{OPT}\eqref{exact-
primal}$. Notice that ($P_{qo}$) is of the form $\eqref{exact-
primal}:\min_{d}\\{c^{T}d:A^{o}d\leq b^{o},d\geq 0\\}$, where $c$ depends
linearly on $q$ and only $A^{o}$ and $b^{o}$ depend on the choice of $o$. The
dual of ($P_{qo}$) is $(D_{qo})$: $\min_{y}\\{y^{T}b^{o}:y^{T}A^{o}\geq
c,y\geq 0\\}$. So, the problem of computing an instance-optimal randomized SCF
is equivalent to

$\min_{q\in\Delta_{F}}\max_{o\in F}\text{OPT}\eqref{exact-
primal}=\min_{q\in\Delta_{F}}\\{\gamma:\text{OPT}\eqref{exact-
primal}\leq\gamma~{}\forall
o\in\mathcal{F}\\}=\min_{q\in\Delta_{F}}\\{\gamma:\exists y^{o}\geq
0~{}\text{s.t.}(y^{o})^{T}A^{o}\geq c,(y^{o})^{T}b\leq\gamma~{}\forall
o\in\mathcal{F}\\}$

where the last transition follows due to LP-duality. We expand the constraints
of the final LP, $(y^{o})^{T}A^{o}\geq c,(y^{o})^{T}b\leq\gamma$, to obtain
(Best-Dist) given below.

We use $\mathcal{T}_{\ell F}$ to denote the set of triangles
$i,j,k\in\mathcal{C}\cup\mathcal{F}$ that contain $\ell$ facilities. More
precisely, $\mathcal{T}_{0F}$ denotes triangles consisting of three clients,
$\mathcal{T}_{1F}$ denotes triangles consisting of a single facility and two
clients, $\mathcal{T}_{2F}=\\{(j,i_{1},i_{2}):j\in C,i_{1},i_{2}\in
F,i_{1}\neq i_{2},i_{1}\succeq_{j}i_{2}\\}$, and $\mathcal{T}_{3F}$ denotes
triangles consisting of three facilities.

$\displaystyle\min$ $\displaystyle~{}~{}\gamma$ (Best-Dist) s.t.
$\displaystyle~{}~{}\sum_{T=(i,j,\cdot)\in\mathcal{T}_{1F}}(-\alpha^{(1),o}_{1,T}+\alpha^{(1),o}_{2,T}-\alpha^{(1),o}_{3,T})+\sum_{T=(i,\cdot,j)\in\mathcal{T}_{1F}}(-\alpha^{(1),o}_{1,T}-\alpha^{(1),o}_{2,T}+\alpha^{(1),o}_{3,T})$
$\displaystyle\qquad+\sum_{T=(j,\cdot,i)\in\mathcal{T}_{2F}}(\alpha^{(2),o}_{1,T}-\alpha^{(2),o}_{2,T})+\sum_{T=(j,i,\cdot)\in\mathcal{T}_{2F}}(-\alpha^{(2),o}_{1,T}-\alpha^{(2),o}_{2,T})+\beta^{o}_{j1}\mathbbm{I}_{[i=\text{alt}(j,1)]}$
$\displaystyle\qquad+\sum_{r=1}^{n-2}(\beta^{o}_{j,r+1}-\beta^{o}_{j,r})\mathbbm{I}_{[i=\text{alt}(j,r+1)]}-\beta^{o}_{j,m-1}\mathbbm{I}_{[i=\text{alt}(j,m)]}+\gamma\mathbbm{I}_{[i=o]}\geq
q_{i}$ $\displaystyle\forall j\in\mathcal{C},\forall i\in\mathcal{F}\forall
o\in\mathcal{F}$ (5)
$\displaystyle~{}~{}\sum_{T=(i_{1},i_{2},\cdot)\in\mathcal{T}_{3F}}(\alpha^{(3),o}_{1,T}-\alpha^{(3),o}_{2,T}-\alpha^{(3),o}_{3,T})+\sum_{T=(i_{1},\cdot,i_{2})\in\mathcal{T}_{3F}}(-\alpha^{(3),o}_{1,T}+\alpha^{(3),o}_{2,T}-\alpha^{(3),o}_{3,T})$
$\displaystyle\qquad+\sum_{T=(\cdot,i_{1},i_{2})\in\mathcal{T}_{3F}}(-\alpha^{(3),o}_{1,T}-\alpha^{(3),o}_{2,T}+\alpha^{(3),o}_{3,T})+\sum_{T\in\mathcal{T}_{2F}:i_{1},i_{2}\in
T}(\alpha^{(2),o}_{2,T}-\alpha^{(2),o}_{1,T})\geq 0$ $\displaystyle\forall
i_{1},i_{2}\in\mathcal{F}\forall o\in\mathcal{F}$ (6)
$\displaystyle~{}~{}\sum_{(j_{1},j_{2},\cdot)\in\mathcal{T}_{0F}}(\alpha^{(0),o}_{1,T}-\alpha^{(0),o}_{2,T}-\alpha^{(0),o}_{3,T})+\sum_{(j_{1},\cdot,j_{2})\in\mathcal{T}_{0F}}(-\alpha^{(0),o}_{1,T}+\alpha^{(0),o}_{2,T}-\alpha^{(0),o}_{3,T})$
$\displaystyle\qquad+\sum_{(\cdot,j_{1},j_{2})\in\mathcal{T}_{0F}}(-\alpha^{(0),o}_{1,T}-\alpha^{(0),o}_{2,T}+\alpha^{(0),o}_{3,T})+\sum_{(\cdot,j_{1},j_{2})\in\mathcal{T}_{1F}}(\alpha^{(1),o}_{1,T}-\alpha^{(1),o}_{2,T}-\alpha^{(1),o}_{3,T})\geq
0$ $\displaystyle\forall j_{1},j_{2}\in\mathcal{C}\forall o\in\mathcal{F}$ (7)
$\displaystyle~{}~{}\sum_{i\in\mathcal{F}}q_{i}\geq 1$ (8)
$\displaystyle~{}~{}\alpha^{(0),o},\alpha^{(1),o},\alpha^{(2),o},\alpha^{(3),o},\beta^{o},\gamma,q\geq
0$ $\displaystyle\forall o\in\mathcal{F}$ (9)

The dual of (Best-Dist) is equivalent to

$\displaystyle\max$ $\displaystyle~{}~{}\varphi$ (Best-Dist-Dual) s.t.
$\displaystyle~{}~{}\sum_{o\in\mathcal{F}}\sum_{j\in\mathcal{C}}d^{o}_{oj}\leq
1$
$\displaystyle~{}~{}\varphi-\sum_{o\in\mathcal{F}}\sum_{j\in\mathcal{C}}d^{o}_{ij}\leq
0$ $\displaystyle\forall i\in\mathcal{F}$
$\displaystyle~{}~{}d^{o}_{\text{alt}(j,r),j}\leq d^{o}_{\text{alt}(j,r+1),j}$
$\displaystyle\forall j\in\mathcal{C}\,\forall r\in[m-1]\forall
o\in\mathcal{F}$ $\displaystyle~{}~{}d^{o}_{ij}\leq d^{o}_{ik}+d^{o}_{jk}$
$\displaystyle\forall i,j,k\in\mathcal{C}\cup\mathcal{F}\,\forall
o\in\mathcal{F}$ $\displaystyle~{}~{}\varphi,d^{o}\geq 0$
$\displaystyle\forall o\in\mathcal{F}$

###  3.1 A lower bound for the distortion of randomized SCFs

We show that, for any randomized social choice function $f$,
$distortion(f)\geq 2.063164$.

######  Theorem 3.1.

There exists an instance $(\mathcal{C},\mathcal{F},\sigma)$ such that, for any
randomized social choice function $f$,
$\sup_{d\triangleleft\,\sigma}\frac{\mathbb{E}[\sum_{j\in\mathcal{C}}d_{f(\sigma)j}]}{\min_{o\in\mathcal{F}}\sum_{j\in\mathcal{C}}d_{oj}}\geq
2.063164$.

###### Proof.

Consider the following instance with $\mathcal{C}=\\{1,2,3,4,5,6,7\\}$, and
$\mathcal{F}=\\{a,b,c,d,e,f,g\\}$. The preference profile $\sigma$ is given by

$\displaystyle 1,2,3:c\succeq e\succeq b\succeq a\succeq f\succeq g\succeq d,$
$\displaystyle 4,5,6:d\succeq g\succeq f\succeq a\succeq e\succeq b\succeq c,$
$\displaystyle 7:b\succeq a\succeq f\succeq g\succeq e\succeq c\succeq d$

For this instance, $\text{OPT}\eqref{opt-RSCF}=2.063164$ – that is, for any
randomized social choice function $f$,
$\sup_{d\triangleleft\,\sigma}\frac{\mathbb{E}[\sum_{j\in\mathcal{C}}d_{f(\sigma)j}]}{\min_{o\in\mathcal{F}}\sum_{j\in\mathcal{C}}d_{oj}}\geq
2.063164$. The instance-optimal distribution $q$ is

$\displaystyle q_{a}=0.039301$ $\displaystyle q_{b}=0.121723$ $\displaystyle
q_{c}=0.388299$ $\displaystyle q_{d}=0.291224$ $\displaystyle q_{e}=0.107872$
$\displaystyle q_{f}=0.029475$ $\displaystyle q_{g}=0.022107$

The values of the remaining variables are presented in Appendix A.

The optimal solution to the dual of (Best-Dist) also has value 2.063164, and
is given below. The dual variables $d^{a},d^{b},\ldots,d^{g}$ can be
interpreted as metrics, which are represented by the graphs given on the
following page. In this solution, clients with the same preference rankings
are colocated – namely, clients in $\mathcal{C}_{1}=\\{1,2,3\\}$ are colocated
and clients in $\mathcal{C}_{2}=\\{4,5,6\\}$ are colocated. The exact values
of the dual variables are presented in Appendix B.

$\mathcal{C}_{1}$$a$$\mathcal{C}_{2}$7$b$$c,e$$d,f,g$$M_{a}$$M_{a}$$M_{a}$$M_{a}$$M_{a}$$M_{a}$$M_{a}$
(a) For any $i,j\in\mathcal{C}\cup\mathcal{F}$, $d^{a}_{ij}$ is the shortest-
path distance in the above graph, where $M_{a}=0.014507$

$\mathcal{C}_{1}$$e$$b,7$$c$$a,d,f,g$$\mathcal{C}_{2}$$M_{b}$$M_{b}$$M_{b}$$M_{b}$$M_{b}$$M_{b}$
(b) For any $i,j\in\mathcal{C}\cup\mathcal{F}$, $d^{b}_{ij}$ is the shortest-
path distance in the above graph, where $M_{b}=0.020955$

$\mathcal{C}_{2}$$c,\mathcal{C}_{1}$$d$$a,b,e,f,g$$7$$M_{c}$$M_{c}$$M_{c}$$M_{c}$$M_{c}$
(c) For any $i,j\in\mathcal{C}\cup\mathcal{F}$, $d^{c}_{ij}$ is the shortest-
path distance in the above graph, where $M_{c}=0.038866$

$7$$\mathcal{C}_{1}$$d,\mathcal{C}_{2}$$a,b,c,e,f,g$$M_{d}$$M_{d}$$M_{d}$$M_{d}$$M_{d}$
(d) For any $i,j\in\mathcal{C}\cup\mathcal{F}$, $d^{d}_{ij}$ is the shortest-
path distance in the above graph, where $M_{d}=0.051820$

$d$$\mathcal{C}_{2}$$a,f,g$$7$$e$$b$$\mathcal{C}_{1}$$c$$M_{e}$$M_{e}$$M_{e}$$M_{e}$$M_{e}$$M_{e}$$M_{e}$$M_{e}$
(e) For any $i,j\in\mathcal{C}\cup\mathcal{F}$, $d^{e}_{ij}$ is the shortest-
path distance in the above graph, where $M_{e}=0.013433$

$c,e$$a,b$$d,g$$f$$\mathcal{C}_{1}$$\mathcal{C}_{2}$$7$$2M_{f}$$M_{f}$$M_{f}$$M_{f}$$M_{f}$$M_{f}$$M_{f}$$M_{f}$$2M_{f}$
(f) For any $i,j\in\mathcal{C}\cup\mathcal{F}$, $d^{f}_{ij}$ is the shortest-
path distance in the above graph, where $M_{f}=0.019343$

$d$$a,b,f$$\mathcal{C}_{2}$$7$$g$$\mathcal{C}_{1}$$c,e$$2M_{g}$$2M_{g}$$M_{g}$$M_{g}$$M_{g}$$M_{g}$$M_{g}$$M_{g}$$M_{g}$
(g) For any $i,j\in\mathcal{C}\cup\mathcal{F}$, $d^{g}_{ij}$ is the shortest-
path distance in the above graph, where $M_{g}=0.025791$

∎

## References

  * [1] E. Anshelevich, O. Bhardwaj, E. Elkind, J. Postl, and P. Skowron.  Approximating optimal social choice under metric preferences.  Artificial Intelligence, 264:27–51, Nov. 2018.
  * [2] E. Anshelevich, A. Filos-Ratsikas, N. Shah, and A. A. Voudouris.  Distortion in Social Choice Problems: The First 15 Years and Beyond.  In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, pages 4294–4301, 2021.
  * [3] E. Anshelevich and J. Postl.  Randomized Social Choice Functions Under Metric Preferences.  In J. Artif. Intell. Res., volume 58, pages 797–827, 2017.
  * [4] C. Boutilier, I. Caragiannis, S. Haber, T. Lu, A. D. Procaccia, and O. Sheffet.  Optimal social choice functions: A utilitarian view.  Artificial Intelligence, 227:190–213, Oct. 2015.
  * [5] F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors.  Handbook of Computational Social Choice.  Cambridge University Press, 2016.
  * [6] M. Charikar and P. Ramakrishnan.  Metric Distortion Bounds for Randomized Social Choice.  arXiv:2111.03694 [cs], Nov. 2021.
  * [7] V. Gkatzelis, D. Halpern, and N. Shah.  Resolving the Optimal Metric Distortion Conjecture.  In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 1427–1438, 2020.
  * [8] D. Kempe.  An Analysis Framework for Metric Voting based on LP Duality.  In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pages 2079–2086, 2020.
  * [9] D. Kempe.  Communication, distortion, and randomness in metric voting.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2087–2094, 2020.
  * [10] K. Munagala and K. Wang.  Improved Metric Distortion for Deterministic Social Choice Rules.  In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 245–262, June 2019.
  * [11] A. D. Procaccia and J. S. Rosenschein.  The distortion of cardinal preferences in voting.  In International Workshop on Cooperative Information Agents, pages 317–331. Springer, 2006.

##  Appendix A Optimal solution to (Best-Dist)

The optimal solution to (Best-Dist) is presented below (variables whose value
is zero have been omitted).

$\displaystyle\gamma=2.063164$ $\displaystyle\beta^{a}_{11}=0.905962$
$\displaystyle\beta^{a}_{21}=0.812009$ $\displaystyle\beta^{a}_{31}=0.776597$
$\displaystyle\beta^{a}_{41}=0.668060$ $\displaystyle\beta^{a}_{51}=0.771224$
$\displaystyle\beta^{a}_{61}=0.822806$ $\displaystyle\beta^{a}_{71}=0.653305$
$\displaystyle\beta^{a}_{12}=1.013834$ $\displaystyle\beta^{a}_{22}=1.027753$
$\displaystyle\beta^{a}_{32}=0.884469$ $\displaystyle\beta^{a}_{42}=0.815437$
$\displaystyle\beta^{a}_{52}=0.815437$ $\displaystyle\beta^{a}_{62}=0.844913$
$\displaystyle\beta^{a}_{13}=1.149475$ $\displaystyle\beta^{a}_{23}=1.149475$
$\displaystyle\beta^{a}_{33}=1.149475$ $\displaystyle\beta^{a}_{43}=0.874388$
$\displaystyle\beta^{a}_{53}=0.874388$ $\displaystyle\beta^{a}_{63}=0.874388$
$\displaystyle\beta^{a}_{25}=0.029475$ $\displaystyle\beta^{a}_{35}=0.029475$
$\displaystyle\beta^{a}_{45}=0.107872$ $\displaystyle\beta^{a}_{55}=0.107872$
$\displaystyle\beta^{a}_{65}=0.107872$ $\displaystyle\beta^{a}_{76}=0.223522$
$\displaystyle\beta^{b}_{11}=0.919881$ $\displaystyle\beta^{b}_{21}=0.919881$
$\displaystyle\beta^{b}_{31}=0.878328$ $\displaystyle\beta^{b}_{41}=0.582448$
$\displaystyle\beta^{b}_{51}=0.633313$ $\displaystyle\beta^{b}_{61}=0.822806$
$\displaystyle\beta^{b}_{12}=1.027753$ $\displaystyle\beta^{b}_{22}=1.027753$
$\displaystyle\beta^{b}_{32}=1.027753$ $\displaystyle\beta^{b}_{42}=0.626661$
$\displaystyle\beta^{b}_{52}=0.655420$ $\displaystyle\beta^{b}_{62}=0.844913$
$\displaystyle\beta^{b}_{43}=0.685612$ $\displaystyle\beta^{b}_{53}=0.714371$
$\displaystyle\beta^{b}_{63}=0.874388$ $\displaystyle\beta^{b}_{73}=0.058951$
$\displaystyle\beta^{b}_{44}=0.842814$ $\displaystyle\beta^{b}_{54}=0.792972$
$\displaystyle\beta^{b}_{64}=0.913689$ $\displaystyle\beta^{b}_{74}=0.125271$
$\displaystyle\beta^{b}_{45}=1.021561$ $\displaystyle\beta^{b}_{55}=1.021561$
$\displaystyle\beta^{b}_{65}=1.021561$ $\displaystyle\beta^{c}_{41}=0.822806$
$\displaystyle\beta^{c}_{51}=0.633313$ $\displaystyle\beta^{c}_{61}=0.582448$
$\displaystyle\beta^{c}_{71}=0.380657$ $\displaystyle\beta^{c}_{12}=0.107872$
$\displaystyle\beta^{c}_{22}=0.107872$ $\displaystyle\beta^{c}_{32}=0.107872$
$\displaystyle\beta^{c}_{42}=0.844913$ $\displaystyle\beta^{c}_{52}=0.655420$
$\displaystyle\beta^{c}_{62}=0.604554$ $\displaystyle\beta^{c}_{72}=0.537859$
$\displaystyle\beta^{c}_{43}=0.874388$ $\displaystyle\beta^{c}_{53}=0.684896$
$\displaystyle\beta^{c}_{63}=0.634030$ $\displaystyle\beta^{c}_{73}=0.655761$
$\displaystyle\beta^{c}_{44}=0.913689$ $\displaystyle\beta^{c}_{54}=0.724196$
$\displaystyle\beta^{c}_{64}=0.673330$ $\displaystyle\beta^{c}_{74}=0.744188$
$\displaystyle\beta^{c}_{45}=1.021561$ $\displaystyle\beta^{c}_{55}=0.832068$
$\displaystyle\beta^{c}_{65}=0.781203$ $\displaystyle\beta^{c}_{75}=0.852060$
$\displaystyle\beta^{c}_{46}=1.143284$ $\displaystyle\beta^{c}_{56}=1.143284$
$\displaystyle\beta^{c}_{66}=1.143284$ $\displaystyle\beta^{d}_{11}=0.579753$
$\displaystyle\beta^{d}_{21}=0.776597$ $\displaystyle\beta^{d}_{31}=0.441859$
$\displaystyle\beta^{d}_{71}=0.121723$ $\displaystyle\beta^{d}_{12}=0.687625$
$\displaystyle\beta^{d}_{22}=0.884469$ $\displaystyle\beta^{d}_{32}=0.549731$
$\displaystyle\beta^{d}_{72}=0.161023$ $\displaystyle\beta^{d}_{13}=1.038942$
$\displaystyle\beta^{d}_{23}=1.149475$ $\displaystyle\beta^{d}_{33}=0.987360$
$\displaystyle\beta^{d}_{73}=0.190499$ $\displaystyle\beta^{d}_{14}=1.078243$
$\displaystyle\beta^{d}_{24}=1.188776$ $\displaystyle\beta^{d}_{34}=1.144563$
$\displaystyle\beta^{d}_{74}=0.212606$ $\displaystyle\beta^{d}_{15}=1.196145$
$\displaystyle\beta^{d}_{25}=1.218256$ $\displaystyle\beta^{d}_{35}=1.174038$
$\displaystyle\beta^{d}_{45}=0.107872$ $\displaystyle\beta^{d}_{55}=0.107872$
$\displaystyle\beta^{d}_{65}=0.107872$ $\displaystyle\beta^{d}_{75}=0.320478$
$\displaystyle\beta^{d}_{16}=1.240358$ $\displaystyle\beta^{d}_{26}=1.240358$
$\displaystyle\beta^{d}_{36}=1.240358$ $\displaystyle\beta^{d}_{76}=1.240358$
$\displaystyle\beta^{e}_{11}=0.919881$ $\displaystyle\beta^{e}_{21}=0.919881$
$\displaystyle\beta^{e}_{31}=0.919881$ $\displaystyle\beta^{e}_{41}=0.661783$
$\displaystyle\beta^{e}_{51}=0.773953$ $\displaystyle\beta^{e}_{61}=0.602832$
$\displaystyle\beta^{e}_{71}=0.445339$ $\displaystyle\beta^{e}_{42}=0.683889$
$\displaystyle\beta^{e}_{52}=0.796060$ $\displaystyle\beta^{e}_{62}=0.624938$
$\displaystyle\beta^{e}_{72}=0.626286$ $\displaystyle\beta^{e}_{13}=0.121723$
$\displaystyle\beta^{e}_{23}=0.121723$ $\displaystyle\beta^{e}_{33}=0.121723$
$\displaystyle\beta^{e}_{43}=0.713365$ $\displaystyle\beta^{e}_{53}=0.855011$
$\displaystyle\beta^{e}_{63}=0.713365$ $\displaystyle\beta^{e}_{73}=0.655761$
$\displaystyle\beta^{e}_{44}=0.913689$ $\displaystyle\beta^{e}_{54}=0.913689$
$\displaystyle\beta^{e}_{64}=0.913689$ $\displaystyle\beta^{e}_{74}=0.744188$
$\displaystyle\beta^{e}_{66}=0.041552$ $\displaystyle\beta^{f}_{11}=0.919881$
$\displaystyle\beta^{f}_{21}=0.919881$ $\displaystyle\beta^{f}_{31}=0.536904$
$\displaystyle\beta^{f}_{41}=0.800699$ $\displaystyle\beta^{f}_{51}=0.778593$
$\displaystyle\beta^{f}_{61}=0.800699$ $\displaystyle\beta^{f}_{71}=0.574704$
$\displaystyle\beta^{f}_{12}=1.027753$ $\displaystyle\beta^{f}_{22}=1.027753$
$\displaystyle\beta^{f}_{32}=0.758857$ $\displaystyle\beta^{f}_{42}=0.844913$
$\displaystyle\beta^{f}_{52}=0.844913$ $\displaystyle\beta^{f}_{62}=0.844913$
$\displaystyle\beta^{f}_{72}=0.692606$ $\displaystyle\beta^{f}_{13}=1.149475$
$\displaystyle\beta^{f}_{23}=1.149475$ $\displaystyle\beta^{f}_{33}=1.110175$
$\displaystyle\beta^{f}_{14}=1.188776$ $\displaystyle\beta^{f}_{24}=1.188776$
$\displaystyle\beta^{f}_{34}=1.188776$ $\displaystyle\beta^{f}_{45}=0.107872$
$\displaystyle\beta^{f}_{55}=0.101663$ $\displaystyle\beta^{f}_{65}=0.107872$
$\displaystyle\beta^{f}_{76}=0.341424$ $\displaystyle\beta^{g}_{11}=0.776597$
$\displaystyle\beta^{g}_{21}=0.776597$ $\displaystyle\beta^{g}_{31}=0.776597$
$\displaystyle\beta^{g}_{41}=0.822806$ $\displaystyle\beta^{g}_{51}=0.822806$
$\displaystyle\beta^{g}_{61}=0.822806$ $\displaystyle\beta^{g}_{71}=0.580913$
$\displaystyle\beta^{g}_{12}=0.884469$ $\displaystyle\beta^{g}_{22}=0.950789$
$\displaystyle\beta^{g}_{32}=0.884469$ $\displaystyle\beta^{g}_{72}=0.692606$
$\displaystyle\beta^{g}_{13}=1.092503$ $\displaystyle\beta^{g}_{23}=1.072512$
$\displaystyle\beta^{g}_{33}=1.149475$ $\displaystyle\beta^{g}_{63}=0.029475$
$\displaystyle\beta^{g}_{73}=0.722081$ $\displaystyle\beta^{g}_{14}=1.159301$
$\displaystyle\beta^{g}_{24}=1.159301$ $\displaystyle\beta^{g}_{34}=1.188776$
$\displaystyle\beta^{g}_{15}=1.218252$ $\displaystyle\beta^{g}_{25}=1.218252$
$\displaystyle\beta^{g}_{35}=1.218252$ $\displaystyle\beta^{g}_{45}=0.107872$
$\displaystyle\beta^{g}_{55}=0.107872$ $\displaystyle\beta^{g}_{65}=0.107872$
$\displaystyle\beta^{g}_{75}=0.041552$ $\displaystyle\beta^{g}_{76}=0.429851$
$\displaystyle\alpha^{(1),a}_{1,(a,1,5)}=0.695693$
$\displaystyle\alpha^{(1),a}_{1,(a,1,7)}=0.164776$
$\displaystyle\alpha^{(1),a}_{1,(a,2,4)}=0.051582$
$\displaystyle\alpha^{(1),a}_{1,(a,2,5)}=0.035412$
$\displaystyle\alpha^{(1),a}_{1,(a,2,6)}=0.679522$
$\displaystyle\alpha^{(1),a}_{1,(a,2,7)}=0.107872$
$\displaystyle\alpha^{(1),a}_{1,(a,3,4)}=0.874388$
$\displaystyle\alpha^{(1),a}_{1,(a,4,7)}=0.223505$
$\displaystyle\alpha^{(1),a}_{1,(a,5,7)}=0.418371$
$\displaystyle\alpha^{(1),a}_{1,(a,6,7)}=0.456034$
$\displaystyle\alpha^{(1),b}_{1,(b,1,5)}=0.575539$
$\displaystyle\alpha^{(1),b}_{1,(b,1,7)}=0.338149$
$\displaystyle\alpha^{(1),b}_{1,(b,2,4)}=0.068776$
$\displaystyle\alpha^{(1),b}_{1,(b,2,5)}=0.143283$
$\displaystyle\alpha^{(1),b}_{1,(b,2,6)}=0.679522$
$\displaystyle\alpha^{(1),b}_{1,(b,2,7)}=0.022106$
$\displaystyle\alpha^{(1),b}_{1,(b,3,4)}=0.740929$
$\displaystyle\alpha^{(1),b}_{1,(b,3,5)}=0.029475$
$\displaystyle\alpha^{(1),b}_{1,(b,3,7)}=0.143284$
$\displaystyle\alpha^{(1),b}_{1,(b,4,7)}=0.110175$
$\displaystyle\alpha^{(1),b}_{1,(b,5,7)}=0.171582$
$\displaystyle\alpha^{(1),b}_{1,(b,6,7)}=0.240358$
$\displaystyle\alpha^{(1),c}_{1,(c,1,2)}=0.229595$
$\displaystyle\alpha^{(1),c}_{1,(c,1,3)}=0.058951$
$\displaystyle\alpha^{(1),c}_{1,(c,1,4)}=0.531582$
$\displaystyle\alpha^{(1),c}_{1,(c,1,6)}=0.240358$
$\displaystyle\alpha^{(1),c}_{1,(c,1,7)}=0.609023$
$\displaystyle\alpha^{(1),c}_{1,(c,2,3)}=0.029475$
$\displaystyle\alpha^{(1),c}_{1,(c,2,5)}=0.291224$
$\displaystyle\alpha^{(1),c}_{1,(c,2,7)}=0.061407$
$\displaystyle\alpha^{(1),c}_{1,(c,3,5)}=0.189493$
$\displaystyle\alpha^{(1),c}_{1,(c,3,6)}=0.291224$
$\displaystyle\alpha^{(1),c}_{1,(c,3,7)}=0.101510$
$\displaystyle\alpha^{(1),c}_{1,(c,5,7)}=0.050866$
$\displaystyle\alpha^{(1),d}_{1,(d,1,4)}=0.250405$
$\displaystyle\alpha^{(1),d}_{1,(d,1,5)}=0.229595$
$\displaystyle\alpha^{(1),d}_{1,(d,1,6)}=0.051582$
$\displaystyle\alpha^{(1),d}_{1,(d,2,4)}=0.143284$
$\displaystyle\alpha^{(1),d}_{1,(d,2,5)}=0.388299$
$\displaystyle\alpha^{(1),d}_{1,(d,3,4)}=0.161978$
$\displaystyle\alpha^{(1),d}_{1,(d,3,5)}=0.140009$
$\displaystyle\alpha^{(1),d}_{1,(d,3,6)}=0.229595$
$\displaystyle\alpha^{(1),d}_{1,(d,4,5)}=0.068776$
$\displaystyle\alpha^{(1),d}_{1,(d,4,7)}=0.143284$
$\displaystyle\alpha^{(1),d}_{1,(d,5,6)}=0.039301$
$\displaystyle\alpha^{(1),d}_{1,(d,6,7)}=0.388299$
$\displaystyle\alpha^{(1),e}_{1,(e,1,5)}=0.422431$
$\displaystyle\alpha^{(1),e}_{1,(e,1,6)}=0.590874$
$\displaystyle\alpha^{(1),e}_{1,(e,1,7)}=0.022107$
$\displaystyle\alpha^{(1),e}_{1,(e,2,4)}=0.388299$
$\displaystyle\alpha^{(1),e}_{1,(e,2,5)}=0.019377$
$\displaystyle\alpha^{(1),e}_{1,(e,2,6)}=0.320699$
$\displaystyle\alpha^{(1),e}_{1,(e,2,7)}=0.307036$
$\displaystyle\alpha^{(1),e}_{1,(e,3,4)}=0.452247$
$\displaystyle\alpha^{(1),e}_{1,(e,3,5)}=0.286567$
$\displaystyle\alpha^{(1),e}_{1,(e,3,6)}=0.029475$
$\displaystyle\alpha^{(1),e}_{1,(e,3,7)}=0.267121$
$\displaystyle\alpha^{(1),e}_{1,(e,4,7)}=0.201058$
$\displaystyle\alpha^{(1),e}_{1,(e,5,7)}=0.313228$
$\displaystyle\alpha^{(1),e}_{1,(e,6,7)}=0.100554$
$\displaystyle\alpha^{(1),f}_{1,(f,1,5)}=0.456614$
$\displaystyle\alpha^{(1),f}_{1,(f,1,6)}=0.388299$
$\displaystyle\alpha^{(1),f}_{1,(f,2,4)}=0.577791$
$\displaystyle\alpha^{(1),f}_{1,(f,2,6)}=0.022107$
$\displaystyle\alpha^{(1),f}_{1,(f,3,4)}=0.465706$
$\displaystyle\alpha^{(1),f}_{1,(f,3,5)}=0.224461$
$\displaystyle\alpha^{(1),f}_{1,(f,3,7)}=0.154746$
$\displaystyle\alpha^{(1),f}_{1,(f,4,7)}=0.145279$
$\displaystyle\alpha^{(1),f}_{1,(f,5,7)}=0.262687$
$\displaystyle\alpha^{(1),f}_{1,(f,6,7)}=0.778371$
$\displaystyle\alpha^{(1),g}_{1,(g,1,4)}=0.474610$
$\displaystyle\alpha^{(1),g}_{1,(g,1,5)}=0.056972$
$\displaystyle\alpha^{(1),g}_{1,(g,1,6)}=0.291224$
$\displaystyle\alpha^{(1),g}_{1,(g,2,4)}=0.320699$
$\displaystyle\alpha^{(1),g}_{1,(g,2,5)}=0.388299$
$\displaystyle\alpha^{(1),g}_{1,(g,2,6)}=0.047488$
$\displaystyle\alpha^{(1),g}_{1,(g,2,7)}=0.066320$
$\displaystyle\alpha^{(1),g}_{1,(g,3,4)}=0.143284$
$\displaystyle\alpha^{(1),g}_{1,(g,3,5)}=0.291224$
$\displaystyle\alpha^{(1),g}_{1,(g,3,6)}=0.388299$
$\displaystyle\alpha^{(1),g}_{1,(g,4,7)}=0.279659$
$\displaystyle\alpha^{(1),g}_{1,(g,5,7)}=0.481757$
$\displaystyle\alpha^{(1),g}_{1,(g,6,7)}=0.491241$
$\displaystyle\alpha^{(1),b}_{2,(a,1,5)}=0.039301$
$\displaystyle\alpha^{(1),e}_{2,(a,1,6)}=0.161023$
$\displaystyle\alpha^{(1),c}_{2,(a,1,7)}=0.039301$
$\displaystyle\alpha^{(1),b}_{2,(a,2,4)}=0.039301$
$\displaystyle\alpha^{(1),e}_{2,(a,2,5)}=0.019377$
$\displaystyle\alpha^{(1),c}_{2,(a,2,7)}=0.039301$
$\displaystyle\alpha^{(1),e}_{2,(a,2,7)}=0.141646$
$\displaystyle\alpha^{(1),b}_{2,(a,3,4)}=0.039301$
$\displaystyle\alpha^{(1),e}_{2,(a,3,4)}=0.161023$
$\displaystyle\alpha^{(1),c}_{2,(a,3,7)}=0.039301$
$\displaystyle\alpha^{(1),d}_{2,(a,4,5)}=0.039301$
$\displaystyle\alpha^{(1),g}_{2,(a,4,7)}=0.039301$
$\displaystyle\alpha^{(1),f}_{2,(a,5,7)}=0.039301$
$\displaystyle\alpha^{(1),g}_{2,(a,5,7)}=0.011804$
$\displaystyle\alpha^{(1),f}_{2,(a,6,7)}=0.039301$
$\displaystyle\alpha^{(1),g}_{2,(a,6,7)}=0.021288$
$\displaystyle\alpha^{(1),c}_{2,(b,1,6)}=0.240358$
$\displaystyle\alpha^{(1),b}_{2,(b,1,7)}=0.218832$
$\displaystyle\alpha^{(1),b}_{2,(b,3,5)}=0.189493$
$\displaystyle\alpha^{(1),b}_{2,(b,3,7)}=0.040102$
$\displaystyle\alpha^{(1),a}_{2,(b,4,7)}=0.086311$
$\displaystyle\alpha^{(1),e}_{2,(b,4,7)}=0.121723$
$\displaystyle\alpha^{(1),a}_{2,(b,5,7)}=0.229595$
$\displaystyle\alpha^{(1),e}_{2,(b,5,7)}=0.121723$
$\displaystyle\alpha^{(1),f}_{2,(b,5,7)}=0.223386$
$\displaystyle\alpha^{(1),g}_{2,(b,5,7)}=0.229595$
$\displaystyle\alpha^{(1),a}_{2,(b,6,7)}=0.215676$
$\displaystyle\alpha^{(1),e}_{2,(b,6,7)}=0.080171$
$\displaystyle\alpha^{(1),f}_{2,(b,6,7)}=0.229595$
$\displaystyle\alpha^{(1),g}_{2,(b,6,7)}=0.229595$
$\displaystyle\alpha^{(1),d}_{2,(b,4,7)}=0.143284$
$\displaystyle\alpha^{(1),d}_{2,(c,6,7)}=0.388299$
$\displaystyle\alpha^{(1),c}_{2,(d,1,4)}=0.531582$
$\displaystyle\alpha^{(1),a}_{2,(d,1,5)}=0.291224$
$\displaystyle\alpha^{(1),b}_{2,(d,1,5)}=0.291224$
$\displaystyle\alpha^{(1),e}_{2,(d,1,5)}=0.291224$
$\displaystyle\alpha^{(1),f}_{2,(d,1,5)}=0.291224$
$\displaystyle\alpha^{(1),g}_{2,(d,1,6)}=0.291224$
$\displaystyle\alpha^{(1),f}_{2,(d,2,4)}=0.291224$
$\displaystyle\alpha^{(1),g}_{2,(d,2,4)}=0.291224$
$\displaystyle\alpha^{(1),b}_{2,(d,2,5)}=0.291224$
$\displaystyle\alpha^{(1),a}_{2,(d,2,6)}=0.291224$
$\displaystyle\alpha^{(1),b}_{2,(d,2,6)}=0.291224$
$\displaystyle\alpha^{(1),e}_{2,(d,2,6)}=0.291224$
$\displaystyle\alpha^{(1),a}_{2,(d,3,4)}=0.291224$
$\displaystyle\alpha^{(1),b}_{2,(d,3,4)}=0.291224$
$\displaystyle\alpha^{(1),e}_{2,(d,3,4)}=0.291224$
$\displaystyle\alpha^{(1),f}_{2,(d,3,4)}=0.095079$
$\displaystyle\alpha^{(1),f}_{2,(d,3,5)}=0.196145$
$\displaystyle\alpha^{(1),g}_{2,(d,3,5)}=0.291224$
$\displaystyle\alpha^{(1),c}_{2,(d,3,6)}=0.291224$
$\displaystyle\alpha^{(1),a}_{2,(f,1,5)}=0.029475$
$\displaystyle\alpha^{(1),e}_{2,(f,1,5)}=0.029475$
$\displaystyle\alpha^{(1),b}_{2,(f,1,7)}=0.029475$
$\displaystyle\alpha^{(1),c}_{2,(f,1,7)}=0.088426$
$\displaystyle\alpha^{(1),c}_{2,(f,2,3)}=0.029475$
$\displaystyle\alpha^{(1),b}_{2,(f,2,4)}=0.029475$
$\displaystyle\alpha^{(1),e}_{2,(f,2,6)}=0.029475$
$\displaystyle\alpha^{(1),b}_{2,(f,3,5)}=0.029475$
$\displaystyle\alpha^{(1),e}_{2,(f,3,6)}=0.029475$
$\displaystyle\alpha^{(1),a}_{2,(g,1,5)}=0.022107$
$\displaystyle\alpha^{(1),f}_{2,(g,1,5)}=0.022107$
$\displaystyle\alpha^{(1),b}_{2,(g,1,7)}=0.022107$
$\displaystyle\alpha^{(1),c}_{2,(g,1,7)}=0.022107$
$\displaystyle\alpha^{(1),e}_{2,(g,1,7)}=0.022107$
$\displaystyle\alpha^{(1),a}_{2,(g,2,4)}=0.051582$
$\displaystyle\alpha^{(1),f}_{2,(g,2,6)}=0.022107$
$\displaystyle\alpha^{(1),b}_{2,(g,2,7)}=0.022107$
$\displaystyle\alpha^{(1),c}_{2,(g,2,7)}=0.022107$
$\displaystyle\alpha^{(1),e}_{2,(g,2,7)}=0.022107$
$\displaystyle\alpha^{(1),a}_{2,(g,3,4)}=0.051582$
$\displaystyle\alpha^{(1),b}_{2,(g,3,4)}=0.022107$
$\displaystyle\alpha^{(1),f}_{2,(g,3,5)}=0.022107$
$\displaystyle\alpha^{(1),c}_{2,(g,3,7)}=0.022107$
$\displaystyle\alpha^{(1),e}_{2,(g,3,7)}=0.022107$
$\displaystyle\alpha^{(1),g}_{3,(a,1,5)}=0.027497$
$\displaystyle\alpha^{(1),g}_{3,(a,2,6)}=0.047489$
$\displaystyle\alpha^{(1),f}_{3,(a,3,4)}=0.039301$
$\displaystyle\alpha^{(1),d}_{3,(a,3,5)}=0.117902$
$\displaystyle\alpha^{(1),b}_{3,(a,4,7)}=0.039301$
$\displaystyle\alpha^{(1),d}_{3,(a,5,6)}=0.039301$
$\displaystyle\alpha^{(1),c}_{3,(b,1,2)}=0.229595$
$\displaystyle\alpha^{(1),g}_{3,(b,1,4)}=0.086311$
$\displaystyle\alpha^{(1),d}_{3,(b,1,5)}=0.229595$
$\displaystyle\alpha^{(1),d}_{3,(b,2,4)}=0.143284$
$\displaystyle\alpha^{(1),a}_{3,(b,3,4)}=0.143284$
$\displaystyle\alpha^{(1),d}_{3,(b,3,4)}=0.086311$
$\displaystyle\alpha^{(1),f}_{3,(b,3,4)}=0.229595$
$\displaystyle\alpha^{(1),g}_{3,(b,3,4)}=0.143284$
$\displaystyle\alpha^{(1),d}_{3,(b,3,6)}=0.229595$
$\displaystyle\alpha^{(1),d}_{3,(c,1,4)}=0.191454$
$\displaystyle\alpha^{(1),g}_{3,(c,1,4)}=0.388299$
$\displaystyle\alpha^{(1),a}_{3,(c,1,5)}=0.352887$
$\displaystyle\alpha^{(1),b}_{3,(c,1,5)}=0.245015$
$\displaystyle\alpha^{(1),e}_{3,(c,1,5)}=0.101731$
$\displaystyle\alpha^{(1),f}_{3,(c,1,5)}=0.143284$
$\displaystyle\alpha^{(1),e}_{3,(c,1,6)}=0.429851$
$\displaystyle\alpha^{(1),f}_{3,(c,1,6)}=0.388299$
$\displaystyle\alpha^{(1),a}_{3,(c,1,7)}=0.164776$
$\displaystyle\alpha^{(1),b}_{3,(c,1,7)}=0.286567$
$\displaystyle\alpha^{(1),e}_{3,(c,2,4)}=0.388299$
$\displaystyle\alpha^{(1),f}_{3,(c,2,4)}=0.286567$
$\displaystyle\alpha^{(1),a}_{3,(c,2,5)}=0.035412$
$\displaystyle\alpha^{(1),b}_{3,(c,2,5)}=0.143284$
$\displaystyle\alpha^{(1),d}_{3,(c,2,5)}=0.388299$
$\displaystyle\alpha^{(1),g}_{3,(c,2,5)}=0.388299$
$\displaystyle\alpha^{(1),a}_{3,(c,2,6)}=0.388299$
$\displaystyle\alpha^{(1),b}_{3,(c,2,6)}=0.388299$
$\displaystyle\alpha^{(1),e}_{3,(c,2,7)}=0.143284$
$\displaystyle\alpha^{(1),a}_{3,(c,3,4)}=0.388299$
$\displaystyle\alpha^{(1),b}_{3,(c,3,4)}=0.388299$
$\displaystyle\alpha^{(1),d}_{3,(c,3,4)}=0.053561$
$\displaystyle\alpha^{(1),f}_{3,(c,3,4)}=0.101731$
$\displaystyle\alpha^{(1),e}_{3,(c,3,5)}=0.286567$
$\displaystyle\alpha^{(1),g}_{3,(c,3,6)}=0.388299$
$\displaystyle\alpha^{(1),b}_{3,(c,3,7)}=0.101731$
$\displaystyle\alpha^{(1),e}_{3,(c,3,7)}=0.245015$
$\displaystyle\alpha^{(1),f}_{3,(c,3,7)}=0.046874$
$\displaystyle\alpha^{(1),c}_{3,(d,1,7)}=0.240358$
$\displaystyle\alpha^{(1),a}_{3,(d,4,7)}=0.085612$
$\displaystyle\alpha^{(1),e}_{3,(d,4,7)}=0.079335$
$\displaystyle\alpha^{(1),f}_{3,(d,4,7)}=0.123173$
$\displaystyle\alpha^{(1),g}_{3,(d,4,7)}=0.240358$
$\displaystyle\alpha^{(1),a}_{3,(d,5,7)}=0.188776$
$\displaystyle\alpha^{(1),b}_{3,(d,5,7)}=0.050865$
$\displaystyle\alpha^{(1),c}_{3,(d,5,7)}=0.050866$
$\displaystyle\alpha^{(1),e}_{3,(d,5,7)}=0.191505$
$\displaystyle\alpha^{(1),g}_{3,(d,5,7)}=0.240358$
$\displaystyle\alpha^{(1),a}_{3,(d,6,7)}=0.240358$
$\displaystyle\alpha^{(1),b}_{3,(d,6,7)}=0.240358$
$\displaystyle\alpha^{(1),e}_{3,(d,6,7)}=0.020384$
$\displaystyle\alpha^{(1),f}_{3,(d,6,7)}=0.509475$
$\displaystyle\alpha^{(1),g}_{3,(d,6,7)}=0.240358$
$\displaystyle\alpha^{(1),a}_{3,(e,2,7)}=0.107872$
$\displaystyle\alpha^{(1),g}_{3,(e,2,7)}=0.066320$
$\displaystyle\alpha^{(1),f}_{3,(e,3,5)}=0.006209$
$\displaystyle\alpha^{(1),b}_{3,(e,3,7)}=0.041552$
$\displaystyle\alpha^{(1),f}_{3,(e,3,7)}=0.107872$
$\displaystyle\alpha^{(1),b}_{3,(e,4,7)}=0.070874$
$\displaystyle\alpha^{(1),b}_{3,(e,5,7)}=0.120716$
$\displaystyle\alpha^{(1),c}_{3,(f,1,3)}=0.058951$
$\displaystyle\alpha^{(1),d}_{3,(f,1,4)}=0.058951$
$\displaystyle\alpha^{(1),g}_{3,(f,1,5)}=0.029475$
$\displaystyle\alpha^{(1),d}_{3,(f,1,6)}=0.029475$
$\displaystyle\alpha^{(1),g}_{3,(f,2,4)}=0.029475$
$\displaystyle\alpha^{(1),d}_{3,(f,4,5)}=0.029475$
$\displaystyle\alpha^{(1),a}_{3,(f,4,7)}=0.029475$
$\displaystyle\alpha^{(1),d}_{3,(g,1,6)}=0.022107$
$\displaystyle\alpha^{(1),d}_{3,(g,3,4)}=0.022107$
$\displaystyle\alpha^{(1),d}_{3,(g,3,5)}=0.022107$
$\displaystyle\alpha^{(1),a}_{3,(g,4,7)}=0.022107$
$\displaystyle\alpha^{(1),f}_{3,(g,4,7)}=0.022107$
$\displaystyle\alpha^{(2),f}_{1,(5,f,c)}=0.245015$
$\displaystyle\alpha^{(2),a}_{1,(6,a,b)}=0.013919$
$\displaystyle\alpha^{(2),a}_{2,(1,b,a)}=0.013919$
$\displaystyle\alpha^{(2),f}_{2,(2,b,f)}=0.245015$

##  Appendix B Optimal solution to (Best-Dist-Dual)

Define $M_{a}=0.014507$, $M_{b}=0.020955$, $M_{c}=0.038866$ $,M_{d}=0.051820$,
$M_{e}=0.013433$, $M_{f}=0.019343$, and $M_{g}=0.025791$. The values of the
non-zero dual variables are given below.

$\begin{array}[]{lll}\varphi=2.063164\\\
d_{a,j}^{a}=M_{a}~{}j\in\mathcal{C}_{1}&d_{b,j}^{a}=M_{a}~{}j\in\mathcal{C}_{1}&d_{c,j}^{a}=M_{a}~{}j\in\mathcal{C}_{1}\\\
d_{d,j}^{a}=3M_{a}~{}j\in\mathcal{C}_{1}&d_{e,j}^{a}=M_{a}~{}j\in\mathcal{C}_{1}&d_{f,j}^{a}=3M_{a}~{}j\in\mathcal{C}_{1}\\\
d_{g,j}^{a}=3M_{a}~{}j\in\mathcal{C}_{1}&d_{a,j}^{a}=M_{a}~{}j\in\mathcal{C}_{2}&d_{b,j}^{a}=3M_{a}~{}j\in\mathcal{C}_{2}\\\
d_{c,j}^{a}=3M_{a}~{}j\in\mathcal{C}_{2}&d_{d,j}^{a}=M_{a}~{}j\in\mathcal{C}_{2}&d_{e,j}^{a}=3M_{a}~{}j\in\mathcal{C}_{2}\\\
d_{f,j}^{a}=M_{a}~{}j\in\mathcal{C}_{2}&d_{g,j}^{a}=M_{a}~{}j\in\mathcal{C}_{2}&d_{i,7}^{a}=M_{a}~{}i\in\\{a,b\\}\\\
d_{i,7}^{a}=3M_{a}~{}i\in\mathcal{F}\setminus\\{a,b\\}&d_{a,i}^{a}=2M_{a}~{}i\in\mathcal{F}\setminus\\{a\\}&d_{b,i}^{a}=2M_{a}~{}i\in\mathcal{F}\setminus\\{b\\}\\\
d_{c,i}^{a}=2M_{a}~{}i\in\mathcal{F}\setminus\\{c,e\\}&d_{d,i}^{a}=2M_{a}~{}i\in\mathcal{F}\setminus\\{d,f,g\\}&d_{e,i}^{a}=2M_{a}~{}i\in\mathcal{F}\setminus\\{c,e\\}\\\
d_{f,i}^{a}=2M_{a}~{}i\in\mathcal{F}\setminus\\{d,f,g\\}&d_{g,i}^{a}=2M_{a}~{}i\in\mathcal{F}\setminus\\{d,f,g\\}&d_{j_{1},j_{2}}^{a}=2M_{a}~{}j_{1}\in\mathcal{C}_{1},j_{2}\in\mathcal{C}_{2}\\\
d_{j,7}^{a}=2M_{a}~{}\forall
j\in\mathcal{C}_{1}\cup\mathcal{C}_{2}\\\\[10.0pt]
d_{a,j}^{b}=3M_{b}~{}j\in\mathcal{C}_{1}&d_{b,j}^{b}=M_{b}~{}j\in\mathcal{C}_{1}&d_{c,j}^{b}=M_{b}~{}j\in\mathcal{C}_{1}\\\
d_{d,j}^{b}=3M_{b}~{}j\in\mathcal{C}_{1}&d_{e,j}^{b}=M_{b}~{}j\in\mathcal{C}_{1}&d_{f,j}^{b}=3M_{b}~{}j\in\mathcal{C}_{1}\\\
d_{g,j}^{b}=3M_{b}~{}j\in\mathcal{C}_{1}&d_{a,j}^{b}=M_{b}~{}j\in\mathcal{C}_{2}&d_{b,j}^{b}=M_{b}~{}j\in\mathcal{C}_{2}\\\
d_{c,j}^{b}=3M_{b}~{}j\in\mathcal{C}_{2}&d_{d,j}^{b}=M_{b}~{}j\in\mathcal{C}_{2}&d_{e,j}^{b}=M_{b}~{}j\in\mathcal{C}_{2}\\\
d_{f,j}^{b}=M_{b}~{}j\in\mathcal{C}_{2}&d_{g,j}^{b}=M_{b}~{}j\in\mathcal{C}_{2}&d_{i,7}^{b}=2M_{b}~{}i\in\mathcal{F}\setminus\\{b\\}\\\
d_{a,i}^{b}=2M_{b}~{}i\in\mathcal{F}\setminus\\{a,d,f,g\\}&d_{b,i}^{b}=2M_{b}~{}i\in\mathcal{F}\setminus\\{b\\}&d_{c,i}^{b}=2M_{b}~{}i\in\mathcal{F}\setminus\\{c\\}\\\
d_{d,i}^{b}=2M_{b}~{}i\in\mathcal{F}\setminus\\{a,d,f,g\\}&d_{e,i}^{b}=2M_{b}~{}i\in\mathcal{F}\setminus\\{e\\}&d_{f,i}^{b}=2M_{b}~{}i\in\mathcal{F}\setminus\\{a,d,f,g\\}\\\
d_{g,i}^{b}=2M_{b}~{}i\in\mathcal{F}\setminus\\{a,d,f,g\\}&d_{j_{1},j_{2}}^{b}=2M_{b}~{}j_{1}\in\mathcal{C}_{1},j_{2}\in\mathcal{C}_{2}&d_{j,7}^{b}=3M_{b}~{}j\in\mathcal{C}_{1}\cup\mathcal{C}_{2}\end{array}$

$\begin{array}[]{lll}d_{i,j}^{c}=2M_{c}~{}j\in\mathcal{C}_{1},i\in\mathcal{F}\setminus\\{c\\}&d_{i,j}^{c}=M_{c}~{}j\in\mathcal{C}_{2},i\in\mathcal{F}&d_{i,7}^{c}=M_{c}~{}i\in\mathcal{F}\setminus\\{d\\}\\\
d_{d,7}^{c}=3M_{c}&d_{c,i}^{c}=2M_{c}~{}i\in\mathcal{F}\setminus\\{c\\}&d_{d,i}^{c}=2M_{c}~{}i\in\mathcal{F}\setminus\\{d\\}\\\
d_{i_{1},i_{2}}^{c}=2M_{c}~{}i_{1}\notin\\{c,d\\},i_{2}\in\\{c,d\\}&d_{j,7}^{c}=M_{c}~{}j\in\mathcal{C}_{1}&d_{j,7}^{c}=2M_{c}~{}j\in\mathcal{C}_{2}\\\
d_{j_{1},j_{2}}^{c}=M_{c}~{}j_{1}\in\mathcal{C}_{1},j_{2}\in\mathcal{C}_{2}\\\\[10.0pt]
d_{i,j}^{d}=M_{d}~{}j\in\mathcal{C}_{1},i\in\mathcal{F}&d_{i,j}^{d}=2M_{d}~{}j\in\mathcal{C}_{2},i\in\mathcal{F}\setminus\\{d\\}&d_{i,7}^{d}=M_{d}~{}i\in\mathcal{F}\\\
d_{i,d}^{d}=2M_{d}~{}i\in\mathcal{F}\setminus\\{d\\}&d_{j_{1},j_{2}}^{d}=M_{d}~{}j_{1}\in\mathcal{C}_{1}j_{2}\in\mathcal{C}_{2}&d_{j,7}^{d}=M_{d}~{}j\in\mathcal{C}_{2}\\\\[10.0pt]
d_{i,j}^{e}=3M_{e}~{}j\in\mathcal{C}_{1},i\in\mathcal{F}\setminus\\{c,e\\}&d_{i,j}^{e}=M_{e}~{}j\in\mathcal{C}_{1},i\in\\{c,e\\}&d_{i,j}^{e}=M_{e}~{}j\in\mathcal{C}_{2},i\in\mathcal{F}\setminus\\{b,c\\}\\\
d_{i,j}^{e}=3M_{e}~{}j\in\mathcal{C}_{2},i\in\\{b,c\\}&d_{i,7}^{e}=M_{e}~{}i\in\mathcal{F}\setminus\\{c,d\\}&d_{i,7}^{e}=3M_{e}~{}i\in\\{c,d\\}\\\
d_{i_{1},i_{2}}^{e}=2M_{e}~{}i_{1}\in\\{a,f,g\\},i_{2}\notin\\{a,f,g\\}&d_{b,i}^{e}=2M_{e}~{}i\in\mathcal{F}\setminus\\{b\\}&d_{c,i}^{e}=2M_{e}~{}i\in\mathcal{F}\setminus\\{c\\}\\\
d_{d,i}^{e}=2M_{e}~{}i\in\mathcal{F}\setminus\\{d\\}&d_{e,i}^{e}=2M_{e}~{}i\in\mathcal{F}\setminus\\{e\\}&d_{j_{1},j_{2}}^{e}=2M_{e}~{}j_{1}\in\mathcal{C}_{1},j_{2}\in\mathcal{C}_{2}\\\
d_{j,7}^{e}=2M_{e}~{}j\in\mathcal{C}_{1}\cup\mathcal{C}_{2}\\\\[10.0pt]
d_{i,j}^{f}=M_{f}~{}j\in\mathcal{C}_{1},i\in\mathcal{F}\setminus\\{d,g\\}&d_{i,j}^{f}=3M_{f}~{}j\in\mathcal{C}_{1},i\in\\{d,g\\}&d_{i,j}^{f}=3M_{f}~{}j\in\mathcal{C}_{2},i\in\mathcal{F}\setminus\\{d,f,g\\}\\\
d_{i,j}^{f}=M_{f}~{}j\in\mathcal{C}_{2},i\in\\{d,f,g\\}&d_{i,7}^{f}=3M_{f}~{}i\in\mathcal{F}\setminus\\{a,b,f\\}&d_{i,7}^{f}=M_{f}~{}i\in\\{a,b,f\\}\\\
d_{a,i}^{f}=2M_{f}~{}i\in\mathcal{F}\setminus\\{a,b\\}&d_{b,i}^{f}=2M_{f}~{}i\in\mathcal{F}\setminus\\{a,b\\}&d_{c,i}^{f}=2M_{f}~{}i\in\mathcal{F}\setminus\\{c,e\\}\\\
d_{d,i}^{f}=2M_{f}~{}i\in\mathcal{F}\setminus\\{d,g\\}&d_{e,i}^{f}=2M_{f}~{}i\in\mathcal{F}\setminus\\{c,e\\}&d_{f,i}^{f}=2M_{f}~{}i\in\mathcal{F}\setminus\\{f\\}\\\
d_{g,i}^{f}=2M_{f}~{}i\in\mathcal{F}\setminus\\{d,g\\}&d_{j_{1},j_{2}}^{f}=2M_{f}~{}j_{1}\in\mathcal{C}_{1},j_{2}\in\mathcal{C}_{2}&d_{j,7}^{f}=2M_{f}~{}\forall
j\in\mathcal{C}_{1}\cup\mathcal{C}_{2}\\\\[10.0pt]
d_{i,j}^{g}=M_{g}~{}j\in\mathcal{C}_{1},i\in\mathcal{F}\setminus\\{d\\}&d_{d,j}^{g}=3M_{g}~{}j\in\mathcal{C}_{1}&d_{i,j}^{g}=3M_{g}~{}j\in\mathcal{C}_{2},i\in\mathcal{F}\setminus\\{d,g\\}\\\
d_{i,j}^{g}=M_{g}~{}j\in\mathcal{C}_{2},i\in\\{d,g\\}&d_{i,7}^{g}=M_{g}~{}i\in\mathcal{F}\setminus\\{c,d,e\\}&d_{i,7}^{g}=3M_{g}~{}i\in\\{c,d,e\\}\\\
d_{a,i}^{g}=2M_{g}~{}i\in\mathcal{F}\setminus\\{a,b,f\\}&d_{b,i}^{g}=2M_{g}~{}i\in\mathcal{F}\setminus\\{a,b,f\\}&d_{c,i}^{g}=2M_{g}~{}i\in\mathcal{F}\setminus\\{c,e\\}\\\
d_{d,i}^{g}=2M_{g}~{}i\in\mathcal{F}\setminus\\{d\\}&d_{f,i}^{g}=2M_{g}~{}i\in\mathcal{F}\setminus\\{a,b,f\\}&d_{g,i}^{g}=2M_{g}~{}i\in\mathcal{F}\setminus\\{g\\}\\\
d_{j_{1},j_{2}}^{g}=2M_{g}~{}j_{1}\in\mathcal{C}_{1},j_{2}\in\mathcal{C}_{2}&d_{j,7}^{g}=2M_{g}~{}\forall
j\in\mathcal{C}_{1}\cup\mathcal{C}_{2}\\\ \end{array}$