Lecture notes for COMS 6998 - Social Network Economics
Fall 2013, Columbia University
by A. Chaintreau

---

Part B.2 - The Theory of Social Goods

Motivation

Most goods analyzed in traditional economic setting are exclusive and private. For any given apple, only one person can eat it entirely, and hence the utility I obtain from eating that apple affects your consumption in no particular way. But some goods are not exclusive, such as the provision of a park in your neighborhood, investment to reduce pollution in an area, or gifts made to charity that improves the human environment in which you live.

A (global) public good traditionally denotes a good which can be purchased or obtained due to a private effort but typically benefit all members of a society. In other words, I gain from the public good I helps produce, but only indirectly through those produced overall by the whole group. Starting in the 1960s, economic analysis predicted that these goods are typically undersupplied by voluntary contributions under utility maximizing strategy, leading to recommendations on the necessity of tax, subsidies, and a central state to coordinate efforts. In other words, some positive level of public goods are produced because one benefits personally from them. However, the ability to free ride on the effort of others individually discourages what would collectively bring a better outcome to all. One would like ideally to analyze this gap, and see how it can be reduced with minimal effort of intervention.

This theory was recently revived following the following observation: most non exclusive goods are not globally available but they affects the outcome of various agents differently. A (local, or networked) social good is one in which the goods produced by others only affect me when these are neighbors in a given graph. In such a setting, not only are the various utilities of nodes to take into account, but also the topological properties which dictates who benefits from whose efforts.

List of challenges we would like to answer:

First, in a situation where a system evolves as that of a public game, we would like to address some challenges related to predict its behavior:

• (Q1) Do there exist configurations that are self enforcing (i.e. Nash equilibrium of the game)? Which of these configurations, if any, are robust to small perturbation of the system? Under which conditions is such a configuration unique?
• (Q2) Are equilibria of the game related to topological properties of network? In particular how does the purchase of a social good relates to the importance of a node? When do we observe specialization, which denotes the fact that at equilibrium only a subset of nodes end up purchasing the good or exerting an effort, while all others free ride?

Second, some challenges on the modeling part:

• (Q3) Can we predict in which directions the system evolves when an edge is added or removed? More generally, can we relate a modification in the parameters of the game to the overall output of the system such as nodes participation or total utility. Such comparison is sometimes called, with analogy to the analysis of mechanical system, as comparative statics. Can we find the critical player or link whose removal or addition results in the largest or smallest change?
• (Q4) Are configurations obtained by the game efficient? This could either be defined in a strong sense - leading nodes to collectively maximize social welfare - or in a weaker sense - finding a point that cannot be strictly improved for all nodes. When it is not can we improve the efficiency of the game by proceedings first to an income redistribution (i.e., using tax and subsidy that are budget balanced).
• (Q5) Assuming you can produce a social good for a fixed marginal cost, how would you set price this product to maximize your profit? How much would price differentiation allow you to extract additional revenue?

Examples of social goods

Scenario 1: Procurement of a social good

Assume first that node $i$ faces a classic procurement problem, in which the nodes can obtain a quantity $x$ of a particular good for a fixed cost-per-unit. This decision can be represented as solving the following problem:

$$\max U_i(x) = b_i(x) - c_i\cdot x \;\textrm{such that}\; x\geq 0\;,$$ where $b$ is a non-decreasing, concave and differentiable function.

What is the solution to this problem?

