Approaches to Extending Game-Theoretic Analyses to Complex, Real-World Scenarios
Authors: William Neal Reilly, Leonard Eusebi
Abstract: In domains ranging from military engagements to business to politics to games, competitors take actions to gain an advantage over others. Game theory has been used extensively since the 1950s to analyze such domains and to gain insights into the best moves for all competitors. While it is a powerful tool for analysis, game theory often falls short when applied to real-world encounters. Game-theoretic approaches over-simplify by assuming each side is composed of rational actors that attempt to maximize a single-valued utility function. Even with that simplification, real-world scenarios are often difficult to formalize as a solvable “game,” and even when the problem can be defined as a game, it is computationally expensive to calculate the best actions for each actor.We will present research that extends game theory to include multiple forms of utility for each actor. This enables us to recast traditional, albeit simple game-theory games like the Prisoners’ Dilemma and the Ultimatum Game, which produce results at odds with real-world expectations when confined to traditional measures of utility (i.e., minimizing jail time and maximizing money). By adding utility measures like commitment and fairness, we can generate a Pareto-optimal set of solutions that are better at recreating and explaining real-world behavior than traditional single-utility game theory. In our formulation, the actors are still acting rationally, they are just factoring in a more complex set of tradeoffs that our multi-utility game theory can naturally model.We will also present research into a game representation scheme that lets the scenario modeler express real-world action-to-action constraints like “enables” and “blocks.” These constraints support basic reasoning about ordering of actions without having to build full search tress or reason about time generally. Accounting for these constraints also significantly reduces the space of possible solutions, making it tractable to find exact solutions for certain classes of complex scenarios.Finally, we will present a software toolkit that simplifies the process of defining a game and analyzing the plausible outcomes. The model building tool helps analysts capture the goals and motivations of each actor, the actions available, and how those actions affect goals or other actions. Using these models, the analysis suite calculates the Pareto-optimal choices for each actor in that scenario and helps analysts navigate the plausible outcomes. With these tools, decision makers can assess the value of their strategic options, even in cases where adversaries may choose actions traditional game theory would label incorrect.We have used the software toolkit to create and analyze several models, from simple games like rock-paper-scissors to a real-world political gray-zone conflict with 3 nation states, 23 possible actions, 18 different motivations, and 10^21 possible solutions. The results were computed in seconds and align with behavior of the real-world actors. Policy analysts without a background in computational modeling have also used the toolkit to create “backcasting” models of historical situations. These models successfully explained the behavior of the actors involved. These evaluations show that the toolkit is both useful and usable for analyzing real-world multi-actor interactions.
Keywords: game theory, computational modeling, adversarial decision making, decision support, multi-objective optimization
Cite this paper: