Discussion:
Arrow's Theorem - The Return (again)
Eric Gorr
2003-08-02 19:36:53 UTC
Permalink
I recently purchased a copy of Arrow's book 'Social Choice and
Individual Values' Second Edition (ISBN: 0300013647).

The last time this topic came up, it was argued that Arrow's Theorem
only involved strict preferences, based on the document found at:

http://faculty-web.at.northwestern.edu/economics/chung/mr/Reny.pdf

However, this does not appear to be the case.

On page 13, Arrow states as Axiom I

For all x and y, either x R y or y R x

For Arrow's purposes, R is defined to mean in the case of x R y that
a person either preferrs x over y or is indifferent in the comparison
of x to y. To quote Arrow again,

"Note that Axiom I is presumed to hold when x = y, as well as when x is
distinct from y, for we ordinarily say that x is indifferent to itself
for any x, and this implies x R x." (page 13)

After a few more formal statements and descriptions, based, in part,
on Axiom I, he goes on to say that:

"However, it may be as well to give sketches of the proofs, both to show
that Axiom I and II really imply all that we wish to imply about the
nature of orderings of alternatives and to illustrate the type of
reasoning to be used subsequently." (page 14)

On page 36, he goes on to develop the Pareto principle based, in
part, on Axiom I.

"The Pareto principle was originally given in the text (p.36) as a form of
the compensation principle." (page 96)

So, (to ask a question) why does Reny use only strict preferences?
Well, Arrow does the same thing near the end of his book, starting on
page 96, he reasoning appears to be:

"Since the Pareto principle is universally accepted, the new set of
conditions will be easier to compare with other formulations of the
problem of social choice." (page 96)

"We give it [Pareto principle] here in a slightly weaker form (involving
only strict preferences)." (page 96)

I would venture to guess that Reny used the same basic philosophy in
his paper when writing about both Arrow's Theorem and
Gibbard-Satterthwaite theorem.


Now, I fully admit that this may be a case of knowing just enough to
get me into trouble and would appreciate it if someone else could
take a look at the book and verify or clarify what I have said based
on the original work.
--
== Eric Gorr ========= http://www.ericgorr.net ========= ICQ:9293199 ===
"Therefore the considerations of the intelligent always include both
benefit and harm." - Sun Tzu
== Insults, like violence, are the last refuge of the incompetent... ===
----
Election-methods mailing list - see http://electorama.com/em for list info
Alex Small
2003-08-02 20:17:36 UTC
Permalink
OK, I stand corrected on the assertion that Arrow's Theorem assumes strict
preferences.

However, this whole discussion began over the question "Does Approval
Voting satisfy Arrow's assumptions?" Approval Voting certain satisfies
non-dictatorship and Pareto. Does it satisfy the assumption that the
winner is uniquely determined from the voters' preference orders? If so,
then it cannot satisfy IIAC. If it doesn't satisfy that, then we must
look elsewhere to see if Approval satisfies IIAC.

Arrow assumes that, if we know each voter's ranking of the candidates we
can uniquely determine who will win (leave aside the question of ties).
We don't need to know cardinal utilities, we don't need to know an
Approval cut-off, we don't need a 5-4 Supreme Court ruling, and we don't
need input from Chicago graveyards. All we need is the set of voter
preferences and we know the winner.

If I say to you "My preference is Libertarian>Democrat>Repubican", can you
predict with certainty what my Approval ballot will be? Of course not.
Now, if you knew my cardinal utilities, maybe (just maybe) you could use
one of the methods that Forest is developing. If you had polling data,
you could assume that I'll vote for my favorite of the top 2. But you
don't have that. You CAN assume that I'll approve the Libertarian but not
the Republican if you make the assumption that I am a rational person (my
wife might argue with that...). But you have no idea if I'll approve the
Democrat.

So, if we knew how many people hold each preference order in a 3-candidate
race, unless everybody happened to have binary preferences (e.g.
Libertarian=Democrat>Republican) we would have no clue who the Approval
winner is in general.

(There are exceptions. If 45% of the electorate put candidate A in last
place, 45% put candidate B in last place, and 60% put C in first place,
then the most that A and B can get is 55%, while C is guaranteed at least
60%. But these are exceptions. In general, we can't predict the outcome
of an Approval election purely from the set of individual preferences.)

Anyway, because the outcome of an Approval Voting election is not uniquely
determined from the set of individual preferences, Approval Voting does
not satisfy one of Arrow's assumptions. Therefore, it is not governed by
Arrow's conclusions, and we have to look elsewhere to figure out if
Approval satisfies IIAC.



Here's a good argument for why Approval flunks IIAC:

Say that the electorate is as follows:

30 (A>B)>C
30 (C)>A>B
40 (B)>A>C

The parentheses indicate which candidates a particular group of voters
approved. In this case, B wins with 70 votes.

Now give all of the voters a ballot again, but don't include candidate C
on it. If the people who approved both A and B the first time around are
rational they will only approve A this time. If the people who only
approved C the first time around are rational they will only approve A
this time. A now wins 60-40.

A mathematician at Northwestern published a paper on this premise a few
years back. He used more sophisticated assumptions about voter behavior,
but the final conclusion was that Approval Voting flunks IIAC. I wasn't
impressed when I ran across it. If we can use a single counter-example to
prove that a statement is false, then a long proof is unnecessary. But I
suspect he's from the Saari school of voting theory (Saari used to teach
at Northwestern), and really wanted to drive home that Approval Voting
isn't perfect. (I'm sure everybody here, Donald especially, was
completely shocked to learn that Approval Voting isn't perfect. ;)



Alex


----
Election-methods mailing list - see http://electorama.com/em for list info
Eric Gorr
2003-08-04 01:09:14 UTC
Permalink
Post by Alex Small
OK, I stand corrected on the assertion that Arrow's Theorem assumes strict
preferences.
However, this whole discussion began over the question "Does Approval
Voting satisfy Arrow's assumptions?" Approval Voting certain satisfies
non-dictatorship and Pareto. Does it satisfy the assumption that the
winner is uniquely determined from the voters' preference orders?
I can see no reason, based on the original work, that it would not
satisfy this assumption.

Arrow seems to be perfectly content with allowing equal rankings.

