 Award ID(s):
 2114269
 NSFPAR ID:
 10325844
 Date Published:
 Journal Name:
 Operations Research
 ISSN:
 0030364X
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

In the classical discrete Colonel Blotto game—introducedby Borel in 1921—two colonels simultaneously distributetheir troops across multiple battlefields. The winner of eachbattlefield is determined by a winnertakeall rule, independentlyof other battlefields. In the original formulation, eachcolonel’s goal is to win as many battlefields as possible. TheBlotto game and its extensions have been used in a widerange of applications from political campaign—exemplifiedby the U.S presidential election—to marketing campaign,from (innovative) technology competition to sports competition.Despite persistent efforts, efficient methods for findingthe optimal strategies in Blotto games have been elusivefor almost a century—due to exponential explosion inthe organic solution space—until Ahmadinejad, Dehghani,Hajiaghayi, Lucier, Mahini, and Seddighin developed thefirst polynomialtime algorithm for this fundamental gametheoreticalproblem in 2016. However, that breakthroughpolynomialtime solution has some structural limitation. Itapplies only to the case where troops are homogeneous withrespect to battlegruounds, as in Borel’s original formulation:For each battleground, the only factor that matters to the winner’spayoff is how many troops as opposed to which sets oftroops are opposing one another in that battleground.In this paper, we consider a more general setting of thetwoplayermultibattleground game, in which multifacetedresources (troops) may have different contributions to differentbattlegrounds. In the case of U.S presidential campaign,for example, one may interpret this as different typesof resources—human, financial, political—that teams can investin each state. We provide a complexitytheoretical evidencethat, in contrast to Borel’s homogeneous setting, findingoptimal strategies in multifaceted Colonel Blotto gamesis intractable. We complement this complexity result witha polynomialtime algorithm that finds approximately optimalstrategies with provable guarantees. We also study a furthergeneralization when two competitors do not have zerosum/constantsum payoffs. We show that optimal strategiesin these twoplayermultibattleground games are as hard tocompute and approximate as Nash equilibria in general noncooperative games and economic equilibria in exchange markets.more » « less

Although security games have attracted intensive research attention over the past years, few existing works consider how information from local communities would affect the game. In this paper, we introduce a new player  a strategic informant, who can observe and report upcoming attacks  to the defenderattacker security game setting. Characterized by a private type, the informant has his utility structure that leads to his strategic behaviors. We model the game as a 3player extensiveform game and propose a novel solution concept of Strong Stackelbergperfect Bayesian equilibrium. To compute the optimal defender strategy, we first show that although the informant can have infinitely many types in general, the optimal defense plan can only include a finite (exponential) number of different patrol strategies. We then prove that there exists a defense plan with only a linear number of patrol strategies that achieve the optimal defender's utility, which significantly reduces the computational burden and allows us to solve the game in polynomial time using linear programming. Finally, we conduct extensive experiments to show the effect of the strategic informant and demonstrate the effectiveness of our algorithm.

Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u,p)maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a (u, p)maxmin strategy for these games. The first game that we consider is Colonel Blotto, a wellstudied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battlefields. Each battlefield is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battlefields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players’ goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding (u, p)maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for (u, p)maxmin strategies.more » « less

We consider partiallyspecified optimization problems where the goal is to actively, but efficiently, acquire missing information about the problem in order to solve it. An algo rithm designer wishes to solve a linear pro gram (LP), maxcT x s.t. Ax ≤ b,x ≥ 0, but does not initially know some of the pa rameters. The algorithm can iteratively choose an unknown parameter and gather information in the form of a noisy sample centered at the parameter’s (unknown) value. The goal is to find an approximately feasible and optimal so lution to the underlying LP with high proba bility while drawing a small number of sam ples. We focus on two cases. (1) When the parameters b of the constraints are initially un known, we propose an efficient algorithm com bining techniques from the ellipsoid method for LP and confidencebound approaches from bandit algorithms. The algorithm adaptively gathers information about constraints only as needed in order to make progress. We give sample complexity bounds for the algorithm and demonstrate its improvement over a naive approach via simulation. (2) When the param eters c of the objective are initially unknown, we take an informationtheoretic approach and give roughly matching upper and lower sam ple complexity bounds, with an (inefficient) successiveelimination algorithm.more » « less

We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower’s optimization problem. The objective, from the attacker’s viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower’s subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 01 knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of generalpurpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cuttingplanes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 01 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems.more » « less