Bayesian Learning in Social Networks Douglas Gale(Corresponding Author) Department of Economics. New York University 69 Mercer St. 7th Floor. New York. NY. 10003-668 E-mail: douglas. gale@nyu. Url:http://www.econ.nyuedu/user/galed/ Fax:(212)9953932 Shachar Kariv Department of Economics. New York Universi 269 Mercer St, 7th Floor, New York, NY, 10003-6687 e extend the standard model of social learning in two ways. First,we introduce a social network and assume that agents can only observe the actions of agents to whom they are connected by this network. Secondly, we allow agents to choose a different action at each date. If the network satisfies a connectedness assumption, the initial diversity resulting from diverse private information is eventually replaced by uniformity of actions, though not necessarily of beliefs. in finite time with probability one. We look at particular networks to illustrate he impact of network architecture on speed of convergence and the optimality of absorbing states. Convergence is remarkably rapid, so that asymptotic results are a good approximation even in the medium run. Journal of Economic Literature Classification Numbers: D82 D83 Key Words: Networks, Social learning, Herd behavior, Informational cascades Running Title: Bayesian Learning in Social Networks. assed this problem with Bob Rosenthal several years ago, when we were both at Boston University. At that time, we found the problem of learning in networks fascinating but made no progress and were eventually diverted into working or oundedly rational learning, which led to our paper on imitation and experimentation Ve thank seminar participants at NYU. DELTA, INSEAD. Cergy, Cornell and lowa for their comments. The financial support of the National Science Foundation through Grant No. SES-0095 109 is gratefully acknowledged
Bayesian Learning in Social Networks1 Douglas Gale (Corresponding Author ) Department of Economics, New York University 269 Mercer St., 7th Floor, New York, NY, 10003-6687. E-mail: douglas.gale@nyu.edu Url: http://www.econ.nyu.edu/user/galed/ Phone: (212) 998-8944 Fax: (212) 995-3932 and Shachar Kariv Department of Economics, New York University 269 Mercer St., 7th Floor, New York, NY, 10003-6687. E-mail: sk510@nyu.edu Url: http://home.nyu.edu/~sk510 Version: March 13, 2003. We extend the standard model of social learning in two ways. First, we introduce a social network and assume that agents can only observe the actions of agents to whom they are connected by this network. Secondly, we allow agents to choose a different action at each date. If the network satisfies a connectedness assumption, the initial diversity resulting from diverse private information is eventually replaced by uniformity of actions, though not necessarily of beliefs, in finite time with probability one. We look at particular networks to illustrate the impact of network architecture on speed of convergence and the optimality of absorbing states. Convergence is remarkably rapid, so that asymptotic results are a good approximation even in the medium run. Journal of Economic Literature Classification Numbers: D82, D83 Key Words: Networks, Social learning, Herd behavior, Informational cascades. Running Title: Bayesian Learning in Social Networks. 1One of us discussed this problem with Bob Rosenthal several years ago, when we were both at Boston University. At that time, we found the problem of learning in networks fascinating but made no progress and were eventually diverted into working on boundedly rational learning, which led to our paper on imitation and experimentation. We thank seminar participants at NYU, DELTA, INSEAD, Cergy, Cornell and Iowa for their comments. The financial support of the National Science Foundation through Grant No. SES-0095109 is gratefully acknowledged. 1
1. INTRODUCTION The canonical model of social learning comprises a set of agents 1,a finite set of actions A, a set of states of nature Q, and a common payoff function U(a, w), where a is the action chosen and w is the state of nature. Each agent i receives a private signal oi(w), a function of the state of nature w, and uses this private information to identify a payoff-maximizing action. This setup provides an example of a pure information externality. Each agent's payoff depends on his own action and on the state of nature. It does not depend directly on the actions of other agents. However, each agents action reveals something about his private signal, so an agent can generally improve his decision by observing what others do before choosing his own action. In social settings, where agents can observe one another's actions. it is rational for them to learn from one another This kind of social learning was first studied by Banerjee(1992)and Bikhchandani, Hirshleifer and Welch(1992). Their work was extended by Smith and Sorensen(2000). These models of social learning assume a sim- ple sequential structure, in which the order of play is fixed and exogenous. They also assume that the actions of all agents are public information Thus, at date 1, agent 1 chooses an action a1, based on his private in- formation; at date 2, agent 2 observes the action chosen by agent 1 and chooses an action a based on his private information and the information evealed by agent 1s action; at date 3, agent 3 observes the actions chosen by agents 1 and 2 and chooses an action a3.. and so on. In what follows we refer to this structure as the sequential social-learning model(SSLM) One goal of the social learning literature is to explain the striking uni- formity of social behavior that occurs in fashion, fads, "mob psychology and so forth. In the context of the SslM, this uniformity takes the form of herd behavior. Smith and Sorensen(2000) have shown that, in the SSLM, herd behavior arises in finite time with probability one. Once the proportion of agents choosing a particular action is large enough, the pub- lic information in favor of this action outweighs the private information of any single agent. So each subsequent agent"ignores"his own signal and follows the herd” This is an important result and it helps us understand the basis for uniformity of social behavior. At the same time. the sslM has several 2A herd occurs if, after some finite date t, every agent chooses the action. An informational cascade occurs if, after some finite date t, every agent finds it optimal to he same action regardless of the value of his private signal. An informational implies herd behavior, but a herd can arise without a cascade most interesting property of the models of Bikhchandani, Hirshleifer and Welch (1992)and Banerjee(1992)is that informational cascades arise very rapidly. before much information has been revealed. For example, models if the first two agents the same choice, all subsequent agents will ignore their information and imitate the first two. The behavior of a potential infinity of agents is determined by the behavior of the first two. This is both informationally inefficient and Pareto inefficient
1. INTRODUCTION The canonical model of social learning comprises a set of agents I, a finite set of actions A, a set of states of nature Ω, and a common payoff function U(a, ω), where a is the action chosen and ω is the state of nature. Each agent i receives a private signal σi(ω), a function of the state of nature ω, and uses this private information to identify a payoff-maximizing action. This setup provides an example of a pure information externality. Each agent’s payoff depends on his own action and on the state of nature. It does not depend directly on the actions of other agents. However, each agent’s action reveals something about his private signal, so an agent can generally improve his decision by observing what others do before choosing his own action. In social settings, where agents can observe one another’s actions, it is rational for them to learn from one another. This kind of social learning was first studied by Banerjee (1992) and Bikhchandani, Hirshleifer and Welch (1992). Their work was extended by Smith and Sørensen (2000). These models of social learning assume a simple sequential structure, in which the order of play is fixed and exogenous. They also assume that the actions of all agents are public information. Thus, at date 1, agent 1 chooses an action a1, based on his private information; at date 2, agent 2 observes the action chosen by agent 1 and chooses an action a2 based on his private information and the information revealed by agent 1’s action; at date 3, agent 3 observes the actions chosen by agents 1 and 2 and chooses an action a3 ...; and so on. In what follows we refer to this structure as the sequential social-learning model (SSLM). One goal of the social learning literature is to explain the striking uniformity of social behavior that occurs in fashion, fads, “mob psychology”, and so forth. In the context of the SSLM, this uniformity takes the form of herd behavior.2 Smith and Sørensen (2000) have shown that, in the SSLM, herd behavior arises in finite time with probability one. Once the proportion of agents choosing a particular action is large enough, the public information in favor of this action outweighs the private information of any single agent. So each subsequent agent “ignores” his own signal and “follows the herd”. This is an important result and it helps us understand the basis for uniformity of social behavior.3 At the same time, the SSLM has several 2A herd occurs if, after some finite date t, every agent chooses the same action. An informational cascade occurs if, after some finite date t, every agent finds it optimal to choose the same action regardless of the value of his private signal. An informational cascade implies herd behavior, but a herd can arise without a cascade. 3The most interesting property of the models of Bikhchandani, Hirshleifer and Welch (1992) and Banerjee (1992) is that informational cascades arise very rapidly, before much information has been revealed. For example, in these models if the first two agents make the same choice, all subsequent agents will ignore their information and imitate the first two. The behavior of a potential infinity of agents is determined by the behavior of the first two. This is both informationally inefficient and Pareto inefficient. 2
special features that deserve further examination: (i) each agent makes a single, irreversible decision; (ii) the timing of the agent's decision(his osition in the decision-making queue)is fixed and exogenous; (ii)agent observe the actions of all their predecessors; and (iv) the number of signals like the number of agents, is infinite. so once a cascade begins the amount of information lost is large. These features simplify the analysis of the SSLM, but they are quite restrictive In this paper, we study the uniformity of behavior in a framework that llows for a richer pattern of social learning. We depart from the SSLM two ways. First, we drop the assumption that actions are public infor- mation and assume that agents can observe the actions of some, but not necessarily all, of their neighbors. Second, we allow agents to make deci sions simultaneously, rather than sequentially, and to revise their decisions rather than making a single, irreversible decision. We refer to this structure as the social network model(sNM). For empirical examples that illustrate he important role of networks in social learning, see Bikhchandani. Hirsh leifer and Welch(1998) On the face of it, uniform behavior seems less likely in the SNM, where agents have very different information sets, than in the SSLM. However uniformity turns out to be a robust feature of connected social networks. The following results are established for any connected network: Uniformity of behavior: Initially, diversity of private information leads to diversity of actions. Over time. as agents learn by observing the actions of their neighbors, some convergence of beliefs is inevitable. A central question is whether agents can rationally choose different actions forever Disconnected agents can clearly 'disagree'forever. Also, there may be cases where agents are indifferent between two actions and disagreement of actions is immaterial. However, apart from cases of disconnectedness and indifference, all agents must eventually choose the same action. Thus, learning occurs through diversity but is eventually replaced by uniformity. Optimality: We are interested in whether the common action chosen asymp- otically is optimal, in the sense that the same action would be chosen if all the signals were public information. In special cases, we can show that asymptotically the optimal action is chosen but, in general. there is no reason why this should be the case. Although the process of learning in networks can be very complicated e SNM has several features that make the asymptotic analysis tractable. The first is the welfare-improvement principle Agents have perfect recall, so expected utility is non-decreasing over time. This implies that equilibri d A network is a directed graph in which the node Agent i can observe the actions of agent j if i is connected to agent 3. A network is onnected if, for any two agents i and j, there is a sequence il,. iK such that il =i. iK=j and ik is connected to ik+1 for k= l,,K-1
special features that deserve further examination: (i) each agent makes a single, irreversible decision; (ii) the timing of the agent’s decision (his position in the decision-making queue) is fixed and exogenous; (iii) agents observe the actions of all their predecessors; and (iv) the number of signals, like the number of agents, is infinite, so once a cascade begins the amount of information lost is large. These features simplify the analysis of the SSLM, but they are quite restrictive. In this paper, we study the uniformity of behavior in a framework that allows for a richer pattern of social learning. We depart from the SSLM in two ways. First, we drop the assumption that actions are public information and assume that agents can observe the actions of some, but not necessarily all, of their neighbors. Second, we allow agents to make decisions simultaneously, rather than sequentially, and to revise their decisions rather than making a single, irreversible decision. We refer to this structure as the social network model (SNM). For empirical examples that illustrate the important role of networks in social learning, see Bikhchandani, Hirshleifer and Welch (1998). On the face of it, uniform behavior seems less likely in the SNM, where agents have very different information sets, than in the SSLM. However, uniformity turns out to be a robust feature of connected social networks.4 The following results are established for any connected network: Uniformity of behavior : Initially, diversity of private information leads to diversity of actions. Over time, as agents learn by observing the actions of their neighbors, some convergence of beliefs is inevitable. A central question is whether agents can rationally choose different actions forever. Disconnected agents can clearly ‘disagree’ forever. Also, there may be cases where agents are indifferent between two actions and disagreement of actions is immaterial. However, apart from cases of disconnectedness and indifference, all agents must eventually choose the same action. Thus, learning occurs through diversity but is eventually replaced by uniformity. Optimality: We are interested in whether the common action chosen asymptotically is optimal, in the sense that the same action would be chosen if all the signals were public information. In special cases, we can show that asymptotically the optimal action is chosen but, in general, there is no reason why this should be the case. Although the process of learning in networks can be very complicated, the SNM has several features that make the asymptotic analysis tractable. The first is the welfare-improvement principle. Agents have perfect recall, so expected utility is non-decreasing over time. This implies that equilibrium 4A network is a directed graph in which the nodes correspond to representative agents. Agent i can observe the actions of agent j if i is connected to agent j. A network is connected if, for any two agents i and j, there is a sequence i1, ..., iK such that i1 = i, iK = j and ik is connected to ik+1 for k = 1, ..., K − 1. 3
payoffs form a submartingale. We use the martingale convergence theorem to establish that an agents(random) payoff converges almost surely to a constant Another useful property of the model is the imitation principle. If agent i can observe the actions of agent j, then one strategy available to him imitate whatever i does. Since i and j have different information sets. their conditional payoffs under this strategy may be different. However,on average, i must do as well as j The imitation principle, together with the connectedness of the network is used to show that, asymptotically, i and j must get the same average unconditional) payoffs. It turns out that this is only possible if agents choose the same actions. More precisely, agents choose different actions only if they are indifferent While the convergence properties of the model are quite general, other properties have only been established for particular networks Convergence in finite time: In special cases, we can rule out the possibility of indifference between actions with probability one. In that case, all agents choose the same action in finite time with probability one Speed of convergence: In two- and three-person networks, we can show that convergence to a uniform action is extremely rapid typically occurring within five or six periods with probability close to 1. What happens in those first few periods is important for the determination of the asymptotic state Network architecture: Systematic differences can be identified in the behav ior of different networks. For example, in three-person complete networks (where each agent observes all the others ), learning stops almost immedi- ately and the probability of an incorrect action in the long run is high. In hree-person incomplete networks, learning continues for a longer time and he probability of choosing an incorrect action in the long run is lower The rest of the paper is organized as follows. In Section 2 we define the model and the equilibrium concept more precisely. In Section 3 we use the case of two-person networks to illustrate the working of the general model and some special features of complete networks. In Section 4 we derive the asymptotic properties of the general model. In Section 5 we study a selection of three-person graphs. Here we see the impact of lack of common knowledge on the dynamics of social learning and the efficiency of aggregation. We also compare the dynamic and asymptotic properties of different networks. The results are discussed in Section 6. Proofs are gathered in Section 7 2. THE MODEL The social learning literature ignores the complications of strategic be- havior in order to focus on pure Bayesian learning. Non-strategic behavior
payoffs form a submartingale. We use the martingale convergence theorem to establish that an agents’ (random) payoff converges almost surely to a constant. Another useful property of the model is the imitation principle. If agent i can observe the actions of agent j, then one strategy available to him is to imitate whatever j does. Since i and j have different information sets, their conditional payoffs under this strategy may be different. However, on average, i must do as well as j. The imitation principle, together with the connectedness of the network, is used to show that, asymptotically, i and j must get the same average (unconditional) payoffs. It turns out that this is only possible if agents choose the same actions. More precisely, agents choose different actions only if they are indifferent. While the convergence properties of the model are quite general, other properties have only been established for particular networks: Convergence in finite time: In special cases, we can rule out the possibility of indifference between actions with probability one. In that case, all agents choose the same action in finite time with probability one. Speed of convergence: In two- and three-person networks, we can show that convergence to a uniform action is extremely rapid, typically occurring within five or six periods with probability close to 1. What happens in those first few periods is important for the determination of the asymptotic state. Network architecture: Systematic differences can be identified in the behavior of different networks. For example, in three-person complete networks (where each agent observes all the others), learning stops almost immediately and the probability of an incorrect action in the long run is high. In three-person incomplete networks, learning continues for a longer time and the probability of choosing an incorrect action in the long run is lower. The rest of the paper is organized as follows. In Section 2 we define the model and the equilibrium concept more precisely. In Section 3 we use the case of two-person networks to illustrate the working of the general model and some special features of complete networks. In Section 4 we derive the asymptotic properties of the general model. In Section 5 we study a selection of three-person graphs. Here we see the impact of lack of common knowledge on the dynamics of social learning and the efficiency of aggregation. We also compare the dynamic and asymptotic properties of different networks. The results are discussed in Section 6. Proofs are gathered in Section 7. 2. THE MODEL The social learning literature ignores the complications of strategic behavior in order to focus on pure Bayesian learning. Non-strategic behavior 4
is simpler to analyze and it also seems more appropriate for a model of social behavior. However, special assumptions are needed to rationalized non-strategic behavior. In the Sslm, for example, an agent is assumed to make a once-in-a-lifetime decision. Because his payoff is independent of other agents'actions, it is rational for him to behave myopically and ig nore the affect of his action on the agents who follow him. In the sNm. an agent's payoff is independent of other agents'actions but, unlike the SSLM agents make repeated decisions. In order to eliminate strategic behavior, we assume that the economy comprises a large number of individually in- significant agents and that agents only observe the distribution of actions t each date. Since a single agent cannot affect the distribution of actions he cannot influence the future play of the game. This allows us to "strategic"considerations and focus on the pure Bayesian-learning of the model The agents Formally, we assume there is a finite set of locations indexed by i=1,.,n At each location, there is a non-atomic continuum of identical agents. In he sequel, the continuum of agents at location i is replaced by a single representative agent i who maximizes his short-run payoff in each period Uncertainty is represented by a probability measure space( Q, F,P) where s is a compact metric space, F is a a-field, and P a probability measure. Time is represented by a countable set of dates indexed by t 1.2 Let ACR be a finite set of actions and let U:AxQ-R be the common payoff function, where U(a, )is a bounded, measurable function for every action a. Each(representative)agent i receives a private signal Ji(w) at date 1, where ;: Q2-+R is a random variable The network A social network is represented by a family of sets N;: i=l,.,n), where N≤{1,…,-1,i+1,…,n} For each agent i, Ni denotes the set of agents j# i who can be observed by agent i. We can think of Ni as representing is"neighborhood". The sets IN: 1=1, , n define a directed graph with nodes N=(1,.,ny and edges E= U(i,): J N. The social network determines the information How in the economy. agent i can observe the action of agent j if and only if j E Ni. Agents have perfect recall so their information set at each date includes the actions they have observed at every previous date For any nodes i and j, a path from i to j is a finite sequence il, . iK such that i1=i, iK =3 and ik+1 E Nik for k= 1,.K-1. A node connected to j if there is a path from i to j. The network INil is connected if every pair of nodes i and j is connected. Connectedness is essential for uniformity of behavior. but not for other results
is simpler to analyze and it also seems more appropriate for a model of social behavior. However, special assumptions are needed to rationalized non-strategic behavior. In the SSLM, for example, an agent is assumed to make a once-in-a-lifetime decision. Because his payoff is independent of other agents’ actions, it is rational for him to behave myopically and ignore the affect of his action on the agents who follow him. In the SNM, an agent’s payoff is independent of other agents’ actions but, unlike the SSLM, agents make repeated decisions. In order to eliminate strategic behavior, we assume that the economy comprises a large number of individually insignificant agents and that agents only observe the distribution of actions at each date. Since a single agent cannot affect the distribution of actions, he cannot influence the future play of the game. This allows us to ignore “strategic” considerations and focus on the pure Bayesian-learning aspect of the model. The agents Formally, we assume there is a finite set of locations indexed by i = 1, ..., n. At each location, there is a non-atomic continuum of identical agents. In the sequel, the continuum of agents at location i is replaced by a single representative agent i who maximizes his short-run payoff in each period. Uncertainty is represented by a probability measure space (Ω, F, P), where Ω is a compact metric space, F is a σ-field, and P a probability measure. Time is represented by a countable set of dates indexed by t = 1, 2, .... Let A ⊂ R be a finite set of actions and let U : A × Ω → R be the common payoff function, where U(a, ·) is a bounded, measurable function for every action a. Each (representative) agent i receives a private signal σi(ω) at date 1, where σi : Ω → R is a random variable. The network A social network is represented by a family of sets {Ni : i = 1, ..., n}, where Ni ⊆ {1, ..., i − 1, i + 1, ..., n}. For each agent i, Ni denotes the set of agents j 6= i who can be observed by agent i. We can think of Ni as representing i’s “neighborhood”. The sets {Ni :1=1, ..., n} define a directed graph with nodes N = {1, ..., n} and edges E = ∪n i=1{(i, j) : j ∈ Ni}. The social network determines the information flow in the economy. Agent i can observe the action of agent j if and only if j ∈ Ni. Agents have perfect recall so their information set at each date includes the actions they have observed at every previous date. For any nodes i and j, a path from i to j is a finite sequence i1, ..., iK such that i1 = i, iK = j and ik+1 ∈ Nik for k = 1, ..., K − 1. A node i is connected to j if there is a path from i to j. The network {Ni} is connected if every pair of nodes i and j is connected. Connectedness is essential for uniformity of behavior, but not for other results. 5