Approval voting merely requires the user to divide the options into
two different groups, but doing do does not violate Arrow's Axioms or
definitions regarding voter choice.

Again, from his book:

"However, it may be as well to give sketches of the proofs, both to show
that Axiom I and II really imply all that we wish to imply about the
nature of orderings of alternatives and to illustrate the type of
reasoning to be used subsequently." (page 14)
Post by Alex Small
Anyway, because the outcome of an Approval Voting election is not uniquely
determined from the set of individual preferences, Approval Voting does
not satisfy one of Arrow's assumptions.
Again, individual preferences do not have to be strict orderings.

As such, the voting system that Approval uses is fully accounted for
by Arrow's Theorem.

I would strongly recommend that you pick up a copy of his book (I
assume you don't have it) so we can discuss in more detail how Arrow
has developed his theorem.
--
== Eric Gorr ========= http://www.ericgorr.net ========= ICQ:9293199 ===
"Therefore the considerations of the intelligent always include both
benefit and harm." - Sun Tzu
== Insults, like violence, are the last refuge of the incompetent... ===
----
Election-methods mailing list - see http://electorama.com/em for list info
Alex Small
2003-08-04 04:40:52 UTC
Permalink
Post by Eric Gorr
Arrow seems to be perfectly content with allowing equal rankings.
Approval voting merely requires the user to divide the options into two
different groups, but doing do does not violate Arrow's Axioms or
definitions regarding voter choice.
"However, it may be as well to give sketches of the proofs, both to show
that Axiom I and II really imply all that we wish to imply about the
nature of orderings of alternatives and to illustrate the type of
reasoning to be used subsequently." (page 14)
No, no, no, no, no!

Arrow assumes that, whether voters happen to have strict preferences or
whether they instead rank some candidates equal, voters are free to report
ANY transitive ranking of candidates (which might include equal rankings).
Based on this information, i.e. every voter giving his COMPLETE
preference order, the election method then chooses a winner.

Approval does NOT allow voters to express their complete preferences.
Sure, if a person happens to have a lot of equal rankings so that the
candidates fall into two groups, then Approval lets that PARTICULAR voter
express his full preferences. BUT, if the person sorts the candidates
into 3 or more categories, Approval does not let them express their
complete preferences.

Once again, Arrow basically proves that no method can satisfy all of the
following criteria simultaneously when there are 3 or more candidates:

1) Non-dictatorship (plenty of methods, and any seriously proposed
method, will satisfy this)

2) Pareto (plenty of methods, and any seriously proposed method, will
satisfy this)

3) IIAC

4) The use of RANKED ballots, which allow ANY voter to indicate his
entire preference, WHATEVER it might happen to be.


APPROVAL DOES NOT SATISFY THIS CRITERION! If my preference is A>B>C then
I have to make a decision about whether or not to approve B.

Can I please get some back-up here? Somebody, anybody, please back me up
on this? I can't believe how difficult it is to drive home the point that
Approval Voting is not a ranked method.

Anyway, since Approval flunks criterion #4, it is in keeping with Arrow's
Theorem. It flunks at least one of his criteria.



Alex


----
Election-methods mailing list - see http://electorama.com/em for list info
Stephane Rouillon
2003-08-04 13:23:21 UTC
Permalink
Approval is not a ranked method.
It allows to represent preferential ballots that contain only one
preference symbol: (A=B=C=...=D) > (E=F=G...=H)
So Approval allows to represent equal rankings, but it
does not allow to represent ballots containing many
preference symbols (>).
Post by Alex Small
Can I please get some back-up here? Somebody, anybody, please back me up
on this? I can't believe how difficult it is to drive home the point that
Approval Voting is not a ranked method.
----
Election-methods mailing list - see http://electorama.com/em for list info
Eric Gorr
2003-08-04 16:58:45 UTC
Permalink
A
Post by Stephane Rouillon
Post by Alex Small
Can I please get some back-up here? Somebody, anybody, please back me up
on this? I can't believe how difficult it is to drive home the point that
Approval Voting is not a ranked method.
Approval is not a ranked method.
It allows to represent preferential ballots that contain only one
preference symbol: (A=B=C=...=D) > (E=F=G...=H)
So Approval allows to represent equal rankings, but it
does not allow to represent ballots containing many
preference symbols (>).
Approval is a ranked method by Arrow's Axioms
which only requires voters express their opinion
on the comparison between candidates through the
following relation:

For all x and y, either x R y or y R x

Now, since R can be either '=' or '>', Approval
does not violate this. At best, it could probably
be called a 'weak' ranked method, but a ranked
method, nonetheless.
--
== Eric Gorr ========= http://www.ericgorr.net ========= ICQ:9293199 ===
"Therefore the considerations of the intelligent always include both
benefit and harm." - Sun Tzu
== Insults, like violence, are the last refuge of the incompetent... ===
----
Election-methods mailing list - see http://electorama.com/em for list info
Stephane Rouillon
2003-08-04 18:09:26 UTC
Permalink
By your definition forcing every voter to put
A=B=....=H=I would be a "ranked electoral method".

IMHO, it is not
For all x and y, either x R y or y R x
you want, it is
For all x and y, ALL x R y or y R x ARE EXPRESSABLE...

Sorry, I'm still with Alex for now.
Post by Eric Gorr
A
Post by Stephane Rouillon
Post by Alex Small
Can I please get some back-up here? Somebody, anybody, please back me up
on this? I can't believe how difficult it is to drive home the point that
Approval Voting is not a ranked method.
Approval is not a ranked method.
It allows to represent preferential ballots that contain only one
preference symbol: (A=B=C=...=D) > (E=F=G...=H)
So Approval allows to represent equal rankings, but it
does not allow to represent ballots containing many
preference symbols (>).
Approval is a ranked method by Arrow's Axioms
which only requires voters express their opinion
on the comparison between candidates through the
For all x and y, either x R y or y R x
Now, since R can be either '=' or '>', Approval
does not violate this. At best, it could probably
be called a 'weak' ranked method, but a ranked
method, nonetheless.
--
== Eric Gorr ========= http://www.ericgorr.net ========= ICQ:9293199 ===
"Therefore the considerations of the intelligent always include both
benefit and harm." - Sun Tzu
== Insults, like violence, are the last refuge of the incompetent... ===
----
Election-methods mailing list - see http://electorama.com/em for list info
Eric Gorr
2003-08-04 17:06:25 UTC
Permalink
Post by Alex Small
Arrow assumes that, whether voters happen to have strict preferences or
whether they instead rank some candidates equal, voters are free to report
ANY transitive ranking of candidates (which might include equal rankings).
I have found no evidence, in the original work, to support this claim.

