# Dynamic Network Formation with Farsighted Players and Limited Capacities

Michel Grabisch, Elena Parilina, Agnieszka Rusinowska, Georges Zaccour

<figure><img src="image_1.png" /></figure>

## To cite this version:

Michel Grabisch, Elena Parilina, Agnieszka Rusinowska, Georges Zaccour. Dynamic Network Formation with Farsighted Players and Limited Capacities. 2025. halshs-05274180

HAL Id: halshs-05274180

https://shs.hal.science/halshs-05274180v1

Submitted on 23 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
CES

Centre d'Économie de la Sorbonne
UMR 8174

Dynamic Network Formation with Farsighted Players
and Limited Capacities

Michel GRABISCH, Elena PARILINA,
Agnieszka RUSINOWSKA, Georges ZACCOUR

2025.19
Dynamic Network Formation with Farsighted Players and
Limited Capacities

Michel Grabisch*

Elena Parilina†

Agnieszka Rusinowska‡

Georges Zaccour§

Abstract

We investigate a *T*-stage dynamic network formation game with linear-quadratic payoffs. Players interact through network which they create as a result of their actions. We study two versions of the dynamic game and provide the equilibrium analysis. First, we assume that players sequentially propose links to others with whom they want to connect and choose the levels of contribution for their links. The players have limited total contributions or capacities for forming links at every stage which can differ among players and over time. They cannot delete links, but the principle of natural elimination of links with no contribution is adopted. Next, we assume that the players simultaneously and independently propose links to other players and have overall limited capacities for the whole game, and not for each stage. This means that every player can redistribute the capacity not only over links, but also over time. The equilibrium concept for the first version of the dynamic game is subgame perfect equilibrium, while it is the Nash equilibrium in open-loop strategies for the second version. Both models are illustrated with numerical examples.

**JEL Classification:** D85, C73

**Keywords:** Network Formation Game; Dynamic Linear-Quadratic Game; Farsighted Players; Limited Capacities; Nash Equilibrium.

<footnote>*Centre d'Economie de la Sorbonne, Université Paris 1 Panthéon-Sorbonne, Paris School of Economics, France, michel.grabisch@univ-paris1.fr</footnote>

<footnote>†Saint Petersburg State University, Saint Petersburg, Russia, e.parilina@spbu.ru</footnote>

<footnote>‡Centre d'Economie de la Sorbonne, CNRS - Université Paris 1 Panthéon-Sorbonne, Paris School of Economics, Paris, France, agnieszka.rusinowska@univ-paris1.fr, *Corresponding author*</footnote>

<footnote>§Chair in Game Theory and Management, GERAD, HEC Montréal, Canada, Montreal, georges.zaccour@gerad.ca</footnote>
# 1 Introduction

In this paper, we propose a dynamic network formation model, where players are farsighted and have limited capacities for forming links. We propose and analyze two T-stage dynamic network formation games that differ in the mode of play, the constraints on the contributions to links, and in the equilibrium concept.

In the first version, each stage is divided into two steps. In the network-building step, the players sequentially propose links to others with whom they want to connect. In the second step, the players simultaneously decide how to allocate their limited budget (or capacity) to their links. To fix ideas, suppose that the set of players is formed of researchers working in the same area. In the first step, each researcher proposes to others to work on a research project and once their collaborative group is established, each must decide how much time to devote to the project. The available budget (the disposable time in this example) is not necessarily the same for all players at each stage, nor over stages. We adopt the principle of natural elimination of links, which states that a link will be deleted if both players decide not to contribute to it. We assume that each player's stage payoff is given by a linear-quadratic function that depends on the player's and partners contributions to her links. Each player aims at maximizing the sum of her stage payoffs. We show that there exists at least one subgame-perfect equilibrium for our network formation game. We illustrate the model and the computational procedure with a numerical example of 3-stage network formation game with 3 players. We report and discuss the network formation process, that is, which networks are formed in equilibrium and whether players reconsider the links they formed over time.

As above, our second model involves two steps at each stage, namely, a network building step followed by a step in which the players decide their contributions to the different links. Here, however, the players act simultaneously in the first step. A second difference with the first model is that the budget available to each player is for the whole game without replenishment. This makes the model truly dynamic in the sense of state-space games, that is, we have a state variable (the budget) that evolves over stages. As in a nonrenewable resource problem where the rate at which the resource is extracted has an implication on the stream of discounted revenues, here the rate at which the budget is exhausted is also profit relevant. Back to our example, in this second model a researcher has a total number of hours that she can devote to all her projects during the whole game, e.g., an academic year. We adopt an open-loop information structure, that
is, the players' strategies depend on the stage, but not on the state variable (remaining budget), although each player must account at each stage for the budget constraint. Consequently, we will determine a constrained open-loop Nash equilibrium. We will provide a maximum principle giving the necessary conditions for such an equilibrium to exist. On the top of having a global constraint for the whole game, the fact that the decision of creating a link is a binary variable renders the problem more complicated. We illustrate with a numerical example our second model and the procedure for computing an equilibrium.

**Related Literature** The present paper relates to several streams of the vast literature on network formation, which has been first initiated by models in static settings (e.g., Jackson and Wolinsky (1996)) and the analysis of different basic types of equilibria (e.g., Bloch and Jackson (2006)), and then followed by works including dynamic considerations (e.g., Bala and Goyal (2000); Watts (2001); Jackson and Watts (2002)).

First of all, our paper is related to the significant literature on farsighted network formation that has been mainly developed during the last twenty years or so, see, e.g., Mauleon and Vannetelbosch (2016) for a survey. Some frameworks focus on populations consisting of only farsighted players, while other models assume the presence of both myopic and farsighted players or consider limited farsightedness. The farsightedness of players is captured by the notion of farsighted improving paths (Jackson (2008); Herings et al. (2009)). For taking a decision, there is a fundamental difference in reasoning by these two types of players. While myopic players compare their current network's payoff with the resulting network's payoff after one stage, farsighted players compare their current network's payoff with their end network's payoff after the process stops. Jackson (2008) defines the concept of farsightly pairwise stability, being a modification of pairwise stability when all players are farsighted. Herings et al. (2009) introduce the notion of a pairwise farsightly stable set. The idea of limited farsightedness is investigated in Herings et al. (2019), where farsighted players compare the current payoff with their payoff in *K* stages, where *K* is given. Luo et al. (2021) study network formation with the player set partitioned into myopic and farsighted players. The players can create and delete links that results in a myopic-farsighted improving path. de Callataÿ et al. (2023) discuss the notion of myopic-farsighted absorbing set, which determines the networks emerging in the long run when the set of players is partitioned into myopic and farsighted subsets of players. Song and van der Schaar (2020) present a dynamic
model of network formation with agents being farsighted and having a (possibly partial) information about the history, and characterize efficient networks.

While in de Callataÿ et al. (2023); Herings et al. (2009, 2019); Jackson (2008); Luo et al. (2021) the farsighted players compare their current and end payoffs to take decisions, in Teteryatnikova (2021) the discounted stream of payoffs is considered as a player's utility function. The author examines properties of improving and surely improving paths with specific per-stage payoff functions (co-author model, equal value networks, criminal networks). The discounted stream of payoffs is also considered as a payoff function in Dutta et al. (2005) who model an equilibrium process of network formation, i.e., a strategy profile such that no pair of players can benefit by deviation. Players take the ongoing process as given and evaluate the entire stream of consequences arising from a single action. Myopic players can be imitated in the model by taking zero discount factor. Navarro (2014) considers a similar framework of dynamic network formation with farsighted players, but with the possibility of side payments between players. Also a number of other earlier works on network formation propose various farsighted concepts, see, e.g., Page et al. (2005); Page and Wooders (2009). More recently, Zhao et al. (2024) investigate a dynamic network formation with a social planner who builds a link to connect unlinked pairs of agents. The authors show that with the forward-looking social planner, forming a nested split graph at each period is optimal for any discount function. Moreover, when the social planner is sufficiently myopic, it is optimal to form a quasi-complete graph at each period.

Another stream of related literature follows the model of Ballester et al. (2006), where players are connected within a social network and choose their contributions to the network. A number of works propose some modifications of the Ballester’s model, see, e.g., Jadbabaie and Kakhbod (2019); Zhou and Chen (2015). Some studies consider (dynamic) network formation in the setting of Ballester et al. (2006). König et al. (2009) develop a two-stage game based on Ballester et al. (2006), where in the first stage, agents play the equilibrium contributions proportional to their Bonacich centrality (Bonacich (1987)). In the second stage, a randomly chosen agent best responds and updates her linking strategy by forming a new link. The authors adopt a myopic approach, i.e., they assume that agents creating a link only look at the second-order neighbor that gives them the current highest utility. König et al. (2010) extend König et al. (2009) and consider a network formation model where agents with capacity constraints in the number of links
that they can maintain, form and sever links based on the centrality of their potential partners. The authors show that the existence of capacity constrains leads to networks characterized by positive degree correlations and therefore assortativity. Also König et al. (2014) develop a two-stage game, where the game of Ballester et al. (2006) played in the first stage is followed by a linking-formation process in the second stage. The authors use stochastic stability and show that this network formation process converges to nested split graphs. As in their previous cited works, König et al. (2014) assume that the agents create links myopically, i.e., they only look at the agents giving them the current highest payoff.

An economic network formation model, where players pairwisely Cournot compete with their neighbors in dynamics (discrete time) is proposed by Kochevadov and Sedakov (2023). The authors also use linear-quadratic utility functions in their investment and production strategies. Liu et al. (2012) develop a network formation model to determine key criminals, i.e., those who once removed generate the highest possible reduction in aggregate crime level in a network. Network formation is also considered by Lee et al. (2021) who empirically identify the key player defined in Ballester et al. (2006). Colombo et al. (2025) begin from the model of Ballester et al. (2006) and investigate an infinite-horizon linear-quadratic differential game to study criminal networks. More precisely, the authors extend the static crime network game of Ballester et al. (2006, 2010) to a dynamic setting, where criminal activities negatively impact the accumulation of total wealth in the economy. Apart from conducting the equilibrium analysis and a comparative dynamic analysis, they study the problem of identifying the key criminals in the dynamic framework.

