More Like this

1. Maximizing Truth Learning in a Social Network is NP-Hard

   Uradnik, Filip; Wang, Amanda; Gao, Jie (May 2025, Proceedings of the 24th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS))

   Sequential learning models situations where agents predict a ground truth in sequence, by using their private, noisy measurements, and the predictions of agents who came earlier in the sequence. We study sequential learning in a social network, where agents only see the actions of the previous agents in their own neighborhood. The fraction of agents who predict the ground truth correctly depends heavily on both the network topology and the ordering in which the predictions are made. A natural question is to find an ordering, with a given network, to maximize the (expected) number of agents who predict the ground truth correctly. In this paper, we show that it is in fact NP-hard to answer this question for a general network, with both the Bayesian learning model and a simple majority rule model. Finally, we show that even approximating the answer is hard. 

   more » « less
2. Learning from Neighbours about a Changing State

   https://doi.org/10.1093/restud/rdac077  

   Dasaratha, Krishna; Golub, Benjamin; Hak, Nir (November 2022, Review of Economic Studies)

   Abstract Agents learn about a changing state using private signals and their neighbours’ past estimates of the state. We present a model in which Bayesian agents in equilibrium use neighbours’ estimates simply by taking weighted sums with time-invariant weights. The dynamics thus parallel those of the tractable DeGroot model of learning in networks, but arise as an equilibrium outcome rather than a behavioural assumption. We examine whether information aggregation is nearly optimal as neighbourhoods grow large. A key condition for this is signal diversity: each individual’s neighbours have private signals that not only contain independent information, but also have sufficiently different distributions. Without signal diversity—e.g. if private signals are i.i.d.—learning is suboptimal in all networks and highly inefficient in some. Turning to social influence, we find it is much more sensitive to one’s signal quality than to one’s number of neighbours, in contrast to standard models with exogenous updating rules. 

   more » « less
3. Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences

   Schoenebeck, Grant; Tao, Biaoshuai (January 2021, Advances in Neural Information Processing Systems 34 pre-proceedings (NeurIPS 2021))

   We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. As a special case, our model captures the common scenario where voters can be categorized into three types: those who always prefer one alternative, those who always prefer the other, and those contingent voters whose preferences depends on the state. In this setting, even if every voter is a contingent voter, agents voting according to their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased.We present a mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority. In particular, voters truthfully reporting their signals forms a strong Bayes Nash equilibrium (where no coalition of voters can deviate and receive a better outcome). 

   more » « less
4. The Wisdom of Strategic Voting

   https://doi.org/10.1145/3580507.3597681  

   Han, Qishen; Schoenebeck, Grant; Tao, Biaoshuai; Xia, Lirong (July 2023, ACM)

   We study the voting game where agents' preferences are endogenously decided by the information they receive, and they can collaborate in a group. We show that strategic voting behaviors have a positive impact on leading to the "correct" decision, outperforming the common non-strategic behavior of informative voting and sincere voting. Our results give merit to strategic voting for making good decisions. To this end, we investigate a natural model, where voters' preferences between two alternatives depend on a discrete state variable that is not directly observable. Each voter receives a private signal that is correlated with the state variable. We reveal a surprising equilibrium between a strategy profile being a strong equilibrium and leading to the decision favored by the majority of agents conditioned on them knowing the ground truth (referred to as the informed majority decision): as the size of the vote goes to infinity, every ε-strong Bayes Nash Equilibrium with ε converging to 0 formed by strategic agents leads to the informed majority decision with probability converging to 1. On the other hand, we show that informative voting leads to the informed majority decision only under unbiased instances, and sincere voting leads to the informed majority decision only when it also forms an equilibrium. 

   more » « less
5. Misinterpreting Others and the Fragility of Social Learning

   https://doi.org/10.3982/ECTA16981  

   Frick, Mira; Iijima, Ryota; Ishii, Yuhta (January 2020, Econometrica)

   null (Ed.)

   We exhibit a natural environment, social learning among heterogeneous agents, where even slight misperceptions can have a large negative impact on long‐run learning outcomes. We consider a population of agents who obtain information about the state of the world both from initial private signals and by observing a random sample of other agents' actions over time, where agents' actions depend not only on their beliefs about the state but also on their idiosyncratic types (e.g., tastes or risk attitudes). When agents are correct about the type distribution in the population, they learn the true state in the long run. By contrast, we show, first, that even arbitrarily small amounts of misperception about the type distribution can generate extreme breakdowns of information aggregation, where in the long run all agents incorrectly assign probability 1 to some fixed state of the world, regardless of the true underlying state. Second, any misperception of the type distribution leads long‐run beliefs and behavior to vary only coarsely with the state, and we provide systematic predictions for how the nature of misperception shapes these coarse long‐run outcomes. Third, we show that how fragile information aggregation is against misperception depends on the richness of agents' payoff‐relevant uncertainty; a design implication is that information aggregation can be improved by simplifying agents' learning environment. The key feature behind our findings is that agents' belief‐updating becomes “decoupled” from the true state over time. We point to other environments where this feature is present and leads to similar fragility results. 

   more » « less