His proofs are based upon the relation 'R' takes into full account
equal or distinct rankings.

While I could write to Dr. Arrow again, I would only want to do so if
presented with a compelling reason based on the original work.

----
Election-methods mailing list - see http://electorama.com/em for list info
Alex Small
2003-08-04 18:35:36 UTC
Permalink
Post by Eric Gorr
I have found no evidence, in the original work, to support this claim.
His proofs are based upon the relation 'R' takes into full account
equal or distinct rankings.
While I could write to Dr. Arrow again, I would only want to do so if
presented with a compelling reason based on the original work.
Consider this argument:

If ALL voters have, or at least choose to report, dichotomous rankings (a
voter places the candidates within two groups, and is indifferent among
the candidates within each group but has a preference between the 2
groups), then there is ALWAYS a Condorcet winner, i.e. a candidate who
defeats all other candidates pairwise. Moreover, Approval Voting always
finds this winner.

(For more on this claim, go look at Brams and Fishburn's book _Approval
Voting_. I believe it's in Chapter 2, but I don't have the book in front
of me.)

Anyway, if we regard Approval Voting as a system that uses ranked ballots
(a claim that I dispute, but I'll go along with it for now to make my
point), then we find the following:

1) Approval Voting is non-dictatorial. (I HOPE nobody argues with this
one.)
2) Approval Voting is Pareto efficient, since if every single voter
prefers A to B then B will get no approval votes but A will get unanimous
approval. B will therefore lose, and A will win, unless A ties with
another unanimously approved candidate.
3) Approval Voting is a ranked method (I know, most other people here are
skeptical of that claim, but Eric isn't, and I'm trying to make a point
here).
4) Approval voting can handle 3 or more candidates.
5) Approval Voting satisfies IIA.

That last claim needs proof. Take as a given for now that when ALL voters
have dichotomous preferences Approval Voting finds the candidate who
defeats all other candidates pairwise (although he probably won't get a
majority in all pairwise contests, since a lot of voters might be
indifferent between 2 candidates). This claim is documented and proven in
Brams and Fishburn. If you send me to the library, I'll send you to the
library ;)

Anyway, if we add another candidate and assume that all voters still have
dichotomous preferences (they just put him in one of their two categories)
then there will still be a Condorcet candidate, and it will either be the
previous Condorcet winner, or the new guy. It all comes down to whether
the new guy defeats the previous winner pairwise.


Uh, oh, we now have a ranked voting system that satisfies IIA, Pareto, and
non-dictatorship when we have 3 or more candidates. What went wrong?

Nothing. We limited ourselves to the case where ALL voters have
dichotomous or binary preferences. We have a mapping from the set of all
voters with binary preferences to the set of all candidates, and we find
that it satisfies all of Arrow's criteria. But Arrow specified that the
mapping should be from ANY possible set of voter preferences (including
sets in which at least one voter has trichotomous preferences) to the set
of all candidates. If we try to "enlarge" our function, to handle a
larger domain that includes electorates where at least one person has
trichotomous preferences (or perhaps even more finely differentiated
preferences), we will find that at least one criterion will have to give
way.

We might decide to get rid of the assumption that the method allows each
voter to report his true preferences, WHATEVER THEY MIGHT HAPPEN TO BE.
Then we have Approval Voting.

We might get rid of IIA, which is flunked by virtually any Pareto
Efficient and non-dictatorial method that we can think of.


Finally, a question for Eric:

What will it take to persuade you that Approval is not a ranked method in
the sense that voters with ANY preference order are ABLE to report their
actual preferences, WHATEVER those preferences might happen to be? Will
anything short of Arrow's assurances do the job for you?



Alex


----
Election-methods mailing list - see http://electorama.com/em for list info
Bart Ingles
2003-08-10 18:10:22 UTC
Permalink
Condition 1' (from p.96): All logically possible orderings of the
alternative social states are admissible.

The original Condition 1 (from p.24) stated: Among all the alternatives
there is a set S of three alternatives such that, for any set of
individual orderings T1, ..., Tn of the alternatives in S, there is an
admissible set of individual orderings R1, ..., Rn of all the
alternatives such that, for each individual i, x Ri y if and only if x
Ti y for x and y in S.

Condition 3 (from p.27): Let R1, ..., Rn and R1', ..., and Rn' be two
sets of individual orderings and let C(S) and C'(S) be the corresponding
social choice functions. If, for all individuals i and for all x and y
in a given environment S, x Ri y if and only if x Ri' y, then C(S) and
C'(S) are the same (independence of irrelevant alternatives).

Condition P (from p.96): If x Pi y for all i, then x P y (Pareto
principal).

Condition 5 (from p.30): The social welfare function is not to be
dictatorial (non-dictatorship).


Theorum 2 (from p.97): Conditions 1', 3, P, and 5 are inconsistent.


Clearly, approval voting does not satisfy either Condition 1 or 1'.
Since x Ri y in Condition 3 appears to refer to *admissible* orderings,
and not to the individual orderings from which they were derived (see
original condition 1), approval voting does seem to meet Condition 3.

