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.
[1] 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.
[2] 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.
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.
approximates the distribution over a neighbors' degree from the configuration model with respect to a degree sequence represented by P. Given
Asymptotically, the belief that exactly m out of the d neighbors of player i choose action 1 follows a binomial distribution
Thus, the expected utility of player i of degree
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 Bayesian equilibrium of this network game is a strategy
Consider a network game of local provision of public good[4] 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,
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
Define the set of neighbors of player
Every individual must choose independently an action in
The gross payoff to agent i is assumed to equal 1 if
Providing the public good, i.e. choosing action 1 bears cost c, where
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.
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
Suppose that between any two of the N agents a link is formed independently with probability
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:
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:
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.