927: Order Invariant Games/1

Fri Mar 4 09:11:51 EST 2022

I made some FOM postings on games recently:

https://cs.nyu.edu/pipermail/fom/2022-January/023084.html
https://cs.nyu.edu/pipermail/fom/2022-February/023159.html
and one pending

The basic motivation of the first was theoretical. The basic
motivation for the second was to raise the question of how well AI can
play NIM, humans playing NIM perfectly. The pending posting discusses
a way of systematically generalizing NIM and asking the corresponding
questions, aimed at both AI and theory.

I decided to strengthen the last two postings on both fronts here.

Let R be any binary relation. I.e., any set of ordered pairs. There is
an associated game G(R,x), x in fld(R), in which Alice and Bob
alternatively play, with Alice starting with x, and thereafter each
player required to play an R successor of the previous move of their
opponent. The player making the last move wins.

Alice (Bob) wins G(R,x) just in case she (he) has a winning strategy.
If neither player has a winning strategy then the game is considered
to be a tie.

THEOREM (von Neumann). For these games, either Alice has a winning
strategy or Bob has a winning strategy or both players have strategies
avoiding losing for them.

ORDER INVARIANT AND ORDER THEORETIC

We focus on two families of subsets of the spaces N^k. These sets are
defined both in terms of invariance and in terms of definability. Here
N is the set of all nonnegative integers.

DEFINITION 1. x,y in N^k are order equivalent if and only if for all
i,j, x_i < x_j iff y_i < y_j.

DEFINITION 2. S contained in N^k is order invariant if and only if for
all order equivalent x,y in N^k, x in S iff y in S.

THEOREM 1. (well known) Let S containedin N^k. The following are equivalent.
i.  S is order invariant.
ii. S is a boolean combination of inequalities xi < xj, for 1 <= i,j <= k.
iii. S is defined by a quantifier free formula without parameters over (N,<).

DEFINITION 3. Let A be contained in N. x,y in N^k are order equivalent
over A if and only if for all i,j,
1) x_i < x_j iff y_i < y_j
2) if x_i in A or y_i in A then x_i = x_j

DEFINITION 4. S contained in N^k is order theoretic if and only if
there is a finite A contained in N such that the following holds. For
all x,y order equivalent over A, x in S iff y in S.

THEOREM 2. (well known) Let S containedin N^k. The following are equivalent.
i.  S is order theoretic.
ii. There is a finite set A contained in N such that the following
holds. S is a boolean combination of inequalities xi < xj, xi < p, p <
xi, for 1 <= i,j <= k, p in A.
iii. S is defined by a quantifier free formula over (N,<), with
parameters from N allowed.

An order invariant (theoretic) relation on N^k is an order invariant
(theoretic) subset of N^2k.

ORDER INVARIANT AND ORDER THEORETIC GAMES ON N^k

NIM is an order invariant game on N^k in the following sense. There is
a simple order invariant relation R on N^k such that playing G(R,x), x
in N^k, is the same as playing NIM with k piles containing x_1,...,x_k
stones respectively. Technically speaking, to be faithful to NIM, we
require x to have only positive coordinates. Even more technically, we
don't allow piles with zero stones, and instead remove the pile. But
these are technicalities and can be safely ignored.

What is the relation? x R y if and only if

x1 > y1 and x2 = y2 and ... and xk = yk; or
x2 > y2 and x1 = y1 and x3 = y3 and ... and xk = yk
...
xk > yk and x1 = y1 and ... and xk-1 = yk-1

Note of course that NIM is therefore given by an order invariant
relation on N^k that is particularly simple among the space of order
invariant relations on N^k

QUESTION 1. Who wins G(R,x) for order invariant R on N^k, or is it a
tie? How simple can the winning and tieing strategies be?
Computational complexity issues? How does AI do?

QUESTION 2.  Same as Question 1 but more generally for order theoretic
R. How does AI do?

This starts to become nontrivial already for k = 2. But I am sure that
with just a little bit of trouble, we can completely understand
Question 1 for k = 2 and with some more trouble completely understand
Question 2, both with low level computational complexity using base 2
representation of the data.

 But already it seems interesting to see if AI can fully handle k = 2
with only being given the R or the R,x. Obviously one needs to be
careful to ensure that this is properly formulated as an AI challenge.

I think things get really interesting starting with k = 3, both
theoretically and AI oriented.

MUCH MORE AMBITIOUS

Use larger classes of binary R on the N^k. The most ambitious of this
character would be the Presburger relations. These are first order
defined over (N,+). But there are many interesting and important
fragments.

##########################################

My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 927th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-899 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

900: Ultra Convergence/2  10/3/21 12:35AM
901: Remarks on Reverse Mathematics/6  10/4/21 5:55AM
902: Mathematical L and OD/RM  10/7/21  5:13AM
903: Foundations of Large Cardinals/1  10/12/21 12:58AM
904: Foundations of Large Cardinals/2  10/13/21 3:17PM
905: Foundations of Large Cardinals/3  10/13/21 3:17PM
906: Foundations of Large Cardinals/4  10/13/21  3:17PM
907: Base Theory Proposals for Third Order RM/1  10/13/21 10:22PM
908: Base Theory Proposals for Third Order RM/2  10/17/21 3:15PM
909: Base Theory Proposals for Third Order RM/3  10/17/21 3:25PM
910: Base Theory Proposals for Third Order RM/4  10/17/21 3:36PM
911: Ultra Convergence/3  1017/21  4:33PM
912: Base Theory Proposals for Third Order RM/5  10/18/21 7:22PM
913: Base Theory Proposals for Third Order RM/6  10/18/21 7:23PM
914: Base Theory Proposals for Third Order RM/7  10/20/21 12:39PM
915: Base Theory Proposals for Third Order RM/8  10/20/21 7:48PM
916: Tangible Incompleteness and Clique Construction/1  12/8/21   7:25PM
917: Proof Theory of Arithmetic/1  12/8/21  7:43PM
918: Tangible Incompleteness and Clique Construction/1  12/11/21  10:15PM
919: Proof Theory of Arithmetic/2  12/11/21  10:17PM
920: Polynomials and PA  1/7/22  4:35PM
921: Polynomials and PA/2  1/9/22  6:57 PM
922: WQO Games  1/10/22 5:32AM
923: Polynomials and PA/3  1/11/22  10:30 PM
924: Polynomials and PA/4  1/13/22  2:02 AM
925: Polynomials and PA/5  2/1/22  9::04PM
926: Polynomials and PA/6  2/1/22 11:20AM

Harvey Friedman