Challenging Ehrenfeucht Fraisse Games being under Game Theory

The result of an Ehrenfeucht Fraisse Game is a foregone conclusion

“Ehrenfeucht Fraisse Games”. Image by GPT-4o and author.

While it may come as surprise to those who study formal logic and mathematics, Ehrenfeucht Fraisse Games come with a bold assumption, which allows for multiple interpretations to coexist at the same time and neither player of the game any the wiser under the standard interpretation of the game itself.

Any the wiser to what?

Any the wiser as to whether they play under the same interpretation or different interpretations.

To investigate that, let us look at the basic definition of an Ehrenfeucht Fraisse Game:

“The main idea behind the game is that we have two structures, and two players — Spoiler and Duplicator. Duplicator wants to show that the two structures are elementarily equivalent (satisfy the same first-order sentences), whereas Spoiler wants to show that they are different” [1]

Let us say that Duplicator wins, and we have the same elementary equivalent structures, as below:

Elementary Equivalent Structure. Image by author.

You might look at those structures and ask: “Don’t they represent the same thing?”

The answer would be “Yes”, and to make that obvious we can project the image onto a linear plane where both structures map to the following:

Logical Structure. Image by author.

But the definition of an Ehrenfeucht Fraisse Game does not say that the same first-order sentences must be under the same theory.

This is a sizable omission within the definition of an Ehrenfeucht Fraisse Game.

Why?

Well, it comes down to what the elements of the structures represent. They do not represent sentences (or theorems) of a theory but concrete elements that are defined by the sentences/theorems themselves.

This is a crucial point, because multiple first-order theories can use the same symbols of logic, the same theorem construction rules, and are what are otherwise known as structures in their own right under model theory.

What this means is that either Ehrenfeucht Fraisse Games (EF Games) may be exploitable or EF Games as they are currently defined allow for ambiguity as to the theories used by the Spoiler and Duplicator subjectively and simultaneously may be (throughout the game) the same, or different by default. There is no way of telling whether the Spoiler or Duplicator are playing by the same rules (same theory) or not only that it is agreed that the structures are elementary equivalent under the same first-order sentences (which we say may be under different theories).

By repeated playing of EF Games between two players, both players may agree, I propose, that each player shares the same interpretation (by sequential and iterative game play resulting in agreement of winning or losing, and shared agreement of the rules/theories), or simply be none the wiser as to whether one or other player uses a different theory (or interpretation) that results in harmonious game play.

Indeed, if Spoiler and Duplicator did not play by using different theories, there would be no game at all. Simply two players would agree on the theory being used and two structures elementary equivalent that trivially identified as for there to be no game.

There would be no fun to it. It would be the same as one person saying: “That box is green” and the other saying “Yes, that box is green”.

Games are characterised by their being an element of surprise, especially if they are non-cooperative, and if an EF Game is not cooperative, then Duplicator must be playing under a different theory, or there would be no element of surprise.

We know this to be true, as in our analogy, nobody knows if “green” to one person is the exact same thing in their mind as “green” in another’s mind until it is tested. What would be a surprise, and is testable, is when a person takes a colour-blind test and realises that they are not seeing the world as others see it.

But Ehrenfeucht Fraisse Games are not like that. The only test is that the two structures satisfy the same first-order sentences. And without agreement up-front as to the theory under which the game is being played, and without communication between players as to the theory they are using, neither player would know if the other player was using the same theory because the game would continue on and winners and losers found, each oblivious to the theory under which the other player used. This, because the game would continue on and for all intents and purposes each player would be making an assumption that the other player was using the same theory because none of the moves would seem out of the normal.

1.1 EF Games don’t sit under Game Theory at all.

There can only be a Duplicator winner in an Ehrenfeucht Fraisse Game if both Spoiler and Duplicator operate over a single structure that is known to be elementary equivalent to two other structures up-front, as below. Otherwise, the game is lost to the Duplicator even before the game starts or the Spoiler and Duplicator are not smart enough to see the elementary equivalence or absence thereof.

If we assume that an Ehrenfeucht Fraisse Game is intended to be zero-sum, we can easily determine that EF Games diverge from games of strategy as the tokens on the board are fixed (the structure under investigation), the structure/model of the theories being used by the Duplicator and Spoiler are fixed, and the only essence of a game is whatever enjoyment one would get by being smart enough to spot the elementary equivalence or lack thereof.

I.e. EF Games have a foregone conclusion the moment the structure under investigation has been selected to initiate the game, and similarly with the theory/ies used by the Duplicator and the Spoiler.

Ehrenfeucht Fraisse Games have a Foregone Conclusion. Image by author.

It does not matter who goes first, or which player plays Spoiler or Duplicator, because if there is no elementary equivalent structure/or-not agreeable to both players up-front, then there is no game worth winning.

To paint an analogy, if two differently worded Google searches came back with the same top-ranking result, then the chances are that the Google search terms were the same or similar. With an Ehrenfeucht Fraisse Game we are talking about concrete elements, and structures as concrete as we can get under formal logic, and so we either start the game with their being elementary equivalent or not.

With first-order theories variably being able to be interpreted as higher-order theories, the result is extensible to other areas of formal logic. Indeed, if it were not in the rules of an EF Game, neither Spoiler or Duplicator would be any the wiser as to which theory, whatsoever, the other player was playing under, as we do not have access to disassemble the human brain as to its inner workings with any knowledge of the models it is using. I.e. We can’t normally read other people’s minds, unless we know them well, which comes from repeated transactions and game play, and as discussed for EF Games here.

We can tie this to communication theory.

When it comes to Communication Theory, an elementary equivalent structure may be seen as a message, received by the Receiver if the Receiver has and uses the same interpretation as the Sender, or has/uses a theory that maps to the same elementary equivalent structure for there to be a Duplicator-equivalent winner, regardless of which person is the Sender (Spoiler) and which the Receiver (Duplicator).

Logical Structure becomes a Message under Communication Theory. Image by author.

Noise, under this analogy may well be that the Sender perceives that they are using the same theory as the Receiver (but this not being the case), but two winners none the less if both agree on the same elementary equivalent structure. I.e. The message is clear to each player, regardless of differences between the two players.

That it is impossible for any transactions to be shared between players without a message through a medium/channel is central to what we discuss.

In formal logic, there may well be structures to discuss, but when we extend the study of Formal Logic to Model Theory, we don’t just discuss concrete elements, we discuss the symbols of a theory, the structure of theorems of a theory and their rules of inference, and so Formal Logic becomes tightly coupled to Communication Theory, and if we consider the likes of Ehrenfeucht Fraisse Games, Formal Logic under Game Theory itself.

This article is a challenge:

1. The current definition of Ehrenfeucht Fraisse games does not explicitly state that both players use the same formal theory. It either needs to, or such a definition allows for EF Games to be exploited, or used in ways unintended by the definition of EF Games;
2. Ehrenfeucht Fraisse Games do not sit under Game Theory, and specifically zero-sum games, because in reality there is no strategy involved, as the result of the game is a foregone conclusion to sufficiently versed players and of the knowledge of the theory they operate under;
3. Ehrenfeucht Fraisse Games are then merely fun and an intellectual exercise of the Duplicator and Spoiler.
4. Ehrenfeucht Fraisse Games may have two winners if and when the structure under investigation is either elementary equivalent or not, depending on the theory used by each player.

We can draw conclusion from this:

1. Winning is subjective under Ehrenfeucht Fraisse Games, unless agreement on the theory under investigation is agreed up front by both players;

References

1. Ehrenfeucht–Fraïssé game — Wikipedia, Accessed at 09/03/2025.

==============End============