Game without a value

<h2 id="the-game">The game</h2>
Players I and II choose numbers 
 
 
 
 x
 
 
 {\displaystyle x}
 
 and 
 
 
 
 y
 
 
 {\displaystyle y}
 
 respectively, between 0 and 1. The payoff to player I is

K
 (
 x
 ,
 y
 )
 =
 
 
 {
 
 
 
 −
 1
 
 
 
 if 
 
 x
 <
 y
 <
 x
 +
 1
 
 /
 
 2
 ,
 
 
 
 
 0
 
 
 
 if 
 
 x
 =
 y
 
  or 
 
 y
 =
 x
 +
 1
 
 /
 
 2
 ,
 
 
 
 
 1
 
 
 
 otherwise.
 
 
 
 
 
 
 
 
 
 {\displaystyle K(x,y)={\begin{cases}-1&{\text{if }}x<y<x+1/2,\\0&{\text{if }}x=y{\text{ or }}y=x+1/2,\\1&{\text{otherwise.}}\end{cases}}}

That is, after the choices are made, player II pays 
 
 
 
 K
 (
 x
 ,
 y
 )
 
 
 {\displaystyle K(x,y)}
 
 to player I (so the game is <a href="/facts/Zero-sum/ccouScgK">zero-sum</a>).
If the pair 
 
 
 
 (
 x
 ,
 y
 )
 
 
 {\displaystyle (x,y)}
 
 is interpreted as a point on the unit square, the figure shows the payoff to player I. Player I may adopt a mixed strategy, choosing a number according to a <a href="/facts/Probability_density_function/zvfybna4">probability density function (pdf)</a> 
 
 
 
 f
 
 
 {\displaystyle f}
 
, and similarly player II chooses from a pdf 
 
 
 
 g
 
 
 {\displaystyle g}
 
. Player I seeks to maximize the payoff 
 
 
 
 K
 (
 x
 ,
 y
 )
 
 
 {\displaystyle K(x,y)}
 
, player II to minimize the payoff, and each player is aware of the other's objective.

<h2 id="game-value">Game value</h2>
Sion and Wolfe show that

sup
          
            f
          
        
        
          inf
          
            g
          
        
        ∬
        K
        
        d
        f
        
        d
        g
        =
        
          
            1
            3
          
        
      
    
    {\displaystyle \sup _{f}\inf _{g}\iint K\,df\,dg={\frac {1}{3}}}

but

inf
          
            g
          
        
        
          sup
          
            f
          
        
        ∬
        K
        
        d
        f
        
        d
        g
        =
        
          
            3
            7
          
        
        .
      
    
    {\displaystyle \inf _{g}\sup _{f}\iint K\,df\,dg={\frac {3}{7}}.}

These are the maximal and minimal expectations of the game's value of player I and II respectively.
The 
 
 
 
 sup
 
 
 {\displaystyle \sup }
 
 and 
 
 
 
 inf
 
 
 {\displaystyle \inf }
 
 respectively take the supremum and infimum over pdf's on the unit interval (actually <a href="/facts/Borel_measure/8cYR8Ysw">Borel probability measures</a>). These represent player I and player II's (mixed) strategies. Thus, player I can assure himself of a payoff of at least 3/7 if he knows player II's strategy, and player II can hold the payoff down to 1/3 if he knows player I's strategy.
There is no <a href="/facts/Epsilon_equilibrium/LR9jWpPH">epsilon equilibrium</a> for sufficiently small 
 
 
 
 ε
 
 
 {\displaystyle \varepsilon }
 
, specifically, if 
 
 
 
 ε
 <
 
 
 1
 2
 
 
 
 (
 
 
 
 3
 7
 
 
 −
 
 
 1
 3
 
 
 
 )
 
 ≃
 0.0476
 
 
 {\displaystyle \varepsilon <{\frac {1}{2}}\left({\frac {3}{7}}-{\frac {1}{3}}\right)\simeq 0.0476}
 
. Dasgupta and Maskin<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> assert that the game values are achieved if player I puts probability weight only on the set 
 
 
 
 
 {
 
 0
 ,
 1
 
 /
 
 2
 ,
 1
 
 }
 
 
 
 {\displaystyle \left\{0,1/2,1\right\}}
 
 and player II puts weight only on 
 
 
 
 
 {
 
 1
 
 /
 
 4
 ,
 1
 
 /
 
 2
 ,
 1
 
 }
 
 
 
 {\displaystyle \left\{1/4,1/2,1\right\}}
 
.
<a href="/facts/Glicksberg%2527s_theorem/hrRVtKMt">Glicksberg's theorem</a> shows that any zero-sum game with <a href="/facts/Upper_semicontinuous/4unJbWdW">upper</a> or <a href="/facts/Lower_semicontinuous/4unJbWdW">lower semicontinuous</a> payoff function has a value (in this context, an upper (lower) semicontinuous function K is one in which the set 
 
 
 
 {
 P
 ∣
 K
 (
 P
 )
 <
 c
 }
 
 
 {\displaystyle \{P\mid K(P)<c\}}
 
 (resp 
 
 
 
 {
 P
 ∣
 K
 (
 P
 )
 >
 c
 }
 
 
 {\displaystyle \{P\mid K(P)>c\}}
 
) is <a href="/facts/Open_set/QfTCIqMu">open</a> for any <a href="/facts/Real_number/R02gw5Pb">real number</a> c).
The payoff function of Sion and Wolfe's example is not semicontinuous. However, it may be made so by changing the value of K(x, x) and K(x, x + 1/2) (the payoff along the two discontinuities) to either +1 or −1, making the payoff upper or lower semicontinuous, respectively. If this is done, the game then has a value.

<h2 id="generalizations">Generalizations</h2>
Subsequent work by Heuer<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> discusses a class of games in which the unit square is divided into three regions, the payoff function being constant in each of the regions.

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

<ol>
<li id="fn:1">Sion, Maurice; Wolfe, Phillip (1957), "On a game without a value", in Dresher, M.; Tucker, A. W.; Wolfe, P. (eds.), Contributions to the Theory of Games III, Annals of Mathematics Studies 39, Princeton University Press, pp. 299–306, ISBN 9780691079363 {{citation}}: ISBN / Date incompatibility (help) <a href="9780691079363" target="_blank">9780691079363</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">P. Dasgupta and E. Maskin (1986). "The Existence of Equilibrium in Discontinuous Economic Games, I: Theory". Review of Economic Studies. 53 (1): 1–26. doi:10.2307/2297588. JSTOR 2297588. <a href="/wiki/Partha_Dasgupta" target="_blank">/wiki/Partha_Dasgupta</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">G. A. Heuer (2001). "Three-part partition games on rectangles". Theoretical Computer Science. 259: 639–661. doi:10.1016/S0304-3975(00)00404-7. <a href="https://doi.org/10.1016%2FS0304-3975%2800%2900404-7" target="_blank">https://doi.org/10.1016%2FS0304-3975%2800%2900404-7</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

Game without a value open-in-new

Game without a value