Multi-Agent Team Formation: Diversity Beats Strength?

1 Introduction

Team formation is essential when dealing with a multi-agent system. Given limited resources, we must select a strong team to deal with a complex problem. Many works model

tain task with the maximum expected value, given a model of the capabilities of each agent [Nair and Tambe, 2005; Guttmann, 2008]. Other works go beyond a simple sum of skills, for example by considering synergetic effects in a team of agents [Liemhetcharat and Veloso, 2012] or studying how to automatically configure a network of agents [Gaston and desJardins, 2005].

After forming a team, their members must work together. There are many different ways for a team to coordinate. One common and simple way is to use voting. By voting, a team of agents can get closer to finding the best possible decision in a given situation [List and Goodin, 2001]. Only one voting iteration might not be enough, sometimes the agents must vote continuously in many different scenarios. Consider, for example, agents that are cooperating in a board game [Obata et al., 2011], deciding together stock purchases across different economic scenarios, or even picking items to recommend to a large number of users [Burke, 2002]. This situation imposes a conflict for team formation: should we focus on the diversity of the team or on the strength of each individual member? Previous works do not address this issue. Diversity is proposed as an important concept for team formation in the field of Economics and Social Science [Hong and Page, 2004; LiCalzi and Surucu, 2012]. However, [Hong and Page, 2004; LiCalzi and Surucu, 2012] assume a model where each agent brings more information, and the system converges to one of the best options known by the group. When a team votes to decide its final opinion, their model and theorems do not hold anymore. In the current literature on voting it is assumed a model where agents have a fixed probability to take the best action [Condorcet, 1785; List and Goodin, 2001; Young, 1995; Conitzer and Sandholm, 2005; Xia, 2011], and under that model it is not possible to show any advantage in having a diverse team of agents. Our experiments show, however, that a diverse team can outperform a uniform team of stronger agents. It is necessary to develop, therefore, a new model to analyze a team of voting agents.

In this work, we present a new model of diversity and strength for a team of voting agents. The fundamental novelty of our model is to consider a setting with multiple world states, and each agent having different performance levels across world states. Under this model, we can show that a team of diverse agents can perform better than a uniform team composed by strong agents. We present the necessary conditions for a diverse team to play better than a uniform team, and study optimal voting rules for a diverse team.

We present synthetic experiments with a large number of teams that demonstrate that both diversity and strength are important to the performance of a team. We also show results in one of the main challenges for Artificial Intelligence: Computer Go. Go is an iterative game, and the possible board states can represent a great variety of different situations, in such a way that the relative strength of different Go playing software changes according to the board state. Therefore, we can use our model to study a team of agents voting to play Computer Go. By using a diverse team we were able to increase the winning rate against Fuego (one of the strongest Go software) by 17%, and we could play 7% better than a team of copies of Fuego. Moreover, we could play 7% to 9% better than one of the versions of parallelized Fuego. We could also improve the performance of the diverse team by

12% using one of our proposed voting rules. Therefore, we effectively show that a team of diverse agents can have competitive strength, and even play better, than a uniform team composed by stronger agents. Our new model provides a theoretical explanation for our results.

2 RelatedWork

This work is related mainly to the study of team formation, diversity and voting. We will first introduce general works on team formation, then we will talk about diversity, and finally we will discuss voting.

Team formation is the problem of selecting the best possible team to accomplish a certain goal, given limited resources. In the traditional model, certain skills are necessary to accomplish a task, and we must select a team that has all the necessary skills with the maximum expected value [Nair and Tambe, 2005; Guttmann, 2008]. More recent work go beyond a simple sum of skills and also models the synergy of a group [Liemhetcharat and Veloso, 2012], how to lead a group to the optimal joint action with a new ad-hoc agent [Agmon and Stone, 2012] or how to automatically configure a network of agents [Gaston and desJardins, 2005]. In [Matthews et al., 2012], a team formation procedure is presented for a class of online soccer prediction games, and the system is able to play successfully against a large number of human players. However, the existing models do not cover the situation where we must select a team to vote together at each step of a complex problem. In this work, we present a new perspective to team formation, and we also introduce a new problem: in the pursuit of the best possible team of voting agents should we focus on the diversity of the team or on the strength of each individual member?

