(CoL)

Section 2** **

**Games**

2.1 The two players

2.3 Constant games

2.4 Not-necessarily-constant games

2.5 Static games

2.1 The two players

The CoL games are between two players, called Machine and Environment (not always capitalized, and may take articles). On the picture below we see a few other names for these players.

We will be using and as symbolic names for Machine and Environment, respectively. is a deterministic mechanical device only capable of following algorithmic strategies. ’s strategies, on the other hand, are arbitrary. Throughout this article, we shall consistently use the green color to represent Machine, and red for Environment. As seen from the picture, our sympathies are with the machine. Why should we be fans of the machine even when it is us who act in the role of its “evil” environment? Because the machine is a tool, and what makes it valuable as such is exactly its being a good player. In fact, losing a game by the machine means that it is malfunctioning. Imagine Bob using a computer for computing the “28% of *x*” function in the process of preparing his US federal tax return. This is a game where the first move is by Bob, consisting in inputting a number *m* and meaning asking his machine the question “what is 28% of *m*?”. The machine wins iff it answers by the move/output *n* such that *n*=0.28*m*. Of course, Bob does not want the machine to tell him that 27,000 is 28% of 100,000. In other words, he does not want to win against the machine. For then he could lose the more important game against Uncle Sam.

2.2 Moves, runs and positions

Machine and Environment interact with each other through mutually observable *actions*. We will be using the term “move” instead of “action”. Looking back at the ordinary Turing machine model, it is about games where only two moves are made: the first move, called “input”, is by the environment, and the second move, called “output”, is by the machine. ** **

We agree on the following:

- A
is any finite string over the keyboard alphabet. We will be using α, β, γ as metavariables for moves.*move* - A
is a move a together with one of the two colors*colored move**green*or*red*, with the color indicating which player has made the move. We shall write such a move as α or α,*.*Often we omit the word “colored” and simply say “move”. The letter λ - A
is a (finite or infinite) sequence of colored moves. We will be using Γ,Δ,Ω,Σ as metavariables for runs.*run* - A
is a finite run. We will be using Φ, Ψ, Ξ as metavariables for positions.*position* - We will be writing runs and positions as 〈α, β, γ〉, 〈Φ〉, 〈Φ, Ψ, β, Γ〉, etc. The meanings of such expressions should be clear. For instance, 〈Φ, Ψ, β, Γ〉
- 〈
.*empty position*

2.3 Constant games

A ** gamestructure** is a nonempty set

**Lr**of runns, called

**, satisfying the condition that a run is in**

*legal runs***Lr**iff so are all finite initial segments of it.

**The empty position 〈**

**〉**

**is thus always legal. The runs that are not in**

**Lr**are said to be

**. An**

*illegal*

*illegal***in a given position 〈Φ〉 is a move λ such that 〈Φ,λ〉**

*move***is illegal. The player who made the first illegal move in a given run is said to be the**

**. Intuitively, illegal moves can be thought of as moves that cannot or should not be made. Alternatively, they can be seen as actions that cause the system to crash (e.g., requesting to divide a number by**

*offender***0**).

Gamestructures can be visualized as upside-down trees where the nodes represent positions. Each edge is labeled with a colored move. Such an edge stands for a legal move in the position represented by the upper node of it. Here is an example:

**Figure 2.3.1: **A gamrestructure

This gamestructure consists of the following 16 runs: 〈** **〉, 〈α〉, 〈β〉, 〈γ〉, 〈α, β〉, 〈α, γ〉, 〈β, α〉, 〈γ, α〉, 〈γ,β〉,** **〈γ, γ〉, 〈α, γ,β〉, 〈α, γ,γ〉,** **〈γ, α, β〉, 〈γ, α, γ〉, 〈γ, β, α〉, 〈γ, γ, α〉. All of the infinitely (in fact, uncountably) many other runs are illegal. An example of an illegal run is 〈γ, γ, β, β, α〉. The offender in it is Environment, because the offending third move is red.

