The AMS has switched from Ranked Pairs to Instant-Runoff Voting
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@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
Hi Kristofer,
Le lundi 6 mars 2023 à 10:25:05 UTC−6, Kristofer Munsterhjelm km_elmet@t-online.de a écrit :
I recently made a calculator that tries to show the steps to solve Ranked Pairs and River
and I couldn't come up with a satisfying way to dedupe all the possible ways that one could
traverse the propositions when there are tied strengths, and potentially many. I settled on
showing up to two traversals per possible winner.
IIRC, Tideman originally proposed a method where X wins if there exists
a way to break ties so that X comes unambiguously first in Ranked Pairs.
This method is neutral, but it's also (as Colin said) NP-complete. In
practice, people just break ties in some way. I think that the AMS
method (just a coin flip) fails clone independence and that random voter
hierarchy, while cloneproof, fails summability. But I'm not entirely
sure about either.
That sounds right. Additionally, I think you can't escape that if you say "We had to flip a
coin at step 4" or something, people will probably demand to know whether that determined
the outcome and if so which other candidates might have won.
(E.g. part of my intuition says: "if you pick a random voter and rank
A>B over B>A if that voter ranks A over B... isn't that the same as a
coin toss? Because imagine you eliminate everybody but A and B, then the
number of voters who rank A above B is just A>B, and the number of
voters who rank B above A is B>A; and by presumption that there's a tie,
A>B must be equal to B>A, so the chance of picking a voter who prefers A
to B is 50%". If it were that simple, then there would be no need for
random voter hierarchy, so clearly I'm missing something.)
Candidates in an RP tie don't need to be in a pairwise tie. The situation can be that you
have tied strengths E>F and I>J and depending on which one gets considered first, some
other random candidate will win.
One thing I could do is provide a bunch of examples on what methods
look like in my framework, taking the form of a Python 3 class, and
then people could just send me methods if they want. I'm not sure if
there would be any takers for that. It would probably be more
interesting if I was maintaining and publishing a big list of
results, which at the moment I'm not. (Partly due to the sensitivity
of results to scenario parameters.)
I've had similar ideas myself, that surely it should be possible to not
be duplicating each other's efforts as much. Strictly speaking, my
quadelect simulator is extensible, but I wouldn't call it very easy to
use and C++ has its own quirks.
Would you be interested in putting your code on a version control system
of some kind?
Not any time soon. It's easier to consider sharing some version privately, if you think it
would help your investigations. I'd still need to put some work into that though.
Kevin
votingmethods.net
On 3/5/23 11:28, Kristofer Munsterhjelm wrote:
There might also be something buried in the minutes here, although I
really don't fancy trawling through all the documents:
https://www.ams.ubc.ca/about-us/student-council/agendas-presentations-minutes/
An update on this: I downloaded all the pdfs (I think I got them all)
from ams.ubc.ca and made a quick and dirty pdftotext|grep thing to
search for runoff. The results I could find were mainly about water
runoff and projects related to it, but I found some information about
the IRV change.
The proposal seems to be due to the Elections Committee, but the
documents don't say just what happened in committee. The first mention I
can see of the IRV change is the Elections' Committee proposal,
https://www.ams.ubc.ca/wp-content/uploads/2023/02/CODE-CHANGES-2023-Miscellaneous-Election-Changes.pdf,
which clearly deletes the Condorcet language and adds IRV language
instead. This was passed on February 1 with a 2/3 majority:
https://www.ams.ubc.ca/wp-content/uploads/2023/01/Feb-1-Agenda-from-OnBoard.pdf
as part of a package of "miscellaneous election changes",
https://www.ams.ubc.ca/wp-content/uploads/2023/03/309-23-CODE-CHANGES-2023-Miscellaneous-Election-Changes.docx.pdf.
Then there is a record of a change to the IRV language:
https://www.ams.ubc.ca/wp-content/uploads/2023/02/AMS-Council-Submission-Code-Change-Instant-Run-Off-Voting.pdf,
but by this point the Condorcet language is already gone and it's just
fixing a definition of "majority" under optional IRV.
This fixup shows up in the council minutes of February 13, and is again
passed.
https://www.ams.ubc.ca/wp-content/uploads/2023/02/Agenda_2023-02-13.pdf
So the story seems to be that tht elections committee replaced the
Condorcet language with IRV language, made various other changes, and
the whole thing got passed in one go. But this just pushes the question
back to: why did the Elections Committee remove Ranked Pairs? The
documents don't seem to answer this question.
-km