Bolletta (2021) investigates a model of strategic network formation, where the players first form the network by suggesting links to others and next choose their efforts for the whole constructed network. A Nash equilibrium is determined for linear-quadratic utility function in efforts; see also Golub et al. (2024) for a related work. At the first stage, pairwise stability equilibrium concept and best response dynamics are used. Another model of network formation with linear-quadratic utility function is proposed by Sandler and Golub (2024) who focus on positive/negative effects of the partners and find stable networks as a result of the Nash equilibrium in the game.

Other general settings are considered in Baetz (2015) and Hiller (2017) who model the network formation problem as a simultaneous game with players deciding jointly on
actions and links; see also Vega-Redondo (2016) for a survey of the literature combining network formation with games on networks and focusing on co-evolution of links and actions. Lagerås and Seim (2016) investigate the role of strategic complementarities in the context of network games and network formation models. The authors extend their study to a dynamic setting, comprising a game stage and a formation stage, and provide the convergence analysis. The paper by Bayer et al. (2021) is based on the model presented in Ballester et al. (2006), but it considers a game of local public goods where all players, except one, are myopic. The farsighted player can manipulate the other players' behaviors. Depending on the network formed at any stage, the players can be partitioned into two groups: leaders and followers who choose their contributions sequentially. The partition can be defined based on centrality measures of players in the network formed at the previous stage and/or their capacities. The idea of leaders is also examined in, e.g., Belhaj and Deroïan (2018); Jadbabaie and Kakhbod (2019).

There exist numerous other works on network formation with strategic formula-
tion that study various aspects of network formation, e.g., limited capacity for forming
links, the role of intermediation, ambiguity of network formation, among others. Bau-
mann (2021) investigates a model of weighted network formation in which every agent
has a limited resource to form links of possibly different intensities with other agents and
to use for private purposes. The author studies Nash equilibria of the game in which
all agents simultaneously choose their investment strategies, and shows that equilibria
are not pairwise stable and not efficient. Goyal and Vega-Redondo (2007) study inter-
mediate players in strategic network formation. They analyze the case when capacity
constraints on links are absent, as well as the implications of capacity constraints in
the ability of agents to form links. in t'Veld et al. (2020) build on the framework of
Goyal and Vega-Redondo (2007) and examine the role of intermediation in a network
formation model of a financial market. Zhang et al. (2014) investigate network forma-
tion game among countries concerning a free trade agreement and characterize pairwise
stable networks in this setting. First, they provide a static analysis and then develop a
dynamic model. Bayer and Guerdjikova (2024) study a model of endogenous two-sided
network formation where players face uncertainty about decisions of other players. The
authors analyze the impact of ambiguity and optimism on equilibrium networks.

**Summary of our main contributions** Our paper contributes to all the related literature mentioned above, and more specifically, to dynamic models and farsightedness
in network formation, and extensions of a noncooperative game with linear-quadratic
utilities of Ballester et al. (2006). To the best of our knowledge, this is the first paper
that combines these different approaches, proposing a dynamic network formation game
applied to the static framework of Ballester et al. (2006) and assuming that players are
farsighted and have limited capacities. The farsightedness in our models means that
players make their decisions maximizing the sum of the stage payoffs, but not the stage
payoff, as it is called being myopic in most literature of network formation.

Several new results are shown. First of all, we find the equilibrium network (which
exists but can be non-unique) in a T-stage network formation game with two steps when
players first choose their strategies and second decide on their contributions or efforts into
the links they possess in the formed network. In comparison with the existing literature,
we propose a novel approach of modeling network by assuming that players choose
the redistribution of their capacities under the per-stage capacity constraint among the
links but not to the whole network. In the original model of Ballester et al. (2006) and
a number of its extensions mentioned above, the player's payoff function is also linear-
quadratic in players' contributions but players choose the contribution to the whole
network and, moreover, they have unlimited capacities.

Second, we find the Nash equilibrium (and corresponding network) in the dy-
namic game of network formation when players still choose their contributions to the
links they possess but in the case when the player's overall capacity (for the entire time
horizon) is limited. We use the Pontryagin maximum principle to determine the network
formation and the equilibrium contribution strategies. This principle is of common use
in optimal control and in state-space dynamic games, but it is the first time it is applied
in the context of network formation. This methodological contribution is all the more
innovative that is done in the presence of dichotomous variables, which is far from being
a standard case.

Also, we would like to highlight the two features of the network formation games
introduced in the paper: (i) the principle of natural elimination of the links according
to which players can create a link but in case of zero contributions from both sides of
the link it will be eliminated from the network, (ii) the capacity constraints on players'
efforts (on stage contribution in the first model and on overall contribution in the second
model) that players realize to have gains from the links. The farsightedness in addition
to all above mentioned features makes the models of network formation original. While
there exist some works that consider limited capacities in link formation, they assume that players are myopic.

The remaining parts of the paper are organized as follows. Section 2 presents our dynamic network formation game played sequentially by players having limited capacities of forming links at every stage of the game. We focus on the equilibrium analysis in Section 3. We show the existence of subgame perfect equilibrium in Subsection 3.1 and provide a numerical example in Subsection 3.2. Section 4 concerns a modified version of the model, where the game is played simultaneously and players have overall limited capacities for the whole game that can be redistributed over links and time. We present the modified model in Subsection 4.1, determine the necessary conditions for the open-loop Nash equilibrium in Subsection 4.2 and provide a second numerical example in Subsection 4.3. In Section 5 we mention some further steps for research on the investigated framework. Appendix A presents tables with Nash equilibria for the numerical example of Subsection 3.2.

## 2 Model with Stage Capacity Constraint

Denote by $N = \{1, \dots, n\}$, $n \ge 3$, the set of players and consider a T-stage network formation game. A communication structure on $N$ is represented by an undirected network $(N, g)$, where $g \subseteq G = \{ij \mid i, j \in N, i \neq j\}$ is a collection of unordered pairs of players. To keep the notation simple, and if no ambiguity arises, we write $g$ when we refer to a network $(N, g)$. The initial network $g^0$ is given, and at the beginning of stage $t$, the players are connected by network $g^{t-1}$.

Each stage $t = 1, \dots, T$ is divided into two steps:

**Step 1:** In this step, the players sequentially choose the set of links they want to establish with the other players, with the sequence being defined by $\omega: N \to N$. The set of actions of player $i \in N$ in stage $t$ is

$$A_i^t = \{a_i^t : a_{ij}^t \in \{0, 1\}, ij \notin g^{t-1}, j \in N, j \neq i\},$$

where $a_{ij}^t = 1$, if player $i$ wants to create a link with player $j$, and 0 otherwise. Denote by $a^t$ the profile of players' actions ($a_i^t: i \in N$), $a_i^t \in A_i^t$. In this first step, the information is perfect, i.e., the players know the order and actions that players
previously chose. The link connecting players i and j is formed at stage t if both players choose actions $a_{ij}^t = a_{ji}^t = 1$ and each pays a cost $c > 0$ to create the link. We assume that this cost is the same for all links and does not vary over stages. The resulting formed network is denoted by $g^t$. If a link connecting players i and j exists in network $g^t$, we write $ij \in g^t$.

**Step 2:** In this step, any player i chooses her contribution $x_{ij}^t$ to each link $ij \in g^t$, thus forming a vector $x_i^t$ of contributions for existing links connecting this player with her neighbors. The total contribution of player i at stage t is constrained. Consequently, the action set of player i $\in N$ in stage t is defined by

$$X_i^t = \left\{ x_i^t : x_{ij}^t \ge 0, j \in N, j \ne i, ij \in g^t \text{ such that } \sum_{ij \in g^t} x_{ij}^t \le \bar{x}_i^t \right\},$$

where $\bar{x}_i^t$ is the upper bound for player i's contribution at stage t. The players choose their contributions $x_i^t$, $i \in N$, simultaneously, i.e., the information is imperfect in this step. Denote by $x^t$ the profile of players' actions ($x_i^t : i \in N$), $x_i^t \in X_i^t$, at the second step.<fnref n="1" />

A strategy of player i at stage t is a pair $(a_i^t, x_i^t)$, where $a_i^t \in A_i^t$, $x_i^t \in X_i^t$. Once the two steps are completed, player i $\in N$ obtains her stage payoff defined by

$$\pi_i^t(a^t, x^t) = \sum_{ij \in g^t} \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) + \delta \sum_{ij \in g^t} x_{ij}^t x_{ji}^t - \sum_{\substack{ij \in g^t \\ ij \notin g^{t-1}}} c, \quad (1)$$

where $\alpha_{ij} > 0$ for any $i, j \in N$ and $ij \in g^t$, $\delta > 0$, $a_i^t \in A_i^t$, and $x_i^t \in X_i^t$. In (1), the term $\alpha_{ij}x_{ij}^t - \frac{1}{2}(x_{ij}^t)^2$ represents the revenue that player i gets from establishing a link with player j. The (concave) linear-quadratic specification is adopted to account for the decreasing marginal returns in the contribution to a link. The term $\delta \sum_{ij \in g^t} x_{ij}^t x_{ji}^t$ corresponds to the synergetic benefit of players i and j contributions. The last term represents the cost of link formation, which is paid only for new links that are formed

<footnote n="1">¹The action set $X_i^t$ obviously depends on network $g^t$ but we omit the argument of network $g^t$ in notation $X_i^t$ for simplicity.</footnote>
at stage t. Payoff function (1) can be rewritten equivalently as

$$ \pi_i^t(a^t, x^t) = \sum_{ij \in g^t} \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) + \delta \sum_{ij \in g^t} x_{ij}^t x_{ji}^t - c \sum_{ij \in g^t} a_{ij}^t a_{ji}^t, \quad (2) $$

where $a_{ij}^t a_{ji}^t$ is equal to 1 if both players i and j choose to create link ij; otherwise, it is equal to zero.

