Adversarial decision and optimization-based models

Abstract

Decision making is all around us. Everyone makes choices everyday, from the moment we open our eyes in the morning. Some of them do not have very important consequences in our life and these consequences are easy to take into account. However, in the business world, managers make decisions that have important consequences on the future of their own firm (in terms of revenues, market position, business policy) and their employees. In these cases, it is difficult to account for all the possible alternatives and consequences and to quantify them. Decision making tools such as Decision Analysis are required in order to determine the optimal decision. Furthermore, when several competing agents are involved in a decision making situation and their combination of actions affect each other’s revenues, the problem becomes even more complicated. The way an agent makes a decision and the tools required to determine the optimal decision change. When we are aware of someone observing and reacting to our behavior, one might occasionally prefer a sub-optimal choice aimed at causing confusion on the adversary, so that it will be more difficult for him to guess our decision in future encounters, which may report us a larger benefit. This situation arises in counter-terrorist combat, terrorism prevention, military domains, homeland security, computer games, intelligent training systems, economic adversarial domains, and more. In simple terms, we define an adversary as an entity whose aims are somehow inversely related to ours, and who may influence the profits we obtain from our decisions by taking his/her own actions. This kind of competitive interaction between two agents fits a variety of complex situations which can be analyzed with a number of techniques ranging from Knowledge Engineering and Artificial Intelligence (agent-based modeling, tree exploration, machine learning) to Operational Research, with an emphasis on Game Theory. The objective of this thesis is the analysis and design of adversarial decision and optimization-based models which are able to represent adversarial situations. We are going to conduct theoretical studies and propose practical applications including imitation games, security games and patrolling domains. More precisely, we first study a two-agent imitation game in which one of the agents does not know the motivation of the other, and tries to predict his decisions when repeatedly engaging in a conflict situation, by observing and annotating the past decisions. We propose randomized strategies for the agents and study their performance from a theoretical and empirical point of view. Several variants of this situation are analyzed. Then we move on to practical applications. We address the problem of extracting more useful information from observations of a randomized Markovian strategy that arises when solving a patrolling model, and propose a mathematical procedure based on fuzzy sets and fuzzy numbers for which we provide a ready-to-use implementation in an R package. Finally, we develop an application of adversarial reasoning to the problem of patrolling an area using an autonomous aerial vehicle to protect it against terrestrial intruders, and solve it using a mix of game-theoretic techniques and metaheuristics.