††thanks: These authors contributed equally to this manuscript.††thanks: These
authors contributed equally to this manuscript.††thanks: Corresponding
author.††thanks: Corresponding author.††thanks: Corresponding author.

# Recipe for single-pair-Weyl-points phonons carrying the same chiral charges

Guangqian Ding  School of Science, Chongqing University of Posts and
Telecommunications, Chongqing 400065, China  School of Physical Science and
Technology, Southwest University, Chongqing 400715, China  Chengwu Xie  School
of Physical Science and Technology, Southwest University, Chongqing 400715,
China  Jingbo Bai  School of Physical Science and Technology, Southwest
University, Chongqing 400715, China  Zhenxiang Cheng<EMAIL_ADDRESS>Institute for Superconducting and Electronic Materials (ISEM), University of
Wollongong, Wollongong 2500, Australia  Xiaotian Wang<EMAIL_ADDRESS>School of Physical Science and Technology, Southwest University, Chongqing
400715, China  Weikang Wu<EMAIL_ADDRESS>Key Laboratory for Liquid-
Solid Structural Evolution and Processing of Materials (Ministry of
Education), Shandong University, Jinan, Shandong 250061, China

###### Abstract

Recently, Wang et al. [Phys. Rev. B, 106, 195129 (2022)] challenged a widely
held belief in the field of Weyl physics, demonstrating that single-pair-Weyl-
points (SP-WPs) can exist in nonmagnetic spinless systems, contrary to
previous assumptions that they could only exist in magnetic systems. Wang et
al. observed that the SP-WPs with opposite and even chiral charges ($i.e.$,
$|\mathcal{C}|$ = 2 or 4) could also exist in nonmagnetic spinless systems. In
this Letter, we present a novel finding in which SP-WPs have a partner, namely
a charged nodal surface, in nonmagnetic spinless systems. In contrast to
previous observations, we show that the SP-WPs can have uneven chiral charges
($i.e.$, $|\mathcal{C}|$ = 1). We identify 6 (out of 230) space groups (SGs)
that contain such SP-WPs by searching the encyclopedia of emergent particles
in three-dimensional crystals. Our finds were confirmed through the phonon
spectra of two specific materials Zr3O (with SG 182) and NaPH2NO3 (with SG
173). This discovery broadens the range of materials that can host SP-WPs and
applies to other nonmagnetic spinless crystals.

Introduction. An outstanding challenge in Weyl physics is to realize an ideal
Weyl state with a minimal number of Weyl points (WPs), typically a single pair
add1 ; add2 . The presence of minimum WPs is due to the simplicity it provides
in studying their physical properties and imaging surface state modes in
spectroscopy experiments add3 . Theoretical models and experiments are
simplified when the number of WPs is kept to a minimum. In the past, it was
commonly believed that single-pair-Weyl-points (SP-WPs) could only be realized
in magnetic systems with broken time-reversal symmetry. The statement appeared
in the pioneering work by Wan et al. add4  and was cited in subsequent works
add3 ; add5 ; add6 ; add7 ; add8 ; add9 . Consequently, the search for SP-WPs
was focused on magnetic materials in the past decade, with limited success: To
date, there are only a few candidates, such as MnBi2Te4 add10 ; add11 ,
EuCd2As2 add12 ; add13 ; add14 , and their band structures are far from ideal.

In 2022, Wang et al. add15  discovered a loophole in Wan et al’s original
argument add4 , demonstrating that a single pair of Weyl points can exist in
nonmagnetic systems. Specifically, Wang et al. add15  showed that the SP-WPs
could exist at two time-reversal-invariant momenta points in nonmagnetic
spinless systems. Moreover, they add15  proved that the two WPs of the SP-WPs
have opposite and even charges ($i.e.$, $|\mathcal{C}|$ = 2 or 4). Following
this breakthrough, Li et al. add16  experimentally observed SP-WPs with
$|\mathcal{C}|$ = 2 (specifically, one WP with $|\mathcal{C}|$ = 2 and the
other one with $|\mathcal{C}|$ = $-$2) in artificial periodic systems.
Moreover, Wang et al. add17  proposed an ideal artificial periodic system to
realize the SP-WPs with $|\mathcal{C}|$ = 4 (specifically, one WP with
$|\mathcal{C}|$ = 4 and the other one WP with $|\mathcal{C}|$ = $-$4), noting
that the charges in WPs have an upper limit and that their maximum charge
should be four ($|\mathcal{C}|$ = 4) add18 ; add19 ; add20 ; add21 ; add22 .

One may wonder if each WPs of the SP-WPs at the high-symmetry points (HSPs)
can have the same and uneven charge. In this work, we demonstrate that it is
possible to achieve two WPs with a same and uneven charge in the nonmagnetic
spinless systems if the SP-WPs have a partner, $i.e.$, a charged nodal surface
state. To achieve such SP-WPs, we searched the encyclopedia of emergent
particles in 3D crystals add18  and developed a strategy. We find that SP-WPs
at the HSPs (with a same and uneven charge) can be hosted in 6 (out of 230)
space groups (SGs), and we confirm that the $|\mathcal{C}|$ of each WP is
equal to 1. We then demonstrate our approach by presenting the phonon
dispersions for two realistic material candidates Zr3O (with SG 182) and
NaPH2NO3 (with SG 173). It is worth noting that phonons add23 ; add24 ; add25
play a vital role in many solid-state system features, including thermal and
electrical conductivity, neutron scattering, and related phenomena such as
superconductivity. Consequently, it is hoped that topological phonons add26 ;
add27 ; add28 ; add29 ; add30 ; add31 ; add32 ; add33 ; add34 ; add35 ; add36
; add37 ; add38 ; add39 ; add40 ; add41 ; add42 ; add43 ; add44 ; add45 ;
add46  will lead to rich and unconventional physics, and the search for
materials containing topological phonons will become a key priority in the
field.

In both materials, SP-WPs (with $|\mathcal{C}|$ = $+1$ for Zr3O and with
$|\mathcal{C}|$ = $-1$ for NaPH2NO3), along with a partner charged nodal
surface state (with $|\mathcal{C}|$ = $-2$ for Zr3O and with $|\mathcal{C}|$ =
$+2$ for NaPH2NO3), appear in their phonon spectrums. Note that all the phonon
bands are relevant for experimental detection, as the phonons are not subject
to the Pauli exclusion principle and Fermi surface constraints. In addition to
achieving two WPs with a same charge, these systems have another advantage
add47 ; add48 : A charged nodal surface state appears at the $k_{z}=\pm\pi$
planes in the Brillouin zone (BZ), allowing investigation of the relationship
between the charged WPs and the charged nodal surface in a single system. Our
proposal applies to spinless systems ranging from phononic to other bosonic
systems, and even to electronic systems without spin-orbit coupling.

Table 1:  The candidate SGs that can host C-1 SP-WPs (with the same charge) in spinless systems. Irreps denotes the irreducible (co-) representation of the little group associated with the two C-1 WP at the K and K’ HSPs. The symbols of the Irreps are adapted from Refs. add18 ; add55 . SG | Generators | HSPs | Irreps | Species | Materials
---|---|---|---|---|---
169 |  $\\{C_{3}^{+}|00\frac{1}{3}\\}$,$\\{C_{6}^{+}|00\frac{1}{6}\\}\mathcal{T}$ | K; K’ | $R_{2},R_{3}$ | C-1 WP |
170 |  $\\{C_{3}^{+}|00\frac{1}{3}\\}$,$\\{C_{6}^{+}|00\frac{1}{6}\\}\mathcal{T}$ | K; K’ | $R_{2},R_{3}$ | C-1 WP | Tl3PO4, Tl3AsO4,
|  |  |  |  | Y3CuGeS7, NaPH2NO3
173 |  $\\{C_{3}^{+}|000\\}$,$\\{C_{6}^{+}|00\frac{1}{2}\\}\mathcal{T}$ | K; K’ | $R_{2},R_{3}$ | C-1 WP |
178 |  $\\{C_{3}^{+}|00\frac{1}{3}\\}$,$\\{C_{21}^{{}^{\prime\prime}}|00\frac{1}{2}\\}$,$\\{C_{6}^{+}|00\frac{1}{6}\\}\mathcal{T}$ | K; K’ | $R_{3}$ | C-1 WP | Hf5Ir3
179 |  $\\{C_{3}^{+}|00\frac{2}{3}\\}$,$\\{C_{21}^{{}^{\prime\prime}}|00\frac{1}{2}\\}$,$\\{C_{6}^{+}|00\frac{5}{6}\\}\mathcal{T}$ | K; K’ | $R_{3}$ | C-1 WP |
182 |  $\\{C_{3}^{+}|000\\}$,$\\{C_{21}^{{}^{\prime\prime}}|00\frac{1}{2}\\}$,$\\{C_{6}^{+}|00\frac{1}{2}\\}\mathcal{T}$ | K; K’ | $R_{3}$ | C-1 WP | ReO3, Zr3O

General analysis. Based on the Nielsen-Ninomiya no-go theorem add49 ; add50 ,
Weyl systems must satisfy compensation effects. This means that there must be
at least one pair of Weyl points (WPs) with opposite charges in the BZ, and
the total chiral charge of all the WPs should be zero. Thus, two WPs with the
same charge ($i.e.$, all the WPs have a net chiral charge) cannot exist alone
in the BZ. In order to eliminate the net chiral charge in BZ, the two WPs
(with a same charge) need a partner in the BZ.

In this work, we focus on spinless systems and consider charged nodal surfaces
as the partner of the two WPs. First, we list $three$ $symmetry$ $conditions$
that can help to realize SP-WPs with charged nodal surfaces: (i) The space
group (SG) must allow for the coexistence of WPs and nodal surfaces in a same
system; (ii) To achieve a nonzero topological charge for nodal surfaces, the
system should be noncentrosymmetric add51 ; add52 ; add53 ; add54 , as
inversion ($\mathcal{P}$) together with time-reversal ($\mathcal{T}$) symmetry
leads to the zero Chern number; (iii) To ensure SP-WPs at the high-symmetry
points (HSPs) sharing the same $\mathcal{C}$, the pair of WPs should be
related to each other by a proper rotation or $\mathcal{T}$. In other words,
for the little group $S$ of a HSP as a subgroup of the SG $G$, the
representative of coset decomposition of $G$ over $S$ should consist only of
proper rotations and/or $\mathcal{T}$, not merely the identity. Taking into
account the (i)-(iii) conditions, we screened the encyclopedia of emergent
particles in spinless 3D crystals add18 , following the strategy shown in Fig.
1.

Figure 1: Flowchart of screening for SP-WPs with the same $\mathcal{C}$ in
spinless systems from the encyclopedia of emergent particles in Ref. add18

We found that 138 candidate SGs lacked inversion symmetry. Among these, 21
SGs, 5 SGs, and 6 SGs were identified as candidate SGs to host one-, two-, and
three-nodal surface states add55 ; add56 ; add57 ; add58 ; add59 ; add60 ,
respectively. Based on the work of Wang et al. add15 , if the SP-WPs (in
spinless systems) have no partner in the 3D BZ, meaning that all coexisting
band degeneracies in the 3D BZ are WPs, the charges for each Weyl point in the
SP-WPs must be even ($|\mathcal{C}|$ = 2 or 4) and opposite. Additionally,
according to the work of Wang et al. and Liu et al. add61 ; add62 , the C-3 WP
(in spinless systems) can only appear on the high-symmetry paths, not at the
HSPs. Therefore, in this Letter, we focus on the case of C-1 WPs at the HSPs,
which host the same charge $\mathcal{C}$ = 1 or -1.

Figure 2: (a) Crystal structure for Zr3O with SG $P6_{3}22$ (No. 182). (b) 3D
BZ and the positions of one-nodal surface (NS) and two WPs with the same
charge. (c) phonon dispersion for Zr3O. The phonon branches No. 17 and No. 18
form a doubly degenerate point (with a red dot) at the K and a doubly
degenerate line along the A-L-H-A paths (with green background). (d) 3D plot
of the phonon bands around the SP-WPs at the K and K’. (e) 3D plots of the
phonon bands at the $k_{z}$ = 0.9 $\pi$, $k_{z}$ = $\pi$, and $k_{z}$ = 1.1
$\pi$ planes. A nodal surface (NS) can be found at the $k_{z}$ = $\pi$ plane.
(f) Distribution of Berry curvature in the $k_{x}$ = 0 plane. The dashed line
indicates the first BZ, and the green line shows the NS.  Figure 3: (a) 3D
bulk and 2D surface BZs. (b) phonon LDOS projected on the (100) surface for
Zr3O along the $\bar{a}-\bar{b}-\bar{c}-\bar{d}-\bar{e}-\bar{f}-\bar{a}$
surface paths. (c)-(e) isofrequency surface contours of the (100) surface at
the frequencies of 6.45 THz, 6.50 THz, and 6.55 THz, respectively.

