Minimax theorem

<h2 id="bilinear-functions-and-zero-sum-games">Bilinear functions and zero-sum games</h2>
<p>Von Neumann's original theorem<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> was motivated by game theory and applies to the case where 
</p>
<ul><li>
  
    
      
        X
      
    
    {\displaystyle X}
  
 and 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 are <a href="/facts/Simplex/0FCfNRN8">standard simplexes</a>: 
  
    
      
        X
        =
        {
        (
        
          x
          
            1
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
        )
        ∈
        [
        0
        ,
        1
        
          ]
          
            n
          
        
        :
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          x
          
            i
          
        
        =
        1
        }
      
    
    {\textstyle X=\{(x_{1},\dots ,x_{n})\in [0,1]^{n}:\sum _{i=1}^{n}x_{i}=1\}}
  
 and 
  
    
      
        Y
        =
        {
        (
        
          y
          
            1
          
        
        ,
        …
        ,
        
          y
          
            m
          
        
        )
        ∈
        [
        0
        ,
        1
        
          ]
          
            m
          
        
        :
        
          ∑
          
            j
            =
            1
          
          
            m
          
        
        
          y
          
            j
          
        
        =
        1
        }
      
    
    {\textstyle Y=\{(y_{1},\dots ,y_{m})\in [0,1]^{m}:\sum _{j=1}^{m}y_{j}=1\}}
  
, and</li>
<li>
  
    
      
        f
        (
        x
        ,
        y
        )
      
    
    {\displaystyle f(x,y)}
  
 is a linear function in both of its arguments (that is, 
  
    
      
        f
      
    
    {\displaystyle f}
  
 is <a href="/facts/Bilinear_form/gyvzn9ym">bilinear</a>) and therefore can be written 
  
    
      
        f
        (
        x
        ,
        y
        )
        =
        
          x
          
            
              T
            
          
        
        A
        y
      
    
    {\displaystyle f(x,y)=x^{\mathsf {T}}Ay}
  
 for a finite matrix 
  
    
      
        A
        ∈
        
          
            R
          
          
            n
            ×
            m
          
        
      
    
    {\displaystyle A\in \mathbb {R} ^{n\times m}}
  
