So I implemented chain climbing as a higher order/meta method in quadelect to check if it is compatible with or can improve strategy resistance. What I've found so far (assuming my implementation is correct) is: - Strategy resistant methods don't seem to preserve their resistance when used as the base method for chain climbing (starting from loser and then building a chain). - At least for three candidates, where I have brute-force methods, there do exist base methods whose compositions with chain climbing are strategy resistant. - However, these base methods make absolutely no sense on their own. So the pattern seems to be that while chain climbing ensures Banks compliance, it nonlinearly warps the landscape of which methods are good and which are bad, which means that our usual heuristics won't work. It becomes very difficult to create a method that preserves desirable properties when passed through chain climbing. As an example of strange base methods, here's a linear three-candidate method in the format of fpA-fpC: f(A) = BAC + 2 BCA - ABC The composition of this and chain climbing has about the same strategy resistance as Smith,IRV. And here's a nonlinear method: f(A) = BCA * BAC with similar performance as fpA - fpC. Neither of these strange methods is monotone. On a more theoretical level, it should be possible to craft a base method so that the chain climbing composition always produces the same winner as fpA-fpC in the three candidate case, by building a set of implications. E.g. let f(A) = fpA - fpC be the method we want to replicate, and g(A) be the scoring function for the base method we want to pass through chain climbing, then we have whenever f(A) > f(B) > f(C) (i.e. A wins) then either g(C) > g(A) > g(B) or g(A) > g(C) > g(B) and then similarly for every way to relabel candidates. In the first case, B is admitted, then A beats B pairwise and is admitted, then C isn't because C doesn't beat B; in the second case, B is admitted, then C is skipped, then A is admitted. But it's not a particularly pleasant way to design a method! -km

As soon as you abandon the monotone agenda formation requirement, chain Climbing (from the nominally unpromising end of the agenda towards the nominally favorable end) loses its validity ... all bets are off. In the three candidate Smith set case the most promising candidate that defeats the least promising Smith member is elected. The least promising Smith member is usually the sincere CW. The Smith member that beats it is the "bus" under which it was nuried ... so good poetic punishment for the niriers. Like most methods good at punishing the buriers, this method needs a sincere runoff to recover the sincere CW. The appropriate three candidate runoff is the chain climbing winner W [most likely the bus] versus a runoff between the least promising Smith member Z [probably the sincere CW] and the one that does not defeat Z [the probable burier candidate]. Rational voters informed on preferences will pass on W, and elect Z. Any Condorcet method that almost always positively punishes the buriers (by electing the "bus"rather than either the buried CW or burier) will look just as strange. In particular it will fail symmetry reversal when restricted to a three member Smith set. Hence the importance of the sincere runoff for any such method, not just chain climbing. On Sun, Aug 13, 2023, 10:04 AM Kristofer Munsterhjelm <km_elmet@t-online.de> wrote: > So I implemented chain climbing as a higher order/meta method in > quadelect to check if it is compatible with or can improve strategy > resistance. What I've found so far (assuming my implementation is > correct) is: > > - Strategy resistant methods don't seem to preserve their resistance > when used as the base method for chain climbing (starting from loser and > then building a chain). > > - At least for three candidates, where I have brute-force methods, there > do exist base methods whose compositions with chain climbing are > strategy resistant. > > - However, these base methods make absolutely no sense on their own. > > So the pattern seems to be that while chain climbing ensures Banks > compliance, it nonlinearly warps the landscape of which methods are good > and which are bad, which means that our usual heuristics won't work. It > becomes very difficult to create a method that preserves desirable > properties when passed through chain climbing. > > As an example of strange base methods, here's a linear three-candidate > method in the format of fpA-fpC: > > f(A) = BAC + 2 BCA - ABC > > The composition of this and chain climbing has about the same strategy > resistance as Smith,IRV. And here's a nonlinear method: > > f(A) = BCA * BAC > > with similar performance as fpA - fpC. Neither of these strange methods > is monotone. > > On a more theoretical level, it should be possible to craft a base > method so that the chain climbing composition always produces the same > winner as fpA-fpC in the three candidate case, by building a set of > implications. E.g. let f(A) = fpA - fpC be the method we want to > replicate, and g(A) be the scoring function for the base method we want > to pass through chain climbing, then we have > whenever f(A) > f(B) > f(C) (i.e. A wins) > then either > g(C) > g(A) > g(B) or > g(A) > g(C) > g(B) > > and then similarly for every way to relabel candidates. > > In the first case, B is admitted, then A beats B pairwise and is > admitted, then C isn't because C doesn't beat B; in the second case, B > is admitted, then C is skipped, then A is admitted. > > But it's not a particularly pleasant way to design a method! > > -km > ---- > Election-Methods mailing list - see https://electorama.com/em for list > info >