From Fig. 1, one can see that the two C-1 WPs do not exist at the HSPs, along
with the two- and three-nodal surfaces in the spinless systems. Only six
candidate SGs, with Nos. 169, 170, 173, 178, 179, and 182 can cohost charged
one-nodal surface and two C-1 WPs (with the same charge) at the HSPs in
spinless systems. The results are presented in Table 1, which lists the
candidate SGs, the possible locations of the two WPs, and the corresponding
symmetry representation. Note that the SP-WPs with the same charge are located
at the HSPs K and K’, and the topological charge $|\mathcal{C}|$ for the two
WPs is noneven and equal to 1. Table I provides a recipe for the SP-WPs
carrying the same chiral charges in spinless systems. In this main text, we
shall take phonons in two real materials as examples. More details about the
computational methods and the other material candidates can be found in the
supplementary material (SM) add63 .

Figure 4: (a) Crystal structure for NaPH2NO3 with SG P63 (No. 173). (b) 3D
bulk and 2D surface BZs. (c) phonon dispersion for Zr3O. The phonon branches
No. 43 and No. 44 form a doubly degenerate point (with a red dot) at the K and
a doubly degenerate line along the A-L-H-A paths (with green background). (d)
3D plot of the phonon bands around the SP-WPs at the K and K’. (e) 3D plots of
the phonon bands at the $k_{z}$ = 0.9 $\pi$, $k_{z}$ = $\pi$, and $k_{z}$ =
1.1 $\pi$ planes. A nodal surface (NS) can be found at the $k_{z}=\pi$ plane.
(f) Distribution of Berry curvature in the $k_{x}=0$ plane. The dashed line
indicates the first BZ. (g) Phonon LDOS projected on the (100) surface for
NaPH2NO3 along the $\bar{a}$-$\bar{b}$ surface path. (h) isofrequency surface
contour of the (100) surface at the frequency of 44.108 THz.

Example 1: Zr3O with SG 182. We show the first material example, Zr3O with SG
$P6_{3}22$ (No. 182). The crystal structure for Zr3O is shown in Fig. 2(a), in
which the Zr and O occupy the 6g, and 2c Wyckoff positions, respectively. The
determined lattice constants from the first-principle calculations are a = b =
5.66 Å, c = 5.23 Å, which is in good agreement with the experimental ones
add64  (a = b = 5.61 Å, c = 5.18 Å). The phonon dispersion for Zr3O along the
$\Gamma$-M-K-$\Gamma$-A-L-H-A-L-M high-symmetry paths is shown in Fig. 2(c). A
supercell of 2$\times$2$\times$2 is adopted for the calculation of force
constants. According to Fig. 2(c), there is no imaginary frequency in the
phonon spectrum, showing that Zr3O is dynamically stable. We then focus on the
frequency region of phonon branches No. 17 and No. 18 in Fig. 2(c); one finds
these two phonon branches are doubly degenerate at the HSP K and along the
A-L-H-A paths. Actually, the degenerate point at the K is a WP, and one more
WP can also be found at the HSP K’ (see Fig. 2(d)). The degenerate lines along
the A-L-H-A (with green background) belong to a one-nodal surface at the
$k_{z}=\pm\pi$ planes.

To better view the one-nodal surface, we show the 3D plot of the phonon bands
for the $k_{z}$ = 0.9 $\pi$, $k_{z}$ = $\pi$, and $k_{z}$ = 1.1 $\pi$ planes
in Fig. 2(e). Obviously, the two phonon bands overlap entirely with each other
and form a doubly degenerate band at the $k_{z}=\pi$ plane, reflecting the
one-nodal surface behavior. The nodal surface add59  is dictated by the
combination of the time-reversal ($\mathcal{T}$) and twofold screw axis
($S_{2z}$) symmetries. At the $k_{z}=\pi$ plane, one notes
$(S_{2z}\mathcal{T})^{2}=-1$ which leads to the Kramers degeneracy over the
whole plane. Away from this plane, the degeneracy is generally lifted due to
the violation of $S_{2z}\mathcal{T}$, so that a nodal surface is formed at the
$k_{z}=\pi$ plane. Note that the two WPs with the same charge and the one-
nodal surface are topologically nontrivial. The two WPs (at the HSPs K and K’)
and the one-nodal surface (at the $k_{z}=\pm\pi$ planes) carry a nonzero
topological charge, with $\mathcal{C}=+1$ for the WPs and $\mathcal{C}=-2$ for
the one-nodal surface. This can be visualized in the plot of the Berry
curvature field in Fig. 2(f). One can see that the field is emitted from the
two WPs with $\mathcal{C}=+1$ and absorbed by the one-nodal surface with
$\mathcal{C}=-2$. Moreover, Zr3O hosts a neutral chiral charge; the two WPs
and their partner, a one-nodal surface, are constrained by the no-go theorem
add49 ; add50 . Note that the two WPs in the phonon dispersion of Zr3O have
the same and uneven charge, and the results of the first-principle
calculations are in consistent with the results of the general analysis
collected in Table 1.

Figure 3(b) shows the phonon local density of states (LDOS) projected on the
(100) surface for Zr3O. Surface states in the phonon spectrum are clearly
visible in the 6.45-6.6 THz frequency ranges. Figs. 3(c)-(e) show isofrequency
surface contours of the (100) surface at the frequencies of 6.45 THz, 6.50
THz, and 6.55 THz, respectively. These figures reveal two surface arcs
connecting the projected nodal surface, each connecting to one of the
projected SP-WPs (marked by red dots). These clean arcs are not masked by the
bulk states and should be easily detected experimentally add65 .

Example 2: NaPH2NO3 with SG 173. The second material example is NaPH2NO3 with
SG P63 (No. 173). Figure 4(a) depicts the relaxed crystal structure of
NaPH2NO3; the Na, P, H, N, and O atoms occupy the 2a, 2b, 6c, 2b, and 6c
Wyckoff positions, respectively. The lattice constants for NaPH2NO3 obtained
in theory are a = b = 5.80 Å, c = 6.16 Å, agreeing well with the experimental
ones add66  (a = b = 5.77 Å, c = 6.03 Å). The phonon dispersion for NaPH2NO3
along the $\Gamma$-M-K-$\Gamma$-A-L-H-A-L-M paths is shown in Fig. 4(c). From
Fig. 4(c), one finds that the one-nodal surface appears at the $k_{z}=\pi$
plane (see Fig. 4(e)), and two WPs appear at the HSPs K and K’ (see Fig.
4(d)). The SP-WPs at the K and K’ and the one-nodal surface carry a
$\mathcal{C}=-1$ and $+2$, respectively. The corresponding Berry curvature
field distribution is shown in Fig. 4(f). Obviously, the Berry curvature near
the one-nodal surface and the SP-WPs indicates convergent and divergent field
morphology, respectively, corresponding to the chirality of one-nodal surface
and the SP-WPs, respectively. Fig. 4(g) shows the phonon LDOS projected on the
(100) surface for NaPH2NO3. Furthermore, Fig. 4(h) shows the isofrequency
surface contour of the (100) surface at the frequency of 44.108 THz,
respectively. As with Zr3O, two surface arcs connect the projected nodal
surface and the projected SP-WPs.

Summary. The SP-WPs previously proposed by Wang et al. add15  in spinless
systems do not have a partner in the 3D BZ. In their work, the two WPs of the
SP-WPs add16  have opposite and even charges. In this Letter, we extend the
previously proposed SP-WPs to a new case in the spinless systems, where they
have a partner, i.e., a charged one-nodal surface, in the 3D BZ. In this case,
the two WPs of the SP-WPs have the same and uneven charge, $i.e.$,
$|\mathcal{C}|$ = 1. We proposed a recipe for the new case of SP-WPs based on
the encyclopedia of emergent particles and reported that they could exist in 6
(out of 230) SGs, $i.e.$, 169, 170, 173, 178, 179, and 182. Based on the
recipe, we also contribute to the materials’ realization. The SP-WPs with
$|\mathcal{C}|$ = 1 can be observed in the phonon spectra of two concrete
materials: Zr3O and NaPH2NO3. Our findings apply to many spinless systems,
including phononic, other bosonic, and even electronic systems without spin-
orbit coupling.