, or equivalently as 
  
    
      
        f
        (
        x
        ,
        y
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          ∑
          
            j
            =
            1
          
          
            m
          
        
        
          A
          
            i
            j
          
        
        
          x
          
            i
          
        
        
          y
          
            j
          
        
      
    
    {\textstyle f(x,y)=\sum _{i=1}^{n}\sum _{j=1}^{m}A_{ij}x_{i}y_{j}}
  
.</li></ul>
<p>Under these assumptions, von Neumann proved that
</p>

max
          
            x
            ∈
            X
          
        
        
          min
          
            y
            ∈
            Y
          
        
        
          x
          
            
              T
            
          
        
        A
        y
        =
        
          min
          
            y
            ∈
            Y
          
        
        
          max
          
            x
            ∈
            X
          
        
        
          x
          
            
              T
            
          
        
        A
        y
        .
      
    
    {\displaystyle \max _{x\in X}\min _{y\in Y}x^{\mathsf {T}}Ay=\min _{y\in Y}\max _{x\in X}x^{\mathsf {T}}Ay.}

<p>In the context of two-player <a href="/facts/Zero-sum_game/ccouScgK">zero-sum games</a>, the sets 
  
    
      
        X
      
    
    {\displaystyle X}
  
 and 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 correspond to the strategy sets of the first and second player, respectively, which consist of lotteries over their actions (so-called <a href="/facts/Mixed_strategies/VEXD1jyj">mixed strategies</a>), and their payoffs are defined by the <a href="/facts/Payoff_Matrix/1zxxyHC0">payoff matrix</a> 
  
    
      
        A
      
    
    {\displaystyle A}
  
. The function 
  
    
      
        f
        (
        x
        ,
        y
        )
      
    
    {\displaystyle f(x,y)}
  
 encodes the <a href="/facts/Expected_value/1XV0JKL8">expected value</a> of the payoff to the first player when the first player plays the strategy 
  
    
      
        x
      
    
    {\displaystyle x}
  
 and the second player plays the strategy 
  
    
      
        y
      
    
    {\displaystyle y}
  
.
</p>
<h2 id="concave-convex-functions">Concave-convex functions</h2>

<p>Von Neumann's minimax theorem can be generalized to domains that are compact and convex, and to functions that are concave in their first argument and convex in their second argument (known as concave-convex functions). Formally, let 
  
    
      
        X
        ⊆
        
          
            R
          
          
            n
          
        
      
    
    {\displaystyle X\subseteq \mathbb {R} ^{n}}
  
 and 
  
    
      
        Y
        ⊆
        
          
            R
          
          
            m
          
        
      
    
    {\displaystyle Y\subseteq \mathbb {R} ^{m}}
  
 be <a href="/facts/Compact_space/d0cgXJH7">compact</a> <a href="/facts/Convex_set/vdAuJRJl">convex</a> sets. If 
  
    
      
        f
        :
        X
        ×
        Y
        →
        
          R
        
      
    
    {\displaystyle f:X\times Y\rightarrow \mathbb {R} }
  
 is a continuous function that is concave-convex, i.e.
</p>

f
        (
        ⋅
        ,
        y
        )
        :
        X
        →
        
          R
        
      
    
    {\displaystyle f(\cdot ,y):X\to \mathbb {R} }
  
 is <a href="/facts/Concave_function/HxVEBkce">concave</a> for every fixed 
  
    
      
        y
        ∈
        Y
      
    
    {\displaystyle y\in Y}
  
, and

f
        (
        x
        ,
        ⋅
        )
        :
        Y
        →
        
          R
        
      
    
    {\displaystyle f(x,\cdot ):Y\to \mathbb {R} }
  
 is <a href="/facts/Convex_function/IbzG5SLF">convex</a> for every fixed 
  
    
      
        x
        ∈
        X
      
    
    {\displaystyle x\in X}
  
.
<p>Then we have that
</p>

max
          
            x
            ∈
            X
          
        
        
          min
          
            y
            ∈
            Y
          
        
        f
        (
        x
        ,
        y
        )
        =
        
          min
          
            y
            ∈
            Y
          
        
        
          max
          
            x
            ∈
            X
          
        
        f
        (
        x
        ,
        y
        )
        .
      
    
    {\displaystyle \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y).}

<h2 id="sions-minimax-theorem">Sion's minimax theorem</h2>
<p>Sion's minimax theorem is a generalization of von Neumann's minimax theorem due to <a href="/facts/Maurice_Sion/Devxnlkc">Maurice Sion</a>,<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> relaxing the requirement that X and Y be standard simplexes and that f be bilinear. It states:<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a>
</p><p>Let 
  
    
      
        X
      
    
    {\displaystyle X}
  
 be a <a href="/facts/Convex_set/vdAuJRJl">convex</a> subset of a <a href="/facts/Linear_topological_space/XRex1ChN">linear topological space</a> and let 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 be a <a href="/facts/Compact_space/d0cgXJH7">compact</a> <a href="/facts/Convex_set/vdAuJRJl">convex</a> subset of a <a href="/facts/Linear_topological_space/XRex1ChN">linear topological space</a>.  If 
  
    
      
        f
      
    
    {\displaystyle f}
  
 is a real-valued <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> on 
  
    
      
        X
        ×
        Y
      
    
    {\displaystyle X\times Y}
  
 with
</p>

f
        (
        ⋅
        ,
        y
        )
      
    
    {\displaystyle f(\cdot ,y)}
  
 <a href="/facts/Upper_semicontinuous/4unJbWdW">upper semicontinuous</a>  and <a href="/facts/Quasi-convex_function/emHsjeRj">quasi-concave</a> on 
  
    
      
        X
      
    
    {\displaystyle X}
  
, for every fixed 
  
    
      
        y
        ∈
        Y
      
    
    {\displaystyle y\in Y}
  
