Chain Climbing --> Chain Filling

Dear Forest!

Post by Forest Simmons
Unfortunately, reverse TACC is not monotonic with respect to approval.
If the winner moves up to the top approval slot without also becoming
the CW, she will turn into a loser.

That's right.

Post by Forest Simmons
Working from top to bottom of the approval list, fill in a chain by
incorporating each candidate that can be included transitively. The
candidate at the top of the resulting maximal chain is the winner.

This is a nice idea, but upon closer inspection it turns out not to be
monotonic, unfortunately. Look at this example: Assume the approval list
from top to bottom is A,B,C,D,E, and the defeats are
A>B>C>D>E>A>D>B<E>C>A. Then the chain filling begins A>B, C is skipped,
D is added to give A>D>B, and E is skipped. Hence A wins. Now reverse
the defeat C>A into A>C without changing approvals. Then the chain
filling begins A>B>C, D is skipped, and E is added to give E>A>B>C.
Hence E wins although the original winner A was raised.

Post by Forest Simmons
As mentioned above, I wanted to work top down so that I would come to
the Pareto dominators before getting to the Pareto dominated candidates.
Then it doesn't matter if the Pareto dominated candidates are eliminated
at the beginning; the rest of the chain will be the same, including the
top candidate.

That's a good point! I think that for this reason, we should proceed
trying to find a variation which works top down.

Yours, Jobst

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

Ted Stern

2005-03-12 22:18:09 UTC

Post by Jobst Heitzig
Dear Forest!

That's right.

At first, I didn't understand what Frest meant by 'transitive, but I gather
what he mans is, start a chain by adding the first candidate from the sorted
list (Call that candidate A_i), to the new chain (call that B_j). When adding
a new candidate, start at the winning end, and test to see if the candidate
defeats the first B_j. If not, follow the list down to the next weaker
candidate and test again. Repeat until you find a defeated candidate. Mark
the location, but don't insert the A into the B list.

Then start testing from the losing end of the B list. If the A candidate
defeats the B candidate, continue following links to stronger B candidates.

If you end up at the same spot each time, the A candidate isn't in a cycle,
and can be inserted. Otherwise, you're effectively eliminating it from
further consideration. This causes the loss of monotonicity noted by Jobst

Post by Jobst Heitzig
This is a nice idea, but upon closer inspection it turns out not to be
monotonic, unfortunately. Look at this example: Assume the approval list
from top to bottom is A,B,C,D,E, and the defeats are
A>B>C>D>E>A>D>B<E>C>A. Then the chain filling begins A>B, C is skipped,
D is added to give A>D>B, and E is skipped. Hence A wins. Now reverse
the defeat C>A into A>C without changing approvals. Then the chain
filling begins A>B>C, D is skipped, and E is added to give E>A>B>C.
Hence E wins although the original winner A was raised.

That's a good point! I think that for this reason, we should proceed
trying to find a variation which works top down.
Yours, Jobst

Thanks to both of your responses, I have an idea now that I think will work,
and it should have (my) desired quality of encouraging generous approval
cutoff and ranking of candidates below the cutoff.

Basically, the idea is simply Beatpath: Break each cycle at the weakest link.
But what should be the weakest link? Why not call it the defeat made by the
candidate with lowest approval? We could call this Total Approval
Beatpath (TAB), but suggest a better name if you want.

Forest's idea can proceed almost identically as before:

(1) Sort candidates by approval, from highest to lowest, into a list
{A_1, A_2,..., A_n}.

(2) Initialize a linked list (or chain, if you prefer) of candidates B with
Approval Winner A_1. The beginning of the list is the winning end, and
the end is the losing end.

(3) For each A_i, i=2:n,

B node points to losing end candidate.

While A_i defeats B-node,
follow B-list backward to next stronger candidate,
set B-node to that candidate.
End while

Insert A_i before B-node.
End For

The winner is the candidate at the left most end of the list. The list gives
you the social ordering of the candidates.

This is just like Forest's proposal but doesn't eliminate candidates from the
B list.

Essentially, each candidate has to run the gauntlet and defeat candidates with
higher approval before it is inserted in the list. It may have a cycle with
higher candidates, but there is always a beatpath down to it with higher
approval at every step.

This is similar to Jobst's grand compromise and James Green-Armytage's
Approval-weighted Pairwise, but it isn't necessary to carry along a second
pairwise array.

It is also easier to implement than standard or cardinal-weighted Beatpath --
The defeat chain automatically gives you the total approval beatpath strengths.

Why might this be preferable to the other schemes mentioned?

- There is a strong disincentive to bullet vote or truncate (an exercise for
the reader, but consider the 35:A>B>>C, 25:B, 40:C, in which B voters ahve
truncated their true preference 25:B>A>>C).

- There is a strong incentive to be generous with approval cutoff -- you want
your nearest neighbors, if you will, to be considered earliest in the list.

- Much less strategic incentive to equal rank due to the approval cutoff.
Voters can express true preferences above the approval cutoff, AND below,
without fear of hurting their candidate.

This is too simple to not have been mentioned before ... have I simply missed
something years ago in the archives? Is there some major criterion that isn't
satisfied?

Testing with Jobst's example, I see

A
A > B
A > B > C
A > B > C > D
A > B > C > D > E ==> A wins.

both times. Any other examples?

Just to stake a claim in case it hasn't been proposed before, Total approval
ranking in the first list could be replaced by total cardinal rating. But I
don't see any obvious advantage.

Ted

--
Change reply address to tedstern at u dot washington dot edu
for direct replies.

Frango ut patefaciam -- I break so that I may reveal
----
Election-methods mailing list - see http://electorama.com/em for list info

Forest Simmons

2005-03-13 00:10:46 UTC

Dear Ted,

Your TAB method is what I used to call "Approval Seeded Bubble Sort."

Then after a year of thinking that it was my invention I came across an
article about the Kemeny Order in which the authors called our bubble
sort process "Local Kemenization" and suggested using it as a way of
refining various other orders including the Border order.

One thing that bothered me was lack of reverse symmetry, so I eventually
came to this version:

Start with the approval order (greatest to least approval <--> top to
bottom).

While any candidate is beaten by the candidate immediately above her ...

swap the two adjacent candidates with the greatest "discrepancy"

EndWhile

The winner is the candidate that ends up at the top of the list.

It's like lining up recruits for drill, and sorting them into order of
height by successive swaps, most urgent first.

"Discrepancy," like defeat strength can be measured in several ways.

If you use margins, or some other symmetric measure, then the final order
reverses when all of the ballots are reversed.

However this reverse symmetry may not be the best goal when trying to
discourage manipulation.

Forest

Post by Jobst Heitzig
Dear Forest!

That's right.

At first, I didn't understand what Frest meant by 'transitive, but I gather
what he mans is, start a chain by adding the first candidate from the sorted
list (Call that candidate A_i), to the new chain (call that B_j). When adding
a new candidate, start at the winning end, and test to see if the candidate
defeats the first B_j. If not, follow the list down to the next weaker
candidate and test again. Repeat until you find a defeated candidate. Mark
the location, but don't insert the A into the B list.
Then start testing from the losing end of the B list. If the A candidate
defeats the B candidate, continue following links to stronger B candidates.
If you end up at the same spot each time, the A candidate isn't in a cycle,
and can be inserted. Otherwise, you're effectively eliminating it from
further consideration. This causes the loss of monotonicity noted by Jobst