## References

  * (1) B. Yan and C. Felser, Annu. Rev. Condens. Matter Phys. 8, 337-354 (2017).
  * (2) N. P. Armitage, E. J. Mele, and A. Vishwanath, Rev. Mod. Phys. 90, 015001 (2018).
  * (3) I. Belopolski, K. Manna, D. S. Sanchez, G. Chang, B. Ernst, J. Yin, S. S. Zhang, T. Cochran, N. Shumiya, and H. Zheng et al., Science 365, 1278 (2019).
  * (4) X. Wan, A. M. Turner, A. Vishwanath, and S. Y. Savrasov, Phys. Rev. B 83, 205101 (2011).
  * (5) L. M. Schoop, F. Pielnhofer, and B. V. Lotsch, Chem. Mater. 30, 3155 (2018).
  * (6) D. F. Liu, A. J. Liang, E. K. Liu, Q. N. Xu, Y. W. Li, C. Chen, D. Pei, W. J. Shi, S. K. Mo, P. Dudin, T. Kim, C. Cacho, G. Li, Y. Sun, L. X. Yang, Z. K. Liu, S. S. P. Parkin, C. Felser, and Y. L. Chen, Science 365, 1282 (2019).
  * (7) S. Nie, T. Hashimoto, and F. B. Prinz, Phys. Rev. Lett. 128, 176401 (2022).
  * (8) L. Lu, L. Fu, J. D. Joannopoulos, and M. Solja$\rm{\breve{c}}$i$\rm{\acute{c}}$, Nat. Photonics 7, 294 (2013).
  * (9) O. Vafek and A. Vishwanath, Annu. Rev. Condens. Matter Phys. 5, 83 (2014).
  * (10) J. Li, Y. Li, S. Du, Z. Wang, B.-L. Gu, S.-C. Zhang, K. He, W. Duan, and Y. Xu, Sci. Adv. 5, eaaw5685 (2019).
  * (11) D. Zhang, M. Shi, T. Zhu, D. Xing, H. Zhang, and J. Wang, Phys. Rev. Lett. 122, 206401 (2019).
  * (12) L. L. Wang, N. H. Jo, B. Kuthanazhi, Y. Wu, R. J. McQueeney, A. Kaminski, and P. C. Canfield, Phys. Rev. B 99, 245147 (2019).
  * (13) J. R. Soh, F. de Juan, M. G. Vergniory, N. B. M. Schr$\rm{\ddot{o}}$ter, M. C. Rahn, D. Y. Yan, J. Jiang, M. Bristow, P. Reiss, J. N. Blandy, Y. F. Guo, Y. G. Shi, T. K. Kim, A. McCollam, S. H. Simon, Y. Chen, A. I. Coldea, and A. T. Boothroyd, Phys. Rev. B 100, 201102(R) (2019).
  * (14) J.-Z. Ma, S. M. Nie, C. J. Yi, J. Jandke, T. Shang, M. Y. Yao, M. Naamneh, L. Q. Yan, Y. Sun, A. Chikina, V. N. Strocov, M. Medarde, M. Song, Y.-M. Xiong, G. Xu, W. Wulfhekel, J. Mesot, M. Reticcioli, C. Franchini, and C. Mudry et al., Sci. Adv. 5, eaaw4718 (2019).
  * (15) X. Wang, F. Zhou, Z. Zhang, W. Wu, Z.-M. Yu, and S. A. Yang, Phys. Rev. B 106, 195129 (2022).
  * (16) X.-P. Li, D. Zhou, Y. Wu, Z.-M. Yu, F. Li, and Y. Yao, Phys. Rev. B 106, L220302 (2022).
  * (17) Z. Q. Wang, Q. B. Liu, X. F. Yang, and H. H. Fu, Phys. Rev. B 106, L161302 (2022).
  * (18) Z.-M. Yu, Z. Zhang, G.-B. Liu, W. Wu, X.-P. Li, R.-W. Zhang, S. A. Yang, and Y. Yao, Sci. Bull. 67, 375 (2022).
  * (19) T. T. Zhang, R. Takahashi, C. Fang, and S. Murakami, Phys. Rev. B 102, 125148 (2020).
  * (20) Q.-B. Liu, Y. Qian, H.-H. Fu, and Z. Wang, Npj Comput. Mater. 6, 95 (2020).
  * (21) Q.-B. Liu, Z. Wang, and H.-H. Fu, Phys. Rev. B 103, L161303 (2021).
  * (22) C. Cui, X. P. Li, D. S. Ma, Z. M. Yu, and Y. Yao, Phys. Rev. B 104, 075115 (2021).
  * (23) G. Xie, D. Ding, and G. Zhang, Adv. Phys.: X 3, 1480417 (2018).
  * (24) N. Li, J. Ren, L. Wang G. Zhang, P. H$\rm{\ddot{a}}$nggi, and B. Li, Rev. Mod. Phys. 84, 1045 (2012).
  * (25) J. Chen, J. He, D. Pan, X. Wang, N. Yang, J. Zhu, S. A. Yang, and G. Zhang, Sci. China Phys. Mech. Astron. 65, 117002 (2022).
  * (26) X. Wang, T. Yang, Z. Cheng, C. Surucu, J. Wang, F. Zhou, Z. Y. Zhang, and G. Zhang, Appl. Phys. Rev. 9, 041304 (2022).
  * (27) Y. Liu, X. Chen, and Y. Xu, Adv. Funct. Mater. 30, 1904784 (2020).
  * (28) S. Singh, Q. S. Wu, C. Yue, A. H. Romero, and A. A. Soluyanov, Phys. Rev. Materials 2, 114204 (2018).
  * (29) J. Li, J. Liu, S. A. Baronett, M. Liu, L. Wang, R. Li, Y. Chen, D. Li, Q. Zhu, and X. Chen, Nat. Commun. 12, 1204 (2020).
  * (30) B. Peng, S. Murakami, B. Monserrat and T. T. Zhang, Npj Comput. Mater. 7, 195 (2021).
  * (31) Z. Huang, Z. Chen, B. Zheng, and H. Xu, Npj Comput. Mater. 6, 87 (2020).
  * (32) J. J. Zhu, W. K. Wu, J. Z. Zhao, H. Chen, L. F. Zhang, and S. S. A. Yang, Npj Quantum Mater. 7, 52 (2022).
  * (33) X.-Q. Chen, J. Liu, and J. Li, Innovation 2, 100134 (2021).
  * (34) Y. Liu, N. Zou, S. Zhao, X. Chen, Y. Xu, and W. Duan, Nano Lett. 22, 2120 (2022).
  * (35) H. Miao, T. T. Zhang, L. Wang, D. Meyers, A. H. Said, Y. L. Wang, Y. G. Shi, H. M. Weng, Z. Fang, and M. P. M. Dean, Phys. Rev. Lett. 121, 035302 (2018).
  * (36) B. W. Xia, R. Wang, Z. J. Chen, Y. J. Zhao, and H. Xu, Phys. Rev. Lett. 123, 065501 (2019).
  * (37) T. Zhang, Z. Song, A. Alexandradinata, H. Weng, C. Fang, L. Lu, and Z. Fang, Phys. Rev. Lett. 120, 016401 (2018).
  * (38) C. Xie, Y. Liu, Z. Zhang, F. Zhou, T. Yang, M. Kuang, X. Wang, and G. Zhang, Phys. Rev. B 104, 045148 (2021).
  * (39) W. W. Yu, Y. Liu, X. M. Zhang, and G. D. Liu, Phys. Rev. B 106, 195142 (2022).
  * (40) Y. Feng, C. Xie, H. Chen, Y. Liu, and X. Wang, Phys. Rev. B 106, 134307 (2022).
  * (41) W.-W. Yu, Y. Liu, W. Meng, H. Liu, J. Gao, X. Zhang, and G. Liu, Phys. Rev. B 105, 035429 (2022).
  * (42) G. Liu, Y. Jin, Z. Chen, and H. Xu, Phys. Rev. B 104, 024304 (2021).
  * (43) Z. J. Chen, R. Wang, B. W. Xia, B. B. Zheng, Y. J. Jin, Y. J. Zhao, and H. Xu, Phys. Rev. Lett. 126, 185301 (2021).
  * (44) B. Zheng, B. Xia, R. Wang, Z. Chen, J. Zhao, Y. Zhao, and H. Xu, Phys. Rev. B 101, 100303(R) (2020).
  * (45) B. Peng, Y. Hu, S. Murakami, T. Zhang, and B. Monserrat, Sci. Adv. 6, eabd1618 (2020).
  * (46) J.-Y. You, X.-L. Sheng, and G. Su, Phys. Rev. B 103, 165143 (2021).
  * (47) J. Wang, H. Yuan, M. Kuang, T. Yang, Z.-M. Yu, Z. Zhang, and X. Wang, Phys. Rev. B 104, L041107 (2021).
  * (48) P. C. Sreeparvathy, C. Mondal, C. K. Barman, and A. Alam, Phys. Rev. B 106, 085102 (2022).
  * (49) H. B. Nielsen and M. Ninomiya, Nucl. Phys. B 185, 20 (1981).
  * (50) H. B. Nielsen and M. Ninomiya, Nucl. Phys. B 193, 173 (1981).
  * (51) Y. Yang, J.-p. Xia, H.-x. Sun, Y. Ge, D. Jia, S.-q. Yuan, S. A. Yang, Y. Chong, and B. Zhang, Nat. Commun. 10, 5185 (2019).
  * (52) G. Q. Chang, B. J. Wieder, F. Schindler, D. S. Sanchez, I. Belopolski, S. M. Huang, B. Singh, D. Wu, T. R. Chang, T. Neupert, S.-Y. Xu, H. Lin, and M. Z. Hassan, Nat. Mater. 17, 978 (2018).
  * (53) M. Kim, D. Lee, D. Lee, and J. Rho, Phys. Rev. B 99, 235423 (2019).
  * (54) M. Xiao, L. Ye, C. Qiu, H. He, Z. Liu, and S. Fan, Sci. Adv. 6, eaav2360 (2020).
  * (55) C. Bradley and A. Cracknell, The Mathematical Theory of Symmetry in Solids: Representation Theory for Point Groups and Space Groups (Oxford University Press, 2010).
  * (56) C. Xie, H. Yuan, Y. Liu, and X. Wang, Phys. Rev. B 105, 054307 (2022).
  * (57) C. Xie, H. Yuan, Y. Liu, X. Wang, and G. Zhang, Phys. Rev. B 104, 134303 (2021).
  * (58) J. Wang, H. Yuan, Z.-M. Yu, Z. Zhang, and X. Wang, Phys. Rev. Mater. 5, 124203 (2021)
  * (59) W. Wu, Y. Liu, S. Li, C. Zhong, Z.-M. Yu, X.-L. Sheng, Y. X. Zhao, and S. A. Yang, Phys. Rev. B 97, 115125 (2018).
  * (60) X. M. Zhang, Z.-M. Yu, Z. M. Zhu, W. K. Wu, S.-S. Wang, X.-L. Sheng, and S. A. Yang, Phys. Rev. B 97, 235150 (2018).
  * (61) X. T. Wang, F. Zhou, Z. Y. Zhang, Z. M. Yu, and Y. G. Yao, Phys. Rev. B 106, 214309 (2022).
  * (62) G. Liu, Z. Chen, P. Wu, and H. Xu, Phys. Rev. B 106, 214308 (2022).
  * (63) See the supplementary material (SM) for the computational details, and the other material candidates with single-pair-Weyl-points phonons carrying the same chiral charges, which includes Refs. add67 ; add68 ; add69 ; add70 ; add71 ; add72 ; add73 ; add74 ; add75 ; add76
  * (64) A. B. Riabov, V. A. Yartys, B. C. Hauback, P. W. Guegan, G. Wiesinger, and I. R. Harris, J. Alloys Compd., 93, 293-295 (1999).
  * (65) T. T. Zhang, H. Miao, Q. Wang, J. Q. Lin, Y. Cao, G. Fabbris, A. H. Said, X. Liu, H. C. Lei, Z. Fang, H. M. Weng, and M. P. M. Dean, Phys. Rev. Lett. 123, 245302 (2019).
  * (66) E. Hobbs, D. E. C. Corbridge and B. Raistrick, Acta Crystallographica, 123, 621-626 (1953).
  * (67) G. Kresse and J. Hafner, Phys. Rev. B 49, 14251 (1994).
  * (68) G. Kresse and J. Furthm$\rm{\ddot{u}}$ller, Phys. Rev. B 54, 11169 (1996).
  * (69) P. E. Bl$\rm{\ddot{o}}$chl, Phys. Rev. B 50, 17953 (1994).
  * (70) J. P. Perdew, K. Burke, and M. Ernzerhof, Phys. Rev. Lett. 77, 3865 (1996).
  * (71) X. Gonze and C. Lee, Phys. Rev. B 55, 10355 (1997).
  * (72) A. Togo and I. Tanaka, First principles phonon calculations in materials science, Scr. Mater. 108, 1 (2015).
  * (73) Q.-S. Wu, S.-N. Zhang, H.-F. Song, M. Troyer, and A. A. Soluyanov, Comput. Phys. Commun. 224, 405 (2018).
  * (74) M. L. Sancho, J. L. Sancho, and J. Rubio, J. Phys. F 14, 1205 (1984).
  * (75) M. P. L. Sancho, J. M. L. Sancho, and J. Rubio, J. Phys. F 15, 851 (1985).
  * (76) A. A. Soluyanov and D. Vanderbilt, Phys. Rev. B 83, 235401 (2011).


The emerging Internet of Things (IoT) applications that leverage ubiquitous connectivity and big data are facilitating the realization of smart everything initiatives. IoT-enabled infrastructures have naturally a multi-layer system architecture with an overlaid or underlaid device network and its coexisting infrastructure network. The connectivity between different components in these two heterogeneous interdependent networks plays an important role in delivering real-time information and ensuring a high-level situational awareness. However, IoT-enabled infrastructures face cyber threats due to the wireless nature of communications. Therefore, maintaining network connectivity in the presence of adversaries is a critical task for infrastructure network operators. In this paper, we establish a three-player three-stage dynamic game-theoretic framework including two network operators and one attacker to capture the secure design of multi-layer interdependent infrastructure networks by allocating limited resources. We use subgame perfect Nash equilibrium (SPE) to characterize the strategies of players with sequential moves. In addition, we assess the efficiency of the equilibrium network by comparing with its team optimal solution counterparts in which two network operators can coordinate. We further design a scalable algorithm to guide the construction of the equilibrium IoT-enabled infrastructure networks. Finally, we use case studies on the emerging paradigm of the Internet of Battlefield Things (IoBT) to corroborate the obtained results.

Heterogeneous Networks, Internet of Things, Interdependency,  Cybersecurity, Dynamic Game

§ INTRODUCTION

The massive deployment of Internet of Things (IoT) technologies provides ubiquitous connectivity for heterogeneous machines and devices for data collection, information exchange and operational decision-making. Therefore, IoT is widely adopted in various application domains especially in the infrastructures including smart grids, smart homes, intelligent transportations, and smart cities <cit.>.
With the current information and communication technologies (ICTs), an IoT-enabled infrastructure network has its own networking platform that is interoperable within the existing Internet infrastructure. Hence, an IoT-enabled infrastructure can be naturally viewed as a two-layer interdependent network consisting of the infrastructure layer network and the overlaid or underlaid device layer network. For instance, in the Internet of Battlefield Things (IoBT), the soldier networks equipped with wearable devices are integrated with the unmanned aerial vehicle (UAV) ad hoc networks to perform tasks. The connections in the two-layer network architecture can be classified into two types: (i) the interlinks by which devices/infrastructures communicate between themselves as well as (ii) the intralinks by which devices communicate with the infrastructure.

The connectivity of an IoT-enabled infrastructure network plays an important role in information dissemination and real-time decision-making for mission-critical operations. Note that devices can communicate with each other or with infrastructures to maintain a global situational awareness of the network. Furthermore, the IoT devices which are scarce of on-board computational resources can outsource heavy computations to the data centers through cloud computing infrastructure <cit.>. IoT-enabled infrastructures are often vulnerable to cyberattacks which can degrade the system performance, since most of the communications within the IoT networks are wireless in nature. For example, in IoBT networks, the communications between a soldier and a UAV relay node can be jammed by an attacker, and a soldier thus becomes isolated and loses information and awareness of the battlefield.

Therefore, to protect the IoT-enabled infrastructure from adversarial behaviors, it is imperative to design secure and robust two-layer networks that can maintain connectivity despite of link failures.
Due to the heterogeneous and two-layer feature of the network, the design of the network is decentralized essentially. Specifically, the  network design involves two players who design their own subnetworks sequentially. As in IoBT networks, UAVs form their own relay networks, while a team of soldiers forms a network based on the knowledge of UAV locations to maintain the communications among soldiers and command and control stations. The objectives of these two network operators are to maintain the connectivity of the global network by considering network creation cost, while an attacker aims to disconnect the network at the minimum attacking cost.

In this paper, we use a three-player three-stage game to capture the secure interdependent IoT-enabled infrastructure network design. At the first stage, the network operator 1 creates links by anticipating the behavior of the network operator 2 and the adversary. At the second stage, the network operator 2 observes the links created by operator 1 and forms links to secure the network by anticipating the adversarial behaviors. Finally, the adversary observes the whole network created by the two operators and launches an attack targeting to disconnect the network. The two operators have aligned objectives to make the two-layer network connected. However, they have different costs or capabilities in forming communication links. For example, creating links between UAVs can be more expensive than links between soldiers as the distance between UAVs can be much longer. In addition, the differences in network creativity and the ordering of the two network players can affect the outcome of the designed network. For clarity, we present an example in Fig. <ref> to illustrate the dynamic game model considered in this work.

