Saeed Seddighin

AAMAS Conference 2026 Conference Paper

Stackelberg Equilibria of Blotto Games

• Masoud Seddighin
• Saeed Seddighin

The Colonel Blotto game, introduced by Borel in 1921, models the allocation of a fixed budget of troops across multiple battlefields and is widely used in applications such as elections, innovation contests, advertising, and sports. While Nash equilibria in Blotto games can be computed in polynomial time despite the exponential strategy space, much less is known about (pure) Stackelberg equilibria. The best known result is a polynomial-time 2-approximation due to Behnezhad et al. (SODA’18). We improve this by giving a polynomial-time algorithm that computes Stackelberg strategies with approximation factor 1 +𝜖 for any constant 𝜖 > 0.

AIJ Journal 2024 Journal Article

Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem

• Masoud Seddighin
• Saeed Seddighin

In this work, we study the maximin share fairness notion ( MMS ) for allocation of indivisible goods in the subadditive and fractionally subadditive settings. While previous work refutes the possibility of obtaining an allocation which is better than 1/2-MMS, the only positive result for the subadditive setting states that when the number of items is equal to m, there always exists an Ω ( 1 / log ⁡ m ) -MMS allocation. Since the number of items may be larger than the number of agents (n), such a bound can only imply a weak bound of Ω ( 1 n log ⁡ n ) - MMS allocation in general. In this work, we improve this bound exponentially to Ω ( 1 log ⁡ n log ⁡ log ⁡ n ) -MMS guarantee. In addition to this, we prove that when the valuation functions are fractionally subadditive, a 0. 2192235-MMS allocation is guaranteed to exist. This also improves upon the previous bound of 1/5-MMS guarantee for the fractionally subadditive setting.

AIJ Journal 2022 Journal Article

Fair allocation of indivisible goods: Beyond additive valuations

• Mohammad Ghodsi
• MohammadTaghi Hajiaghayi
• Masoud Seddighin
• Saeed Seddighin
• Hadi Yami

We conduct a study on the problem of fair allocation of indivisible goods when maximin share [1] is used as the measure of fairness. Most of the current studies on this notion are limited to the case that the valuations are additive. In this paper, we go beyond additive valuations and consider the cases that the valuations are submodular, fractionally subadditive, and subadditive. We give constant approximation guarantees for agents with submodular and XOS valuations, and a logarithmic bound for the case of agents with subadditive valuations. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for submodular and XOS settings in polynomial time.

AAAI Conference 2022 Conference Paper

Improved Maximin Guarantees for Subadditive and Fractionally Subadditive Fair Allocation Problem

• Masoud Seddighin
• Saeed Seddighin

In this work, we study the maximin share fairness notion for allocation of indivisible goods in the subadditive and fractionally subadditive settings. While previous work refutes the possibility of obtaining an allocation which is better than 1/2-MMS, the only positive result for the subadditive setting states that when the number of items is equal to m, there always exists an Ω(1/ log m)-MMS allocation. Since the number of items may be larger than the number of agents (n), such a bound can only imply a weak bound of Ω( 1 n log n )-MMS allocation in general. In this work, we improve this gap exponentially to an Ω( 1 log n log log n )-MMS guarantee. In addition to this, we prove that when the valuation functions are fractionally subadditive, a 1/4. 6-MMS allocation is guaranteed to exist. This also improves upon the previous bound of 1/5-MMS guarantee for the fractionally subadditive setting.

AAAI Conference 2021 Conference Paper

Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable

• Sina Dehghani
• Hamed Saleh
• Saeed Seddighin
• Shang-Hua Teng

