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

[Kristofer Munsterhjelm]

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