Illustration of the three-player three stage game.  Operator 1 can construct links within layer 1 and between two layers, while operator 2 can establish links within layer 2 and between two layers. Case 1: Operator 1 anticipates that operator 2 has the capability to establish at least 6 links and the attacker is able to disrupt 1 link. Thus, operator 1 does not create link at the first stage, and operator 2 creates 6 links at the second stage, where the global network is resistant to any 1 link removal attack. At stage 3, the adversary does not attack as 1 link removal cannot disconnect the network. Case 2: Operator 2 is able to construct at most 5 links. Thus, operator 1 needs to construct 1 link at the first stage by anticipating 1 link removal, and operator 2 creates 4 links at the second stage. The attacker does not compromise any link and the network is connected at stage 3.

We adopt subgame perfect Nash equilibrium (SPE) <cit.> as the solution concept to the three-player sequential IoT-enabled infrastructure network design game. We first observe that the SPE of the  game results in a $k$-connected graph  if the network remains connected at equilibrium. To understand the efficiency of the Nash equilibrium network, we use a centralized network design problem as a benchmark in which both operators coordinate and design an optimal secure network as a team.
We further observe that the price of anarchy (PoA) can be unbounded in general cases. However, when two subnetworks contain the same number of nodes and the unitary costs of creating links are the same with only a non-null strategy of operator 2 at SPE, then the PoA is 1, which means that the decentralized network design is as efficient as that of centralized one.
Some counter-intuitive results are further presented in Section <ref>, e.g., the payoff of operator 1 is unique at SPE while operator 2's may vary.
Finally, we use case studies on IoBT to illustrate the design principles of secure infrastructure networks. We observe that with a higher threat level, the two network operators prefer more collaborations to secure the IoBT network.

The contributions of this paper are summarized as follows:

* We propose a three-player three-stage dynamic game  to investigate the secure design of interdependent IoT-enabled infrastructure networks. By considering costs for creating and compromising links, the network operators aim to maintain the network connected while the attacker's goal is to disconnect the network.

* We adopt subgame perfect Nash equilibrium (SPE) as the solution concept for the established game, and analyze the SPE systematically including the optimal strategies of two network operators and the attacker through backward induction.

* We quantify the efficiency of the SPE by comparing it with the team optimal solution in which two network operators can coordinate. Furthermore, we derive a number of meaningful results including the non-unicity of equilibrium cost of network operators and the price of seniority quantifying the benefits of playing first in the dynamic game.

* We design a scalable algorithm for constructing the secure interdependent IoT-enabled infrastructure network. In addition, we use case studies of IoBT to illustrate the derived design principles.

§.§ Organization of the Paper

The rest of the paper is organized as follows. Section <ref> presents related works. Section <ref> introduces the  IoT-enabled infrastructures framework and formulates the dynamic game problem. Equilibrium analysis of the game and structural results are presented in Section <ref>. Section <ref> designs an algorithm to guide the secure solution network construction. Case studies on IoBT networks are provided in Section <ref>, and Section <ref> concludes this paper.

§ RELATED WORK

With the increasing amount of cyber threats, security becomes a critical concern for IoT-enabled infrastructure networks <cit.>. The infrastructure networks face various types of attacks in terms of the potential of cyber attackers <cit.>. For example, attackers can target the edge computing nodes in IoT including sensor nodes. Some typical adversarial scenarios include node replication attack <cit.> and DoS attack <cit.>. The attackers can also launch attacks through the IoT communication networks.  In the eavesdropping attack, the attacker captures the private information over the channel, and utilizes the information to design other tailored attacks <cit.>. In the data injection attack, the attacker injects fraudulent packets into IoT communication links through insertion, manipulation, and replay techniques <cit.>.  In our work, we focus on the adversarial attacks which lead to communication link removal in the IoT-enabled infrastructure networks.

Different methodologies have been proposed in previous works to address the cyber threats in the IoT and critical infrastructures <cit.>. In  <cit.>,
contract and insurance mechanisms have been adopted to mitigate the cyber risks with a consideration of dependencies between different entities. In
<cit.>, the authors have provided a comprehensive review on the machine learning-based security schemes in the IoT systems. Another widely adopted approach for investigating infrastructure network security is through dynamic games. For example, the authors in <cit.> have proposed stochastic game nets for stochastic games representation with Petri nets to study the security analysis for enterprise networks. <cit.> has proposed a dynamic game model including pre-attack defense and post-attack recovery phases in designing resilient IoT-enabled infrastructure networks.  In <cit.>, the authors have adopted a two-player stochastic game to investigate the network security in which the nodes' security assets and vulnerabilities are correlated. <cit.> has investigated optimal design of two-layer IoT network with heterogeneous security considerations at different layers. In our work, we develop a three-player three-stage dynamic game framework and study the operators' and attacker's strategies in defending and compromising the network sequentially.

Infrastructure network connectivity is critical in information exchange in many civilian and military applications. Regarding the technical aspect, we investigate the secure design of IoT-enabled infrastructure network by considering the connectivity <cit.> using graph theory <cit.> and dynamic games <cit.>. Different from <cit.> which has adopted a dynamic game approach in designing secure infrastructure, this work extends the single network paradigm to various network operators by considering the heterogeneity of multi-layer networks. Comparing with  previous works <cit.> that have focused on a single-layer adversarial network design, we establish a two-layer heterogeneous network framework and characterize the decentralized decision-making of each network operator explicitly. Furthermore, the current work extends our previous one <cit.> in multiple aspects.  First, we include much more analytical results with investigations on the properties of the game in Section <ref>. Specifically, more results on the efficiency of equilibrium are presented in Section <ref>, and the findings in both Sections <ref> and <ref> are completely new. Second, we provide a complete analysis of the algorithm including its complexity and scalability in Section <ref>. Third, we include detailed proofs of all theoretical results which were omitted in <cit.>.  Fourth, we extensively expand the introduction and related work sections as well as the case studies with more examples and discussions to corroborate the obtained results.

§ INTERDEPENDENT IOT-ENABLED INFRASTRUCTURE MODEL AND PROBLEM FORMULATION

We consider two infrastructure network operators and two sets of nodes ${\cal N}_1$ and ${\cal N}_2$, where nodes represent the devices and infrastructures in the IoT-enabled network. The first operator controls nodes in ${\cal N}_1$ and as such can create wireless communication links between those nodes as well as links connecting a node in ${\cal N}_1$ to one in ${\cal N}_2$. Similarly, the second operator controls nodes in ${\cal N}_2$ and can create links except those in ${\cal N}_1$. For convenience, we define the following notations:

* $E_1$ is the set of possible links between nodes of ${\cal N}_1$, that is $E_1 = \{e_1 = (n_a, n_b): n_a \in {\cal N}_1, \, n_b \in {\cal N}_1, n_a\neq n_b\}$.

* $E_2$ is the set of possible links between nodes of ${\cal N}_2$, that is $E_2 = \{e_2 = (n_a, n_b): n_a \in {\cal N}_2, \, n_b \in {\cal N}_2,  n_a\neq n_b\}$.

* $E_{1,2}$ is the set of possible links between nodes of ${\cal N}_1$ and ${\cal N}_2$, that is $E_{1,2} = \{e_{1,2} = (n_a, n_b): n_a \in {\cal N}_1, \, n_b \in {\cal N}_2\}$.

Further, the number of nodes in two networks are equal to $|\mathcal{N}_1|=n_1$ and $|\mathcal{N}_2|=n_2$, respectively, where $|\cdot|$ denotes the cardinality of a set. Note that the created links by both network operators are assumed to be undirected, i.e., two nodes can communicate bidirectionally if they are connected with a link.

The adversarial IoT-enabled infrastructure network formation consists of three stages which are as follows.

1) At round $1$, operator $1$ has the choice of creating a set of communication links in $E_1 \cup E_{1,2}$.

2) At round $2$, operator $2$ can create a set of communication links in $E_2 \cup E_{1,2}$.

3) At round $3$, an adversary can remove a set of communication links, e.g., through jamming attacks, that have been created during the previous two rounds.

Note that the order of play between two network operators are determined before the game begins. As shown in Section <ref> later, playing first or second impacts the utility of two network operators in this dynamic game.

A network is a pair $(\cal N, \cal E)$, with $\cal N$ a set of nodes and $\cal E$ a set of edges, or links between two nodes. At round $1$, starting from an empty network $({\cal N}, \emptyset)$, with ${\cal N} = {\cal {N}}_1\cup \mathcal{N}_2$, operator $1$ creates a set ${\cal E}_1:={\cal E}_1^1\cup {\cal E}_1^{1,2}$ of links and thus designs network $G_1 = ({\cal N}, {\cal E}_1)$ such that ${\cal E}_1$ is a subset of $E_1 \cup E_{1,2}$, the set of admissible links for operator $1$, i.e., ${\cal E}_1^1 \subseteq E_1$ and ${\cal E}_1^{1,2}\subseteq E_{1,2}$.
Then, at round $2$, starting from network $G_1$, operator $2$ creates a set ${\cal E}_2:={\cal E}_2^2\cup {\cal E}_2^{2,1}$ of links and thus designs network $G_2 = ({\cal N}, {\cal E}_1 \cup {\cal E}_2)$ such that ${\cal E}_2^2 \subseteq E_2$ and ${\cal E}_2^{2,1} \subseteq E_{1,2}$.

Finally, at round $3$, the adversary chooses a subset of the links ${\cal E}_A \subseteq {\cal E}_1 \cup {\cal E}_2$ that it removes from $G_2$, resulting in network $G_3 = ({\cal N}, {\cal E}_1 \cup {\cal E}_2 \backslash {\cal E}_A)$. We denote the total number of nodes as $|{\cal N}|=n_1+n_2 = n$.

One metric to measure the performance of the IoT-enabled infrastructure network is its connectivity defined as follows.

An infrastructure network $G=(\mathcal{N},\mathcal{E})$ is said to be connected if every node in $\mathcal{N}$ can be reached from any others through a sequence of links from $\mathcal{E}$.

The goal of the operators is to construct a connected IoT-enabled infrastructure network, i.e., a network where every node can be reached from any others through a sequence of links. Conversely, the role of the adversary is to obtain a disconnected infrastructure network, and thus a node or a group of nodes becomes not accessible to the rest of the network. Note that the adopted binary network connectivity metric is suitable for mission-critical IoT-enabled infrastructures, e.g., IoBT. In these types of systems, the connectivity among agents is the minimum requirement and thus of first priority of the network operator.

In IoT-enabled infrastructure network, both creating and removing links are costly. Let $c_{1}$ and $c_{2}$ be the normalized unitary costs for creating a link for operators $1$ and $2$ in $E_1$ and $E_2$, respectively, and $c_{1,2}$ and $c_{2,1}$ be their corresponding normalized unitary costs for creating a link in $E_{1,2}$. In addition, $c_{A}$ is the normalized unitary cost of the adversary to compromise a link.  Let $\mathds{1}_G$ be the indicator factor that equals $1$ if network $G$ is connected and $0$ otherwise. Then, the payoffs of operators $1$, $2$ and the adversary are, respectively,

\begin{equation}\label{utility}
\begin{split}
U_{1}({\cal E}_1, {\cal E}_2, {\cal E}_A) &= \mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2 \backslash {\cal E}_A)} - c_{1} |{\cal E}_1^1| - c_{1,2} |{\cal E}_1^{1,2} |,\\
U_{2}({\cal E}_1, {\cal E}_2, {\cal E}_A) &=\mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2 \backslash {\cal E}_A)} - c_{2} |{\cal E}_2^2| - c_{2,1} |{\cal E}_2^{2,1}|,\\
U_{A}({\cal E}_1, {\cal E}_2, {\cal E}_A) &= 1-\mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2 \backslash {\cal E}_A)} - c_{A} |{\cal E}_A|.
\end{split}
\end{equation}

In (<ref>), we normalize the cost of creating and attacking links with respect to the unitary network connectivity measure. Note that these constant cost parameters are directly related to the monetary cost of creating and attacking links. To avoid trivial solutions, the unitary costs $c_1$, $c_2$, $c_{1,2}$, $c_{2,1}$, and $c_A$ admit a value between 0 and 1. Both operators adopt the same type of communication technology (e.g., WiFi, Zigbee, LTE, NB-IoT) to construct the links. Thus, both intralinks and interlinks in the two-layer network have an identical level of security. This fact leads to a unified unitary attack cost for the adversary, regardless of the type of communication links (i.e., intralink or interlink). Extension of the framework to include heterogeneous attack costs is also possible. One direction is to consider that the operators can construct secure (with protection mechanism) and insecure links. The attacker is incapable of compromising those secure links or very costly to do so. We leave this nontrivial extension as future work.

In this work, we are interested in seeking the subgame perfect Nash equilibrium (SPE) of the three-stage dynamic game. SPE is a refinement of  Nash equilibirum (NE) by focusing on the sequential strategic decision-making of players, comparing with NE that treats all players' strategies as choices made once before the play begins. An SPE has the property that in no subgame can any player benefit by unilaterally deviating from the SPE strategy.  Another critical property is that every SPE is an NE (but not vise versa), as SPE is a more restricted solution concept. Furthermore, SPE is a strategy profile that induces an NE in every subgame. A more comprehensive discussion of SPE can be found in <cit.> and <cit.>. In this regard, SPE is an appropriate solution concept for our three-stage game. Specifically, we seek for optimal strategies of the three players as follows.

