Arrow Research search

Author name cluster

Soheil Behnezhad

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

32 papers
2 author rows

Possible papers

32

ICML Conference 2025 Conference Paper

Correlation Clustering Beyond the Pivot Algorithm

  • Soheil Behnezhad
  • Moses Charikar
  • Vincent Cohen-Addad
  • Alma Ghafari
  • Weiyun Ma

We study the classic correlation clustering problem. Given $n$ objects and a complete labeling of the object-pairs as either “similar” or “dissimilar”, the goal is to partition the objects into arbitrarily many clusters while minimizing disagreements with the labels. A classic Pivot algorithm for this problem, due to [Ailon et al STOC’05], obtains a 3-approximation for this problem. Over the years, this algorithm has been successfully implemented in various settings. The downside of the Pivot algorithm is that the approximation analysis of 3 is tight for it. While better approximations have been achieved in some settings, these algorithms are often hard to implement in various settings. For example, [Behnezhad et al FOCS19] showed that the output of Pivot can be maintained in polylog time per update in a dynamic setting, a bound that was improved to constant by [Dalirrooyfard et al ICML’24]. But obtaining a better approximation remains open. In this paper, we present Modified Pivot, an algorithm that locally improves the output of Pivot. Our Modified Pivot algorithm can be implemented just as efficiently as Pivot in various settings. Our experiments show that the output of Modified Pivot on average makes less than 77% of the mistakes made by Pivot. More surprisingly, we prove theoretically that Modified Pivot has approximation ratio $3-\epsilon_0$ for some absolute constant $\epsilon_0 > 0$. This, e. g. , leads to a better than 3 approximation in the dynamic setting in polylog time, improving the 3-approximation obtained by [Behnezhad et al FOCS’19] and [Dalirrooyfard et al ICML’24].

Details

FOCS Conference 2025 Conference Paper

Lower Bounds for Non-adaptive Local Computation Algorithms

  • Amir Azarmehr
  • Soheil Behnezhad
  • Alma Ghafari
  • Madhu Sudan 0001

We study non-adaptive Local Computation Algorithms (LCA). A reduction of Parnas and Ron (TCS’07) turns any distributed algorithm into a non-adaptive LCA. Plugging known distributed algorithms, this leads to non-adaptive LCAs for constant approximations of maximum matching (MM) and minimum vertex cover (MVC) with complexity $\Delta^{O(\log \Delta / \log \log \Delta)}$, where $\Delta$ is the maximum degree of the graph. Allowing adaptivity, this bound can be significantly improved to $\operatorname{poly}(\Delta)$, but is such a gap necessary or are there better non-adaptive LCAs? Adaptivity as a resource has been studied extensively across various areas. Beyond this, we further motivate the study of non-adaptive LCAs by showing that even a modest improvement over the Parnas-Ron bound for the MVC problem would have major implications in the Massively Parallel Computation (MPC) setting. In particular, it would lead to faster truly sublinear space MPC algorithms for approximate MM, a major open problem of the area. Our main result is a lower bound that rules out this avenue for progress. Specifically, we prove that $\Delta^{\Omega(\log \Delta / \log \log \Delta)}$ queries are needed for any non-adaptive LCA computing a constant approximation of MM or MVC. This is the first separation between non-adaptive and adaptive LCAs, and already matches (up to constants in the exponent) the algorithm obtained by the black-box reduction of Parnas and Ron. Our proof blends techniques from two separate lines of work: sublinear time lower bounds and distributed lower bounds. Particularly, we adopt techniques such as couplings over acyclic subgraphs from the recent sublinear time lower bounds of Behnezhad, Roghani, and Rubinstein (STOC’23, FOCS’23, STOC’24). We apply these techniques on a very different instance, particularly (a modified version of) the construction of Kuhn, Moscibroda and Wattenhoffer (JACM’16) from distributed computing. Our proof reveals that the (modified) KMW instance has the rather surprising property that any random walk of any length has a tiny chance $\left(\Delta^{-\Omega(\log \Delta / \log \log \Delta)}\right)$ of identifying a matching edge. In contrast, the work of KMW only proves that short walks (i. e. , walks of depth $O(\log \Delta / \log \log \Delta)$) are not useful.

Details

FOCS Conference 2025 Conference Paper

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance

  • Amir Azarmehr
  • Soheil Behnezhad
  • Mohammad Roghani
  • Aviad Rubinstein

