Diverse Randomized Agents Vote to Win Tuomas Sandholm CMU
We investigate the power of voting among diverse, randomized software agents. With teams of computer Go agents in mind, we develop a novel theoretical model of two-stage noisy voting that builds on recent work in machine learning. This model allows us to reason about a collection of agents with different biases (determined by the first-stage noise models), which, furthermore, apply randomized algorithms to evaluate alternatives and produce votes (captured by the secondstage noise models). We analytically demonstrate that a uniform team, consisting of multiple instances of any single agent, must make a significant number of mistakes, whereas a diverse team converges to perfection as the number of agents grows. Our experiments, which pit teams of computer Go agents against strong agents, provide evidence for the effectiveness of voting when agents are diverse.
The paper provides a framework for analyzing the quality of a vote among a team of agents (compared to some underlying true ranking) where the teams are generated differently: by multiple instantiations of the same agent ("Uniform"), and by a single instantiation of several different types of agents ("Diverse"). Under some conditions, the authors show that as the number of agents grow the Diverse team converges in probability almost surely to choosing the correct choice, where the Uniform team always has a non-zero probability of making a mistake. The paper is quite clear and the technical quality is high. The results are significant and relevant. The main idea here is that voting among a diverse team leads to robust choices, whereas a population of fixed players does not have enough variance and will play "too predictably", but the authors provide a nice theoretical foundation to quantify these notions and show that even diversity obtained from a single (widely-used) Go program with different parameters can lead to significant performance boosts in 9x9 Go (against the same copies of the optimally-tuned parameter version of the Go program) when using an appropriate voting scheme. The authors also show how their assumptions and voting rules relate to other rules used in the literature. I have a some problems with the paper. The first is that there seems to be a disconnect between the experiments and the foundations that came before it. The experimental section is specific, focusing on the single application to Go, while the theoretical framework is quite general. I was expecting to see experiments comparing different noise models, something that validates the assumptions listed in section 3, or some stronger link between the first half of the paper and second. As far as I can tell there is no mention of whether the Go application even satisfies the assumptions 1-4, so does Theorem 2 even hold in this experiment? This is also true for the discussion section, which seems to again focus on the application to games while the first part is more general.Also, as this is follow-up work based heavily on past work ([18,19]) the authors should do a better job of highlighting what is new in this paper. The noise model approach certainly seems appropriate for the computer Go setting where there indeed is some underlying true ranking of alternatives, but this might not be true in other more general social choice settings such as elections.. can anything be said on whether this approach could be applied when the existence of a true ranking is unknown?