If $t = T$, then the game stops; otherwise, stage $t+1$ starts with an initial network $g^t$ given by

$$ g^t = g^{t-1} \cup \{ij : ij \notin g^{t-1}, a_{ij}^t = a_{ji}^t = 1\} \setminus \{ij : ij \in g^{t-1}, x_{ij}^t = x_{ji}^t = 0\}, \quad (3) $$

where $\{ij : ij \notin g^{t-1}, a_{ij}^t = a_{ji}^t = 1\}$ represents the set of links created at stage t and $\{ij : ij \in g^{t-1}, x_{ij}^t = x_{ji}^t = 0\}$ is the set of links eliminated by virtue of the principle of

**Natural elimination of links:** Link $ij \in g^t$ is deleted at the end of stage $t = 2, \dots, T$ if $ij \in g^{t-1}$ and $x_{ij}^t = x_{ji}^t = 0$.

The players use behavior strategies in the game, represented by a mapping $\sigma_i$ defined on the set of histories. Specifically, $\mathcal{H}$ is the history of play, that is, $((a^1, x^1), \dots, (a^T, x^T))$. The sequence of networks formed along the game process is uniquely defined for any history $\mathcal{H}$ by (3) with given initial network $g^0$. At stage $t$ for any reduced history $\mathcal{H}^t$, that is, the sequence of actions $((a^1, x^1), \dots, (a^{t-1}, x^{t-1}))$ chosen by the players at stages $1, \dots, t-1$, respectively, the behavior strategy $\sigma_i(\mathcal{H}^t)$ determines a pair of actions to player i. Therefore, $\sigma_i(\mathcal{H}^t) = (a_i^t, x_i^t)$, where $a_i^t \in A_i^t$ and $x_i^t \in X_i^t$. We denote the profile of behavior strategies by $\sigma = (\sigma_1, \dots, \sigma_n)$, and the set of behavior strategies of player i by $\Sigma_i$.

**Definition 1.** A T-stage network formation game is defined by the set of players N, the set of behavior strategies $\Sigma_i$, $i \in N$, with the game process as described above, and the payoff to player i in the game defined by

$$ \Pi_i(\sigma) = \sum_{t=1}^{T} \pi_i^t(a^t, x^t). \quad (4) $$

We denote by $\Gamma(g^0)$ the T-stage network formation game with initial network $g^0$ and by $\Gamma^t(g^{t-1})$ the subgame starting at stage $t$ with initial network $g^{t-1}$. A behavior
strategy of any player $i \in N$ in subgame $\Gamma^t(g^{t-1})$ is a restriction of the behavior strategy $\sigma$ on this subgame denoted by $\sigma_i|_t$. Denote by $\Sigma_i^t$ the set of behavior strategies of player $i$. The profile of behavior strategies in subgame $\Gamma^t(g^{t-1})$ is $\sigma|_t = (\sigma_1|_t, \dots, \sigma_n|_t)$, where $\sigma_i|_t \in \Sigma_i^t$. The payoff to player $i$ in subgame $\Gamma^t(g^{t-1})$ is determined by

$$ \Pi_i^t(\sigma|_t) = \sum_{\tau=t}^{T} \pi_i^\tau(a^\tau, x^\tau), \qquad (5) $$

where a pair of action profiles $(a^\tau, x^\tau)$ is chosen at stage $\tau \ge t$ as a realization of behavior strategy profile $\sigma|_t$.

# 3 Equilibrium Analysis

## 3.1 Subgame Perfect Nash Equilibrium

A subgame perfect Nash equilibrium is a strategy profile $\sigma^*$ in the T-stage network formation game such that for every subgame, the restriction of strategy profile $\sigma^*$ to the subgame $\Gamma^t(g^{t-1})$ denoted by $\sigma^*|_t$ is a Nash equilibrium in that subgame, i.e., for any player $i \in N$, any strategy $\sigma_i \in \Sigma_i$, and any subgame starting at stage $t$ with initial network $g^{t-1}$ it holds that

$$ \Pi_i^t(\sigma^*|_t) \ge \Pi_i^t(\sigma_i, \sigma_{-i}^*|_t). \qquad (6) $$

**Proposition 1.** A T-stage network formation game admits at least one subgame perfect equilibrium.

*Proof.* For any $i \in N$ and $t = 1, \dots, T$, the set of actions $A_i^t$ is finite and the set of actions $X_i^t$ is compact. The payoff function $\pi_i^t(a^t, x^t)$ is concave in player $i$'s actions. Moreover, the set of networks, that is, the set of states in the dynamic network formation game, is finite. Therefore, there always exists at least one subgame perfect equilibrium in T-stage network formation game. ■

## 3.2 Numerical Example

We illustrate our network formation game with an example with 3 players ($N = \{1, 2, 3\}$) and 3 stages. We suppose that $\delta = 0.8$, $c = 0.5$. The values of $\alpha_{ij}$, $i, j \in N$ and the upper bounds on the capacities $\bar{x}_i^t$, $i \in N$, $t = 1, 2, 3$ are given in Table 1 and Table 2, respectively.
<table><caption>Table 1: Values of $\alpha_{ij}$, $i, j \in N$</caption><thead><tr><th>$i$</th><th>$j$</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><td>1</td><td></td><td>-</td><td>0.8</td><td>1</td></tr><tr><td>2</td><td></td><td>0.5</td><td>-</td><td>0.9</td></tr><tr><td>3</td><td></td><td>0.5</td><td>0.5</td><td>-</td></tr></tbody></table>

<table><caption>Table 2: Upper bound for players' contribution</caption><thead><tr><th>$i$</th><th>$\bar{x}_i^1$</th><th>$\bar{x}_i^2$</th><th>$\bar{x}_i^3$</th></tr></thead><tbody><tr><td>1</td><td>4</td><td>4</td><td>4</td></tr><tr><td>2</td><td>3</td><td>3</td><td>3</td></tr><tr><td>3</td><td>1</td><td>1</td><td>1</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>Figure 1: All possible networks formed by the players from set $N = \{1, 2, 3\}$</figcaption></figure>

Let the players choose their actions $a_i^t$ at any stage $t$ with the order $\omega(1, 2, 3) = (1, 2, 3)$. To find a subgame perfect equilibrium we proceed backward. We start with $t=3$ and consider all possible initial states for this subgame, i.e., all possible networks represented in Figure 1 and denoted as $\ell_1, \dots, \ell_8$, respectively. We describe finding the Nash equilibrium in subgame $\Gamma^3(g^2)$ for any possible network $g^2 \in \{\ell_1, \dots, \ell_8\}$ in detail. The calculations for other subgames will be omitted, but the Nash equilibria for all subgames will be presented in the tables in Appendix A.

We first solve the game played at the second step for all possible networks formed by the players from $N$. At the second step, the network is defined after the players choose
their actions $a_i^t$ at the first step of stage $t$. Then, at the second step of stage $t$ player $i \in N$ solves the following optimization problem:

$$ \max_{x_i^t \in X_i^t} \left\{ \sum_{ij \in g^t} \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) + \delta \sum_{ij \in g^t} x_{ij}^t x_{ji}^t \right\}. $$

We should notice that the last term in expression (1), that is, the cost of establishing links, is omitted as this term is independent of actions $x_i^t$, $i \in N$.

The Lagrangian of player $i$ is given by

$$ L_i^t(g^t, x^t, \lambda_i^t) = \sum_{ij \in g^t} \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) + \delta \sum_{ij \in g^t} x_{ij}^t x_{ji}^t + \lambda_i^t \left( \sum_{ij \in g^t} x_{ij}^t - \bar{x}_i^t \right), $$

which is maximized subject to constraints:

$$ \begin{aligned} x_{ij}^t &\ge 0, \quad \forall ij \in g^t, \\ \lambda_i^t &\le 0, \\ \lambda_i^t \left( \sum_{ij \in g^t} x_{ij}^t - \bar{x}_i^t \right) &= 0. \end{aligned} $$

A Nash equilibrium is obtained by solving the system:

$$ \begin{aligned} \frac{\partial L_i^t}{\partial x_{ij}^t} &= \alpha_{ij} - x_{ij}^t + \delta x_{ji}^t + \lambda_i^t = 0, \quad \forall ij \in g^t, \quad \forall i \in N, \\ x_{ij}^t &\ge 0, \quad \forall ij \in g^t, \\ \lambda_i^t &\le 0, \quad \forall i \in N, \\ \lambda_i^t \left( \sum_{ij \in g^t} x_{ij}^t - \bar{x}_i^t \right) &= 0, \quad \forall i \in N. \end{aligned} $$

To illustrate the computational procedure, we consider first Table 3, which gives the players’ Nash equilibrium contributions for all possible networks, that is, for any $g \in \{\ell_1, \dots, \ell_8\}$.

We make the following observations: (i) The most efficient network that maximizes total profit is not the complete network, but network $\ell_5$, with only players 1 and 2 being linked. (ii) The most profitable network is $\ell_2$ for player 1 with links 12 and 13, $\ell_5$ for player 2 with the single link 12, and $\ell_6$ for player 3 with the single link 13. (iii)
<table><caption>Table 3: Nash equilibrium for the game at the second step</caption><thead><tr><th>Network</th><th>NE strategies</th><th>Payoffs</th><th>Total payoff</th></tr></thead><tbody><tr><td>1 2 3</td><td>x<sub>12</sub> = 2.46, x<sub>13</sub> = 1.54, x<sub>21</sub> = 2.20, x<sub>23</sub> = 0.80, x<sub>31</sub> = 0.80, x<sub>32</sub> = 0.20</td><td>(4.61, 3.54, 1.27)</td><td>9.42</td></tr><tr><td>1 2 3</td><td>x<sub>12</sub> = 2.5, x<sub>21</sub> = 2.5, x<sub>13</sub> = 1.5, x<sub>31</sub> = 1.00</td><td>(5.45, 3.13, 1.20)</td><td>9.78</td></tr><tr><td>1 2 3</td><td>x<sub>13</sub> = 1.49, x<sub>31</sub> = 0.61, x<sub>23</sub> = 1.21, x<sub>32</sub> = 0.39</td><td>(1.11, 0.73, 1.34)</td><td>3.18</td></tr><tr><td>1 2 3</td><td>x<sub>12</sub> = 2.24, x<sub>21</sub> = 1.79, x<sub>23</sub> = 1.21, x<sub>32</sub> = 1.00</td><td>(2.50, 3.82, 0.96)</td><td>7.28</td></tr><tr><td>1 2 3</td><td>x<sub>12</sub> = 3.20, x<sub>21</sub> = 3.00</td><td>(5.12, 4.68, 0.00)</td><td>9.80</td></tr><tr><td>1 2 3</td><td>x<sub>13</sub> = 1.80, x<sub>31</sub> = 1.00</td><td>(1.62, 0.00, 1.44)</td><td>3.06</td></tr><tr><td>1 2 3</td><td>x<sub>23</sub> = 1.70, x<sub>32</sub> = 1.00</td><td>(0.00, 1.45, 1.36)</td><td>2.81</td></tr><tr><td>1 2 3</td><td>—</td><td>(0, 0, 0)</td><td>0</td></tr></tbody></table>

