# Best-response dynamics in directed network games††thanks: We thank Yann
Bramoullé, Péter Csóka, P. Jean-Jacques Herings, Botond Kőszegi, Mánuel László
Mágó, Ronald Peeters, Miklós Pintér, Ádám Szeidl, Frank Thuijsman, Yannick
Viossat, and Mark Voorneveld for valuable feedback and suggestions.

Péter Bayer Corresponding author. Université Grenoble Alpes, GAEL, 1241 Rue
des Résidences, 38400 Saint Martin d’Hères, France. E-mail: peter.bayer@univ-
grenoble-alpes.fr. György Kozics Central European University, Department of
Economics and Business, Nádor utca 9, 1051 Budapest, Hungary. E-mail:
<EMAIL_ADDRESS>Nóra Gabriella Szőke Université Grenoble Alpes,
Institut Fourier, CS 40700, 38058 Grenoble cedex 09, France. E-mail:
<EMAIL_ADDRESS>Research supported by the Swiss National
Science Foundation, Early Postdoc.Mobility fellowship no. P2ELP2_184531.

###### Abstract

We study public goods games played on networks with possibly non-reciprocal
relationships between players. Examples for this type of interactions include
one-sided relationships, mutual but unequal relationships, and parasitism. It
is well known that many simple learning processes converge to a Nash
equilibrium if interactions are reciprocal, but this is not true in general
for directed networks. However, by a simple tool of rescaling the strategy
space, we generalize the convergence result for a class of directed networks
and show that it is characterized by transitive weight matrices. Additionally,
we show convergence in a second class of networks; those rescalable into
networks with weak externalities. We characterize the latter class by the
spectral properties of the absolute value of the network’s weight matrix and
show that it includes all directed acyclic networks.
Keywords: Networks, externalities, local public goods, potential games, non-
reciprocal relations.
JEL classification: C72, D62, D85.

##  1 Introduction

All social and economic networks feature relationships which cannot be
described as a partnership of equals. There are relationships between pairs of
agents in which only one party is interested and the other is not. Some
relationships are beneficial for one party but harmful for the other. Even
when both parties benefit or both are harmed, the extent by which they are
affected by their counterpart’s decisions is not necessarily equal.
Nevertheless, most scientific works, both theoretical and applied, are using
models in which the reciprocity of interactions is a fundamental property.
These frameworks, simple graphs and weighted networks, have received a lot of
recent interest from economic theorists due to them providing a highly
accurate, rich, and efficient description of real-life interactions. However
for reasons relating to either convenience or convention, non-reciprocal
relations, and their relevance to economic theory, are relatively unexplored
in network literature.

In particular, most models featuring externalities in networks such as
Ballester et al., (2006) and Bramoullé and Kranton, (2007) assume reciprocal
interactions. These highly influential theoretical papers opened the way for a
number of applications, such as R&D expenditure between interlinked firms
(König et al.,, 2019), peer effects (Blume et al.,, 2010), defense
expenditures (Sandler and Hartley,, 1995, 2007), and crime (Ballester et al.,,
2010). Most of the applied literature continues to assume reciprocity of
relations and performs equilibrium analysis. However, as it will be apparent
from our results, the basis behind using the Nash equilibrium as a prediction
in networks with non-reciprocal interactions is much weaker than with only
reciprocal ones. Thus, predictions made by models using simple graphs or
weighted networks are only justified for applications where the underlying
interaction network is shown to consist only of reciprocal relations.

In this paper we extend the theoretical literature of learning in networks to
include non-reciprocal relations by the use of directed networks. By doing so
we intend to fill a gap in the theory literature and provide a jumping off
point for a stronger connection between subsequent applied literature and
real-life interaction networks. Our setting generalizes games played on
weighted networks: instead of one weight, each link is defined by two distinct
weights, one for each direction. The three important types of non-reciprocal
relations we highlight are (1) one-directional links with one of the weights
of the link being zero and the other being non-zero, e.g., an upstream city
along a river affects a neighboring downstream city by polluting the river but
not vice versa, (2) parasitic links with one weight being positive and the
other being negative, e.g., a criminal organization engaging in the extortion
of a small business gains benefits from the interaction but it comes with
losses for the business, and (3) mutual but unequal benefit or harm, with both
weights being positive or both being negative but they are not equal, e.g., a
monopolistic seller and a competitive buyer both benefit from their economic
relationship but the gains from the interaction tend to be greater for the
seller than for the buyer.

One of the focuses of theoretical literature of public goods and networks is
the convergence of learning processes to the Nash equilibrium. This is to
provide a behavioral and an evolutionary motivation to use equilibrium as a
prediction in applied settings. Under symmetric weight matrices a number of
powerful convergence results are known: Stability of Nash equilibria with
respect to the continuous best-response dynamic has been established by
Bramoullé et al., (2014). Convergence of the continuous best-response dynamic
to some Nash equilibrium in all such games has been shown by Bervoets and
Faure, (2019). Bayer et al., 2019b  shows convergence of a class of one-sided
learning processes. Bervoets et al., (2018) constructs a convergent learning
process not requiring the sophistication of the best response. Bayer et al.,
2019a  studies the impact of a farsighted agent on the process in a population
of myopic players. Together, these results allow for an interpretation of the
game’s Nash equilibria as the results of a sequence of improvements made
separately by the players.

All of the above papers assume reciprocal network interactions. Thus, they
make use of more general results of games of reciprocal interactions (Dubey et
al.,, 2006; Kukushkin,, 2005), as well as that of generalized aggregative
games (Jensen,, 2010). The latter structure allows for the use of the theory
of potential games (Monderer and Shapley,, 1996), specifically, best-response
potential games (Voorneveld,, 2000). The main intuition behind the existence
of a differentiable best-response potential function for reciprocal
interaction networks is that the potential’s Hessian, a symmetric matrix, must
correspond to the Jacobian of the system of best-responses, which, in this
case, is equal to the network’s weight matrix. In this paper, however, we show
that the best-response potential structure can be exploited in important
classes of networks even when the relations, as expressed by the interaction
matrix, are not reciprocal.

We consider convergence to Nash equilibria under one-sided improvement
dynamics taking place in discrete time. Starting from a profile of production
decisions, in every time period one player receives an opportunity to change
her production, while every other player remains on the previous period’s
level. In the next period, another player receives a revision opportunity, and
so on. We consider three versions of the best-response dynamic. In increasing
order of generality, these are the pure best-response dynamic, in which every
revision takes the player to her current best choice given the actions of
others, the best-response-approaching dynamic, in which every revision moves
the player into the interval between her current action and her current best
choice, and the best-response-centered dynamic, in which every revision
reduces the distance between her action and her current best choice. Pure
best-response dynamics as described above are widely studied. In directed
network games, best-response-approaching dynamics include the naive learning
dynamics introduced by Bervoets et al., (2018), while best-response-centered
dynamics are studied in Bayer et al., 2019b . These two dynamics are similar
to the directional learning model (Selten and Stoecker,, 1986; Selten and
Buchta,, 1998) in which players are making attempts to find their targets by
adjusting towards the direction they believe the target is located. Such
qualitative learning models are known to explain experimental behavior in
various settings (Cachon and Camerer,, 1996; Cason and Friedman,, 1997; Kagel
and Levin,, 1999; Nagel and Vriend,, 1999).

While none of these dynamics can cycle under reciprocal interactions, in
directed network games cycles can emerge. Cycles indicate that convergence to
the Nash equilibrium is not a universal property of learning processes. We
discuss two examples: (1) directed cycle networks allow for best-response
cycles as economic activity of the players flows in the opposite direction as
the external effects of the network, and (2) parasite-host networks with
amplifying links lead to best-response cycles as the parasite’s economic
activity increases with the host’s activity level, while the host’s economic
activity decreases with that of the parasite.

Nevertheless, classes of networks exist without cycles where convergence to a
Nash equilibrium can be shown, given some mild assumptions on the order of
updates. In this paper we identify two such classes, networks with transitive
relative importance, and games rescalable to exhibit weak influences or weak
externalities.

The former class captures networks that can be transformed into symmetric
networks with some appropriate rescaling of the action space, an idea raised
by Bramoullé et al., (2014). Rescaling can be understood as changing the
measurement of one player’s production from, e.g., euros to dollars. Rescaling
does not affect the equilibrium structure or the convergence properties of the
game, but it does change its nominal interaction structure as expressed by the
network’s weight matrix. Thus, a network with reciprocal interactions can be
rescaled into non-reciprocal ones, which thus inherit its convergence
properties. A network can be rescaled in such a way if and only if it
satisfies the property of transitive relative importance and it does not have
one-way or parasitic interactions.

The relative importance of a link for a player is measured by the relative
payoff-effects between the two players. If a link is reciprocal, then the
relative importance of that link for both players is unity. A link with a
larger weight for one player and a small weight for the other is relatively
more important to the former and, inversely, not so important for the latter.
Transitive relative importance restricts the network through these values. For
instance, if the link $\\{i,j\\}$ is more important to $i$ than to $j$, and if
the link $\\{j,k\\}$ has equal importance to both participants, then the link
$\\{i,k\\}$ must be more important to $i$ than to $k$. This property presumes
a common hierarchy of players with important players whose production matters
greatly in relative terms for all individuals and less important players whose
production matters little.

This property is closely connected to Kolmogorov’s reversibility criterion for
Markov chains (see e.g. Kelly, (2011)), as well as transitive matrices (Farkas
et al.,, 1999) a property applied in pairwise comparison matrices (Bozóki et
al.,, 2010) and Analytic Hierarchy Processes (Saaty,, 1988). We show that
these networks and only these can be rescaled into symmetric ones, and these
are the only ones that have a quadratic best-response potential function.

The second class of networks with convergent best-response dynamics are those
that are rescalable to exhibit weak influences or weak externalities. A player
is influenced weakly by her opponents if the total effects of a unit change in
all of her opponents’ actions on her are smaller than the effect of a unit
change in her own action. These networks are characterized by row diagonally
dominant weight matrices. In social networks, this property can be interpreted
as a form of individualism. On the other hand, weak external effects are
characterized by column diagonally dominant weight matrices, meaning a unit
change in any player’s action has a larger effect on herself than on all the
other players combined. In economics, small level of externalities is a
characteristic of efficient markets.

In non-cooperative game theory, weakness of externalities is known be
sufficient for uniqueness of the Nash equilibrium as well as convergence to
the unique Nash equilibrium under best-response dynamics (Gabay and Moulin,,
1980; Moulin,, 1986). In networks, weak influences are studied by Parise and
Ozdaglar, (2019) while both types of diagonal dominance are studied by Scutari
et al., (2014). Since in our model, network weights are allowed to be both
negative and positive, weak externalities is a separate condition from small
network effects (Bramoullé et al.,, 2014; Belhaj et al.,, 2014). Under small
network effects, given an equilibrium production profile, a tremor in a
player’s production decision is dampened by the network such that the system
returns to the original equilibrium under best-response dynamics. We show that
small network effects in absolute value, that is, the spectral radius of the
absolute value of the weight matrix being less than one is sufficient and
necessary for rescalability into networks with weak influences and those with
weak externalities. We thus fully characterize the class of networks for which
uniqueness of equilibrium and global convergence of best-response dynamics can
be shown by either type of diagonal dominance. Moreover, we show that this
class of games also has a potential structure.

Additionally, this class also includes the set of directed acyclic networks.
In this subclass every interaction is one-way and there are no directed
cycles. The latter property imposes a hierarchy on the players with respect to
the one-way interactions; players on the highest level of the hierarchy are
not affected by any other player, players on intermediate levels are affected
by those on higher levels but not by those on lower levels, while players on
the lowest level have no effect on any other player. The most direct
application of this class of games is pollution management of cities along a
river (Ni and Wang,, 2007) or a river network (Dong et al.,, 2012), but the
same model is used in studying the conservation of common-pool resources
(Richefort and Point,, 2010) and games with permission structures (van den
Brink et al.,, 2018).

Overall, our results have a number of implications with respect to convergence
in directed network games. A negative finding is that, in networks with
directed cycles and parasite-host interactions with amplifying weights, the
interpretation of the Nash equilibrium as an outcome of a series of
decentralized improvements by the players is questionable as the convergence
of simple learning processes is not assured. We complement this with a set of
positive results by identifying and characterizing interesting classes of
networks where convergence is assured. Our two sets of positive results
uncover insights into the relationship between reciprocity of network
interactions, the spectral properties of the network, and the games’ potential
structure as well as generalize the powerful results achieved for the case of
reciprocal interactions.

Our paper is organized as follows: Section 2 presents our two main concepts,
directed network games and best-response dynamics. In Section 3 we present the
two simple networks with best-response cycles. Section 4 contains our
characterization and convergence results for networks that can be rescaled
into symmetric networks. Section 5 contains the same sets of results for
networks rescalable to games with weak influences or weak externalities, and
shows that this class includes directed acyclic networks. Section 6 concludes.

##  2 The model

Let $I=\\{1,\ldots,n\\}$ be the set of players. For $i\in I$ and upper bounds
$\overline{x}_{i}>0$ the set $X_{i}=[0,\overline{x}_{i}]$ is called the action
set of player $i$, $X=\prod_{i\in I}X_{i}$ is called the set of action
profiles. We let $x_{i}\in X_{i}$ denote the action taken by player $i$ while
$x_{-i}\in X\setminus X_{i}$ denotes the truncated action profile of all
players except player $i$, and $x=(x_{i})_{i\in I}$ denotes the action profile
of all players.

The formal definition of directed network games used in this paper is as
follows.

######  Definition 2.1.

The tuple $G=(I,X,(\pi_{i})_{i\in I})$ is called a directed network game with
payoff functions $\pi_{i}\colon X\to\mathbb{R}$ given by

$\displaystyle\pi_{i}(x)=f_{i}\left(\sum_{j\in
I}w_{ij}x_{j}\right)-c_{i}x_{i},$ (1)

where $f_{i}:\mathbb{R}\to\mathbb{R}$ is twice differentiable,
$f_{i}^{\prime}>0$, $f_{i}^{\prime\prime}<0$, $w_{ij}\in\mathbb{R}$,
$w_{ii}=1$, and $c_{i}\geq 0$ for every $i,j\in I$.

The interpretation is the following. Each player produces a specialized good
with linear production technology, incurring costs $c_{i}$ for every unit of
the good produced. Players derive benefits from the consumption of their own
goods and they are affected by their opponents’ production decisions. Player
$i$’s enjoyment of player $j$’s good is represented by the weight
$w_{ij}\in\mathbb{R}$. We normalize the interaction parameter of each player
$i$ with herself, $w_{ii}$, to $1$. The overall benefits of player $i$ are
given by the benefit function $f_{i}$ over the weighted sum of her and her
opponents’ goods. Crucially, we do not impose reciprocal relations, meaning
that $w_{ij}\neq w_{ji}$ may hold, so the weight matrix $(w_{ij})_{i,j\in
I}=W$ might not be symmetric.

