# Resilient Strong Structural Controllability in Networks
using Leaky Forcing in Graphs

Waseem Abbas W. Abbas is with the Systems Engineering Department at the
University of Texas at Dallas, Richardson, TX (Email:
waseem.abbas@utdallas.edu).

###### Abstract

This paper studies the problem of selecting input nodes (leaders) to make
networks strong structurally controllable despite misbehaving nodes and edges.
We utilize a graph-based characterization of network strong structural
controllability (SSC) in terms of zero forcing in graphs, which is a dynamic
coloring of nodes. We consider three types of misbehaving nodes and edges that
disrupt the zero forcing process in graphs, thus, deteriorating the network
SSC. Then, we examine a leader selection guaranteeing network SSC by ensuring
the accuracy of the zero forcing process, despite $k$ misbehaving nodes/edges.
Our main result shows that a network is resilient to $k$ misbehaving
nodes/edges under one threat model if and only if it is resilient to the same
number of failures under the other threat models. Thus, resilience against one
threat model implies resilience against the other models. We then discuss the
computational aspects of leader selection for resilient SSC and present a
numerical evaluation.

###### Index Terms:

Strong structural controllability, zero forcing sets, resilience in networks,
dynamics over graphs.

##  I Introduction

The ability to control a network of agents through external control signals
profoundly depends on the underlying network topology [1, 2, 3, 4, 5]. The
control signals are injected into the network via a subset of agents,
typically called leaders. Computing a minimum number of leaders and their
locations within the network for complete controllability are central issues
in the cooperative control of networks. A popular approach for the leader
selection problem, which is well-studied, is to characterize network
controllability from a graph-theoretic perspective. Then formulate an
appropriate vertex selection problem in graphs that can be solved through
various combinatorial methods.

To this end, several graph-based characterizations of network controllability
have been presented, including those based on graph distances, zero forcing in
graphs, dominating sets, matching in graphs, and others (e.g., [6, 7, 8, 9,
10, 11, 12]). The notion of zero forcing in graphs is particularly useful for
strong structural controllability (SSC) in networks, which ascertains that for
a given set of leaders, if the network is controllable for one set of edge
weights, then it is controllable for all feasible edge weights. The zero
forcing phenomenon, introduced in [13], is a dynamic coloring of nodes in a
graph in which only a subset of nodes are initially colored, causing other
nodes to change colors according to some rules. A set of initially colored
nodes that eventually color the entire graph is called a zero forcing set of
the graph. Interestingly, a leader set for the strong structural
controllability of a network is directly related to the idea of a zero forcing
set in the underlying network graph [6, 14, 15]. A set of leaders makes a
given network strong structurally controllable if the corresponding nodes in
the underlying graph constitute a zero forcing set.

In this paper, we consider the leader selection for _resilient strong
structural controllability_ , that is, the network remains SSC despite some
misbehaving nodes or edges deviating from their normal functionalities. A
single misbehaving agent or an edge (due to a fault or an adversary) can
severely deteriorate the network’s controllability. Considering the
susceptibility of networks to adversarial attacks and failures, the resilient
SSC is a crucial paradigm in network control systems. We consider three
different abnormal behaviors by nodes (agents) and edges. These misbehaving
nodes and edges primarily disrupt the zero forcing process in the underlying
network graph, affecting the network’s SSC. In particular, we examine leak
nodes (agents that do not follow the rules of the zero forcing process), non-
forcing edges (links that again disrupt the zero forcing process), and
removable edges (links that are lost and affect interconnections between
nodes). We then study the leader set guaranteeing the network SSC despite a
given number of such misbehaving nodes/edges. For this, we utilize the idea of
_leaky forcing_ , a variant of zero forcing in graphs recently introduced in
[16, 17]. Our main result shows that the resilient leader selection against
one abnormal behavior implies resilience against the other two abnormal
behaviors. The main contributions are below:

  * •

We study the resilient SSC problem in networks by connecting it to the notion
of leaky forcing in graphs.

  * •

We consider three models of misbehaving nodes/edges in networks, including
node leaks, non-forcing edges, and removable edges, and formulate leader
selection in networks to guarantee that the network remains SSC despite $k$
such abnormal nodes/edges (Section III).

  * •

We show that a given leader set is resilient to $k$ misbehaving nodes/edges
under one model if and only if it is resilient to the same number of
misbehaving nodes/edges in the other model (Section IV).

  * •

Finally, we discuss computational aspects of selecting leaders for the
resilient SSC and also present a numerical evaluation (Section V).

There have been works discussing the impact of nodes/edges addition and
deletion on the network’s controllability, for instance, [18, 19, 20, 21].
Similarly, some researchers have considered the effects of actuators/input
node failures on the overall controllability of systems. Some also propose
methods to have a sufficient number of input nodes maintaining network
controllability despite such failures [22, 23, 24, 25]. Our work differs from
theirs as we consider node/edge misbehavior models beyond deletion. These
misbehaving nodes/edges remain within the network disrupting the underlying
graph-theoretic process required to ensure SSC. Our goal is to have leader
sets guaranteeing SSC despite the existence of any $k$ such nodes/edges within
the network. For this, we utilize the idea of leaky forcing in graphs.

The rest of the paper is organized as follows: Section II presents preliminary
ideas related to network controllability and zero forcing in graphs. Section
III explains various threat models and formulates the leader selection
problems for the resilient SSC in networks. Section IV presents the main
result regarding the equivalence of leader selection for resilient SSC under
various threat models. Section V discusses the computational aspects and
provide numerical illustrations. Finally, Section VI concludes the paper.

##  II Preliminaries

We consider a network of agents modeled by an undirected graph $G=(V,E)$. The
node set $V$, and the edge set $E$, represent agents and interconnections
between agents, respectively. The edge between nodes $i$ and $j$ is denoted by
an unordered pair $(i,j)$. The _neighborhood_ of $u$ is
$\mathcal{N}_{i}=\\{j\in V|\;(i,j)\in E\\}$. The _distance_ between nodes $i$
and $j$, denoted by $d(i,j)$, is the number of edges in the shortest path
between them. For a given graph $G=(V,E)$ with $|V|=n$ nodes, we define a
family of symmetric matrices $\mathcal{M}(G)$ as below:

$\begin{split}\mathcal{M}(G)=\\{M\in\mathbb{R}^{n\times
n}\;&|\;M=M^{\top},\text{ and for }i\neq j,\\\ &M_{ij}\neq
0\Leftrightarrow(i,j)\in E\\}.\end{split}$ (1)

Note that the location of zero and non-zero entries in every
$M\in\mathcal{M}(G)$ remains the same, and is entirely described by the edge
set of $G$.

###  II-A System Model and Graph Controllability

We consider the following leader-follower system defined over a graph
$G=(V,E)$.

$\dot{x}(t)=Mx(t)+Bu(t),$ (2)

where $x(t)\in\mathbb{R}^{n}$ is the system state, $u(t)\in\mathbb{R}^{m}$ is
the external input, $M\in\mathcal{M}(G)$ (as in (1)) is the system matrix, and
$B\in\mathbb{R}^{n\times m}$ is the input matrix describing the _leader_
(input) nodes. If $V=\\{v_{1},v_{2},\cdots,v_{n}\\}$, and
$V^{\prime}=\\{\ell_{1},\ell_{2},\cdots,\ell_{m}\\}\subseteq V$ is a set of
leader nodes, then we define $B$ as follows:

$[B]_{ij}=\left\\{\begin{array}[]{lll}1&\text{if }v_{i}=\ell_{j},\\\
0&\text{otherwise.}\end{array}\right.$ (3)

We observe that the family of matrices $\mathcal{M}(G)$ describes a number of
system matrices defined over $G$, including the Laplacian and adjacency
matrices.

For a given graph $G$, system matrix $M\in\mathcal{M}(G)$, and input matrix
$B$, the system in (2) is called _controllable_ if there exists an input to
drive the system from an arbitrary initial state $x(t_{0})$ to an arbitrary
final state $x(t_{f})$. In this case, we say that $(M,B)$ is a _controllable
pair_. A pair $(M,B)$ is controllable if and only if the rank of the
_controllability matrix_ $\Gamma(M,B)$, defined below, is $|V|=n$ (i.e., full
rank).

$\Gamma(M,B)=\left[\begin{array}[]{lllll}B&MB&M^{2}B&\cdots&M^{n-1}B\\\
\end{array}\right].$ (4)

Since leader nodes $V^{\prime}$ define the input matrix $B$, we sometimes
abuse the notation slightly and use _$(M,V^{\prime})$ is controllable_ to
denote that $(M,B)$ is a controllable pair.

###### Definition 1

_(Network Strong Structural Controllability)_ A network $G=(V,E)$ with a
leader set $V^{\prime}\subseteq V$ is strong structurally controllable if and
only if $(M,V^{\prime})$ is a controllable pair _for all_
$M\in\mathcal{M}(G)$.

Network strong structural controllability is a stronger notion compared to the
(weak) structural controllability, which requires the existence of at least
one matrix $M\in\mathcal{M}(G)$ for which $(M,V^{\prime})$ is a controllable
pair.

###  II-B Network Controllability and Zero Forcing in Graphs

A central problem in network controllability is to compute a minimum leader
set $V^{\prime}\subseteq V$ that makes the network strong structurally
controllable (as defined above). The problem is often referred to as the
_minimum leader selection_ for network controllability. A graph-theoretic
characterization of the minimum leader set rendering the network strong
structurally controllable is remarkably useful here. Monshizadeh et al.
characterized the minimum leader set for network strong structural
controllability in [6] using the notion of _zero forcing_ in graphs, which is
related to the dynamic coloring of nodes. We introduce zero forcing ideas
below and then state the main result from [6].

###### Definition 2

(_Zero forcing_) Given a graph $G=(V,E)$ whose nodes are initially colored
either _black_ or _white_. Consider the following node color changing rule:
_If $v\in V$ is colored black and has exactly one white neighbor $u$, change
the color of $u$ to black._ Zero forcing is the application of the above rule
until no further color changes are possible.

###### Definition 3

_(Force)_ A force is an application of the color changing rule due to which
the color of a white node $u$ is changed to black by some black node $v$. We
say that $v$ _forced_ $u$ and denote it by $v\rightarrow u$.

###### Definition 4

(_Input and derived sets_) For a graph $G=(V,E)$ with an initial set of black
nodes $V^{\prime}\subseteq V$, the _derived set_ of $V^{\prime}$, denoted by
$\mathcal{D}(V^{\prime})$, is the set of black nodes obtained after applying
the zero forcing rule exhaustively. The initial set of black nodes
$V^{\prime}$ is the set of _input nodes_.

We note that for a given input set $V^{\prime}$, the derived set
$\mathcal{D}(V^{\prime})$ is unique [13].

###### Definition 5

(_Zero forcing set (ZFS) and zero forcing number_) For a graph $G=(V,E)$, an
input set $V^{\prime}\subseteq V$ is a ZFS if $\mathcal{D}(V^{\prime})=V$
(i.e., all nodes are colored black after the exhaustive application of the
zero forcing rule). We denote a ZFS by $Z_{0}$. The number of nodes in the
minimum ZFS is the _zero forcing number_ of the graph and denoted by
$z_{0}(G)$.

Figure 1 illustrates the zero forcing terms defined above.

Figure 1: $V^{\prime}=\\{v_{4},v_{5}\\}$ is a ZFS of the graph along with a
sequence of forces coloring all nodes black.

A leader set for the strong structural controllability is closely related to
the notion of ZFS of the network graph. A direct consequence of Theorems IV.4,
IV.8, and Proposition IV.9 in [6] is the following result:

###### Theorem 2.1

[6] The undirected network $G=(V,E)$ is strong structurally controllable with
a leader set $V^{\prime}\subseteq V$ (as in Definition 1) if and only if
$V^{\prime}$ is a ZFS of $G$, (i.e., $\mathcal{D}(V^{\prime})=V$).

Thus, ZFS in graphs is an important idea from the network controllability
perspective and it completely characterizes the leader set for the strong
structural controllability of the network. The above results implies that the
minimum number of leaders needed for the network strong structural
controllability is same as the zero forcing number of the network graph. We
note that computing a minimum ZFS and zero forcing number are NP-hrad in
general [26]. However, there are several heuristics to compute a small-sized
ZFS, for instance, see [27, 28, 29, 30].

##  III Resilient Strong Structural Controllability (SSC) in Networks

The equivalence between ZFS and leader set for network SSC is significant. The
zero forcing process can be disrupted by some nodes/edges abnormal behaviors
or edge failures, and consequently, the network SSC can be adversely impacted.
For instance, consider the network in Figure 2 with the leader set
$V^{\prime}=\\{v_{1},v_{2}\\}$. If all nodes are normal, the ZF process
initiated by the leader set $V^{\prime}$ will eventually color all nodes in
$V$ (i.e., $\mathcal{D}(V^{\prime})=V$), and the network will be strong
structurally controllable with $V^{\prime}$. However, if $v_{5}$ behaves
abnormally in the sense that it does not force any other node, then the zero
forcing process will be hindered and $\mathcal{D}(V^{\prime})\neq V$ asserting
that the network is not strong structurally controllable. Similarly, if we
consider all nodes normal, but the edge $(v_{5},v_{6})$ is removed, the ZF
process will again be disrupted, causing $\mathcal{D}(V^{\prime})\neq V$,
which means the network is not strong structurally controllable with
$V^{\prime}$.

(a) $V^{\prime}=\\{v_{1},v_{2}\\}$

(b)

(c)

Figure 2: (a) $V^{\prime}$ is a ZFS of $G$. (b) $v_{5}$ is a misbehaving node
not forcing any other node. (c) $(v_{5},v_{6})$ is a misbehaving edge.

However, if $V^{\prime}=\\{v_{1},v_{2},v_{7}\\}$, then the network remains SSC
despite any single misbehaving node (refusing to force other nodes) or an
edge. Thus, the network SSC can be preserved even in the presence of
misbehaving nodes or edges through some redundant leader nodes selected
carefully. Our goal here is to study: _how we can guarantee resilient network
SSC in the face of some misbehaving nodes and edges that might disrupt the
zero forcing process and impact the network SSC_.

Next, we will consider three different abnormal node and edge behaviors
disrupting the zero forcing process. Then, we present leader selections
guaranteeing all nodes in the network get colored due to the zero forcing
process despite a certain number of misbehaving nodes and edges, thus
achieving the resilient network SSC. Our main result (in Section IV) shows
that resilience to one type of misbehaving nodes/edges implies resilience to
the other kinds of misbehaving nodes/edges.

###  III-A Failure Models and Resilience Problems

We consider the following three node and edge misbehaviors that can be caused
by the adversarial attack or other abnormality. All of these failures
ultimately disrupt the zero forcing process.

_1) Leak (non-forcing) nodes:_ A _leak_ is a node $v\in V$ that does not force
any other node, i.e., considering $v$ to be a leak node that is colored black
and has exactly one white neighbor, then $v$ does not force its white neighbor
(which it should in case $v$ was normal). A set of all leaks is the _leak set_
, denoted by $L\subseteq V$.