The players use their total capacities only when the network is complete. In all other possible networks, there always exists at least one player whose total contribution is less than her capacity $\bar{x}_i^t$. (iv) All networks in the set {$\ell_1, \dots, \ell_8$} are Pareto optimal except the empty network $\ell_8$.

Once we find the Nash equilibrium contributions in the simultaneous game played
in the second step for any network $g$, we can draw the extensive form tree for a given sequence of players. In this example, we retain $\omega(1, 2, 3) = (1, 2, 3)$. The subgame starting at stage 3 can be represented in extensive-form game for any given initial state $g^2 \in \{\ell_1, \dots, \ell_8\}$. The Nash equilibria for this subgame are given in Table 4.

<table><caption>Table 4: Nash equilibrium for subgame $\Gamma^3(g^2)$</caption><thead><tr><th>Initial network g<sup>2</sup></th><th>Strategies</th><th>Payoffs</th><th>Final network g<sup>3</sup></th></tr></thead><tbody><tr><td><pre>1
  2
3</pre></td><td>$x_{12}^3 = 2.46, x_{13}^3 = 1.54, x_{21}^3 = 2.20,$<br>$x_{23}^3 = 0.80, x_{31}^3 = 0.80, x_{32}^3 = 0.20$</td><td>(4.61, 3.54, 1.27)</td><td><pre>1
  2
3</pre></td></tr><tr><td><pre>1
  2
3</pre></td><td>$a_{23}^3 = 0, a_{32}^3 = 0,$<br>$x_{12}^3 = 2.5, x_{21}^3 = 2.5,$<br>$x_{13}^3 = 1.5, x_{31}^3 = 1.00$</td><td>(5.45, 3.13, 1.20)</td><td><pre>1
  2
3</pre></td></tr><tr><td><pre>1
  2
3</pre></td><td>$a_{12}^3 = 1, a_{21}^3 = 1,$<br>$x_{12}^3 = 2.46, x_{13}^3 = 1.54, x_{21}^3 = 2.20,$<br>$x_{23}^3 = 0.80, x_{31}^3 = 0.80, x_{32}^3 = 0.20$</td><td>(4.11, 3.04, 1.27)</td><td><pre>1
  2
3</pre></td></tr><tr><td><pre>1
  2
3</pre></td><td>$a_{13}^3 = a_{31}^3 = 0,$<br>$x_{12}^3 = 2.24, x_{21}^3 = 1.79,$<br>$x_{23}^3 = 1.21, x_{32}^3 = 1.00$</td><td>(2.50, 3.82, 0.96)</td><td><pre>1
  2
3</pre></td></tr><tr><td><pre>1
  2
3</pre></td><td>$a_{13}^3 = a_{31}^3 = a_{23}^3 = a_{32}^3 = 0,$<br>$x_{12}^3 = 3.20, x_{21}^3 = 3.00$</td><td>(5.12, 4.68, 0.00)</td><td><pre>1
  2
3</pre></td></tr><tr><td><pre>1
  2
3</pre></td><td>$a_{12}^3 = a_{21}^3 = 1, a_{23}^3 = a_{32}^3 = 0,$<br>$x_{12}^3 = 2.5, x_{21}^3 = 2.5,$<br>$x_{13}^3 = 1.5, x_{31}^3 = 1.00$</td><td>(4.95, 2.63, 1.20)</td><td><pre>1
  2
3</pre></td></tr><tr><td><pre>1
  2
3</pre></td><td>$a_{12}^3 = a_{21}^3 = 1, a_{13}^3 = a_{31}^3 = 0,$<br>$x_{12}^3 = 2.24, x_{21}^3 = 1.79,$<br>$x_{23}^3 = 1.21, x_{32}^3 = 1.00$</td><td>(2.00, 3.32, 0.96)</td><td><pre>1
  2
3</pre></td></tr><tr><td><pre>1
  2
3</pre></td><td>$a_{12}^3 = a_{21}^3 = 1, a_{13}^3 = a_{31}^3 = 0,$<br>$a_{32}^3 = a_{23}^3 = 0,$<br>$x_{12}^3 = 3.20, x_{21}^3 = 3.00$</td><td>(4.62, 4.18, 0.00)</td><td><pre>1
  2
3</pre></td></tr></tbody></table>
There exist many equilibria for any given initial network $g^2$, but for all equilibria the final network that is formed after the players choose their strategies is unique for each given network $g^2$, and the players' payoffs are also the same. Therefore, to save on space, we represent only one equilibrium in Table 4. The Nash equilibria in the subgame $\Gamma^2(g^1)$ starting at stage $t=2$ are given in Table 7 in Appendix A, and for the whole game $\Gamma^1(g^0)$ in Table 8 in Appendix A. In all tables we present the initial network, players strategies (actions for each stage of the game or subgame), players' payoffs, and final network formed under equilibrium strategies.

We make the following observations:

1. For any given initial network, the final network depends on the number of remaining stages. For example, if we start with the empty network and have only one stage left (see Table 4), then only link 12 appears in the final network, but if the number of stages is two or three (Tables 7 and 8), then the final network is $\ell_2$ with two links 12 and 13. As investing in a link is costly, a sufficiently remaining planning horizon is needed to amortize this cost.

2. For all initial networks, we end up with either the complete network $\ell_1$ (for 4 different initial networks) or the two-link network $\ell_2$ (for the other 4 initial networks). The order of play is given in the example by $\omega(1, 2, 3) = (1, 2, 3)$. Clearly, the results may change if another order were considered.

3. In all cases, the network formed in the first stage is the final network, that is, the players invest in the links they want to establish as early as possible and do not eliminate a link later on. This result is related to the cost argument given above. Once a link is established, a player is better off contributing any positive number rather than zero. In our setting, the link is eliminated if both players make zero contribution in at least one stage. If we allow elimination of a link when at least one player contributes at a zero level, then the result may change.

As an extension, once the equilibrium is determined, we could construct a corresponding weighted graph to the formed network, with the weight of a link being given by the product of the two players' contributions. Such a weighted graph reflects the strategic interactions between the players, which are the results of their choices of connections and contributions to the created links.
# 4 Dynamic Network Formation with Overall Limited Capacities of the Players

## 4.1 Model with Overall Capacity Constraint

We modify the dynamic game of network formation presented in Section 2 in two respects. First, the players simultaneously and independently propose links to other players, and as a result, the network is formed. Recall that in the previous model, this step in any stage was played sequentially. Second, the capacity endowment for each player is defined for the whole game and not for each stage, which adds one more dynamic feature to our model. Indeed, the players now face an intertemporal arbitrage when allocating their contributions to their links. We denote by $y_i^t$ the remaining available capacity to player $i$ in stage $t$ and by $y_i^0$ the total capacity. In the parlance of dynamic optimization, $y_i^t$ is a stock of a nonrenewable resource (state variable) that is depleted over stages.

We briefly describe the T-stage dynamic network formation game with overall limited capacities, with initial given network $g^0$. The game proceeds as follows:

1. Each stage $t$ is divided into two steps. First, given the network $g^{t-1}$ formed in stage $t-1$, the players propose links to other players. Second, they choose their contributions to the links in the network considering remaining available capacity. More specifically, we have:

Step 1. The players simultaneously and independently choose their actions $a_i^t \in A_i^t$, where $A_i^t = \{a_i^t : a_{ij}^t \in \{0,1\}, ij \notin g^{t-1}, j \in N, j \neq i\}$, and $a_{ij}^t = 1$ if player $i$ is willing to create a link with player $j$, and 0 otherwise. Denote by $a^t$ the profile of players' actions ($a_i^t : i \in N$), $a_i^t \in A_i^t$, at the first step. For any player $i \in N$, the cost of creating a link is $c > 0$, and it will be paid by players $i$ and $j$ if $a_{ij}^t = a_{ji}^t = 1$. The network formed at stage $t$ after players choose their actions is denoted by $g^t$ and defined by

$$g^t = g^{t-1} \cup \{ij : ij \notin g^{t-1}, a_{ij}^t = a_{ji}^t = 1\}. \quad (7)$$

The network $g^t$ is known to the players.

