Next Article in Journal / Special Issue
Horizon-K Farsightedness in Criminal Networks
Previous Article in Journal
Validating Game-Theoretic Models of Terrorism: Insights from Machine Learning
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

The Evolution of Networks and Local Public Good Provision: A Potential Approach

1
Departamento de Economía, Edificio Amigos, Universidad de Navarra, 31009 Pamplona, Spain
2
Department of Economics, University of Antwerp, Prinsstraat 13, 2000 Antwerp, Belgium
*
Author to whom correspondence should be addressed.
These authors contributed equally to this work.
Submission received: 4 June 2021 / Revised: 24 June 2021 / Accepted: 29 June 2021 / Published: 2 July 2021
(This article belongs to the Special Issue Game Theory in Social Networks)

Abstract

:
In this paper, we propose a game in which each player decides with whom to establish a costly connection and how much local public good is provided when benefits are shared among neighbors. We show that, when agents are homogeneous, Nash equilibrium networks are nested split graphs. Additionally, we show that the game is a potential game, even when we introduce heterogeneity along several dimensions. Using this result, we introduce stochastic best reply dynamics and show that this admits a unique and stationary steady state distribution expressed in terms of the potential function of the game. Hence, even if the set of Nash equilibria is potentially very large, the long run predictions are sharp.
JEL Classification:
C72; D00; D83; H41; O31

1. Introduction

Individuals or firms often interact with each other; for example, researchers share their knowledge to produce joint research, and firms collaborate in R&D activities. In such instances, the benefits of these interactions frequently depend not only on some individual characteristics of the partners involved but also on investments such as the effort devoted to a research project or to engage in R&D activities.
These investments display the characteristics of a local public good: they are local because they present direct externalities only for agents who are collaborating; they are public because one’s investment benefits all one’s partners; and, once a collaboration is established, the more one invests, the less one’s partner’s incentives are to invest. Additionally, the pattern of collaborations is itself endogenous, as researchers and firms decide with whom to collaborate.
These applications have motivated several authors to investigate the properties of local public good games on endogenous networks [1,2,3]. The key insight of these models is that, when agents are allowed to unilaterally establish links, equilibrium networks display core-periphery structures in which few agents are the largest contributors who collaborate with each other (the core), while others link to them to partly or completely free ride on their contributions (the periphery).
However, the set of equilibria of these games is typically very large, as one’s public good contribution (and hence the incentives to link to others and to attract links) depends on one’s position in the network. While this multiplicity does not diminish the importance of the characterization results of [1,2,3], it is a limitation when bringing these models to the data and performing counterfactual analysis.
The aim of this paper is to propose a novel model of local public goods on endogenous networks whose predictions are in line with those of the previous literature but that can also be empirically tested. In particular, we propose a game that admits a potential [4]. In this game, heterogeneous players decide how much local public good to provide and with whom to link. Links are established unilaterally as in [5]; however, once two players are linked, they access each other’s public good provision. Hence, as spillovers are never negative, incoming links are always accepted. When a link is established, the two players involved have a collaboration.
We assume that players derive private benefits from their own public good provision, as well as from each pairwise collaboration with another player. While these benefits from the public good can be heterogeneous across players, throughout the paper we maintain the assumption that the concave benefits of a collaboration are the same for both players involved. The motivation for this choice is twofold. On the one hand, this would naturally result when the two players involved in a collaboration equally share its benefits. On the other hand, this assumption constitutes the key property for the game to admit a potential. In other words, the changes in utility due to a player’s deviation are captured by the change in the value of the potential function in the two states. We assume the (possibly heterogeneous) costs of direct provision of the public good are linear, although this assumption can be relaxed, as we discuss below.
First, we characterize the set of Nash equilibria of the (static) game for homogeneous players. In particular, we show that any Nash equilibrium network is a nested split graph. This is a class of core-periphery graphs in which one’s neighborhood is a subset of the neighborhoods of players with more links. Hence, the largest contributors form a core of connected players, while the other players only sponsor links, but do not receive any. This result hinges upon two properties. First, a player always links to the players providing the largest amount of the public good. Otherwise, it would be profitable for them to redirect a link to another player who produces more and to whom they are not already connected. Second, the gains from a connection are higher for players who have more neighbors. This is because a player’s public good provision has larger private returns as they become involved in more collaborations.
We, then, introduce the stochastic best reply dynamics of the game with heterogeneous players and study its steady state distribution over all possible networks and provisions in the economy. In the dynamics, time is discrete, and each time period is randomly selected to be either a link adjustment period or a public good provision adjustment period. If the period is a link adjustment period, a link between two players is randomly selected to be revised. This implies that, if the link is there at the beginning of the period, the player establishing the link decides whether to delete it; if the link is not there at the beginning of the period, the player decides whether to establish it. If the period is a public good provision adjustment period, a player is randomly selected from the population, and this player revises her public good provision.
While there is literature studying the stochastic dynamics of actions and play [6,7,8], differently from those models, here play (public good provision) is a continuous variable. Hence, this requires a different distribution of shocks from linking in the stochastic process. To stress this point, we separate decisions about links and actions.
The decisions of revising a link or the public good provision are taken myopically, in the sense that players decide given the current state of the economy without taking into account other possible deviations in reaction to their adjustments. When there are no other stochastic components, all pure strategy Nash equilibria of the game are absorbing states, as they are local maximizers of the potential function of the game. Furthermore, the dynamics converges to one of these Nash equilibria. Only the initial state of the economy and the order of play determine which equilibrium is selected.
However, we derive sharper predictions when these choices are stochastic, in the sense that the players’ payoffs are affected by an idiosyncratic random shock. This shock might be interpreted as a miscalculation of the value associated to a collaboration, to the returns of the public good provision, as idiosyncratic and unobserved characteristics that determine the success of collaboration, or of one’s investment in the public good.
Note that some papers assume shocks to player actions to determine which states are stochastically stable [9,10]. Here, instead, we assume that the stochastic shocks is to player payoffs, which has the advantage of giving us a probability distribution over all states. This allows us to derive a unique stationary steady state distribution of the stochastic best reply dynamics. This distribution is independent of the initial state of the economy and is constructed using the potential function of the game. Hence, the combinations of networks and provision, which entail a larger value for the potential, are more likely to emerge in the long run.
Additionally, this steady state distribution could be used to bring the model to the data, as in [11,12]. In this respect, it is important to note that we can derive this steady state distribution in the formulation of the problem, which allows for player heterogeneity. This is particularly relevant for future empirical applications of our model.
Our paper naturally relates to the literature studying games played on endogenous networks. The first papers in this literature mostly modeled network formation as a generic socialization effort [13,14,15,16] or based on not-fully-strategic decisions [17]. The seminal contribution of [1] provided a framework to study these games. Their analysis has been extended to allow for heterogeneous agents [2] and strategic complements [18,19]. Additionally, Ref. [3] introduced a budget constraint, and revisited the classical results of the public good games literature [20] for when spillovers are local and the network is endogenous.
The contribution of this paper, with respect to this literature, is to introduce a potential game approach for local public goods. The properties of potential games have been used before to theoretically study network games on fixed networks [21] and network formation games without strategic interactions [22]. To the best of our knowledge, we are the first to provide a characterization result for a local public good game with (one-sided) link formation.
Other papers introduced co-evolutionary processes of networks and play either using random graph models [23] or when players play a 2 × 2 game [7,24]. The authors in [17] studied the co-evolutionary process of networks and actions when players played a game with payoffs exhibiting strategic complements as in [25]. More related to this paper, Ref. [26] used a potential game approach to estimate peer effects on exogenous network, while [11] was the first to show how network formation processes can be estimated using the properties of potential games but without any other strategic interaction.
More recently, Ref. [12] developed a similar approach for a game of strategic complements in an endogenous network, and introduced a notion of equilibrium (k-Nash) that spanned from two-sided to one-sided link formation. Additionally, Ref. [27] studied the co-evolution of networks and behavior in a potential game and showed how the model could be estimated. The contribution of this paper with respect to this literature is twofold. First, contrarily to [12,27], we studied a game with non-linear best-replies. As a result, we could not make use of the techniques developed by [25] to characterize the equilibrium set. Second, despite this complication, we provide a characterization of Nash networks of the corresponding static game.
The paper proceeds as follows. Section 2 introduces the environment. Section 3 presents the results; in particular, in Section 3.1, we introduce the static game and derive its potential function; we also characterize its Nash networks when players are homogeneous; Section 3.2 introduces stochastic best response dynamics that have a unique stationary distribution that depends on the potential of the game. Section 4 concludes this paper. All proofs are in Appendix A.