Since the benefit functions $f_{i}$ are increasing and concave and the cost
parameters $c_{i}$ are positive, for every $x_{-i}$ there is a unique value of
$x_{i}$ that maximizes $\pi_{i}(x)$. Let the target values $t_{i}$ be
implicitly defined by $f^{\prime}_{i}(t_{i})=c_{i}$, i.e. the value player $i$
would produce if all others produce $0$ and let $t=(t_{i})_{i\in I}$ denote
the vector of targets. We make the simplifying assumption that every player is
able to produce her target amount of the good.

######  Assumption 2.2.

We assume that $f_{i}$ are given such that for every $i\in I$ we have
$t_{i}\in(0,\overline{x}_{i})$.

Note that if $w_{ij}>0$ and $w_{ji}>0$, then the goods of players $i$ and $j$
are strategic substitutes. If $w_{ij}<0$ and $w_{ji}<0$ then their goods are
strategic complements. If $w_{ij}>0$ and $w_{ji}<0$, then we say that players
$i$ and $j$ share a parasitic link. If $w_{ij}=0$, then player $i$ is not
directly affected by player $j$’s production decision.

For player $i\in I$ and $x\in X$, $b_{i}(x)=\operatorname*{argmax\,}_{x_{i}\in
X_{i}}\pi_{i}(x)$ denotes player $i$’s best-response function.

######  Lemma 2.3.

Let $G=(I,X,(\pi_{i})_{i\in I})$ be a weighted network game. Then, for every
$i\in I$ and $x\in X$ the best response functions are the following:

$\displaystyle b_{i}(x)=\begin{cases}0&\text{if }t_{i}-\sum_{j\in
I\setminus\\{i\\}}w_{ij}x_{j}<0,\\\ t_{i}-\sum_{j\in
I\setminus\\{i\\}}w_{ij}x_{j}&\text{if }t_{i}-\sum_{j\in
I\setminus\\{i\\}}w_{ij}x_{j}\in[0,\overline{x}_{i}],\\\
\overline{x}_{i}&\text{if }t_{i}-\sum_{j\in
I\setminus\\{i\\}}w_{ij}x_{j}>\overline{x}_{i}.\end{cases}$ (2)

###### Proof.

First, we calculate the unconstrained best response for player $i$. The first-
order condition is

$\displaystyle\frac{\partial\pi_{i}(x)}{\partial
x}=f_{i}^{\prime}\left(\sum_{j\in I}w_{ij}x_{j}\right)-c_{i}=0.$

Combining with $f^{\prime}_{i}(t_{i})=c_{i}$, we get that the unconstrained
best response, $\tilde{b}_{i}(x)$ is

$\displaystyle\tilde{b}_{i}(x)=t_{i}-\sum_{j\in
I\setminus\\{i\\}}w_{ij}x_{j}.$ (3)

The second-order condition is

$\displaystyle\frac{\partial^{2}\pi_{i}(x)}{\partial
x^{2}}=f_{i}^{\prime\prime}\left(\sum_{j\in I}w_{ij}x_{j}\right)<0,$

hence $\tilde{b}_{i}(x)$ is indeed maximizing the payoff. This means that for
every $x_{i}>\tilde{b}_{i}(x)$, a marginal increase of $x_{i}$ decreases
$\pi_{i}(x)$, while for every $x_{i}<\tilde{b}_{i}(x)$, a marginal increase of
$x_{i}$ increases $\pi_{i}(x)$. Therefore, if
$\tilde{b}_{i}(x)\in[0,\overline{x}_{i}]$, then $b_{i}(x)=\tilde{b}_{i}(x)$.
If $\tilde{b}_{i}(x)<0$, then $b_{i}(x)=0$, as choosing a larger $x_{i}$ would
decrease the payoff. Similarly, if $\tilde{b}_{i}(x)>\overline{x}_{i}$, then
$b_{i}(x)=\overline{x}_{i}$. ∎

######  Proposition 2.4.

Every directed network game has at least one Nash equilibrium.

Bramoullé et al., (2014)’s analogue result using Brouwer’s fixed-point theorem
for a positive and symmetric weight matrix is directly applicable in the
directed network case. Let the set of Nash equilibria be denoted by
$X^{\ast}$.

Lemma 2.3 and Proposition 2.4 have close analogues in existing models with
symmetric interaction, but, as we will show shortly, results concerning the
cycling and convergence of simple learning processes do not hold in general in
the directed network case.

We now formally introduce the learning processes of our paper, the best-
response dynamic and two extensions.

######  Definition 2.5.

The sequence of action profiles $(x^{k})_{k\in\mathbb{N}}$ is a one-sided
dynamic if

  * •

for every $k\in\mathbb{N}$ there exists an $i^{k}\in I$ such that
$x_{-i^{k}}^{k}=x_{-i^{k}}^{k+1}$, and

  * •

for every $i\in I$ the set $K^{i}=\\{k\in\mathbb{N}\colon i^{k}=i\\}$ is
infinite.

######  Definition 2.6 (Best-response dynamics).

The one-sided dynamic $(x^{k})_{k\in\mathbb{N}}$ is a

  * •

best-response dynamic (BRD), if we have $x_{i^{k}}^{k+1}=b_{i^{k}}(x^{k})$.

  * •

best-response-approaching dynamic (BRAD) with approach parameter
$0\leq\beta<1$, if
$|x_{i^{k}}^{k+1}-b_{i^{k}}(x^{k})|\leq\beta|x_{i^{k}}^{k}-b_{i^{k}}(x^{k})|$
and if $x_{i^{k}}^{k+1}\neq b_{i^{k}}(x^{k})$, then
$\operatorname{sgn}(x_{i^{k}}^{k+1}-b_{i^{k}}(x^{k}))=\operatorname{sgn}(x_{i^{k}}^{k}-b_{i^{k}}(x^{k}))$.

  * •

best-response-centered dynamic (BRCD) with centering parameter
$0\leq\alpha<1$, if
$|x_{i^{k}}^{k+1}-b_{i^{k}}(x^{k})|\leq\alpha|x_{i^{k}}^{k}-b_{i^{k}}(x^{k})|$,

for every $k\in\mathbb{N}$.

In a one-sided dynamic exactly one player changes her action in every time
period. In a BRD, every revision takes the updating player to her best
response, in a BRAD, players move closer to their best responses without
overshooting it, while in a BRCD, players move closer to their best responses
and are allowed to overshoot. The approach and centering parameters of a BRAD
and a BRCD, respectively, indicate the maximum fraction to which the distances
are allowed to decrease. These processes allow payoff-maximizing players to
make mistakes, their ability of reaching the best-response is captured by the
two parameters with lower values indicating a higher level of accuracy. It is
clear that every BRD is a BRAD and every BRAD is a BRCD.

In all cases, through Definition 2.5, we restrict our attention to dynamics
where every player revises infinitely many times. This brings the property
that every convergent dynamic will converge to a Nash equilibrium, and no
player can get stuck playing a suboptimal action indefinitely by not having
the opportunity to revise.

Bramoullé et al., (2014) and Bervoets and Faure, (2019) consider the BRD in
continuous time. Parise and Ozdaglar, (2019), in addition to the continuous-
time dynamic, also considers discrete-time BRD, both simultaneous and
sequential updating in a fixed order of players. Our BRD process is more
general than the latter as revision opportunities may arrive in any order.
Bayer et al., 2019b  considers both the BRD and the BRCD as above.

Finally in this section we define one of the main concepts used in this paper,
best-response potential games.

######  Definition 2.7 (Voorneveld, (2000)).

A game $G=(I,X,(\pi_{i})_{i\in I})$ is a best-response potential game, if
there exists a best-response potential function $\phi:X\to\mathbb{R}$ such
that for every $i\in I$, and every $x_{-i}\in X_{-i}$ it holds that

$\displaystyle\operatorname*{argmax\,}_{x_{i}\in
X_{i}}\pi_{i}(x)=\operatorname*{argmax\,}_{x_{i}\in X_{i}}\phi(x).$

Definition 2.7 states that $G$ is a best-response potential game if the best-
response behavior of all players can be characterized by a single real-valued
function $\phi$, called the best-response potential.

##  3 Networks with best-response cycles

In this section we discuss the cycling of best-response dynamics. The non-
existence of best-response cycles is a necessary but not sufficient condition
of the convergence of best-response dynamics (Kukushkin,, 2015), which is true
in networks with reciprocal interactions. In this section we show that
directed cycle networks and parasitic relations with amplifying links lead to
cycling and thus hinder any general convergence results.

We begin with a formal definition of cycles.

######  Definition 3.1 (Cycles).

A sequence $(x^{k})_{k\in\mathbb{N}}$ has a cycle if there exist three time
periods, $k<k^{\prime}<k^{\prime\prime}$ such that
$x^{k}=x^{k^{\prime\prime}}$, but $x^{k}\neq x^{k^{\prime}}$.

In words, a process has a cycle if it non-trivially revisits an action profile
in two different time periods.

######  Example 3.2 (Directed cycle network).

Consider the directed cycle network, with $I=\\{1,2,3\\}$, $X_{i}=[0,1]$ for
$i\in I$, and the weight matrix

$\displaystyle W=\begin{pmatrix}1&0&1\\\ 1&1&0\\\ 0&1&1\end{pmatrix},$

representing a directed cycle with three players. Let $f_{i}(x)=\log(1+x)$ and
$c_{i}(t_{i})=1/(1+t_{i})$ for $i\in I$, so player $i$’s payoff is

$\displaystyle\pi_{i}(x)=\log\left(1+\sum_{j\in
I}w_{ij}x_{j}\right)-\frac{1}{1+t_{i}}x_{i}.$

As $f^{\prime}(t_{i})=c_{i}(t_{i})$, $t$ is indeed the vector of targets. Now
fix $t=(1,1,1)^{\top}$.

This game has a single Nash equilibrium, $x^{\ast}=(0.5,0.5,0.5)^{\top}$.
Consider the BRD with the initial action profile $x=(1,0,0)^{\top}$. Let
player 3 receive the first revision opportunity, followed by player 1.

1$1$0$2$0$3$ |  | 1$1$0$2$1$3$ |  | 0$1$0$2$1$3$
---|---|---|---|---
Period 1 |  | Period 2 |  | Period 3
Figure 1: Economic activity shifts in the opposite direction of externalities
under the BRD.

Figure 1 shows how player 1’s initial production moves along its incoming link
to player 3. It is easy to see that by allowing player 2 to revise next
followed by player 3, activity shifts further on to player 2. Moving along one
step further completes the best-response cycle to $x=(1,0,0)^{\top}$.

The directed cycle of this example thus permits a best-response cycle in which
the players’ activity moves along the cycle in the opposite direction as the
players’ externalities. It is easy to see that this property remains true for
directed cycles of $n$ players. If $n$ is even, it may be possible to reach an
equilibrium in which every second player produces $1$ and the others produces
$0$ for some order of revisions, but no $0$-$1$ equilibrium exists if $n$ is
odd. Therefore, in the latter case, if every player begins at a production
level of either $0$ or $1$, then the only two possible production levels in
any best-response path are also $0$ and $1$, and hence, convergence to the
Nash equilibrium is impossible. For $n=3$, the game will repeat the cycle in
Figure 1 ad infinitum.

Next, we consider a parasitic link between two players.

######  Example 3.3 (Parasitism).

Let $I=\\{1,2\\}$, $f_{i}(x)=\log(1+x)$, $c_{i}(t_{i})=1/(1+t_{i})$ for $i\in
I$, $t_{1},t_{2}=1$, and let

$\displaystyle W=\begin{pmatrix}1&-2\\\ 0.5&1\end{pmatrix}.$

Under the BRD, starting from the action profile $x=(1,0)^{\top}$, if both
players revise in turns, the game has a best-response cycle of length four.

1$1$0$2$$0.5$$-2$ | 1$1$.5$2$$0.5$$-2$
---|---
Period 1: Self-sustaining host. | Period 2: Activation of parasite.
2$1$.5$2$$0.5$$-2$ | 2$1$0$2$$0.5$$-2$
Period 3: Increased host activity. | Period 4: Passive, free-riding parasite.
Figure 2: The best-response cycle of Example 3.3.

In this example, player $1$ is called the host and player $2$ is called the
parasite. A self-sustaining host is engaged by a parasite. The host responds
by increasing her activity to offset the parasite’s negative effects. The
parasite’s benefits from the host are large enough that it ceases production
entirely and free-rides on the host. The host is then able to return to the
self-sustaining stage, completing the cycle. This process is shown in Figure
2.

The same pattern of parasite-host interaction can be replicated by different
calibration of parameters. A parasitic network requires $w_{12}<0$ and
$w_{21}>0$. If the network weights and targets also satisfy

  1. (i)

$\overline{x}_{1}\geq t_{1}-w_{12}(t_{2}-w_{21}t_{1})$ (host has a large
enough capacity to feed the parasite),

  2. (ii)

$\overline{x}_{2}\geq t_{2}-w_{21}t_{1}$ (parasite has a large enough capacity
to cause a nuisance to a self-sustaining host),

  3. (iii)

$t_{2}-w_{21}t_{1}>0$ (self-sustaining host does not satisfy the parasite),

  4. (iv)

$|w_{12}w_{21}|\geq 1$ (the link is amplifying),

then the best-response cycle qualitatively equivalent to that of Figure 2 is
achieved by sequential updates by the players.

Examples 3.2 and 3.3 together indicate that directed cycles and parasitic
relations lead to the cycling of BRDs, and hence that of BRADs and BRCDs.

##  4 Transitive relative importance

As shown in the previous section, allowing for non-reciprocal interactions in
network games changes their convergence properties under BRDs. However, there
are classes of directed network games where convergence to the game’s Nash
equilibrium can still be shown.

It is well known in the literature that convergence of BRDs in networks of
reciprocal interactions can be shown by exploiting the game’s potential
structure. In section VI, Bramoullé et al., (2014) raises the idea that, by an
appropriate rescaling of the action space, this method may be extended for
some class of directed networks as well. In this section we identify and
characterize this class of networks as those with transitive weight matrices.
Additionally, we show that, of all directed network games, games played on
these and only these networks have quadratic best-response potentials.

We first formally restate the convergence result in the symmetric case for
future use. We begin by defining regular updates by players.

######  Definition 4.1.

We say that players update regularly in a one-sided dynamic
$(x^{k})_{k\in\mathbb{N}}$, if there exists a $K>0$ such that for every $i\in
I$ and $k\in\mathbb{N}$ there exists a $k^{\prime}$ such that
$k<k^{\prime}\leq k+K$ and $i^{k^{\prime}}=i$.

Players updating regularly ensures that no player’s frequency of receiving
revision opportunities approaches zero.

