PhD Proposal: Algorithms for Huge Constant-Sum Games

Game theory is about selfish rational agents who strive to maximize their own payoffs, which in the case of constant-sum two-player games, is offset by the other player's loss. If the number of possible strategies of the players in such games is small (i.e., bounded by a polynomial), standard algorithmic approaches can be used to obtain optimal (i.e., maximin) strategies in polynomial time. In most natural games of interest, however, players have deeply structured, but exponentially many strategies. We consider a number of such succinct games and propose algorithms that exploit these combinatorial structures to find optimal — or approximately optimal — strategies in polynomial time.Spatio-temporal security games are a class of games in which the goal is to protect a set of valuable mobile targets from an adversary. This is a critical international concern with far-reaching applications, including, e.g., wildlife protection, border protection, etc. Security games cast these issues as two-player games between a defender and an attacker. The defender has a limited number of patrols and has to specify a time-dependent patrolling strategy over a spatial domain to protect the targets against an attacker who strives to inflict damage on them. We first study this problem in a one-dimensional space and give polynomial time algorithms for finding the maximin strategy of the defender. As an extension, we propose a new model for targets moving on a two-dimensional space and give approximation algorithms for that. The Colonel Blotto game, first introduced by Borel in 1921, is a well-studied game theory classic. Two colonels each have a pool of troops that they divide simultaneously among a set of battlefields. The winner of each battlefield is the colonel who puts more troops in it and the overall utility of each colonel is the sum of weights of the battlefields that she wins. Over the past century, the Colonel Blotto game has found applications in many different forms of competition from advertisements to politics to sports. In the literature, the main objective that is considered for this game is maximizing the guaranteed expected payoff. This corresponds to the conventional utility maximization. We also propose another natural objective which is to maximize the probability of obtaining a minimum payoff. This concerns scenarios such as elections where the candidates' goal is to maximize the probability of getting at least half of the votes (rather than the expected number of votes). We consider both of these objectives and show how it is possible to obtain (almost) optimal solutions in both cases.

Examining Committee:

Chair: Dr. MohammadTaghi Hajiaghayi Dept. rep: Dr. John Dickerson Members: Dr. David Mount Dr. Alexander Slivkins