Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields. The winner of each battlefield is determined independently by a winnertakesall rule. The ultimate payoff for each colonel is the number of battlefields won. The Colonel Blotto game is commonly used for analyzing a wide range of applications from the U.S. Presidential election to innovative technology competitions to advertising, sports, and politics. There are persistent efforts to find the optimal strategies for the Colonel Blotto game. However, the first polynomialtime algorithm for that has very recently been provided by Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin. Their algorithm consists of an exponential size linear program (LP), which they solve using the ellipsoid method. Because of the use of the ellipsoid method, despite its significant theoretical importance, this algorithm is highly impractical. In general, even the simplex method (despite its exponential running time in practice) performs better than the ellipsoid method in practice. In this paper, we provide the first polynomialsize LP formulation of the optimal strategies for the Colonel Blotto game using linear extension techniques. Roughly speaking, we consider the natural representation of the strategy space polytope and transform it to a higher dimensional strategy space, which interestingly has exponentially fewer facets. In other words, we add a few variables to the LP such that, surprisingly, the number of constraints drops down to a polynomial. We use this polynomialsize LP to provide a simpler and significantly faster algorithm for finding optimal strategies of the Colonel Blotto game. We further show this representation is asymptotically tight, which means there exists no other linear representation of the strategy space with fewer constraints. We also extend our approach to multidimensional Colonel Blotto games, in which players may have different sorts of budgets, such as money, time, human resources, etc. By implementing this algorithm, we are able to run tests that were previously impossible to solve in a reasonable time. This information allows us to observe some interesting properties of Colonel Blotto; for example, we find out the behavior of players in the discrete model is very similar to the continuous model Roberson solved.more » « less

null (Ed.)We study the problem of fair allocation for indivisible goods. We use the maximin share paradigm introduced by Budish [Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.] as a measure of fairness. Kurokawa et al. [Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):8.] were the first to investigate this fundamental problem in the additive setting. They showed that in delicately constructed examples, not everyone can obtain a utility of at least her maximin value. They mitigated this impossibility result with a beautiful observation: no matter how the utility functions are made, we always can allocate the items to the agents to guarantee each agent’s utility is at least 2/3 of her maximin value. They left open whether this bound can be improved. Our main contribution answers this question in the affirmative. We improve their approximation result to a 3/4 factor guarantee.more » « less

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

null (Ed.)The edit distance between two strings is defined as the smallest number of insertions , deletions , and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [37]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an quantum algorithm that approximates the edit distance within a factor of 3. We further extend this result to an quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of , with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.more » « less

null (Ed.)Simulated annealing is an effective and general means of optimization. It is in fact inspired by metallurgy, where the temperature of a material determines its behavior in thermodynamics. Likewise, in simulated annealing, the actions that the algorithm takes depend entirely on the value of a variable which captures the notion of temperature. Typically, simulated annealing starts with a high temperature, which makes the algorithm pretty unpredictable, and gradually cools the temperature down to become more stable. A key component that plays a crucial role in the performance of simulated annealing is the criteria under which the temperature changes namely, the cooling schedule. Motivated by this, we study the following question in this work: "Given enough samples to the instances of a specific class of optimization problems, can we design optimal (or approximately optimal) cooling schedules that minimize the runtime or maximize the success rate of the algorithm on average when the underlying problem is drawn uniformly at random from the same class?" We provide positive results both in terms of sample complexity and simulation complexity. For sample complexity, we show that O (m^1/2) samples suffice to find an approximately optimal cooling schedule of length m. We complement this result by giving a lower bound of Ω (m^1/3) on the sample complexity of any learning algorithm that provides an almost optimal cooling schedule. These results are general and rely on no assumption. For simulation complexity, however, we make additional assumptions to measure the success rate of an algorithm. To this end, we introduce the monotone stationary graph that models the performance of simulated annealing. Based on this model, we present polynomial time algorithms with provable guarantees for the learning problem.more » « less

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