######  Proposition 4.2.

Let $W$ be given such that for every $i,j\in I$ we have $w_{ij}=w_{ji}$ and
let $t$ be such that $|X^{\ast}|<\infty$. Then, every BRD and BRCD
$(x^{k})_{k\in\mathbb{N}}$ in which players update regularly converges to a
Nash equilibrium.

For the full proof of Proposition 4.2 see Theorem 5.3 in Bayer et al., 2019b .
By Lemma 3.2 in Bayer et al., 2019b , for every network, the set of target
vectors which result in infinitely many Nash equilibria is small both in the
measure theoretic sense and the topologial sense, so the finiteness condition
is not restrictive. The main intuition for the BRD part is that
$w_{ij}=w_{ji}$ implies that the function

$x^{\top}t-\frac{1}{2}x^{\top}Wx$

serves as a best-response potential. Every player’s update will weakly
increase the value of the best-response potential, which is bounded as the
action space is bounded. Regular updating ensures that, in time, every player
will be close to her current best-response, while finite number of Nash
equilibria ensures that convergence of $\phi$ translates to convergence to an
isolated peak of the potential value landscape, corresponding to a Nash
equilibrium. Additionally, Bayer et al., 2019b  show that the finiteness of
the equilibrium set is a generic property of undirected network games.

Take a vector $a\in\mathbb{R}^{n}$, called a scaling vector, such that $a>0$,
i.e., for every $i\in I$ we have $a_{i}>0$ and let $y_{i}=a_{i}x_{i}$ and
$\overline{y}_{i}=a_{i}\overline{x}_{i}$. Furthermore, let
$Y_{i}=[0,\overline{y}_{i}]$ and $Y=\prod_{i\in I}Y_{i}$. It is clear that any
BRD, BRAD, or BRCD in the game played on $X$ is a BRD, BRAD, or BRCD,
respectively, in the game played on $Y$ with the same approach or centering
parameters in the cases of BRAD and BRCD. Similarly, the convergence
properties of the processes in the game played on $Y$ are identical to those
in the game played on $X$.

By Lemma 2.3 the unconstrained best-response function of player $i$ in the
rescaled game is given by

$\displaystyle t_{i}a_{i}-\sum_{j\in
I\setminus\\{i\\}}w_{ij}\frac{a_{i}}{a_{j}}y_{j}.$

Let $w_{ij}a_{i}/a_{j}=v_{ij}$ and let $V=(v_{ij})_{i,j\in I}$ denote the
matrix of rescaled weights. Our goal in this section is to characterize the
class of networks that are rescalable into a symmetric network, i.e., the set
of networks $W$ for which there exists a vector $a>0$ such that for every
$i,j\in I$ we have

$\displaystyle\frac{a_{i}}{a_{j}}w_{ij}=v_{ij}=v_{ji}=\frac{a_{j}}{a_{i}}w_{ji}.$
(4)

Note that rescaling a network means that we conjugate its weight matrix by the
diagonal matrix of scaling weights. That is, consider
$S=\mathrm{diag}(a_{1},\dots,a_{n})$. Then, we have $V=SWS^{-1}$. We continue
to talk about rescalability instead of conjugate matrices as $S$ being a
diagonal matrix is crucial for our results, as it will be apparent in Theorem
4.6. A similar notion appears in Golub and Jackson, (2012) who rely on this
special case of matrix similarity to symmetric matrices.

We now define transitive relative importance of links.

######  Definition 4.3.

We say that the weight matrix $W$ shows transitive relative importance if for
every $3\leq m\leq n$ and for all pairwise distinct
$i_{1},i_{2},\ldots,i_{m}\in I$ we have

$w_{i_{1}i_{2}}w_{i_{2}i_{3}}\ldots
w_{i_{m-1}i_{m}}w_{i_{m}i_{1}}=w_{i_{1}i_{m}}w_{i_{m}i_{m-1}}\ldots
w_{i_{3}i_{2}}w_{i_{2}i_{1}}.$

For simplicity we write that $W$ is transitive if it satisfies Definition 4.3.
Notice that if $W$ is symmetric, then it is also transitive. In fact, a
symmetric $W$ satisfies the requirements of Definition 4.3 for $2\leq m\leq
n$. Also notice that if for every $i,j\in I$ it holds that $w_{ij}\neq 0$,
then $w_{ij}w_{jk}w_{ki}=w_{ik}w_{kj}w_{ji}$ for every pairwise distinct
$i,j,k\in I$ implies transitivity.

The interpretation is as follows: for $w_{ij},w_{ji}\neq 0$ define the value
$r_{ij}=w_{ij}/w_{ji}$ as player $i$’s relative importance on the link between
$i$ and $j$. It is clear that, if well-defined, the matrix $R=(r_{ij})_{i,j\in
I}$ is symmetrically reciprocal. In this case the transitivity property
reduces to having

$\displaystyle r_{ij}r_{jk}=r_{ik},$ (5)

for every $i,j,k\in I$. Thus, qualitatively, if the link $\\{i,j\\}$ is more
important to $i$ than to $j$ and if the link $\\{j,k\\}$ is more important to
$j$ than to $k$, then the link $\\{i,k\\}$ must be more important to $i$ than
to $k$.

######  Remark 4.4.

Transitivity as defined in Definition 4.3 is identical as Kolmogorov’s
characterization of reversible Markov chains with the exception that network
weights are allowed to be negative. If $R$ is defined, then transitivity of
$W$ means that $R$ is a consistent pairwise comparison matrix of an Analytic
Hierarchical Process (Saaty,, 1988). Here, the literature seems to use the
terms consistent (Bozóki et al.,, 2010) and transitive (Farkas et al.,, 1999)
interchangeably when describing the symmetrically reciprocal comparison matrix
$R$. We use transitivity of $W$ to indicate the intuition imposed on links.

The final definition we require is that of sign-symmetry.

######  Definition 4.5.

We say that the weight matrix $W$ is sign-symmetric if for every
$\\{i,j\\}\subseteq I$ we have
$\operatorname{sgn}(w_{ij})=\operatorname{sgn}(w_{ji})$.

Sign-symmetry of networks rules out one-way interactions and parasitic
interactions between players.

We are ready to present the main result of this section.

######  Theorem 4.6.

The following statements are equivalent:

  1. 1.

the network $W$ is rescalable into a symmetric matrix,

  2. 2.

the network $W$ is transitive and sign-symmetric,

  3. 3.

there exists a game $G$ on $W$ that has a quadratic best-response potential
function,

  4. 4.

every game $G$ on $W$ has a quadratic best-response potential function.

The proof is shown as an appendix.

Theorem 4.6 shows that transitivity of a network combined with sign-symmetry
is equivalent to it being rescalable into a symmetric network. Additionally,
no other network has a quadratic potential function, which shows that this
property cannot be exploited further. Our result thus gives a full
characterization for which types of directed networks satisfy the requirements
put forward in Bramoullé et al., (2014) section VI.

Theorem 4.6 and Proposition 4.2 give rise to the following corollary.

######  Corollary 4.7.

Let $W$ be a transitive and sign-symmetric network and let $t$ be given such
that $|X^{\ast}|<\infty$. Then, every BRD and BRCD in which players update
regularly converges to a Nash equilibrium.

For a fixed symmetric network, since the number of Nash equilibria is finite
for almost every target vector (Bayer et al., 2019b, ), Corollary 4.7 also
applies to every network and almost every target vector, thus convergence is
generically established for this class of networks.

##  5 Weak influences and weak externalities

In this section we characterize another class of networks with convergent
dynamics. A key concept in describing this class is the players’ influence and
the externalities they produce. A player $i$’s decisions are influenced by her
opponents through her incoming weights, measured by their total magnitude:
$\sum_{j\in I\setminus\\{i\\}}|w_{ij}|$. Similarly, a player $i$’s external
effects on her opponents is measured by the total magnitude of her outgoing
weights: $\sum_{j\in I\setminus\\{i\\}}|w_{ji}|$.

In this section we show that if total influences or externalities are weak
enough in a network, then games played on this network have a unique Nash
equilibrium and all BRDs and BRADs converge to it. As a motivating example,
consider a parametric version of Example 3.2.

######  Example 5.1 (Directed cycle with weights).

Consider the three player directed cycle network given by the weight matrix

$\displaystyle W=\begin{pmatrix}1&0&\delta\\\ \delta&1&0\\\
0&\delta&1\end{pmatrix},$

and with $\delta\in[0,1]$. Let $f_{i}(x)=\log(1+x)$,
$c_{i}(t_{i})=1/(1+t_{i})$ and fix $t_{i}=1$ for $i\in\\{1,2,3\\}$ as
previously. By Lemma 2.3, the best-response functions are $b_{1}(x)=1-\delta
x_{3}$, $b_{2}(x)=1-\delta x_{1}$, $b_{3}(x)=1-\delta x_{2}$. The only Nash
equilibrium is $x^{\ast}=(1/(1+\delta),1/(1+\delta),1/(1+\delta))^{\top}$.

If the strength of the influences is as strong as the own effects, i.e.
$\delta=1$, then best-response cycles may exist as shown in Example 3.2. In a
game with no interaction, $\delta=0$, best-response cycles cannot exist, since
the matrix is symmetric. We now consider how the cycling properties change by
changing $\delta$.

In Table 1 we show the sequence of action profiles in the BRD where players
receive revision opportunities in the same, repeating order $(3,1,2)$,
starting, again, in the action profile $(1,0,0)^{\top}$. In this order of
revisions, the player holding the revision opportunity in period $k$ will
revise to $\sum_{\ell=0}^{k}(-\delta)^{\ell}=(1-(-\delta)^{k+1})/(1+\delta)$
for parameter values of $\delta<1$ (see Table 1). Playing on in this order
will produce no cycles, and lead to convergence to the Nash equilibrium.

$k$ | $x_{1}^{k}$ | $x_{2}^{k}$ | $x_{3}^{k}$ | $i^{k}$ | $\sum_{j\in I}w_{i^{k}j}x_{j}$ | $b_{i^{k}}(x_{i^{k}})$
---|---|---|---|---|---|---
$0$ | $1$ | $0$ | $0$ | $3$ | $0$ | $1$
$1$ | $1$ | $0$ | $1$ | $1$ | $\delta$ | $1-\delta$
$2$ | $1-\delta$ | $0$ | $1$ | $2$ | $\delta-\delta^{2}$ | $1-\delta+\delta^{2}$
$3$ | $1-\delta$ | $1-\delta+\delta^{2}$ | $1$ | $3$ | $\delta-\delta^{2}+\delta^{3}$ | $1-\delta+\delta^{2}-\delta^{3}$
Table 1: The best-response dynamic of Example 5.1.

Example 5.1 suggests that even a non-negligible level of
influences/externalities can lead to the disappearance of best-response
cycles. As we will show in this section, this turns out to be a general
property: if every player’s total influences or total externalities are
smaller than her own weight, the game has a single Nash equilibrium and every
BRD and BRAD converges to it.

We introduce these games formally.

######  Definition 5.2.

A network $W$ has

  * •

weak influences if for every $i\in I$ it holds that $\sum_{j\in
I\setminus\\{i\\}}|w_{ij}|<1$,

  * •

weak externalities if for every $i\in I$ it holds that $\sum_{j\in
I\setminus\\{i\\}}|w_{ji}|<1$.

Networks with weak influences are characterized by row diagonally dominant
weight matrices, while those with weak externalities have column diagonally
dominant weight matrices. Games with weak influences satisfy Assumption 2b of
Parise and Ozdaglar, (2019), while both classes are covered by Scutari et al.,
(2014)’s Proposition 7.

It turns out that both classes of games have a unique Nash equilibrium and
every BRD and BRAD converges to it. Once again we can make use of rescaling:
any network which is rescalable into one of the two classes inherits the
uniqueness of the Nash equilibrium as well as the convergence properties. As
before, for $a\in\mathbb{R}^{n}$, $a>0$, define $V=(v_{ij})_{i,j\in I}$ as
$v_{ij}=w_{ij}a_{i}/a_{j}$. We show that the two classes are rescalable into
each other. Furthermore, a network is rescalable to either class if and only
if the spectral radius of $|W|-I_{n}$ is less than one, where $I_{n}$ is the
$n\times n$ identity matrix.

Recall that the _spectral radius_ $\rho(M)$ of a square matrix
$M\in\mathbb{C}^{n\times n}$ is the largest absolute value of its eigenvalues,
i.e.,

$\rho(M)=\max\\{|\lambda|:\lambda\in\mathbb{C}\text{ is an eigenvalue of
}M\\}.$

The next proposition states that a network $W$ can be rescaled into one with
weak influences and one with weak externalities if and only if
$\rho(|W|-I_{n})<1$.

######  Proposition 5.3.

The following statements are equivalent for $W$.

  1. 1.

There exists a scaling vector $a\in\mathbb{R}^{n}$, $a>0$ such that the
rescaled matrix $V$ has weak influences.

  2. 2.

There exists a scaling vector $a\in\mathbb{R}^{n}$, $a>0$ such that the
rescaled network $V$ has weak externalities.

  3. 3.

$\lim_{k\to\infty}(|W|-I_{n})^{k}=0$.

  4. 4.

$\rho(|W|-I_{n})<1$.

The fact that a diagonally dominant $W$ satisfies points 3 and 4 of
Proposition 5.3, as well as the equivalence of 3 and 4 are well-known in
linear algebra. Our characterization adds the notion of rescalability.

######  Proposition 5.4.

If $\rho(|W|-I_{n})<1$, then every game played on the network $W$ has a unique
Nash equilibrium.

By Ui, (2016), every positive definite $W$ has a unique equilibrium. If $W$ is
symmetric, then the condition $\rho(|W|-I_{n})<1$ implies positive
definiteness, but for an asymmetric $W$ neither condition is implied by the
other.

Proposition 5.4 follows from the fact that such networks are rescalable to
diagonally dominant matrices (Proposition 5.3), allowing us to use Moulin,
(1986), Chapter 6, Theorems 2 and 3. As a result, games played on such
networks are _dominance solvable_ Moulin, (1984), that is, iterated
elimination of dominated strategies leads to a unique solution. Thus, they
have a unique Nash equilibrium and convergent BRD. We now show a stronger
convergence property: the convergence of BRAD.

######  Theorem 5.5.

If $\rho(|W|-I_{n})<1$, then in every game played on network $W$, every BRAD
(and hence every BRD) converges to the unique Nash equilibrium.

Theorem 5.5 is related to Theorem 4 of Moulin, (1986), Chapter 6, which shows
local stability of equilibria with respect to BRD for which the Jacobian’s
spectral radius is less than one. Our condition is global due to the linear
best response functions of the network environment hence we have global
convergence. Another related result is Theorem 4.1 of Gabay and Moulin, (1980)
who shows convergence of BRAD where revisions arrive in a fixed order for
diagonally dominant Jacobians. Our result is more general in directed network
games as we cover a wider class of networks and in that revision opportunities
may arrive in any order.

