# What is the definition of “Winning Strategy” in an Ehrenfeucht-Fraïssé game?

I've read many descriptions and applications of a Winning Strategy, as much as many for a Strategy tout court, but when a formal, algebraic definition is called upon, I've found close to no input.

I recall that an Ehrenfeucht-Fraïssé game involves two players, namely spoiler and duplicator, and it is used to compare the similarities about two structures and also to inspect the power of expression in a first-order environment of such structures. The Ehrenfeucht theorem then states that "given two $S$-structures $\mathfrak A$ and $\mathfrak B$, with A$\cap$B=$\emptyset$, with $S$ a finite signature, the following expressions are equivalent:

$(I_i)_{i\leq n}$:$\mathfrak A\cong_f \mathfrak B$.

$\mathfrak A \equiv_n \mathfrak B$.

Duplicator has a Winning Strategy for an Ehrenfeucht-Fraïssé game."

Therefore my request for a proper definition of a Winning Strategy. Thank you.

A precise formal definition of a (winning) strategy for Duplicator really is not very enlightening. A strategy would tell how Duplicator should play given the position of the current play of the game. Each play of the game is essentially a sequence in $A \cup B$:
$$\begin{array}{r|cccccccc} \text{Spoiler} & c_0 & & c_2 & & c_4 & & \cdots & & c_{2k-2} \\ \hline \text{Duplicator} & & c_1 & & c_3 & & c_5 & & \cdots & & c_{2k-1} \end{array}$$ where $c_{2i} \in A$ iff $c_{2i+1} \in B$. What Duplicator wants to do is preserve the play encapsulating a partial isomorphism between $\mathfrak{A}$ and $\mathfrak{B}$. Namely, for each $i < k$ we define $$a_i = \begin{cases} c_{2i}, &\text{if }c_{2i} \in A \\ c_{2i+1}, &\text{otherwise} \end{cases} \qquad b_i = \begin{cases} c_{2i+1}, &\text{if }c_{2i+1} \in B \\ c_{2i}, &\text{otherwise} \end{cases} \quad$$ and consider the mapping $a_i \mapsto b_i$. If this is a partial isomorphism between $\mathfrak{A}$ and $\mathfrak{B}$ we require that the strategy tells Duplicator how to respond to any possible next move of Spoiler. In a bit more formality, for each $a \in A$ the strategy will return some $$\sigma ( c_0 , c_1 , \ldots , c_{2k-1} , a ) \in B$$ such that extending the partial isomorphism above by the $a \mapsto \sigma ( c_0 , c_1 , \ldots , c_{2k-1} , a )$ is also a partial isomorphism, and (analogously) for any $b \in B$ the strategy returns some $$\sigma ( c_0 , c_1 , \ldots , c_{2k-1} , b ) \in A$$ such that extending the partial isomorphism above by the $\sigma ( c_0 , c_1 , \ldots , c_{2k-1} , b ) \mapsto b$ is also a partial isomorphism.
A proper formal definition of a winning strategy for Duplicator will then talk about a function $\sigma$ with domain the set of all odd-length sequences (of length $<2n$) in $A \cup B$ (or perhaps $(A \times \{ A \} ) \cup ( B \times \{ B \} )$ to ensure a disjoint union) such that for any $( c_0 , c_2 , \ldots , c_{2k-1} , c_{2k} )$ in the domain we have that $$\sigma ( c_0 , c_2 , \ldots , c_{2k-1} , c_{2k} ) \in A \quad \Leftrightarrow \quad c_{2k} \in B$$ and if the initial segment of this sequence of length $2k$ encapsulates a partial isomorphism between $\mathfrak{A}$ and $\mathfrak{B}$, as described above, then the extension of this function in the manner described above is also a partial isomorphism.