2. Methods

We now introduce the setup of the model. Let N = 1 , 2 , , n with n 3 be the set of players and let i and j be typical members of this group. Each individual chooses, simultaneously, their local public good provision x i X = [ 0 , ) and a set of links with other players to access their provision. Player i’s linking strategy is denoted by a row vector g i = ( g i 1 , , g i n ) G i = { 0 , 1 } n , where g i i = 0 and g i j { 0 , 1 } for all i , j N , i j . Player i links to player j if g i j = 1 and g i j = 0 otherwise. Then, g = ( g 1 , , g n ) T .
The set of strategies of player i is denoted by S i = X × G i . Define S = S 1 × S 2 × × S n as the set of strategies of all players. A strategy profile s = ( x , g ) S specifies both the actions and the set of relations initiated by each player, while x i denotes the vector of provisions of all agents other than i. Similarly, let g i denote the matrix of interactions of all players but i. The network of links g is a directed graph; let G be the set of all possible directed graphs of n nodes. Define N i ( g ) = { j N : g i j = 1 } as the set of players with whom i has formed a link. Let η i ( g ) = | N i ( g ) | .
We assume that a link of player i to j allows both players i and j to enjoy the benefits of the relationship (i.e., the neighbor’s provision), although only player i pays the cost of establishing the link. For this reason, it is convenient to define the closure of g, which is an undirected network denoted by g ¯ = c l ( g ) , where g ¯ i j = m a x { g i j , g j i } for each i and j in N. Define N i ( g ¯ ) = { j N : g ¯ i j = 1 } as the set of players connected to i. In words, the set N i ( g ¯ ) defines the peer group of each player i.
The payoffs to player i under the strategy profile s = ( x , g ) are defined as U i ( x , g ) . The payoff function is assumed to be as follows:
U i ( x , g ) = f i ( x i ) + j N { i } g ¯ i j h i j x i + x j c i x i k i η i ( g ) ,
where c i > 0 reflects i’s cost of public good provision and k i > 0 is i’s cost to establish one link. We could assume that this cost is increasing in the number of existing links. This would affect the characterization of equilibrium networks but not the subsequent results on the steady state distribution of the best reply dynamics introduced below.
For brevity, we will sometimes write U i ( s ) instead of U i ( x , g ) . The game has local externalities: a player shares the public good only with her immediate neighbors. We assume that, for all i , j N , f i ( x ) and h i j ( x ) are twice continuously differentiable, increasing and strictly concave in x; f i ( 0 ) = 0 ; f i ( 0 ) > c i ; and lim x f i ( x ) + ( n 1 ) h i j ( x ) = m i < c i . In words, a player’s provision of the public good is positive in isolation and finite in the complete network.
Furthermore, we assume that h i j ( · ) = h j i ( · ) for all i , j N . This symmetry condition ensures that the benefits from a collaboration are the same for both agents involved, and it is key for the game to admit a potential. There is a path in g ¯ from i to j if either g ¯ i j = 1 , or there are m different players j 1 , , j m distinct from i and j, such that g ¯ i j 1 = g ¯ j 1 j 2 = = g ¯ j m j = 1 . A component of the network g ¯ is a set of players such that there is a path connecting every two players in the set and no path to players outside the set.
In a core-periphery graph, there are two groups of players, the periphery  P ( g ¯ ) and the core C ( g ¯ ) , such that, for every i , j P ( g ¯ ) , g ¯ i j = 0 , while, for every l , m C ( g ¯ ) , g ¯ l m = 1 ; moreover, for any i P ( g ¯ ) , there is l C ( g ¯ ) such that g ¯ i l = 1 . Nodes in C ( g ¯ ) are referred to as hubs. We write C and P instead of C ( g ¯ ) and P ( g ¯ ) , respectively, when no confusion arises.
A core-periphery network with a single hub is referred to as a star. A core-periphery network in which the sets of players’ neighbors are nested is a nested split graph: for any pair of players i and j, if η j ( g ¯ ) < η i ( g ¯ ) , then N j ( g ¯ ) { j } N i ( g ¯ ) { i } . A strategy profile s = ( x , g ) is a Nash equilibrium if for all s i S i and all i N , U i ( s ) U i ( s ) , where s = ( s i , s i ) .