Let **Lr** be a gamestructure. A *content** on***Lr** is a function **Wn**: **Lr** **{**,**}**. When **Wn**〈Γ〉 = , we say that Γ is ** won** by the machine (and

**by the environment); and when**

*lost***Wn**〈Γ〉 =, we say that Γ is won by the environment (and lost by the machine). We extend the domain of

**Wn**to all runs by stipulating that an illegal run is always lost by the offender. Since we are fans of Machine, the default meaning of just “won” (or “lost”) is “won (or lost) by the machine”.

**Definition 2.3.2** A *constant game**G* is a pair **(Lr**^{G}**,Wn**^{G}**)**, where **Lr**^{G}** **is a gamestructure, and **Wn*** ^{G}* is a content on

**Lr**

*.*

^{G}Given a constant game G, we will be using the notation Lp^{G} ("legal positions of G") to mean the set {Φ | Φ is finite and Φ∈**Lr*** ^{G}*}. In order to define the gamestructure

^{}component of G, it is sufficient to simply define Lp

^{G}. The latter uniquely extends to

**Lr**

*because, as implied by our definition of gamestructures, a run is in*

^{G }**Lr**

*iff all of its finite initial segments are in*

^{G}**Lp**

*.*

^{G}Figure 2.3.3 below shows a constant game of the structure of Figure 2.3.1:

**Figure 2.3.3:** A constant game

Here the winner in each position is indicated by the color of the corresponding node. So, for instance, the run 〈γ, α, β〉 is won by the machine; but if this run had stopped after its second move, then the environment would be the winner. Of course, such a way of indicating winners is not sufficient if there are infinitely long branches (legal runs), for such branches do not have “the corresponding nodes”.

We say that a constant game is ** strict** iff, in every legal position, at most one of the two players has legal moves. Our games generally are not strict. For instance, in the start position of the game of Figure 2.3.3, both players have legal moves. We call such (not-necessarily-strict) games

**. Free games model real-life situations more directly and naturally than strict games do. Hardly many tasks that humans, computers or robots perform are strict. Imagine you are playing chess over the Internet on two boards against two independent adversaries that, together, form the (one) environment for you. Let us say you play white on both boards. Certainly in the initial position of this game only you have legal moves. However, once you make your first move --- say, on board #1 --- the picture changes. Now both you and the environment have legal moves, and who will be the next to move depends on who can or wants to act sooner. Namely, you are free to make another opening move on board #2, while the environment --- adversary #1 --- can make a reply move on board #1. A strict-game approach would have to impose some not-very-adequate supplemental conditions uniquely determining the next player to move, such as not allowing you to move again until receiving a response to your previous move. Let alone that this is not how the real two-board game would proceed, such regulations defeat the very purpose of the idea of parallel/distributed computations with all the known benefits it offers.**

*free*Because our games are free, strategies for them cannot be defined as functions from positions to moves, because, in some positions (such as the root position in the game of Figure 2.3.3) both players may have legal moves and, if both are willing to move, which of them acts sooner will determine what will be the next move.

The exact meaning of “strategy” will be defined later, but whatever it means, we can see that the machine has a winning strategy in the game of Figure 2.3.3, which can be put this way: *Regardless of what the adversary is doing or has done, go ahead and make move *α*; make *β* as your second move if and when you see that the adversary has made move *γ*, no matter whether this happened before or after your first move*”. This strategy obviously guarantees that the machine will not offend. There are 5 possible legal runs consistent with it, i.e., legal runs that could be generated (depending on how the environment acts) when it is followed by the machine: 〈α〉, ** **〈α, β〉,** **〈β, α〉,** **〈α, γ, β〉 ** **and** **〈γ, α, β〉. All are won by the machine.

Let *G* be a constant game. *G* is said to be ** finite-depth** iff there is a (smallest) integer

*d*, called the

**of**

*depth**G*, such that the length of every legal run of

*G*is ≤

*d*. And

*G*is