That's a good point! I think that for this reason, we should proceed
trying to find a variation which works top down.
Yours, Jobst

Thanks to both of your responses, I have an idea now that I think will work,
and it should have (my) desired quality of encouraging generous approval
cutoff and ranking of candidates below the cutoff.
Basically, the idea is simply Beatpath: Break each cycle at the weakest link.
But what should be the weakest link? Why not call it the defeat made by the
candidate with lowest approval? We could call this Total Approval
Beatpath (TAB), but suggest a better name if you want.
(1) Sort candidates by approval, from highest to lowest, into a list
{A_1, A_2,..., A_n}.
(2) Initialize a linked list (or chain, if you prefer) of candidates B with
Approval Winner A_1. The beginning of the list is the winning end, and
the end is the losing end.
(3) For each A_i, i=2:n,
B node points to losing end candidate.
While A_i defeats B-node,
follow B-list backward to next stronger candidate,
set B-node to that candidate.
End while
Insert A_i before B-node.
End For
The winner is the candidate at the left most end of the list. The list gives
you the social ordering of the candidates.
This is just like Forest's proposal but doesn't eliminate candidates from the
B list.
Essentially, each candidate has to run the gauntlet and defeat candidates with
higher approval before it is inserted in the list. It may have a cycle with
higher candidates, but there is always a beatpath down to it with higher
approval at every step.
This is similar to Jobst's grand compromise and James Green-Armytage's
Approval-weighted Pairwise, but it isn't necessary to carry along a second
pairwise array.
It is also easier to implement than standard or cardinal-weighted Beatpath --
The defeat chain automatically gives you the total approval beatpath strengths.
Why might this be preferable to the other schemes mentioned?
- There is a strong disincentive to bullet vote or truncate (an exercise for
the reader, but consider the 35:A>B>>C, 25:B, 40:C, in which B voters ahve
truncated their true preference 25:B>A>>C).
- There is a strong incentive to be generous with approval cutoff -- you want
your nearest neighbors, if you will, to be considered earliest in the list.
- Much less strategic incentive to equal rank due to the approval cutoff.
Voters can express true preferences above the approval cutoff, AND below,
without fear of hurting their candidate.
This is too simple to not have been mentioned before ... have I simply missed
something years ago in the archives? Is there some major criterion that isn't
satisfied?
Testing with Jobst's example, I see
A
A > B
A > B > C
A > B > C > D
A > B > C > D > E ==> A wins.
both times. Any other examples?
Just to stake a claim in case it hasn't been proposed before, Total approval
ranking in the first list could be replaced by total cardinal rating. But I
don't see any obvious advantage.
Ted

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

Ted Stern

2005-03-14 18:23:15 UTC

Post by Forest Simmons
Dear Ted,
Your TAB method is what I used to call "Approval Seeded Bubble Sort."

Hi Forest, thanks for the reference check. It figures that if anybody
might have considered it earlier, it would have been you or Jobst ;-).

But in my earlier enthusiasm, I mis-spoke in two respects.

First:

If you sort the candidates first by total approval, then do a careful
bubble sort (order of operations *is* important), then this method
turns out to be equivalent to Ranked Pairs (total approval), *not*
Beatpath (total approval).

So you could call it Total Approval Ranked Pairs (TARP), or RP(ta), or
Approval Seeded Bubble Sort, but yes, they're all the same thing.

Just to be clear what I'm talking about,

Sort by approval so that the front of the list has highest approval.

Starting at the second point in the list, move that candidate forward
(higher) if it defeats higher candidates. Then start at the 3rd point in
the list and bubble that candidate upward, etc.

In Matlab/octave notation, say you have the pairwise matrix stored in
the array A, with A(i,i) containing the total approval of candidate
X(i).

These octave (and possibly Matlab) operations will give you the winner:

I = [1:N] ; % Initialize index array with 1 to N

K = for i=1:N; K(i) = A(i,i); endfor % Approval sort keys

[T,J] = sort([K' I'], 1) % sort by ascending approval,
% also return index array

I = flipud(J)(:,1) % Store descending approval
% indices into index vector

% Bubble sort, with a bias toward higher approval:
for j=2:N
i = j
while ( A(I(i),I(i-1)) > A(I(i-1),I(i)) )
% Swap the indices to bubble the i-th candidate upward
k = I(i-1)
I(i-1) = I(i)
I(i) = k
i = i - 1
if ( i == 1 )
break
endif
endwhile
endfor

I think this is conceptually easier to grasp than to sort all defeats
by the minimum approval of either contestant (total approval defeat
strength), but the end result is the same. Any contests that are not
considered in the while loop are the same defeats dropped by RP(ta).

Unlike traditional ranked pairs, which is already fairly easy to
explain, you don't have to rank the defeats, you don't have to discuss
"consistency" (cycles), and you don't have to explicitly state that
you're dropping defeats. All of those arise automatically from the
two sort stages. IMO, this would definitely have a higher
voter-appeal factor.

TARP also has an intuitive "sports-like" analogy, particularly
appropriate during this first week of March Madness (US college
basketball playoffs):

"Rank candidate 'seeds' in descending order of approval. For a
candidate to move up in rank, it has to defeat all higher seeded
teams in succession, and only after each of those has itself moved
up in rank as much as possible."

Jobst, as you said, this may indeed be equivalent to Kevin's
approval-completed Condorcet, but I'd like to point out that there's
no mention of elimination in this implementation, and the result is a
social ordering.

Not eliminating candidates too early, to my mind, is one of
Condorcet's strongest arguments against plurality or IRV. So whenever
possible, you should avoid any formulation that mentions elimination!

I'll cover the second problem I found below.

Post by Forest Simmons
Then after a year of thinking that it was my invention I came across an
article about the Kemeny Order in which the authors called our bubble
sort process "Local Kemenization" and suggested using it as a way of
refining various other orders including the Border order.
One thing that bothered me was lack of reverse symmetry, so I eventually

Is RP(wv) symmetric?

I think total approval ranked pairs is symmetric with respect to the
approval cutoff. In other words, if "X1>>X2" votes are changed to
"X2>>X1" votes.

Post by Forest Simmons
Start with the approval order (greatest to least approval <--> top to
bottom).
While any candidate is beaten by the candidate immediately above her ...
swap the two adjacent candidates with the greatest "discrepancy"
EndWhile
The winner is the candidate that ends up at the top of the list.
It's like lining up recruits for drill, and sorting them into order of
height by successive swaps, most urgent first.
"Discrepancy," like defeat strength can be measured in several ways.
If you use margins, or some other symmetric measure, then the final order
reverses when all of the ballots are reversed.
However this reverse symmetry may not be the best goal when trying to
discourage manipulation.

I'm not sure that I consider lack of symmetry important.

Post by Ted Stern
- There is a strong disincentive to bullet vote or truncate (an
exercise for the reader, but consider the 35:A>B>>C, 25:B, 40:C, in
which B voters have truncated their true preference 25:B>A>>C).