The SPE of the investigated three-player three-stage game is a strategy profile $\{{\cal E}_1^{\text{MAX}}, {\cal E}_2^{\text{MAX}},{\cal E}_A^{\text{MAX}}\}$ that satisfy the following constraints.

1) Given network $G_2$, the adversary chooses the optimal set ${\cal E}_A^{\text{MAX}}({\cal E}_1, {\cal E}_2) $ that maximizes its utility ${\cal E}_A^{\text{MAX}}({\cal E}_1, {\cal E}_2) \in \argmax_{{\cal F}} \{U_{A}({\cal E}_1, {\cal E}_2, {\cal F})\}$.

2) Given network $G_1$, operator $2$ chooses the optimal set ${\cal E}_2 ^{\text{MAX}}({\cal E}_1)$ that maximizes its utility ${\cal E}_2^{\text{MAX}}({\cal E}_1) \in \argmax_{{\cal F}} \{U_{2}({\cal E}_1, {\cal F}, {\cal E}_A^{\text{MAX}}({\cal E}_1, {\cal F}))\}$.

3) Operator $1$ chooses the optimal set ${\cal E}_1^{\text{MAX}}$ that maximizes its utility ${\cal E}_1^{\text{MAX}} \in \argmax_{{\cal F}} \{U_{1}({\cal F}, {\cal E}_2^{\text{MAX}} ({\cal F}), {\cal E}_A^{\text{MAX}}({\cal F}, {\cal E}_2^{\text{MAX}} ({\cal F})))\}$.

By convention, the adversary attacks the network when $c_{A} |{\cal E}_A|=1$ and $\mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2 \backslash {\cal E}_A)}=0$ at SPE. This consideration makes sense, especially in mission-critical scenarios, as the attacker's goal is to disrupt the network connectivity. Attacking the network with success can still be an incentive-compatible strategy for the adversary, even if it yields a zero net utility. However, this convention is not strict, i.e., the adversary may not attack the network in this boundary case. To keep the notation simple during the SPE analysis (e.g., characterization of $k$ in (<ref>)), we follow such convention. Note that the developed theoretical methods in later sections are valid under both considerations. In contrast, the operators will not secure the network if $c_{1} |{\cal E}_1^1| + c_{1,2} |{\cal E}_1^{1,2}|=1$, $c_{2} |{\cal E}_2^2| + c_{2,1} |{\cal E}_2^{2,1}|=1$, and $\mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2 \backslash {\cal E}_A)}=1$. Therefore, the SPE yields the equilibrium topology of the two-layer adversarial IoT-enabled infrastructure networks.

Remark: We next comment on the information structure of game. In this dynamic game, the adversary is the follower and his optimal actions are best responses to the network constructed by the two operators after the first two steps. Thus, the adversary does not necessarily know the exact link creation costs of two network operators but reacts to the operators' strategy profile ${\cal E}_1\cup {\cal E}_2$ optimally by maximizing $U_A$. In comparison, both operators need to know the threat level of the network captured by the unitary attack cost $c_A$. With a smaller $c_A$, the operators strategies are more conservative by anticipating more attacks. When $c_A$ is not precisely known by operators, there are two possible ways to address this challenge. The first one is that, since $c_A$ is directly related to the number of attacks, then the operators can estimate $c_A$ based on the distribution of number of attacks using historical data. The second approach is to model this unknown information directly using a parameter $\theta$, representing the uncertain type of the adversary. Then, the operators determine their optimal strategies conditioned on the random type parameter $\theta$. This yields a new dynamic Bayesian game which is nontrivial and worth of investigation in the future work.

§ SPE ANALYSIS AND ANALYTICAL RESULTS

In this section, we analyze the formulated three-player three-stage IoT-enabled infrastructure network formation game  in Section <ref> with a focus on the derivation of its SPE.

§.§ Backward Induction

To derive the SPE, we proceed by backward induction, i.e., we first compute the optimal strategy for the adversary, then operator $2$ and finally operator $1$.

A network $G=(\cal N,\cal E)$ is called a $p$-connected network, if (i) it remains connected after the deletion of any $p$ links, and (ii) there exists a set $\cal F$ of $p+1$ links ($|\mathcal F| = p+1$) so that the network $(\mathcal{N},\mathcal{E}\backslash \cal{F})$ is disconnected.

Remark: Any connected network $G=(\cal N,\cal E)$ is a $p$-connected network for some value of $1 \leq p \leq |\cal E|$. By convention, we say that a non-connected network is $(-1)$-connected. The value $p$ is called the link connectivity of the network. In addition, a network is $p$-resistant if it remains connected after the deletion of $p$ links, that is, if it is $m$-connected for some $m \geq p$.

For notational clarity, in the following, we denote

\begin{equation}\label{notation-k}
k := \floor*{1/c_A}.
\end{equation}

Note that the floor operator $\floor*{x}$ and the ceiling operator $\ceil*{x}$ denote the largest integer no greater than $x$ and the smallest integer no less than $x$, respectively. As shown in the analysis of following Lemma <ref>, $k$ can be interpreted as the maximum number of links that the adversary may attack at the SPE. The following result presents the strategy of the adversary.

Let ${\cal E}_1$ and ${\cal E}_2$ be played by operator $1$ and $2$ respectively.
Then, the adversary's optimal strategy ${\cal E}_A^{\text{MAX}}$ is:

1) $\emptyset$ if $({\cal N}, {\cal E}_1 \cup {\cal E}_2)$ is not connected,

2) $\emptyset$ if $({\cal N}, {\cal E}_1 \cup {\cal E}_2)$ is $m$-connected with $m \geq k$,

3) any ${\cal F}$ such that $\mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2\backslash \cal F)}=0$ and $\displaystyle |{\cal F}| = m+1$ if $({\cal N}, {\cal E}_1 \cup {\cal E}_2)$ is $m$-connected with $m<k$.

Note that since $1-\mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2)} \in \{0,1\}$ then the utility of the adversary is upper bounded by $1$.
Further, if $\mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2)} = 0$, i.e., if $({\cal N}, {\cal E}_1 \cup {\cal E}_2)$ is not connected, then $U_{A}({\cal E}_1, {\cal E}_2, {\cal E}_A) = 1$ if and only if (iff) $|{\cal E}_A| = 0$, which is thus the (only) optimal strategy.

Assume now that $\mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2)} = 1$. Note that $U_{A}({\cal E}_1, {\cal E}_2, \emptyset) = 1-\mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2)}=0$. Thus, the optimal strategy of the adversary is not the empty set iff there exists an ${\cal F} \neq \emptyset$ such that $ \mathds{1}_{({\cal N}, {\cal E}_1 \cup {\cal E}_2 \backslash {\cal F})} = 0$ and $U_{A}({\cal E}_1, {\cal E}_2, {\cal F}) >0$.

Let $m$ be the connectivity of network $ ({\cal N}, {\cal E}_1 \cup {\cal E}_2)$. Let ${\cal F}$ be a non-empty set such that $({\cal N}, {\cal E}_1 \cup {\cal E}_2\backslash \cal F)$ is connected. Then, $U_{A}({\cal E}_1, {\cal E}_2, {\cal F}) = - c_A|{\cal F}| <0$.
Thus this strategy is strictly dominated by the null strategy and therefore is not optimal. Reciprocally, let ${\cal F}$ be such that $({\cal N}, {\cal E}_1 \cup {\cal E}_2\backslash \cal F)$ is disconnected. Then $U_{A}({\cal E}_1, {\cal E}_2, {\cal F}) = 1- c_A|{\cal F}| \leq 1-(m+1) c_A$.

Thus, the null strategy is optimal iff $k \leq 1/c_A < m+1$, and a non-null strategy is optimal iff $m+1 \leq 1/c_A < k+1$, i.e., if $m<k$.

In a similar vein, we can detail the optimal strategy of operator $2$ as follows.

Let ${\cal E}_1$ be played by operator $1$.
Then, the operator 2's optimal strategy ${\cal E}_2^{\text{MAX}}$ in the IoT-enabled infrastructure is:

1) $\emptyset$ if $({\cal N}, {\cal E}_1)$ is $k$-connected;

2) Otherwise, let $F$ be the set of sets of $E_2 \cup E_{1,2}$ such that for each element ${\cal F}$ of $F$, network $({\cal N}, {\cal E}_1 \cup {\cal F})$ is $k$-connected. If $F$ is not empty, we consider its element ${\cal F}$ that has the minimal cost, that is the set of links $\displaystyle {\cal F} = {\cal F}_2\cup {\cal F}_{2,1}$, where $\{ {\cal F}_2, {\cal F}_{2,1}\}= \argmin_{{\cal A}_2, {\cal A}_{2,1}} \{ c_2 |{\cal A}_2| + c_{2,1} |{\cal A}_{2,1}|,\ \text{s.t. } {\cal A}_2 \subseteq E_2, \, {\cal A}_{2,1} \subseteq E_{1,2} \}$.

* If $F = \emptyset$ or $c_2 |{\cal F}_2| + c_{2,1} |{\cal F}_{2,1}| \geq 1$, then the optimal strategy of operator 2 is the null strategy and the resulting payoff is $0$.

* Otherwise (i.e. $F$ is not empty and $c_2 |{\cal F}_2| + c_{2,1} |{\cal F}_{2,1}| < 1$), then the optimal payoff of operator $2$ is $1-c_2 |{\cal F}_2| - c_{2,1} |{\cal F}_{2,1}|$, and an optimal strategy is ${\cal F}$.

This result leads us finally to the optimal strategy for operator $1$ in the IoT-enabled infrastructure networks.

Let ${\cal G}$ be the set of $k$-connected networks. (Note that ${\cal G}$ is not empty iff $k+1 \leq n-1$.) Any network of ${\cal G}$ can be written in the form $({\cal N}, {\cal E}_1^1 \cup {\cal E}^{1,2}_{1} \cup {\cal E}_2^2  \cup {\cal E}^{2,1}_{2})$ with ${\cal E}_1^1 \subseteq E_1$, ${\cal E}_2^2 \subseteq E_2$, ${\cal E}^{1,2}_{1} \subseteq E_{1,2}$ and ${\cal E}^{2,1}_{2} \subseteq E_{1,2}$. Now, let ${\cal \tilde{G}} \subseteq {\cal G}$ be the subset of $k$-connected networks that lead to positive utilities for operator $1$ and $2$, that is networks ${\cal \tilde{G}}=({\mathcal N},{\cal \tilde{E}}_1^1\cup {\cal \tilde{E}}_2^2\cup  {\cal \tilde{E}}^{1,2}_{1}\cup {\cal \tilde{E}}^{2,1}_{2})$ such that $c_1 |{\cal \tilde{E}}_1^1| + c_{1,2}{\cal |\tilde{E}}^{1,2}_{1}| < 1$ and $c_2 |{\cal \tilde{E}}_2^2| + c_{2,1} |{\cal \tilde{E}}^{2,1}_{2}| < 1$. Then, the optimal strategy of the first operator ${\cal E}_1^{\text{MAX}}$ is:

1) $\emptyset$ if ${\cal \tilde{G}} = \emptyset$, and the associated payoff is $0$.

2) the elements of ${\cal \tilde{G}}$ that have the minimal value of $c_1 |{\cal \tilde{E}}_1^1| + c_{1,2}{\cal |\tilde{E}}^{1,2}_{1}|$ otherwise.

From Lemmas <ref>, <ref>, and <ref>, we can finally deduce the SPE.

Let ${\cal G}$ be the set of $k$-connected networks. Now, let ${\cal \tilde{G}} \subseteq {\cal G}$ be the subset of $k$-connected networks that lead to positive utilities for operator $1$ and $2$, that is networks $\cal \tilde{G}$ such that $c_1 |{\cal \tilde{E}}_1^1| + c_{1,2}{\cal |\tilde{E}}^{1,2}_{1}| < 1$ and $c_2 |{\cal \tilde{E}}_2^2| + c_{2,1} |{\cal \tilde{E}}^{2,1}_{2}| < 1$. We obtain the following results.

1) If ${\cal \tilde{G}} = \emptyset$, then the optimal strategy for operator $1$ and $2$ and adversary are empty sets and the resulting utilities are $U_1(\emptyset, \emptyset, \emptyset) = U_2(\emptyset, \emptyset, \emptyset) = 0$ and $U_A(\emptyset, \emptyset, \emptyset) = 1$.

