Incomplete information network game

Network games of incomplete information represent strategic network formation when agents do not know in advance their neighbors, i.e. the network structure and the value stemming from forming links with neighboring agents. In such a setting, agents have prior beliefs about the value of attaching to their neighbors; take their action based on their prior belief and update their belief based on the history of the game. While games with a fully known network structure are widely applicable, there are many applications when players act without fully knowing with whom they interact or what their neighbors’ action will be.

For example, people choosing major in college can be formalized as a network game with imperfect information: they might know something about the number of people taking that major and might infer something about the job market for different majors, but they don’t know with whom they will have to interact, thus they do not know the structure of the network.

Game theoretic formulation

In this setting, players have private and incomplete information about the network and this private information is interpreted as player's own type (here, private knowledge of own degree). Conditional on their own degree, players form beliefs about the degrees of their neighbors. The equilibrium concept of this game is Bayesian Nash Equilibrium.The strategy of a player is a mapping from the player's degree to the player's action.

Let $\textstyle \sigma _{(d)}\in [0,1]$ be the probability that a player of degree d chooses action 1. For most degrees (d) the action will be either 0 or 1, but in some cases mixed strategy might occur.

The degrees of i's neighbor are drawn from a degree distribution $\textstyle {\tilde {P}}$, where $\textstyle {\tilde {P}}(d)={\frac {P(d)d}{\langle d\rangle }}$ approximates the distribution over a neighbors' degree from the configuration model with respect to a degree sequence represented by P.

Given $\textstyle {\tilde {P}}$, the probability that a neighbor takes action 1 is: $\textstyle p_{\sigma }=\sum _{d}\sigma (d){\tilde {P}}(d)$.

Asymptotically, the belief that exactly m out of the d neighbors of player i choose action 1 follows a binomial distribution $\textstyle \ {d_{i} \choose m}p_{\sigma }^{m}(1-p_{\sigma })^{(d_{i}-m)}$.

Thus, the expected utility of player i of degree $\textstyle \ d_{i}$ who takes action $\textstyle \ x_{i}$ is given by: $\textstyle \ U_{d_{i}}(x_{i},p_{\sigma })=\sum _{m=0}^{d_{i}}u_{d_{i}}(x_{i},m){d_{i} \choose m}p_{\sigma }^{m}(1-p_{\sigma })^{(d_{i}-m)}$, where $\textstyle \ u_{d_{i}}$ is the payoff corresponding to a game played on a certain network structure, in which players choose their strategies knowing how many links they will have but not knowing which network will be realized, given the incomplete information about the link formation of neighbors.

Assuming independence of neighbors' degrees, the above formulation of the game does not require knowledge of the precise set of players. The network game is specified by defining a utility $\textstyle \ u_{d}$ for each d and a distribution of neighbor's degrees $\textstyle {\tilde {P}}$.

The Bayesian equilibrium of this network game is a strategy $\textstyle \sigma (d)$ such that for each d, if $\textstyle \sigma (d)>0$, then $\textstyle \ U_{d}(1,p_{\sigma })\geq U_{d}(0,p_{\sigma })$, and if $\textstyle \sigma (d)<1$, then $\textstyle \ U_{d}(1,p_{\sigma })\leq U_{d}(0,p_{\sigma })$.

Example of imperfect information game played on networks

Consider a network game of local provision of public good when agent's actions are strategic substitutes, (i.e. the benefit of the individual from undertaking a certain action is not greater if his partners undertake the same action) thus, in the case of strategic substitutes, equilibrium actions are non-increasing in player's degrees.

Define a finite set of players or individuals, $\textstyle N=\left\{1,...,n\right\}$, connected in some network relationship.

The simplest framework is to think of an undirected network, where two agents are either connected or not.

Connections are represented by the adjacency matrix $\textstyle \ g\in \left\{0,1\right\}^{n\times n}$, with $\textstyle \ g_{ij}=1$, implying that i's payoff is affected by j's behavior.

Conventionally, $\textstyle \ g_{ii}=0$ for all $\textstyle \ i\in N$.

Define the set of neighbors of player $\textstyle \ i$ as $\textstyle \ N_{i}(g)=\left\{j|g_{ij}=1\right\}$.

The number of connections of player $\textstyle \ i$, i.e. its degree is given by $\textstyle \ k_{i}(g)=|N_{i}(g)|$.

Every individual must choose independently an action in $\textstyle \ X=\left\{0,1\right\}$, where 1 indicates taking that action an 0 indicates not doing so.

Payoff is defined as $\textstyle \ y_{i}\equiv x_{i}+{\overline {x}}_{Ni}$, which is the sum of $\textstyle \ x_{i}$, the action chosen by agent i and the aggregate action in the neighborhood defined as $\textstyle {\overline {x}}_{Ni}\equiv \sum _{j\in N_{i}}x_{j}$.

The gross payoff to agent i is assumed to equal 1 if $\textstyle \ y_{i}\geq 1$, and 0 otherwise. Providing the public good, i.e. choosing action 1 bears cost c, where $\textstyle \ 0<c<1$, while action 0 bears no cost. The net payoff of the game is defined as gross payoff minus the cost c. Given the cost, an agent would prefer that someone in his or her neighborhood take action 1 and would rather not take the action himself/herself. If someone else in the neighborhood of i contributes, public good is provided and agent i is free-riding. However, if nobody in the neighborhood of i contributes, agent i would be willing to contribute and take action 1.

Under imperfect information (players form beliefs about the degrees of the neighbors, summarized by a probability distribution), a player's pure strategy can be defined as a mapping $\textstyle \sigma$ from degree k to action $\textstyle \ X=\left\{0,1\right\}$. Suppose that between any two of the N agents a link is formed independently with probability $\textstyle \ p\in (0,1)$. The probability that any randomly selected neighbor is of degree k is the probability that the neighbor is connected to k-1 additional agents of the remaining N-2 agents and is given by:

$\textstyle \mathbb {Q} (k;p)={N-2 \choose k-1}p^{(k-1)}(1-p)^{(N-k-1)}$.

If an agent of degree k chooses action 1 in equilibrium, it follows from degree independence (assuming that n is infinitely large) that an agent of degree k-1 faces a lower likelihood of an arbitrary neighbor choosing action 1 and would be best responding by choosing action 1 as well. It can be shown that any equilibrium is characterized by a threshold. Denote with t the smallest integer for which the public good will be provided:$\textstyle \ 1-{[1-\sum _{k=1}^{t}Q(k;p)]}^{t}\geq 1-c$.

An equilibrium $\textstyle \sigma$ must satisfy $\textstyle \sigma (k)=1$ for all $\textstyle k<t$, $\textstyle \sigma (k)=0$ for all $\textstyle k>t$ and $\textstyle \ \sigma (t)\in [0,1]$. In particular, $\textstyle \sigma (k)$ is non-increasing.

It can be seen that the underlying network structure and the relation between network connections and actions influence the outcome of the game. Social connections create personal advantages: players with degree greater than t obtain higher expected payoff as compared to the less connected players of degree less than t.

Further reading

• Jackson, M. O., and L. Yariv (2005) "Diffusion on Social Networks," Economie Publique 16(1): 3-16.
• Jackson, M. O., and L. Yariv (2007) "The Diffusion of Behavior and Equilibrium Structure on Social Networks," American Economic Review (papers and proceedings) 97(2):92-98.
• Sundararajan, A. (2007) "Local Network Effects and Network Structure," BE Journal of Theoretical Economics 71(1): article 46.