In TARP (aka ASBS), there is some disincentive to truncate
preferences. But it is not as strong as I initially thought. For
instance, in the example immediately above, B could still win with
truncation. But the A block can use the ATLO-like option of placing
its cutoff above B to force a C win if B tries to truncate. The B
block would do better to appeal to the C voters to gain a rank below
their approval cutoff.

So strategy-wise, I think TARP / ASBS / RP(ta) is as strong as ATLO or
Approval-weighted pairwise, but easier to implement and explain to
voters.

Jobst, I would even suggest that in many-candidate elections, it is as
easy or easier than River.

Post by Ted Stern
- There is a strong incentive to be generous with approval cutoff -- you
want your nearest neighbors, if you will, to be considered earliest in the
list.

Well, not as strong an incentive to be generous with approval cutoff as I
thought initially. But maybe it's enough.

Post by Ted Stern
- Much less strategic incentive to equal rank due to the approval cutoff.
Voters can express true preferences above the approval cutoff, AND below,
without fear of hurting their candidate.

I think this still stands.

As others (Kevin? Gervase? Alex?) have mentioned during the last
couple of days, it could be easier to simply have two sets of
rankings, some approved and some disapproved. I think any even number
of options from 6 to 10 would be adequate, with the approval cutoff in
the middle. Perhaps 6 would be a good starting point for a public
proposal.

Ted

--
Ted Stern
(change reply address to tedstern at u dot washington dot edu)
----
Election-methods mailing list - see http://electorama.com/em for list info

Forest Simmons

2005-03-14 21:14:57 UTC

Here's the original recursive procedure that I gave for Approval Seeded
Bubble Sort:

1. List the candidates in order of approval, from top to bottom.

2. Percolate the bottom candidate as far as possible up the recursively
sorted list of the other candidates.

How's that for concise?

Jobst is right: the winner is the lowest approval score candidate that
beats all of the candidates with greater approval, which turns out to be
the same as the first CW that eventually appears as low approval
candidates are eliminated successively.

Furthermore, the set P of all candidates none of which is beaten by any
candidate with greater approval turns out to be the set of candidates that
are as high or higher than the approval winner in the sorted order.

Post by Ted Stern
As others (Kevin? Gervase? Alex?) have mentioned during the last
couple of days, it could be easier to simply have two sets of
rankings, some approved and some disapproved. I think any even number
of options from 6 to 10 would be adequate, with the approval cutoff in
the middle. Perhaps 6 would be a good starting point for a public
proposal.

Using powers of two for the number of ranks makes the most efficient use
of bits. Eight would be just right, requiring just three bits to rank or
rate zero through seven:

Before marking:

John Doe (4) (2) (1)

After marking:

John Doe (*) (2) (*)

[John Doe's rating is five, the sum of the shaded bits.]

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

Ted Stern

2005-03-14 22:37:17 UTC

Concise? Yes. Could the layman grasp it? No. But I agree, it is the same
as what I've been suggesting.

Post by Forest Simmons
Jobst is right: the winner is the lowest approval score candidate that
beats all of the candidates with greater approval, which turns out to be
the same as the first CW that eventually appears as low approval
candidates are eliminated successively.

Okay, I see that now. Your explanation is clearer ;-).

Post by Forest Simmons
Furthermore, the set P of all candidates none of which is beaten by any
candidate with greater approval turns out to be the set of candidates that
are as high or higher than the approval winner in the sorted order.

Seems nice, but why is this a nice property to have? Is there something
special about it?

I think it is nice that the method is so concise. So much is handled
implicitly. It's simple enough you could use it in a middle school student
body election.

Using powers of two for the number of ranks makes the most efficient use
of bits. Eight would be just right, requiring just three bits to rank or
John Doe (4) (2) (1)
John Doe (*) (2) (*)
[John Doe's rating is five, the sum of the shaded bits.]

Sometimes efficiency is too efficient. Is 7 highest or lowest? If 7 is
highest, you need to fill in all 3 blanks to select your first choice (7), 2
blanks for 2nd choice (6), 2 blanks for 3rd choice (5), and 1 blank for your
minimum approval level 4th place (4). And so on for the ranks below the
approval cutoff.

But if 7 is lowest, it means you have to fill in all 3 blanks for every lowest
level candidate.

Sorry for the gross generalization, but grandma and grandpa aren't going to
like that. If you're going to save them having to go to an extra election,
they shouldn't have to fill in more than the 2 blanks they would have used for
two plurality elections. They might be able to deal with 2 more fill-ins, but
not 2*N more!

If what you are after is efficient data storage, go ahead and use 8 ranks.
But the voter enters only 6 ranks, 1 through 6. As Dave Ketchum has
suggested, reserve 7 for default spoiled (if all ranks 1 through 6 have been
used, otherwise one below the lowest ranked), 8 for unfilled.

On another note, it is interesting to consider Rob LeGrand's example election:

98:A>C>E>D>B
64:B>A>E>C>D
12:B>A>E>D>C
98:B>E>A>C>D
13:B>E>A>D>C
125:B>E>D>A>C
124:C>A>E>D>B
76:C>E>A>D>B
21:D>A>B>E>C
30:D>B>A>E>C
98:D>B>E>C>A
139:D>C>A>B>E
23:D>C>B>A>E

Considering the top two as approved, the pairwise matrix looks like this:

319 458 461 485 511
463 440 461 312 623
460 460 460 460 460
436 609 461 311 311
410 298 461 610 312

Ranking the defeats using minimum approval, secondarily using winning votes,
the defeats are ordered as

Initial descending approval:
C,B,A,E,D

Approval-sorted bubble sort ranking:

B > A > E > D > C

Total Approval Ranked Pairs:

B>C 440 (wv 460)
A>C 319 (wv 460)
B>A 319 (wv 463) => B>A>C
B>E 312 (wv 623)
A>E 312 (wv 511) => B>A>E
E>C 312 (wv 461) => B>A>E>C
E>D 311 (wv 610) => B>A>E>D
D>B 311 (wv 609) conflict, excluded
A>D 311 (wv 485)
D>C 311 (wv 460) => B>A>E>D>C

Total Approval Beatpath: B's total approval beatpath to A is 440 (B's
approval, since B>A is a direct victory). A's strongest total approval
beatpath to B is 311.

So B wins both Beatpath and Ranked Pairs. With winning votes only, Beatpath
chooses A and RP chooses B.

Ted

--
Ted Stern
Change reply address to tedstern at u dot washington dot edu
----
Election-methods mailing list - see http://electorama.com/em for list info

Forest Simmons

2005-03-14 23:02:25 UTC

Seems nice, but why is this a nice property to have? Is there something
special about it?

I recently suggested that the winner should be picked from this set P by
random ballot.

This set P always includes the AW and the CW (when there is one), and in
general some other relatively high approval candidates that are good at
winning pairwise contests.

This set P is much more restrictive than the set Q of all candidates with
beat paths to the AW, which I once proposed.

But I think P may be adequate to control most insincere voting, though it
doesn't do as well as Q on the notorious

49 C
24 B>>A>C
27 A>B>>C

example.

For this example, using Jobst's Random Approval Ballot Order as the seed
for bubble sort, and then picking (by random ballot) from the candidates
that end up as high or higher than the AW, might do the job of
discouraging truncation.

