[EM] CR style ballots for Ranked Preferences

[Buddha Buck]

Jobst Heitzig <heitzig at mbox.math.uni-hannover.de> writes:

> I think what most people mean when saying that Condorcet methods are
> 
>    "INCONSISTENT" 
> 
> (a bad name in my opinion since it contains no information about how it's
> defined but instead contains a verbal evaluation that should have no place
> in axiomatics :-) is the following: 
> 
> || It may happen that when the electorate is split in two arbitrary groups
> || and in both groups there is the same Condorcet winner (that means, when
> || only the voters in the group are considered), this alternative might
> || fail to be a Condorcet winner for the whole group.

Hmm...  I'd love to see an example of this, since I fail to see how it
could happen.  

Let's say we have an n-candidate election, with candidates A..N.
For any two candididates I and J, let IJ be the number of ballots that
ranked I strictly preferrable to J.  Of necessity, since no candidate
can be ranked preferrable to itself, then II = 0 for all candidates
I.  Also, since it is possible for a ballot to rank two candidates
equally, it is not true in general that IJ + JI = total number of
ballots.

To say that A is the Condorcet winner is to say that for all
candidates I besides A, then AI > IA.

If the Condorcet Criterion is itself inconsistant, then it should be
possible to partition the ballots in a Condorcet election such that
all the partitions have the same Condorcet Winner, but the combined
ballots have either no Condorcet Winer, or a different Condorcet
winner.  I shall prove that the Condorcet Criterion is not inconsitant
by contradiction.

Suppose the Condorcet Criterion is inconsistant.  Then there is an
election, candidate A is not the Condorcet winner, but the ballots can
be partitioned into n groups 1...n, such that A is the Condorcet
winner in all the groups.

Then by definition of the Condorcet winner, we have, for all
candidates I besides A:

  AI1 > IA1
  ...
  AIn > IAn

Because inequalities are additive, we have 

  AI1 + ... + AIn > IA1 + ... +IAn

for all I not A.

But since every ballot is accounted for in the partition, we have for
the whole election AI = AI1 + ... +AIn, and IA = IA1 + ... + IAn.
Therefore, for all I not A, we have AI > IA.  However, this is the
definition of the Condorcet winner, so candidate A is the Condorcet
winner, which is a contradiction.  Therefore, if candidate A is not
the Condorcet winner, it is impossible for the ballots to be
partitioned into n partitons 1...n, such that A is the Condorcet winner
in all partitions.  Therefore, the Condorcet Criterion is not
inconsistant.

It seems pretty straightforward to me.  If others say the Condorcet
Criterion is inconsistant, I'd like to be shown where I went wrong.

Of course, any particular Condorcet METHOD could yield an inconsistant
result when every partition has the same winner, but not every
parition's winner was a Condorcet winner.

(I define a Condorcet Method as any method which, if there is an
expressed Condorcet Winner, elects that Condorcet Winner.  

> 
> However, what I can't see is why this should be of any importance.
> Instead, it just shows that in order to determine the winner, one cannot
> divide the electorate into groups but must consider all voters
> simultaneously!

For the purposes of administering an election, the electorate tends to
be broken into groups.  At the simplest level, the electorate might be
too large to all vote using the same voting machine (not enough time
in the election), or there may be different elections simultaneously
that have overlapping but non-identical electorates (such as an
election for a national office being held at the same time as an
election for a local office), so the ballot papers are not identical
for each election.  

This leads to what I call the "sumability criterion": A method meets
the sumability criterion ("is summable") if the overall winner can be
determined by an amount of information from each district which is
"small", i.e., polynomial to the number of candidates and independent
of the number of voters.  (I'd appreciate help making that criterion
more formal.)

A lot of methods are summable, Plurality is summable: each district
need only report total votes for each candidate.  Approval is summable
the same way.  Pairwise methods (including most Condorcet methods) are
summable because the pairwise beat matrix for each district.  Borda is
summable; just report the Borda counts.

Some methods are not summable.  IRV is the obvious one here.  The
best-case for district reporting for IRV shown so far is proportional
to n2^n, where n is the number of candidates.  This is not polynomial
in n.

I am not clear on the mechanics of all the methods proposed that use
dyadic rankings, so I don't know if they are summable or not.

I consider summability to be important because it makes elections
practical with a large electorate.  I look back at the recount issues
with the recent US Presidential election in Florida, which had over 10
candidates on the Ballot and over 4,000,000 voters, and a final margin
of victory less than the expected margin of error, and I shudder to
think of what would have happened if a non-summable method, such as
IRV had been used.  Whenever a new uncounted collection of ballots was
discovered, or new absentee ballots were received, the entire election
would have had to be recounted.

> 
> I consider this a very profound disadvantage of "classical" preference
> ballots. There is however a *very simple* (at least theoretically) way to
> solve this problem: 
> 
> || just allow voters to express that they are "UNDECIDED" about certain
> || pairs of alternatives. In other words: do not assume that individual
> || preference relations are complete, but allow them to be any quasi-order
> || (that is, any reflexive and transitive relation). One can even allow
> || cycles in individual preferences! 

If one allows cycles, it isn't transitive.

> 
> (Beware: Undecidedness can *not* always be expressed by simply tying
> alternatives: I can very well prefer A to B without knowing how to
> value C at all. If I had to express this by tying C to either A or B I
> would unwillingly express a preference for C over B or for A over
> C!)

So are you suggesting that, for instance, in an election between A, B,
C and D, the following truncated ballot:

A>B>C

should count towards the pairwise totals for:

A>B
A>C
B>C

but not for:

A>D
D>A
B>D
D>B
C>D
D>C

i.e., it would count neither for nor against D?

Hmmm, how should a voter who knows that A is better than D, but
doesn't know where D ranks among B or C?

> There are enough rules that can handle such kinds of preferences. One
> example that is I think a chimere between IRV and approval voting:
> 
> || In the first round, each alternative gets a weight equal to the number
> || of voters that value it "optimal" (that is, that do not strictly prefer
> || any other alternative over it). Drop the one with the smallest weight
> || and erase it from all the individual preference relations. Iterate
> || until stable.

What is "stable" in this case?

To me, this sounds almost like a classic definition of IRV.  The only
way I could see to apply it to Approval is to apply it to Approval
ballots.  In which case, I see it as trivially eliminating all
candidates except for the Approval winner.  So given 2-level ballots,
IRV selects the same winner as Approval, but with lots more work.
This indicates... what?

OK, I just checked your web-site.  It seems that the ballots you are
using ask the voter to create a quasi-order from the candidates.  I
don't recall a "quasi-order" from my Discrete Math classes (and it
isn't in my texts), but it appears to be the case that a set is
quasi-ordered if for every pair (a,b) of elements of the set then
either a<b, a>b, a==b or a!b, but not more than one, and if a<b then
b>a, if a>b, b<a, if a==b, b==a, and if a!b, b!a, and for all a, a==a.
I haven't read enough of your paper to determine how you do Approval
with that ballot set.

It seems clear to me that the method you describe immediately above is
not summable, and in that respect is clearly worse than standard IRV
because instead of requiring n2^n different ballot tallies in order to
represent the ballots (without transmission of the actual ballots), it
would require 2^(n(n-1)) ballot tallies.

> My GrouCho preference aggregator ( http://welcome.to/groucho ) uses a 
> different method that is more like Tideman's and Schulze's rules (see the
> preprint on that website).
> 
> Jobst