The term ‘leak node’ is adapted from [16], where such a non-forcing behavior
of nodes is introduced. Practically, a leak node can be realized in multiple
ways. For instance, if an additional node $\alpha$, which is not a part of the
original network and is colored white, becomes adjacent to exactly one node,
say $v$, in the network $G$, then $v$ is unable to force any other node in
$G$. Figure 3 illustrates this situation.

Figure 3: $v$ is a leak node not forcing any other node. Equivalently, an
outside node $\alpha$ becomes adjacent to $v$ and prevents $v$ from forcing
any node.

Now the _resilience problem_ is to have a (minimal) leader set such that all
nodes are colored at the end of the zero forcing process despite $\ell$ leak
nodes, which are unknown. For a given $\ell$, computing such a leader set is
referred to as the _$\ell$ -leaky forcing set problem_ [16, 17]. We formally
define the leaky derived set and leaky forcing set below:

###### Definition 6

(_Leaky derived set_) Given a graph $G=(V,E)$, input set $V^{\prime}$, and a
leak set $L$, then the set of black nodes obtained after applying the zero
forcing rule exhaustively while considering the leaks in $L$ is the leaky
derived set, denoted by $\mathcal{D}_{L}(V^{\prime})$.

###### Definition 7

(_$\ell$ -leaky forcing set ($\ell$-LFS)_) An input set $V^{\prime}\subseteq
V$ is an _$\ell$ -LFS_ if for _any_ leak set $L\subset V$ with $\ell$ leaks,
$\mathcal{D}_{L}(V^{\prime})=V$. In other words, starting with $V^{\prime}$,
all nodes are colored black by iteratively applying the zero forcing rule with
_any_ $\ell$ leaks. The cardinality of the minimum $\ell$-LFS is the _$\ell$
-forcing number_ of $G$, denoted by $z_{\ell}(G)$.

We note that for $\ell=0$, the $\ell$-forcing number is same as the zero
forcing number. Further, we know [16],

$z_{0}(G)\;\leq\;z_{1}(G)\;\leq\;\cdots\;\leq\;z_{|V|}(G).$ (5)

_2) Non-forcing edges:_ Here, we consider edge attacks through which an edge
cannot be used by either of its end nodes to force the other end node. We call
such an edge as a non-forcing edge. In particular, an edge $(u,v)$ is a _non-
forcing edge_ if $u$ cannot force $v$, and $v$ cannot force $v$. In this case,
the resilience problem is to find the $\ell$-edge forcing set defined below:

###### Definition 8

(_$\ell$ -Edge forcing set ($\ell$-EFS)_) For a given $G=(V,E)$ and a positive
integer $\ell$, let $E_{\ell}\subseteq E$ be an _arbitrary_ subset of at most
$\ell$ non-forcing edges (i.e., $|E_{\ell}|\leq\ell$). An input set
$V^{\prime}\subseteq V$ is an $\ell$-EFS if there is a zero forcing process
that colors all nodes in $V$ without using the edges in $E_{\ell}$ to force
nodes.

Figure 4 illustrates the non-forcing edge and $1$-EFS.
$V^{\prime}=\\{v_{1},v_{2}\\}$ is a ZFS of $G$ in Figure 4(a). If the edge
between $v_{2}$ and $v_{3}$ is non-forcing, then the derived set consists of
only three nodes $\\{v_{1},v_{2},v_{4}\\}$ at the end of the zero forcing
process. However, if the leader set is $V^{\prime}=\\{v_{1},v_{2},v_{7}\\}$,
then all nodes are colored as a result of the zero forcing process despite any
single non-forcing edge.

(a)

(b)

(c)

Figure 4: (a) $\\{v_{1},v_{2}\\}$ is a ZFS given all edges are normal. (b)
$(v_{2},v_{3})$ is a non-forcing edge. (c) $\\{v_{1},v_{2},v_{7}\\}$ is a
$1$-EFS.

_3) Removable edges:_ The third failure model we consider is the one where a
maximum of $\ell$ edges are removed from the graph to disrupt the zero forcing
process. The corresponding resilience problem is to have enough leaders to
guarantee that despite $\ell$ edge removals, the network remains strong
structurally controllable, or equivalently all nodes are colored as a result
of the zero forcing. In other words, the goal is to find a minimum size
_$\ell$ -forcing set with removable edges_ defined below:

###### Definition 9

_$\ell$ -forcing set with removable edges ($\ell$-FSR)_ For a given $G=(V,E)$
and $\ell$, consider a subgraph $G^{\prime}=(V,E^{\prime})$, where
$E^{\prime}\subseteq E$ and $|E|-|E^{\prime}|\leq\ell$. Then,
$V^{\prime}\subseteq V$ is an $\ell$-FSR of $G$ if $V^{\prime}$ is a ZFS of
_every_ such $G^{\prime}$. Note that an $\ell$-FSR must also be a ZFS of $G$.

We observe that making an edge non-forcing can be different from removing the
edge. For instance, unlike a non-forcing edge, removing an edge can sometimes
be useful, as Figure 5 illustrates. If edge $(v_{4},v_{7})$ in $G$ in Figure
5(a) is removed, then $V^{\prime}=\\{v_{1},v_{2}\\}$ is a ZFS of the resulting
graph (Figure 5(b)), thus, making the network controllable. However, if
$(v_{4},v_{7})$ is a non-forcing edge (Figure 5(c)), then $\\{v_{1},v_{2}\\}$
is no longer a ZFS of the network.

(a)

(b)

(c)

Figure 5: (a) A graph $G$. (b) $\\{v_{1},v_{2}\\}$ becomes a ZFS of $G$ after
removing the edge $(v_{4},v_{7})$. (c) If $(V_{4},v_{7})$ is a non-forcing
edge, then $\\{v_{1},v_{2}\\}$ is a not a ZFS of $G$.

Next, we present the main result showing that a leader set resilient to one
misbehavior model is also resilient to the other models.

##  IV Equivalence of Resilient Leader Selection for Various Failure Models

Here, for a given $G=(V,E)$ and $\ell$, we show the equivalence between
$\ell$-LFS, $\ell$-EFS and $\ell$-FSR. As a result, we show that a leader set
$V^{\prime}\subseteq V$ ensures resilient controllability against one
misbehavior model if and only if it extends resilience to the other two models
(discussed above). For instance, a leader set $V^{\prime}$ that is resilient
to $\ell$ non-forcing nodes must also be resilient to $\ell$ non-forcing edges
and $\ell$ removable edges simultaneously. We introduce the following terms as
in [31, 17].

###### Definition 10

Consider a graph $G=(V,E)$, input set $V^{\prime}\subseteq V$ and the
corresponding derived set $\mathcal{D}(V^{\prime})$, then we define the
following terms:

  * •

A _chronological list of forces_ is a list of forces recorded in the order in
which they are performed to construct the derived set.

  * •

A _forcing process_ $F$ is a set of forces containing a chronological ordering
of forces through which all nodes in $V$ are colored black (i.e.,
$\mathcal{D}(V^{\prime})=V$).

  * •

A _forcing chain_ is a sequence of forces $v_{i}\rightarrow v_{i+1}$, for
$i=1,2,\cdots,k-1$. We denote such a forcing sequence by $v_{1}\rightarrow
v_{2}\rightarrow\cdots\rightarrow v_{k-1}\rightarrow v_{k}$.

  * •

A _maximal forcing chain_ $v_{1}\rightarrow v_{2}\rightarrow\cdots\rightarrow
v_{k-1}\rightarrow v_{k}$ is a forcing chain such that $v_{1}\in V^{\prime}$
and $v_{k}$ does not force ant other node in $G$.

  * •

A _total forcing set_ of $V^{\prime}$, denoted by $\mathcal{F}(V^{\prime})$,
is a set of all possible forces given an input $V^{\prime}$, i.e.,
$v_{i}\rightarrow v_{j}\in\mathcal{F}(V^{\prime})$ if there is a forcing
process in $G$ containing $v_{i}\rightarrow v_{j}$.

  * •

A _total forcing set with leaks_ $L$ and input set $V^{\prime}$, denoted by
$\mathcal{F}_{L}(V^{\prime})$, is a set of all possible forces given an input
set $V^{\prime}$ and leaks $L$. In other words, if $v_{i}\rightarrow
v_{j}\in\mathcal{F}_{L}(V^{\prime})$, then $v_{i}\notin L$ and there is a
forcing process containing the force $v_{i}\rightarrow v_{j}$.

Next, consider $G=(V,E)$, a ZFS $V^{\prime}\subset V$, and a forcing process
$F$ with $V^{\prime}$. Then, we define the following notations:

$F(V^{\prime})=\\{x\rightarrow y\in F:\;y\notin V^{\prime}\\}.$ (6)

Similarly,

$F\backslash F(V^{\prime})=\\{x\rightarrow y\in F:\;y\in V^{\prime}\\}.$ (7)

We now state some results from [17] that will be used later.

###### Lemma 4.1

[17] Consider $G=(V,E)$ and a ZFS $V^{\prime}$. Let $F$ and $F^{\prime}$ be
two forcing processes. Then, $(F\backslash F(\tilde{V}))\cup
F^{\prime}(\tilde{V})$ is a forcing process with $V^{\prime}$ for any
$\tilde{V}$ obtained from $V^{\prime}$ using $F$. Here,

###### Lemma 4.2

[17] A set $V^{\prime}$ is a $1$-LFS if and only if $\forall v\in V\setminus
V^{\prime}$, there exists $x\rightarrow v\in\mathcal{F}(V^{\prime})$,
$y\rightarrow v\in\mathcal{F}(V^{\prime})$, where $y\notin x$.

###### Theorem 4.3

[17] A set $V^{\prime}$ is a $\ell$-LFS if and only if $V^{\prime}$ is an
$(\ell-1)$-LFS for every set of of $\ell-1$ leaks $L$ and $v\in V\setminus
V^{\prime}$, there exists $x\rightarrow v\in\mathcal{F}_{L}(V^{\prime})$,
$y\rightarrow v\in\mathcal{F}_{L}(V^{\prime})$, where $y\notin x$.

###  IV-A Main Result

Our main result here is to show the following:

###### Theorem 4.4

Given a graph $G=(V,E)$, input set $V^{\prime}\subseteq V$, and a positive
integer $\ell\leq|V|$, the following statements are equivalent:

  1. 1.

$V^{\prime}$ is an $\ell$-LFS.

  2. 2.

$V^{\prime}$ is an $\ell$-EFS.

  3. 3.

$V^{\prime}$ is an $\ell$-FSR.

We recall that notions of $\ell$-LFS, $\ell$-EFS, and $\ell$-FSR are explained
in Definitions 7, 8, and 9, respectively. To prove Theorem 4.4, we need some
intermediate results.

###### Lemma 4.5

If $V^{\prime}$ is a $1$-LFS of $G=(V,E)$, then for every edge $e=(u,v)\in E$,
there exists a zero forcing process $F_{e}$ that does not use $e$, i.e.,
$u\rightarrow v\notin F_{e}$ and $v\rightarrow u\notin F_{e}$.

###### Proof:

Consider a forcing process $F$ which contains $u\rightarrow v$. By Lemma 4.2,
there exists a forcing process $F^{\prime}$ such that $x\rightarrow v$, where
$x\neq u$. It suffices to show that there exists a forcing process $F_{e}$
such that $x\rightarrow v$ and $y\rightarrow u$, where $y\neq v$. If $u\in
V^{\prime}$, then $F_{e}=F^{\prime}$. So, assume $u\notin V^{\prime}$. Now,
again consider $F$ and let $\tilde{V}$ be the set of black vertices obtained
from $V^{\prime}$ such that $u\rightarrow v$ is valid given $\tilde{V}$, but
$v\notin\tilde{V}$. Note that at this point, $u$ and all of its neighbors
except $v$ are colored black through $F$. Moreover, a node can only force one
node. Thus, $u$ will not force any node in $F^{\prime}(\tilde{V})$, i.e.,
$u\rightarrow q\notin F^{\prime}(\tilde{V}),\;\forall q\in V$. Now, consider
$F_{e}=(F\backslash F(\tilde{V}))\cup F^{\prime}(\tilde{V})$. Note that
$u\rightarrow v\notin F_{e}$ and $v\rightarrow u\notin F_{e}$. By Lemma 4.1,
$F_{e}$ is a forcing process with input $V^{\prime}$, which proves the desired
claim.