Bart
Post by Alex Small
Post by Eric Gorr
Arrow seems to be perfectly content with allowing equal rankings.
Approval voting merely requires the user to divide the options into two
different groups, but doing do does not violate Arrow's Axioms or
definitions regarding voter choice.
"However, it may be as well to give sketches of the proofs, both to show
that Axiom I and II really imply all that we wish to imply about the
nature of orderings of alternatives and to illustrate the type of
reasoning to be used subsequently." (page 14)
No, no, no, no, no!
Arrow assumes that, whether voters happen to have strict preferences or
whether they instead rank some candidates equal, voters are free to report
ANY transitive ranking of candidates (which might include equal rankings).
Based on this information, i.e. every voter giving his COMPLETE
preference order, the election method then chooses a winner.
Approval does NOT allow voters to express their complete preferences.
Sure, if a person happens to have a lot of equal rankings so that the
candidates fall into two groups, then Approval lets that PARTICULAR voter
express his full preferences. BUT, if the person sorts the candidates
into 3 or more categories, Approval does not let them express their
complete preferences.
Once again, Arrow basically proves that no method can satisfy all of the
1) Non-dictatorship (plenty of methods, and any seriously proposed
method, will satisfy this)
2) Pareto (plenty of methods, and any seriously proposed method, will
satisfy this)
3) IIAC
4) The use of RANKED ballots, which allow ANY voter to indicate his
entire preference, WHATEVER it might happen to be.
APPROVAL DOES NOT SATISFY THIS CRITERION! If my preference is A>B>C then
I have to make a decision about whether or not to approve B.
Can I please get some back-up here? Somebody, anybody, please back me up
on this? I can't believe how difficult it is to drive home the point that
Approval Voting is not a ranked method.
Anyway, since Approval flunks criterion #4, it is in keeping with Arrow's
Theorem. It flunks at least one of his criteria.
Alex
----
Election-methods mailing list - see http://electorama.com/em for list info
Bart Ingles
2003-08-10 22:14:20 UTC
Permalink
I should add that the original Condition 1 (included below) was used in
the original 1951 theorum, but not in the 1962 version. The later
version replaced it with the stronger Condition 1'.

I mainly included the older Condition 1 because it seemed to settle the
question of whether x Rn y in Condition 3 referred to an individual's
complete private orderings, or orderings on an actual ballot. It seems
to be the latter, implying that approval voting satisfies at least
Arrow's definition of IIAC.
Post by Bart Ingles
Condition 1' (from p.96): All logically possible orderings of the
alternative social states are admissible.
The original Condition 1 (from p.24) stated: Among all the alternatives
there is a set S of three alternatives such that, for any set of
individual orderings T1, ..., Tn of the alternatives in S, there is an
admissible set of individual orderings R1, ..., Rn of all the
alternatives such that, for each individual i, x Ri y if and only if x
Ti y for x and y in S.
Condition 3 (from p.27): Let R1, ..., Rn and R1', ..., and Rn' be two
sets of individual orderings and let C(S) and C'(S) be the corresponding
social choice functions. If, for all individuals i and for all x and y
in a given environment S, x Ri y if and only if x Ri' y, then C(S) and
C'(S) are the same (independence of irrelevant alternatives).
Condition P (from p.96): If x Pi y for all i, then x P y (Pareto
principal).
Condition 5 (from p.30): The social welfare function is not to be
dictatorial (non-dictatorship).
Theorum 2 (from p.97): Conditions 1', 3, P, and 5 are inconsistent.
Clearly, approval voting does not satisfy either Condition 1 or 1'.
Since x Ri y in Condition 3 appears to refer to *admissible* orderings,
and not to the individual orderings from which they were derived (see
original condition 1), approval voting does seem to meet Condition 3.
Bart
----
Election-methods mailing list - see http://electorama.com/em for list info
John B. Hodges
2003-08-03 12:47:40 UTC
Permalink
Date: Sat, 2 Aug 2003 13:17:36 -0700 (PDT)
Subject: Re: [EM] Arrow's Theorem - The Return (again)
(snip much)
30 (A>B)>C
30 (C)>A>B
40 (B)>A>C
The parentheses indicate which candidates a particular group of voters
approved. In this case, B wins with 70 votes.
Now give all of the voters a ballot again, but don't include candidate C
on it. If the people who approved both A and B the first time around are
rational they will only approve A this time. If the people who only
approved C the first time around are rational they will only approve A
this time. A now wins 60-40.
A mathematician at Northwestern published a paper on this premise a few
years back. He used more sophisticated assumptions about voter behavior,
but the final conclusion was that Approval Voting flunks IIAC. I wasn't
impressed when I ran across it. If we can use a single counter-example to
prove that a statement is false, then a long proof is unnecessary. But I
suspect he's from the Saari school of voting theory (Saari used to teach
at Northwestern), and really wanted to drive home that Approval Voting
isn't perfect. (I'm sure everybody here, Donald especially, was
completely shocked to learn that Approval Voting isn't perfect. ;)
Alex
JBH here- I was reading Dummett recently, and his comment on the
relevance of the Independence from Irrelevant Alternatives Criterion
was that it implied that there was no "straightforward" voting
system, i.e. that there was no voting system that never gave
incentives for insincere reporting of the voter's preferences.

Alex's example above shows the possibility of a "spoiler effect",
i.e. in a two-person race between A and B, A wins, but adding C to
the race gives the victory to B. Those who vote for C give the
election to their last choice, so if they understood the situation in
advance, they would abstain from voting for their first choice. That
is significant; up to now I thought that Monotonicity implied the
absence of a spoiler effect. If avoiding the spoiler effect depends
on a voting method satisfying IIAC, there will be very, very few
methods that qualify. (Does anybody KNOW of any?)

Then there is the question of how MUCH of a problem this is;
different methods may all share the same set of flaws, but to
different degrees. Plurality suffers from the spoiler effect very
reliably, even if the third party is small. IRV suffers from it
differently; it is center parties that spoil, not wing parties, and
this happens only when the wing party grows larger than its
neighboring centrist party. If Approval also suffers from a spoiler
efect, we have to get some estimate of the relevant circumstances.
--
----------------------------------
John B. Hodges, jbhodges@ @usit.net
Do Justice, Love Mercy, and Be Irreverent.
----
Election-methods mailing list - see http://electorama.com/em for list info
Alex Small
2003-08-03 16:42:14 UTC
Permalink
Alex's example above shows the possibility of a "spoiler effect", i.e.
in a two-person race between A and B, A wins, but adding C to the race
gives the victory to B. Those who vote for C give the
election to their last choice, so if they understood the situation in
advance, they would abstain from voting for their first choice.
No. There is never a disincentive to abstain from approving your first
choice if you use approval voting. Those who voted for C decided NOT to
approve their second choice as well. Maybe they had inadequate polling
data and didn't realize what would happen if they abstained. Maybe they
wanted to punish A for not being good enough. That is their right, and I
will not criticize people who withhold votes from candidates whom they
find to be unworthy.