In the classical discrete Colonel Blotto game—introduced by Borel in 1921—two colonels simultaneously distribute their troops across multiple battlefields. The winner of each battlefield is determined by a winner-take-all rule, independently of other battlefields. In the original formulation, each colonel’s goal is to win as many battlefields as possible. The Blotto game and its extensions have been used in a wide range of applications from political campaign—exemplified by the U.S presidential election—to marketing campaign, from (innovative) technology competition to sports competition. Despite persistent efforts, efficient methods for finding the optimal strategies in Blotto games have been elusive for almost a century—due to exponential explosion in the organic solution space—until Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin developed the first polynomial-time algorithm for this fundamental gametheoretical problem in 2016. However, that breakthrough polynomial-time solution has some structural limitation. It applies only to the case where troops are homogeneous with respect to battlegruounds, as in Borel’s original formulation: For each battleground, the only factor that matters to the winner’s payoff is how many troops as opposed to which sets of troops are opposing one another in that battleground. In this paper, we consider a more general setting of the two-player-multi-battleground game, in which multifaceted resources (troops) may have different contributions to different battlegrounds. In the case of U.S presidential campaign, for example, one may interpret this as different types of resources—human, financial, political—that teams can invest in each state. We provide a complexity-theoretical evidence that, in contrast to Borel’s homogeneous setting, finding optimal strategies in multifaceted Colonel Blotto games is intractable. We complement this complexity result with a polynomial-time algorithm that finds approximately optimal strategies with provable guarantees. We also study a further generalization when two competitors do not have zerosum/ constant-sum payoffs. We show that optimal strategies in these two-player-multi-battleground games are as hard to compute and approximate as Nash equilibria in general noncooperative games and economic equilibria in exchange markets.

STOC Conference 2021 Conference Paper

Improved dynamic algorithms for longest increasing subsequence

• Tomasz Kociumaka
• Saeed Seddighin

SODA Conference 2021 Conference Paper

Improved Sublinear Time Algorithm for Longest Increasing Subsequence

• Michael Mitzenmacher
• Saeed Seddighin

We present a novel sublinear time algorithm for approximating LIS. If we denote the ratio of the solution size over the input size by λ, our approach yields an algorithm with an approximation factor of Ω( λ∊ ) for any constant ∊ > 0, and a truly sublinear runtime. This improves over for example the recent work of Rubinstein et al. [RSSS19] that approximates LIS within a factor Ω( λ 3 ) in truly sublinear time. Our work makes use of a grid packing technique recently introduced by Mitzenmacher and Seddighin to approximate LIS in the dynamic setting [MS20], providing another application for this technique.

TCS Journal 2020 Journal Article

Covering orthogonal polygons with sliding k-transmitters

• Salma Sadat Mahdavi
• Saeed Seddighin
• Mohammad Ghodsi

In this paper, we consider a new variant of covering in an orthogonal art gallery problem where each guard is a sliding k-transmitter. Such a guard can travel back and forth along an orthogonal line segment, say s, inside the polygon. A point p is covered by this guard if there exists a point q ∈ s such that p q ‾ is a line segment normal to s, and has at most k intersections with the boundary walls of the polygon. The objective is to minimize the sum of the lengths of the sliding k-transmitters to cover the entire polygon. In other words, the goal is to find the minimum total length of trajectories on which the guards can travel to cover the entire polygon. We prove that this problem is NP-hard when k = 2, and present a 2-approximation algorithm for any fixed k ≥ 2. The proposed algorithm also works well for an orthogonal polygon where the edges have thickness.

STOC Conference 2020 Conference Paper

Dynamic algorithms for LIS and distance to monotonicity

• Michael Mitzenmacher
• Saeed Seddighin

In this paper, we provide new approximation algorithms for dynamic variations of the longest increasing subsequence (LIS) problem, and the complementary distance to monotonicity (DTM) problem. In this setting, operations of the following form arrive sequentially: (i) add an element, (ii) remove an element, or (iii) substitute an element for another. At every point in time, the algorithm has an approximation to the longest increasing subsequence (or distance to monotonicity). We present a (1+є)-approximation algorithm for DTM with polylogarithmic worst-case update time and a constant factor approximation algorithm for LIS with worst-case update time Õ( n є ) for any constant є > 0.

SODA Conference 2020 Conference Paper

Improved Algorithms for Edit Distance and LCS: Beyond Worst Case

• Mahdi Boroujeni
• Masoud Seddighin
• Saeed Seddighin

Edit distance and longest common subsequence are among the most fundamental problems in combinatorial optimization. Recent developments have proven strong lower bounds against subquadratic time solutions for both problems. Moreover, the best approximation factors for subquadratic time solutions have been limited to 3 for edit distance and super constant for longest common subsequence. Improved approximation algorithms for these problems 1 are some of the biggest open questions in combinatorial optimization. In this work, we present improved algorithms for both edit distance and longest common subsequence. The running times are truly subquadratic, though we obtain 1 + o (1) approximate solutions for both problems if the input satisfies a mild condition. In this setting, first, an adversary chooses one of the input strings. Next, this string is perturbed by a random procedure, and then the adversary chooses the second string after observing the perturbed one.

