[EM] Couple of comments (AMS, Why the fuss)

[Forest Simmons]

To make RP, CSSD, and River more decisive by a couple of orders of
magnitude ... I suggest gauging defeat strength by ....

Winning Votes minus epsilon*(Losing MaxPS)

Where the epsilon term is invoked only to break ties arising from the other
term.

If incomplete rankings are allowed, add another term of the form ...

epsilon^2*(losing abstentions minus winning abstentions).

Here "abstentions" means truncations .... in order to preserve precinct
summability.

If equal top rankings are allowed, add another term of the form
epsilon^3*(winning equal top minus losing equal top) ...

... where equal tops are counted whole, in order to preserve clone
independence.

Then a coin toss will never be needed.

But throw it in anyway for theoretical completeness.

The whole thing is efficiently precinct summable ... no multiple passes
needed!

Trade in wv for margins if you want ... but no need to alter the tie
breaking terms.

-Forest

On Mon, Mar 6, 2023, 8:37 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> On 06.03.2023 11:11, Colin Champion wrote:
> > I think Tideman's original description calls for the implementor to
> > recursively exhaust over all permutations of tied margins, and to
> > construct a winner set as the union of winners under all recursive
> > extensions. This is no fun. The Handbook of Computational Social Choice
> > (one of my few books on the subject) says "Whether a given alternative
> > is a ranked pairs winner... turns out to be NP-complete". (p100.)
>
> Yeah, that's BRILL, Markus; FISCHER, Felix. The price of neutrality for
> the ranked pairs method. In: Proceedings of the AAAI Conference on
> Artificial Intelligence. 2012. p. 1299-1305.
> https://ojs.aaai.org/index.php/AAAI/article/view/8250/8109
>
> (I forgot to put that cite in my reply to Kevin, so here it goes :-)
>
> I would *expect* that River is also NP-complete in the same way, but I
> haven't seen any proofs to that end.
>
> -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/20230307/bbfdc343/attachment.htm>