Maximum Constrained Approval Bucklin

Maximum Constrained Approval Bucklin (MCAB) is a multiwinner method devised by Kristofer Munsterhjelm, based on Bucklin voting. It uses linear optimization to calculate candidate support by assuming earlier surplus transfers were maximally favorable to the candidate in question, and thus reduces the strategic impact of lowering or raising a winning candidate on a ballot.

MCAB works in multiple rounds, each of which sets an implicit approval cutoff for every ballot. The first round considers first preferences as approved, the second round considers first and second preferences, and so on. For each round, the method evaluates every remaining unelected candidate. The unelected candidate with the greatest support is elected if his support is greater than a Droop quota, and a round may elect more than one candidate.

To determine the support of a particular candidate X, MCAB uses a constraint mechanism when counts implicit approvals. To be Droop proportional, MCAB deweights voters who approve of elected candidates, after they're elected. Unlike BTV and STV, however, MCAB does not directly decide which voters are to be deweighted. Instead it adds a constraint to the next rounds that a Droop quota of voters preferring each elected candidate must be discarded. When counting the support for X in later rounds, it maximizes the possible support for X given those constraints. This is called making the case for X.

Determining which voters to eliminate to maximize the support of a candidate subject to earlier constraints is relatively simple to do by linear programming, but hard to do by hand; MCAB can't be counted entirely by hand.

What ended up as MCAB was initially proposed in 2017 and simplified later that year. The method detailed here has been further modified from the EM posts to resist Woodall free riding.

Determining the support for X

Let $r$ be the rank and round number, $n$ the number of candidates so far, and $c_{k}$ the kth elected candidate. Consider unranked candidates to be ranked equal below every explicitly ranked candidate, i.e. never approved in any round. The linear program for determining the support of candidate X as (n+1)th candidate is:

maximize: sum over all voters v: support[v][n+1]

subject to:
       for i = 1 ... n+1:
               (sum over all voters v: support[v][i]) > Droop quota (1)

       for all voters v,
               for i = 1 ... n+1:              (2)
                       support[v][i] >= 0      if voter v ranks c_i at or
                                               higher than rank r
                       support[v][i] = 0       otherwise

       for all voters v: (3)
               (sum over i = 1 ... n+1: support[v][i]) <= v's initial weight

where $c_{n+1}$ is provisionally defined as X for the purpose of determining X's support.

The three clauses do the following:

1. imposes the Droop constraint: that any elected candidate $c_{i}$ must have more than a Droop quota's worth of approvals according to the implicit approval cutoff for round r.
2. defines support: $c_{i}$'s support is the number of voters who rank $c_{i}$ at or above rank $r$.
3. defines each voter's budget: no voter can spread more support across the candidates than his ballot's initial weight. The initial weight is 1 per voter for ordinary elections, or some other value in case of a weighted vote.

If the linear program is infeasible, then there's no way for X to obtain support exceeding a Droop quota, and so X is disqualified from being elected in that round. Among the remaining candidates, the candidate with the greatest support is elected.

Procedure

With the linear programming for determining the support of X defined, the MCAB procedure is this:

1. Start with round = 1.
2. Mark every unelected candidate as qualified for the round.
3. For every unelected undisqualified candidate X:
   1. Solve the linear program to find X's support with r = round.
4. If every unelected candidate is disqualified by the linear program:
   1. If all ranks have been considered, the method is done.
   2. Otherwise, increment the round number and go to 2.
5. If not all candidates have zero support, elect the candidate with greatest support and go to 3.

As a shortcut, the procedure can be stopped once every seat has been filled, since every remaining candidate will be disqualified in every round from that point on.

Example

The vote management example from Wikipedia's article on Schulze STV, https://en.wikipedia.org/wiki/Schulze_STV#Scenario

Without vote management

The unmanaged ballot set is

• 12: A>B>C
• 38: A>C>B
• 13: C>A>B
• 27: B

The Droop quota for two seats is 30.

First round, r = 1