Finally, we show that games played on such networks are best-response
potential games.

######  Proposition 5.6.

Consider a game played on a network $W$, and assume that $a\in\mathbb{R}^{n}$,
$a>0$ is a scaling vector such that the rescaled network $V$ has weak
externalities. Then, the function

$\phi^{\prime}(x)=-\sum_{i\in I}a_{i}|x_{i}-b_{i}(x)|$

is a best-response potential function of the game.

The proofs of Propositions 5.3 and 5.6, as well as that of Theorem 5.5 are
shown as an appendix.

As demonstrated by Example 3.2, a spectral radius equal to $1$ leads to best-
response cycles, hence these results are tight. Additionally, notice that the
BRCD may lead to cycles in this gameclass. For instance, the BRD shown in
Example 3.2 is a BRCD in Example 5.1 for $\delta=0.9$.

It is easy to show that a necessary condition of a network being rescalable to
one with weak externalities is that no pair of players have an amplifying
link, i.e., one where the product of weights is larger than the size of the
own effects in absolute value.

######  Lemma 5.7.

Let $W$ be given such that there exists an $a\in\mathbb{R}^{n}$, $a>0$ for
which the rescaled network $V$ is with weak externalities. Then, for every
$i,j\in I$ it holds that $|w_{ij}w_{ji}|<1$.

###### Proof.

Suppose that $|w_{ij}w_{ji}|>1$. Since $V$ has weak externalities we must have
$v_{ij},v_{ji}<1$. However,

$|v_{ij}v_{ji}|=|\frac{a_{i}}{a_{j}}w_{ij}\frac{a_{j}}{a_{i}}w_{ji}|>1,$

a contradiction. ∎

By Definition 5.2 it is clear that unlike networks that are rescalable to be
symmetric, those that are rescalable to exhibit weak influences or
externalities may allow one-way interactions as well as parasitic ones.
However, in the latter case, the link cannot be amplifying (Lemma 5.7), which
rules out the best-response cycles seen in Example 3.3. Additionally, as seen
in Example 3.2, if the network contains directed cycles we once again get
best-response cycles.

Without directed cycles, however, the network can always be rescaled into one
with weak externalities. We now formalize this fact starting with the
definition of directed acyclic networks.

######  Definition 5.8.

A network $W$ is called a directed acyclic network (DAN) if for every $i<j$,
$i,j\in I$ we have $w_{ij}=0$.

In other words, if $W$ is lower triangular, then the game is played on a DAN.
One can think of an equivalent characterization with upper triangular
matrices, or any permutation of players which leaves $W$ as a lower triangular
matrix. In Definition 5.8 players with lower indices are higher up in the
hierarchy, i.e. player $1$ is unaffected by any other player’s action, player
$2$ is only affected by player $1$, etc.

An economic application of this game is pollution management of a number of
cities with industrial zones located along a river. Each city decides on the
amount of money spent on cleaning the industrial waste in the river and their
decisions affect only those cities that are located downstream. The cities’
target values describe the point at which the marginal benefits of an extra
dollar’s worth of cleaner water are the same as the costs for that city.
Models of this problem include Ni and Wang, (2007) and Dong et al., (2012).

Games of the above nature introduce a hierarchy of players. Such hierarchies
are present in most production chains where goods – and therefore
externalities – flow downstream, or in some organizational networks such as
the military where orders are traveling down the chain of command. Directed
acyclic cycles have applications in biology as well among many other fields;
most trophic networks also have hierarchical features with apex predators on
the highest level and prey animals on lower levels.

We now show that every game played on a DAN is rescalable into one with weak
externalities.

######  Proposition 5.9.

For every DAN, $W$ there exists $a\in\mathbb{R}^{n}$, $a>0$ such that the
rescaled network, $V$ has weak externalities.

###### Proof.

Let $W$ be a DAN, i.e., we have $w_{ij}=0$ for every $i<j$. First, let
$a_{n}=1$. We will define the rest of the $a_{i}$’s recursively. Assume that
we have already defined $a_{n}$, $a_{n-1},\dots,a_{n-j+1}$. Let us choose
$a_{j}>0$ so that we have

$\displaystyle\sum_{k=j+1}^{n}a_{k}|w_{kj}|<a_{j}.$ (6)

Now we can verify that the rescaled matrix $V$ has weak externalities. Let
$j\in I$. We have

$\displaystyle\sum_{i\in I\setminus\\{j\\}}|v_{ij}|$ $\displaystyle=\sum_{i\in
I\setminus\\{j\\}}|w_{ij}|\frac{a_{i}}{a_{j}}$
$\displaystyle=\sum_{i=1}^{j-1}0\cdot\frac{a_{i}}{a_{j}}+\frac{1}{a_{j}}\sum_{i=j+1}^{n}|w_{ij}|a_{i}$
$\displaystyle<0+\frac{1}{a_{j}}\cdot a_{j}=1\qquad\text{ by (\ref{eq:
DAN}).}$

This concludes the proof. ∎

The following corollary regarding the convergence of BRD and BRAD is implied
by Theorem 5.5.

######  Corollary 5.10.

For every game played on a DAN, every BRD and BRAD converges to the game’s
unique Nash equilibrium.

##  6 Conclusion

In this paper we analyze directed network games, a generalization of the
private provision of public goods games model to include possibly non-
reciprocal relationships. These cover one-way interactions, unequal
interactions, and parasitism. While weighted networks and simple graphs are
very useful frameworks, more nuanced models of social and economic networks
should include non-reciprocal interactions.

While best-response dynamics on games played on symmetric networks are known
to converge to a Nash equilibrium due to the games’ potential structure, this
is not true in general for networks with asymmetric weight matrices. In this
paper we show that both one-way interactions and parasitic interactions can
create best-response cycles. This questions the interpretation of the Nash
equilibrium as the result of individual improvements by the players. Together
with other known problems of the Nash equilibrium both conceptual and
behavioral, equilibrium analysis of such games may be of questionable value in
settings with possibly non-reciprocal interactions.

There are classes of asymmetric networks, however, where the predictive power
of the Nash equilibrium is retained. In this paper we highlight two such
classes; those that can be rescaled into symmetric networks and those that are
rescalable to networks with weak influences or weak externalities. We
characterize the former type by transitive relative importance of players and
sign-symmetry of the weight matrix. Additionally, this class captures all
networks with quadratic best-response potential functions, indicating that
other network types with convergence require different approaches to identify.

The latter class captures individualistic social networks as well as
situations where the economic externalities have been internalized. We show
that these types are equivalent with respect to rescaling and any network with
a spectral radius less than one is rescalable to either. Such games are best-
response potential games, have a unique Nash equilibrium, and all BRDs and
BRADs converge to it. A necessary condition for a network to be rescalable to
one with weak externalities is the absence of amplifying links.

Directed acyclic networks can always be rescaled into networks with weak
externalities. This subclass imposes a hierarchy on the players; players are
only influenced by opponents on higher levels and only influence those on
lower levels. Directed acyclic networks have an established application in
economics in the pollution management of cities along a river or a river
network, but, since the hierarchical structure is widely studied, there are
other potential fields of application.

Our results unlock a number of insights into network games. The most apparent
general result is a negative one: the convergence properties of games played
on symmetric networks do not generalize well for the asymmetric case. For
directed cycles and parasitic interactions best-response cycles may appear,
thus identifying convergent classes of networks that include any of these
types of interactions are likely to require different methodologies than the
best-response potentials, rescaling, and spectral properties used in this
paper.

Our positive contribution consists of the full exploration of the idea of
rescalability into symmetric matrices as well as the identification of weak
influences/externalities as networks with convergent dynamics and the full
characterization of the latter class. On a technical level we identify all
network games with a quadratic potential structure and unlock a new class with
a different potential structure. We thus broaden the set of sufficient
conditions that guarantee convergence in network games. Finding a set of
sufficient and necessary conditions, or, failing that, broader sets of
sufficient conditions, is an important direction left for future research.

##  Appendix A Appendix

### Proofs for Section 4

#### Theorem 4.6

It is clear that statement 4 implies statement 3. We show the remaining three
implications.

###### Proof of 1 $\Rightarrow$ 4..

Suppose that the matrix $W$ can be rescaled into a symmetric matrix
$(v_{ij})_{i,j\in I}$ with the vector $a\in\mathbb{R}^{n}$, $a>0$, i.e., we
have $v_{ij}=w_{ij}a_{i}/a_{j}$. Let $G$ be any game on $W$. We now show that
the following quadratic function is a best-response potential of the game.

$\displaystyle\phi^{Q}(x)=\sum_{i\in
I}a_{i}^{2}x_{i}t_{i}-\frac{1}{2}\sum_{i\in I}\sum_{j\in
I}x_{i}x_{j}a_{i}a_{j}v_{ij}.$

For every $i\in I$, the partial derivative is as follows:

$\displaystyle\frac{\partial\phi^{Q}}{\partial x_{i}}(x)$
$\displaystyle=a_{i}^{2}t_{i}-\sum_{j\in I}x_{j}a_{j}a_{i}v_{ij}$
$\displaystyle=a_{i}^{2}t_{i}-\sum_{j\in I}x_{j}a_{i}^{2}w_{ij}$
$\displaystyle=a_{i}^{2}\left(t_{i}-\sum_{j\in I}x_{j}w_{ij}\right)$
$\displaystyle=a_{i}^{2}\cdot\tilde{b}_{i}(x)$

We used that $v_{ij}=v_{ji}$ and that $a_{j}a_{i}v_{ij}=w_{ij}a_{i}^{2}$.

Also, we have

$\displaystyle\frac{\partial^{2}\phi^{Q}}{\partial
x_{i}^{2}}(x)=-a_{i}^{2}w_{ii}=-a_{i}^{2}<0.$

Therefore, if $b_{i}(x)=\tilde{b}_{i}(x)$, then $\phi^{Q}(x)$ is maximal when
$\tilde{b}_{i}(x)=b_{i}(x)=x_{i}$. If $\tilde{b}_{i}(x)<0$ for some $x_{-i}$,
then the derivative of $\phi^{Q}$ with respect to $x_{i}$ is uniformly
negative on $[0,\overline{x}_{i}]$, so the maximum is achieved when $x_{i}=0$.
On the other hand, when $\overline{x}_{i}<\tilde{b}_{i}(x)$, then the
derivative of $\phi^{Q}$ with respect to $x_{i}$ is positive on
$[0,\overline{x}_{i}]$, and hence it takes its maximum in $\overline{x}_{i}$.

Therefore, for a fixed $x_{-i}$ vector the function $\phi^{Q}$ is maximal when
player $i$ is in her best response, so $\phi^{Q}$ is a best-response potential
function. ∎

###### Proof of 3 $\Rightarrow$ 2..

Suppose that there exists a quadratic best-response potential function,
$\phi^{Q}$, for a game $G$ on $W$. We show that the matrix $W$ is sign
symmetric and transitive.

Let the potential function be given as follows.

$\displaystyle\phi^{Q}(x)=\sum_{i\in I}p_{i}x_{i}-\frac{1}{2}\sum_{i\in
I}q_{ii}x_{i}^{2}-\sum_{i,j\in I,i>j}q_{ij}x_{i}x_{j},$

where $p_{i}\in\mathbb{R}$ for every $i\in I$ and $q_{ij}\in\mathbb{R}$ for
every $i,j\in I$, $i\geq j$. For $j>i$, we set $q_{ij}=q_{ji}$ for
convenience. With this notation, the partial derivative of $\phi^{Q}$ is:

$\displaystyle\frac{\partial\phi^{Q}}{\partial
x_{i}}(x)=p_{i}-q_{ii}x_{i}-\sum_{j\in I\setminus\\{i\\}}q_{ij}x_{j}.$ (7)

The function $\phi^{Q}$ is a best-response potential of the weighted network
game $G$, so for every $x\in X$ and for every $i\in I$, the partial derivative
of $\phi^{Q}$ is zero exactly when player $i$ is in her best response. Note
that we have $0<t_{i}<\overline{x}_{i}$ for every $i\in I$, this means that
$t_{i}=b_{i}(0)=\tilde{b}_{i}(0)\in(0,\overline{x}_{i})$ for every $i\in I$.
Therefore, there exists a neighborhood of $0$ where each player’s
unconstrained best response is equal to her best response. Let $\varepsilon>0$
be so that for every $x\in[0,\varepsilon]^{n}$ and for all $i\in I$ we have
$b_{i}(x)=\tilde{b}_{i}(x)$. For a fixed $i$, the functions
$\frac{\partial\phi^{Q}}{\partial x_{i}}(x)$ and $\tilde{b}_{i}(x)-x_{i}$ are
both linear in $x$ and they have the same zero set when
$x\in[0,\varepsilon]^{n}$. Hence, they must be equal up to a constant factor:
there exists $d_{i}\neq 0$ such that we have

$\displaystyle t_{i}-\sum_{j\in I}w_{ij}x_{j}$
$\displaystyle=\tilde{b}_{i}(x)-x_{i}=d_{i}\frac{\partial\phi^{Q}}{\partial
x_{i}}(x)=d_{i}\left(p_{i}-\sum_{j\in
I\setminus\\{i\\}}q_{ij}x_{j}-q_{ii}x_{i}\right)$ (8)

Additionally, as we are maximizing $\phi^{Q}$, the second derivative of
$\phi^{Q}$ with respect to $x_{i}$ has to be negative, so $q_{ii}>0$ for every
$i\in I$. From (8), we get the following for every $i,j\in I$.

$\displaystyle t_{i}$ $\displaystyle=d_{i}\cdot p_{i}$ $\displaystyle
w_{ii}=1$ $\displaystyle=d_{i}\cdot q_{ii}$ $\displaystyle w_{ij}$
$\displaystyle=d_{i}\cdot q_{ij}$ (9)

Since $q_{ii}>0$, we must have $d_{i}>0$ as well for all $i\in I$.

The first two equations give no constraints for $W$. We have to show that if
(9) holds for all $i,j\in I$, that implies the transitivity and the sign-
symmetry of the weight matrix $W$.

Since the $d_{i}$’s are positive and $q_{ij}=q_{ji}$, we have

$\operatorname{sgn}(w_{ij})=\operatorname{sgn}(d_{i}q_{ij})=\operatorname{sgn}(q_{ij})=\operatorname{sgn}(q_{ji})=\operatorname{sgn}(d_{j}q_{ji})=\operatorname{sgn}(w_{ji}),$

so the matrix $W$ is sign-symmetric.

Now let $3\leq s\leq n$, then for all $i_{1},i_{2},...,i_{s}\in I$ pairwise
distinct, we have

$\displaystyle w_{i_{1}i_{2}}w_{i_{2}i_{3}}\dots
w_{i_{s-1}i_{s}}w_{i_{s}i_{1}}$
$\displaystyle=(d_{i_{1}}q_{i_{1}i_{2}})(d_{i_{2}}q_{i_{2}i_{3}})\dots(d_{i_{s-1}}q_{i_{s-1}i_{s}})(d_{i_{s}}q_{i_{s}i_{1}})$
$\displaystyle=(d_{i_{1}}d_{i_{2}}\dots
d_{i_{s}})(q_{i_{1}i_{2}}q_{i_{2}i_{3}}\dots q_{i_{s-1}i_{s}}q_{i_{s}i_{1}})$
$\displaystyle=(d_{i_{1}}d_{i_{2}}\dots
d_{i_{s}})(q_{i_{2}i_{1}}q_{i_{3}i_{2}}\dots q_{i_{s}i_{s-1}}q_{i_{1}i_{s}})$
$\displaystyle=(d_{i_{2}}q_{i_{2}i_{1}})(d_{i_{3}}q_{i_{3}i_{2}})\dots(d_{i_{s}}q_{i_{s}i_{s-1}})(d_{i_{1}}q_{i_{1}i_{s}})$
$\displaystyle=w_{i_{2}i_{1}}w_{i_{3}i_{2}}\dots
w_{i_{s}i_{s-1}}w_{i_{1}i_{s}}$

using $w_{ij}=d_{i}q_{ij}$ for every $i,j\in I$. Therefore, the matrix $W$ is
transitive. ∎

###### Proof of 2 $\Rightarrow$ 1..

Suppose that the matrix $W$ is transitive and sign-symmetric. We would like to
find a scaling vector $a\in\mathbb{R}^{n}$, $a>0$, such that the rescaled
matrix is symmetric, i.e., for every pair $i,j\in I$ we have
$w_{ij}a_{i}/a_{j}=w_{ji}a_{j}/a_{i}$.

First, let us assume that the graph of $W$ is connected, so there exists a
path between any two players. If the graph is not connected, we follow the
described algorithm for every connected component of the graph separately in
order to define the vector $a$.

We start by ordering the players in the following way. Choose player 1
arbitrarily. Let the neighbors of player 1 be $2,\dots,n_{1}$. Players
$n_{1}+1,\dots,n_{2}$ are those neighbors of 2 that are not neighbors of 1,
and so on: players $n_{k}+1,n_{k}+2,\dots,n_{k+1}$ are those neighbors of
player $k+1$ that are not neighbors of players $1,2,\dots,k$. (If there are no
such players, then we have $n_{k}=n_{k+1}$.) Due to the sign-symmetry of $W$,
if two players are neighbors, there is a directed edge between them in both
directions. Hence, since $W$ is connected, there exists a directed path from
player 1 to every player, so after at most $n$ steps we reach all players.

Let $a_{1}=1$. We define all $a_{j}$’s for $j\geq 2$ recursively in the
following way. Suppose we have already defined $a_{1},a_{2},...,a_{j-1}$, and
$n_{i-1}<j\leq n_{i}$, so player $j$ is a neighbor of $i$ but not of players
$1,...,i-1$. In other words, $i$ is the neighbor of $j$ with the smallest
index. Clearly $i<j$, so $a_{i}$ is already defined. Also, we have $w_{ji}\neq
0\neq w_{ij}$, since $i$ and $j$ are neighbors. Let

$\displaystyle a_{j}=a_{i}\frac{\sqrt{|{w_{ij}}|}}{\sqrt{|{w_{ji}}|}}.$ (10)

Now we show that with this scaling vector $a$, for any $k,\ell\in I$ we have
$v_{k\ell}=v_{\ell k}$. Take any $k,\ell\in I$. If $k=\ell$, then
$w_{k\ell}=v_{k\ell}=v_{\ell k}=w_{\ell k}=1$, so we can assume that
$k\neq\ell$. Let $i_{1}\in I$ be so that $k$ is a neighbor of $i_{1}$, but not
of players $1,\dots,i_{1}-1$, so $n_{i_{1}-1}<k\leq n_{i_{1}}$. Similarly, let
$j_{1}\in I$ be so that $n_{j_{1}-1}<\ell\leq n_{j_{1}}$. For every
$m\in\mathbb{N}$, we define $i_{m}$ and $j_{m}$ recursively:

$\displaystyle i_{m+1}$ $\displaystyle=\min\\{i\in I:w_{i_{m}i}\neq 0\\},$
$\displaystyle j_{m+1}$ $\displaystyle=\min\\{j\in I:w_{j_{m}j}\neq 0\\}.$

Both sequences are decreasing, and they both stabilize when they reach 1. Let
$r,s\in\mathbb{N}$ be minimal so that $i_{r}=j_{s}$. Note that this is going
to happen, the latest when they are both equal to 1, and also note that from
this point on, the two sequences coincide. Therefore, we have
$k>i_{1}>\dots>i_{r}$ and $\ell>j_{1}>\dots>j_{s}$, and the numbers
$k,i_{1},\dots,i_{r-1},\ell,j_{1},\dots,j_{s}$ are distinct.

We can calculate $a_{k}$ as follows.

$\displaystyle a_{k}$
$\displaystyle=a_{i_{1}}\frac{\sqrt{|{w_{i_{1}k}}|}}{\sqrt{|{w_{ki_{1}}}|}}$
$\displaystyle=a_{i_{2}}\frac{\sqrt{|{w_{i_{2}i_{1}}}|}}{\sqrt{|{w_{i_{1}i_{2}}}|}}\frac{\sqrt{|{w_{i_{1}k}}|}}{\sqrt{|{w_{ki_{1}}}|}}$
$\displaystyle\ \ \vdots$
$\displaystyle=a_{i_{r}}\frac{\sqrt{|{w_{i_{r}i_{r-1}}}|}}{\sqrt{|{w_{i_{r-1}i_{r}}}|}}\dots\frac{\sqrt{|{w_{i_{2}i_{1}}}|}}{\sqrt{|{w_{i_{1}i_{2}}}|}}\frac{\sqrt{|{w_{i_{1}k}}|}}{\sqrt{|{w_{ki_{1}}}|}}$
$\displaystyle=a_{i_{r}}\left|\frac{w_{i_{r}i_{r-1}}\dots
w_{i_{2}i_{1}}w_{i_{1}k}}{w_{i_{r-1}i_{r}}\dots
w_{i_{1}i_{2}}w_{ki_{1}}}\right|^{\frac{1}{2}}.$

Similarly, we have

$\displaystyle a_{\ell}=a_{j_{s}}\left|\frac{w_{j_{s}j_{s-1}}\dots
w_{j_{2}j_{1}}w_{j_{1}\ell}}{w_{j_{s-1}j_{s}}\dots w_{j_{1}j_{2}}w_{\ell
j_{1}}}\right|^{\frac{1}{2}}.$

Now we can compute $v_{k\ell}$ using that $i_{r}=j_{s}$.

$\displaystyle v_{k\ell}$
$\displaystyle=\frac{a_{k}}{a_{\ell}}w_{k\ell}=a_{k}(a_{\ell})^{-1}w_{k\ell}$
$\displaystyle=\left(a_{i_{r}}\left|\frac{w_{i_{r}i_{r-1}}\dots
w_{i_{2}i_{1}}w_{i_{1}k}}{w_{i_{r-1}i_{r}}\dots
w_{i_{1}i_{2}}w_{ki_{1}}}\right|^{\frac{1}{2}}\right)\left(a_{j_{s}}\left|\frac{w_{j_{s}j_{s-1}}\dots
w_{j_{2}j_{1}}w_{j_{1}\ell}}{w_{j_{s-1}j_{s}}\dots w_{j_{1}j_{2}}w_{\ell
j_{1}}}\right|^{\frac{1}{2}}\right)^{-1}w_{k\ell}$
$\displaystyle=\left|\frac{(w_{i_{r}i_{r-1}}\dots
w_{i_{2}i_{1}}w_{i_{1}k})(w_{j_{s-1}j_{s}}\dots w_{j_{1}j_{2}}w_{\ell
j_{1}})}{(w_{i_{r-1}i_{r}}\dots
w_{i_{1}i_{2}}w_{ki_{1}})(w_{j_{s}j_{s-1}}\dots
w_{j_{2}j_{1}}w_{j_{1}\ell})}\right|^{\frac{1}{2}}w_{k\ell}$
$\displaystyle=\left|\frac{w_{i_{1}k}w_{i_{2}i_{1}}\dots
w_{i_{r}i_{r-1}}w_{j_{s-1}j_{s}}\dots w_{j_{1}j_{2}}w_{\ell
j_{1}}}{w_{ki_{1}}w_{i_{1}i_{2}}\dots w_{i_{r-1}i_{r}}w_{j_{s}j_{s-1}}\dots
w_{j_{2}j_{1}}w_{j_{1}\ell}}\right|^{\frac{1}{2}}\left|\frac{w_{k\ell}}{w_{\ell
k}}\right|^{\frac{1}{2}}\cdot\operatorname{sgn}(w_{k\ell})\sqrt{|{w_{k\ell}w_{\ell
k}}|}$ $\displaystyle=\left|\frac{w_{i_{1}k}w_{i_{2}i_{1}}\dots
w_{j_{s}i_{r-1}}w_{j_{s-1}j_{s}}\dots w_{j_{1}j_{2}}w_{\ell
j_{1}}w_{k\ell}}{w_{ki_{1}}w_{i_{1}i_{2}}\dots
w_{i_{r-1}j_{s}}w_{j_{s}j_{s-1}}\dots w_{j_{2}j_{1}}w_{j_{1}\ell}w_{\ell
k}}\right|^{\frac{1}{2}}\operatorname{sgn}(w_{k\ell})\sqrt{|{w_{k\ell}w_{\ell
k}}|}$

By the transitivity assumption for $k,i_{1},\dots i_{r-1},j_{s},\dots
j_{1},\ell\in I$, we have

$w_{ki_{1}}w_{i_{1}i_{2}}\dots w_{i_{r-1}j_{s}}w_{j_{s}j_{s-1}}\dots
w_{j_{1}\ell}w_{\ell k}=w_{i_{1}k}w_{i_{2}i_{1}}\dots
w_{j_{s}i_{r-1}}w_{j_{s-1}j_{s}}\dots w_{\ell j_{1}}w_{k\ell},$

and hence $v_{k\ell}=\operatorname{sgn}(w_{k\ell})\sqrt{|{w_{k\ell}w_{\ell
k}}|}$. Similarly, we have $v_{\ell k}=sgn(w_{\ell k})\sqrt{|{w_{\ell
k}w_{k\ell}}|}$. Since $W$ is sign-symmetric, these two numbers are equal, so
$v_{k\ell}=v_{\ell k}$ for all $k,\ell\in I$.

Finally, we show that the statement holds even if the graph of $W$ is not
connected. In this case we order the players in each component and define the
$a_{i}$’s for the components separately as described in the beginning of the
proof. Now take any $i,j\in I$. If $i$ and $j$ are the same connected
component, we have already shown that $v_{ij}=v_{ji}$. If they are in
different components, we know that $w_{ij}=w_{ji}=0$, therefore
$v_{ij}=0=v_{ji}$. This concludes the proof. ∎

### Proofs for Section 5

Let us introduce some notations and terminology that will be used in the
proofs of this section.

Recall that a matrix norm $\|\cdot\|\colon\mathbb{C}^{m\times
n}\to\mathbb{R}_{+}$ is an _induced norm_ if it is induced by vector norms on
$\mathbb{C}^{m}$ and $\mathbb{C}^{n}$, i.e., there exist norms
$\|\cdot\|_{\mathbb{C}^{m}}\colon\mathbb{C}^{m}\to\mathbb{R}_{+}$ and
$\|\cdot\|_{\mathbb{C}^{n}}\colon\mathbb{C}^{n}\to\mathbb{R}_{+}$ such that
for $M\in\mathbb{C}^{m\times n}$ we have

$\|M\|=\sup\\{\|Mx\|_{\mathbb{C}^{m}}:x\in\mathbb{C}^{n},\|x\|_{\mathbb{C}^{n}}=1\\}.$

This definition implies that we have

$\displaystyle\|Mx\|_{\mathbb{C}^{m}}\leq\|M\|\cdot\|x\|_{\mathbb{C}^{n}}$
(11)

for every $M\in\mathbb{C}^{m\times n}$ and $x\in\mathbb{C}^{n}$.

We will use a variation of the $\infty$-norm: the weighted maximum norm. Fix a
weight vector $u\in\mathbb{R}^{n}$, $u>0$. For $x\in\mathbb{C}^{n}$, let

$\|x\|_{\infty}^{u}=\max\\{|x_{i}|/u_{i}:1\leq i\leq n\\}.$

The induced matrix norm is the following: for
$M=(m_{ij})\in\mathbb{C}^{n\times n}$, we have

$\displaystyle\|M\|_{\infty}^{u}=\sup\\{\|Mx\|_{\infty}^{u}:\|x\|_{\infty}^{u}=1\\}=\max\left\\{\frac{1}{u_{i}}\sum_{j=1}^{n}u_{j}|m_{ij}|:1\leq
i\leq n\\}\right\\}.$ (12)

For a vector $u\in\mathbb{R}^{n}$, $u>0$, let $u^{-1}\in\mathbb{R}^{n}$ denote
the vector with entries $u_{i}^{-1}$. Let
$D_{u}=\mathrm{diag}(u_{1},u_{2},\dots,u_{n})\in\mathbb{R}^{n\times n}$, by
(12), we have

$\displaystyle\|M\|_{\infty}^{u}=\|D_{u}^{-1}MD_{u}\|_{\infty}.$

If $W$ is a network and $a\in\mathbb{R}^{n}$, $a>0$ is a scaling vector, then
for the rescaled matrix $V$ we have $v_{ij}=w_{ij}a_{i}/a_{j}$. Equivalently,
$V=D_{a}WD_{a}^{-1}$. Therefore, we have

$\displaystyle\|W\|_{\infty}^{a^{-1}}=\|D_{a^{-1}}^{-1}WD_{a^{-1}}\|_{\infty}=\|D_{a}WD_{a}^{-1}\|_{\infty}=\|V\|_{\infty}.$
(13)

For a matrix $M=(m_{ij})_{1\leq i,j\leq n}\in\mathbb{C}^{n\times n}$, we will
denote by $|M|\in\mathbb{R}_{+}^{n\times n}$ the matrix $(|m_{ij}|)_{1\leq
i,j\leq n}$.

We will use the following statement.

######  Proposition A.1 (Perron-Frobenius Theorem).

Let $M\in\mathbb{R}_{+}^{n\times n}$. Then, there exists a vector $z\geq 0$,
$z\neq 0$ such that $Mz=\rho(M)z$.