2) Otherwise, the optimal strategies of operator $1$ are the elements of ${\cal \tilde{G}}$ that have minimal value of $c_1 |{\cal \tilde{E}}_1^1| + c_{1,2}{\cal |\tilde{E}}^{1,2}_1|$. Then, if ${\cal \tilde{E}}_1^1 \cup {\cal \tilde{E}}^{1,2}_{1}$ is the strategy of operator $1$, the optimal strategies of operator $2$ are the elements of ${\cal \tilde{G}}$ of the form $(\mathcal{N}, {\cal \tilde{E}}_1^1  \cup {\cal \tilde{E}}^{1,2}_{1} \cup {\cal \tilde E}_2^2 \cup {\cal \tilde E}^{2,1}_{2})$ with ${\cal \tilde E}_2^2 \subseteq E_2$ and ${\cal \tilde E}^{2,1}_{2} \subseteq E_{1,2}$ that minimizes $c_2 |{\cal \tilde{E}}_2^2| + c_{2,1} |{\cal \tilde{E}}^{2,1}_{2}|$. Finally, the optimal strategy for the adversary is the null strategy leading to $U_A({\cal \tilde{E}}_1^1 \cup {\cal \tilde E}^{1,2}_{1}, {\cal \tilde{E}}_2^2 \cup {\cal \tilde E}^{2,1}_{2}, \emptyset) = 0$.

In the following, we denote the SPE in the following format: $w := (({\cal E}_1^1,{\cal E}^{1,2}_1),({\cal E}_2^2,{\cal E}^{2,1}_2), {\cal E}_A)$ with ${\cal E}_1^1 \cup {\cal E}^{1,2}_1$ the strategy of operator 1, ${\cal E}_2^2 \cup {\cal E}^{2,1}_2$ the strategy of operator $2$, and ${\cal E}_A$ the strategy of the adversary (with ${\cal E}_A \subseteq \mathcal E_{1}^1 \cup {\cal E}^{1,2}_1 \cup {\cal E}_2^2 \cup {\cal E}_2^{2,1} $).

We can thus draw the following result.

From Lemma <ref>, we obtain that
the only SPE is the null strategy for the three players, that is the SPE is $((\emptyset, \emptyset), (\emptyset, \emptyset), \emptyset)$ if any of the following condition is satisfied:

1) $n_1 +n_2-1 < k+1$;

2) $(k+1)\min(c_{1,2}, c_{2,1}) + \floor*{\frac{(n_1-1)(k+1)}{2}} c_1 +  \floor*{\frac{(n_2-1)(k+1)}{2}} c_2\geq 2$ under $c_1 \leq c_{1,2}$ and $c_2 \leq c_{2,1}$.

In these cases, the SPE also corresponds to the optimal strategy for each of the $3$ players.

We prove successively the two conditions:

(i)  $n_1 +n_2-1$ represents the maximal number of nodes that each node can connect to, i.e., the maximal degree. If this value is lower than $k+1$, then the adversary is able to disconnect any given network with at most $k$ link removals.

(ii) Note that for the network to be $k$-resistant, each node should have a degree of (at least) $k+1$. Since there are $n_1+n_2$ nodes, then there are at least $\ceil*{\frac{(n_1+n_2)(k+1)}{2}}$ links in the network. Further, ${\cal E}^{1,2}_1 \cup {\cal E}^{2,1}_2$ should contain at least $k+1$ links. Since $c_1 \leq c_{1,2}$ and $c_2 \leq c_{2,1}$, then these links are the ones with maximal cost. Similarly, there are at least $\floor*{\frac{(n_1-1)(k+1)}{2}}$ links in ${\cal E}_1^1 \cup {\cal E}^{1,2}_1$ and at least $\floor*{\frac{(n_2-1)(k+1)}{2}}$ links in ${\cal E}_2^2 \cup {\cal E}^{2,1}_2$.

In the following, we thus focus our attention in situations in which the conditions of Lemma <ref> are not satisfied. Furthermore, we denote the set of SPE of the game by $\mathcal{L}^*$.

§.§ Efficiency of the Equilibria

In this section, we are interested in how different the costs are at the SPE and in a system where both operators can coordinate. In the scenario where both players can coordinate, the problem amounts to finding the optimal solution, and it uses at least $\ceil*{\frac{(n_1+n_2)(k+1)}{2}}$ links. Note that this bound can be reached using Harary networks <cit.>. However, since the costs $c_1$, $c_2$ and $c_{1,2}$ are different, the Harary networks using the least number of links may not correspond to the ones with the lowest cost. We present the upper and lower bounds of costs in the following proposition.

A lower bound on the total cost for creating a network is

(k+1) \min(c_{1,2},c_{2,1}) + \ceil*{\frac{(n_1+n_2-2)(k+1)}{2}} \min (c_1, c_2).

Suppose that $n_1 \geq k+1$ and $n_2 \geq k+1$. An upper bound on the total minimal cost for creating a network is

(k+1)\min(c_{1,2}+c_{2,1}) + \ceil*{\frac{n_1(k+1)}{2}}c_{1} + \ceil*{\frac{n_2(k+1)}{2}}c_{2}.

We prove successively the two parts.

(Lower Bound): We know that since any node needs to have (at least) a degree of $k+1$, then at least $\ceil*{\frac{(n_1+n_2)(k+1)}{2}}$ links need to be created, among which there should be at least $k+1$ in ${\cal E}_{1,2} \cup {\cal E}_{2,1}$ so that the adversary cannot disconnect nodes of ${\cal N}_1$ from nodes of ${\cal N}_2$.

(Upper bound): Since $n_1 \geq k+1$ and $n_2 \geq k+1$, then construct a $(n_1, k+1)$-Harary network among nodes of ${\cal N}_1$ and a $(n_2, k+1)$-Harary network among nodes of ${\cal N}_2$ which require $\ceil*{\frac{n_1(k+1)}{2}}$ and $\ceil*{\frac{n_2(k+1)}{2}}$ links, respectively. Finally, construct $k+1$ links between distinct nodes of  ${\cal N}_1$ and nodes of ${\cal N}_2$ for the global network being secure.

From Lemma <ref>, at the SPE, the two operators sequentially form an IoT-enabled infrastructure network that is $k$-connected (if such network can be constructed so that they both receive a positive utility). Recall that $w = (({\cal E}_1^1,{\cal E}^{1,2}_1),({\cal E}_2^2,{\cal E}^{2,1}_2), {\cal E}_A)$ with ${\cal E}_1^1 \cup {\cal E}^{1,2}_1$, ${\cal E}_2^2 \cup {\cal E}^{2,1}_2$, and ${\cal E}_A$ denoting the strategies of the first operator, second operator, and  the adversary, respectively. Then, the definition of price of anarchy (PoA) is as follows.

The PoA for the secure IoT-enabled  infrastructure network formation game is defined as

\begin{align}
PoA = \max_{w\in\mathcal{L}^*} \frac{C_{SPE}(w)}{C_{CO}},
\end{align}

where $C_{SPE}$ and $C_{CO}$ are the sum of costs for the operators at the SPE network and the sum of costs they would experience with coordination, respectively.

The following proposition shows that the individual costs  as well as the global sum of costs can be arbitrarily different in the SPE and coordinated optimal infrastructure networks.

The PoA of the secure IoT-enabled infrastructure network formation game can be unbounded.

We show the result by considering a situation with $n_1 >2$, $n_2 = 2$, $k=1$, $c_1=c_2=\frac{1}{n_1^3}$, $c_{1,2}=\frac{1}{n_1^2}$ and $c_{2,1}=\frac{1}{3n_1}$.

An optimal joint strategy is to create all links of the form $(i,i+1)$ with $1 \leq i \leq n_1+2$ and link $(n_1+2,1)$. As this construction forms a cycle of the $n_1+n_2$ nodes, then it is $1$-connected. Further, it contains exactly $\ceil*{\frac{(n_1+n_2)(k+1)}{2}}=n_1+n_2$ links, and among those $k+1=2$ are in $E_{1,2}$. It is therefore an optimal solution. Its cost is $C_{CO} = (n_1+n_2-2)c_1+2c_{1,2} = n_1 c_1+2c_{1,2} = \frac{3}{n_1^2}$.

Next, we investigate the SPE of the game. The operator $1$ plays the null strategy only if operator $2$ can construct a $1$-connected network at a cost lower than $1$. We then consider the following strategy for operator $2$ that consists in creating all links of the form $(i, n_1+1)$ and $(i, n_1+2)$ for all $1 \leq i \leq n_1$. This strategy has a cost of $C_{SPE} = 2 n_1 c_{2,1} = \frac{2}{3} < 1$, and the resulting network is $1$-connected which can be shown by using Menger's theorem <cit.>. Indeed, for any nodes $i$ and $j$, we can construct at least two disjoint paths. For instance, if $i$ and $j$ are both in ${\cal N}_1$, we consider the paths (both of length $2$) $i;(i, n_1+1);n_1+1 ; (n_1+1, j) ; j$ and $i ; (i, n_1+2) ; n_1+2 ; (n_1+2, j) ; j$. If $i \in {\cal N}_1$ and $j \in {\cal N}_2$, we consider the paths of length $1$: $i ; (i, j) ; j$ and the paths of length $3$: $i; (i, k) ; k; (k, \ell) ; \ell ; (\ell, j); j$ (with $k \in {\cal N}_1$, $k \neq i$ and $\ell \in {\cal N}_2$, $\ell \neq j$). Finally, if both $i$ and $j$ are in ${\cal N}_2$, then we consider the paths of length $2$: $i;(i, 1);1 ; (1, j) ; j$ and $i;(i, 2);2 ; (2, j) ; j$. Note that this strategy is optimal for the second operator, since it creates $2 n_1$ links in $E_{1,2}$.

In summary, the degradation of performance in terms of PoA in this scenario is $C_{SPE} / C_{CO} = \frac{2n_1^2}{9}$ which increases quadratically in $n_1$.

We next characterize a class of scenarios in which $PoA=1$, leading to an efficient decentralized design of secure infrastructure network.

When two subnetworks contain the same number of nodes,  and the unitary costs satisfy the following condition $c_1=c_2 = c_{1,2}=c_{2,1}<\frac{1}{n_1(k+1)}$, and $k< n_1$, then the PoA is 1.

In the scenarios that $c_{2,1}<\frac{1}{2n_1}$, we know that at the SPE, only operator 2 creates interlinks which are solely in $E_{1,2}$. Thus, the cost at SPE is $C_{SPE} = n_1(k+1)c_{2,1}$. For the cooperative case, the network configuration is a Harary network due to the same link costs. Therefore, the total cost is $C_{CO} = \ceil*{\frac{(n_1+n_2)(k+1)}{2}}c_1$ in the optimal network. Due to $n_1=n_2$ and $c_{2,1} = c_1$, we obtain $C_{CO} = n_1(k+1)c_{2,1}c_{2,1} = C_{SPE}$, and thus $PoA = 1$ in this scenario.

§.§ Some Counter-Intuitive Results

In this section, we present some counter-intuitive results of the IoT-enabled infrastructure network formation game.

The following Proposition <ref> shows that for given system parameters, the SPE may not be unique. This, in terms of infrastructure network architecture is not surprising, since several topologies can lead to a $k$-connected network with the minimal cost. More surprisingly, however is the fact that the SPE may not be unique in terms of the costs.

For given values of the parameters $n_1$, $n_2$, $c_1$, $c_2$, $c_{1,2}$, $c_{2,1}$ and $c_A$, the SPE may not be unique. More precisely, at the SPE, there is a unique payoff value associated to the operator $1$, but there may be several payoff values of the operator $2$.

We show the result by providing an example with the property. Let parameters be $n_1 = 4$, $n_2 = 3$, $k=2$, and $c_1 = c_2 = c_{1,2} = c_{2,1} = 0.09$.
From the values of $c_2$ and $c_{2,1}$, operator $1$ knows that at the SPE, operator $2$ builds at most $11$ links. Since each node of ${\cal N}_1$ needs to have a degree of $3$, if operator $1$ builds no link, then operator $2$ needs to build at least $12$ links which is more than that it can bear. Thus operator $1$ needs to build at least $1$ link. Then, depending on the choice of the link created by operator $1$, operator $2$ needs to build either $10$ or $11$ links, as illustrated in Fig. <ref>.
protege/.style = line width=4pt
attaque/.style = style=loosely dashed
both/.style = line width=3pt, style=loosely dashed
multi/.style =
shape = rectangle,
line width=1pt,
inner sep = 1.5pt,
outer sep = 0pt,
minimum size = 15pt,

[${\cal E}_1^1 = \emptyset$ and ${\cal E}_1^{1,2}=\{(1,5)\}$. Then ${|\cal E}_2^{2,1}|=11$.]

1 (1)2 (2)3 (3)4
(1)5 (5)6 (6)7
EdgeStyle/.style = protege
[${\cal E}_1^1 = \{(1,2)\}$ and ${\cal E}_1^{1,2}=\emptyset$. Then ${|\cal E}_2^{2,1}|=10$.]

1 (1)2 (2)3 (3)4
(1)5 (5)6 (6)7
EdgeStyle/.style = protege

$\mathcal{N}_1=\{1,2,3,4\}$ and $\mathcal{N}_2=\{5,6,7\}$. Non-unicity of the cost of operator $2$. Operator 2 either creates 10 or 11 links depending on operator 1's strategy at equilibrium. (Bold line: operator $1$; Plain thin line: operator $2$).