STOC Conference 2019 Conference Paper

1+ ε approximation of tree edit distance in quadratic time

• Mahdi Boroujeni
• Mohammad Ghodsi
• MohammadTaghi Hajiaghayi
• Saeed Seddighin

Edit distance is one of the most fundamental problems in computer science. Tree edit distance is a natural generalization of edit distance to ordered rooted trees. Such a generalization extends the applications of edit distance to areas such as computational biology, structured data analysis (e.g., XML), image analysis, and compiler optimization. Perhaps the most notable application of tree edit distance is in the analysis of RNA molecules in computational biology where the secondary structure of RNA is typically represented as a rooted tree. The best-known solution for tree edit distance runs in cubic time. Recently, Bringmann et al. show that an O ( n 2.99 ) algorithm for weighted tree edit distance is unlikely by proving a conditional lower bound on the computational complexity of tree edit distance. This shows a substantial gap between the computational complexity of tree edit distance and that of edit distance for which a simple dynamic program solves the problem in quadratic time. In this work, we give the first non-trivial approximation algorithms for tree edit distance. Our main result is a quadratic time approximation scheme for tree edit distance that approximates the solution within a factor of 1+є for any constant є > 0.

SODA Conference 2019 Conference Paper

Approximating LCS in Linear Time: Beating the √n Barrier

• MohammadTaghi Hajiaghayi
• Masoud Seddighin
• Saeed Seddighin
• Xiaorui Sun

Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinformatics, revision control systems, and data comparison programs 1. Although a simple dynamic program computes LCS in quadratic time, it has been recently proven that the problem admits a conditional lower bound and may not be solved in truly subquadratic time [2]. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains a n x approximation solution in time O ( n 2–2 x ) nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance for which several linear time solutions are obtained in the past two decades [4, 5, 9, 10, 16]. In this work, we present the first nontrivial algorithm for approximating LCS in linear time. Our main result is a linear time algorithm for the longest common subsequence which has an approximation factor of O ( n 0. 497956 ). This beats the barrier for approximating LCS in linear time.

FOCS Conference 2019 Conference Paper

Approximation Algorithms for LCS and LIS with Truly Improved Running Times

• Aviad Rubinstein
• Saeed Seddighin
• Zhao Song 0002
• Xiaorui Sun

Longest common subsequence (LCS) is a classic and central problem in combinatorial optimization. While LCS admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible in truly subquadratic time. A special case of LCS wherein each character appears at most once in every string is equivalent to the longest increasing subsequence problem (LIS) which can be solved in quasilinear time. In this work, we present novel algorithms for approximating LCS in truly subquadratic time and LIS in truly sublinear time. Our approximation factors depend on the ratio of the optimal solution size over the input size. We denote this ratio by λ and obtain the following results for LCS and LIS without any prior knowledge of λ. • A truly subquadratic time algorithm for LCS with approximation factor O(λ^3). • A truly sublinear time algorithm for LIS with approximation factor O(λ^3). Triangle inequality was recently used by Boroujeni et al. [1] and Chakraborty et al. [2] to present new approximation algorithms for edit distance. Our techniques for LCS extend the notion of triangle inequality to non-metric settings.

JAIR Journal 2019 Journal Article

Fair Allocation of Indivisible Goods to Asymmetric Agents

• Alireza Farhadi
• Mohammad Ghodsi
• Mohammad Taghi Hajiaghayi
• Sébastien Lahaie
• David Pennock
• Masoud Seddighin
• Saeed Seddighin
• Hadi Yami

We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.

SODA Conference 2019 Conference Paper

Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence

• MohammadTaghi Hajiaghayi
• Saeed Seddighin
• Xiaorui Sun

SODA Conference 2018 Conference Paper

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

• Mahdi Boroujeni
• Soheil Ehsani
• Mohammad Ghodsi
• MohammadTaghi Hajiaghayi
• Saeed Seddighin

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” [21]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O ( n 1. 858 ) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O ( n 1. 781 ) 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 3, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

