[Experimental Schulze-STV Branch] Wrong test results from various methods with Explicit Ranking

[LiamM32]

After commit 1c46c1f, various test failures show that various methods are outputting the wrong results in explicit ranking mode when run from composer test. This is a very strange bug, as the changes that were made in this commit shouldn't be affecting these methods.

Methods affected, according to the test results, include Borda count, Instant Runoff, Two-round system, Minimax, and Ranked Pairs. CPO-STV instead has test errors.

There appears to be something preventing implicit ranking mode from being disabled when running tests. However, it seems to be working when I specify no implicit ranking in the console application. The tests for the methods pass when run individually, just not when using composer test.

[julien-boudry]

Really strange, but sure I will find a reason...

Your method generates errors, they are shown first in PHPUnit output (before tests failure), and perhaps errors prevent doing tests cleanup (and especially implicit mod), but shouldn't do that, so I do have not the entire reason yet.

Some tests run all available methods, including yours (without checking results, but that allowing crash detection). Tests conflicts if a crash occurs without cleanup can be more dangerous since #67, because some tests are less isolated.

[LiamM32]

I may try to find the cause of the errors. But Schulze-STV can be run from the console without any errors.

[julien-boudry]

I got it (nothing about test or implicit ranking finally):

Like in the CPO_STV class, you use the Vote::initCache() (l.22). it's a dangerous (but very efficient) performance optimization about caching getContextualRanking cache. And it's a static cache.

CPO STV clears the cache at the end of compute() method, you did not. But worse, if an error happens before the normal end, the static cache is never cleaned (currently it's the case).

If I comment on the cache init (l.22), the error from Schulze-STV of course is still here, but failures from other methods disappear.

[julien-boudry]

I may try to find the cause of the errors. But Schulze-STV can be run from the console without any errors.

Maybe the error does not happen with any input. Some of them also happen on getStats with some verbosity parameters.

[LiamM32]

CPO STV clears the cache at the end of compute() method, you did not.

Interesting. But even if I add Vote::clearCache() to the end of Schulze_STV::compute(), the errors and failures remain. Having neither of them results in no test failures, but the same test errors.

[LiamM32]

The errors appear to be related to the Combinations::getPossibleCountOfCombinations() function.

I used the debugger in PhpStorm to debug a run of Examples/Examples-with-html/A.Global_Example.php.

It looks like the problem may be that it sets the number of seats to 100, which means that all candidates have more than a quota of first preferences, so they are all part of the array $candidatesElectedFromFirstRound. $candidatesRemainingFromFirstRound is therefore empty and $numberOfCandidatesNeededToComplete is set to 95 by the time it reaches Combinations::getPossibleCountOfCombinations(). This is the case for both CPO_STV & Schulze_STV.

PhpStorm cannot calculate the value of Combinations::getPossibleCountOfCombinations(count: 0, length: 95) when the debugger is at this point in either class, so I figure that this would be the error. But in that case, I wonder why this error wasn't already happening with CPO_STV before I ever introduced Schulze_STV. CPO_STV has to do this function once with the same parameters as Schulze_STV. CPO_STV is run before Schulze_STV, so why doesn't CPO_STV get the same error?

I see two things that I can do here.

The first would be to prevent Schulze_STV from filling more seats than there are candidates. The number of seats it aims to fill would be set to the number of candidates, or the number of candidates minus one. I was surprised to find that CPO_STV doesn't already do that.

The second thing I can consider doing is to not use Combinations::getPossibleCountOfCombinations(), and write a new static function for factorials. I believe I understand what this (former) function does, but I'm not entirely sure the formula I wrote gets the correct number of combinations for Schulze STV. The Schulze paper says the total number of direct links is (C!)/(((M–1)!)∙((C–M–1)!)). I'm not sure if the following code is mathematically equivalent: Combinations::getPossibleCountOfCombinations( count: \count($this->candidatesRemainingFromFirstRound), length: $numberOfCandidatesNeededToComplete ) * $numberOfCandidatesNeededToComplete * (\count($this->candidatesRemainingFromFirstRound) - $numberOfCandidatesNeededToComplete)

[julien-boudry]

CPO STV clears the cache at the end of compute() method, you did not.

Interesting. But even if I add Vote::clearCache() to the end of Schulze_STV::compute(), the errors and failures remain. Having neither of them results in no test failures, but the same test errors.

Yes, because if an error occurs before the clearCache, the function is stopped before it and the static cache is not cleared before to passing to another method.

[julien-boudry]

The errors appear to be related to the Combinations::getPossibleCountOfCombinations() function.

I used the debugger in PhpStorm to debug a run of Examples/Examples-with-html/A.Global_Example.php.

It looks like the problem may be that it sets the number of seats to 100, which means that all candidates have more than a quota of first preferences, so they are all part of the array $candidatesElectedFromFirstRound. $candidatesRemainingFromFirstRound is therefore empty and $numberOfCandidatesNeededToComplete is set to 95 by the time it reaches Combinations::getPossibleCountOfCombinations(). This is the case for both CPO_STV & Schulze_STV.

PhpStorm cannot calculate the value of Combinations::getPossibleCountOfCombinations(count: 0, length: 95) when the debugger is at this point in either class, so I figure that this would be the error. But in that case, I wonder why this error wasn't already happening with CPO_STV before I ever introduced Schulze_STV. CPO_STV has to do this function once with the same parameters as Schulze_STV. CPO_STV is run before Schulze_STV, so why doesn't CPO_STV get the same error?

I see two things that I can do here.

Stop! You are going too far ;-) Try to do your analysis iteratively, one by one. The first error to solve is much simpler and can impact the following.

