{"id":8602,"date":"2014-12-07T10:46:21","date_gmt":"2014-12-07T18:46:21","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8602"},"modified":"2026-09-30T09:15:03","modified_gmt":"2026-09-30T17:15:03","slug":"sparse-strategies","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/sparse-strategies\/","title":{"rendered":"Sparse strategies for zero-sum matrix games"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<p>Here is a derivation of a Lagrangian-relaxation algorithm for computing approximately optimal mixed strategies for two-player zero-sum matrix games. It illustrates the basic idea of deriving Lagrangian-relaxation algorithms. <\/p>\n<p><!--more--><\/p>\n<p>The algorithm and the derivation are from\u00a0<span class=\"cite\">[<a href=\"#Young95Randomized\">3<\/a>]<\/span>. The approximation guarantee is comparable to those for the packing algorithms of Plotkin, Shmoys, and Tardos\u00a0<span class=\"cite\">[<a href=\"#Plotkin95Fast\">2<\/a>]<\/span>. The mixed strategies also happen to be sparse. The existence proof for sparse mixed strategies is from\u00a0<span class=\"cite\">[<a href=\"#Lipton94Simple\">1<\/a>]<\/span>. <\/p>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Problem statement.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Fix a payoff matrix <script type=\"math\/tex;\">M<\/script> for a two-player zero sum game, so that <script type=\"math\/tex;\">M_{ij}<\/script> is the payoff from MIN to MAX if MAX plays pure strategy <script type=\"math\/tex;\">i\\in [m]<\/script> and MIN plays pure strategy <script type=\"math\/tex;\">j\\in [n]<\/script>. <\/p>\n<p>A <em>mixed strategy<\/em> <script type=\"math\/tex;\">q<\/script> for MIN is a probability distribution on <script type=\"math\/tex;\">[n]<\/script>. The <em>value<\/em> of <script type=\"math\/tex;\">q<\/script> is <script type=\"math\/tex;\">\\max _{i\\in [m]} \\sum _{j\\in [n]} M_{ij} q_j<\/script> (the maximum expected payoff that MAX can force if MIN plays a pure strategy randomly from <script type=\"math\/tex;\">q<\/script>). <\/p>\n<p>We say a mixed strategy <script type=\"math\/tex;\">q<\/script> is <em><script type=\"math\/tex;\">k<\/script>-sparse<\/em> if it chooses uniformly from a multiset of <script type=\"math\/tex;\">k<\/script> pure strategies. Equivalently, each probability <script type=\"math\/tex;\">q_j<\/script> is an integer multiple of <script type=\"math\/tex;\">1\/k<\/script>. <\/p>\n<p>The goal is to compute some <script type=\"math\/tex;\">k<\/script>-sparse mixed strategy <script type=\"math\/tex;\">q<\/script> for MIN whose value is at most <script type=\"math\/tex;\">(1+\\varepsilon )<\/script> times the minimum possible. <\/p>\n<p>(Although we will not use them in this note, of course symmetrical definitions hold for MAX. A mixed strategy <script type=\"math\/tex;\">p<\/script> for MAX is a probability distribution on <script type=\"math\/tex;\">[m]<\/script>; it has value <script type=\"math\/tex;\">\\min _{j\\in [n]} \\sum _{i\\in [m]} M_{ij} p_i<\/script>. If <script type=\"math\/tex;\">q^*<\/script> denotes an optimal (minimum value) mixed strategy for MAX, then Von Neumann\u2019s min-max theorem states that, for any payoff matrix <script type=\"math\/tex;\">M<\/script>, the value of <script type=\"math\/tex;\">p^*<\/script> equals the value of <script type=\"math\/tex;\">q^*<\/script>.) <\/p>\n<\/div><\/div>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000002\">Computing an approximately optimal <script type=\"math\/tex;\">k<\/script>-sparse mixed strategy<\/h1>\n<p>We will derive the following algorithm and performance guarantee: <\/p>\n<table id=\"a0000000003\" class=\"latex-alg\" cellspacing=\"0\" cellpadding=\"4\" width=\"100%\" style=\"border-top:1px solid #CCC;border-bottom:1px solid #CCC;margin-top:2ex;margin-bottom:2ex;\">\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Initialize <script type=\"math\/tex;\">J<\/script> to the empty sequence. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> For <script type=\"math\/tex;\">t=1,2,\\ldots , k<\/script>: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> Choose a pure strategy <script type=\"math\/tex;\">j_t = j<\/script> for MIN minimizing <script type=\"math\/tex;\">\\sum _{i\\in [n]} M_{ij} (1+\\varepsilon )^{P_i}<\/script>, where <script type=\"math\/tex;\">P_i = \\sum _{s=1}^{t-1} M_{ij_s}<\/script> is the total payoff so far if MAX played <script type=\"math\/tex;\">i<\/script> every time.<\/p>\n<div style=\"margin:0pt;padding:0pt;margin-bottom:6px\"><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:1em\"> Add <script type=\"math\/tex;\">j_t<\/script> to the end of <script type=\"math\/tex;\">J<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">5.<\/td>\n<td style=\"padding-left:0em\"> Return <script type=\"math\/tex;\">\\tilde q<\/script>, where <script type=\"math\/tex;\">\\tilde q_j<\/script> equals <script type=\"math\/tex;\">\\frac{1}{k}<\/script> times the number of times <script type=\"math\/tex;\">j<\/script> occurs in <script type=\"math\/tex;\">J<\/script>.<\/td>\n<\/tr>\n<\/table>\n<p>Let <script type=\"math\/tex;\">m<\/script> be the number of pure strategies available to MAX. <\/p>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Theorem.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>For any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script> such that <script type=\"math\/tex;\">k \\ge 2\\ln (m)\/\\, \\mu \\varepsilon ^2<\/script>, given the instance, <script type=\"math\/tex;\">k<\/script>, and <script type=\"math\/tex;\">\\varepsilon <\/script>, if each payoff <script type=\"math\/tex;\">M_{ij}<\/script> is in <script type=\"math\/tex;\">[0,1]<\/script>, then the algorithm returns a <script type=\"math\/tex;\">k<\/script>-sparse strategy <script type=\"math\/tex;\">\\tilde q<\/script> of value at most <script type=\"math\/tex;\">(1+\\varepsilon )\\mu ^*<\/script>, where <script type=\"math\/tex;\">\\mu ^*<\/script> is the minimum value of any mixed strategy for MIN. <\/p>\n<\/div><\/div>\n<p>To prove the theorem, we apply <a href=\"http:\/\/algnotes.info\/on\/method-of-conditional-probabilities\">the method of conditional probabilities<\/a> to the following rounding scheme. Fix any integer <script type=\"math\/tex;\">k<\/script> and let <script type=\"math\/tex;\">q<\/script> be any mixed strategy for MIN. <\/p>\n<blockquote class=\"quote\"><p><em> Randomly sample <script type=\"math\/tex;\">k<\/script> pure strategies independently from the distribution <script type=\"math\/tex;\">q<\/script> on <script type=\"math\/tex;\">[n]<\/script>. <br \/>Return the mixed strategy <script type=\"math\/tex;\">\\tilde q<\/script> such that, for each pure strategy <script type=\"math\/tex;\">j\\in [n]<\/script>, the probability <script type=\"math\/tex;\">\\tilde q_j<\/script> equals the number of times <script type=\"math\/tex;\">j<\/script> was sampled.<\/em> <\/p><\/blockquote>\n<p>First we analyze the rounding scheme. Let <script type=\"math\/tex;\">\\mu <\/script> be the value of the mixed strategy <script type=\"math\/tex;\">q<\/script>. <\/p>\n<div id=\"a0000000005\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (<span class=\"cite\">[<a href=\"#Lipton94Simple\">1<\/a>]<\/span>).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> Assume each payoff <script type=\"math\/tex;\">M_{ij}<\/script> is in <script type=\"math\/tex;\">[0,1]<\/script>. For any <script type=\"math\/tex;\">\\varepsilon \\in (0,1)<\/script>, if <script type=\"math\/tex;\">k \\ge 2\\ln (m)\\, \/\\, \\mu \\varepsilon ^2<\/script>, then, with positive probability, the rounding scheme returns a <script type=\"math\/tex;\">k<\/script>-sparse mixed strategy <script type=\"math\/tex;\">\\tilde q<\/script> of value at most <script type=\"math\/tex;\">(1+\\varepsilon )\\mu <\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000006\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof of lemma\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof of lemma\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> The mixed strategy <script type=\"math\/tex;\">\\tilde q<\/script> is inevitably <script type=\"math\/tex;\">k<\/script>-sparse. <\/p>\n<p>Recall that the value of <script type=\"math\/tex;\">\\tilde q<\/script> is <script type=\"math\/tex;\">\\max _{i\\in [m]} \\sum _{j\\in [n]} \\tilde q_j M_{ij}<\/script>. <\/p>\n<p>Fix any pure strategy <script type=\"math\/tex;\">i\\in [m]<\/script> for MAX. Say that <script type=\"math\/tex;\">i<\/script> is \u201cbad\u201d (for MIN) if <script type=\"math\/tex;\">\\sum _{j\\in [n]} \\tilde q_j M_{ij} \\gt (1+\\varepsilon )\\mu <\/script>. We will show that the probability of this event (<script type=\"math\/tex;\">i<\/script> being bad) is less than <script type=\"math\/tex;\">1\/m<\/script>. This proves the lemma, because it implies that the expected number of bad strategies is less than 1 (so with positive probability there are none). <\/p>\n<p>Let <script type=\"math\/tex;\">J<\/script> be the sequence of <script type=\"math\/tex;\">k<\/script> pure strategies sampled from <script type=\"math\/tex;\">q<\/script> in the randomized-rounding scheme. The value of <script type=\"math\/tex;\">\\tilde q<\/script> against MAX\u2019s pure strategy <script type=\"math\/tex;\">i<\/script> is <\/p>\n<div id=\"a0000000007\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\sum _{j\\in [n]} \\tilde q_j M_{ij} ~ =~  \\sum _{j\\in J} {\\textstyle \\frac{1}{k}} M_{ij}.  <\/script><\/div>\n<p> Multiplying the right-hand side by <script type=\"math\/tex;\">k<\/script>, <script type=\"math\/tex;\">i<\/script> is bad if and only if <\/p>\n<div id=\"eqn\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation} \\label{eqn} \\sum _{j\\in J} M_{ij} ~ \\gt ~  (1+\\varepsilon )\\mu k. \\end{equation}<\/script><\/div>\n<p> Think of the left-hand side of\u00a0(\\ref{eqn}) as the total payoff from MIN to MAX in <script type=\"math\/tex;\">k<\/script> independent plays of the game, where in each play MAX plays <script type=\"math\/tex;\">i<\/script> and MIN plays randomly from <script type=\"math\/tex;\">q<\/script> (as each element in <script type=\"math\/tex;\">J<\/script> is in fact randomly sampled from <script type=\"math\/tex;\">q<\/script>). Then, <script type=\"math\/tex;\">i<\/script> is bad iff MIN\u2019s total payout to MAX is more than <script type=\"math\/tex;\">(1+\\varepsilon )\\mu k<\/script>. <\/p>\n<p>For each of the <script type=\"math\/tex;\">k<\/script> plays individually, since MAX plays <script type=\"math\/tex;\">i<\/script> and MIN plays <script type=\"math\/tex;\">j<\/script> randomly from <script type=\"math\/tex;\">q<\/script>, the expected payout is at most <script type=\"math\/tex;\">\\mu <\/script>. So the total expected payout for all <script type=\"math\/tex;\">k<\/script> plays is at most <script type=\"math\/tex;\">\\mu k<\/script>. Since each payoff <script type=\"math\/tex;\">M_{ij}<\/script> is in <script type=\"math\/tex;\">[0,1]<\/script>, by <a href=\"http:\/\/algnotes.info\/on\/chernoff\">a standard Chernoff bound<\/a>, the probability that this total payout exceeds <script type=\"math\/tex;\">(1+\\varepsilon )\\mu k<\/script> is less than <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2 \\mu k \/ 2)<\/script>. By the assumption on <script type=\"math\/tex;\">k<\/script> in the lemma this is at most <script type=\"math\/tex;\">1\/m<\/script>. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<p>Now we prove the theorem by showing that applying the method of conditional probabilities to the lemma yields the algorithm. <\/p>\n<div class=\"expandable\" id=\"a0000000008\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof of theorem\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof of theorem\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> The algorithm will emulate the rounding scheme, but instead of choosing each pure strategy <script type=\"math\/tex;\">j_t<\/script> for MIN randomly from <script type=\"math\/tex;\">q<\/script>, it will choose <script type=\"math\/tex;\">j_t<\/script> so as to keep the conditional expectation of the number of bad pure strategies <script type=\"math\/tex;\">i<\/script> for MAX below 1. <\/p>\n<p>Let <script type=\"math\/tex;\">J=(j_1,j_2,\\ldots ,j_k)<\/script> be the random sequence of pure strategies for MIN from the rounding scheme. Let <script type=\"math\/tex;\">P_i(t) = \\sum _{s\\le t} M_{ij_s}<\/script> denote the cumulative payoff to MAX in the first <script type=\"math\/tex;\">t<\/script> rounds, assuming, in each round <script type=\"math\/tex;\">s=1,\\ldots ,t<\/script>, MAX and MIN play pure strategies <script type=\"math\/tex;\">i<\/script> and <script type=\"math\/tex;\">j_s<\/script>, respectively. A pure strategy <script type=\"math\/tex;\">i<\/script> for MAX is bad (when the rounding scheme finishes) if <script type=\"math\/tex;\">P_i(k) \\ge (1+\\varepsilon )\\mu k<\/script>. <\/p>\n<p>In using the Chernoff bound for each <script type=\"math\/tex;\">i<\/script>, the analysis of the rounding scheme implicitly bounds the number of bad <script type=\"math\/tex;\">i<\/script>\u2019s by <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\Phi ~ =~  \\sum _{i\\in [m]} \\frac{(1+\\varepsilon )^{\\textstyle P_i(k)} }{ (1+\\varepsilon )^{(1+\\varepsilon ) \\mu k } } ~ =~  \\sum _{i\\in [m]} \\frac{ \\prod _{t=1}^k (1+\\varepsilon )^{\\textstyle M_{ij_t}} }{ (1+\\varepsilon )^{(1+\\varepsilon ) \\mu k } },  <\/script><\/div>\n<p> and it shows this expectation is at most 1. <\/p>\n<p>(To understand where <script type=\"math\/tex;\">\\Phi <\/script> comes from requires a good understanding of <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">the proof of the Chernoff bound<\/a>. Here are the essentials. For each bad <script type=\"math\/tex;\">i<\/script>, the term for <script type=\"math\/tex;\">i<\/script> in the sum is at least 1, so the number of bad <script type=\"math\/tex;\">i<\/script>\u2019s is at most <script type=\"math\/tex;\">\\Phi <\/script>. <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">The proof of the Chernoff bound<\/a> shows that the expectation of the term for <script type=\"math\/tex;\">i<\/script> in <script type=\"math\/tex;\">\\Phi <\/script> is less than <script type=\"math\/tex;\">\\exp (-\\varepsilon ^2 \\mu k\/2)<\/script>. By the assumption on <script type=\"math\/tex;\">k<\/script> in the analysis of the rounding scheme, this is at most <script type=\"math\/tex;\">1\/m<\/script>, so the expectation of <script type=\"math\/tex;\">\\Phi <\/script> is less than 1.) <\/p>\n<p>The algorithm should choose each <script type=\"math\/tex;\">j_t<\/script> to keep the conditional expectation of <script type=\"math\/tex;\">\\Phi <\/script>, given the choices so far, below 1. Fix any <script type=\"math\/tex;\">t\\in \\{ 0,1,\\ldots ,k\\} <\/script>. Recall that <script type=\"math\/tex;\">\\textrm{E}[M_{ij_t}] \\le \\mu <\/script> for all <script type=\"math\/tex;\">i<\/script>. One <a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">pessimistic estimator<\/a> for the conditional expectation of <script type=\"math\/tex;\">\\Phi <\/script>, given the first <script type=\"math\/tex;\">t<\/script> choices, is <\/p>\n<div id=\"a0000000010\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi _t ~ =~  \\sum _{i\\in [m]} \\frac{ \\prod _{s=1}^t (1+\\varepsilon )^{\\textstyle M_{ij_t}} \\times \\prod _{s=t+1}^k (1+\\varepsilon \\mu ) }{ (1+\\varepsilon )^{(1+\\varepsilon ) \\mu k} } ~ =~  \\sum _{i\\in [m]} \\frac{ (1+\\varepsilon )^{P_i(t)} \\times (1+\\varepsilon \\mu )^{k-t} }{ (1+\\varepsilon )^{(1+\\varepsilon ) \\mu k} }.  <\/script><\/div>\n<p> To reach a successful outcome, it suffices if the algorithm chooses each path to ensure that <script type=\"math\/tex;\">\\phi _t<\/script> does not increase, so that <script type=\"math\/tex;\">\\phi _k \\le \\phi _{k-1} \\le \\cdots \\le \\phi _0 \\lt 1<\/script>. <\/p>\n<p>The algorithm will choose each <script type=\"math\/tex;\">j_{t+1}<\/script> to ensure <script type=\"math\/tex;\">\\phi _{t+1} \\le \\phi _t<\/script>. Letting <script type=\"math\/tex;\">\\omega ^i_t<\/script> denote the term for <script type=\"math\/tex;\">i<\/script> in <script type=\"math\/tex;\">\\phi _t<\/script> (so <script type=\"math\/tex;\">\\phi _t = \\sum _i \\omega ^i_t<\/script>) if the algorithm chooses some <script type=\"math\/tex;\">j<\/script> to be <script type=\"math\/tex;\">j_{t+1}<\/script>, then <\/p>\n<div id=\"eq:1\" class=\"equation\"><script type=\"math\/tex; mode=display\">\\begin{equation}  \\label{eq:1} \\phi _{t+1} ~ \\le ~  \\sum _{i\\in [m]} \\frac{ 1+\\varepsilon M_{ij} }{ 1+\\varepsilon \\mu } \\omega ^i_t. \\end{equation}<\/script><\/div>\n<p> If we choose <script type=\"math\/tex;\">j<\/script> randomly as in the sampling scheme, then <script type=\"math\/tex;\">\\textrm{E}[M_{ij}] \\le \\mu <\/script>, so (by inspection) the expectation of the right-hand side of\u00a0(\\ref{eq:1}) is at most <script type=\"math\/tex;\">\\sum _i \\omega ^i_t = \\phi _t<\/script>. <\/p>\n<p>So, to ensure <script type=\"math\/tex;\">\\phi _{t+1}\\le \\phi _t<\/script>, it suffices to choose <script type=\"math\/tex;\">j<\/script> to minimize the right-hand side of\u00a0(\\ref{eq:1}). Inspecting\u00a0(\\ref{eq:1}) and simplifying, , <script type=\"math\/tex;\">j<\/script> should minimize <\/p>\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\sum _{i\\in [m]} M_{ij} M_{ij} \\omega ^i_t.  <\/script><\/div>\n<p> In the definition of <script type=\"math\/tex;\">\\omega ^i_t<\/script> (via <script type=\"math\/tex;\">\\phi _t<\/script>), the factors of <script type=\"math\/tex;\">(1+\\varepsilon \\mu )^{k-t}<\/script> and <script type=\"math\/tex;\">(1+\\varepsilon )^{(1+\\varepsilon )\\mu k}<\/script> are independent of <script type=\"math\/tex;\">i<\/script> and independent of all choices so far. Factoring these irrelevant terms out, <script type=\"math\/tex;\">j<\/script> should minimize <\/p>\n<div id=\"a0000000012\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\sum _{i\\in [m]} M_{ij} \\big(1+\\varepsilon \\big)^{\\textstyle P_i(t)}.  <\/script><\/div>\n<p> (Recall <script type=\"math\/tex;\">P_i(t) = \\sum _{s=1}^t M_{ij_s}<\/script>.) Thus, the algorithm chooses each path to minimize the pessimistic estimator. This keeps the pessimistic estimator from increasing, ensuring a successful outcome. <\/p>\n<p>Finally, note that to do this, the algorithm does not need to know <script type=\"math\/tex;\">q<\/script>, yet is guaranteed to do as well as the rounding scheme for any <script type=\"math\/tex;\">q<\/script>. This proves the lemma. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000013\">Running time<\/h2>\n<p> The algorithm takes <script type=\"math\/tex;\">k<\/script> iterations. Each iteration requires selecting the best response for MIN for a given mixed strategy for MAX. <\/p>\n<p>If the goal is to find an approximately optimal mixed strategy (independent of <script type=\"math\/tex;\">k<\/script>), then one can just take <script type=\"math\/tex;\">k=\\lceil 2\\ln (m)\/\\mu \\varepsilon ^2\\rceil <\/script>. If <script type=\"math\/tex;\">\\mu <\/script> is unknown, then one can simply run the algorithm until the resulting mixed strategy <script type=\"math\/tex;\">\\tilde q<\/script> for MIN has value at most <script type=\"math\/tex;\">1+\\varepsilon <\/script> times the mixed strategy <script type=\"math\/tex;\">p<\/script> for MAX defined by <script type=\"math\/tex;\">p_i \\propto (1+\\varepsilon )^{P_i(t)}<\/script>. (Note that the main loop of the algorithm is independent of <script type=\"math\/tex;\">\\mu <\/script>.) This will take <script type=\"math\/tex;\">O(\\ln (m)\/\\mu \\varepsilon ^2)<\/script> iterations. <\/p>\n<p>In many cases of interest, <script type=\"math\/tex;\">\\mu <\/script> is exponentially small, so the number of iterations can be exponentially large. In this case, <a href=\"http:\/\/algnotes.info\/on\/multicommodity-flow-faster\">Garg and K\u00f6nemann\u2019s technique of non-uniform increments<\/a> can be used to modify the algorithm to have <script type=\"math\/tex;\">O(m\\log (m)\/\\varepsilon ^2)<\/script> iterations. <\/p>\n<\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000014\">Related<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian\">Summary of notes on deriving Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<\/ul>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000015\">Background<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff\">Introduction to the Chernoff bound<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/chernoff-proof\">Proof of the Chernoff bound<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-example\">style Lagrangian-relaxation algorithm<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/modeling\">Maximum multicommodity flow<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Using randomized rounding to derive greedy and Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div>\n<h1 id=\"bibliography\">Bibliography<\/h1>\n<table class=\"bibliography\" cellspacing=\"0\" cellpadding=\"2\">\n<tr>\n<td valign=\"top\">[<a name=\"Lipton94Simple\">1<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;R+Lipton+&quot;+author:&quot;+N+E++Young&quot;+intitle:&quot;+Simple+strategies+for+large+zero-sum+games+with+applications+to+complexity+theory&quot;\">R.\u00a0Lipton and N.\u00a0E. Young. Simple strategies for large zero-sum games with applications to complexity theory. In <em>Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing<\/em>, pages 734\u2013740, Montr\u00e9al, Qu\u00e9bec, Canada, 23\u201325\u00a0May 1994. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Plotkin95Fast\">2<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;S+A++Plotkin&quot;+author:&quot;+D+B++Shmoys&quot;+author:&quot;+&quot;+author:&quot;+E+Tardos&quot;+intitle:&quot;+Fast+approximation+algorithms+for+fractional+packing+and+covering+problems&quot;\">S.\u00a0A. Plotkin, D.\u00a0B. Shmoys, and E.\u00a0Tardos. Fast approximation algorithms for fractional packing and covering problems. <em>Math. Operations Research<\/em>, 20(2):257\u2013301, 1995. Preliminary version in FOCS\u201991. <\/a><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\">[<a name=\"Young95Randomized\">3<\/a>]<\/td>\n<td><a href=\"http:\/\/scholar.google.com\/scholar?q=author:&quot;N+E++Young&quot;+intitle:&quot;+Randomized+rounding+without+solving+the+linear+program&quot;\">N.\u00a0E. Young. Randomized rounding without solving the linear program. In <em>Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms<\/em>, pages 170\u2013178, San Francisco, California, 22\u201324\u00a0Jan. 1995. <\/a><\/td>\n<\/tr>\n<\/table><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Here is a derivation of a Lagrangian-relaxation algorithm for computing approximately optimal mixed strategies for two-player zero-sum matrix games. It illustrates the basic idea of deriving Lagrangian-relaxation algorithms.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8645,"menu_order":4,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8602","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8602","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/comments?post=8602"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8602\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8645"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=8602"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}