[EM] Method X

[Kristofer Munsterhjelm]

On 8/2/23 16:24, Forest Simmons wrote:
> 
> 
> On Tue, Aug 1, 2023, 4:21 PM Kristofer Munsterhjelm 
> <km_elmet at t-online.de <mailto:km_elmet at t-online.de>> wrote:
>>     Now for the bad news:
>>              - it's not summable (a summary takes O(n2^n) space),
>>              - it's not polytime (ditto),
>>              - its use of quotas means it would probably fail IIB,
>>              - and I have no idea why it works.
> 
>>     I can't say I wasn't tempted to name it after myself since it's kind of
>>     a big deal (if I can verify its monotonicity), but given its drawbacks,
>>     maybe it's not a good idea? It's like the Kemeny of monotone
>>     burial-resistant methods: slow and impractical, but it shows what's
>>     *possible*.
> 
> 
> The reason Kemeny is computationally intractable is the sheer number of 
> finish orders that have to be checked to make sure you got the one that 
> minimizes the sum of the Kendall-tau distances (or swap cost metrics for 
> my Cline independent version) to the ballot rankings. Computing the swap 
> cost metric sum for any given finish order is cheap(in both time and 
> space).
> 
> So the simplest way to get the strategy resistant benefit of the method 
> is to allow voters, candidates, and other stake holders to each submit 
> several thousand finish orders, and then generate several trillion more 
> at random ... and then quickly compute the minimal cost solution 
> restricted to these few trillions of proposals.
> 
> It seems to me that the same idea would make Method X "approximately 
> tractable." In other words, MonteCarlo plus unlimited (but not by bots) 
> stake holder submissions.

Yes, you could deal with it that way in practice, possibly combined with 
a restriction to the Smith set. Since there doesn't seem to be any 
monotonicity drawback to just using Smith//X here, and most (current) 
public elections would have a very small Smith set, in the vast majority 
of cases exhaustive calculation would suffice.

Just like Kemeny :-)

There's a part of me that likes mathematical elegance, that would like 
to find something that's to this method what Ranked Pairs is to Kemeny: 
preserving its unique property (LIIA or monotone burial resistance) 
while improving on it (by being polytime).

But I shouldn't let that devalue the significance of finding method X in 
the first place! That does mean I have to find a better name for it, though.

-km