[EM] CR style ballots for Ranked Preferences

[Jobst Heitzig]

On 24 Sep 2001, Buddha Buck wrote:

> Hmm...  I'd love to see an example of this, since I fail to see how it
> could happen.  
> Therefore, the Condorcet Criterion is not
> inconsistant.

Sorry about that: you are of course completely right! Condorcet methods
can only be inconsistent in cases where some of the groups lacks a
Condorcet winner.

> 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.

Right! So summability is the criterion, not "consistency"!

> If one allows cycles, it isn't transitive.

Of course, but individual transitivity is almost completely irrelevant,
especially for many summable rules! The only thing that might go wrong is
Pareto optimality when *all* voters contain the same cycle.

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

(What does truncated ballot mean? The question is how we should interpret
this incomplete preference information...)

> 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?

Yes! I completely think so. Since the voter did not express preferences
concerning D, he might just be completely uninformed about D and might
just want to delegate the decision about D to the other voters.

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

It's preference quasi-order would look like this:

   A
  / \
 B   D
 |
 C

(This is a Hasse diagram) The crucial point is that "ranking" is the wrong
idea - there might be no "ranks" but only some preferences and some
equivalences ("ties").

> What is "stable" in this case?

"Stable" means that by another iteration the (hopefully small) set of
winners-so-far does not become smaller.

> To me, this sounds almost like a classic definition of IRV.  

Of course it is. When all individual preferences are complete rankings, it
is just IRV. But consider the following case: Three voters, three
alternatives, preference profile:

                 C
 A       B       |
 | B     | A     A
 C       C       |
                 B

(that is, one voters has A>B and is undecided about B, one has B>C
and is undecided about A, and one has C>A>B) 
Then the suggested rule would weigh A and B with 2, C with 1, so that C
would be dropped. The restricted profile looks like this:

 A       B       
   B       A     A
                 |
                 B

Now the weights are A=3 and B=2, hence A wins.

> 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.

A quasi-order is a relation, call it <=, that is reflexive (that is, A<=A 
for all A) and transitive (that is, A<=B<=C implies A<=C), but need not be
complete (or what order-theorists call "total"). This incompleteness is
just the possibility that for some A,B, neither A<=B nor B<=A. The
"strict" part of a quasi-order is the relation <, defined as A<B iff A<=B
but not B<=A. Quasi-orders are a good model for individual preferences (or
more precisely, A<=B would mean that the individual thinks that A is at
least as preferable as B) since every quasi-order is an intersection of
complete quasi-orders (that is, rankings with ties). So, when the voters
values the alternatives on a number of independent scales, he gets a
number of rankings, and she should be allowed to express a preference for
A over B only when A is at least as good as B in *all* these rankings and
better in at least one (see the paper for a proof and more detailed
argument).

> 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.

Yes. I don't think this "incomplete IRV" is a good method. I just wanted
to show that "classical" methods can be generalized to the case of
incomplete preferences. I would certainly prefer Condorcet-type methods. 

Jobst