Furthermore, for any $\varepsilon>0$ there exists a vector $u>0$ such that
$\rho(M)<\|M\|_{\infty}^{u}<\rho(M)+\varepsilon$.

For a proof see Chapter 2, Proposition 6.6 of Bertsekas and Tsitsiklis,
(1989).

#### Proposition 5.3

Now we can characterize the networks that can be rescaled into one with weak
externalities.

###### Proof of Proposition 5.3.

Let us start by proving the equivalence of _2_ , _3_ , and _4_ :

_4_ $\Rightarrow$ _2_ : Assume that $\rho(|W|-I_{n})<1$. Then, by Proposition
A.1 for $0<\varepsilon<1-\rho(|W|-I_{n})$, there exists a vector
$u\in\mathbb{R}^{n}$, $u>0$ such that $\||W|-I_{n}\|_{\infty}^{u}<1$. Let us
use $u^{-1}=a$ as a scaling vector, i.e., let $v_{ij}=w_{ij}a_{i}/a_{j}$.
Then, we have

$\displaystyle
1>\||W|-I_{n}\|_{\infty}^{u}=\||W|-I_{n}\|_{\infty}^{a^{-1}}=\||V|-I_{n}\|_{\infty}=\|V-I_{n}\|_{\infty},$

so the matrix $V$ is row diagonally dominant. In other words, $V$ has weak
influences.

_2_ $\Rightarrow$ _3_ : Let $a\in\mathbb{R}^{n}$, $a>0$ be a scaling vector so
that the rescaled matrix $V$ has weak influences, i.e., $V$ is a row
diagonally dominant matrix. Therefore,
$\||V|-I_{n}\|_{\infty}=\|V-I_{n}\|_{\infty}<1$, so by (13), we have

$\displaystyle\||W|-I_{n}\|_{\infty}^{a^{-1}}=\|W-I_{n}\|_{\infty}^{a^{-1}}=\|V-I_{n}\|_{\infty}=\||V|-I_{n}\|_{\infty}<1.$

For any induced matrix norm $\|\cdot\|$, we have $\|MN\|\leq\|M\|\|N\|$ for
any matrices $M$, $N$. Therefore, $\|M^{k}\|\leq\|M\|^{k}$ for any
$k\in\mathbb{N}$ and any matrix $M$. Hence,

$\lim_{k\to\infty}\|(|W|-I_{n})^{k}\|_{\infty}^{a^{-1}}\leq\lim_{k\to\infty}\left(\||W|-I_{n}\|_{\infty}^{a^{-1}}\right)^{k}=0,$

since $\||W|-I_{n}\|_{\infty}^{a^{-1}}<1$. The norm of $(|W|-I_{n})^{k}$
converges to $0$, this is only possible if the matrices converge to the $0$
matrix, so we have $\lim_{k\to\infty}(|W|-I_{n})^{k}=0$.

_3_ $\Rightarrow$ _4_ : Assume that the limit is 0. Let $\lambda$ be any
eigenvalue of $|W|-I_{n}$, and $z\neq 0$ the corresponding eigenvector. Note
that $z$ is also an eigenvector of $(|W|-I_{n})^{k}$ with eigenvalue
$\lambda^{k}$. We have

$\displaystyle
0=\left(\lim_{k\to\infty}(|W|-I_{n})^{k}\right)z=\lim_{k\to\infty}(|W|-I_{n})^{k}z=\lim_{k\to\infty}\lambda^{k}z=\left(\lim_{k\to\infty}\lambda^{k}\right)z.$

Since $z\neq 0$, we must have $\lim_{k\to\infty}\lambda^{k}=0$, hence
$|\lambda|<1$. This is true for any eigenvalue, so $\rho(|W|-I_{n})<1$.

Hence, conditions _2_ , _3_ , and _4_ are equivalent. Now notice that for any
matrix $M$, we have $\lim_{k\to\infty}M^{k}=0$ if and only if
$\lim_{k\to\infty}(M^{\top})^{k}=0$. Therefore, we have the following
equivalences: the network $W$ can be rescaled into a row diagonally dominant
matrix $\Leftrightarrow$ $\lim_{k\to\infty}(|W|-I_{n})^{k}=0$
$\Leftrightarrow$ $\lim_{k\to\infty}((|W|-I_{n})^{\top})^{k}=0$
$\Leftrightarrow$ $W^{\top}$ can be rescaled into a row diagonally dominant
matrix $\Leftrightarrow$ $W$ can be rescaled into a column diagonally dominant
matrix.

Column diagonal dominance means exactly that the network has weak
externalities, so we proved the equivalence of _1_ with the other three
statements. ∎

#### Proposition 5.4

######  Lemma A.2.

Recall that $b\colon X\to X$ denotes the best response mapping. For any vector
$u\in\mathbb{R}^{n}$, $u>0$ and for all $x,x^{\prime}\in X$, we have

$\|b(x)-b(x^{\prime})\|_{\infty}^{u}\leq\|W-I_{n}\|_{\infty}^{u}\|x-x^{\prime}\|_{\infty}^{u}.$

###### Proof.

First, consider the unconstrained best responses $\tilde{b}(x)$ and
$\tilde{b}(x^{\prime})$. We have

$\displaystyle\|\tilde{b}(x)-\tilde{b}(x^{\prime})\|_{\infty}^{u}$
$\displaystyle=\|(t-(W-I_{n})x)-(t-(W-I_{n})x^{\prime})\|_{\infty}^{u}$
$\displaystyle=\|(W-I_{n})(x^{\prime}-x)\|_{\infty}^{u}$
$\displaystyle\leq\|W-I_{n}\|_{\infty}^{u}\|x-x^{\prime}\|_{\infty}^{u}\qquad\text{
by (\ref{eq: inducednorm}).}$

Notice that for every $i\in I$, we have
$|b_{i}(x)-b_{i}(x^{\prime})|\leq|\tilde{b}_{i}(x)-\tilde{b}_{i}(x^{\prime})|$.
Indeed, without loss of generality, we can assume that
$\tilde{b}_{i}(x)\leq\tilde{b}_{i}(x^{\prime})$ and we can verify the
inequality in all cases:

  * •

If $\tilde{b}_{i}(x)\leq\tilde{b}_{i}(x^{\prime})\leq 0$, then
$b_{i}(x)=b_{i}(x^{\prime})=0$, so
$|b_{i}(x)-b_{i}(x^{\prime})|=0\leq|\tilde{b}_{i}(x)-\tilde{b}_{i}(x^{\prime})|$.

  * •

If $\overline{x}_{i}\leq\tilde{b}_{i}(x)\leq\tilde{b}_{i}(x^{\prime})$, then
$b_{i}(x)=b_{i}(x^{\prime})=\overline{x}_{i}$, so
$|b_{i}(x)-b_{i}(x^{\prime})|=0\leq|\tilde{b}_{i}(x)-\tilde{b}_{i}(x^{\prime})|$.

  * •

If $\tilde{b}_{i}(x)\leq 0\leq\tilde{b}_{i}(x^{\prime})$ or if
$\tilde{b}_{i}(x)\leq\overline{x}_{i}\leq\tilde{b}_{i}(x^{\prime})$, then
$\tilde{b}_{i}(x)\leq b_{i}(x)\leq
b_{i}(x^{\prime})\leq\tilde{b}_{i}(x^{\prime})$, and hence
$|b_{i}(x)-b_{i}(x^{\prime})|\leq|\tilde{b}_{i}(x)-\tilde{b}_{i}(x^{\prime})|$.

  * •

If $0\leq\tilde{b}_{i}(x)\leq\tilde{b}_{i}(x^{\prime})\leq\overline{x}_{i}$,
then $b_{i}(x)=\tilde{b}_{i}(x)$ and
$b_{i}(x^{\prime})=\tilde{b}_{i}(x^{\prime})$, so
$|b_{i}(x)-b_{i}(x^{\prime})|=|\tilde{b}_{i}(x)-\tilde{b}_{i}(x^{\prime})|$.

Therefore, we have

$\displaystyle\|b_{i}(x)-b_{i}(x^{\prime})\|_{\infty}^{u}$
$\displaystyle=\sum_{i\in I}|b_{i}(x)-b_{i}(x^{\prime})|/u_{i}$
$\displaystyle\leq\sum_{i\in
I}|\tilde{b}_{i}(x)-\tilde{b}_{i}(x^{\prime})|/u_{i}$
$\displaystyle=\|\tilde{b}(x)-\tilde{b}(x^{\prime})\|_{\infty}^{u}$
$\displaystyle\leq\|W-I_{n}\|_{\infty}^{u}\|x-x^{\prime}\|_{\infty}^{u}.$

This concludes the proof of the lemma. ∎

###### Proof of Proposition 5.4.

By Proposition 5.3, there exists a scaling vector $a\in\mathbb{R}^{n}$, $a>0$
such that the rescaled matrix is row diagonally dominant, i.e., we have
$\|W-I_{n}\|_{\infty}^{a^{-1}}=\|V-I_{n}\|_{\infty}<1$.

Assume that $x^{*}$ and $x^{**}$ are two different Nash equilibria, i.e., we
have $b(x^{*})=x^{*}$, $b(x^{**})=x^{**}$ and $x^{*}\neq x^{**}$. By the
assumption that $\|W-I_{n}\|_{\infty}^{a^{-1}}<1$ and by Lemma A.2, we get

$\displaystyle\|x^{*}-x^{**}\|_{\infty}^{a^{-1}}=\|b(x^{*})-b(x^{**})\|_{\infty}^{a^{-1}}\leq\|W-I_{n}\|_{\infty}^{a^{-1}}\|x^{*}-x^{**}\|_{\infty}^{a^{-1}}<\|x^{*}-x^{**}\|_{\infty}^{a^{-1}}$

which is a contradiction. Hence, there exists a unique Nash equilibrium. ∎

#### Theorem 5.5

###### Proof of Theorem 5.5..

By Proposition 5.3, there exists a scaling vector $a\in\mathbb{R}^{n}$, $a>0$
such that the rescaled matrix is row diagonally dominant, i.e., we have
$\|W-I_{n}\|_{\infty}^{a^{-1}}=\|V-I_{n}\|_{\infty}<1$. Let
$\gamma=\|W-I_{n}\|_{\infty}^{a^{-1}}$, then $0\leq\gamma<1$.

By Proposition 5.4, there is a unique Nash equilibrium, let us denote it by
$x^{*}$. Notice that a BRD is a BRAD with parameter $0$, so it is enough to
prove the statement for BRAD’s. Consider any BRAD $(x^{k})_{k\in\mathbb{N}}$
with approach parameter $0\leq\beta<1$.

By the definition of the weighted maximum norm, for every $x,y\in X$ we have

$\displaystyle a_{i}|x_{i}-y_{i}|\leq\|x-y\|_{\infty}^{a^{-1}}.$ (14)

Hence, for an arbitrary $k\in\mathbb{N}$, we have

$\displaystyle a_{i^{k}}|b_{i^{k}}(x^{k})-x_{i^{k}}^{*}|$
$\displaystyle=a_{i^{k}}|b_{i^{k}}(x^{k})-b_{i^{k}}(x^{*})|$
$\displaystyle\leq\|b(x^{k})-b(x^{*})\|_{\infty}^{a^{-1}}\qquad\text{ by
(\ref{eq: weakthm1})}$
$\displaystyle\leq\|W-I_{n}\|_{\infty}^{a^{-1}}\|x^{k}-x^{*}\|_{\infty}^{a^{-1}}\qquad\text{
by Lemma \ref{le: contraction}}$
$\displaystyle=\gamma\cdot\|x^{k}-x^{*}\|_{\infty}^{a^{-1}}.$ (15)

For the next claim, note that since
$\gamma+\beta-\gamma\beta=1-(1-\gamma)(1-\beta)$, we have
$0\leq\gamma+\beta-\gamma\beta<1$.

######  Claim A.3.

For every $k\in\mathbb{N}$, we have

$\displaystyle
a_{i^{k}}|x_{i^{k}}^{k+1}-x_{i^{k}}^{*}|\leq(\gamma+\beta-\gamma\beta)\|x^{k}-x^{*}\|_{\infty}^{a^{-1}}.$

###### Proof.

Let us use the notation
$D=a_{i^{k}}^{-1}\|x^{k}-x^{*}\|_{\infty}^{a^{-1}}\in\mathbb{R}_{+}$. By (14),
we have $|x_{i^{k}}-x_{i^{k}}^{*}|\leq
a_{i^{k}}^{-1}\|x^{k}-x^{*}\|_{\infty}^{a^{-1}}=D$, and hence $x_{i^{k}}^{k}$
is contained in the interval of lenght $2D$ with midpoint $x_{i^{k}}^{*}$. By
(15), $b_{i^{k}}(x^{k})$ is in the interval of length $\gamma 2D$ centered at
$x_{i^{k}}^{*}$.

For $p,q\in\mathbb{R}$, let us use the notation $[p,q]=[\min\\{p,q\\},\
\max\\{p,q\\}]$ for the interval between $p$ and $q$.

From the definition of BRAD, we have $x_{i^{k}}^{k+1}\in[b_{i^{k}}(x^{k}),\
(1-\beta)b_{i^{k}}(x^{k})+\beta x_{i^{k}}^{k}]$, since this is the
$\beta$-contracted image of $[b_{i^{k}}(x^{k}),\ x_{i^{k}}^{k}]$ towards
$b_{i^{k}}(x^{k})$. This implies that $x_{i^{k}}^{k+1}$ is contained in the
$\beta$-contracted image of $[x_{i^{k}}^{*}-D,\ x_{i^{k}}^{*}+D]$ around
$b_{i^{k}}(x^{k})$, which is a point of $[x_{i^{k}}^{*}-\gamma D,\
x_{i^{k}}^{*}+\gamma D]$. Hence, we get the worst upper bound for
$x_{i^{k}}^{k+1}$ if $b_{i^{k}}(x^{k})$ takes the maximal value in
$[x_{i^{k}}^{*}-\gamma D,\ x_{i^{k}}^{*}+\gamma D]$, and the worst lower bound
if $b_{i^{k}}(x^{k})$ takes the minimal value in the interval. We can compute
these bounds: if $b_{i^{k}}(x^{k})=x_{i^{k}}^{*}+\gamma D$, then the
contracted image of $x_{i^{k}}^{*}+D$ is

$(1-\beta)(x_{i^{k}}^{*}+\gamma
D)+\beta(x_{i^{k}}^{*}+D)=x_{i^{k}}^{*}+(\gamma+\beta-\gamma\beta)D.$

Similarly, for $b_{i^{k}}(x^{k})=x_{i^{k}}^{*}-\gamma D$ we get the lower
bound

$(1-\beta)(x_{i^{k}}^{*}-\gamma
D)+\beta(x_{i^{k}}^{*}-D)=x_{i^{k}}^{*}-(\gamma+\beta-\gamma\beta)D.$

