[EM] Smith, Ext-Minmax(margins) appears to meet mono-add-top - possible proof?

[Kristofer Munsterhjelm]

I have implemented an extended Minmax method, which I'll call 
Ext-Minmax, and let my criterion compliance program test a version 
ensured to be Smith (Smith,Ext-Minmax(margins)). It has thus far not 
found a single mono-add-top failure, although it has done so for certain 
other methods I've tried, where those failures are rare. While that is 
not a proof in itself, I think I see how Smith,Ext-Minmax passes 
mono-add-top.

If there is a CW, then we automatically pass mono-add-top, so we don't 
have to bother about that case. Thus, let's assume there are multiple 
candidates in the Smith set. Then a mono-add-top failure occurs when a 
ballot that ranks the winner first manages to overturn wins so that some 
other candidate that's lower ranked on that ballot displaces the winner 
from the Smith set.

But now consider Minmax with full rankings. It picks the candidate with 
the greatest minimal defeat against itself. That means that it picks the 
candidate who is most protected against having a win turned into a loss, 
because the minimal defeat (the candidate which could defeat it) is as 
far away as possible. Therefore, a ranking that puts this winner top 
will turn other candidates' wins into losses before it turns any of the 
winner's wins to losses, and thus the winner is protected against 
mono-add-top failure as other candidates will be pushed off the Smith 
set before it is.

The extension (the Ext in Ext-Minmax) is required to break ties so that 
the above still holds even if there's an "obscuring candidate" which 
defeats many candidates with equal strength.

Is that right? It seems to be, to me; but I'm more an empirical person 
than a thorough mathematical one, and so the proof may have flaws. If 
you find any, feel free to tell me (and the list).
For instance, I don't know why Margins works and WV doesn't, except that 
WV implies Plurality and that Woodall has shown you can't have all three 
of Smith, Plurality, and Mono-add-top. However, it is clear that if the 
method fails the criterion for full rankings, it also fails no matter 
whether you pick WV or Margins.

-

So, what *is* Ext-Minmax? It is, as I have explained in an earlier post, 
a variant of Minmax that breaks ties by next-to-maximal defeat, and then 
by next to next to maximal defeat and so on. More formally:

Say there are N candidates. For each candidate x, construct a sorted 
(N-1)-vector v_x so that v_x_1 is the strongest defeat against x, v_x_2 
is the next to strongest defeat against x, and so on.

Define a relation between two candidates x and y so that x < y iff there 
is some value P, 1 <= P <= (N-1), so that v_x_Z is equal to v_y_Z for 
all Z < P, and v_x_P < v_y_P. Furthermore, define x = y if it is neither 
the case that x < y nor x > y.

This relation is transitive.

Define each candidate's score as the number of candidates it is lesser 
than, according to the relation. The winner/s is/are the candidate/s 
with the greatest score.

(end definition)

In practice, I have programmed Ext-Minmax as first building the arrays, 
then sorting the contents of each in descending order, then sorting the 
arrays themselves in ascending order. I use C++, so I don't actually 
employ plain arrays, but pair<vector, int> so I can determine which 
candidate is ranked first afterward.

I have also experimented with Landau,Ext-Minmax(margins), and that also 
seems to pass mono-add-top, but I haven't run the program as long there, 
and I'm not completely sure my Landau code is right in the first place. 
Again, "X,Y" breaks ties in X by the relative ordering of those 
candidates according to Y.