Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Alberta

$42,000.00

Human-Scale Game Theory in Imperfect Information Settings

FY 2015-16

Summary
Decision making in the presence of other agents is a critical challenge for deploying artificially intelligent agents in real-world settings. Real world settings -- ranging from negotiation to security to interactive entertainment -- also typically involve imperfect information, where agents are missing key pieces of information to make their decisions. Game-theoretic techniques for decision-making under such circumstances have recently seen considerable improvement. However, they are still not adequate for human-scale problems. For example, advancements in general-purpose equilibrium algorithms for sequential games have made it possible to solve games with trillions of game states (up from millions only 5 years ago), yet the smallest variants of well known games played by humans (e.g., poker) are still far much larger. While my research group has had some recent success at playing complex games at a human level, the techniques employed necessarily give up theoretical guarantees when applied to such large domains. Without guarantees, though, it is hard to predict the success of the approaches for other applications, or guide a practitioner in how best to exploit improvements in computing resources. This research will develop new algorithmic approaches to human-scale multiagent scenarios with imperfect information, while preserving theoretical guarantees. The research aims at developing a toolbox of techniques for automating decisions in such domains, with the theoretical guarantees enabling predictable results for the practitioner. The research focuses on both tools for computing robust static strategies, when no knowledge of the other participating agents is available, and learning strategies that adapt to the other participants' behavior. In addition to tools for decision-making, the research also examines the problem of identifying illicit collusion in complex multiagent interactions. The toolbox aims to make the currently complex domain-dependent game-theoretic algorithms more practical and off-the-shelf usable for domain experts.
Program
Discovery Grants Program - Individual
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
298239-2012
Name nom
Bowling, Michael
Department département
Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2012
Award amount
42000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Partie
4
Nb partie
5
Application title
Human-Scale Game Theory in Imperfect Information Settings
Keyword
NSERC
Application summary
Decision making in the presence of other agents is a critical challenge for deploying artificially intelligent agents in real-world settings. Real world settings -- ranging from negotiation to security to interactive entertainment -- also typically involve imperfect information, where agents are missing key pieces of information to make their decisions. Game-theoretic techniques for decision-making under such circumstances have recently seen considerable improvement. However, they are still not adequate for human-scale problems. For example, advancements in general-purpose equilibrium algorithms for sequential games have made it possible to solve games with trillions of game states (up from millions only 5 years ago), yet the smallest variants of well known games played by humans (e.g., poker) are still far much larger. While my research group has had some recent success at playing complex games at a human level, the techniques employed necessarily give up theoretical guarantees when applied to such large domains. Without guarantees, though, it is hard to predict the success of the approaches for other applications, or guide a practitioner in how best to exploit improvements in computing resources. This research will develop new algorithmic approaches to human-scale multiagent scenarios with imperfect information, while preserving theoretical guarantees. The research aims at developing a toolbox of techniques for automating decisions in such domains, with the theoretical guarantees enabling predictable results for the practitioner. The research focuses on both tools for computing robust static strategies, when no knowledge of the other participating agents is available, and learning strategies that adapt to the other participants' behavior. In addition to tools for decision-making, the research also examines the problem of identifying illicit collusion in complex multiagent interactions. The toolbox aims to make the currently complex domain-dependent game-theoretic algorithms more practical and off-the-shelf usable for domain experts.