Computing team-maxmin equilibria in zero-sum multiplayer games

• Main Author: Zhang, Youzhi
• Other Authors: Bo An
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
• Online Access: https://hdl.handle.net/10356/142946
• Institution: Nanyang Technological University

Efficiently computing Nash Equilibria (NEs) for multiplayer games is still an open challenge in computational game theory. In fact, it is not only hard to compute NEs in multiplayer games, but also hard for players independently choosing strategies and then forming an NE because NEs are not exchangeable. This thesis focuses on computing Team-Maxmin Equilibria (TMEs), which was introduced as a solution concept for zero-sum multiplayer games where players in a team having the same utility function play against an adversary. The Correlated TME (CTME) is a variant of the TME, where team players can synchronize (correlate) their strategies by exploiting a mediator recommending actions to them through communication. According to different forms of communication, the CTME in extensive-form games includes: 1) the TME with Coordination device (TMECor) for the situation where team players can communicate their actions only before the play of the game; and 2) the TME with Communication device (TMECom) for the situation where team players can communicate their actions before the play of the game and during the game’s execution. The TME has some fascinating properties, e.g., it is unique in general, which can avoid the equilibrium selection problem. Moreover, TMEs can capture many realistic scenarios, including: 1) a team of players play against a target player in poker games; and 2) multiple defense resources schedule and patrol against the adversary in security games. Unfortunately, existing algorithms are inefficient to compute TMEs in large games. Therefore, in this thesis, we develop efficient algorithms to compute TMEs in normal-form and extensive-form games, including general algorithms and domain-specific algorithms for applications. First, we develop a novel incremental strategy generation algorithm to compute TMEs in normal-form games efficiently, which is the first incremental strategy generation algorithm guaranteeing to converge to a TME. Second, we apply the TME to a novel escape interdiction game model capturing the interaction between an escaping adversary and a team of multiple defense resources with correlated time-dependent strategies on transportation networks, and then we efficiently compute CTMEs in normal-form games for optimal escape interdiction on such networks with a domain-specific incremental strategy generation algorithm. Third, to efficiently solve the non-convex program for finding TMEs in extensive-form games, we develop a novel global optimization technique, the associated recursive asynchronous multiparametric disaggregation technique, to approximate multilinear terms in the non-convex program, and then we develop a corresponding novel iterative algorithm to compute TMEs within any given accuracy efficiently. Fourth, to efficiently compute TMEsCor in extensive-form games, we develop an incremental strategy generation algorithm converging within finite iterations in the infinite strategy space, where we develop a novel global optimization technique, the associated representation technique, to exactly represent multilinear terms in the best response oracle. Fifth, we apply the TME to a novel network pursuit game model capturing the interaction between an escaping adversary and a team of multiple defense resources who can communicate during the game’s execution on urban networks, and then we efficiently compute TMEsCom in extensive-form game for optimal interdiction of urban criminals with the aid of real-time information by a domain-specific incremental strategy generation algorithm. Finally, experimental results show that our general algorithms are orders of magnitude faster than prior state-of-the-art algorithms in large games, and our domain-specific algorithms can scale up to realistic problem sizes with hundreds of nodes on networks including the real network of Manhattan.