Therefore, $x_{i^{k}}^{k+1}\in[x_{i^{k}}^{*}-(\gamma+\beta-\gamma\beta)D,\
x_{i^{k}}^{*}+(\gamma+\beta-\gamma\beta)D]$, and hence

$a_{i^{k}}|x_{i^{k}}^{k+1}-x_{i^{k}}^{*}|\leq(\gamma+\beta-\gamma\beta)\|x^{k}-x^{*}\|_{\infty}^{a^{-1}},$

as desired. ∎

######  Claim A.4.

For every $m\in\mathbb{N}$ there exists $K(m)\in\mathbb{N}$ such that for all
$k\geq K(m)$ we have

$\|x^{k}-x^{*}\|_{\infty}^{a^{-1}}\leq(\gamma+\beta-\gamma\beta)^{m}\|x^{0}-x^{*}\|_{\infty}^{a^{-1}}.$

###### Proof.

We prove the statement by induction on $m$. For $m=0$, it clearly holds with
$K(0)=0$. Assume that $K(m-1)$ exists, and we would like to find $K(m)$.

Take an arbitrary $k\geq K(m-1)$ and let player $i$ be the one who moves at
time $k$. Then, we have

$\displaystyle a_{i}|x_{i}^{k+1}-x_{i}^{*}|$
$\displaystyle\leq(\gamma+\beta-\gamma\beta)\|x^{k}-x^{*}\|_{\infty}^{a^{-1}}\qquad\text{
by Claim \ref{claim: weak1}}$
$\displaystyle\leq(\gamma+\beta-\gamma\beta)(\gamma+\beta-\gamma\beta)^{m-1}\|x^{0}-x^{*}\|_{\infty}^{a^{-1}}\quad\text{
by ind.~{}hypothesis}$
$\displaystyle=(\gamma+\beta-\gamma\beta)^{m}\|x^{0}-x^{*}\|_{\infty}^{a^{-1}}.$

Therefore, we can see that
$a_{i}|x_{i}^{\ell}-x_{i}^{*}|\leq\gamma^{m}\|x^{0}-x^{*}\|_{\infty}^{a^{-1}}$
for all $\ell>k$, since it is true after every move of player $i$, and it
remains true in all other players’ turns because that does not change the
action of player $i$.

For every $i\in I$, let $k_{i}$ be the first time player $i$ moves after
$K(m-1)$. Let

$K(m)=\max\\{k_{i}:i\in I\\}+1.$

By time $K(m)$, every player moved at least once since $K(m-1)$, so for every
$i\in I$ and all $k\geq K(m)$, we have
$a_{i}|x_{i}^{k}-x_{i}^{*}|\leq(\gamma+\beta-\gamma\beta)^{m}\|x^{0}-x^{*}\|_{\infty}^{a^{-1}}$.
Therefore, we also have

$\displaystyle\|x^{k}-x^{*}\|_{\infty}^{a^{-1}}=\max\\{a_{i}|x_{i}^{k}-x_{i}^{*}|:i\in
I\\}\leq(\gamma+\beta-\gamma\beta)^{m}\|x^{0}-x^{*}\|_{\infty}^{a^{-1}}.$

This proves the statement for every $m\in\mathbb{N}$. ∎

Now we can show the convergence of the BRAD $(x^{k})_{k\in\mathbb{N}}$ to the
Nash equilibrium $x^{*}$. Take any $\varepsilon>0$, then there exists
$m\in\mathbb{N}$ such that
$(\gamma+\beta-\gamma\beta)^{m}\|x^{0}-x^{*}\|_{\infty}^{a^{-1}}<\varepsilon$,
since $\gamma+\beta-\gamma\beta<1$. Therefore, if $k\geq K(m)$ from Claim A.4,
then we have

$\displaystyle\|x^{k}-x^{*}\|_{\infty}^{a^{-1}}\leq(\gamma+\beta-\gamma\beta)^{m}\|x^{0}-x^{*}\|_{\infty}^{a^{-1}}<\varepsilon.$

Hence, $(x^{k})_{k\in\mathbb{N}}$ converges to the Nash equilibrium $x^{*}$. ∎

#### Proposition 5.6

######  Lemma A.5.

If the network $W$ can be rescaled into a network with weak externalities
using the vector $a\in\mathbb{R}^{n}$, $a>0$, then for every $j\in I$, we have
$\sum_{i\in I\setminus\\{j\\}}a_{i}|w_{ij}|<a_{j}$.

###### Proof.

Take a vector $a\in\mathbb{R}^{n}$, $a>0$ such that the rescaled network $V$
is with weak externalities. By definition, this means that for every $j\in I$,
we have

$\displaystyle\sum_{i\in I\setminus\\{j\\}}|v_{ij}|$
$\displaystyle<|v_{jj}|=1$ $\displaystyle\sum_{i\in
I\setminus\\{j\\}}\frac{a_{i}}{a_{j}}|w_{ij}|$ $\displaystyle<|w_{jj}|=1$
$\displaystyle\sum_{i\in I\setminus\\{j\\}}a_{i}|w_{ij}|$
$\displaystyle<a_{j}.$

∎

######  Lemma A.6.

Let $i,j\in I$ and let $(x^{k})_{k\in\mathbb{N}}$ be a best-response dynamic.
If player $i$’s action changes by $\Delta$, player $j$’s best response changes
by a maximum of $|\Delta\cdot w_{ji}|$, i.e., we have
$|b_{j}(x^{k})-b_{j}(x^{k+1})|\leq|w_{ji}|\cdot|x_{i}^{k}-x_{i}^{k+1}|$ for
any $k\in\mathbb{N}$.

###### Proof.

By (3), the unconstrained best response function of player $j$ is
$\tilde{b}_{j}(x)=t_{j}-\sum_{i\in I\setminus\\{j\\}}w_{ji}x_{i}$. Therefore,
if $\tilde{b}_{j}(x)\in(0,\overline{x}_{j})$, then we have
$\tilde{b}_{j}(x)=b_{j}(x)$, so $\partial b_{j}(x)/\partial x_{i}=w_{ji}$. If
$\tilde{b}_{j}(x)\notin[0,\overline{x}_{j}]$, then we know that
$b_{j}(x)\in\\{0,\overline{x}_{j}\\}$, so $\partial b_{j}(x)/\partial
x_{i}=0$. Hence, by the mean value theorem, if player $j$’s action changes by
$\Delta$, her best response can change by at most $|\Delta\cdot w_{ji}|$. ∎

###### Proof of Proposition 5.6..

Let $i\in I$ and fix $x\in X$. We need to prove that only $b_{i}(x)$ maximizes
$\phi^{\prime}(\cdot,x_{-i})$. Assume that we have
$x_{i}^{1}\in\operatorname*{argmax\,}_{x_{i}\in
X_{i}}\phi^{\prime}(x_{i},x_{-i})$. Let $x^{1}=(x_{i}^{1},x_{-i})$ and
$i^{1}=i$. Then $x^{2}=(b_{i}(x^{1}),x_{-i})=(x^{2}_{j})_{j\in I}$. We have
that $\phi^{\prime}(x^{1})\geq\phi^{\prime}(x^{2})$ since
$x_{i}^{1}\in\operatorname*{argmax\,}_{x_{i}\in
X_{i}}\phi^{\prime}(x_{i},x_{-i}^{1})$. Therefore, we have

$\displaystyle 0$ $\displaystyle\geq\phi^{\prime}(x^{2})-\phi^{\prime}(x^{1})$
$\displaystyle=-\left(\sum_{j\in
I\setminus\\{i\\}}a_{j}|x^{2}_{j}-b_{j}(x^{2})|\right)-\left(-\sum_{j\in
I}a_{j}|x^{1}_{j}-b_{j}(x^{1})|\right)$
$\displaystyle=a_{i}|x^{1}_{i}-b_{i}(x^{1})|+\sum_{j\in
I\setminus\\{i\\}}a_{j}\left(|x^{1}_{j}-b_{j}(x^{1})|-|x^{1}_{j}-b_{j}(x^{2})|\right)$
$\displaystyle\geq a_{i}|x^{1}_{i}-b_{i}(x^{1})|-\sum_{j\in
I\setminus\\{i\\}}a_{j}|b_{j}(x^{1})-b_{j}(x^{2})|$ $\displaystyle\geq
a_{i}|x^{1}_{i}-b_{i}(x^{1})|-\sum_{j\in
I\setminus\\{i\\}}a_{j}|w_{ji}||x_{i}^{1}-x_{i}^{2}|\qquad\text{by Lemma
\ref{le: effectonbr}}$ $\displaystyle=\left(a_{i}-\sum_{j\in
I\setminus\\{i\\}}a_{j}|w_{ji}|\right)|x_{i}^{1}-b_{i}(x^{1})|$
$\displaystyle\geq 0\qquad\text{ by Lemma \ref{le: rescaleweak}.}$

Hence, we must have equality everywhere. Since $a_{i}-\sum_{j\in
I\setminus\\{i\\}}a_{j}|w_{ji}|>0$, equality holds in the last line if and
only if $|x_{i}^{1}-b_{i}(x^{1})|=0$, i.e., iff
$x_{i}^{1}=b_{i}(x^{1})=b_{i}(x)$. Thus, we have
$\operatorname*{argmax\,}_{x_{i}\in
X_{i}}\phi^{\prime}(x_{i},x_{-i})=\\{b_{i}(x)\\}$, so $\phi^{\prime}$ is a
best-response potential function. ∎

###  A.1 Cycles in large networks with random weights

In this part we show that if the (ex-ante) possibility of one-way or parasitic
interactions exists in an interaction network, even if the probabilities are
small, then large networks will have a best-response cycle almost surely. The
intuition for this is quite simple: With randomized player interactions
directed cycles or parasitic links producing the cycles seen in Examples 3.2
and 3.3 may appear with positive probability. As the number of players goes to
infinity, a network allowing for best-response cycles will appear almost
surely.

We now turn to a formal description of the above idea. For $i,j\in I$ with
$i\neq j$ let the weight $w_{ij}$ be the realization of a random variable
denoted by $\tilde{w}_{ij}$.

######  Assumption A.7.

For every $i,i^{\prime},j,j^{\prime}\in I$ such that
$\\{i,j\\}\neq\\{i^{\prime},j^{\prime}\\}$ the variables $\tilde{w}_{ij}$ and
$\tilde{w}_{i^{\prime}j^{\prime}}$ are independent.

Assumption A.7 states that any two distributions producing weights not
belonging to the same pair of players are independent. This assumption is made
mostly for convenience, our results may be obtained with less stringent
assumptions. Crucially, we allow the two weights describing the interaction
between a pair of players to be dependent.

Let $w^{-},\underline{w},\overline{w}>0$ be given such that
$\underline{w}<\overline{w}$. We introduce the following notation:

  1. 1.

$P_{0}=\min_{i,j\in I}(P(\tilde{w}_{ij}=\tilde{w}_{ji}=0))$,

  2. 2.

$P_{1}(\underline{w})=\min_{i,j\in
I}(\min\\{P(\tilde{w}_{ij}\geq\underline{w},\tilde{w}_{ji}=0),P(\tilde{w}_{ji}\geq\underline{w},\tilde{w}_{ij}=0)\\})$,

  3. 3.

$P_{2}(w^{-},\underline{w},\overline{w})=$
$\min_{i,j\in
I}(\min\\{P(\tilde{w}_{ij}\in[\underline{w},\overline{w}],\tilde{w}_{ji}\leq-w^{-}),P(\tilde{w}_{ji}\in[\underline{w},\overline{w}],\tilde{w}_{ij}\leq-w^{-})\\})$.

In words, the smallest probability that two players are indifferent to one
another is denoted by $P_{0}$, the smallest probability of there being a one-
directional link of at least strength $\underline{w}$ between an ordered pair
is denoted by $P_{1}(\underline{w})$, and the smallest probability that an
ordered pair has a parasitic link such that the parasite’s effect on the host
is at least $w^{-}$ and the host’s effect on the parasite falls into the
interval $[\underline{w},\overline{w}]$ is denoted by
$P_{2}(w^{-},\underline{w},\overline{w})$.

######  Definition A.8.

We say that the random process generating a network satisfies/allows for

  * •

no forced interaction (NFI) if $P^{0}>0$,

  * •

directed interactions (DI) if there exists $\underline{w}>0$ such that
$P_{1}(\underline{w})>0$.

  * •

biparasitism (BP) if there exist $w^{-},\underline{w},\overline{w}>0$ such
that $P_{2}(w^{-},\underline{w},\overline{w})>0$,

The properties listed in Definition A.8 are interpreted as follows: NFI means
that any two players have a positive probability of mutual indifference,
meaning that at least a fraction of interaction weights will be zero. This is
a feature of the most basic growing random network models where average degree
of players is kept constant as $n$ goes to infinity, thus, in fact, most
interaction weights are zero. Our assumption is much weaker. DI means that
every player may unilaterally influence any other with positive probability, a
possibility of one-way indifference, while BP means that any player may be a
parasite of any other with positive probability, an ex-ante possibility of
parasitism between any ordered pair. Notice that the three properties impose
no restriction on the ex-post realizations of weights. Since all three numbers
can be arbitrarily small, the ex-ante restriction is also mild.

######  Theorem A.9.

As $n$ goes to infinity, if the random process generating the network
satisfies NFI and DI, then the resulting directed network game allows for a
best-response cycle almost surely.

###### Proof.

Let $\underline{t}=\min_{i\in I}t_{i}$ and let $\overline{t}=\max_{i\in
I}t_{i}$. For a fixed $w^{-},\underline{w},\overline{w}$, we shorten the
notations $P_{1}(\underline{w})$ and $P_{2}(w^{-},\underline{w},\overline{w})$
to $P_{1}$ and $P_{2}$, respectively.

Let $m$ be such that $m\underline{t}\underline{w}\geq\overline{t}$. For some
$\ell\in\mathbb{N}$ fix $n$ such that $n=3m\ell$.

We construct three sets of $m$ players, $I_{1}$, $I_{2}$, and $I_{3}$, such
that

  * •

for every pair of players $i,j$, $i\neq j$, belonging to the same group,
$w_{ij}=w_{ji}=0$, and

  * •

for every trio of players $i^{1}\in I^{1}$, $i^{2}\in I^{2}$, $i^{3}\in
I^{3}$, it holds that $w_{i^{1}i^{2}}=w_{i^{2}i^{3}}=w_{i^{3}i^{1}}=0$,
$w_{i^{1}i^{3}},w_{i^{2}i^{1}},w_{i^{3}i^{2}}>\underline{w}$.

The probability of such realization of weights occurring is at least
$P_{0}^{3m(m-1)/2}P_{1}^{3m^{2}}$ which is positive by properties NFI and DI.

We now show that, given such a group of players, no matter the realization of
any other weights in the network, the game has a best-response cycle.

Let $x^{1},x^{2},x^{3}\in X$ be given as follows: For $j\in\\{1,2,3\\}$
$x^{j}_{i}=0$ if $i\notin I^{j}$ and $x^{j}_{i}=t_{i}$ if $i\in I^{j}$. Let
$x^{-1},x^{-2},x^{-3}\in X$ be given as follows: for every $i\in I$
$x^{-1}_{i}=\max\\{x^{2}_{i},x^{3}_{i}\\}$,
$x^{-2}_{i}=\max\\{x^{1}_{i},x^{3}_{i}\\}$,
$x^{-3}_{i}=\max\\{x^{1}_{i},x^{2}_{i}\\}$.

In profile $x^{1}$, only the members of group $I^{1}$ contribute a positive
amount, every other player contributes zero. Since
$ms\underline{w}\geq\overline{t}$, all members of group $I^{2}$ are at best
response. Since the members of group $I^{3}$ receive $0$, the profile $x^{-2}$
follows $x^{1}$ if all members of $I^{3}$ move to their best responses in any
order. Since $ms\underline{w}\geq
m\underline{t}\underline{w}\geq\overline{t}$, the best response of the members
of group $I^{1}$ to $x^{-2}$ is to move to $0$. Hence the profile $x^{3}$
follows $x^{-2}$ by the members of $I^{1}$ moving to their best responses in
any order. Very similarly, $x^{-1}$ follows $x^{3}$, $x^{2}$ follows $x^{-1}$,
$x^{-3}$ follows $x^{2}$, and $x^{1}$ follows $x^{-3}$, completing the cycle.

The probability of three such groups forming in a population of $3m\ell$
players is at least

$1-(1-P_{0}^{3m(m-1)/2}P_{1}^{3m^{2}})^{\ell}.$

Let $E_{n}$ denote the event that a best-response cycle exists in a game of
$n$ players. For every $n\geq 0$ it is clear that $P(E_{n})\leq P(E_{n+1})\leq
1$, so the sequence $P(E_{n})$ is convergent. Therefore, we have

$\lim_{n\to\infty}P(E_{n})=\lim_{\ell\to\infty}P(E_{3m\ell})\geq
1-\lim_{\ell\to\infty}(1-P_{0}^{3m(m-1)/2}P_{1}^{3m^{2}})^{\ell}=1.$

∎

######  Theorem A.10.

For $i\in I$ let $\overline{x}_{i}=\infty$.

As $n$ goes to infinity, if the random process generating the network
satisfies NFI and BP such that $\overline{w}<\min_{i\in I}t_{i}/\max_{i\in
I}t_{i}$, then the resulting directed network game allows for a best-response
cycle almost surely.

###### Proof.

We introduce the notation $z=\underline{t}-\overline{w}\overline{t}$. Notice
that $z>0$ by the assumption of the Theorem. Fix $m\in\mathbb{N}$ such that
$\overline{t}-\underline{w}\underline{t}<m\underline{w}z$.

We construct a set of $m$ players, $I_{1}$, and a player $j\in I\setminus
I_{1}$ such that

  * •

for every pair of players $i,i^{\prime}\in I_{1}$, $i\neq i^{\prime}$, we have
$w_{ii^{\prime}}=w_{i^{\prime}i}=0$, and

  * •

for every $i\in I_{1}$ it holds that $w_{ij}\in[\underline{w},\overline{w}]$
and $w_{ji}\leq-w^{-}$.

The probability of such a realization of weights happening between $m+1$
players is at least $P_{0}^{m(m-1)/2}P_{2}^{m}$, which is positive due to
properties NFI and BP.

We now show that, given such a group of players, no matter the realization of
any other weights in the network, the game has a best-response cycle. For
$i\in I_{1}$ let $z_{i}=t_{i}-w_{i1}t_{j}$. Notice that $z_{i}\geq z>0$. Let
$x^{1},x^{2},x^{3},x^{4}$ be given as follows: For every $i\notin
I_{1}\cup\\{j\\}$ $x^{1}_{i}=x^{2}_{i}=x^{3}_{i}=x^{4}_{i}=0$, let
$x^{1}_{j}=x^{2}_{j}=t_{j}$ and $x^{3}_{j}=x^{4}_{j}=t_{j}-w_{ji}z_{i}$, while
for $i\in I_{1}$ let $x^{1}_{i}=x^{4}_{i}=0$ and $x^{2}_{i}=x^{3}_{i}=z_{i}$.

In profile $x^{1}$, player $j$ contributes her target, the members of $I^{1}$
contribute zero. Since $b_{i}(x^{1})=z_{i}$, a non-negative value by
$z_{j}\geq z>0$, the profile $x^{2}$ follows from $x^{1}$ by the members of
$I^{1}$ moving to best response in any order. Since $\overline{x}_{j}=\infty$,
it also holds that $b_{j}(x^{2})=t_{j}-\sum_{i\in I^{1}}w_{ji}z_{i}$, a non-
negative value by $w_{ji}\leq-w^{-}<0$, hence the profile $x^{3}$ follows from
$x^{2}$ by $j$ moving to her best response. For $i\in I_{1}$ we have

$\hat{b}_{i}(x^{3})=z_{i}+w_{ij}\sum_{i^{\prime}\in
I^{1}}w_{ji^{\prime}}z_{i^{\prime}}\leq\overline{t}-\underline{w}\underline{t}-m\underline{w}z<0$

by the choice of $m$. Hence, for $i\in I^{1}$ we have $b_{i}(x^{3})=0$ and
$x^{4}$ follows $x^{3}$ by the members of $I^{1}$ moving to best response in
any order. Finally, $x^{1}$ follows $x^{4}$ by player $j$ moving to her best
response, completing the cycle.

The probability of such groups forming in a population of $(m+1)\ell$ players
is at least

$1-(1-P_{0}^{m(m-1)/2}P_{2}^{m})^{\ell}.$ (16)

Let $E_{n}$ denote the event that a best-response cycle exists in a game of
$n$ players. For every $n\geq 0$ it is clear that $P(E_{n})\leq P(E_{n+1})\leq
1$, hence the sequence $P(E_{n})$ is convergent. Then we have

$\lim_{n\to\infty}P(E_{n})=\lim_{\ell\to\infty}P(E_{(m+1)\ell})\geq
1-\lim_{\ell\to\infty}(1-P_{0}^{m(m-1)/2}P_{2}^{m})^{\ell}=1.$

∎

Theorems A.9 and A.10 establish that, given NFI, either of BP and DI are
enough to ensure that large networks will allow for best-response cycles with
some additional assumptions on the parameters in the latter case. These
properties are mild, in terms of the restrictions they impose on the
probability distributions on the weights, as well as intuitive, in terms of
what they mean for the links between the players. In large networks, even
small likelihood of one-way interactions or parasitic interactions lead to the
cycles similar to Examples 3.2 and 3.3 almost surely. Thus we identify
directed cycles and parasitism as important stumbling blocks of convergence.
Both theorems generalize to non-independent distributions of weights between
different pairs of players if the probabilities defined in Definition A.8 are
positive, conditional on the possible realizations of other weights.

## References

  * Ballester et al., (2006) Ballester, C., Calvó-Armengol, A., and Zenou, Y. (2006).  Who’s who in networks. wanted: The key player.  Econometrica, 74(5):1403–1417.
  * Ballester et al., (2010) Ballester, C., Zenou, Y., and Calvó-Armengol, A. (2010).  Delinquent networks.  Journal of the European Economic Association, 8(1):34–61.
  * (3) Bayer, P., Herings, P., and Peeters, R. (2019a).  Farsighted manipulation and exploitation in networks.  GSBE Research Memoranda, 023.  Maastricht University.
  * (4) Bayer, P., Herings, P. J.-J., Peeters, R., and Thuijsman, F. (2019b).  Adaptive learning in weighted network games.  Journal of Economic Dynamics and Control, 105:250–264.
  * Belhaj et al., (2014) Belhaj, M., Bramoullé, Y., and Deroïan, F. (2014).  Network games under strategic complementarities.  Games and Economic Behavior, 88(C):310–319.
  * Bertsekas and Tsitsiklis, (1989) Bertsekas, D. P. and Tsitsiklis, J. N. (1989).  Parallel and Distributed Computation: Numerical Methods.  Prentice-Hall, Inc., Upper Saddle River, NJ, USA.
  * Bervoets et al., (2018) Bervoets, S., Bravo, M., and Faure, M. (2018).  Learning with minimal information in continuous games.  arXiv preprint, 1806.11506.
  * Bervoets and Faure, (2019) Bervoets, S. and Faure, M. (2019).  Stability in games with continua of equilibria.  Journal of Economic Theory, 179(C):131–162.
  * Blume et al., (2010) Blume, L. E., Brock, W. A., Durlauf, S. N., and Ioannides, Y. M. (2010).  Identification of Social Interactions.  Economics Series 260, Institute for Advanced Studies.
  * Bozóki et al., (2010) Bozóki, S., Fülöp, J., and Rónyai, L. (2010).  On optimal completion of incomplete pairwise comparison matrices.  Mathematical and Computer Modelling, 52(1-2):318–333.
  * Bramoullé and Kranton, (2007) Bramoullé, Y. and Kranton, R. (2007).  Public goods in networks.  Journal of Economic Theory, 135(1):478–494.
  * Bramoullé et al., (2014) Bramoullé, Y., Kranton, R., and D’Amours, M. (2014).  Strategic Interaction and Networks.  American Economic Review, 104(3):898–930.
  * Cachon and Camerer, (1996) Cachon, G. P. and Camerer, C. (1996).  The sunk cost fallacy, forward induction and behavior in coordination games.  Quarterly Journal of Economics, 111:165–194.
  * Cason and Friedman, (1997) Cason, T. and Friedman, D. (1997).  Price formation in single call markets.  Econometrica, 65(2):311–346.
  * Dong et al., (2012) Dong, B., Ni, D., and Wang, Y. (2012).  Sharing a polluted river network.  Environmental and Resource Economics, 53(3):367–387.
  * Dubey et al., (2006) Dubey, P., Haimanko, O., and Zapechelnyuk, A. (2006).  Strategic complements and substitutes, and potential games.  Games and Economic Behavior, 54(1):77–94.
  * Farkas et al., (1999) Farkas, A., Rózsa, P., and Stubnya, E. (1999).  Transitive matrices and their applications.  Linear Algebra and its Applications, 302-303:423–433.
  * Gabay and Moulin, (1980) Gabay, D. and Moulin, H. (1980).  On the uniqueness and stability of Nash equilibria in noncooperative games.  In Bensoussan, A., Kleindorfer, P. R., and Tapiero, C. S., editors, Applied Stochastic Control in Econometrics and Management Science, pages 271–294. North-Holland.
  * Golub and Jackson, (2012) Golub, B. and Jackson, M. O. (2012).  How homophily affects the speed of learning and best-response dynamics.  The Quarterly Journal of Economics, 127(3):1287–1338.
  * Jensen, (2010) Jensen, M. (2010).  Aggregative games and best-reply potentials.  Economic Theory, 43(1):45–66.
  * Kagel and Levin, (1999) Kagel, J. and Levin, D. (1999).  Common value auctions with insider information.  Econometrica, 67(5):1219–1238.
  * Kelly, (2011) Kelly, F. (2011).  Reversibility and stochastic networks.  Cambridge University Press.
  * König et al., (2019) König, M. D., Liu, X., and Zenou, Y. (2019).  R&d networks: Theory, empirics, and policy implications.  The Review of Economics and Statistics, 101(3):476–491.
  * Kukushkin, (2005) Kukushkin, N. S. (2005).  Strategic supplements in games with polylinear interactions.  EconWPA Paper, 411008.
  * Kukushkin, (2015) Kukushkin, N. S. (2015).  Cournot tatonnement and potentials.  Journal of Mathematical Economics, 59:117 – 127.
  * Monderer and Shapley, (1996) Monderer, D. and Shapley, L. S. (1996).  Potential games.  Games and Economic Behavior, 14(1):124–143.
  * Moulin, (1984) Moulin, H. (1984).  Dominance solvability and cournot stability.  Mathematical Social Sciences, 7:83–102.
  * Moulin, (1986) Moulin, H. (1986).  Game Theory for the Social Sciences.  New York University Press, Washington Square, New York, USA.
  * Nagel and Vriend, (1999) Nagel, R. and Vriend, N. J. (1999).  An experimental study of adaptive behavior in an oligopolistic market game.  Journal of Evolutionary Economics, 9(1):27–65.
  * Ni and Wang, (2007) Ni, D. and Wang, Y. (2007).  Sharing a polluted river.  Games and Economic Behavior, 60(1):176–186.
  * Parise and Ozdaglar, (2019) Parise, F. and Ozdaglar, A. (2019).  A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis.  Games and Economic Behavior, 114(C):47–82.
  * Richefort and Point, (2010) Richefort, L. and Point, P. (2010).  Governing a common-pool resource in a directed network.  FEEM Nota di Lavoro, 147.2010.
  * Saaty, (1988) Saaty, T. L. (1988).  What is the analytic hierarchy process?  In Mitra, G., Greenberg, H. J., Lootsma, F. A., Rijkaert, M. J., and Zimmermann, H. J., editors, Mathematical Models for Decision Support, pages 109–121. Springer, Berlin, Heidelberg.
  * Sandler and Hartley, (1995) Sandler, T. and Hartley, K. (1995).  The Economics of Defense.  Cambridge University Press.
  * Sandler and Hartley, (2007) Sandler, T. and Hartley, K. (2007).  Defense in a Globalized World: An Introduction.  In Hartley, K. and Sandler, T., editors, Handbook of Defense Economics, volume 2, chapter 20, pages 607–621. Elsevier.
  * Scutari et al., (2014) Scutari, G., Facchinei, F., Pang, J.-S., and Palomar, D. P. (2014).  Real and complex monotone communication games.  IEEE Transactions on Information Theory, 60(7):4197–4231.
  * Selten and Buchta, (1998) Selten, R. and Buchta, J. (1998).  Experimental sealed bid first price auctions with directly observed bid functions. Games and Human Behavior: Essays in Honor of Amnon Rapoport.
  * Selten and Stoecker, (1986) Selten, R. and Stoecker, R. (1986).  End behavior in sequences of finite prisoner’s dilemma supergames a learning theory approach.  Journal of Economic Behavior & Organization, 7(1):47 – 70.
  * Ui, (2016) Ui, T. (2016).  Bayesian nash equilibrium and variational inequalities.  Journal of Mathematical Economics, 63:139–146.
  * van den Brink et al., (2018) van den Brink, R., He, S., and Huang, J. (2018).  Polluted river problems and games with a permission structure.  Games and Economic Behavior, 108:182–205.
  * Voorneveld, (2000) Voorneveld, M. (2000).  Best-response potential games.  Economics Letters, 66(3):289–295.