[EM] Method X, Landau

[Kristofer Munsterhjelm]

On 8/3/23 02:54, Kevin Venzke wrote:
> I plan to implement Method X when I get a moment. I'm not completely
> skeptical about its monotonicity since it doesn't seem like there's an
> obvious argument why it shouldn't be monotone.
> 
> For Landau, I use some code like this, which I base on the explanation on Wikipedia:
> 
> let landau = [];
> for(x in candidates) {
> let i_am_covered = false;
> for(z in candidates) {
> if( x != z ) { // X can't cover themselves
> let found_y = false;
> for(y in candidates) {
> // Note that beats_or_ties should evaluate as true if the two operands are the same candidate
> if( x beats_or_ties y && y beats_or_ties z ) {
> // alternative to the above line which should be right:
> // if( not( y beats x || z beats y ) ) {
> found_y = true; // found a counterexample to Z covering X
> break; // cease checking for Ys for this Z
> } //if x...
> } //for y
> if( not found_y ) {
>   i_am_covered = true; // Z evidently covers X
> break; // cease checking for Zs for this X
> } // if not found_y
> } // if x!=z
> } // for z
> if( not i_am_covered ) landau.append( x );
> } // for x
> return landau;

I've run my Landau calculator against this for a day, and I haven't 
found any discrepancies. So it looks like my Landau calculator does 
work, and it's good to know that the weird things I was seeing weren't 
due to bugs.

My Landau set function uses short beatpaths; I was concerned that the 
beatpath calculation code itself was wrong.

In any event, here's the data for Landau//Method X. It's clearly not 
monotone, but as I said elsewhere, I'm not surprised since Forest proved 
that was inevitable as (under reasonable assumptions) independence of 
covered alternatives implies nonmonotonicity. But it's not strategy 
resistant either, so there's not much of a reason to use it!

Burial, no compromise:	9740	0.199174
Compromise, no burial:	7624	0.155904
Burial and compromise:	3730	0.076275
Two-sided:		5483	0.112122
Other coalition strats:	22322	0.456464
==========================================
Manipulable elections:	48899	0.999939

Landau,X isn't much better:

Burial, no compromise:	6093	0.124744
Compromise, no burial:	10123	0.207252
Burial and compromise:	1277	0.0261445
Two-sided:		7138	0.146139
Other coalition strats:	23721	0.485648
==========================================
Manipulable elections:	48352	0.989927

So that's not the way to get uncovered.

-km