Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Dalhousie University

$38,000.00

Games and Graphs

FY 2023-24

Summary
Playing games is one of the oldest human intellectual activities but is only within the last 100 years that mathematics has offered any real insights. Most of mathematics deals with `nature' or it describes ongoing situations. The mathematics of games has to take in to account an intelligent opponent. For example, consider the problems of capturing an intruder who is fleeing pursuers in a system of passageways. If the intruder is much faster than the pursuers this can be used as a model for decontaminating the passageways from chemical or biological spills. The worst-case scenario is that the contaminant/intruder is an intelligent adversary! A second important example is playing for influence before a vote. The main goal is to identify good strategies that humans can understand and implement. There has been great success in the game theory originating in the fields of economics, biology and psychology where there are many players, simultaneous moves and hidden information. Only in the last 50 years has the foundations of a mathematical theory for "last-player-to-move-wins" games (e.g., Chess, Checkers, Go, and Hex) been laid. An important result is that a game can be replaced by an equivalent, unique simplest game thereby reducing the complexity in identifying good strategies. Even identifying an `infinitesimal' (i.e., a very, very small edge) in a game can gain a move that could earn extra money for professional players or turn an election in tight races. In the last 5 years, the theory has been extended significantly to cover where the winner has the greater score. The proposed research will identify and exploit the hidden structures in these classes of games to obtain good strategies. This research will also extend the theory to classes of games where the players move simultaneously but where one player has advanced knowledge of the opponent's move. This is the `Cheating Robot' model where the `robot' is fast enough to recognize what move the `human' is making and respond. The games are deterministic and do not involve any probabilities.
Program
Discovery Grants Program - Individual
Location
Nova Scotia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2019-04914
Name nom
Nowakowski, Richard
Department département
Mathematics and Statistics - Mathematics and Statistics
Organization id
79
Institution établissement
Dalhousie University
Province en
Nova Scotia
Province fr
Nouvelle-Écosse
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2019
Award amount
38000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2950
Research subject group en
Applied mathematics
Research subject group fr
Applied mathematics
Research subject en
Mathématiques appliquées
Research subject fr
Mathématiques appliquées
Application title
Games and Graphs
Keyword
combinatorial games; game-theoretic graph parameters; influence games; scoring games
Application summary
Playing games is one of the oldest human intellectual activities but is only within the last 100 years that mathematics has offered any real insights. Most of mathematics deals with `nature' or it describes ongoing situations. The mathematics of games has to take in to account an intelligent opponent. For example, consider the problems of capturing an intruder who is fleeing pursuers in a system of passageways. If the intruder is much faster than the pursuers this can be used as a model for decontaminating the passageways from chemical or biological spills. The worst-case scenario is that the contaminant/intruder is an intelligent adversary! A second important example is playing for influence before a vote. The main goal is to identify good strategies that humans can understand and implement. There has been great success in the game theory originating in the fields of economics, biology and psychology where there are many players, simultaneous moves and hidden information. Only in the last 50 years has the foundations of a mathematical theory for "last-player-to-move-wins" games (e.g., Chess, Checkers, Go, and Hex) been laid. An important result is that a game can be replaced by an equivalent, unique simplest game thereby reducing the complexity in identifying good strategies. Even identifying an `infinitesimal' (i.e., a very, very small edge) in a game can gain a move that could earn extra money for professional players or turn an election in tight races. In the last 5 years, the theory has been extended significantly to cover where the winner has the greater score. The proposed research will identify and exploit the hidden structures in these classes of games to obtain good strategies. This research will also extend the theory to classes of games where the players move simultaneously but where one player has advanced knowledge of the opponent's move. This is the `Cheating Robot' model where the `robot' is fast enough to recognize what move the `human' is making and respond. The games are deterministic and do not involve any probabilities.
Dalhousie University - $38,000 Grant (2023-24) | Canada Spends