###### Lemma 4.6

If $V^{\prime}$ is a $1$-EFS, then $V^{\prime}$ is a $1$-LFS

###### Proof:

Let $F$ be a forcing process with $V^{\prime}$ as input nodes. Consider $u\in
V$ to be be an arbitrary fixed leak. If $u$ is an end node of a forcing chain,
then $u$ does not force any node. So, we assume that $u\rightarrow v\in F$ for
some $v$. Since $V^{\prime}$ is $1$-EFS, there exists another forcing process
$F^{\prime}$ such that $v$ is not forced by $u$. Let $x\rightarrow v$, for
some $x\neq u$. Now, consider $F$ till the point $u\rightarrow v$ becomes
valid but $v$ is not colored black. Let $\tilde{V}$ be the set of black nodes
till this point. Note that $v\notin\tilde{V}$. Note that all nodes in
$\mathcal{N}[u]\setminus\\{v\\}$ are colored black and $v$ is the only node
that $u$ can force. Consider $F_{u}=(F\backslash F(\tilde{V}))\cup
F^{\prime}(\tilde{V})$. By Lemma 4.1, $F_{u}$ is a valid forcing process with
input nodes $V^{\prime}$ coloring all nodes black. Note that $u$ is not
forcing $v$ in $F_{u}$, and hence $u$ is not forcing any node in $F_{u}$.
Thus, $V^{\prime}$ is a $1$-LFS, which is the desired claim.

###### Lemma 4.7

Let $V^{\prime}$ be an $(\ell-1)$-EFS, $E_{\ell}$ be a set of $\ell$ non-
forcing edges, and $\mathcal{D}(V^{\prime})$ be the derived set after forcing.
If $e=(u,v)\in E_{\ell}$, then $u$ and $v$ can not be white simultaneously.
Moreover, if exactly one end node of $e$, say $u$, is black, then
$N[u]\setminus\\{v\\}\subseteq\mathcal{D}(V^{\prime})$.

###### Proof:

If both end nodes of $e\in E_{\ell}$ are white, then none of the end nodes can
force the other end node. Thus, zero forcing behavior of $V^{\prime}$ does not
change even if $e$ is not a non-forcing edge. So, if we consider
$E_{\ell}\setminus e$ as the set of non-forcing edges,
$\mathcal{D}(V^{\prime})\neq V$, implying that $V^{\prime}$ is not an
$(\ell-1)$-EFS, which is a contradiction. Similarly, let $e=(u,v)\in E_{\ell}$
be such that $u\in\mathcal{D}(V^{\prime})$ and
$v\notin\mathcal{D}(V^{\prime})$. Assume that $x\in N(u)$ is white and $x\neq
v$. Since $u$ has two white neighbors, $u$ can not force any node (including
$v$) even if $e$ is not a non-forcing edge. Again, considering
$E_{\ell}\setminus e$ as the set of non-forcing edges will give
$\mathcal{D}(V^{\prime})\neq V$. It means $V^{\prime}$ is not an
$(\ell-1)$-EFS, which is a contradiction.

###### Lemma 4.8

Let $V^{\prime}$ be an $(\ell-1)$-LFS and $L$ be a set of $\ell$ leaks. Then
$L\subseteq\mathcal{D}(V^{\prime})$, where $\mathcal{D}(V^{\prime})$ is a
derived set with leaks. Also, each $v\in L$ has at most one white neighbor.

###### Proof:

Assume $v\in L$ is white, i.e., $v\notin\mathcal{D}(V^{\prime})$. A white leak
node does not change the zero forcing behavior of the black nodes. So, we
consider $L^{\prime}=L\setminus\\{v\\}$. Since $V^{\prime}$ is an
$(\ell-1)$-LFS, so all nodes should be black for any $(\ell-1)$ leaks.
However, all nodes are not black, which is a contradiction. For the second
part, assume that there is leak node $v\in L$ that is colored black and has
two white neighbors. A black node with two white neighbors can not force any
node, so we consider $L^{\prime}=L\setminus\\{v\\}$ as a set of $(\ell-1)$
leaks. Since $V^{\prime}$ is $(\ell-1)$-LFS, it should color all nodes black
with leaks in $L^{\prime}$, which is not the case. Hence a contradiction
arises, proving the desired claim.

Next, we show the equivalence between $\ell$-LFS and $\ell$-EFS.

###### Theorem 4.9

For a given $\ell$ and $G=(V,E)$, $V^{\prime}\subseteq V$ is an $\ell$-LFS if
and only if $V^{\prime}$ is an $\ell$-EFS.

###### Proof:

($\ell$-LFS $\rightarrow\ell$-EFS) We will prove using induction on $\ell$.
From Lemma 4.5, if $V^{\prime}$ is $1$-LFS, then it is $1$-EFS. So, our
induction hypothesis is, if $V^{\prime}$ is $(\ell-1)$-LFS, then $V^{\prime}$
is $(\ell-1)$-EFS. Now, assume that $V^{\prime}$ is $\ell$-LFS. Thus,
$V^{\prime}$ must be $(\ell-1)$-LFS implying that it is also $(\ell-1)$-EFS
(by our induction hypothesis). Let $E_{\ell}$ be a set of $\ell$ non-forcing
edges. By Lemma 4.7, there is a forcing process $F$ such that for each
$e=(u,v)\in E_{\ell}$, either both end nodes $u$ and $v$ are black, or one end
node, say $u$, is black with $N[u]\setminus\\{v\\}$ also colored black. Let
$\tilde{V}$ be the set of black nodes with the forcing process $F$. Next, for
each $e\in E_{\ell}$, we consider one of its black end node as a leak, and
denote the set of leaks by $L$. There will be at most $\ell$ leaks. We observe
that a black colored leak node can be ignored and deleted without altering the
zero forcing behavior of the other black nodes. So, we consider
$G^{\prime}=G\setminus\\{L\\}$. Since $G$ is $\ell$-LFS with $V^{\prime}$,
$\tilde{V}\setminus L$ is a ZFS of $G^{\prime}$. As a result, all nodes in $V$
are colored black while considering $E_{\ell}$ as non-forcing edges, implying
$V^{\prime}$ is an $\ell$-EFS.

($\ell$-EFS $\rightarrow\ell$-LFS) Again, we will use induction on $\ell$. For
$\ell=1$, if $V^{\prime}$ is $1$-EFS, then it is $1$-LFS (by Lemma 4.6). Our
induction hypothesis is that $V^{\prime}$ is $(\ell-1)$-EFS implies it to be
$(\ell-1)$-LFS. Now assume $V^{\prime}$ to be $\ell$-EFS. It means
$V^{\prime}$ is $(\ell-1)$-EFS and hence, $(\ell-1)$-LFS (by the induction
hypothesis). Consider $L$ to be a set of $\ell$ leaks. By Lemma 4.8, these
leaks are colored black and each of them has at most one white neighbor. Next,
we consider the edge between the leak and its white neighbor as a non-forcing
edge. There will be at most $\ell$ such non-forcing edges, which we denote by
$E_{\ell}$. Since one end node (leak) of each non-forcing edge is colored
black and a leak has at most one white neighbor (which is the other end node
of the non-forcing edge), we can safely delete the non-forcing edge without
affecting the zero forcing behavior of the black node. Thus, we get
$G^{\prime}=G\setminus E_{\ell}$. Since $V^{\prime}$ is $\ell$-EFS, it means
$V^{\prime}$ is a ZFS of $G^{\prime}$. Thus, all nodes will be colored black
despite $\ell$ leaks. Hence, $V^{\prime}$ is $\ell$-LFS, which proves the
desired claim.

###### Lemma 4.10

If $V^{\prime}$ is $1$-FSR then it is $1$-EFS.

###### Proof:

By contraposition, let $V^{\prime}$ be a ZFS that is not a $1$-EFS. It means
there is an edge, say $(u,v)$, such that every forcing process must use the
edge, i.e., $(u,v)$ must be a forcing edge in any forcing process. Without the
loss of generality, we assume $u$ forces $v$. It implies that all the black
neighbors of $v$ have at least two white neighbors and $u$ has only one white
neighbor $v$. Thus, by removing edge $(u,v)$, $v$ can not be forced. Hence,
$V^{\prime}$ is not a $1$-FSR, which is the desired claim.

In the following, we show the equivalence of $\ell$-EFS and $\ell$-FSR.

###### Theorem 4.11

$V^{\prime}$ is $\ell$-EFS if and only if $V^{\prime}$ is $\ell$-FSR.

###### Proof:

($\ell$-EFS $\rightarrow$ $\ell$-FSR) We first note that if $F$ is a ZFP with
$V^{\prime}$ as a ZFS, then there are at most $n-1$ edges used in $F$. If we
remove edges not used in $F$ to get $G^{\prime}$, then $V^{\prime}$ will still
be a ZFS of $G^{\prime}$. Thus, if $V^{\prime}$ is an $\ell$-EFS, it means for
any edge set $E_{\ell}\subseteq E$, where $|E_{\ell}|\leq\ell$, there exist a
forcing process with $V^{\prime}$, say $F_{\ell}$, coloring all nodes black
without using edges in $E_{\ell}$. Since edges in $E_{\ell}$ are not used in
$F_{\ell}$, we can remove them from $G$ while maintaining $V^{\prime}$ to be a
ZFS of $G^{\prime}=(V,E\setminus E_{\ell})$, i.e., $F_{\ell}$ is a forcing
process of $G^{\prime}$ with $V^{\prime}$, implying $V^{\prime}$ is an
$\ell$-FSR of $G$.

($\ell$-FSR $\rightarrow$ $\ell$-EFS) We will prove using induction on $\ell$.
For $\ell=1$, if $V^{\prime}$ is $1$-FSR, then it is $1$-EFS by Lemma 4.10.
Thus, we make the induction hypothesis, if $V^{\prime}$ is $(\ell-1)$-FSR,
then it is $(\ell-1)$-EFS. Assuming $V^{\prime}$ to be $\ell$-FSR, we need to
show that $V^{\prime}$ is $\ell$-EFS. Let $E_{\ell}$ be a set of $\ell$ non-
forcing edges. Since $V^{\prime}$ is $(\ell-1)$-EFS (by the induction
hypothesis), we apply forces such that each edge $e=(u,v)\in E_{\ell}$
satisfies one of the two conditions (by Lemma 4.7): (i) Both end nodes of $e$
are colored black. (ii) If one node, say $u$, is black, then all nodes in
$N[u]\setminus\\{v\\}$ are also colored black. Note that the removal of edges
in both cases (i) and (ii) will not change the zero forcing behavior of the
black nodes. Thus, we remove these $\ell$ edges. Since $V^{\prime}$ is
$\ell$-FSR, it means that all nodes will be colored black at the end of the
forcing process. Thus, all nodes are colored black in spite of $\ell$ non-
forcing edges, i.e., $V^{\prime}$ is $\ell$-EFS, which is the desired result.

A direct corollary of Theorems 4.9 and 4.11 is Theorem 4.4 entailing that
resilience to one type of misbehaving nodes/edges implies resilience to other
kinds of misbehaving nodes/edges.

##  V Computation and Numerical Illustration

Computing a minimum $\ell$-LFS, and therefore, $\ell$-EFS and $\ell$-FSR, are
NP hard problems (since minimum ZFS is NP-hard). Here, first, we illustrate
the characterization of $1$-LFS provided in Theorem 4.2. Then, we present a
greedy algorithm to compute a small-sized $1$-LFS and numerically evaluate it.
A greedy algorithm for any $\ell$ can be designed using a similar approach and
utilizing the characterization in Theorem 4.3.

For a given input set $V^{\prime}$, we define $\mathcal{Q}(V^{\prime})$ to be
the set of non-input nodes, each of which can be forced by at least two
distinct nodes. More precisely,

$\begin{split}\mathcal{Q}(V^{\prime})=\\{v\in V\setminus
V^{\prime}:\;\;&\exists\;x\rightarrow v\in\mathcal{F}(V^{\prime})\text{
and}\\\ &y\rightarrow v\in\mathcal{F}(V^{\prime}),\text{ and }x\neq
y\\}.\end{split}$ (8)

By Theorem 4.2, $V^{\prime}$ is $1$-LFS if and only if
$\mathcal{Q}(V^{\prime})=V\setminus V^{\prime}$. Consider the graph in Figure
6, where $V^{\prime}=\\{v_{1},v_{2},v_{4},v_{6}\\}$ is a $1$-LFS. To verify
this, we need to show that for each $v\in V\setminus V^{\prime}$, there exist
zero forcing processes such that $v$ is forced by at least two distinct nodes.
Table I outlines multiple zero forcing processes. We observe that for each
$v\in V\setminus V^{\prime}$, there exist zero forcing processes where $v$ is
forced by two distinct forcers. For instance, $v_{3}$ is forced by $v_{2}$ and
$v_{8}$ in ZFP 1 and ZFP 2, respectively. Similarly, $v_{5}$ is forced by
$v_{9}$ and $v_{3}$ in ZFP 1 and ZFP 3, respectively.

