Hi Can any experts help with this Statistic question(Game Theory)? Thanks! Theor
ID: 3354205 • Letter: H
Question
Hi Can any experts help with this Statistic question(Game Theory)? Thanks!
Theorem 1 In a progressively bounded impartial combinatorial game under
normal play, X = N UP. That is, from any initial position, one of the players
has a winning strategy. Moreover:
P: Every move leads to N.
N: Some move leads to P (hence cannot contain terminal positions).
Let now be P' and N' disjoint subsets of X (set of positions) such that X =N'UP' and P': Every move leads to N' , N': Every move leads to P'.
Show that N=N' and P=P'
Explanation / Answer
Proof. We proceed by induction on B(x).
Certainly, for all x such that B(x) = 0, we have that x P0 P. Assume
the theorem is true for those positions x for which B(x) n, and consider
any position z satisfying B(z) = n + 1. Any move from z will take us to a
position in N P by the inductive hypothesis.
There are two cases:
Case 1: Each move from z leads to a position in N. Then z lies in one of
the sets Pi by definition, and thus is in P.
Case 2: If it is not the case that every move from z leads to a position in
N, it must be that there is a move from z to some P-position. In this case,
by definition, z N.
Hence, all positions lie in N P
We claim that
N=N' and P=P'
To show this, we need to show first that t Pˆ for every terminal position t.
Second, that for all x Nˆ, there exists a move from x leading to Pˆ. Finally,
we need to show that for every y Pˆ, all moves from y lead to Nˆ.