Quantum Arrow's Theorem
Polymath: Does Arrow's Theorem hold in quantum voting?
Arrow's theorem is a classical result in political game theory. One wishes to construct an aggregation rule (or social welfare function) which takes as input the individual preference rankings members of the society have, and output an aggregated preference ranking.
Arrow's theorem only holds in the case that there are more than 2 choices to compare.
One naturally imposes some restrictions on the aggregation rule, which we take as the classical axioms: Pareto efficiency and Independence of Irrelevant Alternatives (see below for a description. Arrow's theorem states that if an aggregation rule satisfies these axioms, then one member of society necessarily acts as a Dictator, i.e., there exists one person whose personal preference ranking determines the aggregated ranking.
This Polymath Project has two purposes:
- Identify what a system of ``quantum preferences is, and
- Determine whether Arrow's Theorem holds or not in that setting. i.e., is there a Dictator whose preferences determine the aggregated preferences?
Formal statement of the theorem
(taken from Wikipedia)
Let [math]\displaystyle{ \mathrm{A} }[/math] be a set of outcomes, [math]\displaystyle{ \mathrm{N} }[/math] a number of voters or decision criteria. We shall denote the set of all full linear orderings of [math]\displaystyle{ \mathrm{A} }[/math] by [math]\displaystyle{ \mathrm{L(A)} }[/math].
A (strict) social welfare function (preference aggregation rule) is a function [math]\displaystyle{ F : \mathrm{L(A)}^N \to \mathrm{L(A)} }[/math] which aggregates voters' preferences into a single preference order on [math]\displaystyle{ \mathrm{A} }[/math].<ref>Note that by definition, a social welfare function as defined here satisfies the Unrestricted domain condition. Restricting the range to the social preferences that are never indifferent between distinct outcomes is probably a very restrictive assumption, but the goal here is to give a simple statement of the theorem. Even if the restriction is relaxed, the impossibility result will persist.</ref> The [math]\displaystyle{ \mathrm{N} }[/math]-tuple [math]\displaystyle{ (R_1, \ldots, R_N) }[/math] of voters' preferences is called a preference profile. In its strongest and most simple form, Arrow's impossibility theorem states that whenever the set [math]\displaystyle{ \mathrm{A} }[/math] of possible alternatives has more than 2 elements, then the following three conditions become incompatible:
- unanimity, or Pareto efficiency
- If alternative a is ranked above b for all orderings [math]\displaystyle{ R_1 , \ldots, R_N }[/math], then a is ranked higher than b by [math]\displaystyle{ F(R_1, R_2, \ldots, R_N) }[/math]. (Note that unanimity implies non-imposition).
- non-dictatorship
- There is no individual i whose preferences always prevail. That is, there is no [math]\displaystyle{ i \in \{1, \ldots,N\} }[/math] such that Template:Nobreak
- independence of irrelevant alternatives
- For two preference profiles [math]\displaystyle{ (R_1, \ldots, R_N) }[/math] and [math]\displaystyle{ (S_1, \ldots, S_N) }[/math] such that for all individuals i, alternatives a and b have the same order in [math]\displaystyle{ R_i }[/math] as in [math]\displaystyle{ S_i }[/math], alternatives a and b have the same order in [math]\displaystyle{ F(R_1,R_2, \ldots, R_N) }[/math] as in [math]\displaystyle{ F(S_1,S_2, \ldots, S_N) }[/math].
What is a good model for quantum preference?
Here, we take [math]\displaystyle{ R_1, \ldots, R_N }[/math] to be basis vectors in [math]\displaystyle{ N }[/math]-dimensional Hilbert space [math]\displaystyle{ \mathbb C^N }[/math].
The whole point of quantum preference is that people's true preferences can exist in superposition: e.g., they may be .8 liberal and .6i conservative ([math]\displaystyle{ .8^2 + .6^2 = 1 }[/math]).
Non-Quantum Superpositions of Preference Orderings
Here is a non-quantum perspective of superpositions using classical probability. Take the space [math]\displaystyle{ L(A) }[/math] of preference orderings. In Classic Arrow's Theorem, a voter chooses an preference order [math]\displaystyle{ R }[/math] selected from [math]\displaystyle{ L(A) }[/math].
We could also consider a situation with mixed preference rankings. Let [math]\displaystyle{ Σ }[/math] be the space of probability measures on [math]\displaystyle{ L(A) }[/math]. Now, a voter chooses a mixed preference rating [math]\displaystyle{ P \in Σ }[/math]. Choosing a particular preference ordering [math]\displaystyle{ R }[/math] corresponds to choosing the Dirac delta-measure [math]\displaystyle{ δ\lt sub\gt R\lt /sub\gt }[/math]
Does an analogue of Arrow's Theorem still hold in this setting?
A model for the single-voter spinor (wavefunction)
Let [math]\displaystyle{ k\in\mathbb N }[/math] be the cardinality of the set [math]\displaystyle{ \mathrm{A} }[/math], the set of outcomes (e.g., the candidates for president). In this bizarre country, a voter votes for every candidate on the ballot; however, he gives each of them a distinct rank from 1 to [math]\displaystyle{ \mathrm{k} }[/math]. There are thus [math]\displaystyle{ \mathrm{k!} }[/math] distinct orderings he could conceivable have. In general, then, the quantum voter will be in a superposition of all these states:
[math]\displaystyle{ |\psi\rangle = \sum_{j=1}^{k!} a_j P_j }[/math], where [math]\displaystyle{ a_j\in\mathbb C }[/math] and [math]\displaystyle{ \sum_{j=1}^{k!} |a_j|^2 =1 }[/math], and [math]\displaystyle{ P_1, \ldots, P_{k!} }[/math] are all the preference states classical voters choose among. To be clear, [math]\displaystyle{ P_j: A \to \{1, \ldots, k \} }[/math] injectively.
Thus the state space for a single quantum voter is [math]\displaystyle{ \mathbb C^{k!} }[/math]. The need for complex (as opposed to real) coefficients in the basis expansion is not clear. An evolution equation for the quantum state is needed. The nature of this equation will determine whether we need a real or complex vector space to describe the set of all possible quantum voter states. Thus far, we have only defined one observable: the presidential ballot. The k!-component spinor described above is represented in the eigenbasis of the presidential ballot. We could introduce other observables. To get truly quantum phenomena, we necessarily need at least one pair of incompatible observables. Two observables are incompatible if and only if their corresponding linear operators (on the state space) don't commute.
The toppings I want on my pizza and the vegetables I want in my salad cannot be simultaneously observed, because I can't have salad if I'm having pizza, and I can't have pizza if I'm having salad. The pizza operator does not commute with the salad operator.
Election Day and Stern-Gerlach-style Voting
Suppose the voters are casting ballots for president and for governor, and suppose further that the respective observables are incompatible. That is, the presidential ballot operator doesn't commute with the gubernatorial ballot operator. Thus, voting for both offices cannot take place simultaneously. So let's say voters cast for president first, then for governor. This is highly reminiscent of the Stern-Gerlach experiment in quantum mechanics. What the secretary of state reports as the results of the election is essentially the output of the social welfare function. What should the honorable secretary report? When a quantum voter casts for, say, president, his spinor/wavefunction (which is, in general, a linear combination of all k! eigenvectors of the presidential ballot operator) collapses onto a single eigenvector of the presidential ballot. The collapse mechanism is not known and, to be in perfect analogy with quantum mechanics, cannot be known: it is purely random. To be clear, the coefficient of the eigenvector to which the spinor collapsed may have had a relatively small square modulus in the voter's state's eigenbasis expansion. Thus, the fact that he collapsed onto a particular eigenvector after voting for president tells us nothing about his actual state. To get information about the sizes of the [square moduli of the] coefficients his state assigns to each eigenvector, we need to have the voter cast a ballot for president multiple times. Moreover, we need him to cast a ballot for governor in between casting for president, so that we shake him out of a presidential eigenstate and into a gubernatorial eigenstate (which is a superposition of presidential eiegenstates, since the gubernatorial operator is not simultaneously diagonalizable with the presidential operator). If the voter casts, say, a thousand votes for president in a single day, then we have a histogram for the outcomes he produced. This histogram gives us some approximation of the coefficients in the voter's spinor, up to some error (determined by the fact that we have a finite data set). In general, the voter could cast [math]\displaystyle{ \omega\in\mathbb N }[/math] votes for president; and (using elementary statistics) we can calculate an upper bound on the error, as we try to say what his spinor's components are based on the histogram generated with [math]\displaystyle{ \omega }[/math] data points. If we decide we want our error to be less than epsilon, then we can invert the calculation to determine what [math]\displaystyle{ \omega }[/math] should be. So the secretary of state collects the results of, say, a thousand voting iterations per voter per office, and produces his social welfare function's results as a function of this data. In short: for each voter, the voting lasts all day.
Doesn't this assume that the voter returns to his initial state upon casting for governor? What basis would you have for thinking that? None. This is all garbage. Maybe we have to come up with an evolution equation to be sure about any of this.
I am having ice cream. How much chocolate sauce would I like on my ice cream? Well, my options are indexed by a set of cardinality continuum. But ultimately my preference wavefunction is going to collapse to a single definite finite value for how much chocolate sauce I apply to my ice cream.
What are the quantum analogues of Arrow's axioms?
What is a Dictator in the quantum setting?
It is not clear what it means for one person to be a Dictator in this setting.
Quantum Arrow's Theorem
Statement of theorem here.
Proof of quantum Arrow's theorem
The proof should be straightforward once we determine the statement of the theorem.
Probabilistic Formulation of the Model
Let [math]\displaystyle{ \Sigma = L(A) }[/math], the space of individual preference rankings. Let [math]\displaystyle{ \Omega = \Sigma^N }[/math] be the space of society's preference rankings.
We define a probability measure [math]\displaystyle{ \mathbb P }[/math] on the space [math]\displaystyle{ \Omega = \Sigma^N }[/math]. (what assumptions should this measure satisfy?)
Let [math]\displaystyle{ f : \Sigma^N \to \Sigma }[/math] be any function. This represents the aggregation rule. The function [math]\displaystyle{ f }[/math] should satisfy some axioms. In analogy with Classical Arrow's Theorem, it should satisfy Pareto Efficiency (PE) and Independence of Irrelevant Alternatives (IIA). In analogy with the mathematics of the concentration-of-measure phenomenon in mathematical probability, the function [math]\displaystyle{ f }[/math] should be uniformly Lipschitz in the population size.
Let [math]\displaystyle{ X \in \Sigma^N }[/math] be a random variable with probability law [math]\displaystyle{ \mathbb P }[/math]. We should think of [math]\displaystyle{ X }[/math] as simultaneously sampling the full preference ranking of all of society. Of course, we can never truly observe the outcome of [math]\displaystyle{ X }[/math]; it exists solely as a mathematical model.
Now, the random variable [math]\displaystyle{ f(X) \in \Sigma }[/math] represents the aggregated preference of the society.
Let [math]\displaystyle{ m_f }[/math] be a median of the random variable [math]\displaystyle{ f(X) }[/math]. The concentration of measure phenomenon suggests that there exist constants [math]\displaystyle{ C }[/math] and [math]\displaystyle{ \lambda }[/math] (depending on the aggregation rule [math]\displaystyle{ f }[/math] and the distribution [math]\displaystyle{ \mathbb P }[/math]) such that [math]\displaystyle{ \mathbb P( |f(X) - m_f| \gt u ) \le \mathrm C e^{-\lambda n u} }[/math]. This means that the random outcome [math]\displaystyle{ f(X) }[/math] is very close to its median [math]\displaystyle{ m_f }[/math] with extremely high probability.
Question: Is there a dictator? We know that [math]\displaystyle{ f(X) }[/math] is concentrated on its median. We say that an actor [math]\displaystyle{ i }[/math] is a dictator when the median [math]\displaystyle{ m_f }[/math] is very concentrated on the preference of person [math]\displaystyle{ i }[/math]. i.e., [math]\displaystyle{ m_f \approx \pi_i(X) }[/math], where [math]\displaystyle{ \pi_i }[/math] is the projection onto the [math]\displaystyle{ i }[/math] coordinate of the random vector [math]\displaystyle{ X }[/math]
Kalai's Theorem
Here is an article by Gil Kalai on this subject: http://www.ma.huji.ac.il/~kalai/arr.pdf
He assumes that the social choice function [math]\displaystyle{ f }[/math] is rational: this means that the outcome is always a preference order. We assumed this already when we said that its codomain is the space [math]\displaystyle{ \Sigma }[/math] of preference orders.
Kalai assumes the function is neutral: this means that it is invariant under permutations of choices to be ranked. He also assumes it is symmetric: this means it is constant under permutations of its inputs. e.g., if the population size is [math]\displaystyle{ N = 2 }[/math], [math]\displaystyle{ f(R_1, R_2) = f(R_2, R_1) }[/math]