• One typically assumes that $b_i'(0) >c_i$ and $b'_i(\infty) <c_i$. If the former (resp. latter) inequality does not hold, then the marginal utility per unit always stays strictly below (resp. above) the price, so this objective is maximized at $x=0$ (resp. $x=\infty$, in which case probably another constraint such as supply limit, or available of cash, becomes the deciding factor).
• When $b'_i(\infty) < c_i < b'_i(0)$, a point $\tilde{x}_i$ exists such that $b'_i(\tilde{x}_i)=c_i$ and by construction this point attains the maximum of the objective. (NB: this apparently assumes that the derivative $b'$ is continuous. Otherwise, one can show the same result where $\tilde{x}_i$ is defined as $\tilde{x}_i=\sup\{x\;|\;b'_i(x)\geq c_i\}$)

How is the procurement problem different for social goods?

Assume now that all nodes $i$ in an undirected graph $G$ faces a procurement problem, but that they get to enjoy not only the quantity of goods they purchase, but also the one their neighbors purchase. We have

$$\max U_i(x_i) = b_i(x_i + \sum_{j\in N(i)}x_j) - c_i\cdot x_i \;\textrm{such that}\; x_i\geq 0\;,$$ where $N(i)$ denotes all the nodes $j\neq i$ that are connected to $i$. The solution to this problem is more complex since the choice of nodes depend on each other. The key is to observe that, from the selfish viewpoint of node $i$, if we assume that all other nodes’ behaviors are fixed, it reduces to one classic procurement problem. One can then show the best reponse strategy that $i$ can apply is to set its procurement value $x_i$ to: $$x_i \leftarrow \max\left(\tilde{x}_i-x_{-i},0\right) \;\textrm{where}\; x_{-i} = \sum_{j\in N(i)} x_j\;.$$ In other words, with the quick notation $x_{-i}$ that denotes all the goods that $i$ receive for free from a social network effect, node $i$ will in general still enjoy the same amount of goods overall equal to $\tilde{x}_i$. However, now that a quantity $x_{-i}$ comes for free, $i$ will simply purchase the remaining amount herself. Note that this one exception: if the good received from neighbors already exceeds the value $\tilde{x}_i$, $i$ has no incentive to purchase anymore, but will enjoy additional goods.

Scenario 2: Provision of private/public goods

Assume that node $i$ faces a classic purchase problem, in which the nodes can obtain a quantity $x,y,z,\ldots$ of various goods subjects to an overall budget constraint $w_i$. Without loss of generality, we will assume that all goods have the same cost per unit (the unit can be otherwise normalized to achieve that). We focus on the case with two goods (again, no generality is lost here, since we wish to focus on the case of a single social good, we can consider all others to be spending $y$ amount on private goods). This decision can be represented as solving the following problem:

$$\max U_i(x,y) \;\textrm{such that}\; x\geq 0, y\geq 0, x+y\leq w_i\;,$$ where $U_i$ is a non-decreasing, concave function of both goods.

What is the solution to this problem?

• For any value of $w_i$ there exists a unique point $(\tilde{x}_i,\tilde{y}_i)$ maximizing the above problem. We introduce $\gamma(w_i)$ which is equal to $\tilde{x}_i$. Note that by monotonicity, we have $\tilde{y_i}=w_i-\tilde{x}_i=w_i-\gamma(w_i)$. The function $\gamma$ is called the income elasticity of demand, sometimes referred to as Engel’s curve.

• One important property captured by the above function is how demand for goods evolve with income. A priori, one assumes that more income leads to more purchase of a good, but reality have shown that this may not always be the case. One example is a “substitution by a superior good”: You may suddenly stops spending part of your income on your subway card if your income jumps as you win the lottery (assuming you want to stay in traffic jam and have little ecological conscience). However, such an example is an exception rather than a norm, and one may avoid this case by grouping substitutable goods: In the above example, one can define a “transportation” good in which the demand never decreases as a function of your income.

  In general, a good is called a normal good if and only if its income elasticity of demand is non-decreasing. In the above example, $x$ is a normal good if and only if $\gamma'_i(w)\geq 0$ for all $w$. Similarly, as $\tilde{y_i}=w_i-\gamma(w_i)$, $y$ is a normal good if and only if $\gamma'_i(w)\leq 1$ for any $w$. We will always assume that both are satisfied, and hence that the following condition is satified

  $$\textrm{(Strict Normality)}\; \forall i\;, \forall w\geq 0, 0<\gamma'_i(w)<1 \;.$$

How is the purchase different for social goods?

Assume now that all nodes $i$ in an undirected graph $G$ faces a purchase problem, but that the first good is social. The joint purchase problem accross all nodes becomes:

$$\textrm{(PB1)} \max U_i(x_i+\sum_{j}x_j,y_i) \;\textrm{such that}\; x_i\geq 0, y_i\geq 0, x_i+y_i\leq w_i\;,$$ where $N(i)$ denotes all the nodes $j\neq i$ that are connected to $i$.

As above, if we assume that all other nodes’ behaviors except for $i$ are fixed, it reduces to one classic purchase problem with slightly different input. We would like to express the solution as a transform of the original problem, to separate the effects of all nodes on node $i$’s decision.

The key observation is that a change of variable reduces to an optimization problem that is very close to the above one. If we introduce $s_i=x_i+x_{-i}$, the above problem formally becomes:

$$\textrm{(PB1, different form)}\; \max U_i(s_i,y_i) \;\textrm{such that}\; s_i\geq x_{-i}\;, y_i\geq 0\;, s_i+y_i\leq w_i+x_{-i}\;.$$ Except for the additional $s_i\geq x_{-i}$ constraint, this problem is identical to the one that the node will face would it be given to spend a total wealth $w'_i=w_i+x_{-i}$. $$\textrm{(PB2, unconstrained)}\; \max U_i(s_i,y_i) \;\textrm{such that}\; s_i\geq 0\;, y_i\geq 0\;, s_i+y_i\leq w_i+x_{-i}\;.$$ One could interpret this renormalized wealth as a “social income” which takes into account how $i$ is bound to benefits from other in its own purchase. This last objective would be optimized by purchasing the bundle $(\gamma_i(w_i+x_{-i}), w_i+x_{-i}\gamma_i(w_i+x_{-i}))$. From them on two situations can occur: (1) if $\gamma_i(w_i+x_{-i})\geq x_{-i}$, the optimal for \textbf{PB2} is a feasible solution of the constraint problem \textbf{PB1}, hence it is also optimal for that one. Otherwise, we have (2) $\gamma_i(w_i+x_{-i})< x_{-i}$; this denotes a situation in which, if $i$ would be given $w_i+x_{-i}$ in cash, it would spend less than an amount $x_{-i}$ on the first good. One can derive from the concavity of $U_i$ that, starting from $(x_{-i},0)$ with some extra cash $w_i$ it always pay off more to spend it on the second good. The optimal of the constrained problem \textbf{PB1} is then $(x_{-i}, w_i)$.

In summary, the best reponse strategy that $i$ can apply to set her own level of purchase is

$$s_i \leftarrow \max\left(\gamma_i(w_i+x_{-i}),x_{-i}\right) \\ y_i \leftarrow w_i + x_{-i} - s_i = \min\left(w_i+x_{-i} -\gamma_i(w_i+x_{-i}),w_i\right) \;,$$ or equivalently $$x_i \leftarrow \max\left(\gamma_i(w_i+x_{-i})-x_{-i},0\right) \\ y_i \leftarrow w_i - x_i \;.$$

Scenario 3: Exchange economy with differential social good

Exchange economy

In a pure exchange economy with two goods $x$ and $y$ (as usual, we will focus on a single social good, and agglomerate all other goods in a single one), nodes are allowed to exchange goods with each other to improve their wellbeing.

All nodes initially are given a bundle $(a_i,b_i)$ of each good, that they can exchange with each others as they wish. We say that $(p,1)$ is an equilibrium price (without loss of generality we can fix the price for the second good to be $1$) if we have:

1. Assuming that node $i$ first sells its whole bundle at market price and collect a wealth $w_i=p a_i + b_i$, it then acquires a new bundle $(x_i,y_i)$ by solving the optimization problem $$\max U_i(x,y)\;, p x + y \leq w_i = p a_i + b_i \;.$$
2. Once all nodes do that, the market clears which means $\sum_{i} x_i = \sum_{i} a_i$ and $\sum_{i} y_i = \sum_{i} b_i$.

It follows from Arrow Debreu result that an equilibrium price always exists when two conditions are met: (moderate satiability), $U_i$ is increasing, continuous and quasi concave, and (non exclusivity) $\forall i,\; a_i >0$ and $b_i>0$.

As an example, the function $U: (x,y) \mapsto x^{1-\beta} y^{\beta}$ attains its maximum subject to $px+y=w$ when $x=\frac{1-\beta}{p}w$, and $y=\beta w$. Summing among all $i$ we can deduce that $\sum_{i}x_i=\frac{1-\beta}{p} \sum_i {w_i}$ and $\sum_{i} y_i=\beta \sum_i {w_i}$, so that the only equilibrium price is $p=\frac{1-\beta}{\beta}\frac{\sum_{i} b_i }{ \sum_{i} a_i}$. As expected, $p$ increases with the supply of alternative good $y$, and decreases as more good $x$ are available.

Exchange economy with social differential good

A social differential good is one whose value is affected by your relative consumption w.r.t. your neighbors. In one simple linear case, we assume that the effective level of good $x$ that you enjoy is how much you objectively own, $x_i$, plus a differential term that linearly grows with the difference you observe $\sum_{j\in N(i)} (x_i-x_j)$, so that the utility you effectively enjoy is

$$\max U_i(x_i+\delta \sum_{j\in N(i)} (x_i-x_j), y_i) \;, p x_i+y_i \leq w_i = p a_i + b_i$$ where $\delta$ is a constant. When $\delta<0$ a richer neighbor is beneficial (positive externality) which reduces the demand of $i$, otherwise $\delta>0$ the consumption or purchase of a neighbor increases your demand as it “costs” you note to enjoy the same level as her (negative externality).

For instance, assuming $U: (x,y) \mapsto x^{1-\beta} y^{\beta}$, node $i$ solves the following problem:

$$\max \left( x_i+\delta \sum_{j\in N(i)} (x_i-x_j)\right)^{1-\beta} \left( y_i\right)^{\beta} \;, p x_i+y_i \leq w_i = p a_i + b_i \;.$$ Replacing $y_i=w_i-p x_i$ and deriving the objective, one can show that the best response of $i$ that solves this problem is to set $$x_i \leftarrow \frac{\beta \delta}{1+\delta |N(i)|} x_{-i} + \frac{1-\beta}{p} w_i \;\textrm{where, as usual},\; x_{-i}=\sum_{j \in N(i)} x_j\;.$$

Scenario 4: Positive/negative externalities

Various scenarios of social influence, negative/positive externalities and spillovers are initially analyzed assuming that the effect of others’ consumptions on a peer is linear.

Model of linear negative/positive externalities

This leads to develop this game as node $i$ maximizing a quadratic form:

$$\max U_i(x_i) = \alpha_i x_i + \sum_{j} \sigma_{i,j} x_i x_j \;, x_i \geq 0\;.$$ One assumes that $\sigma_{i,i}<0$ since it is necessary for this function to be strictly concave, and one can assume without loss of generality that $\sigma_{i,i}=-\frac{1}{2}$. (Redefine $x'_i=2|\sigma_{i,i}|x_i$ otherwise, which leads to $x'_i$ following the same form as above). We then have $$U_i(x_i) = \left(\alpha_i + \sum_{j} \sigma_{i,j} x_j\right) x_i - \frac{1}{2} x_i^2 \;.$$

One can immediately derive from the expression above that the best response of $i$ once all other nodes actions are fixed is:

$$x_i \leftarrow \max\left(\alpha_i + \sum_{j} \sigma_{i,j} x_j,0\right)\;.$$

Model of substitution

In accordance with the scenario seen above, we typically assume that users get to enjoy social good purchased by their neighbors for free. In other words, purchase or effort incurred by your neighbors play the role of a substitute to your own purchase or effort.

This is what happens in the above optimization when $\sigma_{i,j}$ is negative. As a general rule, the effect of substitution with someone’s else effort should not be stronger than the equivalent increase in your own effort, which implies that $|\sigma_{i,j}|<1$ or equivalently $-1\leq \sigma_{i,j} \leq 0$.

If we assume as above that in a social good the demand always decreases in a neighbor consumption, and that the consumption of all neighbors $j$ of $i$ affect this node in the same way, we have that $\sigma_{i,j}=-\delta_i g_{i,j}$ where $\delta_i$ is a constant and $g_{i,j}$ takes value $1$ if and only if $i$ and $j$ are neighbors. The best response then resembles the form we have already encountered above:

$$x_i \leftarrow \max\left(\alpha_i -\delta_i \cdot x_{-i},0\right)\;.$$

More general models are possible in which different neighbors have different strength of influence over $i$ (with coefficients $0\leq \delta_{i,j} \leq 1$).

Model of complementarity

This model allows to study also social goods that are complementary (for which demand increases as your neighbors’ consumptions gets larger). In which case, the coefficients $\sigma_{i,j}$ are positive.

Some additional condition is required to make sure that the system does not “blow up” as people encourage each other towards more consumption. Two examples of sufficient conditions are:

$$\sum_{j} \sigma_{i,j} < 1 \;\textrm{for any $i$.}$$ or, if we denote the spectral radius of a matrix $M$ by $\rho(M)$: $$\rho(\Sigma)<1 \;\textrm{where $\Sigma_{i,j}=\sigma_{i,j}$ for $i\neq j$ and $\Sigma_{i,j}=0$.}$$

Model with positive & negative externalities

One can build a more general model in which different nodes may interact as strategic substitute (i.e., $\sigma_{i,j}<0$) or complement (i.e., $\sigma_{i,j}>0$) to each other. One introduces two bounds, $\underline{\sigma}=\min \{\sigma_{i,j} \;|\; i\neq j\}<0$ and $\overline{\sigma}=\max \{\sigma_{i,j} \;|\; i\neq j\}$, as well as $\mu=\overline{\sigma}-\underline{\sigma}$. As seen above, we typically assume $|\underline{\sigma}|< 1$, as it captures that someone’s else effect is not a perfect substitute for your own effort, as well as $\mu>0$ to avoid degenerate cases.

We can then write

$$U_i(x_i) = \alpha_i x_i - \frac{1}{2} x_i^2 - |\underline{\sigma}| \sum_{j\neq i} x_i x_j + \mu \sum_{j} \delta_{i,j} x_i x_j = \alpha_i x_i - \frac{1}{2} \beta x_i^2 - |\underline{\sigma}| \left[ \frac{1}{2} x_i^2 + \sum_{j\neq i} x_i x_j \right] + \mu \sum_{j} \delta_{i,j} x_i x_j$$ where $\delta_{i,j}=\frac{\sigma_{i,j}+|\underline{\sigma}|}{\mu}$ which shows in particular that $0\leq \delta_{i,j} \leq 1$, and $\beta=1-|\underline{\sigma}|$.

so that the best response of node $i$ becomes

$$x_i \leftarrow \max\left(\alpha_i -|\underline{\sigma}| \sum_j x_j + \mu \sum_{j} \delta_{i,j} x_j,0\right)\;.$$ Note in particular, if $\sigma_{i,j}$ only takes two values (its maximum and minimum), the matrix defined by $\delta_{i,j}$ is the adjacency matrix of the graph connecting all pairs for which the coefficient is equal to the maximum.

The outcome of Social Good Games

General model

In all the models above, the best response of a node fits within the same form

$$x_i \leftarrow \max \left( \phi_i(x_{-i}), 0 \right) \;\textrm{where}\; x_{-i}=\sum_{j \in N(i)} x_j\;.$$ where $\phi_i$ is a continuous function (typically a linear one). Note that $\phi_i(0)$ denotes the equilibrium of the problem faced by $x$ in the absence of any social effect.

Existence of self-enforcing configuration

In almost all scenarios (Scenario 1, 2, and when externality is positive for 3 and 4), $\phi_i$ is a non-increasing function. In all other scenarios left, a condition always ensures that $x_i$ for any $i$ remains within a bounded domain after a best response is applied. This directly implies that the function that from a particular state of the system applies the best response simultaneously to all coordinates is continuous from a bounded convex domain to a bounded convex domain. According to a celebrated fixed point theorem attributed to Brouwer this shows that one vector $(x_i)_{i}$ exists such that

$$\forall i\;,\; x_i = \max \left( \phi_i(x_{-i}), 0 \right)\;.$$

This proves the general existence of a Nash equilibrium that describes a position of purchase/effort for all nodes from which none will deviate. Immediate questions that comes to mind are ‘Is that unique?’ in which case, we really characterized the only long term configuration of the system. ‘Is it robust to perturbation?’

Unicity of self-enforcing configuration

While the existence of a self-enforcing configuration is rarely an issue due to the general result above, ensuring that there do not exist multiple stable points is much more difficult.

Counter-examples abound in the literature: consider for instance Scenario 1 in which all effort/purchase from neighbors are perfect substitute for your own. Even in a simple case where all value $\tilde{x}_i=\tilde{x}$ are equal, any maximal independent set $S$ in the graph $G$ can be associated with a self-enforcing configuration in which all nodes in $S$ purchases $\tilde{x}$ amounts of good, and all other nodes purchases none. All nodes outside $S$ necessarily have a neighbor in $S$ and hence their best response is to remain passive. No node in $S$ has another neighbor in $S$ and hence receives no good from neighbors. There are hence at least as many equilibrium as independent sets in a graph.

A set of sufficient unicity conditions can however be constructed under the assumption that the effect of neighbors’ aggregate purchase on your own demand is small. How small? it depends on which exact game you look at and property of the graph. All proofs relies on the fact that the aggregate purchase of your neighbor $x_{-i}$ is the image of the purchase vector $x$ by the matrix $G$ representing the adjacency of the graph (with a null diagonal). We should hence describe its property.

Properties of the matrix $G$

Assuming that $G$ is symmetrix and real, we deduce that all eigenvalues of $G$ are real, we can therefore define its smallest $\lambda_{\min}$ and largest $\lambda_{\max}$. Since $G$ is non-negative, we know that its dominant eigenvalue (the one with maximum absolute value) is positive. It’s easy to see that, unless $G$ is empty, $\lambda_{\min}\leq 1$ as any vector containing a single $1$ $-1$ pair for coordinate corresponding to two connected nodes is an eigenvector for $-1$. In summary we have:

$$\textrm{Sp}(G)\subseteq [\lambda_{\min},\lambda_{\max}] \;\textrm{where}\; 0<1\leq -\lambda_{\min} \leq \lambda_{\max}$$

Examples:

• If $G$ is a complete graph, then $G=J-I$ where $J$ is a matrix containing only coefficients $1$. Since $\textrm{Sp}(J)=\{\lambda=0 \;\textrm{with multiplicity $n-1$}\;,\lambda=n\}$, $\textrm{Sp}(G)=\{-1 ,n-1\}$ and $\lambda_{\max}={n-1};\lambda_{\min}=-1$.
• If $G$ is a bipartite graph that contains an even number $n$ of nodes, with $\frac{n}{2}$ on each side, such that all nodes on the left are connected to all nodes on the right, one can show $\lambda_{\min}=-\frac{n}{2};\lambda_{\max}=\frac{n}{2}$.

Bonacich centrality

Let us consider an adjacency matrix $G$ associated with a graph $G=(V,E)$ (where $G_{i,i}=0$), a real number $\delta$ and a weight vector $\pi=(\pi_i)_{i\in V}$.

We define the weighted Bonacich centrality vector, that we denote by $b(G,\delta,\pi)$, to have $i$ coordinate:

$$b(G,\delta,\pi)_i = \sum_{k\geq 0} \sum_{j\in V} \delta^k G^k_{i,j} \pi_{j} \;.$$ One immediate question is whether this vector is even well defined for any weight $\pi$, as this series may diverge in general. We will treat that below but before that, we wish to interpret this definition.

Given that $G$ is an adjacency matrix and that $G_{i,i}=0$, the coefficient $G^k_{i,j}$ denotes the number of path of length exactly $k$ which can be drawn between $i$ and $j$. If we assume for simplicity that $\pi_i=1$ for all $i$, then the value $b(G,\delta,\pi)_i$ counts exactly the total weight of all paths in the graph that originate from $i$, where a path of length $k$ appears in this sum with a factor $\delta^{k}$. Intuitively a central node should have faster connection to many and hence should have a larger sum. This vector hence associates with each node a measure of its importance or influence, which is not a reflection of its degree alone, but more generally depends on its position in the global network.

Note that the parameter $\delta$ allows to tune this centrality to reflect the relative effect of distance, and the weight $\pi$ allows to consider that paths originating from $i$ that attain some particular nodes are more important than others. In most of the application $\pi$ is chosen uniform.

When is the Bonacich centrality well defined?

It generally depends on the value of $\delta$, which should be sufficiently small. One things that is certain is that if $G$ admits an eigenvector $v$ for a value $\lambda$, then $b(G,\delta,v)$ cannot be well defined unless $\delta \cdot |\lambda|<1$. This implies that $\delta<\frac{1}{\rho(G)}$ is a necessary condition, and it is sufficient as well.

When this condition is satisfied, we have

$$b(G,\delta,\pi) = \sum_{k\geq 0} \sum_{j\in V} \delta^k G^k \pi = (I-\delta G)^{-1} \pi \;,$$ where the fact that $G$ is invertible is a consequence of the same condition.

A first (simple) condition for unicity

In a nutshell, it is pervasive in the description and computation of equilibrium associated with social games, for the following reasons:

Assuming that $x_i$ is an equilibrium of a social good best response game:

$$x_i \leftarrow \max\left(\phi_i(x_{-i}),0\right) \;\textrm{where}\; x_{-i} = \sum_{j\in N(i)} x_j\;,$$ and assuming that $\phi_i$ is an affine function (chosen equal for all $i$ for simplicity), we have: $$x_i = \max(1-\delta x_{-i},0)\;.$$ If we now consider the network $G^A$ that is restricted to only the active nodes $A=\{i\in V\;|\; x_i>0\}$ in this equilibrium, we have: $$i\in A \implies x_i = \phi(0)-\delta x_{-i} \;.$$ which implies $(I+\delta G^A)x^A = \phi(0)\cdot e$ where $x^A$ is a vector of the strategy restricted to $A$, and $e$ is the vector $(1,\ldots,1)$, hence $x^A=b(G^A,-\delta,\phi(0)e)$.

This connection allows to make various observations that are used in the study of all the subcases we have introduced (and will be covered in the overview below).

For instance, in the case immediately above if $\delta$ is small enough, we can always avoid in this case that $x_i$ is null. Think for instance, of $\delta$ smaller than $\frac{1}{d_{\max}(G)}$ where $d_{\max}(G)$ denotes the maximum degree in $G$. Then in that case, the only equilibrium that can exist is found to be $x=b(G,-\delta,e)$.

This condition has various limitations: it seems only to apply when $\phi$ is linear, is also assumes that $\delta$ is very small. Can we obtain a more general condition that in particular apply to much larger value of $\delta$? This is what we will do in the next section.

A tight sufficient condition for unicity with social substitution

It turns out that for all scenarios above corresponding to social substitution effect (Scenarios 1, 2, and when externality is positive for 3 and 4), no other condition is required beyond a small magnitude of social substitution effect. A remarkably general result applies to any function $\phi$ that satisfies this condition. The most general result to date is:

Theorem [Allouch 12]: Assuming that the best response function $\phi$ defining the game

$$\forall i\;, x_i = \max \left( \phi_i(x_{-i}), 0 \right)\;, \;\textrm{ where $x_{-i}=\sum_{j\in N(i)}x_j=(G x)_i$ for a symmetric matrix $G$, }$$ satisfies $-\frac{1}{-\lambda_{min}}<\phi_i'<0$, where $\lambda_{min}$ is the smallest eigenvalue of $G$, then a unique equilibrium exists.

Note :

• Before looking at the proof, let us note that it is more general than most results in the literature as (1) it does not require any assumptions about the shape of $\phi$ like linearity, (2) the condition $\phi'>-\frac{1}{-\lambda_{min}}$ is more general than $\phi'>-\frac{1}{\lambda_{max}}$ which had been previously assumed and allows to use a simpler analysis. In some cases the difference is very significant (i.e., in the complete graph $\phi'>-\frac{1}{n-1}$ becomes $\phi'>-1$).

• Inspired by Scenario 2, this condition is sometimes referreed to as network normality by analogy with the necessary condition $0<\gamma'<1$ (equivalently, $-1<\phi'<0$) that precisely captures that goods are normal. Note that the network normality is always more constrained, it is equivalent whenever $\lambda_{\min}=1$, e.g., for a complete graph $G$.

