[FOM] Polynomial Games

[Harvey Friedman]

I wrote:

> Let P:[0,1]^2k into [a,b] be a polynomial with rational coefficients.
>
> We let G(P,t) be the following two person game.
>
> Alice and Bob alternately play k moves, where each move is an element
> of [0,1].
>
> Let x,y in [0,1]^k, where Alice's moves form x, and bob's moves form  
> y.
>
> Alice wins if P(x,y) > t. Bob wins if P(x,y) <= t.

There is a well defined notion of the "value" of the game G(P).

Because we are in a nice compact situation, the value of the game at  
any stage of the play of the game, is continuous. From this we see  
that there is a best possible first move for Alice. In particular,  
there is a largest t such that Alice wins G(P,t).

What happens if we throw a computer package in to determine close  
approximations to the value of G(P)? I would guess that when we are in  
dimension 2k (i.e., there are k moves for each player), and the  
polynomial is nontrivial, then the computer packages will blow up  
badly, and give almost no information about the value of the game.

HOWEVER, note that the associated Tarski formula for, e.g., "the value  
of the game is at least 1/2" is very simple and short:

(therexists x1)(forall y1)...(therexists xk)(forall yk) 
(P(x1,y1,...,xk,yk) > 1/2).

You just have to fall in love with some polynomials P from [0,1]^2k  
with rational coefficients to have some lovable hard problems with  
presumably very small k.

If I am wrong about how hard these problems are, then we can move to

piecewise polynomials with rational coefficients
rationally semialgebraic functions
piecewise linear on the integers with integer coefficients
Presburger functions

Discontinuities should make things yet harder.

The last two stay within Presburger arithmetic.

Harveys