How many adjacency matrix queries (also known as pair queries) are required to estimate the size of a maximum matching in an n-vertex graph G? We study this fundamental question in this paper. On the upper bound side, an algorithm of Bhattacharya, Kiss, and Saranurak [FOCS’23] gives an estimate that is within $\varepsilon n$ of the right bound with $n^{2-\Omega_{\varepsilon}(1)}$ queries, which is subquadratic in n (and thus sublinear in the matrix size) for any fixed $\varepsilon\gt0$. On the lower bound side, while there has been a lot of progress in the adjacency list model, no non-trivial lower bound has been established for algorithms with adjacency matrix query access. In particular, the only known lower bound is a folklore bound of $\Omega(n)$, leaving a huge gap. In this paper, we present the first superlinear in n lower bound for this problem. In fact, we close the gap mentioned above entirely by showing that the algorithm of [BKS’23] is optimal. Formally, we prove that for any fixed $\delta\gt0$, there is a fixed $\varepsilon\gt0$ such that an estimate that is within $\varepsilon n$ of the true bound requires $\Omega\left(n^{2-\delta}\right)$ adjacency matrix queries. Our lower bound also has strong implications for estimating the earth mover’s distance between distributions. For this problem, Beretta and Rubinstein [STOC’24] gave an $n^{2-\Omega_{\varepsilon}(1)}$ time algorithm that obtains an additive $\varepsilon$-approximation and works for any distance function. Whether this can be improved generally, or even for metric spaces, had remained open. Our lower bound rules out the possibility of any improvements over this bound, even under the strong assumption that the underlying distances are in a (1, 2)-metric.

Details

ICML Conference 2024 Conference Paper

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS

  • Amir Azarmehr
  • Soheil Behnezhad
  • Mohammad Roghani

Maximum matching is one of the most fundamental combinatorial optimization problems with applications in various contexts such as balanced clustering, data mining, resource allocation, and online advertisement. In many of these applications, the input graph is massive. The sheer size of these inputs makes it impossible to store the whole graph in the memory of a single machine and process it there. Graph sparsification has been an extremely powerful tool to alleviate this problem. In this paper, we study a highly successful and versatile sparsifier for the matching problem: the edge-degree constrained subgraph (EDCS) introduced first by Bernstein & Stein 2015 The EDCS has a parameter $\beta \geq 2$ which controls the density of the sparsifier. It has been shown through various proofs in the literature that by picking a subgraph with $O(n\beta)$ edges, the EDCS includes a matching of size at least $2/3-O(1/\beta)$ times the maximum matching size. As such, by increasing $\beta$ the approximation ratio of EDCS gets closer and closer to $2/3$. In this paper, we propose a new approach for analyzing the approximation ratio of EDCS. Our analysis is tight for any value of $\beta$. Namely, we pinpoint the precise approximation ratio of EDCS for any sparsity parameter $\beta$. Our analysis reveals that one does not necessarily need to increase $\beta$ to improve approximation, as suggested by previous analysis. In particular, the best choice turns out to be $\beta = 6$, which achieves an approximation ratio of $. 677$! This is arguably surprising as it is even better than $2/3 \sim. 666$, the bound that was widely believed to be the limit for EDCS.

Details

FOCS Conference 2024 Conference Paper

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs

  • Soheil Behnezhad
  • Alma Ghafari