3. Results

3.1. The Static Game

We now characterize the Nash equilibria of the static network formation game for the case of homogeneous players. This will show that our model delivers similar predictions to existing contributions regarding the shape of equilibrium networks [1,2,3]. We will then study the more general formulation of the model that allows for heterogeneous agents, as we believe this is more relevant for future empirical applications. In particular, we derive the potential of the game, which we will use to determine the long-run behavior of the stochastic best reply dynamics.

3.1.1. Homogeneous Agents: Characterization

We say that players are homogeneous if, for all i , j N , (i) c i = c , (ii) k i = k , (iii) f i ( · ) = f ( · ) , and (iv) h i j ( · ) = h j i ( · ) = h ( · ) . An important ingredient in finding a Nash equilibrium of the static game is defining a player’s gains from establishing a new connection. Given a network g and public good provision vector x , we define player i’s gain from a connection to player z who produces x z 0 and g ¯ i z = 0 as
G C i ( x , g + g i z ) = f i ( x ) + j N g ¯ i j h i j x + x j + h i z x + x z c i x f i ( x i ) + j N g ¯ i j h i j x i + x j c i x i ,
where x = arg max x 0 U i ( x , g + g i z ) is the effort that i exerts after accessing z’s provision of the public good.
Lemma 1.
Given ( x , g ) such that i is best-replying to other players’ action for the given network g, i.e., x i = arg max x 0 U i ( ( x , x i ) , g ) , if players are homogeneous, the gains from a connection G C i ( x , g + g i z ) are higher for i as i has more neighbors. Furthermore, i’s provision increases.
Lemma 1 shows that the gains from a connection are higher for players who have more neighbors, as a player’s public good provision has larger private returns when she is involved in more collaborations.
Given this positive relationship between links and public good provision, we can provide a sharp characterization equilibrium networks.
Proposition 1.
In any Nash equilibrium ( x , g ) with homogeneous players, g is a nested split graph.
The characterization of Proposition 1 emerges from Lemma 1 once we recognize a simple and yet powerful requirement of equilibrium behavior, i.e., that a player always links to the players providing the largest amount of public good. Otherwise, it would be profitable for her to redirect a link to another player who produces more and to whom she is not already connected. As a result, the largest contributors are connected, and form a core of interconnected players, while the others link to as many core players as it is profitable for them to do so.

3.1.2. Heterogeneous Agents: Potential Structure and Equilibrium Existence