, and

f
        (
        x
        ,
        ⋅
        )
      
    
    {\displaystyle f(x,\cdot )}
  
 lower semicontinuous and quasi-convex on 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
, for every fixed 
  
    
      
        x
        ∈
        X
      
    
    {\displaystyle x\in X}
  
.
<p>Then we have that
</p>

sup
          
            x
            ∈
            X
          
        
        
          min
          
            y
            ∈
            Y
          
        
        f
        (
        x
        ,
        y
        )
        =
        
          min
          
            y
            ∈
            Y
          
        
        
          sup
          
            x
            ∈
            X
          
        
        f
        (
        x
        ,
        y
        )
        .
      
    
    {\displaystyle \sup _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\sup _{x\in X}f(x,y).}

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Parthasarathy%2527s_theorem/aLR5xTYY">Parthasarathy's theorem</a> – a generalization of  Von Neumann's minimax theorem</li>
<li><a href="/facts/Dual_linear_program/Qm3r26pm">Dual linear program</a> can be used to prove the minimax theorem for zero-sum games.</li>
<li><a href="/facts/Yao%2527s_principle/3zrpxlmr">Yao's principle</a> – an application of the minimax theorem to computational complexity</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Simons, Stephen (1995), Du, Ding-Zhu; Pardalos, Panos M. (eds.), "Minimax Theorems and Their Proofs", Minimax and Applications, Nonconvex Optimization and Its Applications, vol. 4, Boston, MA: Springer US, pp. 1–23, doi:10.1007/978-1-4613-3557-3_1, ISBN 978-1-4613-3557-3, retrieved 2024-10-27 <a href="978-1-4613-3557-3" target="_blank">978-1-4613-3557-3</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Von Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Math. Ann. 100: 295–320. doi:10.1007/BF01448847. S2CID 122961988. <a href="/wiki/Mathematische_Annalen" target="_blank">/wiki/Mathematische_Annalen</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>John L Casti (1996). Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience. p. 19. ISBN 978-0-471-00261-1. <a href="978-0-471-00261-1" target="_blank">978-0-471-00261-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Du, Ding-Zhu; Pardalos, Panos M., eds. (1995). Minimax and Applications. Boston, MA: Springer US. ISBN 9781461335573. <a href="9781461335573" target="_blank">9781461335573</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Brandt, Felix; Brill, Markus; Suksompong, Warut (2016). "An ordinal minimax theorem". Games and Economic Behavior. 95: 107–112. arXiv:1412.4198. doi:10.1016/j.geb.2015.12.010. S2CID 360407. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Von Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Math. Ann. 100: 295–320. doi:10.1007/BF01448847. S2CID 122961988. <a href="/wiki/Mathematische_Annalen" target="_blank">/wiki/Mathematische_Annalen</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Sion, Maurice (1958). "On general minimax theorems". Pacific Journal of Mathematics. 8 (1): 171–176. doi:10.2140/pjm.1958.8.171. MR 0097026. Zbl 0081.11502. <a href="https://doi.org/10.2140%2Fpjm.1958.8.171" target="_blank">https://doi.org/10.2140%2Fpjm.1958.8.171</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Sion, Maurice (1958). "On general minimax theorems". Pacific Journal of Mathematics. 8 (1): 171–176. doi:10.2140/pjm.1958.8.171. MR 0097026. Zbl 0081.11502. <a href="https://doi.org/10.2140%2Fpjm.1958.8.171" target="_blank">https://doi.org/10.2140%2Fpjm.1958.8.171</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Komiya, Hidetoshi (1988). "Elementary proof for Sion's minimax theorem". Kodai Mathematical Journal. 11 (1): 5–7. doi:10.2996/kmj/1138038812. MR 0930413. Zbl 0646.49004. <a href="http://projecteuclid.org/euclid.kmj/1138038812" target="_blank">http://projecteuclid.org/euclid.kmj/1138038812</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
</ol>

Minimax theorem open-in-new

Minimax theorem