Hong and Page presented a contribution to team formation in the Social Science literature by showing the importance of diversity [Hong and Page, 2004]. They proposed a model for agents, and proved that a team of diverse agents can perform better than a team of high-ability agents. In their model, each agent has a set of local minima that they reach while trying to maximize an objective function. The agents can improve the solution from the local minima of their team members, therefore the search of a team stops only in the intersection of the local minima of all agents. By using a large number of diverse agents the system is able to converge to the optimal solution. Many papers followed their work [Luan et al., 2012; Lakhani et al., 2007; Krause et al., 2011], showing the importance of diversity in different settings. Their model, however, does not cover situations where agents are unable to improve the solution from their team members' local minima. This can happen, for example, when we use existing software, that were not architectured to collaborate in this way or when there are time constraints. Therefore, there are many situations where the agents have to collaborate in other ways, such as voting. If a team of agents votes, the system will not necessarily converge to an option in the intersection of their local minima. However, as we will show, it is still possible for a diverse team to play better than a uniform strong team.

A recent model to analyze diversity was proposed in [LiCalzi and Surucu, 2012]. It is an equivalent model to Page's and do not overcome the limitations previously described. In [Braouezec, 2010], the authors show the benefits of diverse agents voting to estimate the optimum of a single peaked function. In our work we are dealing with a harder problem, as the function to be optimized changes at every iteration. Another work that uses voting to study diversity is [West and Dellana, 2009], but they assumed that Page's model would work in a voting context, and do not propose a new model.

Concerning voting, the field has two possible views: voting for aggregating different preferences, and voting to estimate the best possible decision. Our work is related to the second view. The classical work in this line is the Condorcet's Jury Theorem [Condorcet, 1785]. According to the theorem, when facing a binary decision, as long as the average of the probability of each individual being correct is higher than 12 , a group of independent individuals doing majority voting will have a higher probability of being correct than the individuals alone. This theorem is extended to the k options case in [List and Goodin, 2001], where it is shown that if each of the individuals have a probability of choosing the best answer higher than choosing any other answer, the group performing majority voting will be stronger than the individuals alone. These theorems, however, do not present any benefits in having diverse agents. Researchers in Artificial Intelligence contributed to this view of voting by using a maximum likelihood approach to find the optimal voting rule. The idea is that given the votes, we can find which option has the highest probability of being the best, if we have a model of the probability distribution of the agents [Young, 1995; Conitzer and Sandholm, 2005; Xia, 2011]. However, they still do not address the issue of diversity and team formation in the context of voting, as they assume that all agents follow the same probability distribution. As all agents are essentially the same, team formation is not yet an issue in their work.

3 Methodology

Let Φ be a set of agents φi voting to decide an action a in the set of possible actions A and Ω be a set of world states ωj. We assume that we can rank the actions from best to worst and Uj is the vector of expected utilities of the actions in world state ωj, ordered by rank. The agents do not know the ranking of the actions, and will vote according to some decision procedure, characterized by a probability distribution function (pdf) over action ranks. Hence, each agent φi has a pdf Vi,j for deciding which action to vote for in state ωj. Agents that have the same Vi,j in all world states will be referred as copies of the same agent.

Let αj be the likelihood of world state ωj. If the world states are equally frequent, we can use αj = 1/|Ω|. We define strength as the weighted average of the expected utility of an agent or a team. It is given by the following dot product: s = ∑ωj∈Ω αjVj ·Uj, where Vj is the pdf of the agent/team in world state ωj . Vj can be calculated given a team of agents and a voting rule. A voting rule is a function that given the (single) votes of a team of agents, outputs an action.

We define the team formation problem as selecting from the space of all possible agents Ψ a set of n agents Φ that has the maximum strength in the set of world states Ω. An application does not necessarily know Vi,j for all agents and for all world states. In this work, we will focus on showing that the na¨ıve solution of forming a team by selecting the strongest agents (or copies of the best agent) is not necessarily the optimal solution. Therefore, we are introducing a new problem to the study of team formation.

We define diversity as how different are the probability distributions of agents in Φ in the set of world states Ω: d = 1 |Φ|2 ∑ωj∈Ω ∑φi∈Φ ∑φk∈Φ αjH(Vi,j,Vk,j), where H is a distance measure between two pdfs. In this paper, we used the Hellinger Distance [Hellinger, 1909], given by:

At each iteration, each agent will examine the current world state and submit its (single) opinion about which one should be the next action. The opinions are then combined using plurality voting, that picks as a winner the option that received the most votes. We consider in this paper three different voting rules: simple - break ties randomly, static - break ties in favor of the strongest agent overall, optimal - break ties in favor of the strongest agent of each world state. We consider the static voting rule because in some applications we might have a clear idea of which is the strongest agent overall, but the information of which is the strongest agent for a given world state might not be available. We will encounter this situation in the Computer Go domain, as will be clear in Section 4.2. This voting procedure will repeat at every iteration, until the end, when the system can obtain a reward.

3.1 Diversity Beats Strength

We present examples to demonstrate that a diverse team can play better than a uniform team. First, let's consider the simplest case, when all agents are deterministic. The team made of copies of the strongest agent will play as well as the strongest agent, no matter how many members we add in the team. However, a team of diverse agents can overcome the strongest agent, and even reach perfect play, as we increase the number of agents. Consider, for example, the team in Table 1. This diverse team of 5 agents will reach perfect play under simple voting, while copies of the best agent (Agent 1 or Agent 4) will be able to play well only in 3 out of 4 world states, no matter how many agents we use in the team.

We can easily change the example to non-deterministic agents, by decreasing slightly the probability of them playing their deterministic action. A detailed description of the agents used in this example is available in the Appendix 1 .

1 In http://teamcore.usc.edu/people/sorianom/ijcai13a.pdf

The resulting strength of the teams is very similar to the deterministic case. Assuming all world states are equally likely, the strength of the diverse team is 0.9907, while copies of the best agent have strength 0.7499. Therefore, it is possible for a team of weak diverse agents to overcome a uniform team of stronger agents, when in certain states the individual agents are stronger than the overall strongest agent.

Even if we make the number of agents go to infinity, copies of the best agent will still be unable to perform the best action in one world state, and will play worse than the diverse team with only five agents. This situation is not considered in the Condorcet's Jury Theorem, neither in the classical nor in the extended version, because they assume independent agents with a fixed pdf. Therefore, in the previous models, we would not be able to show the importance of diversity.

Necessary Conditions

We present a formal proof of the conditions necessary for a diverse team to play better than copies of the best agent, under the simple voting rule. If the conditions of the theorem are not met, we can simply use copies of the best agent as the optimal team. To simplify the presentation of the proof, we will consider a utility function with a value of 1 for the optimal action and 0 for the other actions. That is, we will consider the optimal team in a fixed world state as the team that has the highest probability of performing the optimal action. Let ψbest be the strongest agent in Ψ, and abest be the best action in a given world state.

Theorem 1. For a diverse team to be the optimal team under the simple voting rule it is necessary that at least one agent in Ψ has a higher probability of taking the best action than ψbest or a lower probability of taking a suboptimal action than ψbest in at least one world state.

Proof We develop the proof by showing that copies of the best agent of a given world state will be the optimal team in that world state. Therefore, it is necessary that the agents in the diverse team play better than the best agent overall in at least one world state. Let ψbest,j be the strongest agent in world state ωj. Let's define the pdf of this agent as < p1, ..., pk >, where p1 is the probability of taking the best action. We will show that a team of n copies of ψbest,j doing simple voting will have a higher probability of taking the best action than a team of n agents composed of x copies of ψbest,j and m agents ψi doing simple voting, where the probabilities of each ψi are given by < p1 - ϵi, p2 + γi2, ..., pk + γik >, γil ≥ 0 ∀l ∈ (2, k) and ∑kl=2 γil = ϵi.

Given a team of agents, let them all vote. We will start with a team of x copies of agent ψbest,j . We will perform m iterations, and at each one we will add either another agent ψbest,j or agent ψi, where i is the current iteration. Let vi-1 be the current vote result. The result of vi-1 is either: (i) victory for abest, (ii) tie between abest and other options, (iii) defeat for abest.

(i) If vi-1 is a victory for abest, the new agent can change the result only when it votes for another option. Suppose al is an option that upon receiving one more vote will change a victory for abest into a tie between abest and al. Agent ψbest,j will vote for option al with probability pl, while agent ψi will vote for option al with probability pl +γil. Therefore, if vi-1