In addition, the order of the operators creating their communication links has an impact on the payoffs of the players.

Consider an IoT-enabled infrastructure network where the roles of the operators are symmetric, i.e.,
$ n_1 = n_2, \; c_{1,2}=c_{2,1}, \; c_1=c_2.
Suppose that $n_1 (k+1) c_{1,2} < 1$. Then at the SPE, the payoff of operator $1$ is $1$ while that of operator $2$ is $1-n_1(k+1) c_{1,2}$.

We consider the network $(\mathcal N, {\cal E})$ with ${\cal E} \subseteq E_{1,2}$. ${\cal E}$ is the set of links $(i,j)$ with $1 \leq i \leq n_1$ and $n_1 +(i -\floor*{\frac{k}{2}}) \mod n_2 \leq j \leq n_1 + (i+\ceil*{\frac{k}{2}}) \mod n_2$. Then, the network is $k$-connected and has exactly $\frac{(n_1+n_2)(k+1)}{2}$ links.
The operator 2 can construct a $k$-connected SPE network which has exactly $\frac{(n_1+n_2)(k+1)}{2}=n_1(k+1)$ links all in $E_{1,2}$.

Next, we investigate the impact of order of play between two operators in constructing the network on their corresponding payoffs. Specifically, we propose a notion, Price of Seniority (PoS), to quantify the potential loss of operator 2 for playing second comparing with the scenario in which he plays first. The formal definition of PoS is presented as follows.

Denote $C_2$ by the total cost of operator 2 at SPE, and $C_2^{(1)}$ by its total cost if it was playing first. Then the price of seniority (PoS) that quantifies the loss of operator 2 for playing second can be defined as

\begin{align}
PoS = \max_{w\in\mathcal{L}^*,\tilde{w}\in\tilde{\mathcal{L}}^*}\ \frac{C_2(w)}{C_2^{(1)}(\tilde{w})}.
\end{align}

Recall that $w$ is a strategy profile including all three players' actions, and $\mathcal{L}^*$ is a set containing SPE of the game. Similar for $\tilde{w}$ and
$\tilde{\mathcal{L}}^*$ where the playing sequence of operators 1 and 2 is interchanged.

Furthermore, in the case of symmetric scenarios, i.e., $n_1=n_2$, $c_1=c_2$, and $c_{1,2}=c_{2,1}$, and denote $C_1$ by the total cost of operator 1, then PoS can be written as

\begin{align*}
PoS = \max_{w\in\mathcal{L}^*}\ \frac{C_2(w)}{C_1(w)} =  \max_{w\in\mathcal{L}^*}\ \frac{c_{2} |{\cal E}_2 \cap E_2| + c_{2,1} |{\cal E}_2 \cap E_{1,2} |}{c_{1} |{\cal E}_1 \cap E_1| + c_{1,2} |{\cal E}_1 \cap E_{1,2} |},
\end{align*}

where $C_2^{(1)}$ is replaced by $C_1$ due to symmetry.

The PoS can be arbitrary large, and it is lower bounded by 1, i.e., $PoS\geq 1$.

Based on Proposition <ref>, we can verify that in the symmetric scenarios with $n_1 (k+1) c_{1,2} < 1$, $C_1 = 0$ and $C_2 = n_1(k+1)c_{1,2}$, and hence $PoS$ can be infinite. For generally cases, we assume that $w$ is an SPE of the original game. Then, $w$ is also a feasible strategy profile for all three players if operator 2 plays first. Thus, we know that the utility of operator $2$ for acting first $C_2^{(1)}$ can at least achieve at a value $C_2$ resulting from the SPE $w$ of original game. Therefore, we conclude that $C_2/C_2^{(1)}\geq 1$, leading to $PoS\geq 1$.

Corollary <ref> states that playing first is beneficial for the operator, and in certain cases the operator's optimal strategy becomes null if moving first in the game. Knowing this fact, the operator who has power to determine the order of players will prefer to move first by acting as a leader in this dynamic game to gain more benefits.

§.§ More Threats Induce Collaboration

In the adversarial network design, cyber attacks induce more collaboration (fair share of the costs) between two network operators. Specifically, when $k$ is small, operator $2$ may be the only player in creating the whole connected network. As $k$ increases (and as the number of required links increases), the cost for creating a connect infrastructure network increases. Then, at some point of $k$ when $(n_1+n_2) (k+1) > 1$, only network operator 2 cannot create a secure infrastructure network. Then, a set of new communication links is required from operator $1$ for the network to be $k$-connected. This phenomenon can be summarized as: a higher level of threats leads to collaboration between operators. Note that in some scenarios, the cost of operator 1 can be larger than that of operator 2 in network formation game. We illustrate these results using the following example.

Let $n_1 = n_2 = 3$, $c_1 = c_{1,2}=0.19$ and $c_2 = c_{2,1}=0.21$.
Then, for $k=1$, the cost of operator 1 is $C_1 = 2c_1 = 0.38$, and the cost of operator 2 is $C_2 = 4c_2 = 0.84$. When $k=2$, the costs of operators 1 and 2 become $C_1 = 5c_1 = 0.95$ and $C_2 = 4 c_2 = 0.84$, respectively, where operator 1 costs more in creating a secure network than operator 2. In addition, as $k$ increases, operator 1 collaborates more with operator 2 to construct a $k$-resistant two-layer network.

Algorithm to construct a secure interdependent IoT-enabled infrastructure network

Parameters $c_1$, $c_2$, $c_{1,2}$, $c_{2,1}$, and odd $n_1$, $k$
Network created by operator $1$ and $2$ at the SPE
Let $e_1=0$ *Number of links for operator $1$ to build
Let $nb_{11} = (n_1-1) (k+1)/2$  *The maximal number of links in $E_1$
Compute $C_2(e_1) = n_1 (k+1) c_{2,1}$  *Cost of operator $2$
$C_2(e_1) \geq 1$ *Increase $e_1$ until $C_2$ becomes lower than $1$

$e_1 = e_1+1$
$e_1 \leq nb_{11}$
$C_2(e_1) = C_2(e_1) - 2 c_{2,1} + c_2$ $C_2(e_1) = C_2(e_1) - c_{2,1}$

Let $e_{12} = \max(0, e_1-nb_{11})$; $e_{11} = e_1-e_{12}$
*Number of links in $E_{1,2}$ and $E_{1}$ created by operator $1$

Let $C_1(e_1) = e_{12} c_{1,2} + e_{11} c_1$*Compute the resulting cost of operator $1$
$C_1(e_1) \geq 1$ *The SPE is $((\emptyset, \emptyset), (\emptyset, \emptyset), \emptyset)$.

Set $m = \floor*{\frac{e_{11}}{n_1-1}}$ *Number of Hamiltonian cycles in $E_1$

$i=1$ to $m(n_1-1)$ *Create $(n_1, m)$-Harary network without links $(1,i)$ with $2 \leq i \leq m$

Let $j, \ell \geq 0$, such that $i-1 = \ell (n_1-1)+j$ and $j < n_1-1$
$j = j+2$; $\ell = \ell+1$;
Create links $(j; (j+\ell) \mod n_1)$ and $(j+n_1; ((j+\ell) \mod n_1) + n_1)$

$i=1$ to $m$ *Create links in $E_{1,2}$ such that $m$ Hamiltonian cycles are formed

Create links $(1; n_1+1+i)$ and $(n_1+1; 1+i)$

Let $z = e_{11}-m(n_1-1)$ *Number of extra links in $E_1$

$\ell =1$ to $z$

$p = (j + (n_1+1)/2) \mod n_1$;
Create link $(j;p)$ and $(j+n_1; p+n_1)$;
Set $j=p$

$\ell =z+1$ to $n_1-1$

$p = (j + (n_1+1)/2) \mod n_1$;
Create link $(j;p+n_1)$ and $(j+n_1; p)$;

Create link $(1; n_1+1)$ and $((n_1+1)/2; n_1 + (n_1+1)/2)$

Let $m_{12} = (k+1)/2-m$ *Remaining Hamilton cycles in $E_{1,2}$   $z>0$$m_{12} = m_{12}-1$

$\ell = 1$ to $m_{12}$

$p=1$ to $n_1$

Create link $(p; (p+m+\ell+1) \mod n_1 +n_1)$ and $(p+m + \ell+1) \mod n_1 + n_1; (p+1) \mod n_1)$

§ DESIGN AND ANALYSIS OF ALGORITHM FOR SECURE INTERDEPENDENT  NETWORK CONSTRUCTION

With the obtained SPE in Section <ref>, the next critical step is to construct the secure interdependent IoT-enabled infrastructure networks. In this section, we present an algorithm to achieve this goal. For clarity purposes, we consider the scenario that $n_1 = n_2$. Further, we suppose that $n_1$ and $k$ are odd numbers. Knowing that in general mission-critical infrastructure networks, creating a link between two networks can be more difficult than creating a link within a network and thus induces a higher cost, we then have the conditions  $c_1 \leq c_{1,2}$ and $c_2 \leq c_{2,1}$ during the algorithm design.

§.§ Network Construction Algorithm Design

To construct a $k$-resistant IoT-enabled infrastructure network, operators $1$ and $2$ need to jointly create a network that has at least $\ceil*{\frac{n(k+1)}{2}} = n_1(k+1)$ links. This constitutes a lower bound on the number of links created (in a non-null strategy). Since $k$ is odd, by using Menger's theorem <cit.>, we propose a construction using a superposition of exactly $\frac{k+1}{2}$ independent Hamiltonian cycles. The algorithm for the network construction is depicted in Algorithm <ref>, and for clarity, we decompose it into 4 stages as follows.

*Stage $\mathbf{1}$ (Algorithm, line 1–15) In this stage, we determine the optimal values of $|{\cal E}_1^1|$ and $|{\cal E}_1^{1,2}|$.

Denote $e_1 = |{\cal E}_1^1 \cup {\cal E}_1^{1,2}|$.
For a given $e_1$, note that the cost of operator $1$ is minimized when $|{\cal E}_{1,2}|$ is minimized (since $c_1 \leq c_{1,2}$).
Further, for each node of ${\cal N}_1$ whose degree is $d$ (with $d \leq k+1$), operator $2$ needs to create at least $k+1-d$ links in $E_{1,2}$. Note that any link of $E_1$ increases the degree of $2$ nodes in ${\cal N}_1$ by $1$, while any link of $E_{1,2}$ increases the degree of only $1$ node in ${\cal N}_1$ by $1$. Thus,
each link created by operator $1$ in $E_1$ allows to decrease $|{\cal E}_2^{2,1}|$ by $2$, while each link created by operator $1$ in $E_{1,2}$ allows to decrease $|{\cal E}_2^{2,1}|$ by only $1$. Furthermore, for a given value of $e_1$, the cost of the second operator is minimized when $|{\cal E}_2^{2,1}|$ is minimized (since $c_2 \leq c_{2,1}$, as long as the sum of degrees of nodes in ${\cal N}_1$ is less than $n_1(k+1)-(k+1)$ since $k+1$ links are required in $E_{1,2}$).

Thus, for a given value of $e_1$,
both operators' costs are minimized when  $|{\cal E}_1^{1,2}|$ is minimized, that is when operator $1$ uses as many links between nodes of ${\cal N}_1$ as possible, as long as the sum of degrees of the nodes in ${\cal N}_1$ is less than $(n_1-1)(k+1)$.
Thus, for a given $e_1$,