Note that we have not yet shown equilibrium existence. Additionally, the static game we analyze admits, in general, a potentially large set of Nash equilibria. As a result, it is difficult to use the model to make empirical predictions or to bring this model to the data. To overcome this difficulty, in the next section, we analyze a best reply dynamics of the game and study its convergence properties.
To prove existence and to study the best reply dynamics, we rely on a particular feature of the game, that is, that it is a potential game, as defined by [4]. In fact, this holds for the general payoff function introduced in (1). The main feature we exploit is that h i j ( · ) = h j i ( · ) for all i , j N .
Proposition 2.
If h i j ( · ) = h j i ( · ) for all i , j N , the game is a potential game and a Nash equilibrium ( x , g ) always exists and is a local maximizer of its potential function, which is given by:
P ( x , g ) = i N f i ( x i ) k i η i ( g ) c i x i + j N { i } 1 2 g ¯ i j h i j x i + x j .
This result immediately follows once we recognize that changes in a player’s utility due to unilateral deviations are reflected in the corresponding change in the value of (2). Hence, the game is a potential game and P ( x , g ) is the potential function associated to the game.
Given that the game is a potential game, the existence of equilibrium follows immediately from the fact that the potential is continuous in public good provision and the set of possible networks is finite. This implies that the potential has as at least a maximum, which is a Nash equilibrium of the game.
Note that the characterization of the Nash equilibria of the static game with homogeneous agents of Proposition 1 might fail to hold for this general class of preferences. This is because now the gains from a connection might be very different for different players. Hence, while it is still the case that one always links to the players contributing the most, it is not obvious that these largest contributors have themselves the highest gain from a connection. Hence, a core might fail to exist.

3.2. A Stochastic Model of the Evolution of the Network and Public Good Provision

We now introduce a best reply dynamics that allows us to characterize the steady state distribution over possible realizations of networks and action profiles. This distribution can then be used to structurally estimate the model and to make predictions on how changes in the economic environment determine which equilibrium is more likely to emerge.
The co-evolution of networks and behavior is a stochastic best-response dynamic similar to that of [11,12,26,27]. Time is discrete and denoted by t = 0 , , and each time period is either a link-adjustment period (with probability 0 < p 0 < 1 ), or an effort-adjustment period (with probability 1 p 0 ).
We denote the realization of the network at time t as g t , and denote a link between i and j at time t as g i j , t . Finally, given a network g t such that g i j , t = 1 , we denote by g t i j the network including all the current links but removing the link from i to j, while if g i j , t = 0 , we denote by g t + i j the network including all the current links plus a link between i and j.

3.2.1. Link Adjustment

In a link adjustment period t, a pair i j is selected randomly from the set of players with probability p i j ( x , g ) > 0 for any i , j N that does not depend on the network at time t 1 , g t 1 . We assume p i j does not depend on the existence of a link between i and j, i.e., p i j ( x , g ) = p i j ( x , g + i j ) where g i j = 0 ; when no confusion may arise, we denote this probability by p i j . These assumptions are such that any player can be chosen and any pair of agents can meet, guaranteeing that any equilibrium network can be reached with positive probability.
When a pair i j is selected, then i can revise the linking strategy with respect to j.
Agents adopt a simple best response behavior, in the sense that they decide whether to sever, add, or maintain a link i j , thus, maximizing their payoffs of the period taking as given their efforts and the strategies of the other players. Hence, agents are myopic, as they do not take into account that others will adjust their best reply in the subsequent steps of the best reply dynamics. The decision is, however, stochastic, as players’ preferences are subject to a shock, that captures, for example, a player’s mistake in calculating the benefits of adding or removing a link.
In particular, there are two cases that need to be analyzed.
Case 1:   g t , i j g t . In this case, player i decides whether to delete the link with player j. This decision depends on the payoff obtained by i in the two cases, assuming that i’s payoffs are influenced by an idiosyncratic random shock. Hence, player i’s utility is given by:
U i , t ( x t , g t ) + ε ¯ i j if g i j is not severed U i ( x t , g t i j ) + ε ̲ i j if g i j is severed .
Note that ( ε ¯ i j , ε ̲ i j ) denote idiosyncratic random shocks associated with keeping or deleting the link. We assume ε ¯ i j and ε ̲ i j are i.i.d. across links and time periods and independent among each other; they follow a Type-I extreme value (or Gumbel) distribution with the distribution function F ( ε ) = exp [ exp ( ε / σ 2 ) ] . Since these components are not explained in the model, we will treat these collaboration specific factors as a random shock hitting the payoffs associated to each link of the network, where σ > 0 represents the level of noise in the adjustment process.
The shocks might be interpreted in many ways. One possibility is that the players might miscalculate the values associated with the collaboration. Alternatively, they can capture idiosyncratic match specific unobserved characteristics that determine the success of the joint project between i and j.
Let ε i j = ε ̲ i j ε ¯ i j . The link is not severed whenever
U i , t ( x t , g t ) + ε ¯ i j U i , t ( x t , g t i j ) + ε ̲ i j ,
that is, when:
U i , t ( x t , g t ) U i , t ( x t , g t i j ) ε i j .
Case 2: g t , i j g . In this case, player i decides whether to establish a link with player j. Recall that links are established one-sidedly, so j’s consent is not required for the link to exist. In particular, it could be that g t , j i g , in which case i, net of the idiosyncratic shock to the gains from linking, would have no incentive to reciprocate the link. Following the same arguments as before, it must be the case that player i wants to establish the link whenever it is profitable to do so. Hence, if player i wants to establish the link, the condition is the following:
U i , t ( x t , g t ) U i , t ( x t , g t + i j ) ε i j .
Let us now define
g t + = g t 1 if i j g t + g t 1 i j if i j g t + .
Hence, g t + is equal to g t 1 once we have deleted the link i j if g t , i j = 1 . Using (3) and (4), we can now summarize the dynamic behavior of the networks as follows:
g ˜ t + 1 = g t + + i j if U i , t ( x t , g t + ) U i , t ( x t , g t + + i j ) ε i j g t + otherwise .
The decision rule is stochastic and depends on the realization of ε i j . Given that the choice specific random shocks ε ̲ i j and ε ¯ i j follow Gumbel distributions, their difference ε ̲ i j ε ¯ i j is logistically distributed.

