Nash equilibrium is a compositional predicate: if each sub-game is in equilibrium given its context, the whole game is in equilibrium. Games compose like programs.
Open games โ games with interfaces
An open game has inputs (what the player observes) and outputs (what the player does), plus a coplay channel that carries consequences back. Think of it as a function with a feedback wire. Games compose by wiring outputs to inputs, the same pattern as sequential composition of programs.
Scheme
; An open game: (play coplay); play: observation -> action; coplay: (observation, action, utility) -> (); The game is "open" because utility comes from outside.
(define (make-game name play)
(list name play))
(define (game-play g observation)
((cadr g) observation))
; Player 1: sees a price, decides to buy or not
(define buyer
(make-game 'buyer
(lambda (price)
(if (< price 50) 'buy 'pass))))
; Player 2: sets a price
(define seller
(make-game 'seller
(lambda (demand)
(if (eq? demand 'high) 7030))))
(display "buyer at price 30: ")
(display (game-play buyer 30)) (newline)
(display "buyer at price 70: ")
(display (game-play buyer 70)) (newline)
(display "seller at demand high: ")
(display (game-play seller 'high)) (newline)
Python
# Open games in Pythondef buyer(price):
return"buy"if price < 50else"pass"def seller(demand):
return70if demand == "high"else30print(f"buyer(30) = {buyer(30)}")
print(f"buyer(70) = {buyer(70)}")
print(f"seller('high') = {seller('high')}")
Selection functions
A selection function picks the "best" element from a set, given a valuation (how good each element is). It's the decision-making core of an open game. The classic example: argmax picks the action that maximizes utility.
Scheme
; Selection function: choose best action given a valuation; epsilon : (X -> R) -> X; "Given how good each action is, which one do you pick?"
(define (argmax actions valuation)
(let loop ((best (car actions))
(best-val (valuation (car actions)))
(rest (cdr actions)))
(if (null? rest) best
(let ((v (valuation (car rest))))
(if (> v best-val)
(loop (car rest) v (cdr rest))
(loop best best-val (cdr rest)))))))
; Player values actions by profit
(define actions '(low medium high))
(define (profit action)
(cond ((eq? action 'low) 10)
((eq? action 'medium) 25)
((eq? action 'high) 15)))
(display "best action: ")
(display (argmax actions profit)) (newline)
; medium โ highest profit; Change the valuation, choice changes
(define (risk-averse action)
(cond ((eq? action 'low) 10)
((eq? action 'medium) 8)
((eq? action 'high) 3)))
(display "risk-averse: ")
(display (argmax actions risk-averse))
; low โ safe choice
Confidence: Exact. argmax is the canonical selection function from the paper.
Composing games โ sequential play
Two open games compose when the first player's action becomes the second player's observation. The composite game's equilibrium condition: each player plays optimally given what they observe.
Here's the punchline. An equilibrium is a predicate on strategy profiles: "no player can improve by deviating" (๐ฒ what is Nash equilibrium?). Hedges shows this predicate is compositional: if each sub-game satisfies it given its context, the whole game does too. Equilibrium is a postcondition.
Scheme
; Nash equilibrium: no player can improve by deviating; Check each player: is their action optimal given others' actions?; BiwaScheme helpers
(define (any pred lst) (if (null? lst) #f (if (pred (car lst)) #t (any pred (cdr lst)))))
(define (take lst n) (if (or (null? lst) (= n 0)) '() (cons (car lst) (take (cdr lst) (- n 1)))))
(define (drop lst n) (if (or (null? lst) (= n 0)) lst (drop (cdr lst) (- n 1))))
(define (nash-eq? strategies utility-fns action-spaces)
(let loop ((i 0) (result #t))
(if (>= i (length strategies)) result
(let* ((current (list-ref strategies i))
(util-fn (list-ref utility-fns i))
(current-util (util-fn strategies))
(can-improve
(any (lambda (alt)
(let ((alt-strats (append (take strategies i)
(list alt)
(drop strategies (+ i 1)))))
(> (util-fn alt-strats) current-util)))
(list-ref action-spaces i))))
(loop (+ i 1) (and result (not can-improve)))))))
; Prisoner's dilemma
(define (u1 s) (let ((a (car s)) (b (cadr s)))
(cond ((and (eq? a 'C) (eq? b 'C)) 3)
((and (eq? a 'C) (eq? b 'D)) 0)
((and (eq? a 'D) (eq? b 'C)) 5)
(else1))))
(define (u2 s) (let ((a (car s)) (b (cadr s)))
(cond ((and (eq? a 'C) (eq? b 'C)) 3)
((and (eq? a 'C) (eq? b 'D)) 5)
((and (eq? a 'D) (eq? b 'C)) 0)
(else1))))
(display "(D,D) equilibrium? ")
(display (nash-eq? '(D D) (list u1 u2) '((C D) (C D)))) (newline)
(display "(C,C) equilibrium? ")
(display (nash-eq? '(C C) (list u1 u2) '((C D) (C D))))
; (D,D) is Nash. (C,C) is not โ each player can improve by defecting.
Confidence: Simplified. Pure strategies over finite games. The paper works with mixed strategies and continuous action spaces.
Python
# Nash equilibrium check in Pythondef is_nash(strategies, utility_fns, action_spaces):
for i inrange(len(strategies)):
current_util = utility_fns[i](strategies)
for alt in action_spaces[i]:
alt_s = strategies[:i] + [alt] + strategies[i+1:]
if utility_fns[i](alt_s) > current_util:
returnFalsereturnTrue# Prisoner's dilemma
u1 = lambda s: {("C","C"):3, ("C","D"):0, ("D","C"):5, ("D","D"):1}[tuple(s)]
u2 = lambda s: {("C","C"):3, ("C","D"):5, ("D","C"):0, ("D","D"):1}[tuple(s)]
print(f"(D,D) Nash? {is_nash(['D','D'], [u1,u2], [['C','D'],['C','D']])}")
print(f"(C,C) Nash? {is_nash(['C','C'], [u1,u2], [['C','D'],['C','D']])}")
Why compositionality matters for games
Classical game theory checks equilibrium over the entire strategy profile at once. Hedges decomposes it: each sub-game checks locally, given its interface. Wire the sub-games together and the local checks compose into a global guarantee.
All examples use pure strategies over finite action spaces. The paper works with mixed strategies, continuous spaces, and open games as morphisms in a symmetric monoidal category with a coplay (contravariant) channel. For example: the Nash equilibrium check on this page iterates over two players with two actions each. In the paper, the same construction applies to a network of open games composed via string diagrams โ where equilibrium is verified by checking each node's selection function against the continuation induced by all downstream nodes. The compositionality is identical. The string-diagrammatic machinery is not.
Watch
Bartosz Milewski explains open games and compositional game theory:
Ready for the real thing? Read the paper. Start at ยง3 for open games, ยง5 for the compositionality theorem.
arXiv:1603.04641
Nash equilibrium is a compositional predicate: if each sub-game is in equilibrium given its context, the whole game is in equilibrium. Games compose like programs.
The Handshake