[EM] Semiproportional methods 2: derandomizing the obvious

[Kristofer Munsterhjelm]

Here's another method that alas, didn't entirely work. Consider the
following "obvious" random approach to proportionality:

- If the council is full, stop. Otherwise:
- Choose a non-blank ballot at random.
- Elect the candidate listed first on that ballot. If there's a tie for
first, choose one at random.
- Eliminate that candidate from every ballot and loop to the beginning.

Since it's random, it's subject to the luck of the draw. So take the
mode (or do the process above many many times and choose the council
that appears most often). The result is monotone: raising A can only get
him elected sooner.

In what sense is the determinized method proportional? If everybody
votes closed party list style, then the process is equivalent to drawing
from a multinomial distribution as many times as there are seats. From
theorem 2 of White et al (http://dx.doi.org/10.1016/j.spl.2009.09.013),
one can start with a council of zero people from every party (which is a
"mode" of the multinomial with n=0) and run the D'Hondt algorithm, and
at every step still be in a mode of the multinomial with that many
seats. So the D'Hondt apportionment is a mode of the multinomial. Thus
(up to tiebreaks), the process above finds the D'Hondt apportionment if
everybody votes closed party list style.

On the other hand, if there's just one seat, then the system reduces to
Plurality. Plurality fails the mutual majority criterion, and thus the
derandomized method fails the DPC. So it's not proportional in general.

I'm finding it a bit difficult to determine just "how proportional" it
is. It seems to depend on both the size of the factions, and on the
number of seats. (Obviously, if there are as many seats as there are
candidates, and each candidate is ranked by at least one voter, then
everybody gets elected.)

I also suspect the disproportionality is in some way analogous to the
disproportionality of Plurality itself. If so, some kind of pairwise
comparison might rescue the method, like Condorcet does Plurality. Of a
related note, using the G-test or chi-square test as an objective
function instead of setting the mode directly results in a Sainte-Laguë
reduction, not a D'Hondt one; and those tests are based on
likelihood-ratio tests, which compare two situations. So perhaps there's
something that can be done by combining Condorcet logic (pairwise
comparisons) and multinomial tests to get something that, in party list
situations, reduce to Sainte-Laguë. But perhaps I'm just reinventing my
own "Statistical Condorcet" of 2014 :-)

---

In any case, the derandomized method above can be directly calculated by
observing it has the Markov property. The probability of some candidate
being elected depends only on the candidates who have already been
elected: the probability of candidate A being chosen is proportional to
the number of (non-blank) ballots that rank A first after every
candidate who's already elected has been eliminated.

Each council cX then has a score equal to p(X_s=cX|X_0={}), and the
winning council is the one that maximizes this probability score. In
theory, one can find the score for every council by dynamic programming
(or even more brute-force, by taking powers of the Markov matrix). In
practice, that doesn't scale well at all for large councils.

(A consequence of the Markov property is that, when electing a council
of s candidates, the method only looks at the first s ranked candidates
on the ballot.)



To take the example from the Droop Judgment post:

58: A>C>B>D
18: B>C>A>D
21: C>A>B>D
32: D>B>A>C

two to elect.

p(X_1={A}|X_0={}) = 58/129 = 0.45
p(X_1={B}|X_0={}) = 18/129 = 0.14
p(X_1={C}|X_0={}) = 21/129 = 0.16
p(X_1={D}|X_0={}) = 32/129 = 0.25

p(X_2={AB}|X_1={A}) = 18/129 = 0.14
p(X_2={AC}|X_1={A}) = 79/129 = 0.61
p(X_2={AD}|X_1={A}) = 32/129 = 0.25
(everything else is zero)

p(X_2={AB}|X_1={B}) = 58/129 = 0.45
p(X_2={BC}|X_1={B}) = 31/129 = 0.30
p(X_2={BD}|X_1={B}) = 32/129 = 0.25

p(X_2={AC}|X_1={C}) = 79/129 = 0.61
p(X_2={BC}|X_1={C}) = 18/129 = 0.14
p(X_2={CD}|X_1={C}) = 32/129 = 0.25

p(X_2={AD}|X_1={D}) = 58/129 = 0.45
p(X_2={BD}|X_1={D}) = 50/129 = 0.39
p(X_2={CD}|X_1={D}) = 21/129 = 0.16

Summing everything up:

p(X_2={AB}|X_0={}) = first elect B then A (0.14 * 0.45) + first elect A
then B (0.45 * 0.14) = 0.1260
p(X_2={AC}|X_0={}) = first C then A (0.16 * 0.61) + first A then C (0.45
* 0.61) = 0.3721
p(X_2={AD}|X_0={}) = first D then A (0.25 * 0.45) + first A then D (0.45
* 0.25) = 0.2250
p(X_2={BC}|X_0={}) = first C then B (0.16 * 0.14) + first B then C (0.14
* 0.30) = 0.0644
p(X_2={BD}|X_0={}) = first D then B (0.25 * 0.39) + first B then D (0.14
* 0.25) = 0.1325
p(X_2={CD}|X_0={}) = first D then C (0.25 * 0.16) + first C then B (0.16
* 0.25) = 0.0800.

And the winning council is AC, which in this particular example respects
the Droop constraints (two candidates should come from {ABC} and one
should be A).