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.

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.