Games and Graphs

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.