We study the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge insertions and deletions. Our focus is particularly on algorithms that maintain the edges of a $(1-\varepsilon)$ -approximate maximum matching for an arbitrarily small constant $\varepsilon > 0$. Until recently, the fastest known algorithm for this problem required $\Theta(n)$ time per update where $n$ is the number of vertices. This bound was slightly improved to $n/(\log^{\ast}n)^{\Omega(1)}$ by Assadi, Behnezhad, Khanna, and Li [STOC'23] and very recently to $n/2_{-}^{\Omega(\sqrt{\log n})}$ by Liu [FOCS'24]. Whether this can be improved to $n^{1-\Omega(1)}$ remains a major open problem. In this paper, we introduce Ordered Ruzsa-Szemerédi (ORS) graphs (a generalization of Ruzsa-Szemerédi graphs) and show that the complexity of dynamic matching is closely tied to them. For $\delta > 0$, define ORS $(\delta n)$ to be the maximum number of matchings $M_{1}, \ldots, 1M_{t}$, each of size $\delta n$, that one can pack in an n-vertex graph such that each matching $M_{i}$ is an induced matching in subgraph $M_{1}\cup\ldots\cup M_{i}$. We show that there is a randomized algorithm that maintains a $(1-\varepsilon)$ -approximate maximum matching of a fully dynamic graph in amortized update-time. While the value of $\text{ORS}(\Theta(n))$ remains unknown and is only upper bounded by $n^{1-o(1)}$, the densest construction known from more than two decades ago only achieves $ORS (\Theta(n))\geq n^{1/\Theta(\log\log n)}=n^{o(1)}$ [Fischer et al. STOC'02]. If this is close to the right bound, then our algorithm achieves an update-time of $\sqrt{n^{1+O(\varepsilon)}}^{-}$, resolving the aforementioned longstanding open problem in dynamic algorithms in a strong sense.

Details

FOCS Conference 2023 Conference Paper

Local Computation Algorithms for Maximum Matching: New Lower Bounds

  • Soheil Behnezhad
  • Mohammad Roghani
  • Aviad Rubinstein

We study local computation algorithms (LCA) for maximum matching. An LCA does not return its output entirely, but reveals parts of it upon query. For matchings, each query is a vertex v; the LCA should return whether v is matched—and if so to which neighbor—while spending a small time per query. In this paper, we prove that any LCA that computes a matching that is at most an additive of $\epsilon n$ smaller than the maximum matching in n-vertex graphs of maximum degree $\Delta$ must take at least $\Delta^{\Omega(1 / \varepsilon)}$ time. This comes close to the existing upper bounds that take $(\Delta / \epsilon)^{O\left(1 / \epsilon^{2}\right)} \operatorname{polylog}(n)$ time. In terms of sublinear time algorithms, our techniques imply that any algorithm that estimates the size of maximum matching up to an additive error of $\epsilon n$ must take $\Delta^{\Omega(1 / \epsilon)}$ time. This negatively resolves a decade old open problem of the area (see Open Problem 39 of sublinear. info) on whether such estimates can be achieved in $\operatorname{poly}(\Delta / \epsilon)$ time.

Details

STOC Conference 2023 Conference Paper

Sublinear Time Algorithms and Complexity of Approximate Maximum Matching

  • Soheil Behnezhad
  • Mohammad Roghani
  • Aviad Rubinstein

Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. For instance, an algorithm of [Behnezhad; FOCS’21] obtains a 1/2-approximation in O ( n ) time for n -vertex graphs. A more recent algorithm by [Behnezhad, Roghani, Rubinstein, and Saberi; SODA’23] obtains a slightly-better-than-1/2 approximation in O ( n 1+є ) time (for arbitrarily small constant ε>0). On the lower bound side, [Parnas and Ron; TCS’07] showed 15 years ago that obtaining any constant approximation of maximum matching size requires Ω( n ) time. Proving any super-linear in n lower bound, even for (1−є)-approximations, has remained elusive since then. In this paper, we prove the first super-linear in n lower bound for this problem. We show that at least n 1.2 − o (1) queries in the adjacency list model are needed for obtaining a (2/3 + Ω(1))-approximation of the maximum matching size. This holds even if the graph is bipartite and is promised to have a matching of size Θ( n ). Our lower bound argument builds on techniques such as correlation decay that to our knowledge have not been used before in proving sublinear time lower bounds. We complement our lower bound by presenting two algorithms that run in strongly sublinear time of n 2−Ω(1) . The first algorithm achieves a (2/3−ε)-approximation (for any arbitrarily small constant ε>0); this significantly improves prior close-to-1/2 approximations. Our second algorithm obtains an even better approximation factor of (2/3+Ω(1)) for bipartite graphs. This breaks 2/3-approximation which has been a barrier in various settings of the matching problem, and importantly shows that our n 1.2− o (1) time lower bound for (2/3+Ω(1))-approximations cannot be improved all the way to n 2− o (1) .

Details

FOCS Conference 2022 Conference Paper

Almost 3-Approximate Correlation Clustering in Constant Rounds

  • Soheil Behnezhad
  • Moses Charikar
  • Weiyun Ma
  • Li-Yang Tan

We study parallel algorithms for correlation clustering. Each pair among n objects is labeled as either “similar” or “dissimilar”. The goal is to partition the objects into arbitrarily many clusters while minimizing the number of disagreements with the labels. Our main result is an algorithm that for any $\varepsilon>0$ obtains a (3 + $\varepsilon$)-approximation in $O(1/\varepsilon$) rounds (of models such as massively parallel computation, local, and semi-streaming). This is a culminating point for the rich literature on parallel correlation clustering. On the one hand, the approximation (almost) matches a natural barrier of 3 for combinatorial algorithms. On the other hand, the algorithm’s round-complexity is essentially constant. To achieve this result, we introduce a simple $O(1/\varepsilon$)-round parallel algorithm. Our main result is to provide an analysis of this algorithm, showing that it achieves a (3 + $\varepsilon$)-approximation. Our analysis draws on new connections to sublinear-time algorithms. Specifically, it builds on the work of Yoshida, Yamamoto, and Ito [1] on bounding the “query complexity” of greedy maximal independent set. To our knowledge, this is the first application of this method in analyzing the approximation ratio of any algorithm. Full version. Due to the page limit, this version of the paper does not include all the proofs. The full version of the paper is available at [2].

Details

FOCS Conference 2021 Conference Paper

Time-Optimal Sublinear Algorithms for Matching and Vertex Cover

  • Soheil Behnezhad

We study the problem of estimating the size of maximum matching and minimum vertex cover in sub linear time. Denoting the number of vertices by $n$ and the average degree in the graph by $\overline{d}$, we obtain the following results for both problems which are all provably time-optimal up to polylogarithmic factors: 1 1 The $\tilde{O}(\cdot)$ notation hides polylog $n$ factors throughout the paper. •A multiplicative $(2+\varepsilon)$ -approximation that takes $\tilde{O}(n/\varepsilon^{2})$ time using adjacency list queries. •A multiplicative-additive $(2, \ \varepsilon n)$ -approximation that takes $\tilde{O}((\overline{d}+1)/\varepsilon^{2})$ time using adjacency list queries. •A multiplicative-additive $(2, \ \varepsilon n)$ -approximation that takes $\tilde{O}(n/\varepsilon^{3})$ time using adjacency matrix queries. Our main contribution and the key ingredient of the bounds above is a near-tight analysis of the average query complexity of randomized greedy maximal matching which improves upon a seminal result of Yoshida, Yamamoto, and Ito $[\text{STOC}^{\prime} 09]$.

Details

STOC Conference 2020 Conference Paper

Stochastic matching with few queries: (1-ε) approximation

  • Soheil Behnezhad
  • Mahsa Derakhshan
  • MohammadTaghi Hajiaghayi

Suppose that we are given an arbitrary graph G =( V , E ) and know that each edge in E is going to be realized independently with some probability p . The goal in the stochastic matching problem is to pick a sparse subgraph Q of G such that the realized edges in Q , in expectation, include a matching that is approximately as large as the maximum matching among the realized edges of G . The maximum degree of Q can depend on p , but not on the size of G . This problem has been subject to extensive studies over the years and the approximation factor has been improved gradually from 0.5 to eventually 2/3 which is a known barrier. In this work, we analyze a natural sampling-based algorithm and show that it can obtain a (1−є) approximation, for any constant є > 0. A key and of possible independent interest component of our analysis is an algorithm that constructs a matching on a stochastic graph, which among some other important properties, guarantees that each vertex is matched independently from the vertices that are sufficiently far. This allows us to bypass a previously known barrier towards achieving (1−є) approximation based on existence of dense Ruzsa-Szemerédi graphs.

Details

FOCS Conference 2020 Conference Paper

Stochastic Weighted Matching: (Stochastic Weighted Matching: (1-ε) Approximation -\varepsilon$) Approximation

  • Soheil Behnezhad
  • Mahsa Derakhshan

Let $G= (V, E)$ be a given edge-weighted graph and let its realization $\mathcal{G}$ be a random subgraph of $G$ that includes each edge $e\in E$ independently with probability $p$. We study a stochastic matching problem where the goal is to non-adaptively pick a sparse subgraph $Q$ of $G$ (without knowing the realization $\mathcal{G}$ ), such that the maximum weight matching among the realized edges of $Q$ (i. e. graph $Q\cap \mathcal{G}$ ) in expectation approximates the maximum weight matching of the whole realization $\mathcal{G}$. In this paper, we prove that for any $\varepsilon\in(0, 1)$, every graph $G$ has a subgraph $Q$ that has maximum degree only $O_{\varepsilon, p}(1)$ and guarantees a ( $1-\varepsilon$ ) -approximation. That is, the maximum degree of $Q$ depends only on $\varepsilon$ and $p$ (both of which are known to be necessary) and not for example on the number of nodes in $G$, the edge-weights, etc. The stochastic matching problem has been studied extensively on both weighted and unweighted graphs. Previously, only existence of (close to) half-approximate subgraphs was known for weighted graphs [Yamaguchi and Maehara, SODA'18; Behnezhad et al. , SODA'19]. Our result substantially improves over these works, matches the state-of-the-art for unweighted graphs [Behnezhad et al. , STOC'20], and settles the approximation factor.

Details

FOCS Conference 2019 Conference Paper

Exponentially Faster Massively Parallel Maximal Matching

  • Soheil Behnezhad
  • MohammadTaghi Hajiaghayi
  • David G. Harris 0001

The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, however, we still have a far more limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximal matching either take polylogarithmic time which is considered inefficient, or require a strictly super-linear space of n1+ (1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm. This affirmatively resolves the conjecture of Czumaj et al. [STOC’18] that a variant of this algorithm might work. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition. We show that this algorithm drastically reduces the vertex degrees. This, among some other results, leads to an O(log log ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space. This is the best possible approximation factor under standard assumptions, culminating a long line of research. It also leads to an improved O(log log ) round algorithm for 1+" approximate matching. All these results can also be implemented in the congested clique model within the same number of rounds.

Details

FOCS Conference 2019 Conference Paper

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time

  • Soheil Behnezhad
  • Mahsa Derakhshan
  • MohammadTaghi Hajiaghayi
  • Cliff Stein 0001
  • Madhu Sudan 0001

We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph-which undergoes both edge insertions and deletions-in polylogarithmic time. Our algorithm is randomized and, per update, takes O(log 2 Δ log 2 n) expected time. Furthermore, the algorithm can be adjusted to have O(log 2 Δ log 4 n) worst-case update-time with high probability. Here, n denotes the number of vertices and Δ is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC'18] who presented an algorithm with O(m 3/4 ) update-time (and thus broke the natural Ω(m) barrier) where m denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had Õ(min{√n, m 1/3 }) update-time [Assadi et al. SODA'19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.

Details

FOCS Conference 2019 Conference Paper

Near-Optimal Massively Parallel Graph Connectivity

  • Soheil Behnezhad
  • Laxman Dhulipala
  • Hossein Esfandiari
  • Jakub Lacki
  • Vahab Mirrokni

Identifying the connected components of a graph, apart from being a fundamental problem with countless applications, is a key primitive for many other algorithms. In this paper, we consider this problem in parallel settings. Particularly, we focus on the Massively Parallel Computations (MPC) model, which is the standard theoretical model for modern parallel frameworks such as MapReduce, Hadoop, or Spark. We consider the truly sublinear regime of MPC for graph problems where the space per machine is n δ for some desirably small constant δ ϵ (0, 1). We present an algorithm that for graphs with diameter D in the wide range [log ε n, n], takes O(log D) rounds to identify the connected components and takes O(log log n) rounds for all other graphs. The algorithm is randomized, succeeds with high probability, does not require prior knowledge of D, and uses an optimal total space of O(m). We complement this by showing a conditional lower-bound based on the widely believed TwoCycle conjecture that Ω(log D) rounds are indeed necessary in this setting. Studying parallel connectivity algorithms received a resurgence of interest after the pioneering work of Andoni etal [FOCS 2018] who presented an algorithm with O(log D log log n) round-complexity. Our algorithm improves this result for the whole range of values of D and almost settles the problem due to the conditional lower-bound. Additionally, we show that with minimal adjustments, our algorithm can also be implemented in a variant of (CRCW) PRAM in asymptotically the same number of rounds.

Details

NeurIPS Conference 2017 Conference Paper

Affinity Clustering: Hierarchical Clustering at Scale

  • MohammadHossein Bateni
  • Soheil Behnezhad
  • Mahsa Derakhshan
  • MohammadTaghi Hajiaghayi
  • Raimondas Kiveris
  • Silvio Lattanzi
  • Vahab Mirrokni

Graph clustering is a fundamental task in many data-mining and machine-learning pipelines. In particular, identifying a good hierarchical structure is at the same time a fundamental and challenging problem for several applications. The amount of data to analyze is increasing at an astonishing rate each day. Hence there is a need for new solutions to efficiently compute effective hierarchical clusterings on such huge data. The main focus of this paper is on minimum spanning tree (MST) based clusterings. In particular, we propose affinity, a novel hierarchical clustering based on Boruvka's MST algorithm. We prove certain theoretical guarantees for affinity (as well as some other classic algorithms) and show that in practice it is superior to several other state-of-the-art clustering algorithms. Furthermore, we present two MapReduce implementations for affinity. The first one works for the case where the input graph is dense and takes constant rounds. It is based on a Massively Parallel MST algorithm for dense graphs that improves upon the state-of-the-art algorithm of Lattanzi et al. (SPAA 2011). Our second algorithm has no assumption on the density of the input graph and finds the affinity clustering in $O(\log n)$ rounds using Distributed Hash Tables (DHTs). We show experimentally that our algorithms are scalable for huge data sets, e. g. , for graphs with trillions of edges.

PDF Details

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.

PDF Details