Step 2. The players simultaneously and independently choose their contributions to the existing links $x_i^t = (x_{ij}^t : j \in N, ij \in g^t) \in X_i^{t'}$ in network $g^t$, and the set
of actions of player i denoted by $X_i^{t'}$ is defined by

$$X_i^{t'} = \left\{ x_i^t : x_{ij}^t \ge 0, j \in N, j \ne i, ij \in g^t \text{ such that } \sum_{ij \in g^t} x_{ij}^t \le y_i^t \right\},$$

where $y_i^t$ is the capacity of player i at stage t. The evolution of this state variable is governed by the following difference equation:

$$y_i^t = y_i^{t-1} - \sum_{ij \in g^{t-1}} x_{ij}^{t-1}, \quad t = 1, \dots, T, \qquad (8)$$

subject to the nonnegativity constraint

$$y_i^t \ge 0, \quad t = 1, \dots, T. \qquad (9)$$

2. After the players make their choices, the network $g^t$ is updated using the principle of natural elimination, that is,

$$g^t := g^t \setminus \{ij : ij \in g^{t-1}, x_{ij}^t = x_{ji}^t = 0\}. \qquad (10)$$

3. The payoff of player $i \in N$ in stage $t$ is given by

$$\pi_i^t(a^t, x^t, g^{t-1}) = \sum_{ij \in g^t} \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) + \delta \sum_{ij \in g^t} x_{ij}^t x_{ji}^t - c \sum_{ij \in g^t} a_{ij}^t a_{ji}^t, \quad (11)$$

where $x^t = (x_i^t : i \in N)$. The payoff function is similar to what we had in the previous model, therefore there is no need to repeat the same comment.

4. If $t < T$, then the game moves to stage $t+1$; otherwise, the game stops.

**Remark 1.** The rule of natural elimination of links is equivalent to the model of network formation described above when players can delete a link at zero cost. Contrary to most known models of network formation, here a link $ij \in g^{t-1}$ is severed at stage $t$ if both players choose action $a_{ij}^t = a_{ji}^t = 0$, which is equivalent to $x_{ij}^t = x_{ji}^t = 0$. Then, the set of player i's actions can be rewritten as

$$A_i^t = \{a_i^t : a_{ij}^t \in \{0,1\}, j \in N, j \ne i\},$$
where

$$a_{ij}^{t} = \begin{cases} 1, & \text{if } ij \notin g^{t-1} \text{ and } i \text{ is willing to create a link with } j, \\ 0, & \text{if } ij \notin g^{t-1} \text{ and } i \text{ is not willing to create a link with } j, \\ 0, & \text{if } ij \in g^{t-1} \text{ and } i \text{ is willing to sever a link with } j. \end{cases}$$

If we describe the rule of elimination of links in such a way, then the network dynamics can be defined by

$$g^t = g^{t-1} \cup \{ij : ij \notin g^{t-1}, a_{ij}^t = a_{ji}^t = 1\} \setminus \{ij : ij \in g^{t-1}, a_{ij}^t = a_{ji}^t = 0\}. \quad (12)$$

Considering the network dynamics (12), the stage payoff function (11) can be rewritten as follows:

$$\begin{align} \pi_i^t(a^t, x^t, g^{t-1}) = & \sum_{ij \in g^{t-1}} \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) + \delta \sum_{ij \in g^{t-1}} x_{ij}^t x_{ji}^t \tag{13} \\ & + \sum_{ij \notin g^{t-1}} a_{ij}^t a_{ji}^t \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) + \delta \sum_{ij \notin g^{t-1}} a_{ij}^t a_{ji}^t x_{ij}^t x_{ji}^t - \sum_{ij \notin g^{t-1}} c a_{ij}^t a_{ji}^t \nonumber \\ & - \sum_{ij \in g^{t-1}} (1 - a_{ij}^t)(1 - a_{ji}^t) \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) - \delta \sum_{ij \in g^{t-1}} (1 - a_{ij}^t)(1 - a_{ji}^t) x_{ij}^t x_{ji}^t, \nonumber \end{align}$$

where $x^t = (x_i^t : i \in N)$. The first row in (13) represents the payoff of the player over existing links in the network $g^{t-1}$, i.e., before creating/deleting links. The second row is the payoff of the player over the links created at stage t, and, finally, the third row represents the loss over the links deleted at stage t.

To wrap up, we define a T-stage network formation game with overall limited capacities of the players by the set of players N, the state dynamics (8) subject to constraints (9), and payoff functions given by

$$\Pi_i(a, x, g^0) = \sum_{t=1}^{T} \pi_i^t(a^t, x^t, g^{t-1}). \quad (14)$$

for any $i \in N$. We denote the T-stage network formation game with overall limited capacities of the players with initial network $g^0$ by $\Gamma'(g^0)$. We note that this game belongs to the class of linear-quadratic games.
## 4.2 Open-loop Nash Equilibrium

