Publications

2015
D. J. Gerber, E. Pantazis, and L. S. Marcolino. 2015. “Design Agency: Prototyping Multi-Agent Systems in Architecture .” In CAAD Futures Conference.Abstract
This paper presents research on the prototyping of multi-agent systems for architectural design. It proposes a design exploration methodology at the intersection of architecture, engineering, and computer science. The motivation of the work includes exploring bottom up generative methods coupled with optimizing performance criteria including for geometric complexity and objective functions for environmental, structural and fabrication parameters. The paper presents the development of a research framework and initial experiments to provide design solutions, which simultaneously satisfy complexly coupled and often contradicting objectives. The prototypical experiments and initial algorithms are described through a set of different design cases and agents within this framework; for the generation of façade panels for light control; for emergent design of shell structures; for actual construction of reciprocal frames; and for robotic fabrication. Initial results include multi-agent derived efficiencies for environmental and fabrication criteria and discussion of future steps for inclusion of human and structural factors.
2015_29_teamcore_caad_futures_195_pp03_print.pdf
L. S. Marcolino, V. Nagarajan, and M. Tambe. 2015. “Every Team Deserves a Second Chance: An Interactive 9x9 Go Experience (Demonstration) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).Abstract
We show that without using any domain knowledge, we can predict the final performance of a team of voting agents, at any step towards solving a complex problem. This demo allows users to interact with our system, and observe its predictions, while playing 9x9 Go.
2015_16_teamcore_aamas15demo.pdf
V. Nagarajan, L. S. Marcolino, and M. Tambe. 2015. “Every team deserves a second chance: Identifying when things go wrong .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).Abstract
Voting among different agents is a powerful tool in problem solving, and it has been widely applied to improve the performance in finding the correct answer to complex problems. We present a novel benefit of voting, that has not been observed before: we can use the voting patterns to assess the performance of a team and predict their final outcome. This prediction can be executed at any moment during problem-solving and it is completely domain independent. We present a theoretical explanation of why our prediction method works. Further, contrary to what would be expected based on a simpler explanation using classical voting models, we argue that we can make accurate predictions irrespective of the strength (i.e., performance) of the teams, and that in fact, the prediction can work better for diverse teams composed of different agents than uniform teams made of copies of the best agent. We perform experiments in the Computer Go domain, where we obtain a high accuracy in predicting the final outcome of the games. We analyze the prediction accuracy for three different teams with different levels of diversity and strength, and we show that the prediction works significantly better for a diverse team. Since our approach is domain independent, it can be easily applied to a variety of domains.
2015_8_teamcore_aamas2015.pdf
V. Nagarajan, L. S. Marcolino, and M. Tambe. 2015. “Every team deserves a second chance: Identifying when things go wrong (Student Abstract Version) .” In Conference on Artificial Intelligence (AAAI 2015). Texas, USA.Abstract
We show that without using any domain knowledge, we can predict the final performance of a team of voting agents, at any step towards solving a complex problem.
2015_9_teamcore_aaai_student_abstract2015.pdf
V. Nagarajan, L. S. Marcolino, and M. Tambe. 2015. “Every Team Makes Mistakes: An Initial Report on Predicting Failure in Teamwork .” In AAAI Workshop Learning for General Competency in Video Games (AAAI 2015). Texas, USA.Abstract
Voting among different agents is a powerful tool in problem solving, and it has been widely applied to improve the performance in machine learning. However, the potential of voting has been explored only in improving the ability of finding the correct answer to a complex problem. In this paper we present a novel benefit in voting, that has not been observed before: we show that we can use the voting patterns to assess the performance of a team and predict their final outcome. This prediction can be executed at any moment during problem-solving and it is completely domain independent. We present a preliminary theoretical explanation of why our prediction method works, where we show that the accuracy is better for diverse teams composed by different agents than for uniform teams made of copies of the same agent. We also perform experiments in the Computer Go domain, where we show that we can obtain a high accuracy in predicting the final outcome of the games. We analyze the prediction accuracy for 3 different teams, and we show that the prediction works significantly better for a diverse team. Since our approach is completely domain independent, it can be easily applied to a variety of domains, such as the video games in the Arcade Learning Environment.
2015_10_teamcore_aaai_workshop2015.pdf
L. S. Marcolino, V. Nagarajan, and M. Tambe. 2015. “Every Team Makes Mistakes, in Large Action Spaces .” In Multidisciplinary Workshop on Advances in Preference Handling (M-PREF 2015).Abstract
Voting is applied to better estimate an optimal answer to complex problems in many domains. We recently presented a novel benefit of voting, that has not been observed before: we can use the voting patterns to assess the performance of a team and predict whether it will be successful or not in problem-solving. Our prediction technique is completely domain independent, and it can be executed at any time during problem solving. In this paper we present a novel result about our technique: we show that the prediction quality increases with the size of the action space. We present a theoretical explanation for such phenomenon, and experiments in Computer Go with a variety of board sizes.
2015_33_teamcore_mpref15.pdf
H. Xu, Z. Rabinovich, S. Dughmi, and M. Tambe. 2015. “Exploring Information Asymmetry in Two-Stage Security Games .” In AAAI Conference on Artificial Intelligence (AAAI).Abstract
Stackelberg security games have been widely deployed to protect real-world assets. The main solution concept there is the Strong Stackelberg Equilibrium (SSE), which optimizes the defender’s random allocation of limited security resources. However, solely deploying the SSE mixed strategy has limitations. In the extreme case, there are security games in which the defender is able to defend all the assets “almost perfectly” at the SSE, but she still sustains significant loss. In this paper, we propose an approach for improving the defender’s utility in such scenarios. Perhaps surprisingly, our approach is to strategically reveal to the attacker information about the sampled pure strategy. Specifically, we propose a two-stage security game model, where in the first stage the defender allocates resources and the attacker selects a target to attack, and in the second stage the defender strategically reveals local information about that target, potentially deterring the attacker’s attack plan. We then study how the defender can play optimally in both stages. We show, theoretically and experimentally, that the two-stage security game model allows the defender to achieve strictly better utility than SSE.
2015_3_teamcore_two_stage_game.pdf
Shahrzad Gholami, Chao Zhang, Arunesh Sinha, and Milind Tambe. 2015. “An extensive study of Dynamic Bayesian Network for patrol allocation against adaptive opportunistic criminals .” In IJCAI'15 Workshop on Behavioral, Economic and Computational Intelligence for Security (BECIS).Abstract
Police patrols are used ubiquitously to deter crimes in urban areas. A distinctive feature of urban crimes is that criminals react opportunistically to patrol officers’ assignments. Different models of adversary behavior have been proposed but their exact form remains uncertain. Recent work [Zhang et al., 2015] has explored learning the model from real-world criminal activity data. To that end, criminal behavior and the interaction with the patrol officers is represented as parameters of a Dynamic Bayesian Network (DBN), enabling application of standard algorithms such as EM to learn the parameters. More specifically, the EMC2 algorithm is a sequence of modifications to the DBN representation, that allows for a compact representation resulting in better learning accuracy and increased speed of learning. In this paper, we perform additional experiments showing the efficacy of the EMC2 algorithm. Furthermore, we explore different variations of Markov model. Unlike DBNs, the Markov models do not have hidden states, which indicate distribution of criminals, and are therefore easier to learn using standard MLE techniques. We compare all the approaches by learning from a real data set of criminal activity obtained from the police department of University of Southern California (USC) situated in Los Angeles, USA. We demonstrate a significant better accuracy of predicting the crime using the EMC2 algorithm compared to other approaches. This work was done in collaboration with the police department of USC.
2015_34_teamcore_keep_pace_with_criminal_workshop.pdf
Amulya Yadav, Thanh Nguyen, Francesco Delle Fave, Milind Tambe, Noa Agmon, Manish Jain, Widodo Ramono, and Timbul Batubara. 2015. “Handling Payoff Uncertainty in Green Security Domains with Adversary Bounded Rationality .” In In IJCAI-15 Workshop on Behavioral, Economic and Computational Intelligence for Security (BECIS-15).Abstract
Research on Stackelberg Security Games (SSG) has recently shifted to green security domains, for example, protecting wildlife from illegal poaching. Previous research on this topic has advocated the use of behavioral (bounded rationality) models of adversaries in SSG. As its first contribution, this paper, for the first time, provides validation of these behavioral models based on real-world data from a wildlife park. The paper’s next contribution is the first algorithm to handle payoff uncertainty – an important concern in green security domains – in the presence of such adversarial behavioral models.
2015_39_teamcore_yadav_becis2015.pdf
Amulya Yadav, Thanh Nguyen, Francesco Delle Fave, Milind Tambe, Noa Agmon, Manish Jain, Widodo Ramono, and Timbul Batubara. 2015. “Handling Payoff Uncertainty with Adversary Bounded Rationality in Green Security Domains .” In In IJCAI-15 Workshop on Algorithmic Game Theory (AGT-15).Abstract
Research on Stackelberg Security Games (SSG) has recently shifted to green security domains, for example, protecting wildlife from illegal poaching. Previous research on this topic has advocated the use of behavioral (bounded rationality) models of adversaries in SSG. As its first contribution, this paper, for the first time, provides validation of these behavioral models based on real-world data from a wildlife park. The paper’s next contribution is the first algorithm to handle payoff uncertainty – an important concern in green security domains – in the presence of such adversarial behavioral models.
2015_38_teamcore_yadav_agt2015.pdf
Yasaman Dehghani Abbasi, Martin Short, Arunesh Sinha, Nicole Sintov, Chao Zhang, and Milind Tambe. 2015. “Human Adversaries in Opportunistic Crime Security Games: Evaluating Competing Bounded Rationality Models .” In Conference on Advances in Cognitive Systems.Abstract
There are a growing number of automated decision aids based on game-theoretic algorithms in daily use by security agencies to assist in allocating or scheduling their limited security resources. These applications of game theory, based on the “security games” paradigm, are leading to fundamental research challenges: one major challenge is modeling human bounded rationality. More specifically, the security agency, assisted with an automated decision aid, is assumed to act with perfect rationality against a human adversary; it is important to investigate the bounded rationality of these human adversaries to improve effectiveness of security resource allocation. This paper for the first time provides an empirical investigation of adversary bounded rationality in opportunistic crime settings, where modeling bounded rationality is particularly crucial. We conduct extensive human subject experiments, comparing ten different bounded rationality models, and illustrate that: (a) while previous research proposed the use of the stochastic choice “quantal response” model of human adversary, this model is significantly outperformed by more advanced models of “subjective utility quantal response”; (b) Combinations of the well-known prospect theory model with these advanced models lead to an even better performance in modeling human adversary behavior; (c) while it is important to model the non-linear human weighing of probability, as advocated by prospect theory, our findings are the exact opposite of prospect theory in terms of how humans are seen to weigh this non-linear probability.
2015_20_teamcore_yasi_cogsy_re_submitted_version.pdf
Dehghani Abbasi Y., Short M., Sinha A., Sintov N., Zhang Ch., and Tambe M. 2015. “Human Adversaries in Opportunistic Crime Security Games: How Past success (or failure) affects future behavior .” In Workshop on Behavioral, Economic and Computational Intelligence for Security (IJCAI).Abstract
There are a growing number of automated decision aids based on game-theoretic algorithms in daily use by security agencies to assist in allocating or scheduling their limited security resources. These applications of game theory, based on the “security games” paradigm, are leading to fundamental research challenges: one major challenge is modeling human bounded rationality. More specifically, the security agency, assisted with an automated decision aid, is assumed to act with perfect rationality against a human adversary; it is important to investigate the bounded rationality of these human adversaries to improve effectiveness of security resource allocation. In (Abbasi et al, 2015), the authors provide an empirical investigation of adversary bounded rationality in opportunistic crime settings. In this paper, we propose two additional factors in the “subjective utility quantal response” model.
2015_28_teamcore_ijcai2015_re_submitted_version.pdf
Zinovi Rabinovich, Albert X. Jiang, Manish Jain, and Haifeng Xu. 2015. “Information Disclosure as a Means to Security .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
In this paper we present a novel Stackelberg-type model of security domains: Security Assets aSsignment with Information disclosure (SASI). The model combines both the features of the Stackelberg Security Games (SSGs) model and of the Bayesian Persuasion (BP) model. More specifically, SASI includes: a) an uncontrolled, exogenous security state that serves as the Defender’s private information; b) multiple security assets with non-accumulating, targetlocal defence capability; c) a pro-active, verifiable and public, unidirectional information disclosure channel from the Defender to the Attacker. We show that SASI with a non-degenerate information disclosure can be arbitrarily more efficient, than a “silent” Stackelberg assets allocation. We also provide a linear program reformulation of SASI that can be solved in polynomial time in SASI parameters. Furthermore, we show that it is possible to remove one of SASI parameters and, rather than require it as an input, recover it by computation. As a result, SASI becomes highly scalable.
2015_42_teamcore_sasi.pdf
Fei Fang, Thanh Nguyen, Benjamin Ford, Nicole Sintov, and Milind Tambe. 2015. “Introduction to Green Security Games (Extended Abstract) .” In Workshop on Cognitive Knowledge Acquisition and Applications (IJCAI 2015).Abstract
Conservation agencies around the world are tasked with protecting endangered wildlife from poaching. Despite their substantial efforts, however, species are continuing to be poached to critical status and, in some cases, extinction. In South Africa, rhino poaching has seen a recent escalation in frequency; while only 122 rhinos were poached in 2009, a record 1215 rhinos were poached in 2014 (approximately 1 rhino every eight hours)[the Rhino International, 2015]. To combat poaching, conservation agencies send well-trained rangers to patrol designated protected areas. However, these agencies have limited resources and are unable to provide 100% coverage to the entire area at all times. Thus, it is important that agencies make the most efficient use of their patrolling resources, and we introduce Green Security Games (GSGs) as a tool to aid agencies in designing effective patrols. First introduced by [Von Stengel and Zamir, 2004] as a Leadership Game, Stackelberg Games have been applied in a variety of Security Game research (i.e., Stackelberg Security Games, or SSGs). In particular, the focus on randomization in Stackelberg Games lends itself to solving real-world security problems where defenders have limited resources, such as randomly allocating Federal Air Marshals to international flights [Tsai et al., 2009]. However, the SSG model focuses on generating an optimal defender strategy against a single defender-attacker interaction (e.g., a single terrorist attack). For domains where attacks occur frequently, such as in wildlife conservation, another type of Security Game is needed that effectively models the repeated interactions between the defender and the attacker. While still following the Leader-Follower paradigm of SSGs, GSGs have been developed as a way of applying Game Theory to assist wildlife conservation efforts, whether its to prevent illegal fishing [Haskell et al., 2014], illegal logging [Johnson et al., 2012], or wildlife poaching [Yang et al., 2014]. GSGs are similar to SSGs except that, in GSGs, the game takes place over N rounds. In SSGs, once the attacker makes a decision, the game is over, but in GSGs, the attacker (e.g., the poacher) and defender have multiple rounds in which they can adapt to each other’s choices in previous rounds. This multi-round feature of GSGs introduces some key research challenges that are being studied: (1) how can we incorporate the attacker’s previous choices into our model of their behavior, in order to improve the defender’s strategy, [Yang et al., 2014; Kar et al., 2015] and (2) how do we choose a strategy such that the long-term payoff (i.e., cumulative expected utility) is maximized [Fang et al., 2015]? In addition to exploring these open research questions, we also discuss field tests of the Protection Assistant for Wildlife Security (PAWS) software in Uganda and Malaysia.
2015_27_teamcore_ijcai2015_gsg.pdf
Chao Zhang, Arunesh Sinha, and Milind Tambe. 2015. “Keeping pace with criminals: Designing patrol allocation against adaptive opportunistic criminals .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).Abstract
Police patrols are used ubiquitously to deter crimes in urban areas. A distinctive feature of urban crimes is that criminals react opportunistically to patrol officers’ assignments. Compared to strategic attackers (such as terrorists) with a well-laid out plan, opportunistic criminals are less strategic in planning attacks and more flexible in executing them. In this paper, our goal is to recommend optimal police patrolling strategy against such opportunistic criminals. We first build a game-theoretic model that captures the interaction between officers and opportunistic criminals. However, while different models of adversary behavior have been proposed, their exact form remains uncertain. Rather than simply hypothesizing a model as done in previous work, one key contribution of this paper is to learn the model from real-world criminal activity data. To that end, we represent the criminal behavior and the interaction with the patrol officers as parameters of a Dynamic Bayesian Network (DBN), enabling application of standard algorithms such as EM to learn the parameters. Our second contribution is a sequence of modifications to the DBN representation, that allows for a compact representation of the model resulting in better learning accuracy and increased speed of learning of the EM algorithm when used for the modified DBN. These modifications use marginalization approaches and exploit the structure of this problem. Finally, our third contribution is an iterative learning and planning mechanism that keeps updating the adversary model periodically. We demonstrate the efficiency of our learning algorithm by applying it to a real data set of criminal activity obtained from the police department of University of Southern California (USC) situated in Los Angeles, USA. We project a significant reduction in crime rate using our planning strategy as opposed to the actual strategy deployed by the police department. We also demonstrate the improvement in crime prevention in simulations when we use our iterative planning and learning mechanism compared to just learning once and planing. This work was done in collaboration with the police department of USC.
2015_13_teamcore_keep_pace_with_criminal.pdf
Chao Zhang, Manish Jain, Ripple Goyal, Arunesh Sinha, and Milind Tambe. 2015. “Keeping pace with criminals: Learning, Predicting and Planning against Crime: Demonstration Based on Real Urban Crime Data (Demonstration) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).Abstract
Crime in urban areas plagues every city in all countries. This demonstration will show a novel approach for learning and predicting crime patterns and planning against such crimes using real urban crime data. A notable characteristic of urban crime, distinct from organized terrorist attacks, is that most urban crimes are opportunistic in nature, i.e., criminals do not plan their attacks in detail, rather they seek opportunities for committing crime and are agile in their execution of the crime [6, 7, 1, 4]. Police officers conduct patrols with the aim of preventing crime. However, criminals can adapt their strategy in response of police deployment by seeking crime opportunity in less effectively patrolled location. The problem of where and how much to patrol is therefore important. There are two approaches to solve this problem. The first approach is to schedule patrols manually by human planners, which is followed in various police departments. However, it has been demonstrated that manual planning of patrols is not only time-consuming but also highly ineffective in related scenarios of protecting airport terminals [3] and ships in ports [5]. The second approach is to use automated planners to plan patrols against urban crime. This approach has either focused on modeling the criminal explicitly [7,6] (rational, bounded rational, etc.) in a game model or to learn the adversary behavior using machine learning [2]. However, the proposed mathematical models of criminal behavior have not been validated with real data. Also, prior machine learning approaches have either only focused on the adversary actions ignoring their adaptation to the defenders’ actions [2]. Hence, in this presentation we propose a novel approach to learn and update the criminal behavior from real data [8]. We model the interaction between criminals and patrol officers as a Dynamic Bayesian Network (DBN). Figure 1 shows an example of such DBN. Next, we apply a dynamic programming algorithm to generate optimal patrol strategy against the learned criminal model. By iteratively updating the criminals’ model and computing patrol strategy against them, we help patrol officers keep up with criminals’ adaptive behavior and execute effective patrols. This process is shown as a flow chart in Figure 2. With this context, the demonstration presented in this paper introduces a web-based software with two contributions. First, our system collects and analyzes crime reports and resources (security camera, emergency supplies, etc.) data, presenting them in various forms. Second, our patrol scheduler incorporates the algorithm in [8] in a scheduling recommendation system. The demonstration will engage audience members by having them participate as patrol officers and using the software to ‘patrol’ the University of Southern California (USC) campus in USA.
2015_15_teamcore_de005_zhang_learning_demo.pdf
Debarun Kar, Fei Fang, Francesco Delle Fave, Nicole Sintov, Arunesh Sinha, Aram Galstyan, Bo An, and Milind Tambe. 2015. “Learning Bounded Rationality Models of the Adversary in Repeated Stackelberg Security Games .” In Adaptive and Learning Agents Workshop at the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015).Abstract
Several competing human behavior models have been proposed to model and protect against boundedly rational adversaries in repeated Stackelberg security games (SSGs). However, these existing models fail to address three main issues which are extremely detrimental to defender performance. First, while they attempt to learn adversary behavior models from adversaries’ past actions (“attacks on targets”), they fail to take into account adversaries’ future adaptation based on successes or failures of these past actions. Second, they assume that sufficient data in the initial rounds will lead to a reliable model of the adversary. However, our analysis reveals that the issue is not the amount of data, but that there just is not enough of the attack surface exposed to the adversary to learn a reliable model. Third, current leading approaches have failed to include probability weighting functions, even though it is well known that human beings’ weighting of probability is typically nonlinear. Moreover, the performances of these models may be critically dependent on the learning algorithm used to learn the parameters of these models. The first contribution of this paper is a new human behavior model, SHARP, which mitigates these three limitations as follows: (i) SHARP reasons based on success or failure of the adversary’s past actions on exposed portions of the attack surface to model adversary adaptiveness; (ii) SHARP reasons about similarity between exposed and unexposed areas of the attack surface, and also incorporates a discounting parameter to mitigate adversary’s lack of exposure to enough of the attack surface; and (iii) SHARP integrates a non-linear probability weighting function to capture the adversary’s true weighting of probability. Our second contribution is a comparison of two different approaches for learning the parameters of the bounded rationality models. Our third contribution is a first “longitudinal study” – at least in the context of SSGs – of competing models in settings involving repeated interaction between the attacker and the defender. This study, where each experiment lasted a period of multiple weeks with individual sets of human subjects, illustrates the strengths and weaknesses of different models and shows the advantages of SHARP.
2015_27_teamcore_ijcai2015_gsg.pdf
D. J. Gerber, E. Pantazis, L. S. Marcolino, and A. Heydarian. 2015. “A Multi-Agent Systems for Design Simulation Framework: Experiments with Virtual-Physical-Social Feedback for Architecture .” In Symposium on Simulation for Architecture and Urban Design (SimAUD 2015).Abstract
This paper presents research on the development of multiagent systems (MAS) for integrated and performance driven architectural design. It presents the development of a simulation framework that bridges architecture and engineering, through a series of multi-agent based experiments. The research is motivated to combine multiple design agencies into a system for managing and optimizing architectural form, across multiple objectives and contexts. The research anticipates the incorporation of feedback from real world human behavior and user preferences with physics based structural form finding and environmental analysis data. The framework is a multi-agent system that provides design teams with informed design solutions, which simultaneously optimize and satisfy competing design objectives. The initial results for building structures are measured in terms of the level of lighting improvements and qualitatively in geometric terms. Critical to the research is the elaboration of the system and the feedback loops that are possible when using the multi-agent systems approach.
2015_18_teamcore_simaud2015.pdf
Eric Shieh. 2015. “Not a Lone Ranger: Unleashing Defender Teamwork in Security Games ”.Abstract
Game theory has become an important research area in handling complex security resource allocation and patrolling problems. Stackelberg Security Games (SSGs) have been used in modeling these types of problems via a defender and an attacker(s). Despite recent successful real-world deployments of SSGs, scale-up to handle defender teamwork remains a fundamental challenge in this field. The latest techniques do not scale-up to domains where multiple defenders must coordinate time-dependent joint activities. To address this challenge, my thesis presents algorithms for solving defender teamwork in SSGs in two phases. As a first step, I focus on domains without execution uncertainty, in modeling and solving SSGs that incorporate teamwork among defender resources via three novel features: (i) a column-generation approach that uses an ordered network of nodes (determined by solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation of iterative reward shaping of multiple coordinating defender units to generate coordinated strategies; (iii) generation of tighter upper-bounds for pruning by solving security games that only abide by key scheduling constraints. In the second stage of my thesis, I address execution uncertainty among defender resources that arises from the real world by integrating the powerful teamwork mechanisms offered by decentralized Markov Decision Problems (Dec-MDPs) into security games. My thesis offers the following novel contributions: (i) New model of security games with defender teams that coordinate under uncertainty; (ii) New algorithm based on column generation that utilizes Decentralized Markov Decision Processes (Dec-MDPs) to generate defender strategies that incorporate uncertainty; (iii) New techniques to handle global events (when one or more agents may leave the system) during defender execution; (iv) Heuristics that help scale up in the number of targets and resources to handle real-world scenarios; (v) Exploration of the robustness of randomized pure strategies. Different mechanisms, from both solving situations with and without execution uncertainty, may be used depending on the features of the domain. This thesis opens the door to a powerful combination of previous work in multiagent systems on teamwork and security games.
2015_19_teamcore_shieh_thesis_20150324.pdf
L. S. Marcolino, H. Xu, A.X. Jiang, M. Tambe, and E. Bowring. 2015. “The Power of Teams that Disagree: Team Formation in Large Action Spaces .” In Coordination, Organizations, Institutions and Norms in Agent Systems X. Springer-Verlag Lecture Notes in AI, 2015.Abstract
Recent work has shown that diverse teams can outperform a uniform team made of copies of the best agent. However, there are fundamental questions that were never asked before. When should we use diverse or uniform teams? How does the performance change as the action space or the teams get larger? Hence, we present a new model of diversity, where we prove that the performance of a diverse team improves as the size of the action space increases. Moreover, we show that the performance converges exponentially fast to the optimal one as we increase the number of agents. We present synthetic experiments that give further insights: even though a diverse team outperforms a uniform team when the size of the action space increases, the uniform team will eventually again play better than the diverse team for a large enough action space. We verify our predictions in a system of Go playing agents, where a diverse team improves in performance as the board size increases, and eventually overcomes a uniform team.1
2015_32_teamcore_coin2014book.pdf

Pages