**iff every legal run of it is finite, even if there are arbitrarily long legal runs. Let us call a legal run Γ of**

*perifinite-depth**G*

**iff Γ is not a proper initial segment of any other legal run of**

*maximal**G*. Then we say that

*G*is

**iff the total number of maximal legal runs of**

*finite-breadth**G*, called the

**of**

*breadth**G*, is finite. Note that, in a general case, the breadth of a game may be not only infinite, but even uncountable.

*G*is said to be (simply)

**iff it only has a finite number of legal runs. Of course,**

*finite**G*is finite only if it is finite-breadth, and when

*G*is finite-breadth, it is finite iff it is finite-depth iff it is perifinite-depth.

As noted in Section 2.2, computational problems in the traditional sense are nothing but functions (to be computed). Such problems can be seen as the following types of games of depth 2:

**Figure 2.3.4:** The “successor” game

- Why is the root green here? Because it corresponds to the situation where there was no input. The machine has nothing to answer for, so it wins.
- Why are the 2
^{nd}level nodes red? Because they correspond to situations where there was an input but no output was generated by the machine. So the machine loses. - Why does each group of 3
^{rd}level nodes has exactly one green node? Because a function has exactly one (“correct”) value for each argument. - What particular function is this game about? The successor function:
*f*(*n*)=*n*+1.

Once we agree that computational problems are nothing but games, the difference in the degrees of generality and flexibility between the traditional approach to computational problems and our approach becomes apparent and appreciable. What we see in Figure 2.3.4 is indeed a very special sort of games, and there is no good call for confining ourselves to its limits. In fact, staying within those limits would seriously retard any more or less advanced and systematic study of computability.

First of all, one would want to get rid of the “one green node per sibling group” restriction for the third-level nodes. Many natural problems, such as the problem of finding a prime integer between *n* and 2*n*, or finding an integral root of *x*^{2}-2*n*=0, may have more than one as well as less than one solution. That is, there can be more than one as well as less than one “right” output on a given input *n*.

And why not further get rid of any remaining restrictions on the colors of whatever-level nodes and whatever-level arcs. One can easily think of natural situations where, say, some inputs do not obligate the machine to generate an output and thus the corresponding 2^{nd} level nodes should be green. An example would be the case where the machine is computing a partially-defined function *f* and receives an input *n* on which *f* is undefined.** **

So far we have been talking about generalizations within the depth-2 restriction, corresponding to viewing computational problems as very short dialogues between the machine and its environment. Permitting longer-than-2 or even infinitely long runs would allow us to capture problems with arbitrarily high degrees of interactivity and arbitrarily complex interaction protocols. The task performed by a network server is an example of an infinite dialogue between the server and its environment **---** the collection of clients, or let us just say the rest of the network.

It also makes sense to consider “dialogues” of lengths less than 2. “Dialogues” of length 0, i.e. games of depth 0 are said to be ** elementary**. There are exactly two elementary constant games, denoted by and :

Note that the symbols and ** **thus have dual meanings: they may stand for the two elementary games as above, or for the corresponding two players. It will usually be clear from the context which of these two meanings we have in mind.

Just like classical logic, CoL sees no extensional distinction between “snow is white” and , or between “snow is black” and : All true propositions, as games, are , and all false propositions are . In other words, a proposition is a game automatically won by the machine when true and lost when false. This way, CoL’s concept of a constant game is a generalization of the classical concept of a proposition.

2.4 Not-necessarily-constant games

We fix an infinite set *Variables* = {*var*_{1}, *var*_{2}, *var*_{3},… } of ** variables**. As usual, lowercase letters near the end of the Latin alphabet will be used to stand (as metavariables) for variables. We further fix the set

*Constants*= {0,1,2,3,…} of decimal numerals, and call its elements

**. With some abuse of concepts, we shall often identify constants with the numbers they represent.**

*constants*A ** universe** (of discourse) is a pair

*U*= (Dm, Dn), where Dm, called the