We seek a Nash equilibrium in open-loop strategies. Let $\sigma_i^t$ be the open-loop strategy of player $i \in N$ defining the strategies $(a_i^t, x_i^t)$, $a_i^t \in A_i^t$, $x_i^t \in X_i^{t'}$ at any stage $t$. Then, the payoff function of player $i \in N$ in open-loop strategy profile $\sigma = (\sigma_i : i \in N)$ is defined by

$$ \Pi_i(\sigma, g^0) = \Pi_i(a, x, g^0) = \sum_{t=1}^{T} \pi_i^t(a^t, x^t, g^{t-1}). \quad (15) $$

Denote the set of open-loop strategies of Player $i$ by $\Sigma_i$.

**Definition 2.** The profile of strategies $\sigma^* = (\sigma_i^* : i \in N)$ is an open-loop Nash equilibrium in $\Gamma'(g^0)$ if

$$ \Pi_i((\sigma_i^*, \sigma_{-i}^*), g^0) \geq \Pi_i((\sigma_i, \sigma_{-i}^*), g^0), $$

for any $\sigma_i \in \Sigma_i$ such that $\sigma_i^t = (a_i^t, x_i^t)$, $a_i^t \in A_i^t$, $x_i^t \in X_i^{t'}$.

The following proposition gives the necessary conditions for the open-loop Nash equilibrium in dynamic game $\Gamma'(g^0)$ with initially given network $g^0$.

**Proposition 2.** If the profile of open-loop strategies $\sigma^* = (\sigma_i^* : i \in N)$, with the components $\sigma_i^{t*} = (a_i^{t*}, x_i^{t*})$, $i \in N$, $t = 1, \dots, T$, is an open-loop Nash equilibrium generating the state trajectory $y^{t*} = (y_i^{t*} : i \in N)$ from initial state $y_i^0$ in the game $\Gamma'(g^0)$ defined by payoff functions (15) and (13), and conditions (12) and (8), then there exist functions of time $\lambda_i^t$, $i \in N$, with values in $\mathbb{R}$ and $\theta_i^t$, $i \in N$, with values in $\mathbb{R}$, such that the following relations hold:

$$ a_{ij}^t = \begin{cases} 1, & \text{if } \left\{ \begin{array}{l} ij \in g^{t-1}, \alpha_{ij}x_{ij}^t - \frac{1}{2}(x_{ij}^t)^2 + \delta x_{ij}^t x_{ji}^t + \lambda_i^{t+1}x_{ij}^t - \theta_i^t x_{ij}^t > 0, \\ \phantom{ij \in g^{t-1}} \text{or} \\ ij \notin g^{t-1}, \alpha_{ij}x_{ij}^t - \frac{1}{2}(x_{ij}^t)^2 + \delta x_{ij}^t x_{ji}^t - \lambda_i^{t+1}x_{ij}^t + \theta_i^t x_{ij}^t > c, \end{array} \right. \\ 0, & \text{if } \left\{ \begin{array}{l} ij \in g^{t-1}, \alpha_{ij}x_{ij}^t - \frac{1}{2}(x_{ij}^t)^2 + \delta x_{ij}^t x_{ji}^t + \lambda_i^{t+1}x_{ij}^t - \theta_i^t x_{ij}^t \leq 0, \\ \phantom{ij \in g^{t-1}} \text{or} \\ ij \notin g^{t-1}, \alpha_{ij}x_{ij}^t - \frac{1}{2}(x_{ij}^t)^2 + \delta x_{ij}^t x_{ji}^t - \lambda_i^{t+1}x_{ij}^t + \theta_i^t x_{ij}^t \leq c; \end{array} \right. \end{cases} $$
$$
x_{ij}^{t} = \left\{
\begin{array}{ll}
\alpha_{ij} + \delta x_{ji}^{t} - \lambda_{i}^{t+1} + \theta_{i}^{t}, & \left\{
\begin{array}{l}
\text{if } ij \in g^{t-1}, a_{ij}^{t} = 1 \text{ or } a_{ji}^{t} = 1, \\
\text{or} \\
\text{if } ij \notin g^{t-1}, a_{ij}^{t} = a_{ji}^{t} = 1,
\end{array}
\right. \\
0, & \left\{
\begin{array}{ll}
\text{if } ij \in g^{t-1}, a_{ij}^{t} = a_{ji}^{t} = 0, & \\
\text{or} \\
\text{if } ij \notin g^{t-1}, a_{ij}^{t} = 0 \text{ or } a_{ji}^{t} = 0,
\end{array}
\right.
\end{array}
\right.
$$

and

$$
\begin{align*}
\lambda_i^t &= - \sum_{\tau=t}^T \theta_i^\tau, \\
0 &= \theta_i^t \left( \sum_{ij \in g^t} x_{ij}^{t*} - y_i^{t*} \right), \quad t=1, \dots, T, \\
0 &\ge \theta_i^t, \quad t=1, \dots, T, \\
\lambda_i^{T+1} &= 0.
\end{align*}
$$

Proof. First, we assume that player $i \in N$ chooses strategies $q_{ij}^t \in [0, 1]$ instead of choosing binary variables $a_{ij}^t \in \{0, 1\}$ at time $t \neq T$. (As we will see, the equilibrium problem of player $i \in N$ is linear in $q_{ij}^t$, so choosing an interior value $q_{ij}^t \in (0, 1)$ has no impact on the equilibrium outcome.) Therefore, variable $q_{ij}^t$ characterizes the willingness of player $i$ to form a link with player $j$ at time $t$. If $q_{ij}^t = 1$, then player $i$ proposes a link to player $j$, and if $q_{ij}^t = 0$, then player $i$ does not propose a link to player $j$. Denote by $q^t$ the vector of strategies $(q_i^t : i \in N)$ at time $t$. Then, the open-loop strategy of player $i$ is modified and let denote it by $\xi_i$, where $\xi_i^t = (q_i^t, x_i^t)$.

Following Pontryagin's maximum principle, we write the Lagrangian function
taking into account inequality (9), conditions (8), and dynamics (12):

$$
\begin{align*}
\mathcal{L}_i(t, y_i^t, q^t, x^t, \lambda_i^{t+1}, \theta_i^t) = & \sum_{ij \in g^{t-1}} \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) + \delta \sum_{ij \in g^{t-1}} x_{ij}^t x_{ji}^t \\
& + \sum_{ij \notin g^{t-1}} q_{ij}^t q_{ji}^t \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) + \delta \sum_{ij \notin g^{t-1}} q_{ij}^t q_{ji}^t x_{ij}^t x_{ji}^t - \sum_{ij \notin g^{t-1}} c q_{ij}^t q_{ji}^t \\
& - \sum_{ij \in g^{t-1}} (1 - q_{ij}^t)(1 - q_{ji}^t) \left( \alpha_{ij} x_{ij}^t - \frac{1}{2} (x_{ij}^t)^2 \right) - \delta \sum_{ij \in g^{t-1}} (1 - q_{ij}^t)(1 - q_{ji}^t) x_{ij}^t x_{ji}^t \\
& + \lambda_i^{t+1} \left[ y_i^t - \sum_{ij \in g^{t-1}} (1 - (1 - q_{ij}^t)(1 - q_{ji}^t)) x_{ij}^t - \sum_{ij \notin g^{t-1}} q_{ij}^t q_{ji}^t x_{ij}^t \right] \\
& + \theta_i^t \left[ \sum_{ij \in g^{t-1}} (1 - (1 - q_{ij}^t)(1 - q_{ji}^t)) x_{ij}^t + \sum_{ij \notin g^{t-1}} q_{ij}^t q_{ji}^t x_{ij}^t - y_i^t \right],
\end{align*}
$$

where $\lambda_i^t, t = 1, \dots, T$, is the costate variable and $\theta_i^t$ is a Lagrange multiplier. If the Karush-Kuhn-Tucker conditions are satisfied, if the profile of open-loop strategies $\xi^* = (\xi_i : i \in N)$ is the Nash equilibrium, then there exist nonzero functions of time $\lambda_i^t$ and $\theta_i^t, t = 1, \dots, T, i \in N$, satisfying the following conditions:

$$
\xi_i^{t*} = \arg \max_{q_i^t \in [0,1]^n, x_i^t \in X_i^{t'}} \mathcal{L}_i(t, y_i^{t*}, (q_i^t, q_{-i}^{t*}), (x_i^t, x_{-i}^{t*}), \lambda_i^{t+1}, \theta_i^t), \quad (16)
$$

$$
\lambda_i^t = \frac{\partial}{\partial y_i^t} \mathcal{L}_i(t, y^{t*}, (q_i^t, q_{-i}^{t*}), (x_i^t, x_{-i}^{t*}), \lambda_i^{t+1}, \theta_i^t),
$$

$$
0 = \theta_i^t \left( \sum_{ij \in g^t} x_{ij}^{t*} - y_i^t \right), \quad t = 1, \dots, T,
$$

$0 \geq \theta_i^t, \quad t = 1, \dots, T,$

$\lambda_i^{T+1} = 0,$

where $y_i^* = (y_i^{t*}, t = 1, \dots, T)$ is a state (capacity) trajectory of player $i$ with initial state
$y_i^{t*} = y_i^0$.
The last four lines of system (16) can be rewritten as follows:

$$
\begin{align*}
\lambda_i^t &= -\sum_{\tau=t}^{T} \theta_i^\tau, \\
0 &= \theta_i^t \left( \sum_{ij \in g^t} x_{ij}^{t*} - y_i^{t*} \right), \quad t = 1, \dots, T, \\
0 &\ge \theta_i^t, \quad t = 1, \dots, T, \\
\lambda_i^{T+1} &= 0.
\end{align*}
$$

Since the Lagrangian is a linear function with respect to strategies $q_{ij}^t$, then the solution of the maximization problem in (16) w.r.t. $q_{ij}^t$ is as follows:

$$
q_{ij}^{t} = \begin{cases}
1, & \text{if } ij \in g^{t-1}, \alpha_{ij}x_{ij}^{t} - \frac{1}{2}(x_{ij}^{t})^{2} + \delta x_{ij}^{t}x_{ji}^{t} + \lambda_{i}^{t+1}x_{ij}^{t} - \theta_{i}^{t}x_{ij}^{t} > 0, \\
0, & \text{if } ij \in g^{t-1}, \alpha_{ij}x_{ij}^{t} - \frac{1}{2}(x_{ij}^{t})^{2} + \delta x_{ij}^{t}x_{ji}^{t} + \lambda_{i}^{t+1}x_{ij}^{t} - \theta_{i}^{t}x_{ij}^{t} \le 0, \\
1, & \text{if } ij \notin g^{t-1}, \alpha_{ij}x_{ij}^{t} - \frac{1}{2}(x_{ij}^{t})^{2} + \delta x_{ij}^{t}x_{ji}^{t} - \lambda_{i}^{t+1}x_{ij}^{t} + \theta_{i}^{t}x_{ij}^{t} > c, \\
0, & \text{if } ij \notin g^{t-1}, \alpha_{ij}x_{ij}^{t} - \frac{1}{2}(x_{ij}^{t})^{2} + \delta x_{ij}^{t}x_{ji}^{t} - \lambda_{i}^{t+1}x_{ij}^{t} + \theta_{i}^{t}x_{ij}^{t} \le c.
\end{cases}
$$

Taking the derivative of $\mathcal{L}_i$ w.r.t. $x_{ij}^t$ and that $q_{ij}^t = 0$ or $1$, we write the first-order conditions for $x_{ij}^t$:

$$
x_{ij}^{t} = \begin{cases}
\alpha_{ij} + \delta x_{ji}^{t} - \lambda_{i}^{t+1} + \theta_{i}^{t}, & \text{if } ij \in g^{t-1}, q_{ij}^{t} = 1 \text{ or } q_{ji}^{t} = 1, \\
0, & \text{if } ij \in g^{t-1}, q_{ij}^{t} = q_{ji}^{t} = 0, \\
\alpha_{ij} + \delta x_{ji}^{t} - \lambda_{i}^{t+1} + \theta_{i}^{t}, & \text{if } ij \notin g^{t-1}, q_{ij}^{t} = q_{ji}^{t} = 1, \\
0, & \text{if } ij \notin g^{t-1}, q_{ij}^{t} = 0 \text{ or } q_{ji}^{t} = 0.
\end{cases}
$$

Since $q_{ij}^t$ takes the values from the set $\{0, 1\}$, we can write down the equilibrium strategies using notations $a_{ij}^t$, which is initially assumed to be binary.

This finishes the proof. ■

4.3 Second Numerical Example

The set of players is $N = \{1, 2, 3\}$, and we consider 3-stage network formation game as
in Section 3.2. We keep the parameters $\delta = 0.8$, $c = 0.5$ at the same values.

The values of $\alpha_{ij}$, $i, j \in N$ are presented in Table 1.
The upper bound of the overall capacities $y_i^0$, $i \in N$, are given in Table 5.

<table><caption>Table 5: Players’ overall capacities</caption><thead><tr><th>$i$</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><td>$y_i^0$</td><td>10</td><td>8</td><td>2</td></tr></tbody></table>

We find the open-loop Nash equilibria using Proposition 2. Assuming that the initial network $g^0$ is the empty network, we find all Nash equilibria solving the system of equations given in Proposition 2. There are ten Nash equilibria and they are presented in Table 6. We divide them into three groups relative to the final network formed in the equilibrium.

We make several conclusions on this numerical example:

1. The open-loop Nash equilibrium is not unique. The multiple equilibria are implied by the finiteness of the set of strategies $A_i$ for any player $i$, i.e., players choose their strategies $a_{ij}$ from a binary set $\{0, 1\}$ and make their choices simultaneously.

2. There are only three networks that can be formed in the equilibria: empty network, $\ell_5$ when only players 1 and 2 are linked, and $\ell_6$ when only players 1 and 3 are linked.

3. In the equilibria $(2.i)-(2.vi)$, player 1's overall capacity is not used, $\sum_{t=1}^3 x_{12}^t = 8.8 < 10 = y_1^0$, while player 2 uses her overall capacity in the game, $\sum_{t=1}^3 x_{21}^t = 2.67 \times 3 \approx 8 = y_2^0$.

4. In the equilibria $(3.i)-(3.ii)$, player 1's overall capacity is not used, $\sum_{t=1}^3 x_{13}^t = 4.6 < 10 = y_1^0$, while player 3 uses her overall capacity in the game, $\sum_{t=1}^3 x_{31}^t = 2 = y_3^0$.

5. Once the players choose the strategies $a_{ij}$ to create the links in the network, they are never willing to remove them, i.e., the links are created for all the stages.

# 5 Conclusion

In this paper, we investigate two versions of a finite dynamic network formation game in which players’ actions concern the choice of links that they wish to form with other players and the levels of contribution to their links. While in the first version of the game
<table><caption>Table 6: Nash equilibria for Example in Section 4.3</caption><thead><tr><th>Strategies</th><th>Payoffs</th><th>Final network g<sup>3</sup></th></tr></thead><tbody><tr><td>(1.i) a<sub>12</sub><sup>t</sup> = 0, a<sub>13</sub><sup>t</sup> = 0, a<sub>21</sub><sup>t</sup> = 0, a<sub>23</sub><sup>t</sup> = 0,<br/>a<sub>31</sub><sup>t</sup> = 0, a<sub>32</sub><sup>t</sup> = 0</td><td>(0, 0, 0)</td><td>(1) (2)<br/>3</td></tr><tr><td>(1.ii) a<sub>12</sub><sup>t</sup> = 0, a<sub>13</sub><sup>t</sup> = 0, a<sub>21</sub><sup>t</sup> = 0, a<sub>23</sub><sup>t</sup> = 1,<br/>a<sub>31</sub><sup>t</sup> = 0, a<sub>32</sub><sup>t</sup> = 0</td><td></td><td></td></tr><tr><td>(2.i) a<sub>12</sub><sup>t</sup> = 1, a<sub>13</sub><sup>t</sup> = 0, a<sub>21</sub><sup>t</sup> = 1, a<sub>23</sub><sup>t</sup> = 0,<br/>a<sub>31</sub><sup>t</sup> = 0, a<sub>32</sub><sup>t</sup> = 0</td><td></td><td></td></tr><tr><td>(2.ii) a<sub>12</sub><sup>t</sup> = 1, a<sub>13</sub><sup>t</sup> = 0, a<sub>21</sub><sup>t</sup> = 1, a<sub>23</sub><sup>t</sup> = 0,<br/>a<sub>31</sub><sup>t</sup> = 0, a<sub>32</sub><sup>t</sup> = 1,</td><td></td><td></td></tr><tr><td>(2.iii) a<sub>12</sub><sup>t</sup> = 1, a<sub>13</sub><sup>t</sup> = 0, a<sub>21</sub><sup>t</sup> = 1, a<sub>23</sub><sup>t</sup> = 1,<br/>a<sub>31</sub><sup>t</sup> = 0, a<sub>32</sub><sup>t</sup> = 0,</td><td></td><td>1 2</td></tr><tr><td>(2.iv) a<sub>12</sub><sup>t</sup> = 1, a<sub>13</sub><sup>t</sup> = 0, a<sub>21</sub><sup>t</sup> = 1, a<sub>23</sub><sup>t</sup> = 0,<br/>a<sub>31</sub><sup>t</sup> = 1, a<sub>32</sub><sup>t</sup> = 0,</td><td>(12.41, 11.61, 0)</td><td>3</td></tr><tr><td>(2.v) a<sub>12</sub><sup>t</sup> = 1, a<sub>13</sub><sup>t</sup> = 0, a<sub>21</sub><sup>t</sup> = 1, a<sub>23</sub><sup>t</sup> = 1,<br/>a<sub>31</sub><sup>t</sup> = 1, a<sub>32</sub><sup>t</sup> = 0,</td><td></td><td></td></tr><tr><td>(2.vi) a<sub>12</sub><sup>t</sup> = 1, a<sub>13</sub><sup>t</sup> = 0, a<sub>21</sub><sup>t</sup> = 1, a<sub>23</sub><sup>t</sup> = 0,<br/>a<sub>31</sub><sup>t</sup> = 1, a<sub>32</sub><sup>t</sup> = 1,<br/>and<br/>x<sub>12</sub><sup>t</sup> = 2.93, x<sub>21</sub><sup>t</sup> = 2.67, t = 1, 2, 3</td><td></td><td></td></tr><tr><td>(3.i) a<sub>12</sub><sup>t</sup> = 0, a<sub>13</sub><sup>t</sup> = 1, a<sub>21</sub><sup>t</sup> = 0, a<sub>23</sub><sup>t</sup> = 0,<br/>a<sub>31</sub><sup>t</sup> = 1, a<sub>32</sub><sup>t</sup> = 0</td><td></td><td></td></tr><tr><td>(3.ii) a<sub>12</sub><sup>t</sup> = 0, a<sub>13</sub><sup>t</sup> = 1, a<sub>21</sub><sup>t</sup> = 0, a<sub>23</sub><sup>t</sup> = 1,<br/>a<sub>31</sub><sup>t</sup> = 1, a<sub>32</sub><sup>t</sup> = 0,<br/>and<br/>x<sub>13</sub><sup>t</sup> = 1.53, x<sub>31</sub><sup>t</sup> = 0.67, t = 1, 2, 3</td><td>(3.03, 0, 2.29)</td><td>1 2<br/>3</td></tr></tbody></table>

players choose sequentially their strategies and then decide about their limitations on contributions for each period, in the second version the game is played simultaneously and players have constraints on overall capacities that they can redistribute over links and time. In our models, players make their decisions by maximizing the sum of the stage payoffs, but not the stage payoff. This farsightedness feature complicates computation of the equilibria. As a consequence, a limitation of our settings is that they cannot be applied to model network formation with very large number of asymmetric players.
We can think of several future research directions. In a possible extension of the model, the benefit from not using the whole capacity of a player can be added. More precisely, if player i chooses strategy $x_i^t = (x_{ij}^t : ij \in g^t)$ such that

$$ \bar{x}_i^t - \sum_{ij \in g^t} x_{ij}^t > 0, $$

then she can benefit from $\bar{x}_i^t - \sum_{ij \in g^t} x_{ij}^t$. This can be interpreted as a benefit from “not working” or from “having a free time”.

In another follow-up research direction, we can compare the subgame perfect equilibrium that we find in the paper with myopic equilibrium, when players choose their strategies myopically without taking into account the influence of their actions on future state represented by network. This would lead to repeated games, where myopic equilibrium (or the sequence of best replies) can be computed.

Furthermore, we are also interested in the issue of social welfare and the investigation of efficient networks. If the network is formed under cooperative approach to maximize the total utility, an interesting question would be whether the cooperative strategies represent the equilibrium. If this is not the case, it would be worth of exploring whether the payment scheme to sustain cooperation over time can be constructed; see Parilina and Zaccour (2022) for payment schemes in dynamic games with finite duration.
References

Baetz, O. (2015) Social activity and network formation, *Theoretical Economics* 10, 315-340.

Bala, V., Goyal, S. (2000) A noncooperative model of network formation, *Econometrica* 68(5), 1181-1229.

Ballester, C., Calvó-Armengol, A., Zenou, Y. (2006) Who's who in networks. Wanted: The key player, *Econometrica* 74(5), 1403-1417.

Ballester, C., Calvó-Armengol, A., Zenou, Y. (2010) Delinquent networks, *Journal of the European Economic Association* 8, 34-61.

Baumann, L. (2021) A model of weighted network formation, *Theoretical Economics* 16(1), 1-23.

Bayer, P., Guerdjikova, A. (2024) Optimism leads to optimality: Ambiguity in network formation, *Journal of Economic Dynamics and Control* 168, 104944.

Bayer, P., Herings, P.J.J., Peeters, R. (2021) Farsighted manipulation and exploitation in networks, *Journal of Economic Theory* 196, 105311.

Belhaj, M., Deroïan, F. (2018) Targeting the key player: An incentive-based approach, *Journal of Mathematical Economics* 79, 57-64.

Bloch, F., Jackson, M.O. (2006) Definitions of equilibrium in network formation games, *International Journal of Game Theory* 34, 305-318.

Bolletta, U. (2021) A model of peer effects in school, *Mathematical Social Sciences* 114, 1-10.

Bonacich, P.B. (1987) Power and centrality: A family of measures, *American Journal of Sociology* 92, 1170-1182.

de Callataÿ, P., Mauleon, A., Vannetelbosch, V. (2023) Myopic-farsighted absorbing networks, *Theory and Decision* 94, 405-422.

Colombo, L., Labrecciosa, P., Rusinowska, A. (2025) A dynamic analysis of criminal networks, *Journal of Economic Theory* 223, 105951.
Dutta, B., Ghosal, S., Ray, D. (2005) Farsighted network formation, *Journal of Economic Theory* 122(2), 143-164.

Golub, B., Hsieh, Y.-C., Sadler, E. (2024) On the difficulty of characterizing network formation with endogenous behavior, *Mathematical Social Sciences* 129, 107-110.

Goyal, S., Vega-Redondo, F. (2007) Structural holes in social networks, *Journal of Economic Theory* 137(1), 460-492.

Herings, P.J.J., Mauleon, A., Vannetelbosch, V. (2009) Farsightedly stable networks, *Games and Economic Behavior* 67, 526-541.

Herings, P.J.J., Mauleon, A., Vannetelbosch, V. (2019) Stability of networks under horizon-K farsightedness, *Economic Theory* 68, 177-201.

Hiller, T. (2017) Peer effects in endogenous networks, *Games and Economic Behavior* 105, 349-367.

in 't Veld, D., van der Leij, M., Hommes, C. (2020) The formation of a core-periphery structure in heterogeneous financial networks, *Journal of Economic Dynamics and Control* 119, 103972.

Jadbabaie, A., Kakhbod, A. (2019) Optimal contracting in networks, *Journal of Economic Theory* 183, 1094-1153.

Jackson, M.O. (2008) *Social and Economic Networks*, Princeton University Press, Princeton.

Jackson, M.O., Watts, A. (2002) The evolution of social and economic networks, *Journal of Economic Theory* 106 (2), 265-295.

Jackson, M.O., Wolinsky, A. (1996) A strategic model of social and economic networks, *Journal of Economic Theory* 71, 44-74.

Kochevadov, V.A., Sedakov, A.A. (2023) Dynamic Models of Competition with Endogenous Network Formation, *Doklady Mathematics* 108(Suppl 1), S56-S65.

König, M.D., Tessone, C., Zenou, Y. (2009) A dynamic model of network formation with strategic interactions, *CCSS Working paper No. CCSS-09-006*
König, M.D., Tessone, C., Zenou, Y. (2010) From assortative to dissortative networks: The role of capacity constraints, *Advances in Complex Systems* 13(04), 483-499.

König, M.D., Tessone, C., Zenou, Y. (2014) Nestedness in networks: A theoretical model and some applications, *Theoretical Economics* 9, 695-752.

Lagerås, A.N., Seim, D. (2016) Strategic complementarities, network games and endogenous network formation, *International Journal of Game Theory* 45(3), 497-509.

Lee, L.-F., Liu, X., Patacchini, E., Zenou, Y. (2021) Who is the key player? A network analysis of juvenile delinquency, *Journal of Business and Economic Statistics* 39, 849-857.

Liu, X., Patacchini, E., Zenou, Y., Lee, L.-F. (2012) Criminal networks: Who is the key player? Fondazione Eni Enrico Mattei Working Papers. Paper 690.

Luo, C., Mauleon, A., Vannetelbosch, V. (2021) Network formation with myopic and farsighted players, *Economic Theory* 71, 1283-1317.

Mauleon, A., Vannetelbosch, V. (2016) Network formation games, In: Y. Bramoullé, Y., Galeotti, A., Rogers, B.W., Editors, *The Oxford Handbook of the Economics of Networks*, Chapter 8, pages 167-190. Oxford University Press.

Navarro, N. (2014) Expected fair allocation in farsighted network formation, *Social Choice and Welfare* 43, 287-308.

Page, F.P., Jr., Wooders, M.H. (2009) Strategic basins of attraction, the path dominance core, and network formation games, *Games and Economic Behavior* 66(1), 462-487.

Page, F.P., Jr., Wooders, M.H., Kamat, S. (2005) Networks and farsighted stability, *Journal of Economic Theory* 120, 257-269.

Parilina, E., Zaccour, G. (2022) Payment schemes for sustaining cooperation in dynamic games, *Journal of Economic Dynamics and Control* 139, 104440.

Sadler, E., Golub, B. (2024) Games on endogenous networks, https://arxiv.org/abs/2102.01587v8.

Song, Y., van der Schaar, M. (2020) Dynamic network formation with foresighted agents, *International Journal of Game Theory* 49 (2), 345-384.
Teteryatnikova, M. (2021) Cautious farsighted stability in network formation games with streams of payoffs, *International Journal of Game Theory* 50, 829-865.

Vega-Redondo, F. (2016) Links and actions in interplay, In: Y. Bramoullé, Y., Galeotti, A., Rogers, B.W., Editors, *The Oxford Handbook of the Economics of Networks*, Chapter 9, pages 191-214. Oxford University Press.

Watts, A. (2001) A dynamic model of network formation, *Games and Economic Behavior* 34 (2), 331-341.

Zhang, J., Cui, Z., Zu, L. (2014) The evolution of free trade networks, *Journal of Economic Dynamics and Control* 38, 72-86.

Zhao, W., Sun, Y., Zhou, J. (2024) Sequential network design, Available at SSRN: https://ssrn.com/abstract=4980853 or http://dx.doi.org/10.2139/ssrn.4980853.

Zhou, J., Chen, Y.-J. (2015) Key leaders in social networks, *Journal of Economic Theory* 157(C), 212-235.
A Nash Equilibria for the Numerical Example in Subsection 3.2

<table><caption>Table 7: Nash equilibrium for subgame $\Gamma^2(g^1)$</caption><thead><tr><th>Initial network g<sup>1</sup></th><th>Strategies</th><th>Payoffs</th><th>Final network g<sup>3</sup></th></tr></thead><tbody><tr><td><img src="initial_network_g1.png" alt="Initial network g<sup>1</sup>" /></td><td><img src="strategies_g1.png" alt="Strategies for initial network g<sup>1</sup>" /></td><td><img src="payoffs_g1.png" alt="Payoffs for initial network g<sup>1</sup>" /></td><td><img src="final_network_g3.png" alt="Final network g<sup>3</sup>" /></td></tr><tr><td><img src="initial_network_g2.png" alt="Initial network g<sup>2</sup>" /></td><td><img src="strategies_g2.png" alt="Strategies for initial network g<sup>2</sup>" /></td><td><img src="payoffs_g2.png" alt="Payoffs for initial network g<sup>2</sup>" /></td><td><img src="final_network_g3.png" alt="Final network g<sup>3</sup>" /></td></tr><tr><td><img src="initial_network_g3.png" alt="Initial network g<sup>3</sup>" /></td><td><img src="strategies_g3.png" alt="Strategies for initial network g<sup>3</sup>" /></td><td><img src="payoffs_g3.png" alt="Payoffs for initial network g<sup>3</sup>" /></td><td><img src="final_network_g3.png" alt="Final network g<sup>3</sup>" /></td></tr></tbody></table>
<table><caption>Table 8: Nash equilibrium for subgame $\Gamma^1(g^0)$</caption><thead><tr><th>Initial network g<sup>0</sup></th><th>Strategies</th><th>Payoffs</th><th>Final network g<sup>3</sup></th></tr></thead><tbody><tr><td><img src="initial_network_g0.png" alt="Initial network g<sup>0</sup>"></td><td>t = 1, 2, 3:<br/>x<sub>12</sub><sup>t</sup> = 2.46, x<sub>13</sub><sup>t</sup> = 1.54, x<sub>21</sub><sup>t</sup> = 2.20,<br/>x<sub>23</sub><sup>t</sup> = 0.80, x<sub>31</sub><sup>t</sup> = 0.80, x<sub>32</sub><sup>t</sup> = 0.20</td><td>(13.83, 10.62, 3.81)</td><td><img src="final_network_g3.png" alt="Final network g<sup>3</sup>"></td></tr><tr><td><img src="initial_network_g1.png" alt="Initial network g<sup>1</sup>"></td><td>t = 1, 2, 3:<br/>a<sub>23</sub><sup>t</sup> = 0, a<sub>32</sub><sup>t</sup> = 0,<br/>x<sub>12</sub><sup>t</sup> = 2.5, x<sub>21</sub><sup>t</sup> = 2.5,<br/>x<sub>13</sub><sup>t</sup> = 1.5, x<sub>31</sub><sup>t</sup> = 1.0</td><td>(16.35, 9.39, 3.60)</td><td><img src="final_network_g2.png" alt="Final network g<sup>2</sup>"></td></tr><tr><td><img src="initial_network_g2.png" alt="Initial network g<sup>2</sup>"></td><td>a<sub>12</sub><sup>t</sup> = 1, a<sub>21</sub><sup>t</sup> = 1,<br/>t = 1, 2, 3:<br/>x<sub>12</sub><sup>t</sup> = 2.46, x<sub>13</sub><sup>t</sup> = 1.54, x<sub>21</sub><sup>t</sup> = 2.20,<br/>x<sub>23</sub><sup>t</sup> = 0.80, x<sub>31</sub><sup>t</sup> = 0.80, x<sub>32</sub><sup>t</sup> = 0.20</td><td>(13.33, 10.12, 3.81)</td><td><img src="final_network_g3.png" alt="Final network g<sup>3</sup>"></td></tr><tr><td><img src="initial_network_g3.png" alt="Initial network g<sup>3</sup>"></td><td>a<sub>13</sub><sup>t</sup> = a<sub>31</sub><sup>t</sup> = 1,<br/>t = 1, 2, 3:<br/>x<sub>12</sub><sup>t</sup> = 2.46, x<sub>13</sub><sup>t</sup> = 1.54, x<sub>21</sub><sup>t</sup> = 2.20,<br/>x<sub>23</sub><sup>t</sup> = 0.80, x<sub>31</sub><sup>t</sup> = 0.80, x<sub>32</sub><sup>t</sup> = 0.20</td><td>(13.33, 10.62, 3.31)</td><td><img src="final_network_g4.png" alt="Final network g<sup>4</sup>"></td></tr><tr><td><img src="initial_network_g4.png" alt="Initial network g<sup>4</sup>"></td><td>a<sub>13</sub><sup>t</sup> = a<sub>31</sub><sup>t</sup> = 1,<br/>t = 1, 2, 3:<br/>a<sub>23</sub><sup>t</sup> = a<sub>32</sub><sup>t</sup> = 0,<br/>t = 2, 3:<br/>x<sub>12</sub><sup>t</sup> = 2.5, x<sub>21</sub><sup>t</sup> = 2.5,<br/>x<sub>13</sub><sup>t</sup> = 1.5, x<sub>31</sub><sup>t</sup> = 1.00</td><td>(15.85, 9.39, 3.10)</td><td><img src="final_network_g5.png" alt="Final network g<sup>5</sup>"></td></tr><tr><td><img src="initial_network_g5.png" alt="Initial network g<sup>5</sup>"></td><td>a<sub>12</sub><sup>t</sup> = a<sub>21</sub><sup>t</sup> = 1,<br/>t = 1, 2, 3:<br/>a<sub>23</sub><sup>t</sup> = a<sub>32</sub><sup>t</sup> = 0,<br/>t = 1, 2, 3:<br/>x<sub>12</sub><sup>t</sup> = 2.5, x<sub>21</sub><sup>t</sup> = 2.5,<br/>x<sub>13</sub><sup>t</sup> = 1.5, x<sub>31</sub><sup>t</sup> = 1.00</td><td>(15.85, 8.89, 3.60)</td><td><img src="final_network_g6.png" alt="Final network g<sup>6</sup>"></td></tr><tr><td><img src="initial_network_g6.png" alt="Initial network g<sup>6</sup>"></td><td>a<sub>12</sub><sup>t</sup> = a<sub>21</sub><sup>t</sup> = 1, a<sub>13</sub><sup>t</sup> = a<sub>31</sub><sup>t</sup> = 1,<br/>t = 1, 2, 3:<br/>x<sub>12</sub><sup>t</sup> = 2.46, x<sub>13</sub><sup>t</sup> = 1.54, x<sub>21</sub><sup>t</sup> = 2.20,<br/>x<sub>23</sub><sup>t</sup> = 0.80, x<sub>31</sub><sup>t</sup> = 0.80, x<sub>32</sub><sup>t</sup> = 0.20</td><td>(12.83, 10.12, 3.31)</td><td><img src="final_network_g7.png" alt="Final network g<sup>7</sup>"></td></tr><tr><td><img src="initial_network_g7.png" alt="Initial network g<sup>7</sup>"></td><td>a<sub>12</sub><sup>t</sup> = a<sub>21</sub><sup>t</sup> = 1, a<sub>13</sub><sup>t</sup> = a<sub>31</sub><sup>t</sup> = 1,<br/>t = 1, 2, 3:<br/>a<sub>23</sub><sup>t</sup> = a<sub>32</sub><sup>t</sup> = 0,<br/>t = 1, 2, 3:<br/>x<sub>12</sub><sup>t</sup> = 2.5, x<sub>21</sub><sup>t</sup> = 2.5,<br/>x<sub>13</sub><sup>t</sup> = 1.5, x<sub>31</sub><sup>t</sup> = 1.0</td><td>(15.35, 8.89, 3.10)</td><td><img src="final_network_g8.png" alt="Final network g<sup>8</sup>"></td></tr></tbody></table>