Talk:MARS voting

From electowiki
Revision as of 16:04, 27 February 2021 by Casimir (talk | contribs) (signature)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

This is the discussion page (the "Talk:" page) for the page named "MARS voting". Please use this page to discuss the topic described in the corresponding page in the main namespace (i.e. the "MARS voting" page here on electowiki), or visit Help:Talk to learn more about talk pages.

Proposed move to "User" space

Hi User:Casimir! Thanks for contributing to electowiki! Is the "MARS voting" method something devised yourself, or is this a method that others helped you with? If it's your method, I think we should move the description to "User:Casimir/MARS voting" until you're able to build broader support for the method. Would you mind if one of the administrators of electowiki did that for you? -- RobLa (talk) 08:56, 18 February 2021 (UTC)

It's something I devised in discussion with others. At first I wanted to create a user page, but then someone independently suggested to create an article here. For now I'm mostly indifferent if it is an article or user page. I also noticed that I published to early as there are still some aspects unfinished. --Casimir (talk) 21:01, 20 February 2021 (UTC)

Algorithm changes

Attn User:Casimir, the MARS application has been updated to reflect both the rename and to add a check for cycles. I'd like to keep this section for tracking consistency between the described algorithm and the program. --Ŝan (talk) 17:33, 23 February 2021 (UTC)

Tie handling

Ties complicate things; I suggest amending the algorithm to describe how they're handled.

There are three tie situations:

  1. There's a cycle, and there's a tie in the pure score (I'm not sure this can happen; I haven't found a sample data set for this yet).
  2. There's a tie in the adjusted score.
  3. There's a tie in both the adjust score as well as the pure score.

I suggest the following changes:

  • In the first case, this is a hard tie with no possible winner.
  • In the second case, determine the winner by the pure score.
  • In the third case, this is a hard tie with no possible winner.

It complicates the algorithm; I've updated the program code and added sample cases in the repository (`input-1*.csv`)

Here is an example for the first tied case.
Voters 11 11 10 1 score
A 10 8 9 1 289
B 9 10 8 0 289
C 8 9 10 0 287
If we ignore candidate C - which is what STAR would do - then A clearly wins by preference. So I think it's fair to say, in the case of a cycle tied by score, the tie is resolved by preference.
The second case is interesting as it can be anything from almost the same score and almost equal fractions in the population (almost case 3), to vastly different scores and preference that just happen to cancel out. Note that this isn't about picking the final winner, but one step with possibly more steps to follow.
Voters 1 1 1 1 1
A 1 1 1 0 0
B 0 0 0 4 4
Since B is the score winner, we start with B and then find the tie with A. As we just compared every candidate to B we could stop here (chose B), or check wether any candidate could beat A. This could either lead to a chain which eventually terminates, or a cycle in which we would choose B again. There could be a candidate C so that C>A and C>B. In order to find it, we have to choose A as the winner in the first round. So for consistency and precision I think it is better to assume the majority winner in a tie and do these extra counts to find the best winner. Therefor we go with the majority winner in both cases.
The third case would be a true tie. But if you give the chance of a tie in a voting method a value T from 0 (never) to 1 (always) then the chance of such a tie occurring it the chance of a tie in score times the chance of tie in a 1 on 1 match. T(MARS) = T(score) x T(1on1). Both of those are already small. Therefor ties like this would be extremely rare.--Casimir (talk) 08:46, 24 February 2021 (UTC)
Is the algorithm description missing a step, then? In the first example, why does A win by preference? Eliminating C still means A and B have the same unmodified score: 289. Is it because the cardinality of votes favors A (33 vs 32)? In your example -- B and C have the same cardinality with 32 votes each, so how do we know to drop C? We can't just drop the person with the lowest score, because they could still win with a modified score.
To back up a step, consider the following two cases:
# Voters A B C
4 5 3 0
4 0 3 5
Outcome: Modified score goes to B. Case 2:
# Voters A B C
4 5 2 0
4 0 2 5
Outcome: B doesn't have enough popularity to win, but A & C tie in total scores, so this is a hard tie.
I believe that you're saying there's another step or case in the tiebreaker determination: if two (leading) candidates have the same score, the one with the higher number of votes wins. If so, then the tiebreaker rules are:
  1. The winner is the one with the highest modified score (HMS, score+modifier); or
  2. If there's an HMS tie, then the winner is the leading candidate with the highest unmodified score (HUS, per MARS); or
  3. If there's an HUS tie, then the winner is the leading candidate with the highest cardinality (number of votes); or
  4. If there's a cardinality tie, then the election is a hard tie with no possible winner.
Does that sound right?
It feels like there's a step missing, though. Something like, if there's a cycle or tie, look at the score and drop the lowest candidate and iterate, like IRV. In the MARS algorithm, there is no candidate elimination step, so where would that go? --Ŝan (talk) 22:15, 24 February 2021 (UTC)
In the above example (ABC cycle, AB tie by score) the process is as follows: Sum up all unmodified scores and find the score winner. There are two score winners tied so we pick either of them (just ignore how for a moment). We pick A and then compare the other candidates to A. We find that C>A and then compare the candidates against C, find that B>C, again compare against B and find that A>B. So we discovered a cycle. In case of a cycle we pick the score winner, but here again A and B are tied. We ignore C because they are not the score winner. Just comparing A and B it is clear that B should win by preference over A.
So there two groups of ties which can be solved by preference and one which can not be solved:
  • Tied in a match against another candidate, or score in the first round. These are essentially the same.
  • Tied by score in the case we found a cycle.
  • True tie by score and preference.
Ties, except true ties, can be resolved by preference. So the the rule for ties just has to be "When there is any tie, pick the majority winner if possible." Unless I missed something. To restate your above list:
  1. The winner of a round is the one with the highest modified score (HMS, score+modifier, in the first round the modifier is 0 for all candidates); or
  2. If there's an HMS tie, then the winner is the leading tied candidate with the highest cardinality (number of votes); or
  3. If there's a cardinality tie, then the election is a hard tie with no possible winner.
For cycles:
  1. If there's a cycle, then the final winner is the leading candidate with the highest unmodified score (HUS); or
  2. If there's an HUS tie within the cycle, then the winner is the leading tied candidate with the highest cardinality (number of votes).--Casimir (talk) 16:04, 27 February 2021 (UTC)