Janssen: "Independent Choices and the Interpretation of IF Logic" (2002)

In this paper, Theo Janssen argues that Jaako Hintikka and Gabriel Sandu's notion of independence-friendly logic does not adequately formalize the notion of quantifier independence, at least according to his intuitions about what independence should mean. He has essentially two arguments, of which the first one is the strongest.

Dependence Chains

The most serious problem that Janssen points out is that IF logic may require that a choice A is independent from a choice C without ruling out that there is some intermediate choice B such that A depends on B, and B depends on C.

Such cases create some quite strange examples, e.g.:

• TRUE: ∀x: (x ≠ 2) v (∃u_/x: x = u).
• FALSE: ∀x: (x = 2) v (∃u_/x: x = u).
• TRUE: ∀x: (x ≠ 2) v (∃u_/x: x ≠ u).
• TRUE: ∀x: (x = 2) v (∃u_/x: x ≠ u).

The true sentence are here true in spite of the independence between u and x, the reason being that the disjunction is not independent of x. The Verifier can thus circumvent the quantifier independence. For instance, in the first sentence, he can set u := 2 and then pick the left disjunct if and only if x = 2.

Similar examples exists where the middle term which smuggles in the dependence is not a disjunction, but another quantifier.

Naming Problems

Another problem occurs, according to Janssen, when "a variable is bound within the scope of a quantifier that binds the same variable" (p. 375). This occurs for instance in sentence like

• ∀x∃x: R(x,x).

He claims that such sentences come about by "classically allowed" substitutions from, in this case,

• ∀x∃y: R(x,y).

After such a substitution, an indirect dependencies referring to the value of y might be lost, and an otherwise winning Verifier strategy might be broken. However, I don't know whether there would be any problem with just banning double-bound quantifiers as the x above; it doesn't seem to have any necessary or positive effect.

Solutions

To avoid the problems of Hintikka's system, Janssen defines a new game with explicit extra conditions such as "The strategy does not have variables in W as arguments" and "If the values of variables in W are changed, and there is a winning choice, then the same choice is a step towards winning" (p. 382).

This solves the problem, but doesn't bring about much transparency, it seems to me. A better solution would probably be to describe the instantiation of the quantifiers and the selection of branches at the connectives as a probability distribution on a suitable power of the domain and of the branch options {L,R}. Then independence could be clearly described as statistical independence.

Such a system would require the domains to be finite, which is not good. However, within finite domains, results about logical strength of solution concepts would be easy to extract, because they would simply correspond to different constraints on the dependencies between the choices, i.e., marginal distributions. It would, in fact, allow us to quantify the amount of information that was transmitted from one choice to another by computing the mutual information between two marginal distributions.

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
Neither	Subgame 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.