Figure 6: $V^{\prime}=\\{v_{1},v_{2},v_{4},v_{6}\\}$ is a $1$-LFS of $G$. ZFP 1 | ZFP 2 | ZFP 3 | ZFP 4 | ZFP 5 | ZFP 6
---|---|---|---|---|---
$\begin{array}[]{c}v_{1}\rightarrow v_{8}\\\ v_{2}\rightarrow v_{3}\\\ v_{4}\rightarrow v_{7}\\\ v_{6}\rightarrow v_{9}\rightarrow v_{5}\end{array}$ | $\begin{array}[]{c}v_{1}\rightarrow v_{8}\rightarrow v_{3}\\\ v_{2}\\\ v_{4}\rightarrow v_{7}\\\ v_{6}\rightarrow v_{9}\rightarrow v_{5}\end{array}$ | $\begin{array}[]{c}v_{1}\rightarrow v_{8}\\\ v_{2}\rightarrow v_{3}\rightarrow v_{5}\\\ v_{4}\rightarrow v_{7}\\\ v_{6}\rightarrow v_{9}\end{array}$ | $\begin{array}[]{c}v_{1}\rightarrow v_{8}\\\ v_{2}\rightarrow v_{3}\rightarrow v_{5}\\\ v_{4}\\\ v_{6}\rightarrow v_{9}\rightarrow v_{7}\end{array}$ | $\begin{array}[]{c}v_{1}\\\ v_{2}\rightarrow v_{3}\rightarrow v_{8}\\\ v_{4}\rightarrow v_{7}\\\ v_{6}\rightarrow v_{9}\rightarrow v_{5}\end{array}$ | $\begin{array}[]{c}v_{1}\rightarrow v_{8}\rightarrow v_{3}\rightarrow v_{5}\\\ v_{2}\rightarrow v_{9}\\\ v_{4}\rightarrow v_{7}\\\ v_{6}\end{array}$
TABLE I: Multiple zero forcing processes (ZFP) with a given
$V^{\prime}=\\{v_{1},v_{2},v_{4},v_{6}\\}$ for the graph in Figure 6. For each
$v\in V\setminus V^{\prime}$, there are at least two ZFP such that $v$ is
forced by distinct nodes in such ZFP.

Algorithm 1 presents a _greedy_ heuristic to compute a $1$-LFS. The main idea
is to iteratively include nodes in the leader set $V^{\prime}$ to maximize the
size of $\mathcal{Q}(V^{\prime})$ (as in (8)) until
$\mathcal{Q}(V^{\prime})=V\setminus V^{\prime}$. Since every $1$-LFS is a ZFS,
we initialize $V^{\prime}$ in Algorithm 1 with a ZFS. As a result of this
greedy selection, $V^{\prime}$ might contain some redundant nodes. Lines
$9-14$ in Algorithm 1 remove such redundant nodes to reduce the size of
$1$-LFS.

---
Algorithm 1: Greedy Heuristics for 1-LFS
$\;1:\;$ given: $G=(V,E)$, $|V|=n$
$\;2:\;$ initialization: $V^{\prime}=\emptyset$
$\;3:\;$ Compute ZFS $Z_{\textbf{0}}$, and assign $V^{\prime}=Z_{\textbf{0}}$
$\;4:\;$ Compute $\mathcal{Q}(V^{\prime})$
$\;5:\;$ while $|\mathcal{Q}(V^{\prime})|<n-|Z_{\textbf{1}}|$
$\;6:$ $v^{\ast}=\operatorname*{arg\,max}\limits_{v\in
V\setminus(V^{\prime}\cup\mathcal{Q}(V^{\prime}))}{\mathcal{Q}(V^{\prime}\cup\\{v\\})}$
$\;7:$ $V^{\prime}=V^{\prime}\cup\\{v^{\ast}\\}$
$\;8:\;$ end while
\-------- removing redundancies --------
$\;9:$ $Z=V^{\prime}$
$\;10:\;$ for all $v\in Z$
$\;11:$ if $|\mathcal{Q}(V^{\prime}\setminus\\{v\\})|=n-|V^{\prime}|$ \- $1$
$\;12:$ $V^{\prime}=V^{\prime}\setminus\\{v\\}$
$\;13:$ end if
$\;14:\;$ end for
$\;15:\;$ return $V^{\prime}$

Figure 7 compares the greedy heuristic with the optimal solution for Erdös-
Rényi (ER) and Barabási-Albert (BA) random graphs with $n=20$ nodes. In ER
graphs, any two nodes are adjacent with a probability $p$. BA graphs are
obtained by attaching a new node (one at a time) to an existing graph through
$m$ edges using a preferential attachment model. The optimal solution is
computed using an exhaustive search. Also, each point on the plots averages
$15$ randomly generated instances. Figures 7(a) and (c) plot the size of
$1$-LFS as a function of $m$ in BA graphs, and as a function of $p$ in ER
graphs, respectively. Figures 7(b) and (d) plot the time taken by the greedy
and optimal solutions to compute $1$-LFS in BA and ER graphs, respectively. We
observe that greedy and optimal solutions are very close, and the difference
between the two solutions reduces as the graphs become dense. However, the
difference in time to compute greedy and optimal solutions is orders of
magnitude, even in small-sized graphs. We can design a similar greedy
heuristic to compute an $\ell$-LFS for $\ell>1$; however, the time complexity
will increase significantly with increasing $\ell$, and even the greedy
heuristic will become inefficient for higher $\ell$. Thus, more efficient
heuristics are needed to compute $\ell$-LFS for large $\ell$ values.

$2$$3$$4$$5$$6$$7$$8$$9$$10$$1$$4$$7$$10$$13$$16$$19$$m$No. of nodes in
$1$-LFSoptimalgreedy (a) BA

$2$$3$$4$$5$$6$$7$$8$$9$$10$$0$$400$$800$$1{,}200$$1{,}600$$2{,}000$time
(sec.)No. of nodes in $1$-LFSoptimalgreedy (b) BA

$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$1$$4$$7$$10$$13$$16$$19$$p$No. of nodes in
$1$-LFSoptimalgreedy (c) ER

$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0$$400$$800$$1{,}200$$1{,}600$$2{,}000$time
(sec.)No. of nodes in $1$-LFSoptimalgreedy (d) ER

Figure 7: Comparison of optimal and greedy heuristic (Algorithm 1) for the
computation of $1$-LFS in Erdös-Rényi (ER) and Barabási-Albert (BA) random
graphs.

##  VI Conclusion

We studied the problem of maintaining SSC in networks despite misbehaving
nodes and edges. We considered different models of misbehaving nodes/edges
aiming to disrupt the zero forcing process in graphs, consequently
deteriorating the network SSC. We showed that resilience to one type of
misbehaving nodes/edges is possible if and only if resilience to other threat
types is ensured. In other words, for a given leader set, if a network is
strong structurally controllable despite $k$ misbehaving nodes/edges under one
threat model, then the network remains to be strong structurally controllable
in the presence of the same number of misbehaving nodes/edges under the other
threat models. We also discussed the leader selection guaranteeing resilient
SSC. Resilience is expensive in the context of SSC because many extra leaders
are needed to nullify the effect of a small number of misbehaving nodes and
edges.

In the future, we aim to address this problem by safeguarding a subset of
nodes and edges, i.e., making them less susceptible to faults and adversarial
attacks, and then analyzing how the number of leaders for resilient SSC is
impacted in the presence of such ‘trusted’ nodes and edges. Since it would be
expensive or infeasible to make every node/edge trusted, we would need to
select them in the network carefully. Another interesting direction in this
domain requiring more exploration is designing efficient heuristics to compute
leaders for resilient SSC.

## References

  * [1] F. Pasqualetti, S. Zampieri, and F. Bullo, “Controllability metrics, limitations and algorithms for complex networks,” _IEEE Transactions on Control of Network Systems_ , vol. 1, no. 1, pp. 40–52, 2014.
  * [2] A. Clark, B. Alomair, L. Bushnell, and R. Poovendran, “Submodularity in input node selection for networked linear systems: Efficient algorithms for performance and controllability,” _IEEE Control Systems Magazine_ , vol. 37, no. 6, pp. 52–74, 2017.
  * [3] T. H. Summers, F. L. Cortesi, and J. Lygeros, “On submodularity and controllability in complex dynamical networks,” _IEEE Transactions on Control of Network Systems_ , vol. 3, no. 1, pp. 91–101, 2015.
  * [4] J. Li, X. Chen, S. Pequito, G. J. Pappas, and V. M. Preciado, “On the structural target controllability of undirected networks,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 10, pp. 4836–4843, 2020.
  * [5] J. Ruths and D. Ruths, “Control profiles of complex networks,” _Science_ , vol. 343, no. 6177, pp. 1373–1376, 2014.
  * [6] N. Monshizadeh, S. Zhang, and M. K. Camlibel, “Zero forcing sets and controllability of dynamical systems defined on graphs,” _IEEE Transactions on Automatic Control_ , vol. 59, pp. 2562–2567, 2014.
  * [7] A. Chapman and M. Mesbahi, “On strong structural controllability of networked systems: A constrained matching approach.” in _American Control Conference (ACC)_ , 2013, pp. 6126–6131.
  * [8] S. Zhang, M. Cao, and M. K. Camlibel, “Upper and lower bounds for controllable subspaces of networks of diffusively coupled agents,” _IEEE Transactions on Automatic control_ , vol. 59, pp. 745–750, 2013.
  * [9] J. Jia, H. L. Trentelman, W. Baar, and M. K. Camlibel, “Strong structural controllability of systems on colored graphs,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 10, pp. 3977–3990, 2019.
  * [10] A. Yazıcıoğlu, W. Abbas, and M. Egerstedt, “Graph distances and controllability of networks,” _IEEE Transactions on Automatic Control_ , vol. 61, no. 12, pp. 4125–4130, 2016.
  * [11] H. J. Van Waarde, M. K. Camlibel, and H. L. Trentelman, “A distance-based approach to strong target control of dynamical networks,” _IEEE Transactions on Automatic Control_ , vol. 62, pp. 6266–6277, 2017.
  * [12] J. Jia, H. J. Van Waarde, H. L. Trentelman, and M. K. Camlibel, “A unifying framework for strong structural controllability,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 1, pp. 391–398, 2020.
  * [13] AIM Minimum Rank Special Graphs Work Group, “Zero forcing sets and the minimum rank of graphs,” _Linear Algebra and its Applications_ , vol. 428, no. 7, pp. 1628–1648, 2008.
  * [14] S. S. Mousavi, M. Haeri, and M. Mesbahi, “On the structural and strong structural controllability of undirected networks,” _IEEE Transactions on Automatic Control_ , vol. 63, no. 7, pp. 2234–2241, 2017.
  * [15] M. Trefois and J.-C. Delvenne, “Zero forcing number, constrained matchings and strong structural controllability,” _Linear Algebra and its Applications_ , vol. 484, pp. 199–218, 2015.
  * [16] S. Dillman and F. Kenter, “Leaky forcing: a new variation of zero forcing,” _arXiv preprint arXiv:1910.00168_ , 2019.
  * [17] J. S. Alameda, J. Kritschgau, N. Warnberg, and M. Young, “On leaky forcing and resilience,” _Discrete Applied Mathematics_ , vol. 306, pp. 32–45, 2022\.
  * [18] M. Pirani, A. Mitra, and S. Sundaram, “A survey of graph-theoretic approaches for analyzing the resilience of networked control systems,” _arXiv preprint arXiv:2205.12498_ , 2022.
  * [19] S. S. Mousavi, M. Haeri, and M. Mesbahi, “Robust strong structural controllability of networks with respect to edge additions and deletions,” in _American Control Conference (ACC)_ , 2017, pp. 5007–5012.
  * [20] Y. Zhang and T. Zhou, “Minimal structural perturbations for controllability of a networked system: Complexities and approximations,” _International Journal of Robust and Nonlinear Control_ , vol. 29, no. 12, pp. 4191–4208, 2019\.
  * [21] W. Abbas, M. Shabbir, Y. Yazıcıoğlu, and X. Koutsoukos, “Edge augmentation with controllability constraints in directed laplacian networks,” _IEEE Control Systems Letters_ , vol. 6, pp. 1106–1111, 2021\.
  * [22] S. Pequito, G. Ramos, S. Kar, A. P. Aguiar, and J. Ramos, “The robust minimal controllability problem,” _Automatica_ , vol. 82, pp. 261–268, 2017.
  * [23] C.-L. Pu, W.-J. Pei, and A. Michaelson, “Robustness analysis of network controllability,” _Physica A: Statistical Mechanics and its Applications_ , vol. 391, no. 18, pp. 4420–4425, 2012.
  * [24] G. Ramos, D. Silvestre, and C. Silvestre, “The robust minimal controllability and observability problem,” _International Journal of Robust and Nonlinear Control_ , vol. 31, no. 10, pp. 5033–5044, 2021.
  * [25] Y. Zhang, “Controllability robustness under actuator failures: Complexities and algorithms,” _arXiv preprint arXiv:1812.07745_ , 2018.
  * [26] A. Aazami, “Hardness results and approximation algorithms for some problems on graphs,” Ph.D. dissertation, University of Waterloo, 2008.
  * [27] B. Brimkov, C. C. Fast, and I. V. Hicks, “Computational approaches for zero forcing and related problems,” _European Journal of Operational Research_ , vol. 273, no. 3, pp. 889–903, 2019.
  * [28] B. Brimkov, D. Mikesell, and I. V. Hicks, “Improved computational approaches and heuristics for zero forcing,” _INFORMS Journal on Computing_ , 2021.
  * [29] A. Agra, J. O. Cerdeira, and C. Requejo, “A computational comparison of compact MILP formulations for the zero forcing number,” _Discrete Applied Mathematics_ , vol. 269, pp. 169–183, 2019.
  * [30] W. Abbas, M. Shabbir, A. Y. Yazicioğlu, and X. Koutsoukos, “Leader selection for strong structural controllability in networks using zero forcing sets,” in _American Control Conference_ , 2022, pp. 1444–1449.
  * [31] F. Barioli, W. Barrett, S. M. Fallat, H. T. Hall, L. Hogben, B. Shader, P. Van Den Driessche, and H. Van Der Holst, “Zero forcing parameters and minimum rank problems,” _Linear Algebra and its Applications_ , vol. 433, no. 2, pp. 401–411, 2010.


