Kotze-Pereira transformation: Difference between revisions
→Notes: Fix outdated links for SimDemocracy
Psephomancy (talk | contribs) (→Further Reading: link titles) |
(→Notes: Fix outdated links for SimDemocracy) |
||
| (11 intermediate revisions by 5 users not shown) | |||
Line 2:
[[File:Kotze-Pereira.png|thumb|Visual representation of the KP-Tansform]]
The '''Kotze-Pereira transformation''' ('''KP transform''') converts scored ballots into Approval ballots, which allows any Approval PR method to be run on scored ballots. Because the score winner will always have the most approvals after the transformation, a PR method that elects the approval winner in the single-winner case will also elect the score winner in the single-winner case when converted to a score method using the transformation. Score methods using this transformation are also generally satisfy [[Scale invariance]] (multiplying all score by a constant leaves the result unaffected), except when the change in score causes differences in surplus handling due to quotas being met or not met. The transformation was independently invented by Kotze in 2011<ref>{{cite web |url=https://www.revleft.space/vb/threads/143429-Voting-with-ratings?s=f9288911a893930199498f370d9e4825&p=2030744#post2030744 |date=2011-02-23 |access-date=2020-02-10 |title=Voting with ratings|author=Kotze}}</ref> and [[Toby Pereira]] in 2015.<ref>https://groups.google.com/forum/#!msg/electionscience/BURkyIxZaBM/GdAcH2z7XkEJ</ref> It was named by [[Forest Simmons]] in 2015.<ref>http://election-methods.5485.n7.nabble.com/EM-A-graphical-description-of-Toby-Pereira-s-Transformation-of-Range-to-Approval-style-ballots-tp33047p33051.html</ref>
==Explanation==
To avoid having fractional approval ballots, some suggest that the KP transform should be done in such a way that one voter's score ballot always produces the smallest number of approval ballots such that they all are integer amounts; with the above example, this would mean multiplying the number of Approval ballots in each set by 5, yielding 2 ABC, 1 AB, and 2 A Approval ballots.
==The formal definition
{{definition|
Line 25 ⟶ 26:
3×(1,1,1) + 2×(1,1,0) + 4×(1,0,0).
Note that the Approval ballots yielded by the KP transform can be converted into ranked ballots by considering all approved candidates on a ballot as ranked co-1st, and all disapproved candidates as ranked co-equal last. With the above example of 0.4 ABC, 0.2 AB, and 0.4 A Approval ballots, this would converted into 0.4 A=B=C, 0.2 A=B(>C), and 0.4 A(>B=C) ranked ballots. This allows ranked PR methods to be done on rated ballots.
==Whole Ballot formulation==
In the whole ballot formulation there is never any fractional approval ballots. All score ballots are turned into the same number of whole approval ballots. The number of ballots is the same as the maximum score.
===Example Ballot===
An illustrative ballot for a max score 5 system is.
A:1 B:3 C:4 D:0
The KP-Transform turns this into 5 approval ballots.
{| class="wikitable"
|-
! Ballot !! A !! B !! C !! D
|-
| 1 || 1 || 1 || 1 || 0
|-
| 2 || 0 || 1 || 1 || 0
|-
| 3 || 0 || 1 || 1 || 0
|-
| 4 || 0 || 0 || 1 || 0
|-
| 5 || 0 || 0 || 0 || 0
|}
===Python Implementation===
The whole ballot formulation is particularly simple computationally. Given a Pandas dataframe '''S''' with columns representing candidates and rows representing voters the entries would encode the score of all the ballots. For a max score of '''K''' and an output set of approval ballots '''A'''.
<source lang="python">
import pandas as pd
import numpy as np
groups = []
for threshold in range(K):
groups.append(np.where(S.values > threshold, 1, 0))
A = pd.DataFrame(np.concatenate(groups), columns=S.columns)
</source>
==Scale Invariance example for RRV==
[[Reweighted Range Voting]] is one example of a method where the Kotze-Pereira Transformation will provide [[Scale invariance]]. This example will use Jefferson RRV because it's marginally easier to work with, but it's basically the same with any divisors.
Let's say we have 5 candidates to elect and there are multiple A and B candidates, and we have the following approval ballots.
200 voters: A
100 voters: B
In this case A would win 3, B would win 1 out of the first 4, and there would be a tie for the final seat. After the initial 4 have been elected, the weighted approvals for A would be 200/4 = 50, and for B it would be 100/2 = 50. So a tie. But now let's move onto score voting (out of 10)
200 voters: A1=10, A2=10, A3=9, A4=9
100 voters: B1=10, B2=9
A1, A2, and B1 would be elected as the first three. This gives us the proportional 2:1 ratio and this is the same as approval currently (because they had max scores). The A votes are now worth 1/3, and the B votes worth 1/2. A3 would be the next elected. But because of the score of 9, there isn't a full deweighting. Each A vote would now be worth 1/(1 + 29/10) = 10/39 or about 0.256. Both A4 and B2 have been given a score of 9 by their voters. The total score for A4 is 200 x 0.9 x 10/39 = 46.15. For B2 it is 100 x 0.9 x 0.5 = 45. So A4 would be elected instead of there being a tie. OK, so it's only a tie being broken, but if there were 101 B voters, then B2 should win the final seat but 101 x 0.9 x 0.5 = 45.45, so it wouldn't be enough to take the final seat. The wrong candidate would win the final seat.
With KP, the initial ballots would be transformed to:
200 ballots: A1, A2
1800 ballots: A1, A2, A3, A4
100 ballots: B1
900 ballots: B1, B2
Imagine A1, A2, B1, A3 are already elected. The new weighted total approvals for A4 would be 1800 x 1/4 = 450. For B2 it would be 900 x 1/2 = 450. This is the exact tie we want. So [[Scale invariance]] is preserved.
== Notes ==
Using the "ranked KP transform" on Score ballots (converting them into Approval ballots which are then converted into ranked ballots, with approved candidates ranked 1st and all others last) and running this through [[Smith-efficient]] [[Condorcet methods]] yields a [[Smith set]] with only the candidates who originally had the most points i.e. the [[Score voting]] winner.
Something similar to the KP transform can be done using randomness: if a voter approves a candidate with a probability proportional to their utility from that candidate, then with probability approaching 1 with many voters, the candidate will have the same [[approval rating]] as they would if every voter had simply scored that candidate.
One way to visualize the KP transform is as follows: imagine that for each voter, 9 additional voters are added to the election, whose ballots are treated as "under the control of" that voter. If the voter decided to make 8 of the 10 ballots under their control approve their favorite candidate, while not doing anything with the remaining 2, then this would be equivalent to them giving that candidate an 8 out of 10 on a rated ballot. Thus, the KP transform helps with [[scale invariance]].
The KP transform often improves or at least doesn't worsen a voting method that it is applied to, but this isn't always the case. For example, [[SMV]] depends on being able to spend an entire ballot even if it didn't give full support to the winner.
The connection that the KP transform shows between Approval and Score ballots can most clearly be seen when the Score ballots are set to a scale of 0 to 1 (with in-between decimals allowed), because a voter who gives a middling score to a candidate is seen to be giving them a fractional approval.
The online community [https://www.reddit.com/r/SimDemocracy SimDemocracy] uses a form of KP-transform with SPAV (Jefferson), called "SPSV" ([[Sequential Proportional Score Voting]]) for its parliamentary elections<ref>{{cite web |url=https://www.reddit.com/r/SimDemocracy/wiki/pr_the_constitution_of_simdemocracy#wiki_article_28_-_appendix |access-date=2022-02-23 |title=The Constitution of r/SimDemocracy}}</ref>. A custom build voting tool is used to hold elections and requires a reddit account<ref>{{cite web |url=https://github.com/jonathanvdc/res-publica |title=Res Publica}}</ref>.
==Further Reading==
Line 33 ⟶ 120:
* [https://www.rangevoting.org/QualityMulti.html#pertrans Smith, Warren D. "Optimal proportional representation" multiwinner voting systems I: methods, algorithms, advantages, and inherent flaws (The "Kotze-Pereira transformation" converts psi voting into harmonic voting). Oct 2015.]
* [https://www.rangevoting.org/NonlinQuality.html#pt Smith, Warren D. "Optimal proportional representation" multiwinner voting systems II: The two classes and the "holy grail" (Kotze-Pereira transform). Nov 2015]
==References==
[[Category:Voting theory]]
<references />
| |||