On 8/15/23 03:20, Forest Simmons wrote: > As soon as you abandon the monotone agenda formation requirement, chain > Climbing (from the nominally unpromising end of the agenda towards the > nominally favorable end) loses its validity ... all bets are off. > > In the three candidate Smith set case the most promising candidate that > defeats the least promising Smith member is elected. > > The least promising Smith member is usually the sincere CW. The Smith > member that beats it is the "bus" under which it was nuried ... so good > poetic punishment for the niriers. > > Like most methods good at punishing the buriers, this method needs a > sincere runoff to recover the sincere CW. > > The appropriate three candidate runoff is the chain climbing winner W > [most likely the bus] versus a runoff between the least promising Smith > member Z [probably the sincere CW] and the one that does not defeat Z > [the probable burier candidate]. > > Rational voters informed on preferences will pass on W, and elect Z. > > Any Condorcet method that almost always positively punishes the buriers > (by electing the "bus"rather than either the buried CW or burier) will > look just as strange. In particular it will fail symmetry reversal when > restricted to a three member Smith set.  Hence the importance of the > sincere runoff for any such method, not just chain climbing. That's not quite what I'm saying. The candidate who is elected by a burial-resistant method may leave something to be desired if burial is done anyway - see my other reply. But what seems to be particular to chain climbing - at least on agendas that aren't strongly monotone - is that it warps the regions where good methods lie and where the bad methods lie so thoroughly that nothing makes sense anymore. It's not just that strategy-resistant methods produce bad outcomes. But rather, methods that were originally strategy resistant stop being so; but methods that weren't strategy resistant don't gain resistance either. I ran the chain climbing composition of just about every method available to quadelect (some methods excluded due to bugs or neutrality/anonymity violations), using a multi-armed bandit search to find the best. The best "plain" strategy-resistant method is usually something like Smith,IRV or Smith//IRV where strategy succeeds around 45-50% of the time under impartial culture (97 voters, 5 candidates), disregarding Antiplurality whose results seem to just be an artifact of IC. With the chain climbing composition, the best methods are Antiplurality-CC and Coombs-CC, at 65% or so. And I suspect they only get that much because of impartial culture's weak spot to antiplurality, although I'm surprised that doesn't get warped away too. Then I did a three candidate search over 15k linear methods and 100k nonlinear ones on three candidates, showing that strategy resistance still exists, but the methods make no sense. So perhaps what we can say is, and what I wanted to say was: - Chain climbing doesn't work on methods that aren't strongly monotone. - For such methods, strategy resistance is neither improved nor preserved through composition. - There do exist non-strongly-monotone methods that when composed with CC are strategy-resistant. - However, designing them is near-impossible. Which I guess is what you implied by "all bets are off". I just don't think the need for a runoff is related to the bizarre behavior of chain climbing in particular. -km

