[EM] Quick and Clean Burial Resistant Smith, compromise

[Kristofer Munsterhjelm]

On 17.01.2022 08:36, Daniel Carrera wrote:
> 
> 
> On Sat, Jan 15, 2022 at 5:54 PM Kristofer Munsterhjelm
> <km_elmet at t-online.de <mailto:km_elmet at t-online.de>> wrote:
> 
>>     I've at times thought that a more realistic approach would be to use
>>     evolutionary stable strategies, e.g. suppose everybody is honest, then
>>     some small faction defecting can't grow in power to the point where
>>     everybody feels the need to vote tactically. But that's even harder to
>>     model, and some societies are used to tactical voting at the start (e.g.
>>     US Plurality elections), and might thus not fit that very well.
> 
> 
> It would be a bit hard to model, but one could imagine allowing the
> electorate to run the election many times and adjust their strategy, but
> insert the assumption that if a voter will not get a better outcome by
> being strategic, they'll choose to be honest. So you could model whether
> an electorate that starts out with strategy evolves toward honesty.

Yes. Perhaps let each voter vote strategically with some probability p,
and if the strategy worked, p increases. It's a bit tricky because most
methods are nonresponsive to just a few ballots changing.

>>     Now I'm wondering if the strategically resistant methods mainly increase
>>     their resistance by making it impossible for trivial strategy to work in
>>     cases where it would otherwise work. From my experimentation, I've found
>>     out that reversal symmetry usually makes for a susceptible method, and
>>     that rev. sym. and Condorcet together are incompatible with dominant
>>     mutual third burial resistance.
> 
> 
> This really got me curious. I've been reading up on these concepts and I
> saw that you posted a proof of this in 2018. I still need to wrap my
> head around these concepts. For example, it's not intuitively obvious to
> me why reversal symmetry is important. If the voters are split into two
> equal camps:
> 
> Camp 1: Loves A, tolerates B, hates C
> Camp 2: Loves C, tolerates B, hates A
> 
> It's easy to see B as the right compromise winner, and if you reverse
> the preferences that wouldn't change.

In this scenario, for a rev. sym. obeying method, if the camps are
equally large, there's a three-way tie; otherwise the majority wins. So
reversal symmetry implies some kind of additional structure; in this
case that it can't be too compromise-friendly. And apparently this
structure then precludes certain types of strategy resistance, though I
have no idea why, as my proof is one of exhaustion.

> The wiki says that "a method that passes DMTBR is immune to electing the
> dark horse", but I can easily devise a pathological example where the
> dark horse is the Condorcet winner:
> 
> 9: A > X > B > C
> 7: B > X > C > A
> 5: C > X > A > B
> 
> So I assume that the wiki most be defining Dark Horse in a narrower
> sense than how I'm reading it.

Yeah, the point is that suppose a Dark Horse initially has no support,
i.e. actually is a universally loathed candidate. Then he's outside of
the innermost DMT set, and DMTBR says that voters who prefer A to the
current winner W can't make A win by burying W under someone who isn't
in the innermost DMT set. So the A-first voters have no incentive to
bury under the dark horse. Thus the ball doesn't get rolling and there's
no escalation into a chicken problem.

Warren then says "perhaps that won't save you because people will bury
blindly anyway". Which is something I don't agree with. Sometimes I get
the impression he draws too much experience from Borda, which *is* awful.

>>     In any case, as you say, strategy-resistant methods like the Smith-IRV
>>     hybrids will reduce the chance that strategy works, and so would give
>>     third parties some more room in which to grow.
> 
>>     It would be interesting to do a test with Range; I imagine that it would
>>     be very susceptible to strategy, similar to Approval. And I would also
>>     imagine that STAR would do considerably better.
> 
> 
> I just implemented Range and STAR and it seems that Range is indeed very
> susceptible but STAR is not much better. I had to make some arbitrary
> choices when implementing the scoring system. I made the score
> proportional to the negative distance between a voter and each
> candidate, normalized to span the 0-5 range. So every voter uses the
> entire 0-5 range, regardless of whether they feel strongly about their
> preferences or not. I imagine that's how most voters would behave.

I agree that's a realistic approach. Incidentally, normalizing the
ballots (which voters would most likely do to make use of the entire
range) means that a Range election outcome can change if losing
candidates enter or leave the race, even though Range strictly speaking
passes IIA.

> I chose a 0-5 range because that's what STAR seems to use. I also had to
> make some decisions on how to implement each strategy for a score ballot:
> 
> 1) For the trivial strategy, I give c_k a score of 5 and w_A a score of
> 0, and leave other scores the same.
> 
> 2) For the reverse strategy, I compute the ballot that w_A would have
> cast, I "reverse" the scores with "new_score = 5 - old_score". Then give
> a score of 5 to c_k and a score of 0 to w_A.
> 
> 3) For the moderate strategy, where I try every possible ranked ballot,
> I was forced to find a way to convert a ranked ballot into a set of
> scores. I decided to spread the scores uniformly from 0 to 5, so it's as
> if each preference is equally strong.
> 
> N_elections = 20,000
> N = 4, V = 99, C = 5
> Method   , 95% c.i.     , trivial, reverse, moderate, majority
> MiniMax  , 0.4019-0.4155, 0.895  , 0.0805 , 0.02447 , 0.219
> Hare     , 0.0683-0.0752, 1.000  , 0.0000 , 0.00000 , 0.135
> Benham   , 0.0470-0.0528, 0.979  , 0.0160 , 0.00502 , 0.132
> Smith_IRV, 0.0474-0.0532, 0.944  , 0.0169 , 0.03888 , 0.137
> Range    , 0.7828-0.7935, 0.832  , 0.1012 , 0.06667 , 0.601
> STAR     , 0.7485-0.7621, 0.620  , 0.0775 , 0.30275 , 0.522

Note that a majority winner doesn't make either Range or STAR
unmanipulable. So that could be (part of) the reason you're getting
different results to JGA.

Also, using every possible *rated* ballot instead of ranked might
slightly improve the moderate strategy.

I'm surprised that STAR is such a poor performer, though! (How about
IRNR_p? This is IRV-style elimination of the loser, except after each
step, the original rated ballot has the eliminated candidates removed
and then the ballot is rescaled to have unit p-norm. Try p=1,2,infinity.)

I guess the hunt's still on for a cardinal method that really resists
strategy. There's Hay voting, which is a strategyproof method (under VNM
utilities), but it has predictably awful honest performance, just like
Random Ballot has in the ranked domain.

-km