STOC Conference 2018 Conference Paper

Fast algorithms for knapsack via convolution and prediction

• MohammadHossein Bateni
• MohammadTaghi Hajiaghayi
• Saeed Seddighin
• Cliff Stein 0001

The knapsack problem is a fundamental problem in combinatorial optimization. It has been studied extensively from theoretical as well as practical perspectives as it is one of the most well-known NP-hard problems. The goal is to pack a knapsack of size t with the maximum value from a collection of n items with given sizes and values. Recent evidence suggests that a classic O ( nt ) dynamic-programming solution for the knapsack problem might be the fastest in the worst case. In fact, solving the knapsack problem was shown to be computationally equivalent to the (min, +) convolution problem, which is thought to be facing a quadratic-time barrier. This hardness is in contrast to the more famous (+, ·) convolution (generally known as polynomial multiplication), that has an O ( n log n )-time solution via Fast Fourier Transform. Our main results are algorithms with near-linear running times (in terms of the size of the knapsack and the number of items) for the knapsack problem, if either the values or sizes of items are small integers. More specifically, if item sizes are integers bounded by, the running time of our algorithm is Õ(( n + t )). If the item values are integers bounded by, our algorithm runs in time Õ( n + t ). Best previously known running times were O ( nt ), O ( n 2 ) and O ( n ) (Pisinger, J. of Alg., 1999). At the core of our algorithms lies the prediction technique: Roughly speaking, this new technique enables us to compute the convolution of two vectors in time ( n ) when an approximation of the solution within an additive error of is available. Our results also improve the best known strongly polynomial time solutions for knapsack. In the limited size setting, when the items have multiplicities, the fastest strongly polynomial time algorithms for knapsack run in time O ( n 2 2 ) and O ( n 3 2 ) for the cases of infinite and given multiplicities, respectively. Our results improve both running times by a factor of ( n max{1, n /}).

SODA Conference 2018 Conference Paper

From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games

• Soheil Behnezhad
• Avrim Blum
• Mahsa Derakhshan
• MohammadTaghi Hajiaghayi
• Mohammad Mahdian
• Christos H. Papadimitriou
• Ronald L. Rivest
• Saeed Seddighin

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 well-studied 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.

AAAI Conference 2017 Conference Paper

A Study of Compact Reserve Pricing Languages

• MohammadHossein Bateni
• Hossein Esfandiary
• Vahab Mirrokni
• Saeed Seddighin

Online advertising allows advertisers to implement fine-tuned targeting of users. While such precise targeting leads to more effective advertising, it introduces challenging multidimensional pricing and bidding problems for publishers and advertisers. In this context, advertisers and publishers need to deal with an exponential number of possibilities. As a result, designing efficient and compact multidimensional bidding and pricing systems and algorithms are practically important for online advertisement. Compact bidding languages have already been studied in the context of multiplicative bidding. In this paper, we study the compact pricing problem. More specifically, we first define the multiplicative reserve price optimization problem (MRPOP) and show that unlike the unrestricted reserve price system, it is NP-hard to find the best reserve price solution in this setting. Next, we present an efficient algorithm to compute a solution for MRPOP that achieves a logarithmic approximation of the optimum solution of the unrestricted setting, where we can set a reserve price for each individual impression type (i. e. , one element in the Cartesian product of all features). We do so by characterizing the properties of an optimum solution. Furthermore, our empirical study confirms the effectiveness of multiplicative pricing in practice. In fact, the simulations show that our algorithm obtains 90–98% of the value of the best solution that sets the reserve prices for each auction individually (i. e. , the optimum set of reserve prices). Finally, in order to establish the tightness of our results in the adversarial setting, we demonstrate that there is no compact pricing system (i. e. , a pricing system using O(n1− ) bits to set n reserve prices) that loses, in the worst case, less than a logarithmic factor compared to the optimum set of reserve prices. Notice that this hardness result is not restricted to the multiplicative setting and holds for any compact pricing system. In summary, not only does the multiplicative reserve price system show great promise in our empirical study, but it is also theoretically optimal up to a constant factor in the adversarial setting. ∗ Supported in part by NSF CAREER award CCF-1053605, NSF BIGDATA grant IIS-1546108, NSF AF: Medium grant CCF- 1161365, DARPA GRAPHS/AFOSR grant FA9550-12-1-0423, and another DARPA SIMPLEX grant. Copyright c 2017, Association for the Advancement of Artificial Intelligence (www. aaai. org). All rights reserved.