**of**

*domain**U*, is a nonempty set, and Dn, called the

**of**

*denotator**U*, is a (total) function of type

*Constants*Dm. The elements of Dm will be referred to as the

**of**

*individuals**U*. The intuitive meaning of

*d*=Dn(

*c*) is that the individual

*d*is the

**of the constant**

*denotat**c*and thus

*c*is a

**(or**

*name***) of**

*code**d*. So, the function Nm from Dm to the powerset of

*Constants*satisfying the condition

*c*∈Nm(

*d*) ⇔

*d*=Dn(

*c*) can be called the

*naming function*of

*U*. Of course, whenever convenient, a universe can be characterized in terms of its naming function rather than denotation function.

A universe (Dm, Dn) is said to be *ideal*** **iff Dn

**is a bijection. Generally, in a not-necessarily-ideal universe, some individuals may have unique names, some have many names, and some have no names at all. Real-world universes are seldom ideal: not all people living or staying in the United States have social security numbers; most stars and planets of the Galaxy have no names at all, while some have several names (Morning Star = Evening Star = Venus); etc. A natural example of an inherently non-ideal universe from the world of mathematics would be the one whose domain is the set of real numbers, only some of whose elements have names, such as 5, 1/3, √2 or π. Generally, even if the set of constants was not fixed, no universe with an uncountable domain would be “ideal” for the simple reason that there can only be countably many names. This is so because names, by their very nature and purpose, have to be finite objects. Observe also that many properties of common interest, such as computability or decidability, are usually sensitive with respect to how objects (individuals) are named, as they deal with the names of those objects rather than the objects themselves. For instance, strictly speaking, computing a function**

*f*(

*x*) means the ability to tell, after seeing a (the) name of an arbitrary object

*a*, a (the) name of the object

*b*with

*b*=

*f*(

*a*). Similarly, an algorithm that decides a predicate

*p*(

*x*) on a set

*S*, strictly speaking, takes not elements of

*S*--- which may be abstract objects such as numbers or graphs --- but rather names of those elements, such as decimal numerals or codes. It is not hard to come up with a nonstandard naming of the natural numbers through decimal numerals where the predicate “

*x*is even” is undecidable. On the other hand, for any undecidable arithmetical predicate

*p*(

*x*), one can come up with a naming such that

*p*(

*x*) becomes decidable --- for instance, one that assigns even-length names to all

*a*with

*p*(

*a*) and assigns odd-length names to all

*a*with

**p(**

*a*). Classical logic exclusively deals with individuals of a universe without a need to also consider names for them, as it is not concerned with decidability or computability. CoL, on the other hand, with its computational semantics, inherently calls for being more careful about differentiating between individuals and their names, and hence for explicitly considering universes in the form (Dm, Dn) rather than just Dm as classical logic does.

The standard universe is the ideal universe whose domain is the set of natural numbersm and whose denotator is the function that sends every constant to the number represented by that constant in decimal notation.

Where *Vr* is a set of variables and *Dm* is the domain of some universe, by a (*Vr**,Dm*)-** valuation** we mean a (total) function

*e*of type

*Vr*

*Dm*. Where x

_{1},..., xn are all the variables of Vr listed according to their lexicographic order, such a valuation e can be simply written as an n-tuple (a

_{1},..., an), meaning that e(x

_{1})=a

_{1},...,e(xn)=an. When

*Vr*and

*Dm*are clear from the context, we may omit an explicit reference to them and simply say “valuation”. References to a universe

*U*or its components can be similarly omitted when talking about individuals, denotats, names or some later-defined concepts such as those of a game or a function.

**Definition**** 2.4.1 **Let *n* be a natural number. An *n*-ary ** game** is a quadruple (Dm,Dn,Vr,G), where (Dm,Dn) is a universe, Vr is a set of

*n*distinct variables, and G is a mapping which sends every (Vr,Dm)-

^{}**e to a constant game G(e).**