3.2.2. Public Good Provision Adjustment

If period t is not a link adjustment period, which happens with probability 1 p 0 , a player i is randomly selected from the population with probability p i > 0 for all i N , which we assume independent from the current network and provision. In that case, player i has the opportunity to revise her public good provision given the current network of collaborations (including her own) and other players’ provision and subject to random shocks. In particular, the probability that a player chooses public good provision x i , t Y X is given by
P r ( x i , t Y | g t 1 , x i , t 1 ) = Y exp [ U i ( ( y , x i , t 1 ) , g t 1 ) / σ 2 ] d y X exp [ U i ( ( x , x i , t 1 ) , g t 1 ) / σ 2 ] d x .
While this formulation allows for Y to be a set consisting of more than one element, we remember that, absent any stochastic shock, given a network and a profile of public good provision of all other players, the best reply for a player delivers a unique maximizer. This formulation can be interpreted as a random utility model over a non-finite choice set, where, again, σ > 0 represents the level of noise in the adjustment process.

3.2.3. Long-Run Predictions without Shocks

Before deriving predictions for the stochastic best reply dynamics, we derive a result pertaining to the best reply dynamics in the absence of idiosyncratic shocks to player payoffs.
Proposition 3.
When h i j ( · ) = h j i ( · ) for all i , j N , p 0 ( 0 , 1 ) , and there are no shocks, any pure-strategy Nash equilibrium is an absorbing state of the co-evolution process of the network and behavior. Furthermore, as t , the economy converges to a Nash equilibrium with Probability 1.
Proposition 3 shows that the absorbing states of best reply dynamics without shocks coincide with the set of Nash equilibria of the game. The intuition is straightforward: as, in a Nash equilibrium, no player has an incentive to deviate, in the absence of random shocks to player preferences, once a Nash equilibrium is reached, the economy will rest there forever. Furthermore, the fact that, in each period, either a link or a player’s public good provision is revised, from any state there is a weakly improving path leading to a Nash equilibrium.
However, the initial state of the economy and the order of revisions of play determine which Nash equilibrium will be reached. Next, we show how the introduction of shocks allows the derivation of a unique steady state distribution that resolves this indeterminacy.

3.2.4. The Steady State Distribution

We can now state the main result regarding the best reply dynamics that we introduced.
Proposition 4.
If p 0 ( 0 , 1 ) , p i j ( x , g ) ( 0 , 1 ) is independent on g i j , p i ( 0 , 1 ) , h i j ( · ) = h j i ( · ) for all i , j N , the co-evolution process of the network and behavior described so far converges to a unique stationary distribution characterized by the Gibbs measure
π ( x , g | θ ) = exp P ( x , g ) / σ 2 g G x X exp [ P ( x , g ) / σ 2 ] d x .
We prove this proposition by applying a combination of the arguments of [11,27]; in particular, players revise both links and actions, as in the second paper, but differently from there, link formation is one-sided as in the first paper.
Some remarks are in order. Proposition 4 stresses the role of the potential function in deriving the long run predictions of the stochastic best reply dynamics. Indeed, as a Nash equilibrium is a maximizer of the potential function (Proposition 2), a Nash equilibrium is more likely to arise than any other state. Additionally, due to the stochastic shocks, the economy is not stuck in a Nash equilibrium once that state is reached. This results in a unique steady state distribution over the networks and public good provision.
While an empirical application of the model goes beyond the scope of this paper, the fact that the distribution is unique allows for an estimation of its key parameters (for example, of the different functions h i j ( · ) describing the importance of collaborations among players). This, in turn, enables both comparative and counterfactual analyses that are not possible in the static version of the game.
Finally, in the model, we have not included any other benefits from adding links other than those coming from accessing the public good provision of others. However, links might have some value per se, and reciprocated links might be more valuable. As shown in [11], it would be easy to account for these concerns in players’ payoffs function without losing the potential property.

4. Conclusions

In this paper, we studied an environment in which players provide a local public good, that is, which benefits only those players who are directly connected to a provider. Additionally, players decide with whom to connect. Consistently with the previous results in the literature, we showed that, in all Nash equilibria of the static game in which homogeneous players simultaneously choose provision and links, the resulting network of spillovers is a nested split graph. Furthermore, we showed that this game admits a potential function.
As equilibrium multiplicity hinders the applicability of the model, we then introduced a stochastic best reply dynamics in which players were randomly allowed to myopically revise their public good provision and links. These choices were subject to idiosyncratic shocks. Under standard assumptions that allow for heterogeneous agents and using the properties of potential games, we derived the unique steady state distribution across all possible states of the economy.
In our paper, we assumed that only two agents collaborated on a project. Some recent work relaxed this assumption by studying the formation of teams of co-authors using different approaches. For example, Ref. [28] modeled the situation as a team formation problem, while [29] modeled it as a bipartite graph between researchers and projects. While it would be interesting to study multilateral collaboration in our framework, this is left for future research.
To conclude, we propose that this paper provides a tractable and flexible model with two main advantages. On the one hand, it delivers testable predictions via the sharp theoretical analysis. On the other hand, it allows for a structural estimation of the underlying parameters. We then hope that this model will be used to perform empirical analysis of local public good games on endogenous networks, which are, at the moment, very scarce in the literature.

