A Reformulation of the CSSR Algorithm and Application to Optimal Deception Strategy in Two Player Games

Open Access
Author:
Paulson, Elisabeth C
Area of Honors:
Mathematics
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
  • Christopher H Griffin, Thesis Supervisor
  • Svetlana Katok, Honors Advisor
  • Svetlana Katok, Faculty Reader
Keywords:
  • hidden markov models
  • probabilistic finite-state machine
  • deception strategy
  • game theory
Abstract:
In this thesis we explore a reformulation of the Casual State Splitting and Reconstruction (CSSR) algorithm and an application to optimal strategies for deception in repeated two-player games. The CSSR algorithm is used to infer probabilistic nite-state machines from an input stream of data. We formulate an integer programming version of the CSSR algorithm which always results in minimal probabilistic nite-state automata given an input stream of data. This reformulation is shown to be NP-hard by comparing it to the minimal clique covering problem in graph theory. We then apply this algorithm to optimal deception strategies in repeated two-player games in which one player seeks to deceive the other by making use of a deceptive \learning period". We find that this can be modeled by combining both linear optimization with a genetic algorithm. We present numerical examples of optimal deception as well as some theoretical results.