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

Open Access
Author:
Paulson, Elisabeth C
Graduate Program:
Mathematics
Degree:
Master of Arts
Document Type:
Master Thesis
Date of Defense:
None
Committee Members:
  • Christopher Griffin, Thesis Advisor
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.