Unleashing the Power of Multi-Agent Voting Teams

Leandro Soriano MarcolinoIJCAI 2015 · OpenReview

Abstract

Teams of voting agents have great potential in finding optimal solutions. However, there are fundamental challenges to effectively use such teams: (i) selecting agents; (ii) aggregating opinions; (iii) assessing performance. I address all these challenges, with theoretical and experimental contributions.

Introduction

In many fields—machine learning, crowdsourcing, and even board games—we use "voting teams" of autonomous agents to find optimal solutions. However, three major hurdles remain: agent selection, opinion aggregation, and real-time performance assessment. Traditionally, social choice theory suggested that uniform teams of the "best" agent were ideal. This research challenges that conventional wisdom, demonstrating that diversity often beats individual strength, especially in complex problems with large action spaces.

The Diversity Paradox in Large Action Spaces

A core finding of this work is the "Diversity Paradox." While a single "best" agent might be stronger than any other individual, a team of diverse agents is less likely to make the same mistakes. In large action spaces, if two diverse agents agree on an action, it is highly likely to be the correct one because the odds of them accidentally picking the same "wrong" action out of thousands of possibilities are incredibly low.

This effect is clearly visible in the domain of Computer Go. As the board size (and thus the action space) increases, the performance gap between diverse teams and uniform teams of the strongest agent widens significantly.

Winning rate of diverse vs. uniform teams as board size increases.

Methods for Optimization and Aggregation

The research introduces several theoretical models and techniques to optimize team performance:

  • Spreading Tail (ST) Agents: A theoretical model where agents have an increasingly large number of actions they might choose with non-zero probability as the total number of possible actions grows. This helps model how diverse agents behave in "large action spaces."
  • Novel Ranking Extraction: Instead of taking a single "best" move from an agent, the author samples each agent multiple times to see the frequency of different actions. This frequency-based approach creates a more robust ranking than standard methods.
  • Multi-Optima Search: A framework for design problems where the goal isn't just one "best" answer, but finding as many high-quality solutions as possible to give a human designer options.

Surprisingly, simple plurality voting often outperformed complex ranked voting rules (like Borda or Copeland) in noisy environments like Go and HIV prevention. This is because agents designed to output one choice often provide "noisy" or unreliable lower-level rankings.

Predicting Performance via Agreement Patterns

Can we predict, in real-time, whether a team is likely to succeed or fail? The author developed a domain-independent performance prediction model that uses "agreement patterns"—how often specific subsets of agents agree on a choice—to predict the final reward of a team using linear models.

Accuracy of performance prediction over the course of a game.

As shown in the figure above, the system can learn to predict the eventual outcome with increasing accuracy as the game progresses, reaching approximately 73% accuracy toward the end of a match. This demonstrates that you don't need to know the "ground truth" of a problem to predict if a team is doing well; the patterns of agreement themselves serve as a powerful signal.

Domain Applications and Results

The research evaluates these methods across three distinct and challenging domains:

  • Computer Go: Using well-known engines like Fuego, Gnugo, Pachi, and Mogo, diverse teams outperformed uniform ones on large boards.
  • HIV Prevention: In a social network domain (PSINET) focused on selecting influential nodes to spread health information, the "PSINET-W" (weighted plurality) approach achieved the highest influence spread.
  • Architectural Design: In tasks like finding optimal building layouts (Base, Office, and Towers), agent teams found a significantly higher percentage of optimal solutions than any individual agent acting alone.

Conclusion and Future Work

This work establishes that diversity is a critical component of effective multi-agent teams in complex domains. While plurality voting has proven robust, future work aims to explore mixed teams of humans and artificial agents, develop more sophisticated aggregation methodologies to handle noise, and deepen the theoretical understanding of why certain voting rules fail in specific multi-agent contexts.

Summary updated

Abstract

Teams of voting agents have great potential in finding optimal solutions. However, there are fundamental challenges to effectively use such teams: (i) selecting agents; (ii) aggregating opinions; (iii) assessing performance. I address all these challenges, with theoretical and experimental contributions.
BibTeX
@inproceedings{marcolino2015unleashing,
  author = {Leandro Soriano Marcolino},
  title = {{Unleashing the Power of Multi-Agent Voting Teams}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=Bk-5wrGdbB},
}
Figure