I normally think of the spoiler effect as happening when the addition of a
new candidate changes the outcome without the new candidate winning, and
all voters voting sincerely. In that case, any system that flunks IIA has
the potential for a spoiler effect. However, it's much less severe in
approval because well-informed voters can make sure there is no
"spoiling." It's only if they follow sincere but uninformed information
that they get "spoilage."

I'm going to post more on this in the next few weeks. I'm examining Nash
equilibria in 3-way Approval races. I'm looking at situations where
everybody approves one of the top 2, so that we simulate what's likely to
happen in response to polls. Interesting things can happen when there's
no CW. More on that in a few weeks.



Alex


----
Election-methods mailing list - see http://electorama.com/em for list info
Rob Speer
2003-08-03 18:17:05 UTC
Permalink
Post by John B. Hodges
Alex's example above shows the possibility of a "spoiler effect",
i.e. in a two-person race between A and B, A wins, but adding C to
the race gives the victory to B. Those who vote for C give the
election to their last choice, so if they understood the situation in
advance, they would abstain from voting for their first choice. That
is significant; up to now I thought that Monotonicity implied the
absence of a spoiler effect. If avoiding the spoiler effect depends
on a voting method satisfying IIAC, there will be very, very few
methods that qualify. (Does anybody KNOW of any?)
Random Dictator.

But seriously:

My advisor at MIT is currently studying a method that has been
discovered independently by a few people, called either Unique Winning
Alliance or Nash-Condorcet (after John Nash).

Since it is non-dictatorial and Pareto-optimal, it of course can't
actually satisfy IIAC in the winner it ultimately chooses. However, the
method is non-deterministic, and the percentage chances of a given
candidate winning _are_ independent from irrelevant alternatives.

There are a couple of ways to describe it: the complicated, detailed way
and the simple way. The complicated way first:

We know that there isn't always a candidate who beats every other
candidate pairwise (i.e. a Condorcet winner). However, there is always
a _combination_ of candidates that beats every other such combination.
Such a combination might be 100% candidate A (a Condorcet winner), or
maybe something like 60% A, 30% B, 10% C (a cycle). The way you can
determine whether one combination beats another is to take percentages
of the winning margins and add them. If X>Y is the number of votes by
which X beats Y, then the combination (80% A, 20% B) beats (80% C, 20%
D) by .64*(A>C) + .16*(B>C) + .16*(A>D) + .04*(B>D).

Though it may seem computationally daunting to find such a combination
(the Unique Winning Alliance), it is actually easily solved by linear
programming, which is something that, for example, Matlab can do. You
can just treat the pairwise victory matrix as a matrix of inequalities
to be solved.

Once you have found the UWA, you still of course need to pick a winner
from it. In a sense you get a "Nash Set" of candidates, which is always
a subset (possibly the same set) of the Smith Set, who are the people
with non-zero shares in the UWA, and you need to pick a winner from it.

The nondeterministic method that sort of satisfies IIAC is to choose the
winner randomly, weighted by their percentages of the win.

Now for the simple description, which justifies wanting to name it after
John Nash.

Treat the pairwise matrix of candidates as a zero-sum game (like Rock
Paper Scissors). Two players each choose a candidate, and if one
candidate beats the other pairwise, the player who chose the winner gets
a number of points equal to the margin of victory. Determine the
winning strategy for the game (which will be a set of possible choices
and the probability that you will make them). Then make one move in this
game according to that winning strategy. The candidate chosen by that
move wins the election.

(If there is a Condorcet winner, then the winning strategy will be to
always pick that candidate, as it always wins. Consider the childhood
RPS variant, "Rock, Paper, Scissors, Nuclear Bomb".)

The properties of this method:
* It is non-dictatorial and Pareto-optimal.
* It is _not_ monotonic. The share that someone gets of the UWA might go
down if they get additional votes. It's a surprising flaw, but a
necessary outcome of the almost-IIAC-ness.
* It is cloneproof. Clones will simply end up dividing their share of the
UWA between them.
* It is almost IIAC. Certainly, if a member of the Nash Set drops out, it
will change the result, but that member would have had a chance to win,
so he isn't especially irrelevant. The result stays the same if anyone
outside the Nash Set leaves. This does not break Arrow's Theorem
because Arrow does not allow for non-deterministic methods.
* Determining whether a candidate is in the Nash Set _is_ monotonic -
you can't fall out of the Nash Set by getting more votes. Thus, UWA can
be completed by other methods besides Weighted Random. UWA Sequential
Dropping seems especially appealing.

Some properties of the Nash Set:
* It is unique as long as ties are prevented. This can be done by adding
a strict preference ordering that counts as half of a vote as a
tiebreaker.
* It always has an odd number of candidates in it.

I hope others find this method as cool as I do. Sure, it's impractical,
but I find the Nash Set to be an even nicer theoretical tool than the
Smith Set.
--
Rob Speer

----
Election-methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2003-08-03 21:13:32 UTC
Permalink
Dear Rob,

it has been proven by Prasanta K. Pattanaik and Bezalel Peleg
("Distribution of power under stochastic social choice rules,"
ECONOMETRICA, vol. 54, p. 909-921, 1986) that there is no
preferential paretian non-dictatorial single-winner method
that meets regularity.

"Regularity" says that an additional candidate cannot increase
the winning probability of an already running candidate. Thus,
regularity can be considered a probabilistic generalization of
Arrow's independence from irrelevant alternatives. Therefore,
I doubt that it is possible to get less manipulable single-
winner methods by making them less deterministic.

However, I have some questions about Unique Winning Alliance:

1) What is the exact definition for the "Nash Set"? (Please don't
use game theoretical terminology.)

2) Could you give an explicite example where the Smith Set differs
from the Nash Set?

3) What are, in your opinion, the advantages of Unique Winning
Alliance compared e.g. to Smith//RandomDictatorship? (At least,
Smith//RandomDictatorship is monotonic.)

Markus Schulze
----
Election-methods mailing list - see http://electorama.com/em for list info
Rob Speer
2003-08-03 23:44:42 UTC
Permalink
Post by Markus Schulze
it has been proven by Prasanta K. Pattanaik and Bezalel Peleg
("Distribution of power under stochastic social choice rules,"
ECONOMETRICA, vol. 54, p. 909-921, 1986) that there is no
preferential paretian non-dictatorial single-winner method
that meets regularity.
[...]
Okay. I hadn't heard of this result - that's actually a more useful
statement than Arrow's Theorem.

Yes, indeed in UWA you can add a candidate that has some share of the
win, and another candidate's share of the win will increase.
Post by Markus Schulze
1) What is the exact definition for the "Nash Set"? (Please don't
use game theoretical terminology.)
Exact definitions:
An "alliance" is an assignment of scores between 0 and 1 to every
candidate, such that the scores add up to 1.

The Unique Winning Alliance (UWA) is the alliance that beats all other
alliances, pairwise. (See my previous message for how to determine
manually whether one alliance beats another.)

The Nash set is the set of candidates whose scores in the UWA are
greater than 0.
Post by Markus Schulze
2) Could you give an explicite example where the Smith Set differs
from the Nash Set?
Sure. Consider this pairwise result matrix:

A B C D
A 0 +1 -1 +1
B -1 0 +1 +1
C +1 -1 0 -1
D -1 -1 +1 0

The UWA is 33% A, 33% B, 33% C, so the Nash set is ABC.
D is not a member of the Nash set because there is a candidate, B, who
is strictly better than D in terms of pairwise results. Therefore, any
alliance with D in it would lose to one which gives D's share to B.

(I'm not sure if this is the reason _every_ time a candidate is excluded
from the Nash set - it would be convenient.)
Post by Markus Schulze
3) What are, in your opinion, the advantages of Unique Winning
Alliance compared e.g. to Smith//RandomDictatorship? (At least,
Smith//RandomDictatorship is monotonic.)
[Aside: Where did the // in method names come from, anyway?]

First to be more clear on terminology: The method I described is what my
advisor calls UWA-Random. UWA is a class of methods.

Because it is not monotonic and not deterministic, I don't think
UWA-Random is actually a very viable method. However, the property it
has - which could be called Very Local IIA, but which you point out is
not the same as regularity - is interesting.

I think there is a lot of promise in UWA completion methods, though.
I mentioned UWA-SD (UWA Sequential Dropping) as a particularly appealing
method. Basically, take the definition of Schwartz Sequental Dropping,
and replace "Schwartz set" with "Nash set".

I believe that this would be monotonic and cloneproof, though I haven't
looked into it much.
--
Rob Speer

----
Election-methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2003-08-04 00:53:59 UTC
Permalink
Dear Rob,
Post by Rob Speer
(...)
* It is _not_ monotonic. The share that someone gets of the UWA might
go down if they get additional votes. It's a surprising flaw, but a
necessary outcome of the almost-IIAC-ness.
(...)
* It is almost IIAC. Certainly, if a member of the Nash Set drops out, it
will change the result, but that member would have had a chance to win,
so he isn't especially irrelevant. The result stays the same if anyone
outside the Nash Set leaves. This does not break Arrow's Theorem
because Arrow does not allow for non-deterministic methods.
However, the property it has - which could be called Very Local IIA,
but which you point out is not the same as regularity - is interesting.
4) What does "almost IIAC" resp. "Very Local IIA" mean in this context?
Does it mean that an additional candidate who isn't in the new Nash Set
cannot change the winning probability of an already running candidate?

5) Could you give a concrete example where the Nash Set differs from
the Uncovered Set? (The "Uncovered Set" is the set of candidates who
beat every other candidate with a path of length 1 or 2. In other
words: When "X >= Y" means that the number of voters who strictly
prefer candidate X to candidate Y isn't strictly smaller than the
number of voters who strictly prefer candidate Y to candidate X,
then candidate A is in the "Uncovered Set" if & only if for every
other candidate B at least one of the following two statements is
valid: [1] A >= B. [2] There is a candidate C with A >= C >= B.)

******
Post by Rob Speer
Aside: Where did the // in method names come from, anyway?
Lowell Bruce Anderson has introduced this terminology. "X//Y"
means that, at first, election method X is applied. But when
election method X doesn't lead to a unique winner but to a set
of potential winners, then all candidates who are not in this
set of potential winners are eliminated and election method
Y is applied to the remaining candidates.

Markus Schulze
----
Election-methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2003-08-04 10:20:59 UTC
Permalink
Dear Rob,
Post by Rob Speer
(...)
* It is _not_ monotonic. The share that someone gets
of the UWA might go down if they get additional votes.
Because it is not monotonic and not deterministic, I
don't think UWA-Random is actually a very viable method.
Could you forward an example where monotonicity is violated?

Markus Schulze
----
Election-methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2003-08-04 14:12:08 UTC
Permalink
Dear Rob,

I see the following problem with the Nash Set:

Situation 1: A > B, A > D, B > C, C > A, D > B, D > C.
The Nash Set is ACD.

Situation 2: Some voters rank candidate C higher so
that "D > C" is changed to "C > D". Now, the Nash Set
is ABC.

In so far as I haven't made any presumptions about the
strengths of the pairwise defeats, it is (at least for
all those election methods X that are not identical to
RandomCandidate in the circular 3-candidate case A>B>C>A)
trivial to create an example where Nash//X chooses
candidate C in situation 1 and doesn't choose candidate C
in situation 2 resp. where Nash//X decreases the winning
probability of candidate C from situation 1 to situation 2
so that Nash//X violates monotonicity.

Do you agree with my conclusions?

Markus Schulze
----
Election-methods mailing list - see http://electorama.com/em for list info
Rob Speer
2003-08-04 17:55:41 UTC
Permalink
Post by Markus Schulze
Dear Rob,
Situation 1: A > B, A > D, B > C, C > A, D > B, D > C.
The Nash Set is ACD.
Situation 2: Some voters rank candidate C higher so
that "D > C" is changed to "C > D". Now, the Nash Set
is ABC.
This is true, at least with some pairwise defeat values.
Post by Markus Schulze
In so far as I haven't made any presumptions about the
strengths of the pairwise defeats, it is (at least for
all those election methods X that are not identical to
RandomCandidate in the circular 3-candidate case A>B>C>A)
trivial to create an example where Nash//X chooses
candidate C in situation 1 and doesn't choose candidate C
in situation 2 resp. where Nash//X decreases the winning
probability of candidate C from situation 1 to situation 2
so that Nash//X violates monotonicity.
Do you agree with my conclusions?
Yes. In fact, here's a specific example:

Situation 1:
A B C D
A 0 1 -2 3
B -1 0 2 -3
C 2 -2 0 -1
D -3 3 1 0

Situation 2:
Change one D>C to C>D.

For any reasonable X, under Nash//X, C wins situation 1, and B wins
situation 2.

Hmm. That's unfortunate.

What's interesting is that in both situations, SSD and Ranked Pairs
choose either A or C (down to a tiebreaker) - they avoid the candidates
who might not be in the Nash set. Although actually restricting the
election to the Nash set is not monotonic, do good Condorcet methods
tend to pick winners in the Nash set anyway? Are there cases where they
don't? Are they justified?
--
Rob Speer

----
Election-methods mailing list - see http://electorama.com/em for list info
Rob Speer
2003-08-04 19:46:12 UTC
Permalink
I'd be happy to incorporate the Nash set into my simulations and test this
out for you, but I may still be a bit unclear on the algorithm to calculate
the Nash set.
First of all, I've been doing it with a Python program. If it will be
any help, I've put up my program at:

http://takeneggs.com/files/uwa.tar.gz

It uses the lpsolve library, which is included in that file, but which
is not cross-platform. It'll only work on Linux.

On any other platform (and this is where I begin to admire you for your
determination) you'd have to also install lpsolve, from
http://takeneggs.com/files/lpsolve-3.2-0.3.tar.gz.

Not the easiest thing to use, I'll admit.
Consider each pair of candidates X and Y such that X beats Y pairwise.
If X does at least as well against every other candidate Z pairwise as Y
does against Z, exclude Y from the Nash set.
Consider each pair of candidates X and Y such that X beats Y pairwise.
If X beats every other candidate Z pairwise that Y beats, exclude Y from
the Nash set.
Or is it something else?
It would be nice if there were a simple method like that. I discovered
when responding to Markus that this was not the case.

I responded to him (meaning to respond to the list) with this example
where the Nash set is ABC but the Uncovered set is ABCD:

A B C D E F
A 0 5 -5 6 3 -3
B -5 0 5 3 -3 6
C 5 -5 0 -3 6 3
D -6 -3 3 0 1 1
E -3 3 -6 -1 0 1
F 3 -6 -3 -1 -1 0

B does not do better in all pairwise contests than D - D in fact beats
E, while B doesn't - but D is still excluded from the Nash set, which is
ABC.

A criterion I've thought about but haven't tested: the Nash set is the
smallest set such that, for any X outside of the Nash set, there exists
a candidate A in the Nash set, such than for any B in the Nash set A
beats B by more than X beats B.

(This is the "does at least as well" rule, but it only matters how you
do against members of the Nash set.)

But I'm not guaranteeing that that works. The only guaranteed definition
is the mathematical one:

Let P(x,y) be the amount by which candidate x beats candidate y. Call
the candidates C1, C2, ..., Cn. Find the series of values v1, v2, ...,
vn that satisfies the N+1 equations

v1 + v2 + ... + vn = 1
For any i in 1...n:
v1*P(Ci, C1) + v2*P(Ci, C2) + ... + vn*P(Ci, Cn) <= 0

The UWA is the set of values v1...vn.
The Nash set is the set of candidates Cj such that vj > 0.

--
Rob Speer

----
Election-methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2003-08-04 18:03:20 UTC
Permalink
Dear Eric,

as far as I remember correctly, Arrow calls the property
that the used election method must be defined for every
possible set of transitive rankings "Unrestricted Domain."
Approval Voting doesn't meet Unrestricted Domain.

Markus Schulze
----
Election-methods mailing list - see http://electorama.com/em for list info
Eric Gorr
2003-08-04 18:09:52 UTC
Permalink
Post by Markus Schulze
as far as I remember correctly, Arrow calls the property
that the used election method must be defined for every
possible set of transitive rankings "Unrestricted Domain."
Approval Voting doesn't meet Unrestricted Domain.
Do you know where? Or could you locate it again?

Could not find "Unrestricted Domain" in the index.
--
== Eric Gorr ========= http://www.ericgorr.net ========= ICQ:9293199 ===
"Therefore the considerations of the intelligent always include both
benefit and harm." - Sun Tzu
== Insults, like violence, are the last refuge of the incompetent... ===
----
Election-methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2003-08-04 18:52:07 UTC
Permalink
Dear Rob,
Post by Rob Speer
What's interesting is that in both situations, SSD and Ranked Pairs
choose either A or C (down to a tiebreaker) - they avoid the candidates
who might not be in the Nash set. Although actually restricting the
election to the Nash set is not monotonic, do good Condorcet methods
tend to pick winners in the Nash set anyway? Are there cases where
they don't?
Example:

A B C D
A 0 1 -5 4
B -1 0 6 -2
C 5 -6 0 -3
D -4 2 3 0

The Nash Set is ACD. SSD, Ranked Pairs, MinMax, Kemeny-Young, and
Smith//Borda would choose candidate B.
Post by Rob Speer
Are they justified?
As you say, these cases are justified by the fact that "restricting
the election to the Nash set is not monotonic."

Markus Schulze
----
Election-methods mailing list - see http://electorama.com/em for list info
Rob Speer
2003-08-04 19:52:26 UTC
Permalink
Post by Rob Speer
A B C D
A 0 1 -5 4
B -1 0 6 -2
C 5 -6 0 -3
D -4 2 3 0
The Nash Set is ACD. SSD, Ranked Pairs, MinMax, Kemeny-Young, and
Smith//Borda would choose candidate B.
I admire whatever method you've been using to find the Nash Set, but it
seems to have broken down there. The Nash Set for that matrix is ABC.

Incidentally, that breaks the guess I just made at a simpler algorithm
to find the Nash set. I can't see a clear reason why D is excluded.
--
Rob Speer

----
Election-methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2003-08-04 20:19:44 UTC
Permalink
Dear Rob,
Post by Rob Speer
Post by Rob Speer
A B C D
A 0 1 -5 4
B -1 0 6 -2
C 5 -6 0 -3
D -4 2 3 0
The Nash Set is ACD. SSD, Ranked Pairs, MinMax, Kemeny-Young, and
Smith//Borda would choose candidate B.
I admire whatever method you've been using to find the Nash Set, but it
seems to have broken down there. The Nash Set for that matrix is ABC.
What is the UWA in the example above due to your calculation?

Markus Schulze
----
Election-methods mailing list - see http://electorama.com/em for list info
Rob Speer
2003-08-05 00:17:38 UTC
Permalink
Post by Markus Schulze
Post by Rob Speer
A B C D
A 0 1 -5 4
B -1 0 6 -2
C 5 -6 0 -3
D -4 2 3 0
[...]
What is the UWA in the example above due to your calculation?
50% A, 41.7% B, 8.3% C.
--
Rob Speer

----
Election-methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2003-08-05 01:27:26 UTC
Permalink
Dear Rob,

A B C D
A 0 1 -5 6
B -1 0 4 -3
C 5 -4 0 -2
D -6 3 2 0

What is the UWA in the example above due to your calculation?

Markus Schulze
----
Election-methods mailing list - see http://electorama.com/em for list info
Markus Schulze
2003-08-04 21:26:00 UTC
Permalink
Dear Rob,
Post by Rob Speer
I responded to him (meaning to respond to the list) with this
A B C D E F
A 0 5 -5 6 3 -3
B -5 0 5 3 -3 6
C 5 -5 0 -3 6 3
D -6 -3 3 0 1 1
E -3 3 -6 -1 0 1
F 3 -6 -3 -1 -1 0
Actually, the Uncovered set is ABCDE.

Markus Schulze
----
Election-methods mailing list - see http://electorama.com/em for list info
Eric Gorr
2003-08-02 19:25:25 UTC
Permalink
I recently purchased a copy of Arrow's book 'Social Choice and
Individual Values' Second Edition (ISBN: 0300013647).

The last time this topic came up, it was argued that Arrow's Theorem
only involved strict preferences, based on the document found at:

http://faculty-web.at.northwestern.edu/economics/chung/mr/Reny.pdf

However, this does not appear to be the case.

On page 13, Arrow states as Axiom I

For all x and y, either x R y or y R x

For Arrow's purposes, R is defined to mean in the case of x R y that a
person either preferrs x over y or is indifferent in the comparison of
x to y. To quote Arrow again,

"Note that Axiom I is presumed to hold when x = y, as well as when x
is
distinct from y, for we ordinarily say that x is indifferent to
itself
for any x, and this implies x R x." (page 13)

After a few more formal statements and descriptions, based, in part, on
Axiom I, he goes on to say that:

"However, it may be as well to give sketches of the proofs, both to
show
that Axiom I and II really imply all that we wish to imply about the
nature of orderings of alternatives and to illustrate the type of
reasoning to be used subsequently." (page 14)

On page 36, he goes on to develop the Pareto principle based, in part,
on Axiom I.

"The Pareto principle was originally given in the text (p.36) as a
form of
the compensation principle." (page 96)

So, (to ask a question) why does Reny use only strict preferences?
Well, Arrow does the same thing near the end of his book, starting on
page 96, he reasoning appears to be:

"Since the Pareto principle is universally accepted, the new set of
conditions will be easier to compare with other formulations of the
problem of social choice." (page 96)

"We give it [Pareto principle] here in a slightly weaker form
(involving
only strict preferences)." (page 96)

I would venture to guess that Reny used the same basic philosophy in
his paper when writing about both Arrow's Theorem and
Gibbard-Satterthwaite theorem.


Now, I fully admit that this may be a case of knowing just enough to
get me into trouble and would appreciate it if someone else could take
a look at the book and verify or clarify what I have said based on the
original work.

----
Election-methods mailing list - see http://electorama.com/em for list info
Alex Small
2003-10-22 05:36:12 UTC
Permalink
Post by Eric Gorr
I recently purchased a copy of Arrow's book 'Social Choice and
Individual Values' Second Edition (ISBN: 0300013647).
The last time this topic came up, it was argued that Arrow's Theorem
Eric-

I freely concede that I was wrong when I said that Arrow's Theorem assumes
strict preferences. Arrow's Theorem allows for the possibility of equal
rankings. I admit it. And I admit that Reny makes an unnecessarily
restrictive assumption. So let's remove Reny from further discussion.

However, the context of that argument was whether or not Approval Voting
is a ranked method in the sense of Arrow's Theorem. And the answer is a
resounding NO!!!!!!!

Arrow assumes that the outcome is determined when voters report their
preferences, whatever they might be, or whatever the voters report them as
when they vote insincerely. If there are 3 candidates I can vote A>B>C,
A=B>C, A>B=C, etc.

Approval Voting violates that assumption. With 3 candidates Approval
Voting requires that I vote 2 of the candidates equal. Now, if that's
what I was planning to do anyway (either because it's a sincere preference
or because of some strategic concern) then I'm in good shape. But if I
was planning to sort them into 3 categories then Approval Voting says
"sorry, no can do."

Now, as I recall in our last exchange over this a great many photons were
shuffled back and forth over fiber optic cables as we argued this point.
I don't know how to make it any clearer.

But I'm going to go even further and argue that CR is not a ranked method.
I know, this will be controversial, but I'm in a reckless mood tonight.
In the past 48 hours I've proven just how fragile 2D localization of
photons is relative to 3D. I feel invincible. So here goes.

Arrow's Theorem assumes that the social choice function is a mapping from
the set of voter preferences to the set of candidates. So if I go into
the voting booth and fill out my ballot to indicate A>B>C (for instance)
that's all that matters. Doesn't matter whether I say A=5, B=2, C=0, or
A=5, B=4, C=0. Regardless of which grade ballot I submit, the machine
that reads the ballot should say "Ah, this ballot indicates A>B>C." And
that piece of info should be sufficient to determine the outcome.

However, with CR the ballots A=5, B=2, C=0 vs. A=5, B=4, C=0 can produce
different election results.

Anyway, that's all I have to say about that.



Alex


----
Election-methods mailing list - see http://electorama.com/em for list info
Continue reading on narkive:
Loading...