In any case this set P is independent from pareto dominated alternatives.

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

Jobst Heitzig

2005-03-15 06:02:10 UTC

Dear Forest, Russ, and Ted!

I suggest that we call the method we discussed under various names in
the last days ARC (Approval Runoff Condorcet) and continue to study its
properties, especially its anti-strategy properties.

I agree with Russ that it is perhaps a very nice first public proposal,
especially because it may be a nice compromise between IRV- and
Condorcet-supporters: Both methods are Runoffs which delete the single
candidate with the least points until there is among the rest a
candidate with a special property!

Yours, Jobst

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

Ted Stern

2005-03-15 16:34:04 UTC

Post by Jobst Heitzig
Dear Forest, Russ, and Ted!
I suggest that we call the method we discussed under various names
in the last days ARC (Approval Runoff Condorcet) and continue to
study its properties, especially its anti-strategy properties.
I agree with Russ that it is perhaps a very nice first public
proposal, especially because it may be a nice compromise between
IRV- and Condorcet-supporters: Both methods are Runoffs which delete
the single candidate with the least points until there is among the
rest a candidate with a special property!
Yours, Jobst

I do agree that Approval Runoff Condorcet (ARC) finds the same winner
as Approval-seeded Bubble Sort (ABS).

But I happen to think eliminating candidates through Runoff is one of
IRV's weakest points. Its only appeal is familiarity. It seems to me
that the key reason for eliminating primaries is to keep candidates in
as long as possible, to enable voters to coalesce around the one whose
views are closest to the majority.

However, if you think that it can be a useful argument, then go ahead.
I just worry that you would be letting the IRV advocates frame the
debate in a way they think they can win.

I admire of the compact description of ABS. I think it is the fastest
possible way to reveal the social ordering of this method. Another
point I would like to make is that although successively eliminating
lowest approved candidates may be easier to describe -- easy to
describe in the same way IRV is easy to describe -- every time you
eliminate a candidate, you have to look for undefeated candidates
again. I think it is just as much work as the Bubble Sort.

Back to elimination again: I was thinking about how elimination of
candidates tends to narrow voter choices, and I thought of this
analogy.

Say Democrats vote along a North-South axis, and Republicans vote
along an East-West axis. But most of the voters are sitting somewere
in the South-West.

In the primary, the core partisans of each camp will choose a
candidate somewhere along their axis. Democrats will probably not
choose the South-leaning candidate who has drifted slightly to the
west, and Republicans will probably not choose the West-leaning
candidate who has drifted slightly South.

The voters end up with a choice between a too-far-north Democrat
with little Western tendencies and a too-far-East Republican with
little Southern tendencies, neither of whom is particularly close to
what they feel is truly important.

When the voters can specify exactly how close they feel to each
candidate without having to channel their choices, the winner will
more likely be the WSW or the SWS candidate. Or even the true SW
candidate who isn't a member of either party.

Ted

--
Ted Stern
Change reply address to tedstern at u dot washington dot edu
----
Election-methods mailing list - see http://electorama.com/em for list info

Ted Stern

2005-03-15 17:16:58 UTC

One more thing I'd like to clarify.

The ballot format part of Russ's ARC aka RAV proposal disallows equal rank and
ranking below the approval cutoff.

I do not agree with that part of the proposal. I think that such restrictions
are unnecessary and are just another example of caving in and letting IRV
advocates frame the alternative voting method debate.

Another key argument about combining Instant Round-Robin (aka Condorcet) with
Approval should be checks and balances. Condorcet alone, Approval alone, or
IRV alone can each fail in some situations. But Condorcet augmented by
Approval is actually simpler and more resistant to manipulation than Condorcet
alone.

Ted

--
Ted Stern
change reply address to tedstern at u dot washington dot edu
----
Election-methods mailing list - see http://electorama.com/em for list info

Russ Paielli

2005-03-16 05:49:20 UTC

I'm just trying strike a balance between simplicity and effectiveness. I
am starting to realize that equal rankings may be worthwhile. As for
allowing ranking past the Approval cutoff point, I am still not sold on
that, but I am open minded. Think of how much simpler the voter
interface will be if it isn't allowed. If we're going to recommend
allowing it, we had better be sure it is worth the added "cost." By
"cost," I mean not only the added complexity itself, but also the
possibility that such added complexity will push the method past the
threshold of public acceptability. Note that the simple idea of ranking
candidates will stress the limits of public acceptability all by itself.

Post by Ted Stern
Another key argument about combining Instant Round-Robin (aka Condorcet) with
Approval should be checks and balances. Condorcet alone, Approval alone, or
IRV alone can each fail in some situations. But Condorcet augmented by
Approval is actually simpler and more resistant to manipulation than Condorcet
alone.

Absolutely. More on that later.

By the way, I'm not too crazy about the name "Approval Runoff Condorcet"
(ARC). I think "Condorcet with Approval Runoff" (CAR) would be
preferable, but I'm not too keen on that name either. Let's think about
this some more.

--Russ

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

Ted Stern

2005-03-16 17:43:04 UTC

Post by Russ Paielli
I'm just trying strike a balance between simplicity and
effectiveness. I am starting to realize that equal rankings may be
worthwhile. As for allowing ranking past the Approval cutoff point,
I am still not sold on that, but I am open minded. Think of how much
simpler the voter interface will be if it isn't allowed. If we're
going to recommend allowing it, we had better be sure it is worth
the added "cost." By "cost," I mean not only the added complexity
itself, but also the possibility that such added complexity will
push the method past the threshold of public acceptability. Note
that the simple idea of ranking candidates will stress the limits of
public acceptability all by itself.

I heartily agree that it could get complex.

Chris Benham sent a message earlier, directing our attention to this
2002 post by Adam Tarr:

http://lists.electorama.com/pipermail/election-methods-electorama.com/2002-March/007699.html

I happen to like graded ballots. In thinking about it, I came up with
two ballot formats:

