A Reformulation of the CSSR Algorithm and Application to Optimal Deception Strategy in Two Player Games
- Author
- Paulson, Elisabeth
- Published
- [University Park, Pennsylvania] : Pennsylvania State University, 2015.
- Physical Description
- 1 electronic document
- Additional Creators
- Griffin, Christopher and Schreyer Honors College
Access Online
- honors.libraries.psu.edu , Connect to this object online.
- Restrictions on Access
- Open Access.
- Summary
- 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 inwhich 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.
- Other Subject(s)
- Genre(s)
- Dissertation Note
- B.S. Pennsylvania State University 2015.
- Technical Details
- The full text of the dissertation is available as an Adobe Acrobat .pdf file ; Adobe Acrobat Reader required to view the file.
View MARC record | catkey: 15439928