Grant: Discovery Grants Program - Individual

A network, also called a graph, is a set of nodes connected by edges. Pursuit-evasion games and combinatorial games are two areas of research that involve competitive two player games on networks. Optimal play involves efficiently allocating resources. In pursuit-evasion games, one player attempts to capture the other, while their opponent attempts to evade capture indefinitely. Players move between nodes using edges. These games model real-world scenarios such as apprehending a criminal within a city or locating a missing person. The main goal in pursuit-evasion research is to determine the minimum number of pursuers (searchers) required for a task. More recently, the time it takes to complete the task as well as balancing the cost of several resources have been studied for the classic game of Cops and Robbers, which has perfect information. My research will develop algorithms and techniques for efficient resource allocation when the pursuers use signal detection to locate an invisible adversary. Using signal detection means the pursuers can travel to any node of the network. This is called the Localization Game and has imperfect information. My goal is to determine how to balance both time and number of pursuers to minimize overall costs. My proposal also outlines two additional scenarios, where I will make significant progress by characterizing graph structures given a game parameter value. Combinatorial game theory is the study of two player, perfect information games of no chance, where players alternate turns. A major challenge is the number of computations needed to determine who wins and their optimal strategy. Game states can be modeled using directed graphs, where one node has an arrow emanating from it to another node when a player can move from one state to the next. Canonical form game graphs are the simplest representation of the games and are useful because they require the fewest number of computations. Though canonical forms of games have been studied for years, they have not yet been studied from a graph theoretic perspective. A real-world application involves two construction companies in competition for contracts to work for a governing body. Each node is the state of construction, and each arrow is given a cost and coloured based on the company offering the service. The most efficient route is the most cost effective for the governing body and determines which company to hire for each task. My goal is to characterize the structure of canonical form game graphs. My research program will contribute to the advancement of knowledge within mathematics. In the broader community, this work will inform best practices for efficient resource allocation for search-and-rescue operations as well as how an agency assigns tasks to two competing firms in the most efficient way while minimizing costs.