On Wed, Aug 16, 2023, 4:39 AM Kristofer Munsterhjelm <km_elmet@t-online.de> wrote: > On 8/15/23 03:20, Forest Simmons wrote: > > As soon as you abandon the monotone agenda formation requirement, chain > > Climbing (from the nominally unpromising end of the agenda towards the > > nominally favorable end) loses its validity ... all bets are off. > > > > In the three candidate Smith set case the most promising candidate that > > defeats the least promising Smith member is elected. > > > > The least promising Smith member is usually the sincere CW. The Smith > > member that beats it is the "bus" under which it was nuried ... so good > > poetic punishment for the niriers. > > > > Like most methods good at punishing the buriers, this method needs a > > sincere runoff to recover the sincere CW. > > > > The appropriate three candidate runoff is the chain climbing winner W > > [most likely the bus] versus a runoff between the least promising Smith > > member Z [probably the sincere CW] and the one that does not defeat Z > > [the probable burier candidate]. > > > > Rational voters informed on preferences will pass on W, and elect Z. > > > > Any Condorcet method that almost always positively punishes the buriers > > (by electing the "bus"rather than either the buried CW or burier) will > > look just as strange. In particular it will fail symmetry reversal when > > restricted to a three member Smith set. Hence the importance of the > > sincere runoff for any such method, not just chain climbing. > > That's not quite what I'm saying. The candidate who is elected by a > burial-resistant method may leave something to be desired if burial is > done anyway - see my other reply. But what seems to be particular to > chain climbing - at least on agendas that aren't strongly monotone - is > that it warps the regions where good methods lie and where the bad > methods lie so thoroughly that nothing makes sense anymore. > > It's not just that strategy-resistant methods produce bad outcomes. But > rather, methods that were originally strategy resistant stop being so; > but methods that weren't strategy resistant don't gain resistance either. > > I ran the chain climbing composition of just about every method > available to quadelect (some methods excluded due to bugs or > neutrality/anonymity violations), using a multi-armed bandit search to > find the best. The best "plain" strategy-resistant method is usually > something like Smith,IRV or Smith//IRV where strategy succeeds around > 45-50% of the time under impartial culture (97 voters, 5 candidates), > disregarding Antiplurality whose results seem to just be an artifact of IC. > > With the chain climbing composition, the best methods are > Antiplurality-CC and Coombs-CC, at 65% or so. And I suspect they only > get that much because of impartial culture's weak spot to antiplurality, > although I'm surprised that doesn't get warped away too. > > Then I did a three candidate search over 15k linear methods and 100k > nonlinear ones on three candidates, showing that strategy resistance > still exists, but the methods make no sense. > > So perhaps what we can say is, and what I wanted to say was: > - Chain climbing doesn't work on methods that aren't strongly > monotone. > - For such methods, strategy resistance is neither improved > nor preserved through composition. > - There do exist non-strongly-monotone methods that when > composed with CC are strategy-resistant. > - However, designing them is near-impossible. > > Which I guess is what you implied by "all bets are off". I just don't > think the need for a runoff is related to the bizarre behavior of chain > climbing in particular. > Well, in the rare but not insignificant case of a sincere three member top cycle, wv Ranked Pairs would give a much, much better result than Chain Climbing on the RP finish order, which will elect the candidate that is defeated by the RP winner But, if the cycle is not sincere, that candidate that is beaten by the RP candidate is the only one whose election will punish the buriers.... and that candidate is the only one that defeats the Smith candidate member that is lowest in the RP finish order ... i.e. that candidate is the Chain Climbing winner. It punishes well, but like other burial resistant methods, it fails to correct the burial. There is a kind of uncertainty principle here, the more surely the method punishes the buriers, the less likely it will elect the buried sincere CW. That's why the better a method punishes buriers, the more important to have a sincere runoff. If you have a method M like RP that works well with sincere cycles, a sincere runoff of the form S1 vs ( S2 vs S3) where S1,S2,S3 are the first three Smith members in the Method M finish order ... that runoff will elect the sincere CW among those three if there is one, else it will appropriately elect S1. It seems that's about the best we can do with a simple deterministic single seat method based on ranked choice ballots and a top three Smith manual runoff. fws > -km >