AAMAS Conference 2017 Conference Paper

Fair Allocation of Indivisible Goods with Different Entitlements

• Alireza Farhadi
• MohammadTaghi Hajiaghayi
• Mohammad Ghodsi
• Sebastien Lahaie
• David Pennock
• Masoud Seddighin
• Saeed Seddighin
• Hadi Yami

We study fair allocation of indivisible goods to agents with unequal entitlements. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang [14] wherein the agents are assumed to be symmetric. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Next, we assume that the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. We show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items. (The full version of the paper is available in https: //arxiv. org/abs/1703. 01649.) CCS Concepts •Computing methodologies → Multi-agent systems;

AAAI Conference 2017 Conference Paper

Faster and Simpler Algorithm for Optimal Strategies of Blotto Game

• Soheil Behnezhad
• Sina Dehghani
• Mahsa Derakhshan
• MohammadTaghi Hajiaghayi
• Saeed Seddighin

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 battle- field is determined independently by a winner-take-all rule. The ultimate payoff of each colonel is the number of battlefields he wins. This game is commonly used for analyzing a wide range of applications such as the U. S presidential election, innovative technology competitions, advertisements, etc. There have been persistent efforts for finding the optimal strategies for the Colonel Blotto game. After almost a century Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin provided a poly-time algorithm for finding the optimal strategies. They first model the problem by a Linear Program (LP) with exponential number of constraints and use Ellipsoid method to solve it. However, despite the theoretical importance of their algorithm, it is highly impractical. In general, even Simplex method (despite its exponential running-time) performs better than Ellipsoid method in practice. In this paper, we provide the first polynomial-size LP formulation of the optimal strategies for the Colonel Blotto game. We use linear extension techniques. Roughly speaking, we project the strategy space polytope to a higher dimensional space, which results in a lower number of facets for the polytope. We use this polynomial-size LP to provide a novel, simpler and significantly faster algorithm for finding the optimal strategies for the Colonel Blotto game. We further show this representation is asymptotically tight in terms of the number of constraints. We also extend our approach to multi-dimensional Colonel Blotto games, and implement our algorithm to observe interesting properties of Colonel Blotto; for example, we observe the behavior of players in the discrete model is very similar to the previously studied continuous model.

AAAI Conference 2016 Conference Paper

From Duels to Battlefields: Computing Equilibria of Blotto and Other Games

• AmirMahdi Ahmadinejad
• Sina Dehghani
• MohammadTaghi Hajiaghay
• Brendan Lucier
• Hamid Mahini
• Saeed Seddighin

We study the problem of computing Nash equilibria of zerosum games. Many natural zero-sum games have exponentially many strategies, but highly structured payoffs. For example, in the well-studied Colonel Blotto game (introduced by Borel in 1921), players must divide a pool of troops among a set of battlefields with the goal of winning (i. e. , having more troops in) a majority. 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 advertisement, to sports. However, because of the size of the strategy space, standard methods for computing equilibria of zero-sum games fail to be computationally feasible. Indeed, despite its importance, only few solutions for special variants of the problem are known. In this paper we show how to compute equilibria of Colonel Blotto games. Moreover, our approach takes the form of a general reduction: to find a Nash equilibrium of a zero-sum game, it suffices to design a separation oracle for the strategy polytope of any bilinear game that is payoff-equivalent. We then apply this technique to obtain the first polytime algorithms for a variety of games. In addition to Colonel Blotto, we also show how to compute equilibria in an infinite-strategy variant called the General Lotto game; this involves showing how to prune the strategy space to a finite subset before applying our reduction. We also consider the class of dueling games, first introduced by Immorlica et al. (2011). We show that our approach provably extends the class of dueling games for which equilibria can be computed: we introduce a new dueling game, the matching duel, on which prior methods fail to be computationally feasible but upon which our reduction can be applied.