is such that one vote can change a victory for abest into a tie between abest and other options, agent ψi will have a higher probability of changing a victory for abest into a tie between abest and other options.

(ii) If vi-1 is a tie between abest and other options, ψbest,j will break the tie in favor of abest with probability p1 while ψi with probability p1 - ϵi. Therefore, agent ψbest,j will have a higher probability of breaking the tie in favor of abest. Moreover, if al is an option that is currently tied with abest, agent ψbest,j will vote for al with probability pl, while agent ψi with probability pl + γil. Therefore, agent ψi will have a higher probability of changing a tie between abest and other options into a defeat for abest.

(iii) If vi-1 is a defeat for abest, ψbest,j will vote for abest with probability p1 while ψi will vote for abest with probability p1-ϵi. Therefore, if vi-1 is such that one vote can change a defeat for abest into a tie between abest and other options, agent ψbest,j will have a higher probability of changing a defeat for abest into a tie between abest and other options.

In all three cases, agent ψbest,j leads to a higher increase in the probability of picking abest than agent ψi. Therefore, up to any iteration i, copies of ψbest,j will have a higher probability of playing the best action than a diverse team. Hence, if ψbest,j = ψbest∀j, then copies of the best agent ψbest will be the best team in all world states, and therefore it will be the optimal team. Therefore, for a diverse team to perform better, at least one agent must have either a higher probability of taking the best action or a lower probability of taking a suboptimal action than ψbest in at least one world state. ■

This theorem, however, only gives the necessary conditions for a diverse team to be stronger than a non-diverse team. The sufficient conditions will depend on which specific game the agents are playing. Basically, given the pdf of the agents for a set of world states, we can calculate the pdf of both the diverse team, and the team made of copies of the best agent. If the diverse team has a higher probability of taking the best action in a subset of the world states that is enough for it to play better, considering that it will have a lower probability of taking the best action in the complementary subset, then the diverse team will play better than copies of the best agent.

Optimal Voting Rules

Given the result of a voting iteration, and the pdf of all agents in a world state, we can calculate which action has the highest probability of being the best. Formally, let < pi1 , ..., pik > be the pdf of agent φi in world state ωj, where pil is the probability of playing the action with rank l. The optimal voting rule is the one that given a voting pattern, selects the action ax that has the highest probability of being the best. Let Y be the set of all other possible rank combinations for all other actions. We write an element of Y as a sequence y1...yk′-1, where yl is a position in the ranking, and k′ is the number of actions in the given voting pattern. We also define Φal as the set of agents in Φ that voted for an action al, and Aγ as the set of all actions in the given voting pattern. Assuming a uniform prior probability for the ranking of all actions, we can calculate the probability of ax being the best action by:

The derivation of the expression is available in the Appendix. We can extend this definition to picking the option with maximum expected utility by calculating the probability of each possible rank (instead of only the best one) and multiplying the resulting probability vector by a utility vector to obtain the expected utility of an option ax.

However, it is possible to use a simpler voting rule. In our next theorem, we show that given some conditions, the optimal voting rule for a diverse team is to consider majority voting, but break ties in favor of the strongest agent that participates in the tie. Basically, we have to assume that all agents are strong enough to contribute to the team, so no agent should be ignored. If there are harmful agents in the team, we can try to remove them until the conditions of the theorem are satisfied. Again, we consider a utility function with a value of 1 for the optimal action and 0 for the other actions. Given a team Φ with size n, our conditions are:

Assumption 1 Weak agents do not harm

For any subset of Φ with an even number of agents n′ , and for a fixed world state ωj, let φ′best,j be the best agent of the subset. We divide the agents in 2 sets: Weak containing the n′ /2-1 agents that have the lowest probability of taking the best action and the highest probability of taking a suboptimal action, and Strong containing the n′ /2 agents that have the highest probability of playing the best action and the lowest probability of taking a suboptimal action (except for the best agent φ′best,j , that is in neither one of the sets). We assume that when all agents in Weak and φ′best,j vote together for an option ax, and all agents in Strong vote together for another option ay, the probability of ax being the best action is higher than the probability of ay being the best action.

Assumption 2 Strong agents are not overly strong

