Social Choice and Logic via Simple Games
Tijmen R. Daniëls · 2007
ion we need, since it is clearly a property of the SAF F itself and not of any particular model based on F . This notion of validity stems from the semantics of modal logic, in which the same distinction is made between satisfaction of a formula φ as a property of models, and validity as a property of some underlying “frame”. Therefore we will look at SAFs as a variant of such modal frames. In the balance of this part of the thesis, we will again be concerned with the logic of SAFs that are monotonic and neutral and satisfy universal domain. We restrict attention to these SAFs because there is a very straightforward link between modal logic and the logic of aggregation functions through simple games. L -models based on such SAFs will be called simple models. 4.3 Passing from Simple Games to Social Choice and Vice-Versa Let Ω = (N,W ) be a simple game. Define: FΩ(π) := {ψ ∈ Lc | ∃A ∈W ∀i ∈ A φπ(i) |= ψ}, In words, ψ ∈ FΩ(π) if there is some winning coalition A of Ω such that every agent i ∈ A accepts ψ. Clearly FΩ is a SAF that satisfies M, N, and UD. In fact, we have the following, mirroring the results in this subsection 3.3: Proposition 36. The following are equivalent. (a) F is a SAF satisfying M, N, UD; (b) F is a SAF generated by a unique simple game Ω. The theory of F is the set of formulae {φ ∈ L | F φ}. Given our previous results, it is unsurprising that some properties of a simple game Ω pass at once to the theory of FΩ: Lemma 37. Let Ω = (N,W ) a simple game. (a). For all ψ ∈ Lc, FΩ ψ → ¬ ¬ψ iff Ω is proper; (b). For all ψ ∈ Lc, FΩ ¬ ¬ψ → ψ iff Ω is strong. Proof. (a ⇐). Let π be an arbitrary choice function. Let ψ ∈ FΩ(π). Then there is A ∈ W such that A = [[ψ]]π. As for any Q ⊆ Q, φQ |= ψ ⇐⇒ φQ 6|= ¬ψ, we have N − [[ψ]]π = [[¬ψ]]π. By (M2a), N − [[ψ]]π / ∈ W . Suppose towards a contradiction that ¬ψ ∈ FΩ(π). Then there is B ∈ W such that every agent i ∈ B accepts ψ. Clearly B ⊆ [[¬ψ]]π, so by (M1) [[¬ψ]]π = N− [[ψ]]π ∈W , a contradiction. Hence (F, π) ¬ ¬ψ. (a ⇒). Let ψ be any formula that isn’t a tautology or a contradiction. Suppose FΩ ψ → ¬ ¬ψ, and that A ∈ W . Let π be any choice function such that [[ψ]]π = A, and so (FΩ, π) ψ. Clearly [[¬ψ]] = N − A. Since FΩ ψ → ¬ ¬ψ, we have (FΩ, π) |= ¬ ¬ψ, and thus N −A / ∈W . (b ⇐). Let π be an arbitrary choice function. Suppose ¬ψ / ∈ FΩ(π). Then there is no