PIE: A Data-Driven Payoff Inference Engine for Strategic Security Applications

Although most game theory models assume that payoff matrices are provided as input, getting payoff matrices in strategic games (e.g., corporate negotiations and counter-terrorism operations) has proven difficult. To tackle this challenge, we propose a payoff inference engine (PIE) that finds payoffs assuming that players in a game follow a myopic best response or a regret minimization heuristic. This assumption yields a set of constraints (possibly nonlinear) on the payoffs with a multiplicity of solutions. PIE finds payoffs by considering solutions of these constraints and their variants via three heuristics. First, we approximately compute a centroid of the resulting polytope of the constraints. Second, we use a soft constraint approach that allows violation of constraints by penalizing violations in the objective function. Third, we develop a novel approach to payoff inference based on support vector machines (SVMs). Unlike past work on payoff inference, PIE has the following advantages. PIE supports reasoning about multiplayer games, not just one or two players, it can use short histories, not long ones which may not be available in many real-world situations, it does not require all players to be fully rational, and it is one to two orders of magnitude more scalable than past work. We run experiments on a synthetic data set where we generate payoff functions for the players and see how well our algorithms can learn them, a real-world coarse-grained counter-terrorism data set about a set of different terrorist groups, and a real-world fine-grained data set about a specific terrorist group. As the ground truth about payoffs for the terrorist groups cannot be tested directly, we test PIE by using the payoffs to make predictions about the actions of the groups and corresponding governments (even though this is not the purpose of this article). We show that compared with recent work on payoff inference, PIE has both higher accuracy and much shorter runtime.