Given a fixed world state ωj, we assume that if m1 agents voted for an action ax and m2 agents voted for an action ay, the probability of ax being the best action is higher than ay being the best action, if m1 > m2. If there is a situation where the opinion of a set of agents always dominates the opinion of another set, we can try to remove the dominated agents until the assumption holds true.

Theorem 2. The optimal voting rule for a team is to consider the vote of all agents, but break ties in favor of the strongest agent if the above assumptions are satisfied.

Proof Sketch Our detailed proof is available in the Appendix. We present here a proof sketch. By Assumption 2 we know that we are looking for a tie-breaking rule, as the action chosen by the majority of the votes should always be taken. By Assumption 1 we know that in the worst possible case, we should still break ties in favor of the strongest agent. If in the worst case, the group with the strongest agent still has a higher probability of selecting the best action than the group without the strongest agent, for any other case the group with the strongest agent will still have a higher probability. ■

As we are going to see in the next section, an application may not have the knowledge of the pdf of the agents in individual world states. Therefore, we also study an approximation of the optimal voting rule, that break ties in favor of the strongest agent overall, instead of breaking ties in favor of the strongest agent in a given world state. In the next section we will see that both the optimal voting rule and our approximation improves the performance of a diverse team.

4 Results

4.1 Synthetic

We perform experiments using the quantal response (QR) model for the agents [McKelvey and Palfrey, 1995]. The quantal response model is a pdf from behavioral game theory to approximate how human beings (or non-rational players) behave while playing a game. It states that the probability of playing the best action is the highest, and it decays exponentially as the utility of the action gets worse. We use the QR model in our experiment, because it is a convenient way to represent non-rational agents with different strengths playing a game with a great number of options.

The pdf depends on a parameter, λ, that defines how rational (i.e., strong) is the agent. As λ gets higher, the agent provides a closer approximation to a perfect player. We define a λij for each agent i and world state j.

We generated 1200 random teams of 4 agents, playing in 10 world states, and with 82 possible actions. We define each λij as a random number in the interval (0, 7), according to a uniform distribution. For each team, we can calculate the diversity and the average strength of the agents, according to the equations defined earlier. In Figure 1, we can see the performance of each team, as a function of diversity and the strength of its members. The strength of a team can be calculated after we generate the pdf of the team, by calculating the probability of all possible situations where the system would pick a particular ranking position. We assume that all world states are equally likely, hence the strength of a team is the average over all world states. We used a utility vector that gives a value close to 1 to the best action, and a low value to the other actions.

We performed a multiple linear regression for each voting rule. The following models were found: simple: z = -0.09+1.48s+0.45d; static: z = -0.03+1.36s+0.55d; optimal: z = 0.09 + 0.92s + 1.29d. The variable s is the average strength of the team members, d is the diversity of the team, and z is the strength of the team. The coefficient of multiple determination (R2 ) of the models are 0.96, 0.81, 0.88, respectively.

As can be seen, both diversity and strength had a positive weight. This shows that groups with more diversity are stronger, given a fixed strength for their members. It is interesting to note that the impact of diversity increases as we change the voting rule from simple to static, and from static to optimal. The mean strength of all teams are 0.56(±0.08), 0.61(±0.08), 0.74(±0.06), respectively. We can note that, as expected, simple had the lowest strength, followed by static, and optimal had the highest strength. The optimal voting rule is 30% stronger than simple voting in average.

4.2 Experiments in Computer Go

We perform experiments with four Go software: Fuego 1.1 [Enzenberger et al., 2010], GnuGo 3.8, Pachi 9.01 [Baudiˇs and Gailly, 2011], MoGo 3 [Gelly et al., 2006], and two (weaker) variants of Fuego (FuegoΔ and FuegoΘ), in a total of 6 different agents. These are all publicly available Go software. Fuego is known to be the strongest Go software among all of them. Fuego, Pachi and MoGo follow an UCT Monte Carlo Go algorithm [Gelly et al., 2006]. The description of FuegoΔ and FuegoΘ is available at the Appendix. All results presented are obtained by playing 1000 9x9 Go games, in a HP dl165 with dual dodeca core, 2.33GHz processors and 48GB of RAM. Our system will play as white, against the original Fuego playing as black with opening database. Therefore, we will compare the winning rate of different agents and teams when playing against the same opponent. When we say that a result is significantly better than another, we use a t-test with 1% significance level (α = 0.01).

Before introducing our results, we will use Theorem 1 to justify that it is worth it to explore a diverse team. If Fuego, the strongest agent, is always stronger in all board positions, then we can just use copies of Fuego as the optimal team. Therefore, we will first test if all agents are able to play better than Fuego in some board positions. In order to analyze the probability of an agent playing the best move in a certain board position, we need an estimate of the best move. Given a board position, we will ask Fuego to perform a movement, but we will give Fuego a time limit 50x higher than the default one. Therefore, Fuego is approximating how a perfect (or at least much stronger) player would play. We selected 100 board states, and we played all agents 50 times for each board state. Based on our estimate, we can calculate the probability of each agent playing the best move (Pbest) for each board state. In Table 2, we can see in how many board states the agents have a higher Pbest than Fuego (in its default time limit). As can be observed, all agents are able to play better than Fuego in some board positions, therefore it is possible for a diverse team to play better than copies of the best agent. As the number of board states where an agent plays better is not small, we can expect that a diverse team should be able to overcome the uniform team.

According to Theorem 2, if we assume that the weak agents (like GnuGo) are not weak enough to harm the system, and the strong agents (like Fuego and its variants) are not strong enough to dominate a subset of the agents, then the optimal voting rule is to break ties in favor of the strongest agent. However, during a game the system does not have access to the pdf of the agents, and has no way to identify which is the strongest agent. Therefore, we present results using the static voting rule, that break ties in favor of the strongest agent overall. Based on our synthetic results, we can predict that static should perform better than simple. We also tried a weighted voting rule, which allowed us to empirically learn the best weights by a hill climbing algorithm. The resulting rule was equivalent to the static voting rule.

We call a team composed by different Go software as "Diverse" or by the name of the voting rule that they use ("Simple" or "Static"). The team of copies of the strongest agent (Fuego) will be called "Copies". The copies are initialized with different random seeds, therefore due to the nature of the search algorithms, they will not always choose the same movement. When we want to be explicit about the number of agents in a team we will add a number after the name of the team. "Diverse" is composed by Fuego, GnuGo, Pachi and MoGo when executed with four agents, and is composed by all agents when executed with six agents. We also work with a parallelized version of Fuego ("Parallel"), and we will add a number after its name to indicate the number of threads.

We can see a summary of all our results in Figure 2. Diverse plays significantly better than Fuego, with 6 agents or when using the static voting rule. When we keep the opening database, Diverse plays significantly better than Copies and Parallel with 6 agents. Without the opening database, Diverse still plays significantly better than Parallel with 6 agents, but the difference between Diverse and Copies is not statistically significant. Static is either significantly better than Simple, or the difference between them is not statistically significant.

By the classical view of voting, our experimental result is not expected. If we view each agent as having a fixed pdf, we would predict that copies of the best agent would perform much better than a diverse team with weaker agents. However, in our results we showed that the diverse team has a competitive strength, and is able to play even better than copies of the best agent when we keep the opening database. Our model provides a theoretical explanation for our results.

5 Conclusion

This paper opens a new path for multi-agent team formation. Unlike existing work, we study team formation in the context of agents that vote together at each step of a complex problem. This introduces a new conflict between focusing on the diversity of a team or on the strength of each individual member when we pursue the best possible team. We opened this new path by showing that the na¨ıve solution of selecting the strongest agents does not work, as it is possible for a team of With DB

No DB

• (b) Winning rate of the uniform team (Copies), the Diverse team (Simple/Static), and a parallelized agent (Parallel)

Figure 2: Results in the Computer Go domain. The error bars show the confidence interval, with 99% of significance.

weak but diverse agents to perform better than a uniform team made of copies of the strongest agent. We also introduced the study of optimal voting rules for a diverse team, and showed both via mathematical analysis and experimentation that our proposed rules improve the performance of a team. Our experiments with a set of Go playing agents demonstrate the importance of our model, as the model provides a theoretical explanation of our results that would not be possible otherwise. It is also a concrete example that diversity can overcome strength in multi-agent team formation.

Acknowledgments: This research was supported by MURI grant W911NF-11-1-0332.