Wednesday, May 16, 2012

Sevenster: "A strategic Perspective on IF Games" (2009)

This is a commentary on Hintikka and Sandu's game-theoretical approach to independence-friendly logic. Sevenster considers how the notion of truth is changed when one changes the information flow or the solution concept for the falsification game over a sentence.

Information Access

When playing an extensive game, one can be "forgetful" to different degrees. In the general setting, forgetfulness has various effects, such as blocking the possibility of threat behavior. In terms of the semantics of quantifiers, the various degrees of forgetfulness also allow for different types of independence:

Memory capacity Solution concept Independence relations
Gobal strategy and past moves Nash equilibrium None
Global strategy Other Existentials of universals
NeitherSubgame perfect equilibirum Anything of anything

To see the difference between the two degrees of independence, consider the following sentence:
  • There is an x and there is a y such that x = y.
Assume that we are in a world with two objects, and that the two existential quantifiers in the sentence are independent of each other. Then the verifier can at most achieve a 50% chance of verifying the sentence, since there is no information flow from the first choice to the other.

If, on the other hand, the second choice is dependent on the first, the verifier can achieve a 100% success rate. The difference is that between a sequential and a simultaneous coordination game.

This example is exactly the one that I have felt missing in Hintikka's discussions, so its nice to see that I'm not alone. Apparently, Theo Janssen has discussed the problem in a paper from 2002 (cf. Sevenster's article, p. 106).

Solution Concepts

Sevenster uses three different solution concepts in his article:
  1. Nash equilibrium
  2. WDS + P
  3. WDS
WDS strategy profiles are profiles in which all players play a weakly dominant strategy, i.e., one that is (weakly) optimal whatever everyone else does. This is a very strong condition.

WDS + P strategy profiles are, as far as I can see from Sevenster's Definition 12, the ones that remain after the removal of the weakly dominated strategies for player n, then for player n – 1, and so on. This is weaker than WDS, since a WDS + P strategy for player i does not need to be (weakly) optimal with respect to every other strategy, but only optimal with respect to the WDS + P strategies for players j with j > i.

Neither of these last two solution concepts are standard. The middle one is slightly problematic because it may give different results when players are enumerated differently. But that's a drawback it shares with all solution concepts based on elimination of weakly dominant strategies.

Some Mixed Equilibria

Just the for the sake of it, let me just briefly review two example sentences:
  • There is an x and there is a y such that x = y.
  • There is an x such that for all y, x = y.
Assume further that we are in a model in which there are exactly two objects, a and b. These two sentences then correspond to a simple coordination game and to Matching Pennies, respectively. The coordination game has the three equilibria (0, 0), (1/2, 1/2), and (1, 1), white Matching Pennies only has the equilibrium (1/2, 1/2).

The interpretation of this in classical logic is that the double existential sentence is supported by two pieces of evidence (a = a and b = b), while the sentence with the universal quantifier is supported by no evidence.

However, in the mixed strategy equilibrium, both strategies pay the same for both players. This means that the players achieve no gain by knowing that the other player is going to play (1/2, 1/2). Accordingly, they correspond to the case without any (useful) information flow between the players.

The existence of such equilibria thus witness the existence of a true, independence-friendly reading of the sentence in the relevant model. Note, however, that this does not mean that the sentences are tautological—the Verifier does not have any strategy that guarantees the payoff 1 in any of the two cases.

No comments :

Post a Comment