• One can help wonder what happens when the condition above is not satisfied due to the network topology or the nature of the substitution. For instance, for the same game, different graph may lead to satisfying/not satisfying this condition for the same best response.

  It can be shown that counter-example exists as soon as $\phi'$ approaches the critical value $-\frac{1}{-\lambda_{\min}}$. In other words this theorem is tight. In fact, such cases may be found even for linear functions (i.e. $\phi'=-\delta$ where $\delta>0$ is a constant). In the linear case, the matrix $I+\delta G$ plays a key role in defining an optimization problem whose solutions are self-enforcing configurations. Unfortunately, as it happens as soon as $\delta (-\lambda_{\min}) \geq 1$, this matrix is not semi definite positive anymore, which renders the optimization

Proof

• First, the proof uses the following linear algebra result: Let $A,B$ be two square real matrices, then exactly one of the following statement is true:
  (i) There exist vectors $x^A>0$ and $x^B>0$ such that $A x^A = B x^B$.
  (ii) There exists a vector $x$ such that $x^T A \geq 0$, $x^T B\leq 0$, and ($A^T x\neq 0$ or $B^T x\neq 0$).

  People familiar with linear algebra will recognize here the characteristic flavor of result deriving from Farkas’ lemma which states that a vector either is included in a cone or (and this case is always exclusive of the first) should be separated from it by an hyperplane. This above form is rewriting a result by Stiemke for a particular case.