The first one, is a language error :

• The property $this->candidatesRemainingFromFirstRound is undeclared, it's deprecated in this actual version of PHP and will be an error in the next one. It's also dangerous because you can try to read it before she is existing, and can lead to dangerous behavior. PHPstorm must point out this error directly without debugging (my IDE does,).

The second one is a Condorcet Internal API error:

That is the "Parameters invalid" error you got. Whatever the formula, it doesn't make sense to ask him what you do. ;-)

So you must fix logic starting at l.39.

I was surprised to find that CPO_STV doesn't already do that.

Implementation of CPO Stv just provides a result with fewer candidates than seats, if candidate's count is less than the number of seats. Feel that is more elegant and perfectly logical. _(the test)_ But don't touch the quotas, because in STV a different quotas lead to different result, and we don't want to silently manipulate the quotas.

[LiamM32]

• The property $this->candidatesRemainingFromFirstRound is undeclared, it's deprecated in this actual version of PHP and will be an error in the next one.

It looks like this is the property I added. It was meant to be a renaming of $this->candidatesEliminatedFromFIrstRound, as I think the name of that one is misleading. But I forgot to rename the declarations.

[LiamM32]

But don't touch the quotas, because in STV a different quotas lead to different result, and we don't want to silently manipulate the quotas.

Well, the way CPO_STV::compute() is currently written, the if statement on line 91 causes it to skip most of the process if there are more seats to fill than candidates available. In these situations, the process isn't really CPO-STV, so this isn't a matter of correct vs incorrect results; the method is already effectively skipped if it can't be done properly.

Despite this, I copied many of the lines after this one to Schulze-STV::compute(). There is now only one error when running tests, and zero test failures.

[LiamM32]

I should add that running Schulze-STV from the terminal now gets new errors.

[julien-boudry]

Hi @LiamM32,

I try to have a new and updated look. I just ran the regular test (all of them), from the last commit. Now I get:

There was 1 error:

1) CondorcetPHP\Condorcet\Tests\DavidHillFormatTest::testBugDavidHillRandomOrderAndStatsRound
TypeError: array_intersect(): Argument #2 must be of type array, null given

/Users/julien/Code/Condorcet/src/Algo/Methods/STV/Schulze_STV.php:74
/Users/julien/Code/Condorcet/src/Algo/Method.php:77
/Users/julien/Code/Condorcet/src/ElectionProcess/ResultsProcess.php:84
/Users/julien/Code/Condorcet/Tests/src/Tools/Converters/DavidHillFormatTest.php:358

ERRORS!
Tests: 426, Assertions: 1630, Errors: 1, Warnings: 1.
Script phpunit handling the test event returned with error code 2

Are you at the same level?

[LiamM32]

Are you at the same level?

No. I no longer get that test failure. I don't remember what I did to solve it, but I think it was before the commit that I just pushed. The only test failure I get now is the test I just added; Schulze_StvTest. The goal now is to get Schulze STV to determine the correct results.

[LiamM32]

The latest commit has a good number of changes. Schulze_STV now outputs the correct result in most cases. But it gets the wrong result for Tideman A22.

There is also a change to SingleTransferableVote to better handle equal rankings. But I made it so that it still passes existing tests.