Friday, November 18, 2022

Social choice principles and invariance under symmetries

A comment by a referee of a recent paper of mine that one of my results in decision theory didn’t actually depend on numerical probabilities and hence could extend to social choice principles made me realize that this may be true for some other things I’ve done.

For instance, in the past I’ve proved theorems on qualitative probabilities. A qualitative probability is a relation on the subsets of some sample space Ω such that:

  1. ≼ is transitive and reflexive.

  2. ⌀ ≼ A

  3. if A ∩ C = B ∩ C = ⌀, then A ≼ B iff A ∩ C ≼ B ∩ C (additivity).

But need not think of Ω as a space of possibilities and of ≼ as a probability comparison. We could instead think of it as a set of people who are candidates for getting some good thing, with A ≼ B meaning that it’s at least as good for the good thing to be distributed to the members of B as to the members of A. Axioms (1) and (2) are then obvious. And axiom (3) is an independence axiom: whether it is at least as good to give the good thing to the members of B as to the members of A doesn’t depend on whether we give it to the members of a disjoint set C at the same time.

Of course, for a general social choice principle we need more than just a decision whether to give one and the same good to the members of some set. But we can still formalize those questions in terms of something pretty close to qualitative probabilities. For a general framework, suppose a population set X (a set of people or places in spacetime or some other sites of value) and a set of values V (this could be a set of types of good, or the set of real numbers representing values). We will suppose that V comes with a transitive and reflexive (preorder) preference relation . Now let Ω = X × V. A value distribution is a function f from X to V, where f(x) = v means that x gets something of value v.

We want to generate a reflexive and transitive preference ordering ≼ on the set VX of value distributions.

Write f ≈ g when f ≼ g and g ≼ f, and f ≺ g when f ≼ g but not g ≼ f. Similarly for values v and w, write v < w if v ≤ w but not w ≤ v.

Here is a plausible axiom on value distributions:

  1. Sameness independence: if f1, f2, g1, g2 are value distributions and A ⊆ X is such that (a) f1 ≼ f2, (b) f1(x) = f2(x) and g1(x) = g2(x) if x ∉ A, (c) f1(x) = g1(x) and f2(x) = g2(x) if x ∈ A.

In other words, the mutual ranking between two value distributions does not depend on what the two distributions do to the people on whom the distributions agree. If it’s better to give $4 to Jones than to give $2 to Smith when Kowalski is getting $7, it’s still better to give $4 to Jones than to give $2 to Smith when Kowalski is getting $3. There is probably some other name in the literature for this property, but I know next to nothing about social choice literature.

Finally, we want to have some sort of symmetries on the population. The most radical would be that the value distributions don’t care about permutations of people, but more moderate symmetries may be required. For this we need a group G of permutations acting on X.

  1. Strong G-invariance: if g ∈ G and f is a value distribution, then f ∘ g ≈ f.

Here, f ∘ g is the value distribution where site x gets f(g(x)).

Additionally, the following is plausible:

  1. Pareto: If f(x) ≤ g(x) for all x with f(x) < g(x) for some x, then f ≺ g.

Theorem: Assume the Axiom of Choice. Suppose on V is reflexive, transitive and non-trivial in the sense that it contains two values v and w such that v < w. There exists a reflexive, transitive preference ordering on the value distributions satisfying (4)–(6) if and only if there is such an ordering that is total if and only if G has locally finite action on X.

A group of symmetries G has locally finite action a set X provided that for each finite subset H of G and each x ∈ X, applying finite combinations of members of G to x generates only a finite subset of X. (More precisely, if ⟨H⟩ is the subgroup generated by G, then Hx is finite.)

If X is finite, then local finiteness of action is trivial. If X is infinite, then it will be satisfies in some cases but not others. For instance, it will be satisfied if G is permutations that only move a finite number of members of X at a time. It will on the other hand fail if X is a infinite bunch of people regularly spaced in a line and G is shifts.

The trick to the proof of the Theorem is to reduce preferences between distributions to comparisons of subsets of X × V and to reduce comparisons of subsets of X to preferences between binary distributions.

Proof of Therem: Suppose that G has locally finite action. Define Ω = X × V. By Theorem 2 of my invariance of non-classical probabilities paper, there is a strongly G-invariant regular (i.e., ⌀ ≺ A if A is non-empty) qualitative probability ≼ on Ω. Given a value distribution f, let f* = {(x,v) : v ≤ f(x)} be a subset of Ω. Define f ≼ g iff f* ≼ g.

Totality, reflexivity, transitivity and strong G-invariance for value distributions follows from the same conditions for subsets of Ω. Regularity of on the subsets of Ω and additivity implies that if A ⊂ B then A ≺ B. The Pareto condition for ≼ on the value distributions follows since if f and g satisfy are such that f(x) ≤ g(x) for all x with strict inequality for some x, then f* ⊂ g*. Finally, the complicated sameness independence condition follows from additivity.

Now suppose there is a (not necessarily total) strongly G-invariant reflexive and transitive preference ordering ≼ on the value distributions satisfying (4)–(6). Given a subset A of X, define A to be the value distribution that gives w to all the members of A and v to all the non-members, where v < w. Define A ≼ B iff A ≼ B. This will be a strongly G-invariant reflexive and transitive relation on the subsets of X. It will be regular by the Pareto condition. Finally, additivity follows from the sameness independence condition. Local finiteness of action of G then follows from Theorem 2 of my paper. ⋄

Note that while it is natural to think of X has just a set of people or of locations, inspired by Kenny Easwaran one can also think of it as a set Q × Ω where Ω is a probability space and Q is a population, so that f(x,ω) represents the value x gets at location ω. In that case, G might be defined by symmetries of the population and/or symmetries of the probability space. In such a setting, we might want a weaker Pareto principle that supposes additionally that f(x,ω) < g(x,ω) for some x and all ω. With that weaker Pareto principle, the proof that the existence of a G-invariant preference of the right sort on the distributions implies local finiteness of action does not work. However, I think we can still prove local finiteness of action in that case if the symmetries in G act only on the population (i.e., for all x and ω there is an y such that g(x,ω) = (y,ω)). In that case, given a subset A of the population Q, we define A to be the distribution that gives w to all the persons in A with certainty (i.e., everywhere on Ω) and gives v to everyone else, and the rest of the proof should go through, but I haven’t checked the details.

1 comment:

Alexander R Pruss said...

I forgot to say that G acts on X x V by acting on the first component in the proof.