Re: [EM] My Favorite Deterministic Condorcet Efficient Method: TACC
2010/11/8 fsimm...@pcc.edu
A few years ago Jobst invented Total Approval Chain Climbing or TACC for
short.
At the time I was too young (not yet sixty) to really appreciate how good
it was. It is a monotonic. clone
free, Condorcet Efficinet method which always elects from the Banks Set,
a nice subset of the Smith
Set (if not the entire Smith Set).
It is easy to describe:
(1) Initialize the variable S as the empty set S = { }.
(2) While some alternative beats every member of S pairwise, augment the
list S with the lowest
approval alternative that does so.
(3) Elect the last alternative added to S, i.e. the member of S with the
greatest approval.
That's it.
Obviously the method will elect the CW when there is one.
If the Smith set consists of a cycle of three alternatives, say A beats B
beats C beats A,, then this
method (TACC) will will elect either the member of this cycle with the
greatest approval or the one with
the second greatest approval, depending on whether or not the cyclic order
goes up or down the approval
list.
What I didn't appreciate in my younger days was how beautifully resistant
the method is to strategic
manipulation.
Scenario 1:
49 C
27 AB
24 B (sincere is BA)
The sincere CW is A, but the B faction creats an ABCA cycle by rruncation.
Assuming that approval is the same as ranked in each of the factions,
the approva order is (from
greatest to least) B, C, A . Since this is in the same cyclic order as
the cycle, C wins. If the B voters
are rational, they will not truncate A!
Now look at the burial temptation scenario:
49 AB (sincere is AC)
27 BC
24 CA
The sincere CW is C.
Now suppose that the A faction buries C as indicated above:
TACC will elect B. whether or not the A faction approves B.
But if the A faction votes ABC (ie, if they approve C), then C wins. So I
think that this method would work best with only 3 rating levels (only 2
approval levels) available.
Forest
Election-Methods mailing list - see http://electorama.com/em for list info
Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] My Favorite Deterministic Condorcet Efficient Method: TACC
Jameson Quinn wrote:
2010/11/8 fsimm...@pcc.edu mailto:fsimm...@pcc.edu
A few years ago Jobst invented Total Approval Chain Climbing or TACC
for short.
At the time I was too young (not yet sixty) to really appreciate how
good it was. It is a monotonic. clone
free, Condorcet Efficinet method which always elects from the Banks
Set, a nice subset of the Smith
Set (if not the entire Smith Set).
It is easy to describe:
(1) Initialize the variable S as the empty set S = { }.
(2) While some alternative beats every member of S pairwise,
augment the list S with the lowest
approval alternative that does so.
(3) Elect the last alternative added to S, i.e. the member of S with
the greatest approval.
That's it.
Obviously the method will elect the CW when there is one.
(...)
49 AB (sincere is AC)
27 BC
24 CA
The sincere CW is C.
Now suppose that the A faction buries C as indicated above:
TACC will elect B. whether or not the A faction approves B.
But if the A faction votes ABC (ie, if they approve C), then C wins.
So I think that this method would work best with only 3 rating levels
(only 2 approval levels) available.
Would this method be any good if Approval was changed into some other
method that's burial resistant and monotone, like Plurality or Bucklin?
For Plurality, the score would simply be the number of first place
votes, breaking ties by the number of second place votes, breaking ties
by the number of third place votes, etc.
For Bucklin, the score for a candidate would be the number of candidates
minus the round at which it attains a majority, breaking ties by how far
above the majority it got. QLTD might produce even fewer ties.
Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] My Favorite Deterministic Condorcet Efficient Method: TACC
Hi Kristofer, --- En date de : Mar 9.11.10, Kristofer Munsterhjelm km-el...@broadpark.no a écrit : Would this method be any good if Approval was changed into some other method that's burial resistant and monotone, like Plurality or Bucklin? Bucklin maybe, but the trick seems to be that it's hard to bury without altering approval order. In a cycle TACC elects the candidate who defeats the approval loser. I doubt there are any scenarios where burial succeeds whether or not the final approval order is changed. I'm not fond of the minimal defense failure... It seems to me the train wreck disincentive to defect is more likely to lead to favorite betrayal (and nomination disincentive) than cooperation. That is: 49 Bush 24 Gore 27 NaderGore If this is a Bush win, and people think the votes might actually look like this, it takes much less convincing to make the Nader voters create a Gore win via compromising, than to make Gore voters add tons of Nader second preferences. It's not even clear here that Gore voters are interested in Nader, in which case a Bush win is purely a favorite betrayal incentive. One might argue that Nader voters won't compromise when Nader seems stronger. But if Gore voters are reluctant to vote for Nader (no matter what the reason is), Nader isn't stronger in any meaningful way. He can't win the election. Kevin Election-Methods mailing list - see http://electorama.com/em for list info
[EM] My Favorite Deterministic Condorcet Efficient Method: TACC
31: AB 32: BC 37: CA Approvals: B63, A68, C69. ABCA. TACC elects A, but C is positionally the dominant candidate and pairwise beats A. For a Condorcet method with pretension to mathematical elegance, I don't see how that can be justified. Chris Benham PS: Could someone please refresh our memories: What is the Banks Set? From Jobst Heitzig (March 2005): ROACC (Random Order Acrobatic Chain Climbing): -- 1. Sort the candidates into a random order. 2. Starting with an empty chain of candidates, consider each candidate in the above order. When the candidate defeats all candidates already in the chain, add her at the top of the chain. The last added candidate wins. The good thing about ROACC is that it is both - monotonic and - the winner is in the Banks Set, in particular, the winner is uncovered and thus the method is Smith-, Pareto-, and Condorcet-efficient. Until yesterday ROACC was the only way I knew of to choose an uncovered candidate in a monotonic way. But Forest's idea of needles tells us that it can be done also in another way. The only difference is that in step 1 we use approval scores instead of a random process: TACC (Total Approval Chain Climbing): 1. Sort the candidates by increasing total approval. 2. Exactly as above. The main differences in properties are: TACC is deterministic where ROACC was randomized, and TACC respects approval information where ROACC only uses the defeat information. And, most important: TACC is clone-proof where ROACC was not! That was something Forest and I tried to fix without violating monotonicity but failed. More precisely, ROACC was only weakly clone-proof in the sense that cloning cannot change the set of possible winners but can change the actual probabilites of winning. With TACC, this makes no difference since it is deterministic and so the set of possible winners consists of only one candidate anyway. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] My Favorite Deterministic Condorcet Efficient Method: TACC
I'm not fond of the minimal defense failure... It seems to me the train wreck disincentive to defect is more likely to lead to favoritebetrayal (and nomination disincentive) than cooperation. That is: 49 Bush 24 Gore 27 NaderGore If this is a Bush win, and people think the votes might actually look like this, it takes much less convincing to make the Nader voters create a Gore win via compromising, than to make Gore voters add tons of Nader second preferences. It's not even clear here that Gore voters are interested in Nader, in which case a Bush win is purely a favorite betrayal incentive. One might argue that Nader voters won't compromise when Nader seems stronger. But if Gore voters are reluctant to vote for Nader (no matterwhat the reason is), Nader isn't stronger in any meaningful way. He can't win the election. Forest Replies: As we know, in the above scenario the result that is best assuming sincere votes is not the same as the result that is best assuming that the Gore faction truncated in order to create the cycle. Assuming sincere votes giving Bush the win encourges favorite betrayal. Assuming insincere truncation of Nader in the second faction and giving Gore the win rewards that truncation. Nader cannot be given the win because of the Plurality criterion. So there is no completely satisfactory deterministic solution. However, on the whole, if we want determinism and Condorcet efficiency, it seems more important to prevent insincere cycle producing truncation than worrying about lack of FBC compliance, since (1) the FBC and Condorcet efficiency are incompatible, any way, and (2) sincere Condorcet cycles are rare (in my opinion). Now consider the following propositions (relative to the above scenario): (1) Woodall's Plurality Criterion says that Nader should have less probability than Bush. (2) It seems that Gore and Nader together should have more probability than Bush. (3) Gore should not have more probability than Bush, because that would encourage truncation in another case where the sincere ballots of the middle faction turn out to be GoreNader . No deterministic method can satisfy these three conditions. But the following probabilities are consistent with all three: Prob(Bush)=38.5% Prob(Gore)=35.5% Prob(Nader)=26% These probabilities came from the stochastic analog of TACC that I call RBOCC for Random Ballot Order Chain Climbing. Forest Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] My Favorite Deterministic Condorcet Efficient Method: TACC
Date: Mon, 08 Nov 2010 23:58:43 + (GMT)
From: fsimm...@pcc.edu
A few years ago Jobst invented Total Approval Chain Climbing or TACC for
short.
At the time I was too young (not yet sixty) to really appreciate how good it
was. It is a monotonic. clone
free, Condorcet Efficinet method which always elects from the Banks Set, a
nice subset of the Smith
Set (if not the entire Smith Set).
It is easy to describe:
(1) Initialize the variable S as the empty set S = { }.
(2) While some alternative beats every member of S pairwise, augment the
list S with the lowest
approval alternative that does so.
(3) Elect the last alternative added to S, i.e. the member of S with the
greatest approval.
That's it.
Obviously the method will elect the CW when there is one.
If the Smith set consists of a cycle of three alternatives, say A beats B
beats C beats A,, then this
method (TACC) will will elect either the member of this cycle with the
greatest approval or the one with
the second greatest approval, depending on whether or not the cyclic order
goes up or down the approval
list.
What I didn't appreciate in my younger days was how beautifully resistant the
method is to strategic
manipulation.
Scenario 1:
49 C
27 AB
24 B (sincere is BA)
The sincere CW is A, but the B faction creats an ABCA cycle by rruncation.
Assuming that approval is the same as ranked in each of the factions, the
approva order is (from
greatest to least) B, C, A . Since this is in the same cyclic order as the
cycle, C wins. If the B voters
are rational, they will not truncate A!
Now look at the burial temptation scenario:
49 AB (sincere is AC)
27 BC
24 CA
The sincere CW is C.
Now suppose that the A faction buries C as indicated above:
TACC will elect B. whether or not the A faction approves B.
Forest
I like it a lot Forest and believe it would make most voters happy
with the outcome. Great that it's monotonic and strategy resistant so
encourages sincere voting.
What does clone free mean again please?
It is a little tricky to count, not very intuitive, so I wonder how to
explain it so most people could understand its logic? The logic seems
solid.
It is precinct-summable with an n x n matrix (n = # candidates) using
the diagonal for the # approval votes for each candidate. Not sure
how to do the sampling mathematics for post-election audits - might be
a challenge to figure out how to limit the risk of certifying an
incorrect candidate.
Do you have a multi-winner version or a proportional representation version?
Regards,
--
Kathy Dopp
http://electionmathematics.org
Town of Colonie, NY 12304
One of the best ways to keep any conversation civil is to support the
discussion with true facts.
Fundamentals of Verifiable Elections
http://kathydopp.com/wordpress/?p=174
Realities Mar Instant Runoff Voting
http://electionmathematics.org/ucvAnalysis/US/RCV-IRV/InstantRunoffVotingFlaws.pdf
View some of my research on my SSRN Author page:
http://ssrn.com/author=1451051
Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Thinned List Chain Climbing
Dear EM list folks, I grew up on a sugar beet farm. Evey spring after the beets sprouted we thinned them to allow the remaining ones to reach their potential. It turns out that chain climbing can enjoy a similar benefit from the thinning of an over crowded seed list. The seed list for TACC is a list of the alternatives in order of approval. Lack of thinning makes ordinary TACC fail the IPDA (Independence from Pareto Dominated Alternatives). In what follows let the letter L represent any list of alternatives such that (a) it is monotonically generated, so that if only alternative A improves relative to other alternatives on one or more ballots, then it is the only one that moves up the list, and (b) if alternative B is ranked ahead of alternative C on at least one ballot, as well as on all ballots where they are not ranked equal (or both truncated), then B appears no lower in the list L than C. For example ... (1) L could be the list of candidates in random ballot order (where additional ballots are drawn at random if necessary to refine the order until it is a complete ranking of the alternatives). OR (2) L could be the list of candidates in the order of fewest truncations on the ballot. The first of these orders can be used to break ties in the second order without disturbing the desired properties. Now for the thinning: To thin L just remove every alternative that is covered by an alternative higher (i.e. earlier) in the original list. In the first example, remove X if it is convered by some Y with fewer truncations. In the second example, remove X if it is covered by some Y that is preferred over X in the random ballot order. Remember that Y covers X iff it pairwise beats X along with every alternative that X beats. After thinning L, apply regular chain climbing to the thinned list. This method (applied to the kinds of lists we are talking about) satisfies Independence from Pareto Dominate Alternatives. In fact, we can say more. If we agree that Y strongly covers X with respect to L when X is covered by Y from higher up the list L, then we can say that the method is Independent from Strongly L-Covered Alternatives. It preserves, monotonicity, and to the degree L respects clone sets, the method satisfies clone independence. Furthermore, if the order of L restricted to the Smith Set is the same as it would be were L recreated from the same ballots with the non-Smith alternatives removed, then the method is Independent from non-Smith Alternatives. The above examples (properly interpreted) satisfy this condition. When we take into account that the method (no matter which L) always picks from the Banks set, we have a truly respectable list of properties. Furthermore, for the above two example orders for L, the method has unparalleled resistance to strategic cycle creation by burial and truncation, which is the Achilles Heel of most otherwise respectable Condorcet methods. Among ourselves, let's call the general technique Thinned List Chain Climbing. For the stochastic method based on Thinned Random Ballot Order (example 1 above), let's call it ThRnBltOCC. For the determinsitic method based on Thinned Fewest Truncations Order, let's call it ThFwTrOCC. Then when we make a public proposal, we can call it the True Majority Choice method, or whatever title will sell the best without fibbing. What do you think? Forest Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] My Favorite Deterministic Condorcet Efficient Method: TACC
Hi Forest, --- En date de : Mar 9.11.10, fsimm...@pcc.edu fsimm...@pcc.edu a écrit : As we know, in the above scenario the result that is best assuming sincere votes is not the same as the result that is best assuming that the Gore faction truncated in order to create the cycle. Assuming sincere votes giving Bush the win encourges favorite betrayal. Assuming insincere truncation of Nader in the second faction and giving Gore the win rewards that truncation. Nader cannot be given the win because of the Plurality criterion. So there is no completely satisfactory deterministic solution. I agree technically, but on these ballots I don't think it's likely that any special incentive is operating on the Gore voters, or that one can be found that would make them completely stop their truncation. In my opinion this unpleasant situation will tend to be solved prior to election day. As I've said before, there is too little to gain and everything to lose in one side running two strong candidates. So, nomination disincentive is actually unavoidable, I think. I don't usually regard truncation as insincere in the same way that burial or compromise is insincere, but it seems particularly unusual to call it insincere in the context of an approval-based method. However, on the whole, if we want determinism and Condorcet efficiency, it seems more important to prevent insincere cycle producing truncation than worrying about lack of FBC compliance, since (1) the FBC and Condorcet efficiency are incompatible, any way, and (2) sincere Condorcet cycles are rare (in my opinion). Well for (1), also burial resistance and LNHarm are incompatible with Condorcet. I'm also not talking about strict FBC compliance, but just minimal defense, which is basically a weak form of FBC for majorities. For (2) I am not sure what all you include in sincere. For strictly ranked sincere ballots, I agree that cycles should be rare. If truncation (as under an approval-based method) isn't considered insincere then I think sincere cycles need not be uncommon. If they are, I would guess it's because in practice not enough viable candidates are nominated to see the problem. Now consider the following propositions (relative to the above scenario): (1) Woodall's Plurality Criterion says that Nader should have less probability than Bush. (2) It seems that Gore and Nader together should have more probability than Bush. (3) Gore should not have more probability than Bush, because that would encourage truncation in another case where the sincere ballots of the middle faction turn out to be GoreNader . No deterministic method can satisfy these three conditions. The way I phrase this problem with this scenario is that no method can simultaneously satisfy Plurality, Minimal Defense, and LNHarm. Which one to lose (with 3 candidates) depends on what you're going for... Personally, the methods I'm interested in all either satisfy MD or LNHarm. I don't really care about Condorcet except as it can service MD or other criteria that protect literal majorities. Kevin Election-Methods mailing list - see http://electorama.com/em for list info
