[EM] Method X, Landau

[Kevin Venzke]

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;

Kevin
(end)


Le mercredi 2 août 2023 à 09:54:45 UTC−5, Forest Simmons <forest.simmons21 at gmail.com> a écrit : 
On Wed, Aug 2, 2023, 4:15 AM Kristofer Munsterhjelm <km_elmet at t-online.de> wrote:
> I tried to check Landau//X. It had plenty of Other strats, which is not
> unexpected given your proof about independence of covered alternatives 
> plus first preference tiebreak implying nonmonotonicity... but I think 
> my implementation of Landau is suspect, so I'm not including it here.

Let M be the matrix whose (j,k) element is one (else zero) if candidate j defeats candidate k.

Then candidate j is uncovered iff the j_th row of (I+M)^2 is devoid of zeros  ... because the (j,k) element of this matrix is the number of distinct short beatpaths (i.e. of length 0,1, or 2) from candidate j to candidate k.