*valuation*^{}Given a game (Dm,Dn,Vr,G), we refer to Dm as the domain of the game, refer to Dn as the denotator of the game, refer to the elements of Vr as the variables on which the game ** depends** (or simply "the variables of" the game), and refer to G as the extension of the game. We further refer to the pair Un=(Dm,Dn) as the

**the game**

*universe of**;*correspondingly, the game can be simply written as the triple (Un,Vr,G) rather than the quadruple (Dm,Dn,Vr,G).

In classical logic, under an intensional (variable-sensitive) understanding, the definition of the concept of an

*n*-ary predicate would look exactly like our definition of an

*n*-ary game after omitting the (now redundant) denotator component, with the only difference that there the extension function returns propositions rather than constant games. And, just like propositions are nothing but 0-ary predicates, constant games are nothing but 0-ary games. Thus, games generalize constant games in the same way as predicates generalize propositions. And, as constant games are generalized propositions, games are generalized predicates.

In formal contexts, we choose a similar intensional approach to functions. The definition of a function *f* below is literally the same as our definition of a game *G*, with the only difference that the extension component is now a mapping of (Vr,Dm* ^{}*)-valuations to Dm

*(rather than to constant games).*

^{}**Definition 2.4.2 **Let *n* be a natural number. An *n*-ary ** function** is a tuple (Dm,Dn

**,**Vr,f), where (Dm,Dn) is a universe, Vr is a set of

*n*distinct variables, and f is a mapping which sends every (Vr,Dm)

**-**

^{}**to an element f(e) of Dm.**

*valuation*^{}Just like in the case of games, we customarily use the same name f for a function (Dm,Dn**,**Vr,f) as for its last component. We refer to the elements of Vr as the variables on which the function *f* ** depends**, refer to Dm as the

*domain of**f*, etc.

Given a game (Dm,Dn,Vr,G), a set X of variables with Vr⊆*X *and an (*X***,**Dm* ^{}*)-valuation

*e*, we write

*G*(e) to mean the constant game G(g), where g

*is the restriction of*

*e*to Vr

*(i.e.,*

*the*

*(Vr*

**,**Dm

*)-valuation that agrees with*

^{}*e*on all variables from Vr). Such a constant game

*G*(e) is said to be an

**of**

*instance**G.*Also, for readability, we usually write

**Lr**

*and*

_{e}^{G}**Wn**

*instead of*

_{e}^{G}**Lr**

^{G(e)}and

**Wn**

^{G(e)}. Similarly, given a function (Dm,Dn

**,**Vr,f), a set X of variables with Vr⊆

*X*and an (

*X,*Dm

*)-valuation*

^{}*e*, we write

*f*(e) to denote the individual f(g) to which f maps g, where

*g*

*is the restriction of*

*e*to Vr.

*eleme***iff so are all of its instances. Thus, games generalize elementary games in the same sense as constant games generalize the constant elementary games and . In turn, (not-necessarily constant) elementary games generalize constant elementary games in the same sense as predicates generalize propositions in classical logic. So, just like we identify constant elementary games with propositions, we will identify elementary games with predicates. Specifically, in the context of a given universe (Dm,Dn), we understand a predicate**

*ntary**p*on Dm as the elementary game (Dm,Dn,Vr,

*G*), where Vr is the set of variables on which p depends, and G is such that, for any (Vr,Dm)-valuation

*e*,

**Wn**

*〈*

_{e}^{G}**〉= iff**

*p*is true at

*e*. And vice versa: An elementary game

*G*will be understood as the predicate

*p*which depends on the same variables as

*G*and which is true at a given valuation

*e*iff

**Wn**

*〈*

_{e}^{G}**〉= .**

**Convention 2.4.3 **Assume *U=*(*Dm,Dn*) is a universe, a∈Dm, *c*∈*Constants * and *x*∈Variables. We shall write *a ^{U }* mean the nullary function (Dm,Dn,∅,

*f*) such that

f()=a,