A has 50 votes and is elected. No other candidate passes the Droop quota, and as there are no equal ranks, no A-first surplus can contribute to getting anyone else elected, so the linear program will mark all as disqualified afterwards. The combined surplus of the A-first voters come out to 50-30=20, but we don't know which particular ballots will be eliminated.

Second round, r = 2

Making the case for B: The optimum assignment is to allocate 12 of the 20 remaining votes to A>B>C, and then eliminate 8 of the A>C>B ballots. This gives B a support score of 27 (from the B-first ballots) + 12 (from the A>B>C ballots) for a total of 39.

Making the case for C: The optimum assignment is to allocate all 20 remaining votes to A>C>B. This gives C a score of 20 + 13 (from the C>A ballots) = 33.

Both candidates have exceeded the Droop quota, but B has greater support, so B is elected. After this, technically speaking, C gets another shot.

Making the case for C, again: Of the 20 remaining votes from electing A, 3 of these must go to electing B, so that 27 + 3 >= 30. That leaves 30 for C, which is not enough to clear the Droop quota. So C is disqualified.

Now every remaining candidate (namely C) is disqualified and the procedure is over. The winners are A and B.

With vote management

The vote-managed ballot set is

• 12: A>B>C
• 26: A>C>B
• 25: C>A>B (now includes some dishonest A>C>B voters)
• 27: B

First round, r = 1

As above, A is elected and then everybody else is disqualified. The surplus is 8 (38 - 30).

Second round, r = 2

Making the case for B: The optimum assignment is to allocate all 8 surplus votes to A>B>C, and then eliminate 4 A>B>C ballots and every A>C>B ballot. Thus B's max support is 27 + 8 = 35.

Making the case for C: The optimum assignment is to allocate all 8 surplus votes to A>C>B and eliminate the remaining A>C>B ballots, as well as every A>B>C ballot. Doing so gives a support of 25 (from the C>A ballots) + 8 = 33.

Both candidates have exceeded the Droop quota, but B has greater support and so is elected.

The case for C again goes as above. Because two Droop quotas have been elected, there are not enough votes left to get anyone else above the Droop quota.

Since A and B were elected in both cases, the vote-management failed.

Criterion compliances

MCAB passes the following criteria:

• Droop proportionality criterion
• Invulnerability to Woodall free riding

MCAB fails the following criteria:

• Weak invulnerability to Hylland free riding
• Monotonicity

Weak invulnerability to Hylland free riding

Suppose B is elected in round p and then later, the method arrives at round q. A voter who votes B ahead of C will contribute to C's support when the method makes the case for C regardless of whether he voted B ahead or not, unless B would not have been elected in any earlier round without his support. In that respect, Hylland free riding has no impact on MCAB. However, suppose there is another voter who votes B ahead of D. When making the case for D, MCAB needs to allocate a Droop quota of votes towards B since B was elected earlier. The B>C voter makes himself available to cover B's deficit when MCAB makes the case for someone who is not C. Had he not voted for B, he would not be thus available, and perhaps MCAB would have needed to exclude the B>D voter instead, electing C instead of D. So while doing Hylland free riding is more risky than in BTV, it can still pay off, and thus MCAB fails weak invulnerability to Hylland free riding.

Example

Without vote management:

• 12: A>B>C>D
• 38: A>C>D>B
• 13: C>A>D>B
• 27: B

The first two ranks are the same as in the Schulze STV example, so A and B are elected.

With vote management:

• 12: A>B>C>D
• 22: A>C>D>B
• 29: C>D>A>B (dishonest A>C>D>B and C>A>D>B voters)
• 27: B

In the first round, A wins. In the second round, the optimal allocation when making the case for B is to remove 22 A>C ballots and 8 A>B ballots. B's score is thus 31. C's score is unchanged, so the free-riding pays off: C wins.

Monotonicity

Like BTV, MCAB fails the monotonicity criterion due to a lookahead problem. However, MCAB passes the two criteria above as long as the candidate to elect in a round is chosen (by some method) from the set of candidates with above Droop quota support for that round. Thus, it is possible that a variant that uses a yet unknown lookahead criterion instead of electing the candidate with the greatest support, could pass monotonicity.