,----[ seeded-bubblesort-ballot ]
| Idea one: Graded ballots. A/B/C get an approval point for purposes of
| the initial ranking, D/E/F get none. Unranked candidates are below F.
|
| Pass Fail
| A B C D E F
|
| X1 ( ) ( ) ( ) ( ) ( ) ( )
|
| X2 ( ) ( ) ( ) ( ) ( ) ( )
|
| X3 ( ) ( ) ( ) ( ) ( ) ( )
|
| X3 ( ) ( ) ( ) ( ) ( ) ( )
|
| Most people would be able to "get" this. After all, in school an F
| usually means you were actually there to take the test. No grade at
| all means you didn't even write your name down.
|
| Passing votes get a point, used for the initial ranking before the
| bubblesort. Failing grades don't get any point, but even a failed
| candidate can bubble up if it defeats all the other candidates
| pairwise.
|
| Idea two: 9 ranks, adjustable first-sort point levels.
|
| Default 100 Default 50 Default 0
|
| A B C D E F G H I
|
| X1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
|
| X2 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
|
| X3 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
|
| X3 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
|
|
| If you want, you can enter a different point level for any of the 3
| rank sets. E.g., you could set the ABC group to 70 points, the DEF
| group to 40 points, and the GHI group to 10 points.
|
| You'd sum up the points for each candidate into its corresponding
| pairwise matrix diagonal element. Those point totals would be used
| for the first round of sorting.
|
| Ideally, I'd like to be able to adjust the point level for each
| candidate separately, but this seems like the most compact way to do
| it.
`----

Post by Russ Paielli

Post by Ted Stern
Another key argument about combining Instant Round-Robin (aka
Condorcet) with Approval should be checks and balances. Condorcet
alone, Approval alone, or IRV alone can each fail in some
situations. But Condorcet augmented by Approval is actually
simpler and more resistant to manipulation than Condorcet alone.

Absolutely. More on that later.
By the way, I'm not too crazy about the name "Approval Runoff
Condorcet" (ARC). I think "Condorcet with Approval Runoff" (CAR)
would be preferable, but I'm not too keen on that name either. Let's
think about this some more.
--Russ

Russ, do you agree with Forest, Jobst and myself that your proposal
(if ranking below the cutoff is allowed) is equivalent to sorting
twice, first in descending order of approval (or cardinal ratings),
then by bubble sort using pairwise comparisons?

Even though Paul Kislanko would disagree with the sports comparison, I
think calling this method Tournament Voting is very descriptive of the
process, and would be convey some intuitive understanding to voters of
how it works.

Specific variations might be denoted TV(Approval), TV(CR), to specify
how you're doing the initial sort.

And yes, "Tournament" is an overloaded term. But so is "Instant
Runoff" ;-).

Just to be clear -- in taxonomy terms, IRR is the family, TV is the
genus, Approval or Cardinal Ratings is the species.

Ted

--
Send real replies to
ted stern at u dot washington dot edu

Frango ut patefaciam -- I break so that I may reveal
----
Election-methods mailing list - see http://electorama.com/em for list info

Eric Gorr

2005-03-16 18:32:45 UTC

Post by Russ Paielli
Note
that the simple idea of ranking candidates will stress the limits of
public acceptability all by itself.

I am not certain this is true.

I have watched and continue to track various efforts to get IRV
implemented in various locations around the USA and I don't believe a
convincing case could be made that this claim is accurate.

--
== Eric Gorr =============================== http://www.ericgorr.net ===
"I believe each individual is naturally entitled to do as he pleases
with himself and the fruits of his labor, so far as it in no way
interferes with any other man's rights." - Abraham Lincoln
== Insults, like violence, are the last refuge of the incompetent... ===
----
Election-methods mailing list - see http://electorama.com/em for list info

Russ Paielli

2005-03-15 19:05:22 UTC

The problem with IRV is not that it eliminates candidates but rather
*how* it eliminates them. IRV elimination is based on the first-choice
counts only. That encourages voters to insincerely promote their "lesser
of two evils" candidate into first position. In RAV (Ranked Approval
Voting, or whatever you call it), on the other hand, elimination is
based on Approval scores, and we all know about the virtues of Approval.

As for a name for the method, I think it might be wise to keep the word
"runoff" out of it just to avoid such associations. The RAV procedure is
not really a runoff in the same sense as IRV.

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

Forest Simmons

2005-03-17 02:20:10 UTC

Before I read your post I proposed a Madison Avenue style name of
"Majority Fair Chance."

It's not very scientific. Perhaps, "Fair Chance Democratic Choice" would
be better, though still not taxonomically descriptive.

I don't think it has quite enough randomness in it for the tough examples.

Here's how we might change it:

Use a random approval ballot order in place of the approval order.

[Thanks to you for that idea in your Chain Climbing post.]

Then when the pairwise defeat agrees with the random approval ballot
order, instead of calling it a "strong defeat" call it a "confirmed
defeat."

From there on everything else is the same; the set of candidates without

confirmed defeats form a chain P whose pairwise order is the exact
opposite of the random approval ballot order.

We choose from P either by (ordinary) random ballot or by (another) set of
random approval ballots, how ever many it takes to determine a winner.

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

Jobst Heitzig

2005-03-19 10:13:01 UTC

Hi Forest!

Post by Forest Simmons
Before I read your post I proposed a Madison Avenue style name of
"Majority Fair Chance."

That's OK but only when we use majority-strength defeats!

Post by Forest Simmons
It's not very scientific.

No problem, as long as we know what it is and can justify the name.

Post by Forest Simmons
Perhaps, "Fair Chance Democratic Choice"
would be better, though still not taxonomically descriptive.

That's better I think, since it indicates that the method is more
democratic than "majority rule".

Post by Forest Simmons
I don't think it has quite enough randomness in it for the tough examples.

Hm, which examples do you have in mind? Of course, since there might be
losers not defeated by any possible winner, it cannot resolve the fake
CW problem completely. But I'm not sure how probable that is, I would
guess that only in pathological examples with many candidates it will
happen that such a loser exists.

However, one could make a minor modification which would only seldom be
used: Determine P, and as long as all of P is beaten by a candidate
outside P, add the most approved such candidate to P. I will try to
prove its monotonicity...

Post by Forest Simmons
Use a random approval ballot order in place of the approval order.

Also a good idea, but it requires to let go of the nice interpretation
of strong defeat...

Post by Forest Simmons
We choose from P either by (ordinary) random ballot or by (another) set
of random approval ballots, how ever many it takes to determine a winner.

I think that it is better to use ordinary random ballot since then all
three major kinds of preference information (approval, pairwise
preferences, direct support) are used to determine the winner, and that
is a very good marketing argument!

By the way, here's a simple "procedural" version of the method, to be
used in meetings:
First, options may be suggested, and for every option it is asked who
approves of it. They are written onto blackboard in order of approval.
Then some member of the group is picked at random. S/he proposes some of
the options, and then this option is subjected to pairwise contests with
the more approved ones, beginning with the most approved one. If none of
them wins with majority strength, the proposed option wins. Otherwise,
the next person is chosen at random and proposes an option, until the
proposed option survives all pairwise contests with more approved ones.
This will hopefully lead to people proposing very good compromises,
since otherwise they will experience to have their proposal defeated by
a more approved option, which would make their proposal look somewhat
ridiculous.

I'd like to ask you to test this procedure with your favourite group!

Yours, Jobst

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

Forest Simmons

2005-03-22 00:56:06 UTC

On Sat, 19 Mar 2005, Jobst Heitzig wrote:

...

Post by Jobst Heitzig
However, one could make a minor modification which would only seldom be
used: Determine P, and as long as all of P is beaten by a candidate
outside P, add the most approved such candidate to P. I will try to
prove its monotonicity...

That would be nice if it works out.

Post by Jobst Heitzig

Post by Forest Simmons
Use a random approval ballot order in place of the approval order.

Also a good idea, but it requires to let go of the nice interpretation
of strong defeat...

Right. The randomly confirmed defeat is not as good as the strong defeat,
so if we go this way, we should finish up the way Ted likes ... pick the
pairwise winner among those whose defeats were not confirmed by the random
ballot order.

This method would be Smith efficient, so if we want a Smith efficient
lottery, this would be a possibility.

Post by Jobst Heitzig

Post by Forest Simmons
We choose from P either by (ordinary) random ballot or by (another) set
of random approval ballots, how ever many it takes to determine a winner.

Great point!

Post by Jobst Heitzig
By the way, here's a simple "procedural" version of the method, to be
First, options may be suggested, and for every option it is asked who
approves of it. They are written onto blackboard in order of approval.
Then some member of the group is picked at random. S/he proposes some of
the options, and then this option is subjected to pairwise contests with
the more approved ones, beginning with the most approved one. If none of
them wins with majority strength, the proposed option wins. Otherwise,
the next person is chosen at random and proposes an option, until the
proposed option survives all pairwise contests with more approved ones.
This will hopefully lead to people proposing very good compromises,
since otherwise they will experience to have their proposal defeated by
a more approved option, which would make their proposal look somewhat
ridiculous.
I'd like to ask you to test this procedure with your favourite group!

This procedure is very appealing to me.

It would be a good way to sell the method in a group setting.

One could use it to pick a restaurant for the group to adjourn to after
the meeting if they didn't want to test it on a more important decision.

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

Monkey Puzzle

2005-03-22 17:23:00 UTC

Jobst, could you please clarify below?

This procedure is very appealing to me.
It would be a good way to sell the method in a group setting.
One could use it to pick a restaurant for the group to adjourn to after
the meeting if they didn't want to test it on a more important decision.
Forest

Jobst / Forest :

Could you translate this into a pairwise sorted algorithm for me?

It appears that by starting with the most approved candidate to test
against, you're bubble-sorting downward instead of upward.

Or am I missing something?

Ted

--
araucaria dot araucana at gmail dot com
----
Election-methods mailing list - see http://electorama.com/em for list info

Forest Simmons

2005-03-22 19:11:30 UTC

Post by Monkey Puzzle
Jobst, could you please clarify below?

The phrase "beginning with the most approved one" is the source of your
confusion.

Actually the order doesn't matter here, except there should be some order.

The point is to find out if the candidate is beten by anybody with more
approval.

If not, then this candidate is a member of P, and has been chosen by
random voter.

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

Forest Simmons

2005-03-17 19:11:43 UTC

Jobst, the more I think about it, the more I like your idea (influenced by
Kevin) of requiring full majorities for strong defeat.

I don't think that we lose any of the basic properties, and it solves
Kevin's 49C, 24B, 27A>B problem without the additional randomness that I
was beginning to accept as inevitable.

The method can be described briefly as follows:

List the candidates from top to bottom in order of decreasing total
approval.

Eliminate every candidate that is beaten pairwise on more than half of the
ballots by some candidate higher up on the approval list.

If more than one candidate remains, then resolve the fundamental ambiguity
by democratically giving each candidate a fair chance: the remaining
candidate that is ranked highest on a randomly drawn ballot wins.

In Kevin's example the sincere ballots are

49 C>>A=B
24 B>>A>C
27 A>B>>C

The approval order (from top to bottom) is B>C>A .

Candidate C is eliminated because B beats C majority pairwise, as well as
in approval.

Random ballot between A and B gives respective probabilities of 27/51 and
24/51.

If the B supporters truncate A, then the approval order is unchanged, and
C is still the only candidate beaten from above by a full majority, since
the C>A defeat is only on 49 percent of the ballots.

The probabilities remain the same, so the truncation gives no advantage to
the B supporters.

Note that if the A supporters didn't like B that much the sincere ballots
would be

49 C
24 B>>A>C
27 A>>B>C

In this case the approval order would be C>A>B, and no candidate would be
eliminated, since the two full majority defeats go uphill (against
approval).

If the B supporters could anticipate this, they might lower their approval
cutoffs:

49 C
24 B>A>>C
27 A>>B>C

Then A would be both the approval winner and the ballot CW.

The approvals order would be A>C>B.

Only C would be eliminated by strong defeat, and the probabilities would
be the same as in the first example.

It is to the advantage of the B faction to (somewhat insincerely) approve
candidate A.

So the method doesn't completely do away with strategy.

Note that A and B are a majority clone set, and that as long as they give
a reasonable amount of support to each other they both have a fair chance
of winning.

But their combined victory over C is by such a slim margin, that if they
do not cooperate, then C also gets a share of the probability.

In other words, a loose clone set doesn't have as much force as a tight
clone set.

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

Russ Paielli

2005-03-15 06:40:44 UTC

Post by Forest Simmons
Here's the original recursive procedure that I gave for Approval Seeded
1. List the candidates in order of approval, from top to bottom.
2. Percolate the bottom candidate as far as possible up the recursively
sorted list of the other candidates.
How's that for concise?
Jobst is right: the winner is the lowest approval score candidate that
beats all of the candidates with greater approval, which turns out to be
the same as the first CW that eventually appears as low approval
candidates are eliminated successively.

I agree with Forest here, but I think the way he phrases it may be
slightly misleading because it seems to imply that a lower Approval
score is advantageous.

Let me explain how I visualize this procedure.

Let's start first with a way to visualize a standard Condorcet pairwise
matrix. Imagine "blacking out" the non-diagonal elements corresponding
to winning scores and "whiting out" the elements corresponding to losing
scores. Let's say the diagonal elements are blacked out too. A CW then
must have a completely blacked out row.

In no CW exists, put the Approval scores on the diagonal and reorder the
matrix so that the diagonal is strictly non-increasing starting from the
upper left and going down.

The least-approved candidate can only win by being the CW, meaning that
his entire row must be blacked out. But I just said that no CW exists,
so that didn't happen. So eliminate the last row and column. Now the
next-to-last-approved candidate can only win by having a completely
blacked out row, which would be blacked out all the way to the diagonal
of the original matrix. If that isn't the case, eliminate the last row
and column again.

The winner is the first candidate, starting at the bottom and going up,
to have his row blacked out all the way to the diagonal.

Note, however, that as you proceed up toward the Approval winner, the
number of blacked-out elements needed to win decreases. The AW himself
needs none. In other words, the Approval winner needs no pairwise wins
to win the election. That's the mirror image of the fact that the
least-approved candidate can be the CW, as Forest pointed out the other day.

--Russ

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

Ted Stern

2005-03-15 16:50:47 UTC

Note, however, that as you proceed up toward the Approval winner, the number
of blacked-out elements needed to win decreases. The AW himself needs
none. In other words, the Approval winner needs no pairwise wins to win the
election. That's the mirror image of the fact that the least-approved
candidate can be the CW, as Forest pointed out the other day.

Hi Russ,

I must respectfully disagree.

Your 'black-only' row method could eliminate the AW at an earlier stage.

Ted

--
Send real replies to
ted stern at u dot washington dot edu

Frango ut patefaciam -- I break so that I may reveal
----
Election-methods mailing list - see http://electorama.com/em for list info

Russ Paielli

2005-03-13 00:43:21 UTC

Post by Ted Stern
Thanks to both of your responses, I have an idea now that I think will work,
and it should have (my) desired quality of encouraging generous approval
cutoff and ranking of candidates below the cutoff.
Basically, the idea is simply Beatpath: Break each cycle at the weakest link.
But what should be the weakest link? Why not call it the defeat made by the
candidate with lowest approval? We could call this Total Approval
Beatpath (TAB), but suggest a better name if you want.
(1) Sort candidates by approval, from highest to lowest, into a list
{A_1, A_2,..., A_n}.
(2) Initialize a linked list (or chain, if you prefer) of candidates B with
Approval Winner A_1. The beginning of the list is the winning end, and
the end is the losing end.
(3) For each A_i, i=2:n,
B node points to losing end candidate.
While A_i defeats B-node,
follow B-list backward to next stronger candidate,
set B-node to that candidate.
End while
Insert A_i before B-node.
End For
The winner is the candidate at the left most end of the list. The list gives
you the social ordering of the candidates.
This is just like Forest's proposal but doesn't eliminate candidates from the
B list.

Thanks for explaining your method. It is interesting, but I'm not sure I
understand it completely.

In step 3, I presume that by "defeats" you mean pairwise (as opposed to
Approval-wise). Suppose an A_i candidate does not pairwise defeat any of
the other candidates already on the chain. Is A_i then dropped or added
to the end of the chain?

If the latter is true, then by the time the least-approved candidate
comes along all the other candidates will be on the chain. Hence, the
least approved candidate cannot win unless he is the Condorcet winner.
Is it possible for the least-approved candidate to be the Condorcet winner?

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

Forest Simmons

2005-03-13 01:06:44 UTC

Kevin's Approval Runoff in which low approval candidates are eliminated
until there is a Condorcet Winner, can also be described as follows:

Pick the lowest approval score candidate that beats all of the candidates
with greater approval scores.

Proof of equivalence:

Kevin's winner KW has to beat all candidates with greater approval because
they do not get eliminated before the winner, which beats all remaining
candidates. And if any lower candidate were to beat all candidates above
it (including KW), then it would become the CW before KW.

Note that this new characterization of Kevin's winner does not require
talking about elimination or Condorcet Winners.

The voter just needs to understand "approval score" and "beats."

Here's a more procedural definition of the method:

List the candidates in order of approval scores, from lowest to highest.

Go up the list until you first come to a candidate that is not beaten
(head to head) by any of the candidates above it.

That candidate is the winner.

One could dispense with approval if ballots are to be strictly ordinal
rankings:

List the candidates in order of average rank, from lowest to highest.

Go up the list until you first come to a candidate that is not beaten
pairwise by any candidate further up the list.

This can be done with any list:

List the candidates in order of number of first place preferences, etc.

Jobst would use random approval ballot order instead of some deterministic
order.

Here's my randomization, which can be done with either a deterministic
order or one of Jobst's random orders (for good measure).

Let P be the set of candidates none of which is defeated pairwise by
anybody further up than she in the order. Pick from P by random ballot.

If both the initial order and the picking are done by random ballot, the
method is hard to second guess.

If approval order or random ballot order is used, then the method is
monotone, clone free, and independent from pareto dominated alternatives,
if I am not mistaken. [I have been wrong before.]

This method requires no concept any more difficult than approval order,
random ballot, or pairwise defeat.

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

Jobst Heitzig

2005-03-13 10:49:32 UTC

Dear Ted!

Post by Ted Stern
At first, I didn't understand what Frest meant by 'transitive, but I gather
what he mans is, start a chain by adding the first candidate from the sorted
list (Call that candidate A_i), to the new chain (call that B_j). When adding
a new candidate, start at the winning end, and test to see if the candidate
defeats the first B_j. If not, follow the list down to the next weaker
candidate and test again. Repeat until you find a defeated candidate. Mark
the location, but don't insert the A into the B list.
Then start testing from the losing end of the B list. If the A candidate
defeats the B candidate, continue following links to stronger B candidates.
If you end up at the same spot each time, the A candidate isn't in a cycle,
and can be inserted. Otherwise, you're effectively eliminating it from
further consideration.

Right.

I was thinking about this when writing the grand compromise proposal but
didn't propose it for some reason I don't remember, so I should give it
another thought. Did you prove any nice properties yet?

Post by Ted Stern
This is similar to Jobst's grand compromise and James Green-Armytage's
Approval-weighted Pairwise, but it isn't necessary to carry along a second
pairwise array.

Right.

Post by Ted Stern
Why might this be preferable to the other schemes mentioned?
- There is a strong disincentive to bullet vote or truncate (an exercise for
the reader, but consider the 35:A>B>>C, 25:B, 40:C, in which B voters ahve
truncated their true preference 25:B>A>>C).
- There is a strong incentive to be generous with approval cutoff -- you want
your nearest neighbors, if you will, to be considered earliest in the list.
- Much less strategic incentive to equal rank due to the approval cutoff.
Voters can express true preferences above the approval cutoff, AND below,
without fear of hurting their candidate.

Sounds promising, I'll think about that!

Yours, Jobst

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

Jobst Heitzig

2005-03-13 21:52:10 UTC

Dear Ted!

I now remember what conclusion I came to about this idea when I first
thought about it some months ago: It will always elect the least
approved candidate which beats all more approved ones. Proof: (i) The
winner, say X, beats all more approved ones; assume otherwise that Y
beats X and has more approval; then the beatpath Y>X is stronger than
all beatpaths X>... . (ii) No candidate with lower approval than X can
beat all more approved candidates; assume otherwise that Y beats all
more approved candidates and has less approval; then the beatpath Y>X is
stronger than all beatpaths ...>Y. This proof applies not only to
Beatpath with your definition of defeat strength but to all immune cycle
breaking methods (Beatpath, River, Ranked Pairs, ...) with your
definition of defeat strength.

In other words, this is the same method as Kevin's!

Yours, Jobst

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

Russ Paielli

2005-03-13 22:33:43 UTC

Post by Jobst Heitzig
Dear Ted!

I now remember what conclusion I came to about this idea when I first
thought about it some months ago: It will always elect the least
approved candidate which beats all more approved ones. Proof: (i) The
winner, say X, beats all more approved ones; assume otherwise that Y
beats X and has more approval; then the beatpath Y>X is stronger than
all beatpaths X>... . (ii) No candidate with lower approval than X can
beat all more approved candidates; assume otherwise that Y beats all
more approved candidates and has less approval; then the beatpath Y>X is
stronger than all beatpaths ...>Y. This proof applies not only to
Beatpath with your definition of defeat strength but to all immune cycle
breaking methods (Beatpath, River, Ranked Pairs, ...) with your
definition of defeat strength.
In other words, this is the same method as Kevin's!

Which method of Kevin's are you referring to?

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

Jobst Heitzig

2005-03-12 13:04:30 UTC

Dear Ted!

I explored TACC with some enthusiasm over the last couple of days.

It's astonishing that a method that simple could give such nice results,
isn't it? That was a fabulous idea by Forest to construct chains in
order of approval! I still want to explore his Needle method in more
detail to see whether it may be an interesting method if one does not
require Condorcet-efficiency.

1) List the candidates from lowest to highest approval
2) Starting with the lowest approved candidate, eliminate anybody she
defeats.
Any remaining candidates must defeat her.
Pick the remaining candidate with next higher approval, and repeat.

Right. That's a bit like Pythagoras' sieve, isn't it?

By the way, Jobst, what do you do about defeat ties or approval ties?

When I design a method I usually don't mind at first. However, ties can
always be resolved using a TBRO as in MAM without violating
monotonicity. Of course, ties will have to get more attention when we
design social choice methods for smaller groups, but here we deal with
general elections, right?

Since members of the Smith set defeats everybody outside the Smith set, TACC
would gets the same result if you start in the Smith set and ignore the
40: A>B>>C
35: B>C>>A
25: C>A>>B
So you start with C. C (approval 60) defeats A, so A (approval 65) is
eliminated. B (approval 75) defeats C and wins via TACC.
This differs from RP and Beatpath.

That's true. It resolves three-cycles in a fundamentally different way
than most Condorcet methods studied in the history of this list. It
doesn't care about defeat strengths but about approval scores instead.

I don't think it encourages altruistic approval cutoff

I missed the definition of that, so I will have to look that up in the
archives...

-- the Nash equilibrium will occur with
40: A>>B>C
35: B>>C>A
25: C>>A>B
which again has B winning.

Why is that? Can you argue for this equilibrium in more detail? It was
always my impression that in most situations there is either no
equilibrium of an interesting kind, or many of them, so why is there
exactly one in this situation? And what definition of "Nash equilibrium"
do you use, are the players (i) the individual voters, (ii) groups of
voters with identical sincere preferences [and approvals], or (iii)
arbitrary groups of voters?

Yours, Jobst

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

Ted Stern

2005-03-12 22:44:34 UTC

Post by Jobst Heitzig

-- the Nash equilibrium will occur with
40: A>>B>C
35: B>>C>A
25: C>>A>B
which again has B winning.

I'm assuming (ii), though of course this isn't entirely realistic.

Starting from the example with more generous approval cutoff, and examining
what happens if one block (say the A's or C's) attempt to gain an advantage
by not approving their 2nd choice.

If the election were repeated, the two other blocks would have no reason to
trust either of the other groups. Like 3-way rock/paper/scissors. Each of
them would withdraw to the more mistrustful position and the result would be
no better than before. But at least no worse.

I call it a Nash equilbrium because it's the strategy that eventually will
stabilize due to blocks attempting to gain best advantage for themselves.
Kind of like the way bidders on eBay have an incentive to bid at the very last
second ("sniping") to avoid betraying their interest.

Any time you want to augment Condorcet with Approval, you need to consider how
to prevent truncated approval, since that is its weakest point.

In my just-proposed Total Approval Beatpath (which may have been proposed long
ago), there is no benefit to "bullet" approval cutoff. Individuals or Blocks
actually have a stronger incentive to put the cutoff below the 2nd or 3rd
choice -- you want candidates you rank slightly lower to be about as high in
the ratings as your favorite, in order to get your softest opponents into
the approval ranking nearby.

Ted

--
Send real replies to
ted stern at u dot washington dot edu

Frango ut patefaciam -- I break so that I may reveal
----
Election-methods mailing list - see http://electorama.com/em for list info

Kevin Venzke

2005-03-14 15:10:53 UTC

Dear Jobst,

Post by Jobst Heitzig
Dear Ted!

Post by Ted Stern
Basically, the idea is simply Beatpath: Break each cycle at the weakest link.
But what should be the weakest link? Why not call it the defeat made by the
candidate with lowest approval? We could call this Total Approval
Beatpath (TAB), but suggest a better name if you want.

I suggested this measure of defeat strength when I proposed an easy way
to hand-count three-slot Condorcet, since by that method the WV information
isn't preserved. I believe you didn't like this measure because it seemed
unintuitive to elect anyone other than the approval winner when there is
a three-candidate cycle.

Kevin Venzke

Découvrez nos promotions exclusives "destination de la Tunisie, du Maroc, des Baléares et la Rép. Dominicaine sur Yahoo! Voyages :
http://fr.travel.yahoo.com/promotions/mar14.html
----
Election-methods mailing list - see http://electorama.com/em for list info

Ted Stern

2005-03-14 20:43:50 UTC

Post by Kevin Venzke
Dear Jobst,

Post by Jobst Heitzig
Dear Ted!

Basically, the idea is simply Beatpath: Break each cycle at the weakest link.
But what should be the weakest link? Why not call it the defeat made by the
candidate with lowest approval? We could call this Total Approval
Beatpath (TAB), but suggest a better name if you want.

Hi Kevin,

I'm not sure Jobst has analyzed my method correctly. Is this equivalent to
what you proposed?

"Rank candidate 'seeds' in descending order of approval. For a
candidate to move up in rank, it has to defeat all higher seeded
teams in succession, and only after each of those has itself moved
up in rank as much as possible."

See also my Total Approval Ranked Pairs message posted earlier.

Ted

--
Send real replies to
ted stern at u dot washington dot edu

Frango ut patefaciam -- I break so that I may reveal
----
Election-methods mailing list - see http://electorama.com/em for list info

Jobst Heitzig

2005-03-15 13:40:15 UTC

Dear Russ!

ARC (aka RAV) cannot elect the Approval winner when s/he beats
no other candidate since the method is Smith-consistent!

Yours, Jobst
______________________________________________________________
Verschicken Sie romantische, coole und witzige Bilder per SMS!
Jetzt bei WEB.DE FreeMail: http://f.web.de/?mc=021193

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

Forest Simmons

2005-03-17 01:32:10 UTC

Date: Tue, 15 Mar 2005 21:49:20 -0800
From: Russ Paielli <***@sneakemail.com>
Subject: [EM] Re: Total Approval Ranked Pairs
To: election-***@electorama.com

Russ worried that putting in an approval cutoff might be too costly.

The cost is the same as adding one extra candidate, the ACC (Approval
Cutoff Candidate).

Voters that truncate the ACC candidate are implicitly approving all of
their ranked candidates, since any ranked candidate is considered to be
ranked above all truncated candidates.

Russ went on to say that he wasn't too crazy about any of the proposed
names for ARC/RAV.

If we want to beat IRV we have to get "majority" into the title.

I suggest that we call it "Definite Majority Choice" which would be
consistent with the following description:

1. Rank as many candidates as you want. One of these candidates is the
Approval Cutoff Candidate (the ACC).

2. For each candidate X (besides the ACC) count how many of the ballots
rank X above the Approval Cutoff Candidate. This number is candidate X's
approval score.

3. Now withdraw the ACC, which has served its purpose.

4. For each candidate X determine if there is another candidate Y with
higher approval score than X, such that Y is also ranked higher than X by
a majority. If this is the case, we say that Y is definitely preferred
over X, and that X is a definite majority choice loser.

[In Fine Print] By "majority" we mean a majority of those voters that
express a preference between X and Y.

5. Eliminate all definite majority choice losers.

6. Choose as winner the candidate that is ranked above each of the other
remaining candidates by a majority.

[In each case it is to be understood that the majority is a majority of
those that express a preference.]

[End of method description]

What do you think?

Personally, I would rather see the last step replaced with

6'. Of the remaining candidates, pick as winner the one which is ranked
highest on a randomly chosen ballot.

But I realize that the advantage of this version over the deterministic
version is too subtle for the general voting public to appreciate.

But just for the record, I would call this stochastic version "Majority
Fair Chance."

Perhaps the citizens of a country like Rwanda could appreciate the method.

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

Araucaria Araucana

2005-03-17 21:14:10 UTC