• STEP1 is to show that if two different Nash Equilibria exist, then the vector defined using the difference between them satisfies the statement $(ii)$ above for $A=R$ and $B=(I+aG)R$, where $0<a<\frac{1}{-\lambda_{min}}$ and $R$ is a diagonal matrix.

  Let $x^{(1)}$ and $x^{(2)}$ be two different Nash Equilibria. We recall that it means, for any $i$ that $x^{(1)}_i=\max\left(0,\phi_{i}(x^{(1)}_{-i})\right)$, maps the quantity of public goods received from neighbors by $i$, denoted $x^{(1)}_{-i}$, to the additional amount she purchases (which could be negative). The condition of the theorem implies in particular that $\phi_i$ is non-increasing (receiving more public goods for free never increases your own additional demand).

  We define $x^{\textrm{dif}}=x^{(1)}-x^{(2)}$ and $r$ as follows: $r_{i}=+1$ if $x^{(1)}_{-i}\leq x^{(2)}_{-i}$, and $r_i=-1$ otherwise (i.e., if $x^{(1)}_{-i} > x^{(2)}_{-i}$).

  Let $R=\textrm{Diag}(r_1,\ldots,r_n)$, we first note that since $x_{-i}=\sum_{j\in N(i)}x_j = (Gx)_i$, one can deduce $RGx^{\textrm{dif}}\leq 0$. Moreover, by definition of the Nash equilibria:

  $$(Rx^{\textrm{dif}})_i=r_i\left(\max\left(0,\phi_{i}(x^{(1)}_{-i})\right) - \max\left(0,\phi_{i}(x^{(2)}_{-i})\right) \right)\;.$$ Three things can be deduced from this statement. First, all coordinate of this vector are non-negative using the monotonicity of $\phi_i$ (i.e., $Rx^{\textrm{dif}}\geq 0$). Second, not all of them are null $Rx^{\textrm{dif}}\neq 0$ as otherwise it would imply that $x^{\textrm{dif}}=0$. Third, each coordinate is less than the difference inside the maximum $(Rx^{\textrm{dif}})_i \leq r_i\left(\phi_{i}(x^{(1)}_{-i})-\phi_{i}(x^{(2)}_{-i})\right)\;.$

  Note that we have already prove that $x^{\textrm{dif}}$ satisfies all the property of the statement $(ii)$ above except $(x^{\textrm{dif}})^T(I+aG)R\leq 0$, which is equivalent to $R(I+aG)x^{\textrm{dif}}\leq 0$

  Let us consider $i$ such that $x^{(1)}_{-i} \neq x^{(2)}_{-i}$. Note that, by the mean value theorem we have:

  $$\phi_i(x^{(1)}_{-i}) - \phi_i(x^{(2)}_{-i}) = \phi'_i(\beta_i) (x^{(1)}_{-i} - x^{(2)}_{-i})$$ where $\beta_i$ lies between the two numbers $x^{(1)}_{-i}$ and $x^{(2)}_{-i}$. From the inequality above, we deduce $$(R x^{\textrm{dif}})_i \leq r_i\left(\phi_{i}(x^{(1)}_{-i})-\phi_{i}(x^{(2)}_{-i})\right) = \phi'_i(\beta_i) (RGx^{\textrm{dif}})_{i} \;.$$ Note that the same inequality is trivially satisfied when $x^{(1)}_{-i} = x^{(2)}_{-i}$ (By definition of Nash Equilibria, such $i$ satisfies $x^{(1)}_i=x^{(2)}_i$).

  Let $a=\max_{i}\left(-\phi'_i(\beta_i)\right)\in ]0;\frac{1}{-\lambda_{min}}[$ where in the maximum, we only consider $i$ such that $x^{(1)}_{-i} \neq x^{(2)}_{-i}$ , we have then:

  $$R x^{\textrm{dif}}_i + a (R G x^{\textrm{dif}})_{i} \leq (a + \phi'_i(\beta_i)) (R G x^{\textrm{dif}})_{i} \leq 0$$ which completes this step.

• STEP2 starts from the observation that, since $(ii)$ above excludes $(i)$, the set $R(\mathbb{R}^n_{++})$ and $(I+aG) R(\mathbb{R}^n_{++})$ are disjoint, where $\mathbb{R}^n_{++}$ denotes the set of $n$ dimensional vectors whose all coordinates are positive. This contradicts that $(I+aG)$ is positive definite, for the following reasons: Both $R(\mathbb{R}^n_{++})$ and $(I+aG) R(\mathbb{R}^n_{++})$ are convex and open (as $\mathbb{R}^n_{++}$ and these transformation are invertible and continuous). As a consequence, if they do not intersect the hyperplane separation theorem implies that a vector $x_{\textrm{sep}}\neq 0$ and a scalar $a$ exists such that:

  $$x_{\textrm{sep}}^T R x\geq b \;\textrm{for any}\; x\in \mathbb{R}^n_{++}\;,$$ $$\textrm{and}\; x_{\textrm{sep}}^T (I+aG) R x\leq b \;\textrm{for any}\; x\in \mathbb{R}^n_{++}\;.$$ By continuity, all these inequalities hold for any $x\in \mathbb{R}^n_{+}$, the set of vectors whose coordinates are all non-negative. This implies that $b=0$ by applying the result to $x=0$, and also that $(x_{\textrm{sep}})_i R_{i,i} \geq 0$ for any $i$, since $R$ is a diagonal matrix. Given that the inverse of $R$ is the same diagonal matrix with inverse coefficients, this proves that $R^{-1} x_{\textrm{sep}} \in \mathbb{R}^n_{+}$. If we apply the second inequality to this vector we find $$x_{\textrm{sep}}^T (I+aG) R R^{-1} x_{\textrm{sep}} = x_{\textrm{sep}}^T (I+aG) x_{\textrm{sep}} \leq 0\;,$$ which is contradicting that $I+aG$ is positive definite.

Condition for Unicity with social complements

Social goods playing the role of a complement (such as Scenario 3 and 4 with negative externalities) are such that the demand grows as the neighbors purchase more, a striking contrast to the abovementioned case.

Various unicity results exist in such cases, subject again to a bound on the social effect of externality. We present two results below. They are generally more constrained: (1) only the linear case have been studied, (2) they have not in general been found to be tight condition, and (3) they typically requires a stronger conditions on the associated matrix.

We first consider the case where we have no substitution effect at all:

Scenario 4 with complements

In such cases, $i$ maximizes the utility

$$U_i(x_i) = \alpha_i x_i - \frac{1}{2} x_i^2 + \sum_{j} \sigma_{i,j} x_i x_j, \;\textrm{with}\; \forall i,j\;, \;\sigma_{i,j}\geq 0$$ which corresponds to $\phi_i(x_{-i})=\alpha_i+x_{-i}$ where we denote $x_{-i} = \sum_{j} \sigma_{i,j} x_j = (\Sigma x)_i$.

For a matrix $M$ we say its diagonal is strictly row dominating if: $\forall i,\; \sum_{j} |M_{i,j}|< M_{i,i}\;.$

Theorem [Candogan et. al 2012] If all coefficient of $\sigma$ are non-negative, and the matrix $I+\Sigma$ has strictly row dominating diagonal ($\;\textrm{i.e.}\; \forall i,\; \sum_{j} |\sigma_{i,j}| < 1$), then there exists a unique equilibrium.

Some remarks

• A matrix that has positive and strictly row dominating diagonal is in particular positive semi definite, so this condition is strictly stronger than having $\lambda_{\min}(\Sigma)>-1$ which would resemble the condition in the substitution case.
• The proof relies on the fact that the game only has strategic complements (a property which makes this game a supermodular game). In this condition, there always exists a maximum equilibrium $x_i$ (such that $x\geq y$ where $y$ is any other equilibrium). Having two equilibrium satisfying $x\geq y$ and $x\neq y$ leads to a contradiction (in a nutshell, considering the coordinate $k$ such that $x_k-y_k$ is maximum, $y_k$ being smaller at equilibrium requires that it receives more “compensation” than $x_k$, which is impossible if $\sum_{j} |\sigma_{k,j}|<1$).
• This result is not necessarily tight.

Scenario 4 with positive/negative externalities

In a slightly more general example of scenario 4 with positive and negative externalities, node $i$ maximizes the general form:

$$U_i(x_i) = \alpha_i x_i - \frac{1}{2} x_i^2 - |\underline{\sigma}| \sum_{j\neq i} x_i x_j + \mu \sum_{j} \delta_{i,j} x_i x_j$$ where $\mu>0$, $\delta_{i,j}=\frac{\sigma_{i,j}+|\underline{\sigma}|}{\mu}$ which shows in particular that $0\leq \delta_{i,j} \leq 1$, and we recall that we have assumed that $-1<\underline{\sigma}<0$.

Theorem [Ballester et. al 2006] If the matrix $\mu\Delta$ has spectral radius smaller than $\beta=1-|\underline{\sigma}|$, i.e., $\mu \rho(\Delta) < \beta = 1-|\underline{\sigma}|$, then there exists a unique equilibrium, in which everyone participates.

Notes:

• Note that when original coefficients $\sigma_{i,j}$ take only two values, $\Delta$ is a $\{0,1\}$ matrix where $1$ are positioned where $\sigma_{i,j}$ is equal to the maximum coefficient. Consider in particular $\sigma_{i,j} \in \{-|\underline{\sigma}|,0\}$. In this case, $\Delta=\bar{G}$. The matrix $\bar{G}$ corresponds to the adjacency matrix of the complementary graph of $G$, which is also equal to $J-I-G$ where $J$ contains only coefficient $1$ everywhere. We then have $\mu=|\underline{\sigma}|$, $\beta=1-\mu$, and the system is exactly the case of substitution with $\sigma_{i,j}=-\mu$ when $i$ and $j$ are neighbors.

  Note that in this linear homogeneous situation, $\phi'_i=-\mu$ for any $i$. The condition of the theorem becomes

  $$\mu \rho(\bar{G})<\beta=1-\mu \iff \rho(\bar{G})<\frac{1}{\mu}-1 \iff \mu <\frac{1}{1+\rho(\bar{G})} \;.$$ It resembles the general condition we had, except that $(-\lambda_{min}(G))$ is replaced by $1+\rho(\bar{G})$. Sometimes, the two conditions coincide (e.g., for a complete graph, both are $1$; for a balanced bipartite graph where each left/right node is connected to all nodes on the other side, both are $n/2$). However, the first condition is always more general $-\lambda_{\min}(G)\leq 1+\rho(\bar{G})$, and the two conditions can vastly differ, especially for small degrees as we have $$-\lambda_{\min}(G) \leq d_{\max}(G) \;\textrm{and}\; 1+\rho(\bar{G}) \geq n-d_{\max}(G) \;.$$ To prove this latter property, observe that for any adjacency matrix $H$ we have $d_{\min}(H) \leq \lambda_{\max}(H) \leq d_{\max}(H)$. Hence, $-\lambda_{\min}(G)\leq \lambda_{\max}(G) \leq d_{\max}(G)$ and $1+\rho(\bar{G})\geq 1+\lambda_{\max}(\bar{G}) \geq 1+ d_{\min}(\bar{G}) \geq n-d_{\max}(G)$. There is no easy proof for the previous general inequality between the two conditions, but it derives from the results on such games, which makes it an apparent oddity: an interesting inequality on matrices whose only proof derive from properties of games.

• The proof the theorem above has some similarities to the first proof in the complementary case but it is a bit simpler. First, from the assumption in the theorem one can show that once the set of active nodes is fixed the solution is unique by inverting the matrix. This shows in particular that an equilibrium where everyone participates exists.

  Second, an equilibrium in which only a subset $S$ of nodes participate would lead to a contradiction since the theorem condition applies to the graph restricted to $S$ applies. If we now consider a node that is not in $S$, the social effect should keep its own demand null. Because of the way the inverted matrix renormalizes demands everywhere in $S$, that implies that the overall social effect keeps demand null everywhere, which would be a contradiction.

Now that we have seen quite generally under which cases each of the game above admits a unique equilibrium, let us overview quickly the type of results that have been exposed about them. We wish to go faster, so as to later focus on some remarkable properties.

Overview of results obtained in the examples above

Scenario 1: Exact Substitute & Specialization

Y. Bramoullé and R. Kranton, “Public goods in networks,” Journal of Economic Theory, vol. 135, no. 1, pp. 478–494, Jul. 2006.

Summary of contributions:

• Presents a model of local public good (or social good) produced by effort. Each agent benefits not only from her own effort but efforts of Neighbors. Main assumptions:

  • A1 Effort exerted incurs a linear cost, and yield a non-decreasing concave return.
  • A2 Nodes are homogeneous in their cost and return function.
  • A3 Nodes are connected in an undirected graph, effort from neighbors are perfect substitute for one’s own effort.

  As a consequence, each node receives a return that depends on the sum of her effort and all of her neighbors (see model below).

• Focuses on characterizing the Nash Equilibrium of the game. Studies in particular the phenomenon of specialization, in which a subset of the nodes are doing maximum effort, while the others exert none.
• Prove (THM1) that specialized Nash equilibria are exactly the maximal independent set of the graph. This results extends beyond assumptions above in the following way
  • When neighbors effort are imperfect substitute (equivalent to $\delta$ times own effort, where $0<\delta<1$) (PROP2), or when the cost is convex (PROP4), there exists $k\in\mathbb{N}$ such that specialized Nash equilibrium of the game are exactly the maximum independent set of order $k$ (i.e., those for which any passive node are connected to at least $k$ active nodes).
  • When neighbors are heterogeneous, specialized Nash Equilibrium corresponds to a maximal independent set (but there is no converse in general).
• Show (THM2) that the locally stable Nash Equilibrium are exactly specialized ones that correspond maximal independent set of order $2$. Here, locally stable means that the system evolving by synchronous best response of all nodes returns to this equilibrium from a neighborhood of the equilibrium.
• Provides additional observations: an efficient allocation, maximizing social welfare, is generally different (e.g., if a node $i$ has a neighborhood strictly included in another $j$, it should work more in a Nash equilibrium, but $i$ would exert no effort in any efficient allocation). However, it can happen that efficient allocation are specialized.
  When considering the best Nash equilibrium as a reference, it is generally one that maximize the sum of effort weighted by degree (i.e. this holds rigorously only for almost linear return). Again, specialization is shown to possibly contribute to this efficiency.
• Finally, shows that adding a link to a network may not necessarily always increases the best Nash equilibrium obtained, while it obviously always increases the social welfare.

The model and the proof of these results are remarkably simple and clear, which is why we include them below for completeness:

• If a node $i$ exerts effort $x_i$ it receives net utility $$U_i(x) = b\left(x_i + \sum_{j\in N(i)} x_j\right) + c\cdot x_i \;,$$ where $b$ is the return function (non-decreasing concave) and $c>0$.
  More generally, one can consider $$U_i(x) = b_i\left(x_i + \sum_{j\in N(i)} x_j\right) + c_i(x_i) \;,$$ where $b_i,c_i$ are non-decreasing and respectively concave and convex.
• The evolution of the homogeneous game is rather straightforward. Let us first denote $x^*$ the effort level when a node is isolated (i.e., $b'(x^*)=c$). We denote by $x(N(i))$ the sum of effort of all neighbors of $i$, then $x_i$ will choose a best response strategy $x_i \leftarrow f_i(x)=\max(x^*-x(N(i)),0)$, since
  • either $x(N(i))\geq x^*$, and then the best response of $i$ is $x_i=0$,
  • or $x(N(i))< x^*$, and then the best response of $i$ is $x_i=x^*-x(N(i))>0$.
• The main proof in the paper is to show the instability of any other equilibrium than the one mentioned above. It follows from two observations about $f\circ f$ which is what happens after two synchronous nodal updates occur. First $f \circ f$ is non-decreasing: $x\leq x'\implies (f\circ f)(x) \leq (f \circ f) (x')$. Second, $f\circ f$ a amplifies difference locally: If we $(f\circ f)(x+\epsilon) \geq x+\epsilon$ when the coordinate $\epsilon_i$ is null for any specialized node (either passive or active), and equal to the same small positive constant for all other $i$. This implies that one never comes back to an initialy position with non-specialized nodes, or even when a specialized passive nodes is connected to a single active one.

Scenario 2: Purchase economy with social good

Given the generality of the problem formulation (with a utility function $U$ that can depend arbitrarily on $x$ and $y$) most of the results center on the qualitative property of redistribution. The key question is how the local effect of networks allow to revisit a celebrated result on the provision of global public good: the neutrality principle. See below.

N. Allouch, “On the Private Provision of Public Goods on Networks,” working paper, 2012.

N. Allouch, “The Cost of Segregation in Social Networks,” SSRN Journal, 2013.

are covered below

Scenario 3: Exchange economy

C. Ghiglino and S. Goyal, “Keeping up with the neighbors: social interaction in a market economy,” Journal of the European Economic Association, vol. 8, no. 1, pp. 90–119, 2010.

Summary of contributions:

• Introduces a model of complements for social good (i.e., demand grows as your neighbors consumptions grow). Node may be affected by the total consumption or by the average per neighbor consumption.
• Case 1: Sensitive to aggregate, homogeneous wealth. Shows (Prop1) that a unique equilibrium exists, which is interior, and goods are allocated according to Bonacich centrality. Shows that for small network effect, adding a link increases price of goods, and that the link with maximal impact derives from centrality, and have a local effect.
• Case 2: Sensitive to aggregate, heterogeneous wealth. The result on equilibrium extends to heterogeneous case when social effect is small. The effect of transferring endowements is connected to the centrality, and in particular it is null in regular networks (related to neutrality principle seen below).
• Case 3: Sensitive to average, homogeneous wealth. All the results from the Case 1 extends to this case.

Scenario 4: Linear externality & Bonacich centrality

General linear substitute/complements

C. Ballester, A. Calvó-Armengol, and Y. Zenou, “Who’s Who in Networks. Wanted: The Key Player,” Econometrica, vol. 74, no. 5, pp. 1403–1417, Sep. 2006.

Summary of contributions:

• Formalizes a quadratic form game whose best response is equivalent to a social good game with imperfect substitute/complements.
• Prove (THM1) that if social effect is sufficiently small (as a function of eigenvalues of the adjacency matrix), a unique Nash eq. exists, it is interior and it is described exactly using Bonacich centrality.
• Prove some comparison as parameters are changed (sometimes referred to as “comparative statics”): (THM2) increasing social effect always increases nodes outcome (i.e. the quadratic form).
• Prove (THM3) that the nodes whose removal maximizes/minimizes the overall outcome can be found with a variant centrality measure (inter-centrality).

Case of linear partial substitute

Y. Bramoullé, R. Kranton, and M. D’Amours, “Strategic interaction and networks,” American Economic Review (forthcoming), 2013.

Summary of contributions:

• Proposes a model that generalizes both (1) 2007 Bramoulle-Kranton model above work where neighbors’ efforts are perfect substitution, and (2) 2006 Ballester et al. paper on imperfect substitute and the effect of centrality.
• The main assumption of the model is that users play a local public good creation game in which their best response depends linearly on the aggregate effort (sum of effort) of their neighbor. This includes both linear substitute and linear complementarity.
  As above, the graph is assumed undirected, the cost linear as well. The isolated effort is generally assumed to be homogeneous, which may be what happens after normalization. One can show that, since the best response function is continuous, a Nash Equilibrium exists from Brouwer’s fixed point theorem. Moreover, all Nash Equilibria satisfy that non-null actions are given by Bonacich centrality on the induced graph of active nodes together with an inequality of sufficient effort for all passive nodes. It is also equivalent to maximizing a potential function that is a quadratic form, and local strict equilibria of this function are exactly the stable one (in a way defined using differential equations)
• The main parameter to vary in the paper is how much others’ actions in aggregate affects yours (i.e. the coefficient in the linear best response function). Most of the previous result were that, if this is sufficiently small, then many properties are guaranteed: the equilibrium is unique, it is based on the minimization of a quadratic form that is strictly convex and hence it can be found in polynomial time and usually stable. The positive result of this paper is to prove a different (generally larger) threshold under which all these properties remain.
• The paper also shows that the result above it tight. Above this treshold, various properties do not hold: the minimization used to find a Nash Equilibrium is not strictly convex anymore, making the problem to find on in general computationally difficult. There is at least one equilibrium that is not interior, which proves there are multiple ones if an interior exists by symmetry (e.g., in regular graphs). Moreover, no interior equilibrium can be locally stable (which is equivalent to be a local strict maximum of potential).
• Prove some comparison results between equilibrium:
  • Equilibrium with less active agents increases overall participation
  • Adding more social effect and/or link decreases overall max. participation, whether you start from the equilibrium with most participants or start from any other equilibrium and keep the same active nodes.
• Show these results are robust to variants: considering various level of connection or weight between nodes, and various level of social network effects, can be addressed using similar tools.

Provisioning a social good

An underlying result in the theory of social goods is that the outcome of the game is not efficient from a welfare standpoint. Hence, for the same exact production function and resource available, a different operating point would produce globally more benefits to all. It has been a stated goal of public economist to design mechanisms that can help to narrow this gap.

We will first survey a redistribution principle, which basically answer the question: can we hope to improve (without necessarily aiming at optimality) the outcome of a social good system by redistribution the wealth or resource available. We then overview one recent work who characterizes Pareto efficiency.

Tax, Redistribution and the Neutrality Principle

The case of a Global Public Good

T. Bergstrom, L. Blume, and H. Varian, “On the private provision of public goods,” Journal of Public Economics, vol. 29, no. 1, pp. 25–49, Feb. 1986.

Summary of contributions:

• A landmark paper that prove a general neutrality theorem, previously mentioned in a more constrained settings by a 1983 paper by P. Warr. According to this result, marginal redistribution of incomes or even tax may have no effect. Under the assumptions that the redistribution taxes each voluntary contributors less than the part of her original income that she initially affected to public good, every dollar taxed results in the loss of a voluntary dollar initially affected.

• An obvious way to increase public good provision is to tax all income and have the government purchase the good, a rather unpopular measure. Hence, follow up results from the neutrality property above are various corollaries on how to effectively produces an increase of public good with either redistribution of a minimal amount of taxation: in particular each of those is an example of a sufficient condition:

  • Redistribute to increase the aggregate wealth of all current contributors.
  • Collect some taxes from non-contributors and purchases public goods
  • Taxing any contributors more than the amount of her contribution and purchase public goods.

  Conversely, each of the following is a necessary condition:

  • When redistributing income, the set of contributors after taxation must be a strict subset of the original ones

• The case where players have identical utility functions (same taste or preferences) is of particular interest. In that case, the equilibrium can be described in details with a critical wealth $w^*$:

  • All positive contributors are strictly richer than $w^*$. In fact, they all consume the same amount of private good, and they spend exactly the difference $w_i-w^*$ on contributing public goods.
  • All non-contributors earns at most $w^*$ and spends this wealth entirely on private goods.

  The following results describes the effect of redistribution:

  • Pairwise wealth equalizing among non-contributors or among current contributors does not change the equilibrium (since it does not affect the set of contributors, this is a consequence of the general neutrality result).
  • Pairwise wealth equalizing from contributor to non-contributors decreases the equilibrium supply of the public good.
  • As a consequence, wealth redistribution obtained through equalizing a fraction of people or all of them never increases the equilibrium supply of the public good.

• The paper also contains an important result to prove that the Nash equilibrium of such system is unique when the income elasticity of demand (i.e., how your purchase of a good depends on your total wealth) is positive for both the public and private goods (such goods are usually referred to as normal goods, and this hypothesis avoids cases of inferior goods being replaced by others etc.).

At a high level, this paper proves that public goods such as parks, beautiful buildings and museums can only be supplied by large inequalities of income (visit Pittsburgh if you ever want to see a real world example) or taxation beyond one’s voluntary contribution (visit Paris or Versailles if you need another proof). Note that comparing these two methods from an efficiency, political or moral standpoint is beyond the scope of this class. One may argue that comparing the two cities above-mentioned allows many to reach a conclusion, but others could question the statistical significance of this test.

The general case of a social good

N. Allouch, “On the Private Provision of Public Goods on Networks,” working paper, 2012.

Summary of contributions:

• Consider a local version of the problem above - the provision of a social good as opposed to a (global) public good - and it shows that the neutrality principle only applies in some specific cases.
• This paper also has the merit to unify previous analyses of public goods. In particular results include linear best responses as a particular case to prove a general result on the unicity and stability of the Nash equilibrium. The general condition assumed is called network normality assumptions: it states that the income elasticity of demand for the social good has marginal increase bounded by $1$ (implied by the fact that the private good is normal, hence its demand will increase with wealth) and larger than $1-\frac{1}{(-\lambda_{min}(G))}$, where $G$ is the neighborhood graph that captures who benefits from whose investment.
• The paper then studies the effect of income redistribution and shows a much richer behavior than in the classical public good scenario.
  • First, it proposes an alternative (somewhat simpler) proof of the neutrality principle in the case where $G$ is the complete graph (the classical (global) public good case).
  • When income elasticity of demand are all identical and affine, it shows that the neutrality principle applies if and only if $G$ is a regular graph. It also observes that neutrality does not hold in general even for regular graph when demands are not identical.
  • All these proofs relies on the fact that the effect of redistribution is well captured by a variant of Bonacich centrality (with the introduction of a diagonal weight matrix). It’s possible in that case to relate the effect of redistribution and nodes’ degree, and in some cases to the eigenvector associated with the lowest value of $G$.

Analysis of Redistribution and tax

• A tax-redistribution vector $t$ is denoting for each node $i$ whether it is taxed $t_i<0$ or subsidized $t_i\geq 0$ on her initial wealth in order to affect the result of the public good purchase system. Note that a consequence from the fact that taxes and subsidies must cancel we have $e^T t=0$ where $e$ denotes a vector containing only coordinates equal to $1$.

We first prove an important result on the effect of redistribution:

Theorem [Allouch 12] Let us assume that all nodes contributes to the public good at equilibrium (i.e., the equilibrium is an interior point, with or without redistribution). Let $x^{(t)}$ the public good purchase of each node after redistribution $t$

$$x^{(t)}-x=(I+AG)^{-1}(I-A)t \;\textrm{where $A=$Diag$( a_1,\ldots,a_n)$}\;,$$ and the coefficients are chosen as follows: First, $a_i=1-\gamma'(x_{-i})$ if $t_i+x^{(t)}_{-i}=x_{-i}$ (this denotes the case where, from $i$’s standpoint, the redistribution and the adjustment of neighbors exactly cancels the tax/subsidy effect), and otherwise $a_i=1-\gamma_i'(\beta_i)$, where $\beta_{i}$ is a real number between $w_i+x_{-i}$ and $w_i+t_i+x^{(t)}_{-i}$ (the case in which $i$ is actually affected by redistribution of wealth).

• To prove the above result, it suffices to make two observations, the first is that such coefficient can be chosen so that we have: $$x^{(t)}_i-x_i+a_i\sum_{j\in N(i)} (x^{(t)}_j - x_j) = (1-a_i) t_i\;.$$ Indeed, if $t_i+x^{(t)}_{-i}=x_{-i}$, this equality becomes $x^{(t)}_i-x_i= t_i\;.$ Since we assume all nodes are contributors, we have $x^{(t)}_i-x_i=\phi^{(t)}_i(x^{(t)}_i)-\phi_i(x_i)=-(x^{(t)}_{-i}-x_{-i})=t_i$ and the equality holds for any $a_i$. If $t_i+x^{(t)}_{-i}\neq x_{-i}$, by mean value theorem, one can choose $\beta_i$ as above to have: $$x^{(t)}_i-x_i =\gamma'(\beta_i)(t_i+x^{(t)}_{-i}-x_{-i})-(x^{(t)}_{-i}-x_{-i}) \\ =(\gamma'(\beta_i)-1)(x^{(t)}_{-i}-x_{-i})+\gamma'(\beta_i)t_i\;.$$ This proves the above equality, which may be rewritten $(I+AG)(x^{(t)}-x)=(I-A)t$. It remains to show that $I+AG$ is invertible.
• The fact that $I+AG$ is invertible is not too surprising since $A$ is a diagonal matrix whose positive entries lies between 0 and $\frac{1}{-\lambda_{\min}}$. In fact, if all coefficients were to be equal the result would be trivial. The fact that they are different makes this is a little more technical. One possibility is the following, define $S=Diag(\sqrt{a_1},\ldots,\sqrt{a_n})$, then $S^2=A$ and $S$ and $A$ are invertible, hence we have $I+AG=S(I+SGS)S^{-1}$. Hence, $I+AG$ and $I+SGS$ have same spectrum. Fortunately, a result from Ostrowski states that the eigenvalues of $SGS$ may be written as $\theta_i\lambda_i$ where $\lambda_i$ is an eigenvalue of $G$ and $\theta_i$ lies between the smallest and largest eigenvalue of $S^2=A$, which is between a positive number and $\frac{1}{-\lambda_{\min}}$ strictly. This proves the result.
• If we assume that not all nodes are contributors (the system starts from a non-interior equilibrium), one could prove a similar result for redistribution restricted to the subset of contributing nodes (all others seeing no change and no subsidy or tax) and small enough not to create new contributors. The result then have to be applied to the graph restricted to contributors.

Proof of neutrality principle after redistribution in the complete Case

• First, all redistribution ending up with equal total public good produced if and only if

  $$\forall t \;\textrm{such that}\; e^T t =0\;,\; \sum_{i}x_i^{(t)}-x_i = e^T (I+AG)^{-1}(I-A)t =0\;.$$ One can see that an equivalent condition is that all coefficients of $e^T (I+AG)^{-1}(I-A)$ must be equal, implying that $e$ is a left eigenvector of this matrix. Indeed, that would be a sufficient condition, as the equality would hold for all such $t$. It is also necessary since having two different coefficient would easily yield a vector $t$ that contradicts the statement.

  Note that it is also equivalent to say that $e$ is a left eigenvector of the inverse matrix $(I-A)^{-1}(I+AG)$, which may also be rewritten $I+(I-A)^{-1}A(G')$ with $G'=I+G$. Note that $e$ is a left eigenvector of a matrix $M$ if and only if $M$ have sums of coefficient along columns that are all equal. So all the following statements are equivalent:

  (i) Neutrality principle holds
  (ii) $e$ is a left eigenvector of $(I-A)^{-1}(I+AG)$
  (iii) $e$ is a left eigenvector of $(I-A)^{-1}A(G')$ with $G'=I+G$
  (iv) $(I-A)^{-1}A(G')$ have sums of coefficients along columns that are all equal.

  NB: one may wonder why we are careful to distinguish left and right eigenvector since these generally corresponds when a matrix is symmetric and all matrices involved $A,G,I$ are symmetric. The problem is that the product of two symmetric matrices is not in general symmetric (unless they commute), so that $(I-A)^{-1}(I+AG)$ or even $AG$ is not a symmetric matrix.

• In the case of a complete graph, $G=J-I$ where $J$ is a matrix containing only coefficient 1 everywhere. So condition (iv) is satisfied if and only if $(I-A)^{-1}AJ$ has sum among columns that are identical.

  Note that the matrix $(I-A)^{-1}A$ is simply a diagonal matrix with ith entries $a_i/(1-a_i)$. $J$ has identical columns, hence $MJ$ for any matrix $M$ has identical columns (if columns are identical, the multiplication by any matrix on the left will also result in identical columns). This implies (iv) holds in this case, which proves the neutrality principle always hold no matter which function is used to define $A$. Note that the converse is also true: if (iv) needs to be satisfiied for a general matrix $A$ whose diagonal coefficients can be different, then it has to be that $G'$ for this graph has identical columns, which shows that the graph $G$ must be complete.

• In the general graph case where all demand functions are affine and identical, $A$ is a diagonal matrix whose entries are equal. Hence $(I-A)^{-1}A(G')=\frac{a}{1-a}G'$ and all columns are equal if and only if this is the case of $G$, which is true if and only if the graph is regular.

  One can find counter examples of regular graph with different affine functions in which the neutrality principle does not hold, which proves that the result above is the most general one can hope.

N. Allouch, “The Cost of Segregation in Social Networks,” SSRN Journal, 2013.

In this paper that follows up the result on the neutrality for social goods, the author shows that an asymptotic neutrality principle holds whenever the society is segregated. In other words, when one considers the actual welfare benefits of redistribution, it is non null in general when the network is not regular but it might become negligible in large network depending on the topology.

• Focusing on an affine income elasticity of demand, this paper shows that the welfare improvement from redistribution is related to the Bonacich centrality through a new measure, the Bonacich transfer index.
• It shows that the Bonacich transfer index can be computed in closed form using the main part of the spectrum of the adjacency matrix (i.e. the eigenvalues whose eigenvector are not orthogonal to $e=(1,\ldots,1)$).
• Models of segregated society (where nodes belong to different clusters and may connect differently to other nodes depending on the group they are part of) are shown to greatly differ in the Bonacich transfer and hence in the ability of social redistribution to be effective.

Towards Pareto efficiency

Beyond the topic of this class, one might consider a less incremental approach to improving efficency of games with public or social good. One recent work made several advances in order to deal with that problem. In a nuthsell, it considers more general mechanism than wealth redistribution, and studies conditions characterizing how they relate to a weak notion of efficiency.

M. Elliott and B. Golub, “A network approach to public goods,” presented at the EC ‘13: Proceedings of the fourteenth ACM conference on Electronic commerce, 2013.

Summary of contributions:

• Consider a system of costly actions with positive externalities which corresponds to a system of social good with substitution.
• Show that an action profile is Pareto efficient if and only the substitution matrix $B$ (or benefit matrix) satisfies $\rho(B)=1$. The coefficient $B_{i,j}$ denotes how much, from $i$’s viewpoint, $j$’s effort return compare to her own cost of increasing her own action. This relation allows to plan for coordinate action, by indicating the critical players to reach Pareto efficiency, and also the relative tax’s inefficiency ratio that would still allows to pyield some improvement.
• The paper then shows that designing stable tax/subsidy to nudge players to invest in the social good, and reach Pareto efficiency, reduces to finding a state for which the action becomes a principal eigenvector of the benefit matrix. The exact formulation of this result involves a definition of robust outcomes with price due to Lindahl.

Pricing a social good

Another domain of active research is to design profit maximizing pricing schemes for social goods.

Pricing with complement effect

O. Candogan, K. Bimpikis, and A. Ozdaglar, “Optimal pricing in networks with externalities,” Operations Research, vol. 60, no. 4, pp. 883–905, 2012.

This work considers a monopoly facing a linear production cost for a divisible good exhibiting social linear complement effect (i.e., your neighbor purchase encourages you to purchase more) which can in the general case be directed.

• It shows a general condition for the demand to reach a single equilibirum (see above)
• With individual price discrimination, the profit maximizing price is shown to derive from Bonacich centrality, and everyone purchases under a simple minimum return condition. An interesting network invariance or irrelevance result states that the price is uniform whenever the complement effects is symmetric (i.e., $G$ is an undirected graph).
• With uniform price, solving the profit maximizing problem for the directed graph becomes a polynomial problem. It essentially derives from increasing prices while accounting for some nodes dropping out due to the increase in price.
• With bipolar pricing, where goods is available to all at full price and only some at a single discounted price, the problem becomes NP hard. On the other hand, a provable approximation polynomial algorithm using a relation with max-cut.

F. Bloch and N. Quérou, “Pricing in Social Networks,” Games and Economic Behavior, vol. 80, no. C, pp. 243–261, Jul. 2013.

This paper considers the purchase of a non-divisible good whose intrinsic value $\theta_i$ is drawn uniformly in $[0;1]$ with an additional complement effects from neighbors’ purchase.

• For a monopolist, it shows a similar network invariance result in which even with price discrimination the optimal pricing strategy reduces to being uniform. Potential exploitation of nodes exactly compensates effect of lost sale on their neighbors. It shows that this result does not hold for non linear production costs, directed network.
• For the case of an oligopoly, the pricing game admits a unique equilibrium deriving by a closed form from the adjacency matrix and the firm competition matrix.
• The paper considers a different models of externalities (where local difference in prices end up boosting the demand), observing similar observation.

Pricing with substitution effect

M. Feldman, D. Kempe, B. Lucier, and R. P. Leme, “Pricing public goods for private sale,” presented at the EC ‘13: Proceedings of the fourteenth ACM conference on Electronic commerce, 2013.

Considers a scenario where agents value differently the access to one undivisible good which is shared between neighbors. In other words, a neighbor owning the good is a perfect substitute to you owning it. Focusing on a posted price strategy with no price discrimination, this paper considers the problem of maximizing a seller’s profit without competition. The game played by the players in general have multiple equilibrium (as seen in Scenario 1 above dealing with exact substitute).

• It shows that for a public (globally available) good, a constant approximation can be found in a strong sense. A uniform price exists in which the revenue for the worst case equilibrium is at least a constant of the revenue of the best equilibrium for any other price. Moreover, this result applies even when compared with the best revenue with price discrimination.
• For regular graphs, a price that does not depend on the network structure is shown to yield a revenue in the worst equilibrium that is at least a constant of the revenue for any other price in its worst equilibrium. This is significantly weaker, and it has to be, as counter-example showed that gap between worst and best, as well as gap due to price discrimination are not bounded in general.
• Following a different and specific proof, when the valuation distribution is uniform, a price of $\frac{1}{2}$ guarantees worst case revenue within $\frac{4}{e}$ of the optimal.

Further reading:

Games with incomplete information

A. Galeotti, S. Goyal, M. O. Jackson, F. Vega-Redondo, and L. Yariv, “Network games,” The Review of Economic Studies, vol. 77, no. 1, pp. 218–244, 2010.

Summary of main contributions:

• This paper argues that (1) complete information game have pathological behaviors (multiple equilibrium, non monotonous behavior), and (2) they imperfectly capture the common situation in which a node has little information about the network it interacts with. As an example, a node may make decision (i.e. taking a particular training program) before they can see a reward, as a prediction of their place in the network. They propose a different model.
• What if nodes can only predict their degree and acts based on that, but are otherwise blind of other’s people’s own neighborhood? A symmetric Bayesian equilibrium is one in which all nodes that know their degree acts according to the same (possibly random) strategy $\sigma(k)$. Note that when nodes have complete information.
• The main results are that Bayesian symmetric equilibrium exists quite generally, often involve pure deterministic strategy typically with a threshold: all neighbors above/below a certain critical degree act in a fixed particular way.
• The second main contribution is to show that, as opposed to complete information games in general, this game follows a monotonicity property.

Endogenous network

What if people are part of a social good games where the network is built strategically, following the classical “cost per edge” assumptions found in the “network formation” literature.

A. Galeotti and S. Goyal, “The law of the few,” American Economic Review, vol. 100, no. 4, pp. 1468–1492, 2010.

This paper considers a situation where people can strategically choose between purchasing a social good or a connection that makes them able to benefit from someone else purchase. This network formation model predicts that the stable equilibrium of the system is one where a small subset of supernodes purchase all the social goods, and are more connected while the others free rides by purchasing only a few connections to these super users.

Empirical work

How do real people behave in a game that reproduces some dynamics of public good game.

M. Wunder, S. Suri, and D. J. Watts, “Empirical agent based models of cooperation in public goods games,” presented at the EC ‘13: Proceedings of the fourteenth ACM conference on Electronic commerce, 2013.

More recent work:

X. Chen and S.-H. Teng, “A Complexity View of Markets with Social Influence,” ITCS ‘11: Proceedings of the 2th conference on Innovations in Theoretical Computer Science. 2011.

Shows that the complexity of finding a market equilibrium in an exchange economy with social effect on the utility of goods makes the problem quickly intractable.

---

Written with StackEdit.