# Domestic Competitive Balance and International Success: The Case of The
Football Industry††thanks: The first author acknowledges financial support
from the Spanish Agencia Estatal de Investigación (AEI) through grant
PID2020-115011GB-I00, funded by MCIN/AEI/10.13039/501100011033.

Juan D. Moreno-Ternero
Tim Pawlowski
Shlomo Weber Universidad Pablo de Olavide, Seville, Spain. Corresponding
author. e-mail<EMAIL_ADDRESS>of Tübingen, Germany. Tim Pawlowski
is also affiliated with the LEAD Graduate School and Research Network, as well
as the Interfaculty Research Institute for Sports and Physical Activity in
Tübingen.Southern Methodist University, Dallas, USA.

###### Abstract

This paper examines the interdependence of international success and
competitive balance of domestic sports competitions. More specifically, we
apply the notion of the Herfindahl-Hirschman index to examine the effect of
international rewards on distortion of competitive balance in domestic
competitions and derive conditions under which the level of domestic
competitive balance raises or falls. Our results yield interesting policy
implications for the regulation of prize schemes in international
competitions.

JEL numbers: L10, L83, Z20.

Keywords: competitive balance, domestic and international competitions,
regulation, Herfindahl-Hirschman index, UEFA Champions League.

##  1 Introduction

The rapid expansion of the sports industry has been tremendously important in
the last decades. Deloitte’s 2023 sports industry outlook states that the
growth and transformation of the sports industry is forcing organizations to
take a more sophisticated approach that makes the industry more attractive for
investors, more immersive for fans, and more supportive of athletes. In the
scientific literature, there has been an increasing interest to study
organizational aspects related to this sports industry. These range from the
fair design of competitions and prize awards, to the analysis of game
scheduling, or the allocation of gate and sportscast revenues (e.g., Peeters,
2015; Arlegi and Dimitrov, 2020; Bergantiños and Moreno-Ternero, 2020; 2021;
Csató, 2021; Dietzenbacher and Kondratev, 2023; Li et al., 2023). And a
special emphasis has been made on competitive balance, a core concept in the
sports economics literature that usually refers to the degree of parity or
equality among competing teams in the same league. However, the concept is not
limited to sports and has also been scrutinized in other parts of the
entertainment business and beyond. For instance, the effects of competition on
process innovation and product introduction have long been studied (e.g.,
Vives, 2008). In this regard, competitive balance ensures the absence of
unfair advantages for a small set of firms. Likewise, in politics, competitive
balance prevents a single political party to attain a monopoly on electoral
power (e.g., Roemer, 2001). Also, equality of opportunity in education is
linked to competitive balance (also known as leveling the playing field) for
the entire student population (e.g., Roemer, 2006).

The seminal contributions in the context of sports by Rottenberg (1956) and
Neale (1964) emphasize the positive relation between the level of balance
within a sports competition and its attractiveness for spectators. Ever since
there have been passionate discussions amongst scholars and practitioners
alike as to whether (and, if so, to which extent) competitive balance indeed
matters for spectators and fans. The empirical literature exploring this is
vast and inconclusive. For instance, Butler (1995) revealed that the
relationship between the number of spectators and competitive balance for
Major League Baseball in the US crucially depends on the chosen measure of
competitiveness. More recently, Guironnet (2023) found that French Ligue 1
attendance is positively correlated with competitive balance, whereas English
Premier League attendance is more dependent of the presence of star players.
Other recent studies, either following a behavioral economics paradigm (see
Budzinski and Pawlowski, 2017, for an overview) and/or using more granular
data for exploring in-play dynamics of entertainment utility (see seminal work
by Ely et al., 2015, and Richardson et al., 2023 for an application to
football) allow to conclude that league organizers, as well as competitors in
sports markets, should have a common incentive to preserve a certain level of
competitive balance.

Our research question is motivated by the regulatory practice in professional
sports. For instance, North American professional sports have long been
implementing salary caps or draft systems, in which weaker clubs have priority
(at least a higher probability) to pick draftees each season to maintain or
even increase competitive balance. Likewise, the allocation of revenues raised
from broadcasting rights, the most important source of revenue for
professional sports, is certainly driven (at least, partially) by that goal
too (e.g., Bergantiños and Moreno-Ternero, 2023a). But sometimes competitions
overlap and the revenue allocations might intertwine each other. In
particular, when participating clubs do not fully overlap in those
competitions (such as in the case of the UEFA Champions League).111UEFA stands
for the Union of European Football Associations, the governing body of
football in Europe. In this paper, we are concerned with the effect that
revenue allocation schemes at international competition will have on domestic
competition.

While one could safely argue that competitive balance is one of the key issues
that European football has to address in order to ensure its long-term
prosperity,222In fact, UEFA President Aleksander Ceferin told the general
assembly of the European Club Association (ECA) in 2017: ”Let’s put our cards
on the table and be honest with ourselves: the biggest challenge over the next
few years will be ‘competitive balance’.” https://www.reuters.com/article/us-
soccer-europe-clubs/uefa-president-says-rich-poor-divide-is-key-issue-in-
european-football-idUSKCN1BF2CX its quantification is not an easy task. The
difficulties are mainly associated with its multi-dimensional nature.
Consequently, there are multiple approaches to measure competitive balance. As
Zimbalist (2002, p. 112) puts it: “there are almost as many ways to measure
competitive balance as there are to quantify money supply”. As we consider
both leagues and teams of various strengths and put an emphasis on the budget
distributions, there are two indices that fit our approach: The Concentration
Ratio (CR), the fraction of industry size held by the larger firms (Hall and
Tideman, 1967; Besanko et al., 2017), and the Herfindahl-Hirschman Index
(HHI), the sum of the quadratic shares (Herfindahl, 1950; Hirschman,
1945).333Bossert et al. (2022) have recently studied a larger family of
indices encompassing these two. See also Martinez and Moreno-Ternero (2022)
for alternative families of indices in a different setting. We opt for the
latter because it is superior on analytical grounds (including the fact that
it weights firms according to their size) and there is a long tradition of use
in industrial organization, since the U.S. Horizontal Merger Guidelines were
unveiled in 1982. Therein, the U.S. Department of Justice divides the spectrum
of market concentration as measured by the HHI into three regions that can be
broadly characterized as unconcentrated (HHI below 1000), moderately
concentrated (HHI between 1000 and 1800) and highly concentrated (HHI above
1800).

The importance of HHI, and, in particular, its link with the societal welfare
has been studied extensively in the industrial organization literature (e.g.,
Dansby and Willig, 1979; Farrell and Shapiro, 1990). More recently, it also
has become a popular measure in sports economics (e.g., Owen et al.,
2007).444Depken (1999) originally applied the same metric to estimate
inequality in the baseball league. In our paper, we apply the HHI to examine
the effect of international rewards on distortion of competitive balance in
domestic competitions and derive conditions under which the level of domestic
competitive balance raises or falls. We focus on the case of football, the
most popular sport (for which sources estimate over 3.5 billion fans
worldwide).555https://worldpopulationreview.com/country-rankings/most-popular-
sport-by-country Our results derive interesting policy implications for the
regulation of prize schemes in international competitions represented in our
setting by the UEFA Champions League (whose structure is described in the
following section).

The rest of the paper is organized as follows. In Section 2, we describe the
structure and brief history of the UEFA Champions League that serves as the
platform for our analysis. In Section 3, we present the benchmark model, which
examines the competitive balance implications of award schemes that share the
prize endowment of the international competition $E$ equally among the $k$-top
clubs in the domestic competition. We show that there is a threshold value of
the number of award recipients, $k^{*}(E)$, such that awarding to $k<k^{*}(E)$
clubs reduces the level of competitive balance (relative to the pre-award
stage) while awarding it to $k>k^{*}(E)$ clubs increases it. In particular,
the award to only one top club hurts competitive balance the most, while
sharing it equally among all clubs (in the domestic competition) improves the
most. In Section 4, we focus our analysis on the threshold value $k^{*}(E)$
and show that this value is weakly increasing in the size of the prize $E$.
However, for a given $k$, competitive balance follows an inverse U-shape with
respect to $E$, i.e., it is increasing below some threshold value and
declining above that threshold. We also provide the support of the equal-share
scheme among the $k$-top schemes by showing that it is optimal in terms of
competitive balance among all other $k$-top schemes. In Sections 5 and 6, we
offer an illustration and discussion of our results, respectively.

##  2 The UEFA Champions League

In 1955, the so-called European Champion Clubs’ Cup was launched. It was a
yearly competition played by the national league football champions of the
strongest UEFA national associations.666More precisely, sixteen teams played
the first edition: Milan (Italy), AGF Aarhus (Denmark), Anderlecht (Belgium),
Djurgrden (Sweden), Gwardia Warszawa (Poland), Hibernian (Scotland), Partizan
(Yugoslavia), PSV Eindhoven (Netherlands), Rapid Wien (Austria), Real Madrid
(Spain), Rot-Weiss Essen (West Germany), Saarbrucken (Saar), Servette
(Switzerland), Sporting CP (Portugal), Stade de Reims (France), and Vrs Lobog
(Hungary). The English champion, Chelsea, decided not to play, and there was
no English team in that first edition. Thus, it was intended for football
champions, but the intention was also for all UEFA national associations to
participate, not only the “strongest.” The competition took on its current
name, the UEFA Champions League, in 1992, adding a group stage to the
competition and allowing multiple entrants from certain countries. In its
present format, it begins with four knockout qualifying rounds and a play-off
round. The surviving clubs enter the group stage, joining clubs qualified in
advance. Overall, 32 clubs are drawn into eight groups of four clubs and play
each other in a double round-robin system. The eight group winners and eight
runners-up proceed to the knockout phase that culminates with the final match.
The 32 teams participating in the group stage during the last editions have
been the title holders (of both UEFA Champions League and Europa League), the
10 champions from the ten strongest domestic competitions, the 6 runners-up
from the six strongest domestic competitions, the 4 third-placed and the 4
fourth-placed teams from the four strongest domestic competitions, and the
winners of a six-round qualifying tournament involving winners and, possibly,
runner-ups from the remaining weaker domestic competitions. Thus, some
domestic competitions are not represented in the group stage, whereas others
are with a number of clubs ranging from 1 to 4 (occasionally 5, for one or two
at most).777From season 2024/2025, 36 (instead of 32) qualified clubs will be
organized in a single league which follows an unbalanced schedule, i.e., each
club plays 8 matches. The top 8 clubs in this league will directly qualify for
the round of 16. The remaining 8 spots for the knockout phase will be decided
after two-legged play-offs between clubs ranked 9 to 24. This change in the
format will increase the number of games played from 125 to 225, which will
probably make the competition more lucrative for UEFA and the participating
teams.

Since 1992, Spanish clubs have accumulated the highest number of victories (19
wins), followed by England (15 wins), Italy (12 wins) and Germany (8 wins).
England has the largest number of winning clubs, with 6 clubs having won the
title. Overall, a total of 23 clubs have won the title (only 6 from 2010). The
competition has thus been dominated by clubs from just four out of UEFA’s 54
member nations, and this dominance is typically associated with the size of
football markets in these countries, that allow the big clubs to buy up the
best players.

Participation in this competition can represent a significant financial boost
for clubs. In particular, performances in the tournament, such as advancement
from round to round, largely increase club’s payouts. In the 2021/2022 season,
for instance, the winning club (Real Madrid) collected €83.2 million in
performance-based prize money (including an additional €4.5 million for
winning the UEFA Super Cup in August 2022). While 55 percent of the total
prize is distributed according to such performance pay, the rest is
distributed among the 32 participants via coefficient payout (30 percent) and
broadcast market payout (15 percent).888The coefficient payout is the outcome
of an algorithm that ranks European performance over a 10-year period.

As only a few clubs from each domestic competition participate in the UEFA
Champions League each year, the scale of such rewards could possibly distort
domestic competitions. By treating the substantial increase in payouts to the
participating clubs in 1999/2000 as a natural experiment, Pawlowski et al.
(2010) provide some empirical evidence for this claim. In this paper, we
theoretically explore the way in which domestic competitions interact with
international competitions like the UEFA Champions League. Our focus is on the
role that prizes at the international level have on the level of competitive
balance in the corresponding domestic competitions, with a special emphasis on
the implications that our results provide on the regulatory policies for prize
schemes in international competitions.

In our (theoretical) analysis, we order clubs by their budget size, assuming
that better teams have larger budgets. We also assume that participation and
prizes in international competitions are also determined by budget size. We
acknowledge that this is not always realistic as, sometimes, small-budget
clubs participate in international competitions (and receive prizes) and some
larger-budget clubs may fail to compete internationally. Nevertheless, in
reality, larger-budget clubs indeed tend to perform better and compete
internationally most of the times.999Kuper and Szymanski (2018) show that wage
spending is highly correlated with league position over time. Nevertheless, it
is also argued that market size highly correlates with regulatory changes in
the 1990s (e.g., Simmons, 1997; Frick, 2009).

##  3 The benchmark analysis

Consider a set of domestic (national) league competitions, one for each
country, i.e., Bundesliga in Germany, La Liga in Spain, Premier League in
England, Serie A in Italy etc. Each competition involves $n\geq 2$ clubs. Let
$N=\\{1,\ldots,n\\}$. For each $i\in N$, let $x_{i}$ denote the budget of club
$i$. Let $X=(x_{i})_{i\in N}=(x_{1},\ldots x_{n})$ and
$x=\sum_{i=1}^{n}x_{i}$. For ease of exposition, assume $x_{1}\geq
x_{2}\geq\ldots\geq x_{n}$. We assume that clubs are utility maximizers (e.g.,
Sloane, 1971), i.e., they invest their budgets in order to maximize sporting
success. As such, budgets determine club’s strength.101010We acknowledge that,
empirically, club investments are correlated with expected payoffs. But we
dismiss this aspect from our stylized theoretical analysis.

We explore the level of competitive balance of competition $N$ by focussing on
the budget distribution, via the so-called Herfindahl-Hirschman Index. The
index increases with decreasing levels of competitive balance.
Formally,111111To ease our analysis, we ignore the $10000$ term that is
typically considered multiplying the expression.

$H(X)=\sum_{i\in N}\left(\frac{x_{i}}{x}\right)^{2}=\frac{1}{x^{2}}\sum_{i\in
N}x_{i}^{2}.$

We also assume that there exists an international competition with a prize
structure granting an overall endowment $E$ to the domestic competition. Let
$R$ be a sharing rule allocating $E$ among clubs in $N$ which yields the
vector of shares $(R_{1}(E),\ldots,R_{n}(E))$ to each club with
$\sum_{j=1}^{n}R_{j}(E)=E$.

We want to explore the implications of sharing rules into competitive balance
of domestic competitions. To do so, let $x_{j}^{R,E}=x_{j}+R_{j}(E)$, for each
$j=1,\dots n$. The aim is to compare the value of the competitive balance
index introduced above for distributions $X$ and $X^{R,E}$.

The first family of sharing rules we consider are the rules $R^{k}$ in which
the $k$-top clubs in each domestic competition are (equally) rewarded, while
the others receive zero. That is, rule $R^{k}$ is such that
$R_{j}^{k}(E)=\frac{E}{k}$ for each $j\in\\{1,\ldots,k\\}$, and $0$ otherwise.
To simplify the notation we denote the resulting distribution by $X^{k,E}$.

To begin, we consider the rule $R^{1}$ that allocates the endowment to a
unique club in the domestic competition. That is, $R^{1}$ is a top
performance-based prize structure of the international competition. Formally,
$R^{1}$ is such that $R_{1}^{1}(E)=E$, $R_{j}^{1}(E)=0$ for each $j>1$. We
then obtain the following result.

###### Proposition 1

The top performance-based prize structure of the international competition
$R^{1}$ hurts competitive balance at domestic competitions. That is,
$H(X^{1,E})\geq H(X)$.

Proof. As mentioned above, in the proofs that follow we shall ignore the
constant in the definition of the HHI for being innocuous in our analysis.
Then,

$H(X^{1,E})=\frac{(x_{1}+E)^{2}+\sum_{i\in
N\setminus\\{1\\}}x_{i}^{2}}{(x+E)^{2}}.$

Thus, $H(X^{1,E})\geq H(X)$ if and only if

$\frac{(x_{1}+E)^{2}+\sum_{i\in
N\setminus\\{1\\}}x_{i}^{2}}{(x+E)^{2}}\geq\frac{\sum_{i\in
N}x_{i}^{2}}{x^{2}}.$

That is,

$x^{2}\left((x_{1}+E)^{2}+\sum_{i\in
N\setminus\\{1\\}}x_{i}^{2}\right)\geq(x+E)^{2}\sum_{i\in N}x_{i}^{2}.$

Or, equivalently,

$(2x_{1}+E)x^{2}\geq(2x+E)\sum_{i\in N}x_{i}^{2},$

which is true as $x_{1}\geq x_{i}$, for each $i\in N$.

We now consider an alternative rule in which we move away from top club-based
to domestic competition-based performance-pay. That is, instead of just
rewarding the top club, an equal-sharing of the international competition
prize is imposed among all clubs in the domestic competition. Formally, assume
that rule $R^{n}$ is such that $R_{i}^{n}(E)=\frac{E}{n}$ for each $i\in N$.

###### Proposition 2

The equal-sharing structure of the international competition prize among clubs
in the domestic competition $R^{n}$ improves competitive balance at domestic
competitions. That is, $H(X^{n,E})\leq H(X)$.

Proof. We have

$H(X^{n,E})=\frac{\sum_{i\in N}(x_{i}+\frac{E}{n})^{2}}{(x+E)^{2}}.$

Then, $H(X^{n,E})\leq H(X)$ if and only if

$\frac{\sum_{i\in
N}x_{i}^{2}}{(x+E)^{2}}+\frac{E^{2}}{n(x+E)^{2}}+\frac{2EX}{n(x+E)^{2}}\leq\frac{\sum_{i\in
N}x_{i}^{2}}{x^{2}}.$

That is,

$\sum_{i\in
N}x_{i}^{2}+\frac{E^{2}}{n}+\frac{2Ex}{n}\leq\left(\frac{x+E}{x}\right)^{2}\sum_{i\in
N}x_{i}^{2}.$

Or, equivalently,

$\frac{E^{2}}{n}+\frac{2Ex}{n}\leq\frac{E}{x^{2}}\left(R+2x\right)\sum_{i\in
N}x_{i}^{2},$

which translates into

$x^{2}\leq n\sum_{i\in N}x_{i}^{2}.$

As $\varphi(\frac{\sum_{i}x_{i}}{n})\leq\frac{\sum_{i}\varphi(x_{i})}{n}$, for
each convex function $\varphi$ (this is the so-called Jensen inequality), by
setting $\varphi(y)=y^{2}$, we confirm the validity of the last inequality.

After examining the two extreme cases, where $k=1$ and $k=n$, we turn to the
intermediate rules $R^{k}$ in which the $k$-top clubs in each domestic
competition are (equally) rewarded, with $1\leq k\leq n$, while the others
receive zero. We first establish that while the effect of awards on
competitive balance is not uniform, there are necessary and sufficient
conditions that identify when competitive balance is reduced or increased.

###### Lemma 1

The $k$-top performance structure of the international competition prize among
clubs in the domestic competition $R^{k}$ improves competitive balance at
domestic competitions for some configurations. More precisely, $H(X^{k,E})\leq
H(X)$ if and only if the following condition holds:

$x^{2}\left(E+2\sum_{i=1}^{k}x_{i}\right)\leq k\left(E+2x\right)\sum_{i\in
N}x_{i}^{2}.$

Proof. We have

$H(X^{k,E})=\frac{\left(\sum_{i=1}^{k}(x_{i}+\frac{E}{k})^{2}\right)+\sum_{i=k+1}^{n}x_{i}^{2}}{(x+E)^{2}}=\frac{\sum_{i=1}^{n}x_{i}^{2}}{(x+E)^{2}}+\frac{E^{2}}{k(x+E)^{2}}+\frac{2E\sum_{i=1}^{k}x_{i}}{k(x+E)^{2}}.$

Thus, $H(X^{k,E})\leq H(X)$ if and only if

$\frac{\sum_{i\in
N}x_{i}^{2}}{(x+E)^{2}}+\frac{E^{2}}{k(x+E)^{2}}+\frac{2E\sum_{i=1}^{k}x_{i}}{k(x+E)^{2}}\leq\frac{\sum_{i\in
N}x_{i}^{2}}{x^{2}}.$

That is,

$\sum_{i\in
N}x_{i}^{2}+\frac{E^{2}}{k}+\frac{2E\sum_{i=1}^{k}x_{i}}{k}\leq\left(\frac{x+E}{x}\right)^{2}\sum_{i\in
N}x_{i}^{2},$

Or, equivalently,

$\frac{E}{k}\left(E+2\sum_{i=1}^{k}x_{i}\right)\leq\frac{E}{x^{2}}\left(E+2x\right)\sum_{i\in
N}x_{i}^{2},$

which translates into

$x^{2}\left(E+2\sum_{i=1}^{k}x_{i}\right)\leq k\left(E+2x\right)\sum_{i\in
N}x_{i}^{2},$

as stated.

As shown in Propositions 1 and 2, the inequality in the statement of Lemma 1
holds for $k=n$, whereas it reverses for $k=1$. The next lemma helps
establishing what happens in the intermediate cases. Recall that:

$H(X^{k,E})=\frac{\sum_{i=1}^{k}(x_{i}+\frac{E}{k})^{2}+\sum_{i=k+1}^{n}x_{i}^{2}}{(x+E)^{2}}.$

###### Lemma 2

For each $X$ and each $E$, the function $H(X^{k,E})$ is decreasing in $k$.

Proof. Let us show that for each $k$, $H(X^{k-1,E})>H(X^{k,E})$. By ignoring
common terms and factors on both sides, it suffices to show that

$\sum_{i=1}^{k-1}(x_{i}+\frac{E}{k-1})^{2}+x_{k}^{2}>\sum_{i=1}^{k}(x_{i}+\frac{E}{k})^{2},$

or

$\frac{2E\sum_{i=1}^{k-1}x_{i}}{k-1}+\frac{E^{2}}{k-1}>\frac{2E\sum_{i=1}^{k}x_{i}}{k}+\frac{E^{2}}{k}.$

The latter inequality holds in our framework as the average budget of the top
$k-1$ clubs exceeds that of the top $k$ clubs.

To summarize, Lemma 2 implies that $H(X^{k,E})$ is decreasing in $k$.
Propositions 1 and 2 show that $H(X^{n,E})\leq H(X)\leq H(X^{1,E})$. Thus, it
follows that there exists $k^{\ast}(X,E)\in\\{1,\ldots,n\\}$ such that
$H(X^{n,E})\leq H(X^{k^{\ast}+1,E})\leq H(X)\leq H(X^{k^{\ast},E})\leq
H(X^{1,E})$. In other words, competitive balance of the status-quo budget
distribution (with no prize allocation) single crosses the sequence of
resulting budget distributions after implementing the $R^{k}$ rules.121212The
so-called single-crossing property has some important implications, well
established in the public economics literature, referring to the progressivity
comparisons of schedules as well as the identification of the majority voting
equilibrium (e.g., Jakobsson, 1976; Hemming and Keen, 1983; Gans and Smart
1996; Moreno-Ternero, 2011; Bergantiños and Moreno-Ternero, 2023b).
Equivalently, for each status-quo budget distribution $X$ there exists a
threshold $k^{\ast}(X,E)$, such that
$H(X^{1,E})>H(X^{2,E})>...>H(X^{k^{\ast}-1},E)>H(X)>H(X^{k^{\ast},E})>...>H(X^{n,E})$.
In other words, we have the following:

###### Proposition 3

For each budget distribution $X$ there exists a threshold
$k^{\ast}(X,E)\in\\{1,\ldots n\\}$, such that

  * •

For each $k=1,\ldots,k^{\ast}(X,E)-1$, the $k$-top performance structure of
the international competition prize among clubs in the domestic competition
$R^{k}$ hurts competitive balance at domestic competitions (with respect to
the original distribution $X$).

  * •

For each $k=k^{\ast}(X,E),\ldots,n$, the $k$-top performance structure of the
international competition prize among clubs in the domestic competition
$R^{k}$ improves competitive balance at domestic competitions (with respect to
the original distribution $X$).

As stated in Proposition 3, there will be a threshold for $k$ (depending on
the distribution $X$ and prize $E$) separating the $k$-top rules that hurt
competitive balance at domestic competitions from those that improve it. The
$k$-top rules are fully ranked according to that feature, ranging from the
$1$-top rule (that hurts competitive balance for all distribution $X$) to the
$n$-top (equal-sharing) rule (that always improves competitive balance for all
distribution $X$).

##  4 Extension and further analysis

An interesting corollary from the above discussion is that competitive balance
is reduced much more in “weak leagues”, i.e., leagues for which only one club
participates in the international competition.131313As mentioned in Section 2,
some leagues might end up having no participant whatsoever in the group stage
of the UEFA Champions League, but all leagues have at least one slot in the
qualifying tournament. For those leagues, $R^{1}$ is the only available
$k$-top rule. And we know from Proposition 1 that such a rule always hurts
competitive balance, whereas other $k$-top rules might not. As stated in Lemma
2, the more clubs of a league benefit from the prize of the international
competition, the better competitive balance in the domestic competition is. In
other words:

###### Corollary 1

Competitive balance in strong domestic leagues with more spots in the
international competition is not hurt as much as in weak leagues with just one
spot in the international competition.

We now generalize $k$-top performance schemes to allow for uneven rewards
among top clubs. Formally, let $k\in\\{1,\ldots,n\\}$ and $a\in\mathbb{R}^{k}$
be such that $a_{1}\geq a_{2}\geq\ldots\geq a_{k}>0$, $a_{1}>\frac{1}{k}$, and
$\sum_{i=1}^{k}a_{i}=1$. Then, the rule $R^{a,k}$ is such that
$R^{a,k}_{i}(E)=a_{i}E$ for each $i\in\\{1,\ldots,k\\}$ and $0$ otherwise. Our
next result states that the even $k$-top performance scheme outperforms (in
terms of competitive balance for the domestic competition) all the uneven
$k$-top performance schemes.

###### Proposition 4

The even $k$-top performance structure of the international competition prize
among clubs in the domestic competition $R^{k}$ improves competitive balance
at domestic competitions more than any other uneven $k$-top performance
structure.

Proof. For each $i\in N$, let $x^{k}_{i}=x_{i}+\frac{E}{k}$ and
$x^{a,k}_{i}=x_{i}+a_{i}E$ denote the budget of club $i$, after $R^{k}$ and
$R^{a,k}$ are implemented. Then,

$H(X^{k})=\frac{\sum_{i=1}^{k}(x_{i}+\frac{E}{k})^{2}+\sum_{i=k+1}^{n}x_{i}^{2}}{(x+E)^{2}}=\frac{\sum_{i=1}^{k}x_{i}^{2}}{(x+E)^{2}}+\frac{E^{2}}{k(x+E)^{2}}+\frac{2E\sum_{i=1}^{k}x_{i}}{k(x+E)^{2}}+\frac{\sum_{i=k+1}^{n}x_{i}^{2}}{(x+E)^{2}},$

and

$H(X^{a,k})=\frac{\sum_{i=1}^{k}(x_{i}+a_{i}E)^{2}+\sum_{i=k+1}^{n}x_{i}^{2}}{(x+E)^{2}}=\frac{\sum_{i=1}^{k}x_{i}^{2}}{(x+E)^{2}}+\frac{E^{2}\sum_{i=1}^{k}a^{2}_{i}}{(x+E)^{2}}+\frac{2E\sum_{i=1}^{k}a_{i}x_{i}}{(x+E)^{2}}+\frac{\sum_{i=k+1}^{n}x_{i}^{2}}{(x+E)^{2}},$

Thus, $H(X^{k})\leq H(X^{a,k})$ if and only if

$\frac{\sum_{i=1}^{k}x_{i}^{2}}{(x+E)^{2}}+\frac{E^{2}}{k(x+E)^{2}}+\frac{2E\sum_{i=1}^{k}x_{i}}{k(x+E)^{2}}\leq\frac{\sum_{i=1}^{k}x_{i}^{2}}{(x+E)^{2}}+\frac{E^{2}\sum_{i=1}^{k}a^{2}_{i}}{(x+E)^{2}}+\frac{2E\sum_{i=1}^{k}a_{i}x_{i}}{(x+E)^{2}}.$

That is,

$\frac{E^{2}}{k}+\frac{2E\sum_{i=1}^{k}x_{i}}{k}\leq
E^{2}\sum_{i=1}^{k}a^{2}_{i}+2E\sum_{i=1}^{k}a_{i}x_{i},$

Or, equivalently,

$\frac{E}{k}\left(E+2\sum_{i=1}^{k}x_{i}\right)\leq
E\left(E\sum_{i=1}^{k}a^{2}_{i}+2\sum_{i=1}^{k}a_{i}x_{i}\right),$

which translates into

$E\left(\sum_{i=1}^{k}a^{2}_{i}-\frac{1}{k}\right)\geq
2\left(\sum_{i=1}^{k}\left(\frac{1}{k}-a_{i}\right)x_{i}\right).$

Note that the left hand side is non-negative because of the Jensen
inequality.141414If $\varphi$ is convex then
$\varphi(\frac{\sum_{i}a_{i}}{k})\leq\frac{\sum_{i}\varphi(a_{i})}{k}$. Thus,
for $\varphi(x)=x^{2}$, we have
$(\frac{1}{k})^{2}=(\frac{\sum_{i}a_{i}}{k})^{2}\leq\frac{\sum_{i}a^{2}_{i}}{k}$,
i.e., $\sum_{i=1}^{k}a^{2}_{i}\geq\frac{1}{k}$. And the right-hand side is
actually non-positive because $x_{1}\geq x_{2}\geq\ldots\geq x_{k}$,
$a_{1}\geq a_{2}\geq\ldots\geq a_{k}>0$, $a_{1}>\frac{1}{k}$, and
$\sum_{i=1}^{k}a_{i}=1$. More precisely, let $\varepsilon=a_{1}-\frac{1}{k}>0$
and, for each $i=2,\ldots k$, let $\varepsilon_{i}=\frac{1}{k}-a_{i}>0$. Note
that $0<\varepsilon_{1}\leq\varepsilon_{2}\leq\ldots\leq\varepsilon_{k}$, and
$\sum_{i=2}^{k}\varepsilon_{i}=\varepsilon$. Then,
$\sum_{i=1}^{k}\left(\frac{1}{k}-a_{i}\right)x_{i}=-\varepsilon
x_{1}+\sum_{i=2}^{k}\varepsilon_{i}x_{i}=\sum_{i=2}^{k}\varepsilon_{i}(x_{i}-x_{1})\leq
0$.

We complete this section upon exploring the impact of the value of the award
$E$ on the level of competitive balance, as well as the threshold reflecting
the single-crossing property of $k$-top schemes’ competitive balance. We first
claim that for every budget distribution $X$ and the number of clubs $k$
receiving the award, competitive balance as a function of $E$ is single-
peaked. That is, there is a threshold $E^{\ast}(X,k)$ that depends on $X$ and
$k$ such that the level of competitive balance increases for $E<E^{\ast}(X,k)$
and declines for $E>E^{\ast}(X,k)$.

###### Proposition 5

Denote

$E^{\ast}(X,k)=\max\left\\{0,\frac{k\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k}x_{i}}{\sum_{i=k+1}^{n}x_{i}}\right\\}.$

Then, $H(X^{k,E})$ is decreasing for all $0\leq E\leq E^{\ast}(X,k)$ and
increasing for all $E\geq E^{\ast}(X,k)$.

Proof. Recall that

$H(X^{k,E})=\frac{\left(\sum_{i=1}^{k}(x_{i}+\frac{E}{k})^{2}\right)+\sum_{i=k+1}^{n}x_{i}^{2}}{(x+E)^{2}}=\frac{\sum_{i=1}^{n}x_{i}^{2}}{(x+E)^{2}}+\frac{E^{2}}{k(x+E)^{2}}+\frac{2E\sum_{i=1}^{k}x_{i}}{k(x+E)^{2}}.$

Taking derivatives of this expression with respect to $E$, we obtain

$\frac{2}{k(x+E)^{3}}\left((x+E)(\sum_{i=1}^{k}x_{i}+E)-k\sum_{i=1}^{n}x_{i}^{2}-E^{2}-2E\sum_{i=1}^{k}x_{i}\right).$

Or, equivalently,

$\frac{2}{k(x+E)^{3}}\left(E\sum_{i=k+1}^{n}x_{i}-k\sum_{i=1}^{n}x_{i}^{2}+x\sum_{i=1}^{k}x_{i}\right),$

from where it follows that $H(X^{k,E})$ is increasing with respect to $E$ if
and only if

$E\geq\frac{k\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k}x_{i}}{\sum_{i=k+1}^{n}x_{i}}.$

Note that the numerator of the last expression
$k\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k}x_{i}$ could be either negative or
positive for various $k$. Indeed, for $k=n$,
$n\sum_{i=1}^{n}x_{i}^{2}\geq(\sum_{i=1}^{n}x_{i})^{2}=x^{2}$. Whereas for
$k=1$, we have
$\sum_{i=1}^{n}x_{i}^{2}-xx_{1}=\sum_{i=1}^{n}[x_{i}^{2}-x_{1}x_{i}]\leq 0.$
Thus, by setting
$E^{\ast}(X,k)=\max\\{0,\frac{k\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k}x_{i}}{\sum_{i=k+1}^{n}x_{i}}\\}$,
we conclude the proof.

Finally, how does $E$ impact $k^{\ast}(X,E)$? According to Lemma 1,
$H(X^{k,E})\leq H(X)$ if and only

$x^{2}\left(E+2\sum_{i=1}^{k}x_{i}\right)\leq k\left(E+2x\right)\sum_{i\in
N}x_{i}^{2}.$

Equivalently,

$\left(k\sum_{i=1}^{n}x_{i}^{2}-x^{2}\right)E\geq
2x\left(x\sum_{i=1}^{k}x_{i}-k\sum_{i=1}^{n}x_{i}^{2}\right).$

If $k\sum_{i=1}^{n}x_{i}^{2}\geq x^{2}$, then the condition above trivially
holds for all $E$ (the left-hand side would be non-negative whereas the right-
hand side would be non-positive).

If $k\sum_{i=1}^{n}x_{i}^{2}\leq x\sum_{i=1}^{k}x_{i}$, then the condition
above trivially does not hold for any $E$ (the left-hand side would be non-
positive whereas the right-hand side would be non-negative).

If $x\sum_{i=1}^{k}x_{i}<k\sum_{i=1}^{n}x_{i}^{2}<x^{2}$, then the condition
is equivalent to write the following:

$E\leq\frac{2x\left(k\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k}x_{i}\right)}{x^{2}-k\sum_{i=1}^{n}x_{i}^{2}}.$

We now explore the above upper bound for $E$, starting with its monotonicity
with respect to $k$.

###### Lemma 3

Assume $x\sum_{i=1}^{k}x_{i}<k\sum_{i=1}^{n}x_{i}^{2}<x^{2}$ and denote

$\hat{E}(k,X)=\frac{2x\left(k\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k}x_{i}\right)}{x^{2}-k\sum_{i=1}^{n}x_{i}^{2}}.$

Then, for each $X$ and each $E$, the function $\hat{E}(k,X)$ is increasing in
$k$.

Proof. Assume $x\sum_{i=1}^{k}x_{i}<k\sum_{i=1}^{n}x_{i}^{2}<x^{2}$. Let us
show that for each $k$, $\hat{E}(k+1,X)\geq\hat{E}(k,X)$. That is,

$\frac{2x\left((k+1)\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k+1}x_{i}\right)}{x^{2}-(k+1)\sum_{i=1}^{n}x_{i}^{2}}\geq\frac{2x\left(k\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k}x_{i}\right)}{x^{2}-k\sum_{i=1}^{n}x_{i}^{2}}.$

Equivalently,

$\left(x^{2}-k\sum_{i=1}^{n}x_{i}^{2}\right)\left((k+1)\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k+1}x_{i}\right)\geq\left(x^{2}-(k+1)\sum_{i=1}^{n}x_{i}^{2}\right)\left(k\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k}x_{i}\right).$

By ignoring common terms and factors on both sides, it suffices to show that

$\left(x^{2}-k\sum_{i=1}^{n}x_{i}^{2}\right)\left(\sum_{i=1}^{n}x_{i}^{2}-xx_{k+1}\right)\geq-\left(\sum_{i=1}^{n}x_{i}^{2}\right)\left(k\sum_{i=1}^{n}x_{i}^{2}-x\sum_{i=1}^{k}x_{i}\right),$

As $x^{2}\geq k\sum_{i=1}^{n}x_{i}^{2}$ and $k\sum_{i=1}^{n}x_{i}^{2}\geq
x\sum_{i=1}^{k}x_{i}$ due to the premises of the lemma, it suffices to show
that

$\sum_{i=1}^{n}x_{i}^{2}\geq xx_{k+1}=x_{k+1}\sum_{i=1}^{n}x_{i}.$

Now, the premises of the lemma also imply that $\sum_{i=1}^{n}x_{i}^{2}\geq
x\sum_{i=1}^{k}\frac{x_{i}}{k}$. As the average budget of the top $k$ clubs
exceeds that of the $k+1$ club (i.e., $\sum_{i=1}^{k}\frac{x_{i}}{k}\geq
x_{k+1}$), the above inequality holds, as desired.

Let us then assume that the premises of Lemma 3 hold, i.e.,
$x\sum_{i=1}^{k}x_{i}<k\sum_{i=1}^{n}x_{i}^{2}<x^{2}$. Then, $k^{\ast}(X,E)$
is the unique value satisfying

$\hat{E}(k^{\ast},X)\leq E\leq\hat{E}(k^{\ast}+1,X).$

Thus, if $E$ increases then either the above upper bound keeps holding (which
means that $k^{\ast}$ remains the same) or not (which means that $k^{\ast}$
increases to at least $k^{\ast}+1$ or beyond). Thus, if $E$ increases then
$k^{\ast}$ weakly increases. This also trivially extends to the case in which
the premises of Lemma 3 do not hold (as then either $k^{\ast}=1$ or
$k^{\ast}=n$). In other words, we have the following:

###### Proposition 6

The optimal value $k^{\ast}$ weakly increases with $E$.

##  5 An illustration

We now illustrate our results for a special case. We take as starting point
the squad spending limits in La Liga (the highest professional soccer league
in Spain) for the 2023/2024 season.151515
https://www.statista.com/statistics/764962/budget-equipment-from-football-
from-the-league-in-spain-2015-2016/ The squad spending limit denotes the
maximum amount that each club or public limited sports company (SAD) can spend
during the course of the summer season, including costs related to players,
the manager, assistant manager and fitness coach. It also includes spending on
the reserves, the youth system and other areas. As clubs usually spend all
they are allowed, we can consider these spending limits as equivalent to
budgets.

We start noticing that the HHI for the initial distribution is $1232.4$. Thus,
according to the U.S. Horizontal Merger Guidelines, within the moderately
concentrated region. It is important to note that Barcelona’s limit spending
(see Table 1) reflects a significant decrease from the ceiling established a
few months earlier due to the diminishing impact of the assets they sold off
to improve short-term finances. Without that decrease, the HHI for the initial
distribution would have been much higher, actually very close to the border
between the moderately concentrated region and the highly concentrated region.

We now apply our results and obtain that, for each $k=1,2,\dots,5$, the
$k$-top rules hurt competitive balance upon increasing the value of HHI, for
each possible value of the prize endowment $E$. The extent of this increase
depends on the specific rule and the specific value of the endowment. For
instance, if $k=1$ and $E\geq 425$ (million euros), the HHI of the resulting
distribution surpasses $1800$; thus, becoming part of the highly concentrated
region.

Note that La Liga is guaranteed $4$ slots in the UEFA Champions League each
year, which sometimes becomes $5$ (when the UEFA Champions League winner or
the UEFA Europa League winner is also from La Liga, and did not finish within
the Top 4 in the domestic competition), but never more than that. Thus, we can
conclude that allocating UEFA Champions League prizes to La Liga by rewarding
only its clubs that qualified for the UEFA Champions League will certainly
hurt La Liga’s competitive balance. In other words, to prevent a decrease of
competitive balance in La Liga, the prizes from the UEFA Champions League
should be redistributed to reach clubs that do not qualify for the UEFA
Champions League.

We also obtain that, for each $k=9,10,\dots,20$, the $k$-top rules improve
competitive balance upon decreasing the value of HHI, for each possible value
of the prize endowment $E$. The extent of this decrease also depends on the
specific rule and the specific value of the endowment. For instance, if $k=20$
and $E\geq 540$ (million euros), the HHI of the resulting distribution falls
short of $1000$; thus, within the unconcentrated region.

Finally, we obtain that for each $k=6,7,8$, the $k$-top rules improve
competitive balance upon decreasing the value of HHI, for each possible value
of the prize endowment $E$ within a realistic domain.161616More precisely,
when $E<1264$ (millions), the $6$-top rule increases competitive balance (the
HHI value is lower). Likewise, when $E<5544$ (millions), the $7$-top rule
increases competitive balance (the HHI value is lower). Finally, when
$E<86338$(millions), the $8$-top rule increases competitive balance (the HHI
value is lower). Thus, in the parlance of Proposition 3, we obtain that for
the case of La Liga, $k^{\ast}=6$.

Insert Table 1 about here

##  6 Discussion

We have explored in this paper the effect that the prize allocation of
international (sports) competitions has on the structure of domestic
competitions. For that purpose, we have resorted to the well-known Herfindahl-
Hirschman index. By comparing the value of the index before and after the
clubs get prize money for participation in international tournaments, one can
analyze the changes in competitive balance. Our main insights can be
summarized in the next three items.

  * •

For each initial clubs’ budget distribution in the league, rewarding a high
number of clubs with the same prize improves competitive balance, while
distributing prize money to a low number of clubs worsens competitive balance.

  * •

For each initial clubs’ budget distribution in the league, equal distribution
of prize money between the clubs participating in the international
competitions is better (from the competitive balance perspective) than any
other monotonic (with respect to a position in the league) distribution
between the same clubs.

  * •

There exists a threshold of the prize value such that competitive balance
increases (as a function of the prize value) below the threshold, whereas it
declines (as a function of the prize value) above the threshold.

In other words, as expected, the rule awarding only the top club in the
domestic competition unambiguously hurts competitive balance in the domestic
competition, whereas the rule equally awarding all clubs in the domestic
competition unambiguously improves competitive balance in the domestic
competition. Our more insightful results show that compromises between these
two polar schemes offer intermediate results. More precisely, the rules that
award a subset of the top clubs in each domestic competition have interesting
features. On the one hand, they are all fully ranked with respect to
competitive balance. That is, the larger the number of top clubs considered,
the better. This implies that “weaker” leagues with only one spot in the
international competition are hurt more than the other competitions. On the
other hand, although fully ranked according to competitive balance, the fact
that the resulting rule hurts or improves competitive balance with respect to
the status quo (without prize allocation) depends on the initial conditions
(the pre-allocation budget distribution and the size of the prize to be
allocated). By extending our benchmark analysis we find support for an equal-
share scheme compared to uneven prize allocations.

One might infer from the above that UEFA’s idea to share at least the market
pool more equally amongst participants from the same country seems to be a
good idea. Thus, in a reward sharing scheme compromising between the market
pool and pure performance pay, our analysis suggests to prioritize the former.
Likewise, the idea to redistribute at least a small share of revenues from
Eredivisie club’s participation in UEFA club competitions amongst the non-
participating clubs in the Dutch first division seems reasonable according to
our findings.171717https://eredivisie.eu/news/eredivisie-first-league-to-
redistribute-revenues-from-uefa-club-competitions/

Moreover, we might argue that increasing the number of participating clubs,
allocating more than just one spot at least to some leagues, seems reasonable.
But it remains an empirical question whether UEFA Champions League revenues
have increased (or will increase after format change in 2024) enough to
mitigate the effect on competitive balance. Likewise, as we suggest that the
Top 5 European leagues (French Ligue 1, Italian Serie A, German Bundesliga,
Spanish La Liga and English Premier League) are less affected (because they
get more spots in the international competition), it would be interesting to
explore empirically the effects in smaller leagues to complement what
Pawlowski et al., (2010) found for the Top 5 leagues.

We also believe our work provides relevant insights for the strand of
literature on financial sustainability (e.g., Peeters and Szymanski, 2014).
Both regulation policies (distribution of prize money and financial
sustainability rules) play a crucial role in determining the future of
European football. In both cases, one of the most important questions is what
will happen with the ensuing inequality.

We conclude with two caveats.

First, our analysis has relied on HHI as a proxy for competitive balance,
which could be rationalized upon connecting with the classical literature
mentioned at the introduction, which relates HHI to welfare via fan interest.
But this is contested as some leagues with different levels of competitive
balance in recent years (e.g., Bundesliga and Premier League) have stadiums
operating at almost full capacity over a season.181818The uncertainty of
outcome hypothesis is nevertheless usually supported with broadcasting
figures, rather than stadium attendance. One might argue that regulatory
agencies care about ranges (rather than specific values) of HHI. To this end,
we have also illustrated that our results can go beyond a linear concern for
competitive balance, offering further insights about the extent of HHI changes
that prize allocations yield. More precisely, we have illustrated in a
specific case (when the initial budget distribution is provided) that
alternative prize allocations can also generate shifts in the range regions of
HHI (from highly concentrated to moderately concentrated, or even
unconcentrated, and vice versa).

Second, our analysis is based on monotonicity assumptions: better clubs
domestically perform better in international competitions, thus obtain higher
revenues and get even stronger. In reality, this is not always the case and
unexpected results might occur. However, the probability of unexpected results
is low. On the other hand, relative differences in budgets usually translate
into much smaller relative differences in outcomes (e.g., points scored in a
season). It is left for future research to study the robustness of our results
to surprises. A plausible way to do so would be considering an expectation of
the HHI. Alternatively, one could explore a multi-period model, where
unexpected results improve competitive balance, but after many seasons the
strong clubs still get even stronger.

## References

  * [1] Arlegi, R., Dimitrov, D., 2020. Fair elimination-type competitions. European Journal of Operational Research 287, 528-535.
  * [2] Bergantiños, G., Moreno-Ternero, J.D., 2020. Sharing the revenues from broadcasting sport events. Management Science 66, 2417-2431.
  * [3] Bergantiños, G., Moreno-Ternero, J.D., 2021. Compromising to share the revenues from broadcasting sports leagues. Journal of Economic Behavior and Organization 183, 57-74.
  * [4] Bergantiños, G., Moreno-Ternero, J.D., 2023a. Broadcasting La Liga. Sports Economics Review 1, 100005.
  * [5] Bergantiños, G., Moreno-Ternero, J.D., 2023b. Decentralized revenue sharing from broadcasting sports. Public Choice 194, 27-44.
  * [6] Besanko, D., Dranove, D., Shanley, M., Schaefer, S., 2017. Economics of Strategy, 7th edition. John Wiley & Sons.
  * [7] Bossert, W., D’Ambrosio, C., Weber, S., 2022. Distance-based social index numbers: A unifying approach. Journal of Mathematical Economics 100, 102617.
  * [8] Budzinski, O., Pawlowski, T., 2017. The behavioral economics of competitive balance: theories, findings, and implications. International Journal of Sport Finance 12, 109-122.
  * [9] Butler, M., 1995, Competitive balance in the major league baseball, The American Economist 39, 46-52.
  * [10] Csató, L., 2021. Tournament design: How operations research can improve sports rules. Springer Nature.
  * [11] Dansby, R., Willig, R., 1979. Industry Performance Gradient Indexes. American Economic Review 69, 249-260.
  * [12] Dietzenbacher, B. J., Kondratev, A. Y., 2023. Fair and consistent prize allocation in competitions. Management Science 69, 3319-3339.
  * [13] Depken, C. A. 1999. Free-agency and the competitiveness of Major League Baseball. Review of Industrial Organization 14, 205-217.
  * [14] Ely, J., Frankel, A., Kamenica, E. 2015. Suspense and surprise. Journal of Political Economy 123, 215-260.
  * [15] Farrell, J., Shapiro, C. 1990. Horizontal Mergers: An Equilibrium Analysis. American Economic Review 80, 107-126.
  * [16] Frick, B., 2009. Globalization and Factor Mobility: The Impact of the “Bosman-Ruling” on Player Migration in Professional Soccer. Journal of Sports Economics 10, 88-106.
  * [17] Gans, J. S., Smart, M., 1996. Majority voting with single-crossing preferences. Journal of Public Economics 59, 219-237.
  * [18] Guironnet, J-P., 2023. Competitive intensity and industry performance of professional sports. Economic Modelling 126, 106441.
  * [19] Hall, M., Tideman, N., 1967. Measures of concentration. Journal of the American Statistical Association 62, 162-168.
  * [20] Hemming, R., Keen, M.J., 1983. Single-crossing conditions in comparisons of tax progressivity. Journal of Public Economics 20, 373-380.
  * [21] Herfindahl, O., 1950. Concentration in the U.S. steel industry, unpublished doctoral dissertation, Columbia University.
  * [22] Hirschmann, A., 1945. National power and the structure of foreign trade, Discussion Paper, University of California, Berkeley.
  * [23] Jakobsson, U., 1976. On the measurement of the degree of progression. Journal of Public Economics 5, 161-168.
  * [24] Kuper, S, Szymanski, S., 2018. Soccernomics: Why England loses, why Germany and Brazil win, and why the US, Japan, Australia, Turkey–and even Iraq–are destined to become the kings of the world’s most popular sport. Hachette UK.
  * [25] Li, M., Davari, M., Goossens, D., 2023. Multi-league sports scheduling with different leagues sizes. European Journal of Operational Research 307, 313-327.
  * [26] Martinez, R., Moreno-Ternero J.D., 2022. An axiomatic approach towards pandemic performance indicators. Economic Modelling 116, 105983.
  * [27] Moreno-Ternero J.D., 2011. Voting over piece-wise linear tax methods. Journal of Mathematical Economics 47, 29-36.
  * [28] Neale, W., 1964. The peculiar economics of professional sports: A contribution to the theory of the firm in sporting competition and in market competition. Quarterly Journal of Economics 78, 1-14.
  * [29] Owen, P.D., Ryan, M., Weatherston, C.R., 2007. Measuring competitive balance in professional team sports using the Herfindahl-Hirschman index. Review of Industrial Organization, 289-302.
  * [30] Pawlowski, T., Breuer, C., Hovemann, A., 2010. Top Clubs’ Performance and the Competitive Situation in European Domestic Football Competitions. Journal of Sports Economics 11, 186-202.
  * [31] Peeters, T., 2015. Profit-maximizing gate revenue sharing in sports leagues. Economic Inquiry 53, 1275-1291.
  * [32] Peeters, T., Szymanski, S. 2014. Financial fair play in European football. Economic Policy 29, 343-390.
  * [33] Richardson, T., Nalbantis, G., Pawlowski, T., 2023. Emotional cues and the demand for televised sports: Evidence from the UEFA Champions League. Journal of Sports Economics 24, 993-1025.
  * [34] Roemer, J.E., 2001. Political competition: Theory and applications. Harvard University Press.
  * [35] Roemer, J.E., 2006. Democracy, Education, and Equality. Econometric Society Monograph. Cambridge University Press.
  * [36] Rottenberg, S., 1956. The baseball player’s labour market. Journal of Political Economy 64, 242-258.
  * [37] Simmons, R., 1997. Implications of the Bosman ruling for football transfer markets. Economic Affairs 17, 13-18.
  * [38] Sloane, P.J., 1971. The economics of professional football: the football club as a utility maximiser. Scottish Journal of Political Economy 18, 121-146.
  * [39] Vives, X., 2008. Innovation and competitive pressure. The Journal of Industrial Economics 56, 419-469.
  * [40] Zimbalist, A., 2002. Competitive balance in sports leagues: An introduction. Journal of Sports Economics 3, 111-121.