$$e_{11} = |{\cal E}_{1}^1| =
\left\{
\begin{array}{ll}
e_1 & \text{if } 2e_1 \leq (n_1-1)(k+1),\\
(n_1-1)(k+1)/2 & \text{otherwise.}
\end{array}\right.

Thus, operator $1$ chooses the minimal value of $e_1$ and a set of links such that operator $2$ can
construct a $k$-resistant network with a cost lower than $1$.
Then, operator $1$ computes its own resulting cost. If it is higher than $1$, then no links are created and the SPE is $((\emptyset, \emptyset), (\emptyset, \emptyset), \emptyset)$. Otherwise, a network with $e_1$ links for operator $1$ and $n_1(k+1)-e_1$ links for operator $2$ is created.

*Stage $\mathbf{2}$ (Algorithm, line 16–24) In this stage, we form $m$ independent Hamiltonian cycles with $m = \floor*{\frac{e_{11}}{n_1-1}}$.

First, operator $1$ creates
links in $E_1$ in a similar manner as in Harary <cit.>. That is, it first creates links between nodes $i$ and $j$ such that $(|i-j| \mod n_1) = 1$, and then $(|i-j| \mod n_1) = 2$, etc. From <cit.>, we know that a $2m$-Harary network contains exactly $m$ independent Hamilton cycles of ${\cal N}_1$, that is cycles that go through all $n_1$ nodes and such that no link is used more than once. Further, <cit.> shows that there exists a construction such that links $(1;2)$, $(1;3)$, ..., $(1; m-1)$ all belong to different cycles. Thus, we remove those links from our construction and build all other links of the Harary network.
We further construct $m(n_1-1)$ links in $E_2$ which are symmetric to as those in $E_1$. Note that these links in $E_2$ are created by operator 2. Hence, this stage creates $2m(n_1-1)$ links.

Further, for $1 \leq i \leq m$,
by constructing two links, one between nodes $1$ and $n_1+i+1$ and one between nodes $n_1+1$ and $i+1$, we form a Hamiltonian cycle between all nodes in ${\cal N}_1 \cup {\cal N}_2$. Note that all $m$ different cycles use independent links. This further creates $2m$ links in ${E}_{1,2}$.

*Stage $\mathbf{3}$ (Algorithm, line 25–37) In the case where $e_{11} > m(n_1-1)$, then operator $1$ still needs to create $z = e_{11}-m(n_1-1)$ links in $E_1$.

In that case, we create an additional Hamiltonian cycle in the following manner. Starting from node $1$, we consider the sequence $i_1; i_2; ... ; i_{n_1}$ with $i_1 = 1$ and $i_{j+1} = (i_{j}+ (n_1+1)/2) \mod n_1$. Since $n_1$ is odd, then for all $1 \leq j, \ell \leq  n_1$ and $j\neq \ell$, we have $i_j \neq i_\ell$ or in other words the sequence $i_1; i_2; ... ; i_{n_1}$ defines a permutation of indices $1, ..., n_1$. We then consider the following construction: for $j \leq z$, we construct the links $(i_j; i_{j+1})$ and $(i_{j}+n_1; i_{j+1}+n_1)$ and for $z < j < n_1$, we construct the links $(i_j; i_{j+1}+n_1)$ and $(i_{j}+n_1; i_{j+1})$. This defines $2$ sequences, and each one contains exactly $n_1$ nodes. By adding links $(1; n_1+1)$ and $((n_1+1)/2; n_1 + (n_1+1)/2)$, we create a full Hamiltonian cycle. Note that none of the links used previously have been created since $m < (k+1)/2$. This stage creates exactly either $0$ link or $2n_1 = n$ links among which $z$ links are in $E_1$, $z$ links are in $E_2$, and $n-2z$ links are in $E_{1,2}$.

*Stage $\mathbf{4}$ (Algorithm, line 38–42) In total, either $m$ or $m+1$ Hamiltonian cycles have been created and $e_{11}$ links have been used. We thus create the remaining $m_{12}$ Hamiltonian cycles with links exclusively in $E_{1,2}$ that have not been created in the previous stages. Here, $m_{12}=(k+1)/2-m$ if $z\leq 0$ and $m_{12}=(k+1)/2-m-1$ otherwise.  A possible solution for $k<n_1$ is as follows. For all $t$ that satisfy $m < t < (k+1)/2$, we construct a Hamiltonian cycle following this pattern:
for any $1 \leq i \leq n_1$, we create links $(i; (i+t \mod n_1) +n_1)$ and $((i+t) \mod n_1 +n_1; (i+1)\mod n_1)$ in the network.

The above 4 stages of construction yield an equilibrium two-layer secure IoT-enabled infrastructure network.

Illustration of the secure network construction process using Algorithm <ref>. Both subnetworks contain 5 nodes. Blue-colored links are created by operator 1, and black-colored links are established by operator 2. The network constructed at SPE is resistant to any 3 link attacks.  Stage 1 of the algorithm yields the number of links that each operator needs to create at the SPE. Stage 2-4 constructs the secure network that satisfies the requirements. In this example, one Hamiltonian cycle is created at both stages 2 and 3, while no further links are constructed at stage 4, as network after stage 3 is resistant to 3 link attacks.

An Illustrative Example:
We next present an example to illustrate how the developed algorithm works. The parameters are summarized as follows: $n_1=n_2=5$, $k=3$, $c_1=c_2 = \frac{1}{20}$, and $c_{1,2} = c_{2,1} = \frac{1}{10}$. Fig. <ref> depicts the detailed steps of the secure network construction process. In stage 1 of the algorithm (line $1-15$), we obtain the following: $e_{12} =|{\cal E}_1^{1,2} | = 0$, $e_{11} = |{\cal E}_1^1| = 7$, which means that operator 1 creates 0 link in $E_{1,2}$ and 7 links in $E_1^1$ at SPE. Furthermore, operator 2 creates  6 links in $E_{1,2}$ and 7 links in $E_2$ at SPE. Hence, the net utilities of operators 1 and 2 at SPE are $\frac{13}{20}$ and $\frac{1}{20}$, respectively. Next, stage 2-4 of the algorithm creates such a secure infrastructure network which is resistant to $k=3$ link removal attacks. Specifically, at stage 2 (line $16-24$), two network operators create an independent Hamiltonian cycle, where operator 1 creates 4 links in $E_1$ and operator 2 creates 4 links in $E_2$ and 2 links in $E_{1,2}$. After this stage, the network is resistant to 1 link attack.  At stage 3 (line $25-37$), two operators create an additional Hamiltonian cycle in our example, after which each node is of degree 4 and thus the network is resistant to 3 link attacks. At this stage, operator 1 further creates 3 links in $E_1$ and operator 2 creates 3 links in $E_2$ and 4 links in $E_{1,2}$. Both operators at stage 4 of the algorithm (line 38-42) do not construct links, as there is no remaining Hamilton cycle to be further created in $E_{1,2}$. This example shows that the algorithm can successfully guide the design of secure interdependent networks.

§.§ Complexity and Scalability Analysis

We proceed to analyze the property of the designed algorithm in this section. The first one is the complexity. In the construction of secure networks based on Algorithm <ref>, we allocate the links in two networks sequentially. Depending on the system parameters, the total number of allocated links is achieved between $\ceil*{\frac{(n_1+n_2)(k+1)}{2}}$ and $\ceil*{\frac{n_1(k+1)}{2}}+\ceil*{\frac{n_2(k+1)}{2}}+k+1$. Note that $\ceil*{\frac{(n_1+n_2)(k+1)}{2}}$ is a lower bound in the sense that it is the minimum number of links for a network containing $n_1+n_2$ nodes being resistant to $k$ attacks. Similarly, $\ceil*{\frac{n_1(k+1)}{2}}+\ceil*{\frac{n_2(k+1)}{2}}+k+1$ is an upper bound for a secure network where each subnetwork is resistant to $k$ attacks and another $k+1$ links are allocated between two subnetworks. Therefore, the complexity of Algorithm <ref> is linear in the number of nodes and the number of attacks, i.e., $O(nk)$, where $n=n_1+n_2$.

We next analyze the scalability of the algorithm. Scalability is critical when the system parameter changes and the equilibrium network becomes different and needs to be reconfigured. In our algorithm, the main procedure in designing the secure network is constructing Hamiltonian cycles sequentially in both subnetworks and between two layers. This construction pattern is highly scalable in the sense that when the number of nodes in two subnetworks or the number of attacks changes, the solution infrastructure network at SPE adopts with a similar topology and only a small set of existing links need to be rewired. The scalability of the algorithm will be further justified using case studies in Section <ref>.

§ CASE STUDIES

In this section, we use case studies of IoBT to illustrate the optimal design principles of secure  IoT-enabled networks with heterogeneous components. In a battlefield scenario, the unmanned ground vehicles (UGV) and unmanned aerial vehicles (UAV) execute missions together. To enhance the information transmission quality and situational awareness of each agent in the battlefield, a secure and reliable communication network resistant to malicious attacks is critical. Note that the results in this section are also applicable to other mission-critical heterogeneous IoT network applications.

§.§ Secure Interdependent Network Design at SPE

In the following case studies, we consider $n_1=9$ UAVs and $n_2=9$ UGVs in the two-layer IoBT network. The normalized costs of creating different types of links are as follows: $c_1 = \frac{1}{30}$, $c_{1,2} = \frac{1}{20}$, $c_2=\frac{1}{45}$, and $c_{2,1} = \frac{2}{45}$. Here, we can see that the cost of creating intralinks across two layers is more than that of creating interlinks within the network itself. In addition, the normalized unit cost of attack is $c_A = \frac{1}{3}$, and hence the attacker can compromise at most $k=3$ links in the network. The above normalized costs can be transformed to their nominal monetary costs when the basis ratio is determined. Based on Lemma <ref>, we obtain that, at SPE, the UAV network operator 1 creates 10 interlinks within its own network, and the UGV network operator 2 formulates 10 interlinks as well as 16 intralinks between two layers in the IoBT. Therefore, the equilibrium payoffs for operators 1 and 2 are $U_1^* = \frac{5}{6}$ and $U_2^* = \frac{1}{15}$, respectively. Note that the equilibrium IoBT network is a 3-connected network, and thus the attacker is incapable of disconnecting the system even with his best effort. By using the designed Algorithm <ref>, we construct the solution IoBT network resistant to $3$ attacks and the result is shown in Fig. <ref>. We can verify that operator 2 not only allocates link resources in his own UGV network but also in the places connecting two interdependent layers. Furthermore, each node in the network is of degree 4, and the network is resistant to anticipated attacks.

§.§ Impact of the Number of Attacks

We next investigate the impact of the number of attacks on the adversarial IoBT network formation. Varying $k$ captures the operators' belief on the attacker's incentives. A larger $k$ indicates that the operators anticipating a higher level of threats, and thus the designed IoBT network needs to be more resistant.  In the following, the link creation costs are the same as those in the previous case study. We vary the attacker's capability $k$, and the obtained results are shown in Fig. <ref>. Fig. <ref> illustrates the number of formed links of network operators 1 and 2 at the equilibrium IoBT configuration. When the attacker can compromise less than 2 links, the UGV network operator creates sufficient interlinks that connect UAVs and UGVs. Therefore, the utility of UAV network operator is 1. As the number of attacks increases, operator 1 begins to contribute to the network defense because operator 2 alone cannot secure the network with a positive payoff. For $2\leq k<7$, operator 1 allocates link resources only within the UAV network. In comparison, operator 2 creates fewer intralinks and allocates more resources in its own UGV network as the cyber threats increase. In addition, when the number of attacks exceeds a certain level, i.e., $k\geq 7$ in this case, both network operators will cease to protect the network, and the corresponding SPE is a null strategy which satisfies the second condition in Lemma <ref>. Fig. <ref> shows the utilities of two operators at the equilibrium IoBT network. The operator 1's payoff decreases as $k$ grows. Interestingly, in the regime where the UAV network operator contributes to the secure IoBT network, i.e.,  $2\leq k \leq 6$, the utility of UGV network operator remains the same which corresponds to the maximum effort that operator 2 can use. Based on this case study, we can conclude that higher threat levels induce more collaborations between two network operators.

The 3-connected equilibrium IoBT network.

[Number of links in the equilibrium network]

[Equilibrium utility of operators]

[](a) shows the number of different types of links that operators 1 and 2 should create at the equilibrium IoBT network. (b) is the corresponding utility of two operators.

§.§ Impact of the Number of Agents

To illustrate the scalability of the designed algorithm, we next present the results with different  number of agents in the network. This scenario is practical in mission-critical applications as the number of agents may change over time. The system parameters are the same as those in Section <ref> except that $n_1$ and $n_2$ are different (agents leaving or joining the battlefield). Note that as $n_1$ and $n_2$ change, the IoBT configurations at SPE are also different. We present the results when some agents in two subnetworks leave the battlefield, i.e., $n_1=8$ and $n_2 = 8$. At the SPE, operator 1 creates 7 interlinks within its network, and operator 2 formulates 7 interlinks and 18 intralinks between two layers in the IoBT. The equilibrium payoffs for operators 1 and 2 are $U_1^* = \frac{23}{30}$ and $U_2^* = \frac{2}{45}$, respectively. Figure <ref> shows the constructed network using Algorithm <ref>. We can see that comparing with the result in Fig. <ref>, the links associated with those leaving agents are removed and link rewiring only happens to a small set of nodes originally connected with leaving agents. The major network configuration stays unchanged which demonstrates the scalability of the algorithm.

The 3-connected equilibrium IoBT network with two agents leaving the field. Comparing with Fig. <ref>, only a small subset of links need to be rewired which shows the scalability of the algorithm.

§ CONCLUSION

In this paper, we have investigated the adversarial network design for the interdependent IoT-enabled infrastructures. To secure the heterogeneous components in the infrastructure networks, we have formulated a three-player three-stage network formation game where two network operators aim to keep the network connected in the presence of attacks. The subgame perfect Nash equilibrium (SPE) of the game has been shown to be an empty set when the number of communication links that the attacker can compromise exceeds a threshold, or the link creations are too costly for the operators. The price of anarchy (PoA), i.e., the ratio of network formation costs between the SPE and team optimal strategies, can be unbounded. Also, we have identified cases where SPE solution is as efficient as the team optimal one, yielding PoA equaling 1. Furthermore, with a higher threat level, we have shown that two network operators are more willing to collaborate to defend against attacks, since one operator alone cannot completely mitigate the threats with a limited amount of link resources. The future work would extend the dynamic game model and investigate the case in which network operators can create secure links and insecure links with distinct costs. Under such modeling, the adversary also has heterogeneous attack costs to different types of communication links.