UTRC CDS Invited Lecture: Shaunak Bopardikar, "Solving Large Zero-Sum Matrix Games"
Friday, February 24, 2017
2168 AV Williams Bldg
Solving Large Zero-Sum Matrix Games: Randomized and Approximate Algorithms
Dr. Shaunak D. Bopardikar
Staff Research Scientist
United Technologies Research Center
East Hartford, CT
Game theory has evolved into a rigorous framework to model problems involving reasoning in the presence of an adversary. However, modern-day engineering systems tend to be inherently complex and the number of possible options to reason over pose problems of scalability. Such situations routinely arise in games, especially under partial-information such as Scrabble, Bridge, etc., in which the computation of optimal strategies involves exploration of very large decision trees. Typical techniques to address such problems are Monte Carlo sampling, for which no formal guarantees on the quality of the solution are known. In this talk, we will see how randomized and approximate algorithms can yield elegant tradeoffs between accuracy (confidence/quality of the outcome) and performance (computational efficiency) to solve large dimensional zero-sum matrix games. I will first formalize randomized algorithms that provide a security policy and a security level which, with a high probability, is also a security policy against an adversary using a similar randomized algorithm to compute her policy. The main highlight will be formal results on determining how many random samples are needed to guarantee a desired level of confidence. We will see the usefulness of the algorithms and the results in a hide-and-seek game that is known to exhibit exponential complexity. I will then address a particular version of the game for which we will examine an incremental approximate method based on a simple criterion to determine whether an approximately computed security policy needs to be re-computed when new information about the adversary is introduced. Finally, I will present future directions for this work.
Dr. Shaunak D. Bopardikar is a Staff Research Scientist with the Controls group of United Technologies Research Center at East Hartford, CT, USA. He contributes to the advancement of scalable computation and optimization, to the cyber-physical security initiative and to the development of autonomous motion planning and control. While at UTRC, he serves as a Principal Investigator on a research award from the Office of Naval Research on Randomized and Distributed Matrix Factorization for Missing Data Inference. Prior to joining UTRC, Shaunak worked as a post-doctoral associate at UC Santa Barbara (2010-2011) during which he developed randomized algorithms for solving large matrix games. He is a member of the IEEE, has over 40 refereed journal and conference publications and has 1 invention filed for a U.S. patent.