Game Theory for Autonomy: From Min-Max Optimization to Equilibrium and Bounded Rationality Learning

Finding Nash equilibria in non-cooperative games can be, in general, an exceptionally challenging task. This is owed to various factors, including but not limited to the cost functions of the game being nonconvex/nonconcave, the players of the game having limited information about one another, or even due to issues of computational complexity. The present tutorial draws motivation from this harsh reality and provides methods to approximate Nash or min-max equilibria in non-ideal settings using both optimization- and learning-based techniques. The tutorial acknowledges, however, that such techniques may not always converge, but instead lead to oscillations or even chaos. In that respect, tools from passivity and dissipativity theory are provided, which can offer explanations about these divergent behaviors. Finally, the tutorial highlights that, more frequently than often thought, the search for equilibrium policies is simply vain; instead, bounded rationality and non-equilibrium policies can be more realistic to employ owing to some players’ learning imperfectly or being relatively naive – "bounded rational." The efficacy of such plays is demonstrated in the context of autonomous driving systems, where it is explicitly shown that they can guarantee vehicle safety.

I. Introduction

Game theory is a mathematical and scientific field that investigates the interactions among multiple decision makers with self-interests [1]. Such interactions have long been ubiquitous in civilian and military applications, hence the research interest in game theory has been incessant, continuously advancing it and making it more applicable to real-world systems that operate in multi-agent environments [2]–[4]. At the same time, it is generally acknowledged that game theory is unable to offer a panacea, i.e., a universally effective algorithm that can enable agents (also called players) to adapt or learn the "best" strategies to respond to other players. This is especially true when the other players’ strategies are unpredictable and imperfect—"bounded rational."