Re: [EM] (Possibly) new method/request for voting paradoxes. :)

[Dave Ketchum]

To look for a better sway to resolve cycles is worthy.  However, I  
still do not see the gain in what you offer, considering the expense.

Each of the members of a cycle would be winner if only one of them ran.
     When they are close to a tie it matters little which wins.
     When far away the deciding is easy.
     We have many competing methods already - choosing among them  
needs more effort than has happened,

Dave Ketchum

On Oct 12, 2009, at 8:59 AM, Michael Rouse wrote:

The additional complexity is to break cycles and come up with a  
complete preference order. In one of the examples below,

5: A>B>C
3: B>C>A
4: C>A>B

the cycle was resolved as A>B>C.

I just wanted to show that it picked the Condorcet winner in the  
absence of cycles. Like other Condorcet methods, breaking cycles is  
where paradoxes arise, like IIA, but I'm also interested in the  
other paradoxes it runs into. I'm also kind of curious how the rank  
orders compare to that of other methods, like Kemeny-Young.

Michael Rouse

PS It's early on the West Coast. I probably shouldn't write after I  
just wake up. :)

Dave Ketchum wrote:
What is the point to all this?  Looks much more complex than I  
sketch below, but I do not see value in the extra effort:

For 10 candidates, fill a 10x10 matrix - for A vs B need an entry  
counting A>B and one for B>A.

With luck about 9 comparisons will identify winner since each  
identifies a non-winner.

If A>B = B>A, keep both for the moment.  If they lose to another,  
that ends them.  If all others lose to them, we have a tie.

Could be cycles.  Comparing winner against 8 losers should identify  
innocence vs guilt.

Dave Ketchum

On Oct 11, 2009, at 12:00 PM, Michael Rouse wrote:

This method always selects the Condorcet winner if there are an  
odd number of voters with no ties or circular ambiguities. *With  
respect to a particular candidate,* the other candidates must form  
a single uniquely-preferred rank order, with a single peak in  
ranking score at the (composite) median voter -- if the median  
voter places B one place below A, the median voter cannot also  
rank C one place below A, unless both B and C are tied. The  
converse is also true -- if A is one place above B, C cannot also  
be one place above B. If you had a rank order with the Condorcet  
winner anywhere other than first position, you could always raise  
the total score by moving the Condorcet winner up the ranking,  
because the median voter would rank the Condorcet winner above the  
other candidates. I *think* this means that the final result will  
be the Condorcet order (in the absence of ties), but I haven't  
tried checking it yet.

Of course, if there are no voters at the median ranking (for  
example, if exactly half of the voters ranked A as first place and  
half ranked A as last place, with no voters in the middle -- which  
is why I mentioned "an odd number of voters" above), you will have  
a range of ranks with the same score. For example, combining the  
votes  A>B>C and B>C>A will result in a tie between those two  
rankings, even though a case can be made that B>A>C would be the  
preferred ranking, if one must be picked. So there are probably a  
whole host of paradoxes out there, in addition to the ones  
inherent in Condorcet methods. :)

For ratings differences, do you mean on a range-type ballot? That  
might be an interesting path to look at. And do you have an  
example of the before and after matrices for your positive  
difference suggestion?

Michael Rouse

PS Of course, it's entirely possible that I made a mistake in  
reasoning somewhere, so I would be interested in any counter- 
examples where the Condorcet winner (or Condorcet order) did not  
match the winner in this system.

Jobst Heitzig wrote:

Dear Michael,

very interesting, I don't think I saw anything like this before.

When trying do evaluate a new method, I always try to check very  
simple
criteria first, like neutrality and anonymity (obviously fulfilled
here), Pareto efficiency, monotonicity, etc. Concerning the  
latter two,
I was not able to verify them for your method yet. I think you  
should
focus on those before checking more complex things like Condorcet
efficiency and so on!

Also, immediately a ratings-based generalization came to mind  
(using
ratings differences instead of rank differences). Finally, when  
only
seeking a single winner, you could alternatively build a score  
for each
option X by adding all entries of the final matrix in rows  
labeled "XY"
and columns labeled with positive differences.

Yours, Jobst


Michael Rouse schrieb:

As usual with such posts, there is a good chance someone has  
come up
with the same (or very similar) method, but I thought it had  
interesting
properties, and was wondering what glaring voting paradoxes it  
had. In
addition, the number of possible orders is overwhelming if there  
are a
large number of candidates, and I'm not sure that can be  
simplified.
Finally, Thunderbird sometimes seems to have weird formatting  
issues in
email, which may screw up the following into unreadability.

With that in mind, here it is.

Step 1: For each ranked ballot, create a matrix for each  
pairwise vote,
based on the distance and direction between each candidate. For  
example,
on the ballot A>B>C, you would get:

      -2    -1    0    1    2
AB    0     0    0    1    0
BA    0     1    0    0    0
AC    0     0    0    0    1
CA    1     0    0    0    0
BC    0     0    0    1    0
CB    0     1    0    0    0

Taking the rows in order, this shows that A is one position  
higher than
B on this ballot, which conversely makes B one position lower  
than A on
the same ballot. Also, A is two positions above C (C is two  
positions
below A), and B is one position above C (or C is one position  
below B).
Such detail may be unnecessary -- simply looking at position 1  
and above
is sufficient, if you don't allow ties -- but I wanted to show the
symmetry.

Step 2. Add all matrices together. As a simple example, let's  
consider
the following 12 votes in a circular tie (to make it interesting):

5: A>B>C
3: B>C>A
4: C>A>B

Taking the first line, A>B>C =

      -2    -1    0    1    2
AB    0     0    0    1    0
BA    0     1    0    0    0
AC    0     0    0    0    1
CA    1     0    0    0    0
BC    0     0    0    1    0
CB    0     1    0    0    0

Multiplied by 5 gives you:

      -2    -1    0    1    2
AB    0     0    0    5    0
BA    0     5    0    0    0
AC    0     0    0    0    5
CA    5     0    0    0    0
BC    0     0    0    5    0
CB    0     5    0    0    0


Taking the second line, 3: B>C>A =

      -2    -1    0    1    2
AB    3     0    0    0    0
BA    0     0    0    0    3
AC    0     3    0    0    0
CA    0     0    0    3    0
BC    0     0    0    3    0
CB    0     3    0    0    0


And finally, taking the third line, 4: C>A>B

      -2    -1    0    1    2
AB    0     0    0    4    0
BA    0     4    0    0    0
AC    0     4    0    0    0
CA    0     0    0    4    0
BC    4     0    0    0    0
CB    0     0    0    0    4

Adding these together gives you

(5: A>B>C, 3: B>C>A, 4: C>A>B) =

      -2    -1    0    1    2
AB    3     0    0    9    0
BA    0     9    0    0    3
AC    0     7    0    0    5
CA    5     0    0    7    0
BC    4     0    0    8    0
CB    0     8    0    0    4

Step 3: This is where a bit of a curve is thrown in. Looking at  
each
position on the matrix, determine which is less -- the sum of the
numbers above the current position, or the sum of the numbers  
below the
current position -- and add that number to the value of the  
current
position. In essence, this is adding the value of a position to  
the
value of all other positions away from the median. Output that  
number to
a new matrix in the appropriate spot. Using the numbers above,  
you end
up with:

      -2    -1    0    1    2
AB    3     3    3    9    0
BA    0     9    3    3    3
AC    0     7    5    5    5
CA    5     5    5    7    0
BC    4     4    4    8    0
CB    0     8    4    4    4

Step 4: Looking at each possible preference order, add the  
values for
the appropriate positions on the matrix, and choose the  
preference order
with the highest score. Using the above values and excluding ties:

A>B>C = (A>B) [one position] + (B>C) [one position] + (A>>C) [two
positions] = 9+8+5 = 22
B>C>A = 8+7+3 = 18
C>A>B = 7+9+4 = 20
A>C>B = 5+4+0 = 9
C>B>A = 4+3+0 = 7
B>A>C = 3+5+0 = 8

So the ranking of possible orders is

A>B>C = 22
C>A>B = 20
B>C>A =18
A>C>B = 9
B>A>C = 8
C>B>A = 7

A>B>C is the most preferred order. C>B>A is the least preferred  
order.

****************

As another example (ignoring a few pages of work), here is a set  
of
ballots used in the Schulze Method entry in Wikipedia:

5:A>C>B>E>D
5:A>D>E>C>B
8:B>E>D>A>C
3:C>A>B>E>D
7:C>A>E>B>D
2:C>B>A>D>E
7:D>C>E>B>A
8:E>B>A>D>C

If I did the math correctly, the winning order is:
E>B>A>D>C = (27+25+30+28)+(23+26+13)+(8+16)+(8) = 204

For comparison, Schulze gives E>A>C>B>D, which this method would  
score
(22+26+28+19)+(16+17+17)+(0+15)+(0) = 160

(Note, no claim is made as to which one is better, I just wanted  
to show
the difference.)

**************

I've tried variants using distance multiplied by score (which  
seems to
encourage strategic raising and lowering of ranks) and absolute  
ranking
rather than relative ranking (which didn't seem to act as nicely  
in vote
aggregation), but neither seemed to act as nicely on brief  
inspection. I
haven't come up with a tiebreaker method yet, either -- like in  
the
simple example of adding together 1: A>B>C and 1:B>C>A (both  
orders have
the same score) -- but that can wait.

Any questions, comments, or criticisms (the latter most likely  
about my
math!) are welcome. Especially welcome would be examples of  
paradoxes,
and links to the same (or similar) method discussed in the past.

Michael Rouse


----
Election-Methods mailing list - see http://electorama.com/em for list info