[EM] Method X

[Forest Simmons]

On Tue, Aug 1, 2023, 4:21 PM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> This is method X, the monotone burial-resistant method from the previous
> post: (It doesn't really have a name yet.)
>
> - Each candidate A obtains his score by eliminating candidates in
> rounds, one candidate per round, until one other candidate (B) remains
> or A himself is forced to be eliminated. In the former case, A's score
> is A>B. In the latter case, A's score is zero.
>
> - When figuring out A's score, the method chooses the sequence of
> candidates to eliminate so as to maximize that score.
>
> - In a round, the method can never eliminate a candidate who has more
> than 1/n of the total number of (non-exhausted) first preferences, where
> n is the number of remaining candidates in the round in question.
>
> - Unlike IFPP, it never eliminates more than one candidate per round.
>
> - Highest score wins.
>
> That's it!
>
> 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.

>
> I would very much like some independent verification or replication,
> though.
>
> -km
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230802/8719e459/attachment.htm>