Abstract
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 conclude with an overview of the research activity in my group.
Biography
Shaunak D. Bopardikar is an Assistant Professor with the Electrical and Computer Engineering Department, and is affiliated with the Center for Connected Autonomous Networked Vehicles for Active Safety (CANVAS) at the Michigan State University. His research interests lie in scalable computation and optimization, in cyber-physical security and in autonomous motion planning and control. He received the Bachelor of Technology (B.Tech.) and Master of Technology (M.Tech.) degrees in Mechanical Engineering from Indian Institute of Technology, Bombay, India, in 2004, and the Ph.D. degree in Mechanical Engineering from the University of California at Santa Barbara, USA, in 2010. From 2004 to 2005, he was an Engineer with General Electric India Technology Center, Bangalore, India. From 2011 to 2018, he was a Staff Research Scientist with the Controls group of United Technologies Research Center (UTRC) at East Hartford, CT, USA and at Berkeley, CA. Prior to joining UTRC, Dr. Bopardikar 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 Senior member of the IEEE, has over 50 refereed journal and conference publications and has 2 inventions filed for U.S. patent.
MENU 