Author Contributions

M.K. and L.P.M. contributed equally to this work. All authors have read and agreed to the published version of the manuscript.

Funding

Kinateder gratefully acknowledges financial support from the Spanish Ministry of Education and Science through grant PGC2018-098131-B-I00. Merlino gratefully acknowledges financial support from the Research Foundation Flanders (FWO), grant number G029621N.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

The study does not report any data.

Acknowledgments

We thank Paolo Pin and Angelo Mele for their comments and suggestions. The usual disclaimers apply.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. Proofs

Proof of Lemma 1.
In order to show that the gains from a connection are higher if i has more neighbors, consider wlog that all players but i provide the same amount of public good, i.e., x j = x ^ for all j N \ { i } . Then, if i has η neighbors in g,
G C i ( x , g + g i z ) = f ( x ) + ( η + 1 ) h ( x + x ^ ) f ( x i ) + η h ( x i + x ^ ) c ( x x i ) ,
By the envelope theorem, we have that
G C i ( x , g + g i z ) η = h ( x + x ^ ) h ( x i + x ^ ) .
Since by player i’s FOC it follows immediately that x > x i , G C i ( x , g + g i z ) / η > 0 , proving the claim of Lemma 1. □
Proof of Proposition 1.
Suppose that ( x , g ) is an equilibrium. Consider players i j who do not receive in-links. Hence, i , j P . Then, by Lemma 1 and the fact that players are homogeneous, x i = x j and N i ( g ) = N j ( g ) . Suppose not, and wlog that U i ( · ) > U j ( · ) . Then, given that both players receive no in-links, j can deviate profitably and choose ( x i , g i ) as well receive U j ( · ) = U i ( · ) . Suppose next that U i ( · ) = U j ( · ) , but g i l = 1 and g j l = 0 . Then, clearly, there is m l with x l = x m such that g i m = 0 and g j m = 1 , and as follows from Lemma 1, i can profitably connect with m, and j with l. Since ( x , g ) is an equilibrium, by hypothesis, there is no other player z such that either i or j (or both) can profitably link to z. So x i = x j and N i ( g ) = N j ( g ) .
Consider now players l m such that g i l = g i m = 1 for all i P . (If there is only one, i.e., l m , then the network is a star.) Next we show that g ¯ l m = 1 . In this case, G C l G C i , since l receives at least an in-link from i, and G C l > G C i if there is more than one periphery player. Since it is profitable for i to link to l, it is also profitable for m to link to l since G C m G C i , and by Lemma 1, x l > x i = x j . Hence, g ¯ l m = 1 for all l , m that receive in-links. By analogous arguments, as for all i P , it holds for all l , m as well that x l = x m and N l ( g ¯ ) { l } = N m ( g ¯ ) { m } .
Finally, consider some player q P such that g ¯ l q = g ¯ m q = 1 . Therefore, q is connected to all players receiving in-links and, since q P , there is some l such that g l q = 1 . (Otherwise, by the same argument as above, x q = x i = x j , N q ( g ) = N i ( g ) = N j ( g ) and q P .) However, since g i q = 0 for all i P , it holds that G C q < G C l = G C m , and, by Lemma 1 and the fact that players are homogeneous, it holds that x l = x m > x q > x i = x j . Finally, this implies that N i ( g ¯ ) = N j ( g ¯ ) N q ( g ¯ ) { q } N l ( g ¯ ) { l } = N m ( g ¯ ) { m } , where the first ⊂ follows from the fact that x q > x i = x j and the second from the fact that i , j link to m , l but not to q.
The existence of a core in which players have more in-links the more they produce implies that the unique component of the network is a nested split graph. This concludes the proof of Proposition 1. □
Proof of Proposition 2.
The fact that P ( x , g ) is the potential function of the game immediately follows once we recognize that
P ( x i , g i , x i , g i ) P ( x i , g i , x i , g i ) = U i ( x i , g i , x i , g i ) U i ( x i , g i , x i , g i ) .
The set of Nash equilibria is the set ( x , g ) such that U i ( x , g ) U i ( x i , g i , x i , g i ) for any ( x i , g i ) S i .
As P ( x , g ) is the potential function, we have that P i ( x , g ) P i ( x i , g i , x i , g i ) for any ( x i , g i ) S i . Hence, ( x , g ) is a maximizer of P. Following the same argument, the converse is easily checked.
To prove existence, first note that the potential function is continuous in a player’s public good provision. Hence, for each network, there exists at least a maximizer of the potential for a fixed network. As the number of possible network configurations is finite and discrete, at least a local maximizer of the full potential exists. As a result, a Nash equilibrium of the game always exists. This concludes the proof of Proposition 2. □
Proof of Proposition 3.
(Suppose ( x t , g t ) = ( x , g ) . Since this is a Nash equilibrium, players have no incentive to change their links nor their public good provision. Therefore, once the chain reaches a Nash equilibrium, it cannot escape from that state. This implies that a Nash network is an absorbing state of the chain.
Given a state ( x t , g t ) , the probability that the potential will (at least weakly) increase from t to t + 1 , P r [ P ( x t + 1 , g t + 1 ) P ( x t , g t ) ] is equal to 1 as, by definition, players are best responding to ( x t + 1 , g t + 1 ) and with probability 1 either a link or a player’s public good provision is updated.
As a Nash equilibrium is an absorbing state of the chain, any probability distribution that puts probability 1 on a Nash network is a stationary distribution. For any initial network, the chain will converge to one of the stationary distributions. It follows that, in the long run, the model will be in a Nash equilibrium, i.e., for any ( x 0 , g 0 ) S and denoting the set of Nash equilibria of the game as N E , lim t P r [ ( x , g ) N E | ( x 0 , g 0 ) ] = 1 . This concludes the proof of Proposition 3. □
Proof of Proposition 4.
By Proposition 2, P ( x , g ) is the potential function of the game. By this result, it follows that player i’s adjustment in a link or effort in the best reply dynamics is also captured by the corresponding changes in P ( x , g ) . It remains to prove that the Gibbs measure given in (6) is the unique stationary distribution of the best reply dynamics.
First note that the sequence ( x t , g t ) generated by the link and public good provision adjustment dynamics is a Markov chain. Inspection of the transition probability proves that the chain is irreducible and aperiodic, therefore it is ergodic. The existence of a unique stationary distribution then follows from the ergodic theorem (see, e.g., [30] for details).
A sufficient condition for stationarity is the detailed balance condition. In this game, this requires π ( ω 0 ) p ( ω 0 , ω 1 ) = π ( ω 1 ) p ( ω 1 , ω 0 ) , where p ( ω 0 , ω 1 ) is the transition density from state ω 0 to state ω 1 . In particular, ω 0 and ω 1 differ either in one link in the directed network g, if the period was a link adjustment period, or in one element of X , if the period was a public good provision adjustment period. We now consider the two cases separately:
(i): Link adjustment. Assume wlog that ω 0 = ( x , g ) with g i j = 0 and ω 1 = ( x , g + i j ) . Then,
π ( ω 0 ) p ( ω 0 , ω 1 ) = = π ( ω 0 ) p 0 p i j ( x , g ) exp P ( x , g + i j ) / σ 2 exp P ( x , g ) / σ 2 + exp P ( x , g + i j ) / σ 2 = = π ( ω 1 ) p 0 p i j ( x , g + i j ) exp P ( x , g ) / σ 2 exp P ( x , g ) / σ 2 + exp P ( x , g + i j ) / σ 2 = = π ( ω 1 ) p ( ω 0 , ω 1 ) .
(ii): Public provision adjustment. Assume wlog that ω 0 = ( x , g ) with g i j = 0 and ω 1 = ( ( x i , x i ) , g ) . Then,
π ( ω 0 ) p ( ω 0 , ω 1 ) = = π ( ω 0 ) ( 1 p 0 ) p i ( x , g ) exp [ U i ( ( x i , x i ) , g ) / σ 2 ] X exp [ U i ( y , g ) / σ 2 ] d y = π ( ω 0 ) ( 1 p 0 ) p i ( x , g ) exp [ P ( ( x i , x i ) , g ) / σ 2 ] X exp [ P ( y , g ) / σ 2 ] d y = π ( ω 1 ) ( 1 p 0 ) p i ( x , g ) exp [ P ( x , g ) / σ 2 ] X exp [ P ( y , g ) / σ 2 ] d y = π ( ω 1 ) ( 1 p 0 ) p i ( x , g ) exp [ U i ( x , g ) / σ 2 ] X exp [ U i ( y , g ) / σ 2 ] d y = π ( ω 1 ) p ( ω 1 , ω 0 ) .
Hence, (6) is a stationary distribution for the dynamic link and public good provision adjustment game. As we have shown, the process is ergodic and it has a unique stationary distribution. Therefore, π ( x , g | θ ) is also the unique stationary distribution. This concludes the proof of Proposition 4. □

References

  1. Galeotti, A.; Goyal, S. The Law of the Few. Am. Econ. Rev. 2010, 100, 1468–1492. [Google Scholar] [CrossRef]
  2. Kinateder, M.; Merlino, L.P. Public Goods in Endogenous Networks. Am. Econ. J. Microecon. 2017, 9, 187–212. [Google Scholar] [CrossRef]
  3. Kinateder, M.; Merlino, L.P. Free Riding in Networks. Technical Report; University of Antwerp: Antwerp, Belgium, 2021. [Google Scholar]
  4. Monderer, D.; Shapley, L.S. Potential Games. Games Econ. Behav. 1996, 14, 124–143. [Google Scholar] [CrossRef]
  5. Bala, V.; Goyal, S. A Noncooperative Model of Network Formation. Econometrica 2000, 68, 1181–1229. [Google Scholar] [CrossRef]
  6. Goyal, S.; Vega-Redondo, F. Network Formation and Social Coordination. Games Econ. Behav. 2005, 50, 178–207. [Google Scholar] [CrossRef] [Green Version]
  7. Staudigl, M.; Weidenholzer, S. Constrained Interactions and Social Coordination. J. Econ. Theory 2014, 152, 41–63. [Google Scholar] [CrossRef] [Green Version]
  8. Cui, Z.; Weidenholzer, S. Lock-in through Passive Connections. J. Econ. Theory 2021, 192, 105187. [Google Scholar] [CrossRef]
  9. Kandori, M.; Mailath, G.J.; Rob, R. Learning, Mutation, and Long Run Equilibria in Games. Econometrica 1993, 29–56. [Google Scholar] [CrossRef]
  10. Young, H.P. The Evolution of Conventions. Econometrica 1993, 57–84. [Google Scholar] [CrossRef]
  11. Mele, A. A Structural Model of Dense Network Formation. Econometrica 2017, 85, 825–850. [Google Scholar] [CrossRef] [Green Version]
  12. Badev, A. Nash Equilibria on k-stable Networks. Econometrica 2021, 89, 1179–1206. [Google Scholar] [CrossRef]
  13. Cabrales, A.; Calvó-Armengol, A.; Zenou, Y. Social Interactions and Spillovers. Games Econ. Behav. 2011, 72, 339–360. [Google Scholar] [CrossRef] [Green Version]
  14. Galeotti, A.; Merlino, L.P. Endogenous Job Contact Networks. Int. Econ. Rev. 2014, 55, 1201–1226. [Google Scholar] [CrossRef] [Green Version]
  15. Merlino, L.P. Formal and Informal Job Search. Econ. Lett. 2014, 125, 350–352. [Google Scholar] [CrossRef]
  16. Merlino, L.P. Informal Job Search through Social Networks and Vacancy Creation. Econ. Lett. 2019, 178, 82–85. [Google Scholar] [CrossRef]
  17. König, M.D.; Tessone, C.J.; Zenou, Y. Nestedness in Networks: A Theoretical Model and Some Applications. Theor. Econ. 2014, 9, 695–752. [Google Scholar] [CrossRef] [Green Version]
  18. Baetz, O. Social Activity and Network Formation. Theor. Econ. 2015, 10, 315–340. [Google Scholar] [CrossRef] [Green Version]
  19. Hiller, T. Peer Effects in Endogenous Networks. Games Econ. Behav. 2017, 105, 349–367. [Google Scholar] [CrossRef] [Green Version]
  20. Bergstrom, T.; Blume, L.; Varian, H. On the Private Provision of Public Goods. J. Public Econ. 1986, 29, 25–49. [Google Scholar] [CrossRef] [Green Version]
  21. Bramoullé, Y.; Kranton, R.; D’Amours, M. Strategic Interaction and Networks. Am. Econ. Rev. 2014, 104, 898–930. [Google Scholar] [CrossRef] [Green Version]
  22. Chakrabarti, S.; Gilles, R.P. Network Potentials. Rev. Econ. Des. 2007, 11, 13–52. [Google Scholar] [CrossRef]
  23. Hellmann, T.; Staudigl, M. Evolution of Social Networks. Eur. J. Oper. Res. 2014, 234, 583–596. [Google Scholar] [CrossRef] [Green Version]
  24. Staudigl, M. Potential Games in Volatile Environments. Games Econ. Behav. 2011, 72, 271–287. [Google Scholar] [CrossRef]
  25. Ballester, C.; Calvó-Armengol, A.; Zenou, Y. Who’s Who in Networks. Wanted: The Key Player. Econometrica 2006, 74, 1403–1417. [Google Scholar] [CrossRef]
  26. Nakajima, R. Measuring Peer Effects on Youth Smoking Behaviour. Rev. Econ. Stud. 2007, 74, 897–935. [Google Scholar] [CrossRef]
  27. Hsieh, C.S.; König, M.D.; Liu, X. A Structural Model for the Coevolution of Networks and Behavior. Rev. Econ. Stat. 2019, 1–41. [Google Scholar] [CrossRef]
  28. Bonhomme, S. Teams: Heterogeneity, Sorting, and Complementarity; Technical Report; University of Chicago: Chicago, IL, USA, 2020. [Google Scholar]
  29. Anderson, K.A.; Richards-Shubik, S. Collaborative Production in Science: An Empirical Analysis of Coauthorships in Economics. Rev. Econ. Stat. 2021. [Google Scholar] [CrossRef]
  30. Gelman, A.; Roberts, G.O.; Gilks, W.R. Efficient Metropolis Jumping Rules. Bayesian Stat. 1996, 5, 42. [Google Scholar]
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Kinateder, M.; Merlino, L.P. The Evolution of Networks and Local Public Good Provision: A Potential Approach. Games 2021, 12, 55. https://0-doi-org.brum.beds.ac.uk/10.3390/g12030055

AMA Style

Kinateder M, Merlino LP. The Evolution of Networks and Local Public Good Provision: A Potential Approach. Games. 2021; 12(3):55. https://0-doi-org.brum.beds.ac.uk/10.3390/g12030055

Chicago/Turabian Style

Kinateder, Markus, and Luca Paolo Merlino. 2021. "The Evolution of Networks and Local Public Good Provision: A Potential Approach" Games 12, no. 3: 55. https://0-doi-org.brum.beds.ac.uk/10.3390/g12030055

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop