Skip to content

Games.Alternative

Martin Escardo, Paulo Oliva, 9th July 2024.

Alternative, equivalent, inductive definition of the type Game of
games, which may have some practical advantages, such as more modular
definitions of games.


{-# OPTIONS --safe --without-K #-}

open import MLTT.Spartan hiding (J)

module Games.Alternative
        {𝓀 𝓦₀ : Universe}
        (R : 𝓦₀ Μ‡ )
       where

open import UF.Equiv
open import UF.FunExt

open import Games.TypeTrees {𝓀}
open import Games.FiniteHistoryDependent {𝓀} R
             renaming (Game to Game' ;
                       game to game')

open import MonadOnTypes.K

open K-definitions R

data Game : 𝓀 ⁺ βŠ” 𝓦₀ Μ‡  where
 leaf   : R β†’ Game
 branch : (X : 𝓀 Μ‡ ) β†’ K X β†’ (X β†’ Game) β†’ Game

leaf' : R β†’ Game'
leaf' r = game' [] (Ξ» ⟨⟩ β†’ r) ⟨⟩

branch' : (X : 𝓀 Μ‡ ) β†’ K X β†’ (X β†’ Game') β†’ Game'
branch' X Ο• Gf = game' (X ∷ (game-tree ∘ Gf))
                       (Ξ» (x :: xs) β†’ payoff-function (Gf x) xs)
                       (Ο• :: (quantifier-tree ∘ Gf))

from-Game : Game β†’ Game'
from-Game (leaf r)        = leaf' r
from-Game (branch X Ο• Gf) = branch' X Ο• (from-Game ∘ Gf)


We need the curried version h of the conversion function to-Game
defined below to convince the termination checker that the following
recursion does terminate.


to-Game : Game' β†’ Game
to-Game (game' Xt q Ο•t) = h Xt q Ο•t
 where
  h : (Xt : 𝑻) β†’ (Path Xt β†’ R) β†’ π“š Xt β†’ Game
  h []       q ⟨⟩        = leaf (q ⟨⟩)
  h (X ∷ Xf) q (Ο• :: Ο•f) = branch X Ο• (Ξ» x β†’ h (Xf x) (subpred q x) (Ο•f x))


The equations we would have liked to use to define the function
to-Game are the following:


to-Game-base : (q : Path [] β†’ R)
             β†’ to-Game (game' [] q ⟨⟩) ＝ leaf (q ⟨⟩)
to-Game-base q = refl

to-Game-step
 : (X : 𝓀 Μ‡ )
   (Xf : X β†’ 𝑻)
   (Ο• : K X)
   (Ο•f : (x : X) β†’ π“š (Xf x))
   (q : Path (X ∷ Xf) β†’ R)
 β†’ to-Game (game' (X ∷ Xf) q (Ο• :: Ο•f))
 ＝ branch X Ο• (Ξ» x β†’ to-Game (game' (Xf x) (subpred q x) (Ο•f x)))
to-Game-step X Xf Ο• Ο•f q = refl


We also have the following equivalent definitional equalities
expressed in terms of leaf' and branch':


to-Game-base' : (r : R) β†’ to-Game (leaf' r) ＝ leaf r
to-Game-base' r = refl

module _
         (X : 𝓀 Μ‡ )
         (Xf : X β†’ 𝑻)
         (Ο• : K X)
         (Ο•f : (x : X) β†’ π“š (Xf x))
         (q : Path (X ∷ Xf) β†’ R)
       where

 subgame : X β†’ Game'
 subgame x = game' (Xf x) (subpred q x) (Ο•f x)

 to-Game-step' : to-Game (branch' X Ο• subgame) ＝ branch X Ο• (to-Game ∘ subgame)
 to-Game-step' = refl


The above conversion functions are mutually inverse and so the types
Game and Game' are equivalent, assuming function extensionality.


module _ (fe : Fun-Ext) where

 from-to-Game : from-Game ∘ to-Game ∼ id
 from-to-Game (game' Xt q Ο•t) = h Xt q Ο•t
  where
   h : (Xt : 𝑻)
       (q : Path Xt β†’ R)
       (Ο•t : π“š Xt)
     β†’ from-Game (to-Game (game' Xt q Ο•t)) ＝ game' Xt q Ο•t
   h []       q ⟨⟩       = refl
   h (X ∷ Xf) q (Ο• :: Ο•f) =
    from-Game (to-Game (game' (X ∷ Xf) q (Ο• :: Ο•f))) ＝⟨refl⟩
    from-Game (branch X Ο• (to-Game ∘ Gf))            ＝⟨refl⟩
    branch' X Ο• Hf                                   ＝⟨ I ⟩
    branch' X Ο• Gf                                   ＝⟨refl⟩
    game' (X ∷ Xf) q (Ο• :: Ο•f)                       ∎
    where
     Gf Hf : X β†’ Game'
     Gf x = subgame X Xf Ο• Ο•f q x
     Hf x = from-Game (to-Game (Gf x))

     IH : Hf ∼ Gf
     IH x = h (Xf x) (subpred q x) (Ο•f x)

     I : branch' X Ο• Hf ＝ branch' X Ο• Gf
     I = ap (branch' X Ο•) (dfunext fe IH)

 to-from-Game : to-Game ∘ from-Game ∼ id
 to-from-Game (leaf x)        = refl
 to-from-Game (branch X Ο• Gf) =
  to-Game (from-Game (branch X Ο• Gf))    ＝⟨refl⟩
  to-Game (branch' X Ο• (from-Game ∘ Gf)) ＝⟨refl⟩
  branch X Ο• (to-Game ∘ from-Game ∘ Gf)  ＝⟨ I ⟩
  branch X Ο• Gf                          ∎
  where
   I = ap (branch X Ο•) (dfunext fe (to-from-Game ∘ Gf))

 Game-is-equiv-to-Game' : Game ≃ Game'
 Game-is-equiv-to-Game' = qinveq from-Game (to-Game , to-from-Game , from-to-Game)