Google Research

History-Independent Distributed Multi-agent Learning

Algorithmic Game Theory: 9th International Symposium, SAGT 2016, Proceedings, Springer, pp. 77-89


How should we evaluate a rumor? We address this question in a setting where multiple agents seek an estimate of the probability, b, of some future binary event. A common uniform prior on b is assumed. A rumor about b meanders through the network, evolving over time. The rumor evolves, not because of ill will or noise, but because agents incorporate private signals about b before passing on the (modified) rumor. The loss to an agent is the (realized) square error of her opinion. Our setting introduces strategic behavior based on evidence regarding an exogenous event to current models of rumor/influence propagation in social networks. We study a simple Exponential Moving Average (EMA) for combining experience evidence and trusted advice (rumor), quantifying its resulting performance and comparing it to the optimal achievable using Bayes posterior having access to the agents private signals. We study the quality of p_T, the prediction of the last agent along a chain of T rumor-mongering agents. The prediction p_T can be viewed as an aggregate estimator of b that depends on the private signals of T agents.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work