Dodgson

[janmotl]

When I use examples from Some Remarks on Dodgson’s Voting Rule then www.condorcet.vote delivers different results than expected. Is it because the implementation provides optimistic estimates on the count of "swaps"? If so, it should be noted in the documentation.

Example 1:

D>A>B>C*1
A>D>B>C*1
A>B>C>D*2
D>B>C>A*2
C>A>B>D*2
B>C>A>D*2
D>C>A>B*2

Expected winner: A Delivered winner: D

Example 2:

B>A>C>D*5
A>C>B>D*5
A>B>D>C*9
B>D>C>A*9
C>A>D>B*15

Expected winner: A Delivered winner: C

[julien-boudry]

Hi,

Thanks for this report. I need a little time to get back to that logic.

I have worked on Dodgson method with relatively little documentation and example, and i write only one test (successful) found here: http://www.cs.wustl.edu/~legrand/rbvote/desc. html

I didn't know that documentation. I have just written 8 new tests from this document. See commit e92756f3

Among them: 3 failures. In total I have 6 of 9 successful tests. Which remains highly questionable. I try to understand and correct it very quickly.

[julien-boudry]

Note that I followed the method described in this document: http://www.cs.wustl.edu/~legrand/rbvote/desc And that it seems to be completely false in comparison with what can be found elsewhere.

[janmotl]

I think I would rather trust peer-reviewed sources than "work in progress": http://www.cs.wustl.edu/~legrand/rbvote/.

Isn't there a typo in testResult_6 test? Shouldn't row C>A>B<D*7 be C>A>B>D*7?

[julien-boudry]

Yes, i fix this typo without consequences and add one more test from https://link.springer.com/article/10.1007/s003550000060

I'm currently working on a completely new implementation (not yet on Git). Strangely, the very firsts results show exactly the same fails tests than the previous implementation whereas the calculation method differ totally.

I keep hoping and try to work on it tonight. If you found detailed step-by-step examples, giving also good practice for specific cases (equality allowed in votes...) : i'm interested.

[janmotl]

Maybe https://link.springer.com/article/10.1007/s13218-016-0454-8 is worth of looking at.

[julien-boudry]

http://dss.in.tum.de/files/brandt-research/dodgson.pdf : The method used in this document is curious. It does not work in terms of number of votes, but by grouping equals votes together. 100 people vote A>B>C = 1 swap 2 people vote C>B>A> = 1 swap

https://link.springer.com/article/10.1007/s003550000060 : I have just re-implemented Dodgson using the method described here. And which looks more like what can be deduced from the very short description of Wikipedia. And which is in contradiction with the way of doing the first document above. Here it is said that 1 swap = 1 vote, which gives different results. Without being able to understand the mathematical proponents behind either approach, this way of doing it seems intuitively much more obvious to me.

I don't know who to believe anymore. But the only tests that fail are from the first document. The others are perfect, both in the result and in detail.

[julien-boudry]

I found that : https://www.maa.org/sites/default/files/pdf/cmj_ftp/CMJ/September%202010/3%20Articles/6%2009-229%20Ratliff/Dodgson_CMJ_Final.pdf

I will try to working on soon.

[janmotl]

Dodgson Quick winner looks like a reasonable approximation of Dodgson winner.

If a breaking change is an option, I propose to remove Dodgson from the library&web and replace it with Dodgson Quick to communicate that it is not Dodgson but merely an approximation of Dodgson method.

[julien-boudry]

In fact, the current functioning actually corresponds to the Tideman's approximation.

I can chose effectively :

1. Correcting it and add limit on number of candidate (like Kemeny-Young) and votes number.
2. Use the Dodgson Quick winner
3. Still using Tidemann's approximation

(in case 2 or 3 : change method name and update the doc)

[julien-boudry]

I try solution 2. Seem to be OK but not better for my example. It fail the same count of tests (6 fails/14) but not the same. But it is perfectly consistent with what was announced in the last documentation found.

https://travis-ci.org/julien-boudry/Condorcet/jobs/308188667 https://github.com/julien-boudry/Condorcet/blob/dev-1.3.x/Tests/lib/Algo/Methods/DodgsonTest.php

[julien-boudry]

Fixed in v1.3.4 -> https://github.com/julien-boudry/Condorcet/releases/tag/v1.3.4

Finally, I kept Tideman approximation but renamed it. And as Dodgson Quick as a different method. To be clear, "Dodgson" no longer answer to either of them anymore. This intentionally creates a small backward incompatible change.

I looking for upgrade www.condorcet.vote

[julien-boudry]

www.condorcet.vote has been updated. You just need to activate Dodgson Quick at creation time or election admin page.

Thanks for all.

[janmotl]

Thank you!