*write c*to mean the nullary function (Dm,Dn,∅,

^{U}*f*) such that f()=Dn(

*c*), and write

*x*to mean the unary function (Dm,Dn,{x},

^{U}*f*) such that, for any ({x},Dm)-valuation

*e*, f(

*e*)=

*e*(

*x*).

**Convention 2.4.4** Assume K=(Dm,Dn,Vr,K) is a function [resp. game]. Following the standard readability-improving practice established in the literature for functions and predicates, we may fix a tuple (*x*_{1},…,*x*_{n}) of pairwise distinct variables for K when first mentioning it, and write *K* as K(*x*_{1},…,*x*_{n}). When doing so, we do not necessarily mean that {*x*_{1},…,*x*_{n}}=Vr. Representing K as K(*x*_{1},…,*x*_{n}) sets a context in which, for whatever functions *f*_{1}=(Dm,Dn,Vr_{1},*f*_{1}), ..., f_{n}=(Dm,Dn,Vr_{n},*f*_{n}), we can write K(f_{1},…,*f*_{n}) to mean the function [resp. game] (*Dm,Dn,Vr',K'*)* *such that:

- Vr'=(Vr
*x*_{1},…,*x*_{n}})∪Vr_{1}∪…∪Vr_{n}^{};^{}

- For any (Vr',Dm)-valuation
*e*', K'(e')=K(e), where*e*is the (Vr,Dm)-valuation such that*e*(*x*_{1})=f_{1}(e'), …,*e*(*x*_{n})=f_{n}(e') and e agrees with e' on all other variables from Vr.

Further, we allow for any of the above “functions” *f _{i}* to be written as just an individual a, just a constant

*c*or just a variable

*x*. In such a case,

*f*should be correspondingly understood as the 0-ary function the 0-ary function

_{i}*a*, the 0-ary function

^{U}

^{}*c*or the unary function

^{U}*x*, where

^{U}*U*=(Dm,Dn). So, for instance,

*K*(0,

*x*) is our lazy way to write

*K*(0

*,*

^{U}*x*).

^{U}The entities that in common language we call games are at least as often non-constant as constant. Board games such as chess and checkers are examples of constant games. On the other hand, almost all card games are more naturally specified as non-constant games: each session/instance of such a game is set by a particular permutation of the card deck, and thus the game can be understood as a game that depends on a variable

*x*ranging over the possible settings of the deck. Even the game of checkers has a natural non-constant generalization

*Checkers*(

*x*) with

*x*ranging over positive even integers, meaning a play on the board of size

*x*×

*x*where, in the initial position, the first 1.5

*x*black cells are filled with white pieces and the last 1.5

*x*black cells with black pieces. Then the ordinary checkers can be written as

*Checkers*(8). Furthermore, the numbers of pieces of either color also can be made variable, getting an even more general game

*Checkers*(

*x*,

*y*,

*z*), with the ordinary checkers being the instance

*Checkers*(8,12,12) of it. By allowing rectangular-shape boards, we would get a game that depends on four variables, etc. Computability theory also often appeals to non-constant games to illustrate certain complexity-theoretic concepts such as alternating computation or PSPACE-completeness. The so called Formula Game or Generalized Geography are typical examples. Both can be understood as games that depend on a variable

*x*, with

*x*ranging over quantified Boolean formulas in Formula Game and over directed graphs in Generalized Geography.

Consider a game *G*. What we call a ** unilegal** run of

*G*is a run which is a legal run of all instances of

*G*. We say that

*G*is

*unistructural***iff all legal runs of all of its instances are unilegal runs of G. The class of unistructural games is known to be closed under all game operations studies in CoL.**

^{[Jap03] }While natural examples of non-unistructural games exist such as the games mentioned in the above paragraph, virtually all other examples of particular games discussed elsewhere in the present article are unistructural.

Non-constant games, as long as they are unistructural, can be visualized as trees in the earlier seen style, with the difference that the nodes of the tree can now be labeled with predicates rather than only propositions (colors) as before. For any given valuation *e*, each such label *L* is telling us the color of the node. Namely, the *L*-labeled node is green if *L* is true at *e*, and red if *L* is false.

**Figure 2.3.5:** The “generalized successor” game

The above figure shows a game which depends on *x*. Specifically, for every valuation *e*, the game is about computing the function* f _{e}*, defined by

*f*(

_{e}*n*) =

*n*+

*e*(z) (“the zth successor of

*n*”).

**Note that we have different functions and thus different constant games for different valuations**

*e*here.

Denoting the game of Figure 2.3.5 by *G*(*x*), the game of Figure 2.3.4 can be seen to be the instance *G*(1) of it. The latter results from replacing z by 1 in Figure 2.3.5. This replacement turns every label *m*=*n*+*z* into the proposition *m=n*+1, i.e., into (green filling) or (red filling).

2.5 Static games

In the particular games that we have seen so far or will see in the subsequent sections, when talking about the existence of a winning strategy or the absence of thereof, the question about the (relative) speeds of the players was never relevant. That is because all those games share one nice property, called the *static* property. Games with this property are (also) said to be static. Below are some intuitive characterizations of this important class of games.

- Static games are games where the speed of the adversary is not an issue: if a player has a winning strategy, the strategy will remain good no matter how fast its adversary is in making moves. And if a player does not have a winning strategy, it cannot succeed no matter how slow the adversary is.
- Static games are games where “it never hurts a player to postpone making moves” (Blass’ words from his AMS review of [Jap03]).
- Static games are contests of intellect rather than speed. In such games, what matters is
*what*to do (strategy) rather than*how fast*to do (speed).

The games that are not static we call ** dynamic**. The following games are dynamic:

In either game, the player who is quick enough to make the first move becomes the winner. And asking whether Machine has a winning strategy is not really meaningful: whether Machine can win or not depends on the relative speeds of the two players. In a sense, *B* is even “worse” than *A*. Just like in *A*, it would not be a good idea for Machine to wait, because, unless Environment is stupid enough to also decide to wait, Machine will lose. Let us now say that Machine goes ahead and initiates the first move. What may happen in *B* is that Environment moves before Machine actually completes its move. This will make Machine not only the loser but also the offender. Machine cannot even be sure that its move will be legal! If communication happens by exchanging messages through a (typically) asynchronous network, that often has some unpredictable delays, this can also be a contest of luck: assuming that the arbitration is done by Environment or a third party who is recording the order of moves, it is possible that Machine makes a move earlier than Environment does, but the message carrying that move is delivered to the arbiter only after Environment’s move arrives, and the arbiter will be unable to see that it was Machine who moved first. An engineering-style attempt to neutralize this problem could be to let all moves carry timestamps. But this would not save the case: even though timestamps would correctly show the real order of moves by each particular player, they could not be used to compare two moves by two different players, for the clocks of the two players would never be perfectly synchronized.

Another attempt to deal with problems in the above style could be to assign to each player, in a strictly alternating order, a constant-length time slot during which the player has exclusive access to the communication medium. Let alone that this could introduce some unfair asymmetry in favor of the player who gets the first slot, the essence of the problem would still not be taken care of: some games would still essentially depend on the relative speeds of the two players, even if arguably no longer on the speed of the network.

Formally, the concept of static games is defined in terms of “delays”. We say that run Δ is a ** green** (resp.

**)**

*red***of run Γ iff the following two conditions are satisfied:**

*delay*- The moves of either color are arranged in Γ in the same order as in Δ.
- For any
*n*,*k*≥1, if the*k*th red (resp. green) move is made earlier than the the*n*th green (resp. red) move in Γ, then so is it in Δ.

In other words, Δ is the result of shifting to the right (“delaying”) some green (resp. red) moves in Γ without violating their order.

Example: 〈0,2,1,3,4,5,7,8,6,10,9〉 is a green delay of 〈0,1,2,3,4,5,6,7,8,9,10〉.** ** The former is obtained from the latter by shifting to the right some green moves. When doing so, a green move can jump over a red move, but one green move cannot jump over another green move.

Now, we say that a constant game *G* is ** static** (or that it has the static property) iff, for either player (color)

*P*and any runs Γ and Δ such that Δ is a

*P*delay of Γ, in the context of

*G*, the following two conditions are satisfied:

- If Γ is won by
*P*, then so is Δ. - If
*P*does not offend in Γ, then neither does it in Δ.

This concept extends to all games by stipulating that a not-necessarily-constant game is static iff so are all of its instances.

All game operations studied in CoL have been shown to preserve the static property of games.^{[Jap03] }So, as long as the atoms of an expression represent static games, so does the whole expression. One natural subset of all static games is the closure of elementary games under the operations of CoL.

As already noted, CoL restricts its attention to static games only (at least, at its present stage of development). To see why static games are really what CoL is willing to call “pure” computational problems, imagine a play over the delay-prone Internet. If there is a central arbiter (which can be located either in one of the players' computer or somewhere on a third, neutral territory) recording the order of moves, then the players have full access to information about the official version of the run that is being generated, even though they could suffer from their moves being delivered with delays. But let us make the situation even more dramatic: assume, as this is a typical case in distributed systems, that there is no central arbiter. Rather, each players’ machine records moves in the order it receives them, so that we have what is called distributed arbitration. Every time a player makes a move, the move is appended to the player’s internal record of the run and, at the same time, mailed to the adversary. And every time a message from the adversary arrives, the move contained in it is appended to the player’s record of the run. The game starts. Seeing no messages from Environment, Machine decides to go ahead and make an opening move α**.**_{ }As it happens, Environment also decides to make an “opening” move β. The messages carrying α and β cross. So, after they are both delivered, Machine’s internal records show the position 〈α,β〉, while Environment thinks that the current position is 〈β,α〉. Both of the players decide to make two consecutive new moves: γ,δ** **and ε,ω, respectively, and the two pairs of messages, again, cross.

After making their second series of moves and receiving a second series of “replies” from their adversaries, both players decide to make no further moves. The game thus ends. According to Machine’s records, the run was 〈α,β,γ,δ,ε,ω〉, while Environment thinks that the run was 〈β,α,ε,ω,γ,δ〉. As for the “real run”, i.e. the real order in which these six moves were made (if this concept makes sense at all), it can be yet something different, such as, say, 〈β,α,γ,ε,δ,ω〉. A little thought can convince us that in any case the real run, as well as the version of the run seen by Environment, will be a green delay of the version of the run seen by Machine. Similarly, the real run, as well as the version of the run seen by Machine, will be a red delay of the version of the run seen by Environment. Hence, provided that the game is static, either player can fully trust its own version of the run and only care about making good moves for this version, because regardless of whether it shows the true or a distorted picture of the real run, the latter is guaranteed to be successful as long as the former is. Moreover: for similar reasons, the player will remain equally successful if, instead of immediately appending the adversary's moves to its own version of the run, it simply queues those moves in a buffer as if they had not arrived yet, and fetches them only later at a more convenient time, after perhaps making and appending to its records some of its own moves first. The effect will amount to having full control over the speed of the adversary, thus allowing the player to select its own pace for the play and worry only about what moves to make rather than how quickly to make them.

Thus, static games allow players to make a full abstraction from any specific assumptions regarding the type of arbitration (central or distributed), the speed of the communication network and the speed of the adversary: whatever strategy they follow, it is always safe to assume or pretend that the arbitration is fair and unique (central), the network is perfectly accurate (zero delays) and the adversary is “slow enough”. On the other hand, with some additional thought, we can see that if a game is not static, there will always be situations whre no particular one of the above three sorts of abstractions can be made. Specifically, such situations will emerge every time when a player *P*’s strategy generates a *P*-won run that has some *P*-lost *P*-delays.