Social Choice Talk

I took part in a workshop celebrating the publication of a new book on Social Choice by Shmuel Nitzan which took place at the Open University. (The book is in Hebrew, and an English version is forthcoming from Cambridge University Press.) It was a very interesting event and all the lectures were excellent. I thought of blogging about my lecture.

The main part of the lecture was about the four old theorems in the table above and about what should replace the two question marks. The left side of the table deals with properties of the majority voting rule for binary preferences. The right side of the table is about general voting rules. On the top tight is the famous Arrow Impossibility Theorem. The table is filled by two theorems I proved in 2002 (in this paper) and it now looks like this:

Here is a quick description of the six entries in the table.

Majority Rule

1. Condorcet’s Paradox: irrational majority-based preferences

Condorcets’s paradox: The outcomes of the majority rule may be intransitive.

It is possible that we have the majority of society preferring alternative A to alternative B, alternative B to alternative C, and alternative C to alternative A. (this can easily be demonstrated with three voters.) Having a transitive preference relation is the definition of a rational agent in economics and Condorcet’s paradox asserts that the majority preference can be irrational.

2. Condorcet’s Jury theorem: the majority rule leads to complete aggregation of information.

Consider two alternatives. Here is a formulation of Condorcet’s jury theorem taken from this article.

Condorcet’s Jury Theorem: Suppose that a group of people each expresses a yes-no opinion about the same matter of fact, that they reach and express these opinions independently, and that each has better than 50% chance of being right. Then as the size of the group increases without bound, the probability that a majority will be right approaches one.

This result is a simple consequence of the law of large numbers. In modern economics jargon this property of the majority rule is referred to as (asymptotically) complete aggregation of information. (This is relevant when individuals have a common goal but different information. Real life elections have a dual role both of aggregating information that individuals have and averaging different interests and opinions.)

 

Marie Jean Antoine Nicolas de Caritat, marquis de Condorcet (17 September 1743 – 28 March 1794)

3. McGarvey’s theorem: non-testable social preferences

McGarvey’s Theorem: Given a set of alternatives, for a large society every preference relation on the alternatives can express majority preferences for some profile of individual (rational) preferences.

In other words, every asymmetric relation (even with indifferences allowed) can be realized as the majority preference relation of a large enough society. McGarvey’s proof was very simple: If the alternatives are 1,2,…,n and you want the society to prefer 1 over 2 add two individuals with preferences: 1>2>3>…>n and n>n-1>n-2>…>3>1>2. The theorem is proved by adding pairs of individuals for every preference relation you want to achieve.

The conclusion of MacGarvey’s theorem is referred to as indeterminacy. Everything can happen; there are no testable implications to the assumption that a given preference relation on a set of alternatives is the outcome of the majority rule.

General rules

The right hand side of the table is about general voting rules – general methods to move from preferences of many individuals to social preferences. Such a methods is called a social welfare function(SWF). Since we will not insist that the social preferences are transitive we will refer to such functions as generalized social welfare functions (GSWF). We will assume two requirements:

IIA – independence of irrelevant alternatives: the society preference between two alternatives depends only on the individual preferences between these alternatives.

P (Pareto): If all individuals prefer alternative A to alternative B then the society prefers A to B.

4. Arrow’s theorem: irrational social outcomes

Arrow’s theorem: Irrational social outcomes cannot be avoided for every non-dictatorial generalized social welfare function satisfying IIA and P:

5. Information aggregation

The next results rely on two additional properties:

M (Monotonicity): If an individual changes his preference to favor alternative A over B this cannot lead the society to change its preference between A and B in the opposite direction.

B (Balance): If all voters change their preferences between alternatives A and B, then so will the society.

They also rely on a notion of power of a voter in a voting rule: the Shapley-Shubik power index. (We mentioned it in some earlier posts on influence and on coalition-forming. Briefly, the Shapley Shubik power of a voter is the probability that this voter is pivotal in the equal-slice measure.)

Theorem: For a sequence of monotone and balanced voting rules, asymptotically complete aggregation of information is equivalent to diminishing maximum Shapley-Shubik power.

Here the condition of having no dictator from Arrow’s theorem is strengthened and replaced by a condition of having no voter with substantial power.

6. Indeterminacy

Theorem : For a fixed set of alternatives, a sequence of monotone and balanced generalized social welfare functions with diminishing maximum Shapley-Shubik power leads to indeterminacy.

(Recall that indeterminacy refers to the conclusion of McGarvey’s theorem.) The key for this result is a tradeoff between information aggregation and testable implication.

Theorem (stated informally): Asymptotic aggregation of information implies indeterminacy!

This implication is quite simple.

Arrow’s theorem was stated, discussed and proved on several blogs: Michael Nielsen’s, the Geomblog, Black belt Bayesian, Secret blogging seminar, and Algorithmic game theory, to name a few.