Simple Voting Methods

Colin Champion, 13 Nov 2021/16 Mar 2023

procedure : other evaluations : results : software : index

This page describes an empirical comparison under simulated elections of more than 50 (mostly ordinal) voting methods. Sincere voting, tactical voting and strategic nomination are considered, and two distinct metrics are presented. The results favour minimax, which is the much the simplest of the competitive methods, and therefore the most recommendable.

The software is provided, and is written in an extensible way so that other users can add voting methods of interest to them with minimal effort (see below).

Elections can be generated under one of three types of model:

GMM (default): voters and candidates are drawn from the same mixture of 3 gaussian components.
Single Gaussian: This is provided for compatibility with other evaluations.
Jury model: This is Condorcet’s model under which the Borda count is almost optimal.

The spatial models can be generated in spaces of any dimension. My results concentrate on 2-D models for compatibility with other authors, but I suspect that real elections are closer to single-dimensionality than they are usually given credit for.

There are two metrics for the spatial models. The first is the percentage of elections in which each method elects the rightful winner, defined as the candidate whose mean distance from voters is minimised. The second is mean Euclidean loss. If a voting method elects a candidate whose mean distance from voters is y, and if the minimum mean distance from voters over candidates is x, then the Euclidean loss is y–x. I consider losses to be intrinsically meaningless, but to provide a sounder basis for comparison than percentage correctness. The average distance from a voter to the best candidate in any election is around 1.7, so the differences in performance between competitive methods are very small.

Table 5 (measuring percentage correct for a particular form of tactical voting) is the sole case in which Condorcet+AV (ie. Condorcet/Hare) outperforms minimax, and when we look at the corresponding figures under Euclidean loss the results are reversed: evidently Condorcet/Hare makes fewer but larger mistakes than minimax, and is weaker overall.

The tables apply both metrics to sincere voting, to 4 forms of tactical voting, and to strategic nomination.

The metrics are essentially the same for jury models. The percentage correct is the percentage of elections in which the best candidate is chosen. Valence loss (i.e. loss of merit) is substituted for Euclidean loss.

My program produces some statistics concerning ties. Since these are not included in the main tables I summarise them here for the main condition (sincere voting under a GMM):

Condorcet cycles arise in only 0.7% of elections. I suspect that this is an upper bound on their frequency under sincere voting in real life.
I find it to be very rare for Copeland’s method to produce a unique winner when there are Condorcet cycles (<3% of the time).
Smith’s method never gives a unique winner in the presence of cycles.
When there is a Condorcet cycle, the minimax winner is also a Copeland winner with probability 11/12. Thus only about once in 2000 elections will a minimax winner not be a Copeland winner.

In the first 3 types of tactical voting, voters whose sincere first preference is for a certain candidate (c₀) place another candidate (c₁) at an insincere position in their lists. Type 1 (compromising) moves c₁ to the top; type 2 (false cycles) puts him second; and type 3 (burying) puts him at the bottom. The names (‘false cycles’) are for convenience and do not necessarily reflect anything about the mechanism by which the manipulation is effective.

The fourth form of tactical voting is list voting. Voters whose sincere first preference is for c₀ are sent a preprinted list telling them how to rank the candidates, and vote according to their instructions.

The number of candidates is reduced to 5 for tactical voting. Each of the 20 (c₀,c₁) pairs corresponds to an attempt at subversion for the first three forms, while there are 5×120 possible subversions to consider for the fourth. A subversion is considered to be successful if the winning candidate is closer to c₀ than the winner under sincere voting. The result attributed to each method is the worst amongst its sincere result and all successful subversions of the given type. (One could alternatively attribute to a method the result of whichever subversion was most favourable to the subverter: this might be a fairer measure, which would also be less pessimistic. The current metric seems almost to assume that the subverter is seeking to damage the electorate as much as to benefit himself.)

An alternative metric is sometimes used for assessing systems under tactical voting. It asks the question “In what percentage of trials does there exist a group of voters who all prefer another candidate to the sincere winner, and who can cause that candidate to win by changing their votes?” The answer is taken as a measure of strategic vulnerability and its converse is interpreted as ‘robustness to strategy’.

I do not consider this a suitable metric for 3 reasons:

It does not indicate how well a voting method works in the circumstances under consideration, but instead measures how much worse it performs than under sincere voting. Hence a coin toss is 100% robust (and outscores all genuine voting methods) because tactical voting doesn’t make it worse than sincere voting.
Voting methods recommended for their resistance to tactical voting sometimes make larger mistakes when they go wrong than methods based on sincere voting. If you don't take this into account, you can draw misleading conclusions.
Thirdly, consider a 3-candidate election using IRV. The central candidate is the Condorcet winner, but supporters of one of the non-central candidates realise that the opposed non-central candidate is likely to win owing to the operation of a centre squeeze, and therefore compromise on the central candidate. This is a case in which insincere voters can cause another candidate to win but is certainly not an additional fault in IRV; on the contrary, it's a mitigation of its weakness under sincere voting.

My own metric reports the number of errors under a tactical voting condition. This is the sum of errors which would have happened anyway (a small minority for Condorcet methods) and those induced by tactical voting.

Readers should be warned that the two sorts of error might be of unequal importance. Nonetheless my figures are readily interpretable. If method X outperforms method Y under sincere voting, and Y outperforms X under a tactical voting condition, then it is reasonable to conclude that the choice between X and Y should depend on the extent to which tactical voting is likely to take place. Under the more traditional metric this conclusion would be invalid. It might be that under all possible intensities of tactical voting X would give better results than Y, since the reported greater robustness of Y does not correspond to performance in any condition.

Strategic nomination is modelled by drawing candidates from a distribution which is displaced relative to the voter distribution. If the voter distribution is a GMM, then the candidates come from a single gaussian whose mean is an exaggerated version of the mean of one of the components of the voter mixture. Draw a line from the origin to the mean of the component; extend it by 0.5; the result is the mean of the candidate distribution.

If the voter distribution is a single Gaussian, then the candidates come from a similar Gaussian displaced by 1 along the x-axis.

My evaluation also contains results for a jury model (aka. valence model). Each candidate i has a valence v_i, and candidates are ranked by voter j in decreasing order of v_i – ε_i j. The valences are drawn from a standard Gaussian distribution and the noise terms ε_i j from a zero-mean Gaussian of standard deviation σ. The Borda count does best under this model with Warren D. Smith’s Sinkhorn method coming second.

A jury model has two components, valence and random noise. I don’t doubt that both are present in political preferences but I doubt that spatial models lose anything through their absence.

The addition of a valence component to a spatial model leaves the median voter theorem unaffected, so is unlikely by itself to change anything. It is the random component of a jury model which gives it its characteristic properties, but while I accept that there is a random element to voters’ behaviour, I doubt that it is large enough to have a significant effect when the number of voters is as large as a typical electorate.

Tactical voting is defined slightly differently for a jury model: an attempted subversion is considered to be successful only if it leads to the election of the candidate c₀ on whose behalf the tactical voters are acting. AV is pretty much best among methods in dealing with tactical voting under a jury model (Condorcet/AV hybrids may give a marginal improvement, but nothing to justify their added complexity).

The evaluation includes a few methods which aren’t purely ordinal. I have misgivings about their presence given that some degree of distortion is needed to accommodate them. I don’t wish to go much further in the direction of adding cardinal or semi-cardinal methods for fear of generating results which are seriously misleading.

mj: this is an idealised highest median method in which a voter’s rating of a candidate is minus the Euclidean distance between them. This is unrealistically favourable to Majority Judgment since it eliminates the requirement on voters to quantise their ratings, which they will do inconsistently. No attempt is made to apply tactical voting to mj.
asm: A voter’s approvals are assumed to be the top half of her rankings (rounded down). This might be either unduly favourable or unduly unfavourable to the method.
seq: Sequential majority voting. This is a poorly defined method in which candidates can be grouped into opposed sets in any number of ways under control of the agenda-setter, and in which there is no clear way for a voter to decide which set to prefer. I assume that a voter prefers the set containing his or her preferred candidate. Forms of tactical voting are available far beyond those possible for other methods (i.e. choosing the set which is most likely to lead to a satisfactory result in subsequent rounds), so I exclude this method from tactical voting evaluations.

Email me at colin.champion@routemaster.app if you have any comments, questions, criticisms, etc., or if you want help in using my software.

Several other evaluations have been performed under a spatial model. In all cases the voters are drawn from a multivariate Gaussian distribution.

Chamberlin and Cohen (1978). These authors measured the ‘Condorcet efficiencies’ of Coombs, Borda, Hare (=AV) and Plurality (=FPTP). Their most meaningful results are those in Table 5 for medium dispersion and 1000 voters, which are consistent with those presented here.

Warren D. Smith makes the criticism that Condorcet efficiency is “a measure intentionally contrived to cause Condorcet’s voting system to be best possible, and having, in my opinion, no particular value aside from that” (“Range voting”, 2000.)

I partly disagree. In the circumstances of C&C’s evaluation Condorcet methods should be almost 100% accurate by the Median Voter Theorem, so Condorcet efficiency is almost the same thing as accuracy. ‘Borda efficiency’ would not have the same significance.

It would presumably have been easy for C&C to have published accuracies as well as Condorcet efficiencies. Given their failure to do so we need to bring in our own prior assumptions to interpret their results. This defeats the purpose of an evaluation, which is to confirm or overturn prior beliefs. I therefore accept that it is a severe methodological flaw to have published Condorcet efficiencies without accuracies; but it is not one which prevents us from making use of their figures. If there was a surfeit of trustworthy alternatives, we could afford to disregard C&C’s work; but as things stand it is valuable confirmation of other results.

S. Merrill III (1984). Merrill performed an evaluation under a spatial metric showing the Borda Count to be more accurate than the Condorcet criterion. Smith suspects that “Merrill’s computer program had bugs” and I agree.

Tideman and Plassmann (2012). Completely unbelievable. Table 1 shows AV as 94.41% correct and Copeland 94.45% on effectively infinite voter populations.

Green-Armytage, Tideman and Cosman (2015). Software possibly exhibiting common mode failures with the preceding; shows AV as 94.45% correct and Minimax as 95.19%. Not credible.

Darlington (2016/2018). I believe these evaluations to be sound; however they have significant methodological drawbacks which I shall mention later. Only the earlier evaluation has been formally published.

Quinn (nd). (Unpublished.) This evaluation seems consistent with my own, Darlington’s, and C&C’s, but is rather vaguely presented. Quinn makes the (Python) software for his evaluation available. He has shortened the description of his evaluation since it first appeared.

Huang (2021). (Unpublished.) Huang’s evaluation (like Quinn’s) pays particular attention to cardinal methods (which I largely ignore). He does not provide much detail. Notice that there are only 51 voters in each of his simulated elections.

My main reservations about Darlington’s evaluations are these:

He is dependent on small sample sizes to prise apart results for different Condorcet methods (a common fault, really, with all evaluations using multivariate Gaussian voter distributions). It’s unreliable because differences in small samples may be affected by features (eg. ties in intermediate results) which vanish as the sample size increases; and the politically important elections have large electorates.
He makes no attempt to include tactical voting in his tests.
His metric is percentage correct with no mention of Euclidean loss. This is common with most other evaluations, but can sometimes be misleading.

My conclusion is that the majority of peer-reviewed evaluations are vitiated by software bugs, and that all the sound evaluations are liable to methodological objections. It is with a view to addressing these problems that I performed my own; but it has no formal status, and lacks the authority of the peer-reviewed evaluations listed above.

The position is unfortunate. The topic is important and readers will look to the academic literature for the gold standard in accuracy; and they will be let down. It is hard to see how this can be put right since journals are unlikely to welcome further evaluations.

At the same time, even informal comparisons (such as Darlington’s second) make no attempt to explain the relationship between their results and earlier work (with the praiseworthy exception of Smith). It’s hard to imagine that it didn’t occur to Darlington that the difference between his own figures and Tideman’s needed to be discussed.

sincere voting : compromising : false cycle : burying : list voting : strategic nomination : jury model

The best result in each table has a solid underline; all other results which are at least as good as minimax have broken underlines, while minimax is indicated by colour. There are various interesting points of detail, but overall the striking feature is minimax’s consistent performance. Smith+BordaR, Smith+MinimaxR and Smith+MinimaxF run it close, but none is likely to recommend itself for practical use.

For a spatial model:

The number of voters is always 30 001.
The number of candidates is 9 for sincere voting and strategic nomination, and 5 for the tactical voting conditions.
The number of trials is 1 million (except that mj is estimated from just 20000 trials).

For a jury model there are 5 candidates and 101 voters. The noise standard deviation is 2.

Some algorithms have more than one name (see below).

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
11.1027 30.9728 45.4295 41.4320 50.6048 57.0026 84.1508 88.9993 70.6870 81.8214 85.6950 53.0478 90.1082
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
93.3844 93.6063 93.6547 93.5641 93.6363 93.6424 93.7199 93.7514 93.7502 93.7344 93.7344 93.5845 93.6520 93.5395 94.0696
condorcet+ random fptp dblv conting borda av
93.4574 93.5176 93.5837 93.5469 93.7325 93.5647
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
93.6238 93.6249 93.6684 93.6608 93.5700 93.7353 93.7430 93.6168 93.5700 93.7475 93.7134
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
93.5845 93.5978 93.6667 93.6351 93.5405 93.7350 93.7925 93.5870 93.5386 93.7515 93.7515

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
55.9869 20.6310 8.6569 10.9055 8.0359 5.4350 0.7980 0.4407 2.1261 1.0969 0.9114 5.4176 0.3846
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 0.1686 0.1620 0.1710 0.1639 0.1616 0.1558 0.1525 0.1526 0.1543 0.1545 0.1726 0.1614 0.1737 0.1394
condorcet+ random fptp dblv conting borda av
0.4731 0.3100 0.2055 0.2079 0.1536 0.1844
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
0.1639 0.1643 0.1609 0.1611 0.1681 0.1531 0.1554 0.1642 0.1681 0.1530 0.1570
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
0.1726 0.1710 0.1637 0.1662 0.1746 0.1531 0.1498 0.1700 0.1745 0.1525 0.1525

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
20.0007 31.7854 34.1326 – 52.9314 38.0291 50.4100 47.6676 41.9468 45.6188 – 53.0537 73.2856
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 72.3275 72.8870 72.8993 72.7738 72.9724 73.1047 73.2373 73.2515 73.1713 73.1781 70.6356 72.6303 72.8885 –
condorcet+ random fptp dblv conting borda av
– 72.8303 67.9920 72.8870 73.0362 72.8718
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 72.8818 72.8251 73.0436 72.9057 73.1144 73.2339 72.8911 72.9057 73.2587 73.1024
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 72.8338 72.8049 68.2522 72.9039 73.0396 73.3728 72.8718 72.8830 73.2375 73.2375

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
49.2849 31.4556 11.7850 – 9.7913 16.2084 7.1877 8.0482 9.6846 8.5198 – 8.6312 3.6829
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 3.7988 3.9858 3.9240 4.1157 3.7571 3.7320 3.5987 3.6017 3.6740 3.6676 4.3030 3.9593 3.9324 –
condorcet+ random fptp dblv conting borda av
– 4.1621 4.7999 4.0501 3.6490 4.0501
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 4.0136 3.9889 3.7698 3.8986 3.6564 3.7493 3.9984 3.8985 3.6076 3.7642
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 4.1219 4.0597 4.7028 3.9479 3.6497 3.5689 4.0492 3.9472 3.5993 3.5993

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
20.0007 57.1667 34.1326 – 69.9718 60.7791 54.2973 55.3429 41.7017 50.9666 – 64.7179 57.8750
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 55.7304 64.0262 61.7371 51.2043 60.0140 61.9014 61.6246 61.7949 61.3333 61.2774 54.8351 53.7411 60.7377 –
condorcet+ random fptp dblv conting borda av
– 50.3920 63.3105 61.8709 64.3308 61.7997
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 58.3927 55.5303 61.1222 62.1022 64.6780 61.7240 63.8664 62.1030 62.3648 62.8929
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 50.4211 48.2041 63.3191 59.2474 64.3255 59.9985 61.7963 60.6458 61.4848 61.4848

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
49.2849 9.9799 11.7850 – 4.1735 5.1672 4.5939 4.0296 9.0881 5.6105 – 4.5262 4.3811
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 6.5879 3.9128 3.9760 5.9088 3.8972 3.3754 3.3970 3.3126 3.4618 3.4688 7.0896 5.7117 4.1980 –
condorcet+ random fptp dblv conting borda av
– 7.9833 4.5206 4.4025 3.0416 3.9572
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 4.2750 4.6456 4.5969 3.7699 2.9712 3.4480 3.4048 3.7697 3.2246 3.2405
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 7.3540 7.6431 4.5147 4.9981 3.0422 3.5175 3.9583 4.2133 3.4104 3.4104

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
20.0007 57.1667 45.7366 – 69.9718 54.8385 34.7185 39.1331 50.9582 31.5745 – 66.5901 56.7348
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 58.9464 66.1568 62.6120 56.2016 59.4338 56.9272 63.6521 62.6556 61.4459 61.4618 61.8846 54.8505 60.7487 –
condorcet+ random fptp dblv conting borda av
– 58.7237 57.1438 64.8663 53.8353 63.2675
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 52.9623 47.4037 55.6170 48.6370 52.3748 50.1771 52.6027 48.6373 60.7338 50.5075
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 59.3491 54.0138 57.1484 61.5081 53.8484 61.7570 63.2740 61.0234 63.6560 63.6560

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
49.2849 9.9799 7.4890 – 4.1735 5.8925 8.4300 7.0227 5.8703 9.4913 – 4.2011 4.5438
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 5.0502 3.1944 3.4266 4.3162 3.5012 3.8407 2.8221 2.9548 3.0429 3.0780 4.9972 4.7644 3.6635 –
condorcet+ random fptp dblv conting borda av
– 4.8002 4.6865 3.3224 4.6156 3.3705
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 5.2926 6.0095 4.8831 5.8268 4.9217 5.4997 5.0971 5.8267 3.3317 5.4607
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 4.2941 4.9628 4.6814 3.7556 4.6109 3.3592 3.3669 3.6593 2.8205 2.8205

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
20.0007 31.7854 34.1326 – 52.9314 26.9207 14.3244 16.2099 40.2093 11.1621 – 53.0512 49.5312
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 52.0154 56.8540 55.4050 45.1275 53.9374 50.5391 56.4355 54.5434 55.0842 55.0406 50.7875 47.5879 54.3975 –
condorcet+ random fptp dblv conting borda av
– 41.4706 48.1860 56.3880 37.5771 55.3957
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 42.3196 41.1952 45.3404 44.9307 36.6265 45.7497 45.5212 44.9930 50.7827 47.2916
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 42.4014 39.8693 47.9396 51.0315 37.6059 45.3390 55.3936 54.3936 56.3636 56.3636

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
49.2849 31.4556 12.9534 – 9.7923 22.5884 19.5541 19.8753 10.3992 21.9441 – 8.6254 9.3379
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 9.0388 8.2970 7.7639 11.6416 8.3166 8.2215 6.7313 6.8754 7.1143 7.2863 11.1395 8.9986 7.9952 –
condorcet+ random fptp dblv conting borda av
– 19.2736 8.9996 8.3298 11.4254 7.7749
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 10.5817 10.6919 9.2444 9.4903 11.0301 8.8241 9.2890 9.4464 7.7144 8.6876
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
– 15.2300 15.5754 9.0347 9.6432 11.3539 8.9603 7.7765 8.0107 6.6932 6.6932

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
11.1246 59.5463 69.6977 66.7128 74.2428 71.9183 75.0801 84.4757 83.0685 67.0086 89.8950 75.0478 93.1177
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
95.3054 95.3786 95.3691 95.3674 95.3969 95.3833 95.4125 95.4181 95.4181 95.4162 95.4164 95.3734 95.3784 95.3492 95.5281
condorcet+ random fptp dblv conting borda av
95.3277 95.3828 95.3934 95.3727 95.3819 95.3703
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
95.3813 95.4054 95.3952 95.4068 95.3611 95.3849 95.4276 95.3881 95.3611 95.4179 95.4126
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
95.3734 95.4013 95.3945 95.4023 95.3514 95.3824 95.4360 95.3770 95.3493 95.4181 95.4181

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
67.0990 7.0665 3.0617 4.2268 2.8424 2.7293 2.6543 1.2453 0.8162 4.6613 0.5603 2.1323 0.2353
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 0.1005 0.1015 0.1015 0.0993 0.0994 0.0977 0.0974 0.0974 0.0976 0.0976 0.1012 0.1001 0.1027 0.0938
condorcet+ random fptp dblv conting borda av
0.2016 0.1107 0.1016 0.1051 0.1005 0.1042
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
0.1001 0.0984 0.0992 0.0983 0.1013 0.1000 0.0974 0.0999 0.1013 0.0975 0.0980
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
0.1012 0.0988 0.0993 0.0986 0.1026 0.1003 0.0967 0.1012 0.1028 0.0974 0.0974

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
20.3591 83.1750 83.9951 71.0137 84.6358 85.3840 86.1016 86.1314 84.0657 86.0711 84.7412 84.6873 84.7317
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
84.2884 84.7671 84.8684 84.7847 84.8802 84.7928 84.9151 84.9060 84.9117 84.9092 84.9006 84.7385 84.8786 84.7852 85.7925
condorcet+ random fptp dblv conting borda av
84.5885 84.8953 84.9132 84.8100 85.0305 84.7860
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
84.7770 84.9118 84.8776 84.9254 84.7986 85.0294 84.9385 84.8054 84.8015 84.9131 84.8905
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
84.7385 84.8988 84.8845 84.9147 84.7908 85.0304 84.9781 84.7860 84.7862 84.9061 84.9061

random fptp dblv seq conting nauru borda sbc2 bucklin sinkhorn mj av coombs
118.4504 4.1748 3.7243 12.9632 3.4531 3.1125 2.7934 2.7831 3.6855 2.8073 3.3853 3.4237 3.4022
clower knockout spe benham btr-irv baldwin nanson minimax minisum rp river schulze asm tideman cupper
– 3.4005 3.3382 3.3756 3.3293 3.3676 3.3062 3.3099 3.3070 3.3106 3.3140 3.4146 3.3278 3.3755 3.0712
condorcet+ random fptp dblv conting borda av
4.0028 3.3220 3.3098 3.3660 3.2501 3.3752
llull+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
3.3822 3.3114 3.3276 3.3026 3.3670 3.2511 3.2946 3.3635 3.3659 3.3065 3.3181
smith+ randomr fptpf fptpr dblvf contingr bordaf bordar avf avr minimaxf minimaxr
3.4146 3.3193 3.3274 3.3089 3.3745 3.2501 3.2753 3.3752 3.3751 3.3096 3.3096

dblv: The ‘double vote’ (Nanson, 1882). A candidate’s score is the sum of his first and second preference votes.

seq: ‘sequential voting’, a series of rounds, in each of which the candidates are split randomly into two sets and voters choose between them, voting for whichever set contains their preferred candidate.

conting: ‘contingent voting’, whose winner is the voters’ pairwise preference between the two candidates with most first-place preferences. This is commonly implemented in two rounds.

sbc₂: the spatial Borda count, a positional method similar to the standard Borda count with weights optimised for circular bivariate Gaussian voter distributions.

spe: Sequential pairwise elimination. This is Llull’s knockout with a pre-ranking. Sort the candidates on their number of first preferences, and then perform the knockout. The first round opposes the two candidates with fewest first-place preferences; and so forth.

clower, cupper: These are the lower and upper bounds of Condorcet methods, both of which elect the Condorcet winner when one exists, while clower is always wrong in other cases and cupper is always right.

Llull’s knockout: Voters choose between the last two candidates, F and G, head to head, then between the winner and E, and so forth. The survivor is elected.

minisum: Suppose that 10 more voters prefer A to B than prefer B to A. Then B has a defeat margin of 10 to A, and A has no defeat margin at all (or a defeat margin of 0) to B. Elect the candidate whose sum of defeat margins is least. This is Tideman’s ‘Simplified Dodgson Rule’ (‘Collective Decisions and Voting’, 2006). It would be better to look at the margin by which a candidate falls short of victory, which is one greater than his defeat margin. I shall try to do this in the next update.

tiebreaks: If Copeland’s method has a full Borda tiebreak, then a Borda ranking is computed on the entire field, and the winner is the Copeland winner who comes highest in it. A restricted Borda tiebreak is computed by applying the Borda count to the Copeland tie set – that is, ballots are compressed by squeezing out candidates not belonging to the set, and Borda’s method applied.

X+Yf is sometimes written ‘X,Y’ and X+Yr ‘X//Y’.

fptp = plurality
av = irv = rcv = hare = ware
condorcet+av = condorcet/hare
llull = copeland
condorcdet+borda = black
llull+borda = Dasgupta/Maskin (not clear whether this is bordar or bordaf)
smith+avf = woodall
smith+avr = smith/irv
X+Yf = X,Y and X+Yr = X//Y

condorcet.c : ranelection.c : simplemethods.c : rankedpairs.c : condorcet.h : condorcetformat : revisions history : to do

Clicking on the following link will download the software as a tar file. Put it in a safe directory and extract the files (tar -xf condorcet.tar). The software is free to use and modify under GPL 3.0.

condorcet.c simplemethods.c rankedpairs.c ranelection.c condorcet.h condorcetformat.c
utilities: memory.h ranf.c random.h radixsort.c radixsort.h

Compile under g++:

g++ -O -g -o condorcet condorcet.c simplemethods.c rankedpairs.c ranelection.c ranf.c radixsort.c

This creates an executable ‘condorcet’. And

g++ -O -g -o condorcetformat condorcetformat.c

The call is:

condorcet dim ncandidates nvoters ntrials options

where dim is the dimension of the space and the options are character strings separated by ‘+’ signs. The legal options are:

Tactical voting: Four models of tactical voting are permitted: compromising, false cycles, burying and list voting. Each of these is recognised as an option whose first 3 characters are respectively com, cyc, bur , and lis.
Optional voting methods: most voting methods known to condorcet are automatically included, but a few are omitted by default and need to be requested individually, namely: av, rp (Ranked pairs), mj, coombs, sbc2, and sinkhorn. Note that you do not need to specify av if you need it as a tie-break/cycle-breaker since it will always be invoked for elections giving rise to a Condorcet cycle.
Diagnostics: the option ‘diag:’ followed by the name of a method asks condorcet to produce diagnostic output for at most 100 elections in which tactical voting causes the method to produce an undesiarable result. This is not available for tie-breaks/cycle-breakers, except that it is available for Smith extensions (namely ‘q&dc’ and ‘tideman’). An example would be ‘diag:borda’.
‘gaussian’: (or ‘gauss’:)this keyword requests condorcet to generate elections from a single tapering Gaussian rather than a GMM. The taper factor qscl may be provided, eg. by specifying ‘gaussian:0.5’ to get a taper factor of ½. If no value is provided, a taper factor of 1 is used, corresponding to a circular Gaussian. The first dimension of the Gaussian has σ = 1, the second has σ = qscl, the third σ = qscl², etc.
‘offset’: this keyword requests condorcet to generate candidates from a distribution which is somewhat offset relative to the distribution of voters as previously described (see strategic nomination above).
‘truncm’: imposes mandatory truncation. You may specify the truncation level after a colon, eg. “truncm:4”. The default (if truncation is requested but no level is specified) is to truncate to 3 candidates. This and the following truncation options are mutually exclusive.
‘truncc’: imposes candidate-specific truncation. The m candidates have associated truncation levels which are a random permutation of the numbers 1...m. A ballot is truncated to the level corresponding to its first candidate.
‘trunca’: imposes approval truncation. Each voter truncates at the largest gap between his or her cardinal rankings.
‘trunci’: imposes ignorance truncation. It must be followed by two real parameters, r and s separated by colons, eg. ‘trunci:3:1.5’. Each candidate has a prominence – i.e. probability of being recognised by an arbitrary voter – drawn (separately for each election) from a Beta(r,s) distribution. Voters rank the candidates they recognise in order of proximity, truncating after the last candidate they recognise.
‘jury’: requests a jury rather than a spatial model. You may specify a noise sd. after a colon, eg. “jury:2”. This option is incompatible with tactical voting and automatically activates all optional voting methods. dim is ignored for jury models.

The following is a fairly maximal call:

condorcet 2 5 30001 300000 cyc+av+coombs+diag:av

condorcet is written as an extensible program allowing you to add voting methods without changing any existing code. You provide a C/C++ function to apply the method and notify its existence through a standard call; you compile your new method in with the existing code base; and then you run condorcet as before. You will need to include condorcet.h in your code.

Your code for a voting method receives the ballots (and possibly additional information) as input and should return the winning candidate. The normal prototype is one of the following:

int newmethod(bitem **bal,int *count,int nbal,int m) ; 
int newmethod(int **bitem,int *count,int nbal,int m,int **r) ;
int newmethod(int **bitem,int *count,int nbal,int m,double **p) ;
int newmethod(int m,int **r) ;
int newmethod(int m,double **p) ;
int newmethod(int m,int **r,double **p) ;

coombs is an example of the first prototype, benham of the second, schulze of the fourth, bucklin voting of the fifth, and contingent voting of the last. The third is never used at present, since I have no methods which use poscounts while needing additional access to the ballots.

bal: a matrix of ballots: bal[i][j] encodes the candidate who is the j^th preference on the i^th ballot. The coding is explained below under ballot format. Candidates are specified as integers (from 0 to m–1) rather than as characters or strings.
count: count[i] says that the ballot occurs this many times.
nbal: the number of ballots (and of counts).
m: the number of candidates.
r: is a matrix of victory margins (or possibly of beatcounts).
p: is a matrix of position counts.

The matrix of victory margins contains all the information needed by many voting methods. A few need only the pos counts. Beatcounts are rather a niche. The matrices are defined as follows:

Beatcounts: r_b[i][j] is the number of ballots in which i is strictly preferred to j. Thus nvoters–r_b[i][j]–r_b[j][i] is the number of voters who rank i and j equally.
Victory margins: r[i][j] is the excess of the number of ballots in which i is preferred to j over the number with the opposite preference. So r[i][j] = r_b[i][j] – r_b[j][i].
Position counts: p[i][j] is the number of ballots in which candidate i occurs in position j (0≤j<m).

Position counts may be fractional because ties are handled by assigning equal fractional ballots to each ordering of the tied candidates.

You could easily compute victory margins or poscounts for yourself, but to avoid duplication you’re urged to use matrices optionally supplied. Often you won’t need to look at the ballots at all.

Extended prototypes pass an additional array a of doubles:

int newmethod(bitem **bal,int *count,int nbal,int m,double *a) ;
int newmethod(bitem **bal,int *count,int nbal,int m,int **r,double *a) ;
int newmethod(int m,int **r,double *a) ;

Again a matrix of double poscounts can be supplied instead of a matrix of integer margins. The array a can have one of several different meanings:

It can be an input array of AV/IRV scores for methods with flag ‘a’. (The AV score is the number of rounds a candidate survives before being eliminated: it is 0 for the first candidate eliminated and m–1 for the winner. It is coded as a double for consistency with other scores.)
It can be an input array of Borda scores for methods with flag ‘b’.
It can be an output array of scores which must be provided by any method whose flag is ‘f’.

Finally there is a prototype for methods which make use of the Smith set:

int newmethod(bitem **bal,int *count,int nbal,int m,int **r,int *a,int na) ;

Here a is the Smith set and na its size. Methods using the Smith set are implemented alongside Smith tiebreaks. (Poscounts are not permitted as an alternative to margins.)

Each candidate in a ballot is specified through a bitem (‘ballot item’) structure, comprising two fields: the candidate number, an int (‘c’), and a character flag (‘flag’). Candidates are specified as integers (from 0 to m–1) rather than as characters or strings, which is why c is a number.

The flag should take one of three values: ‘>’, ‘=’, and the null character. The first two have their standard meanings in voting theory, referring to a strict preference or an indifference between candidates. The null character indicates truncation: i.e. all candidates not ranked so far are less preferred than those who have been ranked, but are indifferent between each other.

Suppose m=3, and a ballot comprises three items:

c=1, flag=‘=’;
c=0, flag=‘>’; and
c=2, flag=null.

Then this corresponds to the ballot conventionally written ‘1=0>2’, i.e. the voter ranks 1 and 0 equal, and places 2 below both of them.

Alternatively, if a ballot comprises the single item:

c=1, flag=null

then the voter has bullet-voted for 1.

Manipulating ballot items is rather irksome. To alleviate the difficulty some utilities are defined in condorcet.h: see ballot utilities below.

You should not assume that the ballots come in any particular order except that the first ballot will be random (to allow for the random ballot required by Ranked Pairs); nor should you assume that a ballot occurs only once in bal.

parseballot: parse a ballot item into a matrix of ints.

int parseballot(bitem *bal,int m,int **res) ;

bal: an input array of ballot items for an election with m candidates;
res: an output matrix expressing the same ballot as integers.

You should allocate the matrix before calling parseballot (res = bmatrix(m+1,m)). Each row contains a set of candidates rated equal, terminated by a ‘-1’; candidates in each row are preferred to candidates in following rows. The return value is the number of rows. You will want to free the matrix when you’ve finished (freeimatrix(res)).

unparseballot: reverse parseballot.

void unparseballot(bitem *bal,int m,int **mat,int nrow) ;

mat is the input, bal the output.

expandballot: detruncate a ballot item.

void expandballot(bitem *a,bitem *b,int m) ;

a is a (possibly truncated) input ballot over m candidates; b, the output, is in the same format but lists all candidates. Thus the ballot over 4 candidates ‘3>1’ is expanded to ‘3>1>0=2’.

You notify condorcet by calling the function ‘notify’ with 3 arguments, which are the function implementing the voting method, its name, and a string of character flags which tell condorcet how to use it.

a: the method uses AV/IRV scores as input.
b: the method uses Borda scores as input.
c: the method is Condorcet-consistent.
C: the method furnishes a Condorcet completion (i.e. it is not Condorcet-consistent, but may be used to resolve Condorcet cycles).
e: the method should be passed beatcounts rather than victory margins.
r: the method should be used as a restricted tiebreak.
f: the method should be used as a full tiebreak.
o: the method is optional, and should not be used unless named in the ‘options’ call-line string.
x: the method should not be included in tactical voting tests.
y: the method should not be included if truncation is being applied. You will want to use this option if your method can’t cope with ties.

The notification needs to take place before main() is invoked. You achieve this by assigning the return value of ‘notify’ to a top-level static variable as shown in the example.

Suppose we want to evaluate Forest Simmons’s ‘Quick and Dirty Condorcet’ (“Count the basic scores of the candidates, which for a given candidate is the number of ballots on which it is ranked above at least one other candidate. Determine the Smith candidate X having the lowest basic score. Elect from among the candidates not pairwise defeated by X, the one with the highest basic score.”). We can write a function to implement it as follows:

#include "memory.h"
#include "condorcet.h"

int qdc(bitem **bal,int *count,int nbal,int m,int **rmat,int *set,int nset)
{ if(nset==1) return set[0] ; 
  int i,j,imax,balno,c,*basicscore=ivector(nset),**ballot=imatrix(m,m+1),nrow ; 
  // Count the basic scores of the candidates, which for a given candidate is  
  // the no. of ballots on which it is ranked above at least one other candidate
  for(i=0;i<nset;i++) for(c=set[i],balno=0;balno<nbal;balno++) 
  { nrow = parseballot(bal[balno],m,ballot) ; 
    for(j=0;ballot[nrow-1][j]>=0&&ballot[nrow-1][j]!=c;j++) ;
    if(ballot[nrow-1][j]<0) basicscore[i] += count[balno] ;
  }
  // Determine the Smith candidate c having the lowest basic score.
  for(c=i=0;i<nset;i++) if(basicscore[i]<basicscore[c]) c = i ; 
  // Elect from among the candidates not pairwise defeated by c, the one with
  // the highest basic score.
  for(imax=-1,i=0;i<nset;i++) if(rmat[c][i]<=0) 
    if(imax<0||basicscore[i]>basicscore[imax]) imax = i ; 
  free(basicscore) ; freeimatrix(ballot) ;
  return set[imax] ; 
}
static int unused = notify(qdc,"q&dc","c") ;

You now need to recompile condorcet with an extended command:

g++ -O -g -o condorcet condorcet.c simplemethods.c rankedpairs.c wbc.c ranf.c qdc.c

When you run condorcet, q&dc results will be included among the output; eg.

    smith+ random  fptpf   fptpr    dblv   bordaf  bordar   avf     avr   minimaxfminimaxrtideman   q&dc
           0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911  0.0911

The various methods have been implemented following the descriptions I found most helpful. They are meant to be usable for reference but I cannot guarantee that all are correct. If you think your favourite algorithm receives short shrift, you may want to validate the software.

My implementation of Ranked Pairs follows Tideman’s original paper literally whereas my River may be simplistic.

Ties (other than those that receive special treatment: Copeland, Smith and Ranked Pairs) are resolved by taking the lexically first tied winner. There would be no advantage in randomly permuting the candidates because they’re randomly ordered in the first place. If you want to make use of my code but want a genuinely random tiebreak, then you should either randomly permute the candidates in advance or modify the code.

After computing the Smith set I sort it lexically because the algorithm for finding it returns elements in decreasing order of Copeland score, which would violate the intended randomness of tie-breaking.

Almost all the code in condorcet except the individual methods is highly generic, so it would be hard for it to disadvantage a particular algorithm. MJ is special-cased throughout so it is something of an exception.

• method • exec • line • print • getnalg • getalg • notify • llullset • smithset • battery • main

#include "memory.h"
#include <math.h>
#include "condorcet.h"
#include "random.h"

int condorcet(int m,int **r) ;
void ranelection(ull *x,int dim,int m,int n,
                 double *dist,double **d2,int *mj,int *trunx,
                 double shift,double qsd,double qscl) ;
int truncate(ull *x,ull *xt,int nbal,int m,int trunc,int *truncarr) ; 
int repack(ull *blist,int nbal,int m,bitem ***obal,int **ocount) ;
void votetactically(ull *x,ull *y,int m,int c0,int c1,int opt,int n) ;

struct method // structure defining a voting method
{ void *f ; 
  char *name,active,argtype ; 
  char cflag,Cflag,aflag,bflag,eflag,rflag,fflag,xflag,yflag,Yflag ; 
  char minm ;
  int res ; 
  method(void *p1,char *p2,char *p3,int p4)
  { char i,j,c,digits[10]={'0','1','2','3','4','5','6','7','8','9'} ; 
    f = p1 ; name = p2 ; argtype = p4 ; 
    yflag = cflag = Cflag = aflag = bflag = rflag = fflag = xflag = eflag = 0 ; 
    Yflag = minm = 0 ; 
    active = 1 ; 
    for(i=0;p3[i];i++) 
    { c = p3[i] ;
      if(c=='o') active = 0 ; 
      else if(c=='c') cflag = 1 ; 
      else if(c=='C') Cflag = 1 ; 
      else if(c=='a') aflag = 1 ; 
      else if(c=='b') bflag = 1 ; 
      else if(c=='r') rflag = 1 ; 
      else if(c=='f') fflag = 1 ; 
      else if(c=='x') xflag = 1 ; 
      else if(c=='y') yflag = 1 ; 
      else if(c=='Y') Yflag = 1 ; 
      else if(c=='e') eflag = 1 ; 
      else 
      { for(j=0;j<10&&digits[j]!=c;j++) ;
        if(j==10) throw up("%c is not a recognised option for %s",c,name) ; 
        minm = j ; 
      }
    }
    if(rflag||fflag) if(minm>2) throw up("method %s (requiring %d candidates) "
                            "cannot be used as a tie-break",name,minm) ;
  }

  int exec(bitem **b,int *c,int nb,int m,int **rbeat,int **r,double **p,
           double *s,int *is,int ns)
  { if(eflag) r = rbeat ; 
    if(argtype==0) return ((int (*)(bitem **,int *,int,int)) f)(b,c,nb,m) ; 
    else if(argtype==1) 
      return ((int (*)(bitem **,int *,int,int,int **)) f)(b,c,nb,m,r) ; 
    else if(argtype==4) 
      return ((int (*)(bitem **,int *,int,int,double **)) f)(b,c,nb,m,p) ; 

    else if(argtype==11) return ((int (*)(int,int **)) f)(m,r) ; 
    else if(argtype==14) return ((int (*)(int,double **)) f)(m,p) ; 
    else if(argtype==16) return ((int (*)(int,int **,double **)) f)(m,r,p) ; 

    else if(argtype==2) 
      return ((int (*)(bitem **,int *,int,int,double *)) f)(b,c,nb,m,s) ; 

    else if(argtype==3) 
      return ((int (*)(bitem **,int *,int,int,int **,double *)) f)
              (b,c,nb,m,r,s) ; 
    else if(argtype==5) 
      return ((int (*)(bitem **,int *,int,int,double **,double *)) f)
              (b,c,nb,m,p,s) ; 

    else if(argtype==13) return ((int (*)(int,int **,double *)) f)(m,r,s) ; 
    else if(argtype==15) return ((int (*)(int,double **,double *)) f)(m,p,s) ; 

    else if(argtype==9) 
      return ((int (*)(bitem **,int *,int,int,int **,int *,int)) f)
              (b,c,nb,m,r,is,ns) ; 
    throw up("can\'t process arg type %d",argtype) ; 
  }
  int line(int l) // says how often a method occurs on line l of output
  { if(l==0) return !cflag ; 
    else if(l==1) return cflag&&argtype!=9 ; 
    else if(l==2) return Cflag ; 
    else if(l==3) return rflag + fflag ;
    else return rflag + fflag + (argtype==9) ;
  }
  void print(char opt)
  { char *buf = charvector("         ") ; 
    int len=strlen(name),l=(opt?len+1:len),i=(18-l)/2-4 ;
    strncpy(buf+i,name,len) ; 
    if(i+l>9) throw up("name \"%s\" too long",name) ; 
    if(opt) buf[i+len] = opt ; 
    printf("%s",buf) ; 
    free(buf) ; 
  }
} ;
static int nmethod=0,methodlen=0 ; 
static method *mlist=0 ; 

static int getnalg()
{ int i,j,n ;
  for(n=i=0;i<nmethod;i++) for(j=0;j<5;j++) n += mlist[i].line(j) ;
  return n ; 
}
static int getalg(char *name)
{ int i,algno ;
  for(algno=i=0;i<nmethod;i++) if(mlist[i].line(0))
  { if(!strcmp(mlist[i].name,name)) return algno ; algno += 1 ; }
  for(i=0;i<nmethod;i++) if(mlist[i].line(1))
  { if(!strcmp(mlist[i].name,name)) return algno ; algno += 1 ; }
  for(i=0;i<nmethod;i++) algno += mlist[i].line(2) + mlist[i].line(3) ;
  for(i=0;i<nmethod;i++) if(mlist[i].line(4))
  { if(!strcmp(mlist[i].name,name)) return algno ; algno += 1 ; }
  return -1 ; 
}
int notify(void *func,char *n,char *t,int a)
{ int i ; 
  for(i=0;i<nmethod;i++) if(!strcmp(mlist[i].name,n))
    throw up("%s has already been notified",n) ;
  if(a==0||a==1) // standard args + possibly results matrix
  { if(strchr(t,'f')||a==4) 
      throw up("%s does not have enough args for type %s",n,t) ; 
  }
  if(strchr(t,'a')||strchr(t,'b')||strchr(t,'f')) 
    if(a!=2&&a!=3&&a!=5&&a!=13&&a!=15)
      throw up("%s has type %s which needs an array argument",n,t) ; 
  if(!strchr(t,'a')&&!strchr(t,'b')&&!strchr(t,'f')) 
    if(a==2||a==3||a==5||a==13||a==15) throw up("%s has type %s which "
        "does not have an array argument needed for full tiebreaks",n,t) ; 
  if(nmethod==methodlen)
  { methodlen += 60 ; 
    mlist = (method *) cjcrealloc(mlist,methodlen*sizeof(method)) ; 
  }
  mlist[nmethod++] = method(func,n,t,a) ;
  return 0 ; 
}
int notify(int (*f)(bitem **,int *,int,int),char *name,char *opts)
{ return notify((void *)f,name,opts,0) ; }
int notify(int (*f)(bitem **,int *,int,int,int **),char *name,char *opts)
{ return notify((void *)f,name,opts,1) ; }
int notify(int (*f)(bitem **,int *,int,int,double **),char *name,char *opts)
{ return notify((void *)f,name,opts,4) ; }

int notify(int (*f)(int,int **),char *name,char *opts)
{ return notify((void *)f,name,opts,11) ; }
int notify(int (*f)(int,double **),char *name,char *opts)
{ return notify((void *)f,name,opts,14) ; }
int notify(int (*f)(int,int **,double **),char *name,char *opts)
{ return notify((void *)f,name,opts,16) ; }

int notify(int (*f)(bitem **,int *,int,int,double *),char *name,char *opts)
{ return notify((void *)f,name,opts,2) ; }

int notify
  (int (*f)(bitem **,int *,int,int,int **,double *),char *name,char *opts)
{ return notify((void *)f,name,opts,3) ; }
int notify
  (int (*f)(bitem **,int *,int,int,double **,double *),char *name,char *opts)
{ return notify((void *)f,name,opts,5) ; }

int notify(int (*f)(int,int **,double *),char *name,char *opts)
{ return notify((void *)f,name,opts,13) ; }
int notify(int (*f)(int,double **,double *),char *name,char *opts)
{ return notify((void *)f,name,opts,15) ; }

int notify(int (*f)(bitem **,int *,int,int,int **,int *,int),char *n,char *o)
{ return notify((void *)f,n,o,9) ; }

int simplenotifier() ; // in simplemethods
static int unusedvariable = simplenotifier() ; 

/* -------------------------------- llullset -------------------------------- */

int llullset(int m,int **r,int *llullscore,int *set)
{ int i,j,t,imax,rsgn ; 
  for(i=0;i<m;i++) for(llullscore[i]=j=0;j<m;j++) 
  { if(r[i][j]>0) rsgn = 1 ; else if(r[i][j]<0) rsgn = -1 ; else rsgn = 0 ; 
    llullscore[i] += rsgn ; 
  }
  for(i=0;i<m;i++) if(i==0||llullscore[i]>imax) imax = llullscore[i] ;  
  for(t=i=0;i<m;i++) if(llullscore[i]==imax) set[t++] = i ; 
  return t ; 
}
/* -------------------------------- smithset -------------------------------- */

int smithset(int m,int **r,int *llullscore,int *set)
{ int i,j,row,col,lhs,rhs,ind[25] ;
  xi* pref = xivector(m) ; 
  for(i=0;i<m;i++) pref[i] = xi(llullscore[i],i) ; 
  xisortdown(pref,m) ; 
  for(i=0;i<m;i++) ind[i] = pref[i].i ; 
  free(pref) ;   

  for(rhs=1,lhs=0;lhs<rhs;lhs=rhs,rhs=row+1)
  { for(;rhs<m&&llullscore[ind[rhs]]==llullscore[ind[rhs-1]];rhs++) ; 
    for(col=rhs,row=m;col==rhs&&row>=rhs;row--) 
      for(col=lhs;col<rhs&&r[ind[row-1]][ind[col]]<0;col++) ; 
  }
  for(i=0;i<lhs;i++) set[i] = ind[i] ; 
  return lhs ; 
}
/* -------------------------------- battery --------------------------------- */

// battery of voting methods; first standalone, then llull and smith tiebreaks
// minimax tells us whether we have a condorcet cycle, and if not we short cut
// the condorcet methods, assigning the condorcet winner to each 

void battery(bitem **bal,int *count,int nbal,int m,int *res,int *tie)
{ int i,j,k,t,minx,minlen,nset,**rmat,ntb=9,nalg=getnalg(),*ccount ; 
  int nn,mi,ai,bi,r,iter,balno,algno,cond,nrow,maxlen,**rdash,num,len ; 
  int *red = ivector(m+1) , **rbeat , **rbeatdash ; 
  int *llullscore = ivector(m) , *set = ivector(m) , *buf = ivector(m) ; 
  bitem **cbal ;
  double **score = matrix(nmethod,m) , **pmat , **pdash , *p , *z = vector(m) ;
  ull *cc = ui64vector(nbal) ; 

  rbeat = genbeatcounts(bal,count,nbal,m) ;
  rmat = marginalise(rbeat,m) ;
  pmat = genposcounts(bal,count,nbal,m) ;
  for(bi=ai=mi=-1,i=0;i<nmethod;i++) 
    if(!strcmp(mlist[i].name,"minimax")) mi = i ; 
    else if(!strcmp(mlist[i].name,"irv")||!strcmp(mlist[i].name,"av")) ai = i ; 
    else if(!strcmp(mlist[i].name,"borda")) bi = i ; 
  if(mi<0) throw up("minimax not provided as a method") ; 
  if(ai<0) throw up("av/irv not provided as a method") ; 
  if(bi<0) throw up("borda not provided as a method") ; 
  cond = condorcet(m,rmat) ; 

  // now do non-Condorcet methods
  for(algno=i=0;i<nmethod;i++) if(mlist[i].line(0))
  { if(mlist[i].active||(cond<0&&mlist[i].Cflag))
    { if(!mlist[i].f) r = -(1+i) ; 
      else r = mlist[i].exec(bal,count,nbal,m,rbeat,rmat,pmat,score[i],0,0) ; 
      mlist[i].res = res[algno] = r ;
    }
    algno += 1 ; 
  }

  if(cond>=0) for(;algno<nalg;algno++) res[algno] = cond ; // no cycle
  else                                                     // condorcet cycle 
  { // do the standalone condorcet methods
    for(i=0;i<nmethod;i++) if(mlist[i].line(1))
    { if(mlist[i].active)
      { if(!mlist[i].f) res[algno] = -(1+i) ; // no function, just save index
        else if(mlist[i].aflag) res[algno] =  // av follow-on
          mlist[i].exec(bal,count,nbal,m,rbeat,rmat,pmat,score[ai],0,0) ; 
        else if(mlist[i].bflag) res[algno] =  // borda follow-on
          mlist[i].exec(bal,count,nbal,m,rbeat,rmat,pmat,score[bi],0,0) ; 
        else if(mlist[i].fflag) res[algno] =  // full tiebreak 
          mlist[i].exec(bal,count,nbal,m,rbeat,rmat,pmat,score[i],0,0) ; 
        else res[algno] = 
          mlist[i].exec(bal,count,nbal,m,rbeat,rmat,pmat,0,0,0) ; 
        if(i==mi) minx = res[algno] ;
      }
      algno += 1 ;
    }

    if(tie) 
    { tie[0] += 1 ;                                 // condorcet cycle
      for(i=0;i<m;i++) if(i!=minx&&score[mi][minx]==score[mi][i]) break ;
      if(i<m) tie[3] += 1 ;                         // minimax tie
    }

    // do the condorcet completions
    for(i=0;i<nmethod;i++) if(mlist[i].line(2)) res[algno++] = mlist[i].res ; 

    // now do the tiebreaks for each of the set-valued methods
    for(iter=0;iter<2;iter++)
    { if(iter==0) nset = llullset(m,rmat,llullscore,set) ;
      else nset = smithset(m,rmat,llullscore,set) ;
      if(tie&&iter==0)
      { for(i=0;i<nset&&(set[i]!=minx);i++) ; 
        if(i==nset) tie[7] += 1 ; // count of minimax winners outside llull set
      }

      isortup(set,nset) ; // so that the smith set is listed in 'random' order
      if(tie) tie[4+iter] += nset ; 
      if(tie&&nset>1) tie[1+iter] += 1 ;           // non-singleton set
      if(nset==1)            // no need for tie-break for singleton set
      { for(i=0;i<nmethod;i++) if(mlist[i].line(3+iter))
        { if(mlist[i].fflag) res[algno++] = set[0] ; 
          if(mlist[i].rflag) res[algno++] = set[0] ; 
          if(iter&&mlist[i].argtype==9) res[algno++] = set[0] ; 
        }
        continue ;
      }

      // compact the ballots - allocate space
      for(i=0;i<m;i++) buf[i] = -1 ; 
      for(i=0;i<nset;i++) buf[set[i]] = i ;
      for(len=balno=0;balno<nbal;balno++)
      { for(t=i=0;i<m;i++) 
        { if(k=buf[bal[balno][i].c],k>=0) red[1+(t++)] = k ; 
          if(bal[balno][i].flag==0) break ; 
        }
        if(t) { red[0] = t ; cc[len++] = compress(red,t+1) ; }
      }
      ui64radixsort(cc,len) ; 
      for(nn=i=0;i<len;i=j) { for(j=i+i;j<len&&cc[j]==cc[i];j++) ; nn += 1 ; }
      cbal = bmatrix(nn,nset) ; 
      ccount = ivector(nn) ; 
      for(nn=i=0;i<len;i=j) 
      { for(num=1,j=i+i;j<len&&cc[j]==cc[i];j++) num += 1 ; 
        decompress(cc[i]>>4,red,cc[i]&15) ; 
        ballotise(red,cbal[nn],cc[i]&15) ; 
        ccount[nn++] = num ; 
      }

      rbeatdash = genbeatcounts(cbal,ccount,nn,nset) ; 
      rdash = marginalise(rbeatdash,nset) ; 
      pdash = genposcounts(cbal,ccount,nn,nset) ; 
      for(i=0;i<nmethod;i++) if(mlist[i].line(3+iter))
      { if(mlist[i].fflag)
        { for(r=j=0;j<nset;j++) if(j==0||score[i][set[j]]>score[i][r]) 
            r = set[j] ; 
          res[algno++] = r ; 
        }
        if(mlist[i].rflag)
        { p = z ;
          if(mlist[i].aflag) for(j=0;j<nset;j++) z[j] = score[ai][set[j]] ; 
          else if(mlist[i].bflag) for(j=0;j<nset;j++) z[j] = score[bi][set[j]] ; 
          else if(mlist[i].fflag) for(j=0;j<nset;j++) z[j] = 0 ;
          else p = 0 ; // array not passed
          j = mlist[i].exec(cbal,ccount,nn,nset,rbeatdash,rdash,pdash,p,0,0) ;
          res[algno++] = set[j&0xffffff] ; // because minimax includes a flag
        }
        if(iter&&mlist[i].argtype==9) // tideman's alternative
          res[algno++] = 
            mlist[i].exec(bal,count,nbal,m,0,rmat,pmat,0,set,nset) ;
      }
      free(ccount) ; freeimatrix(rdash,rbeatdash) ; 
      freematrix(pdash) ; freebmatrix(cbal) ;
    }
  }
  free(llullscore,set,buf,red,z,cc) ; 
  freeimatrix(rmat,rbeat) ; freematrix(pmat,score) ; 
}
/* ---------------------------------- main ---------------------------------- */

int main(int argc,char **argv)
{ int m = argc<3?9:atoi(argv[2]) , n = argc<4?10001:atoi(argv[3]) ;
  int ntests = argc<5?100000:atoi(argv[4]) , dim = argc<2?2:atoi(argv[1]) ;
  int num,opt,mji,diag=-1,metric,trunc=m,resdiag,ndiag,resno,lino,truncopt=0 ; 
  int nalg=getnalg(),i,j,k,l,t,nbal,rightful,testno,c0,c1,mj,mno,offset=0,clim ;
  int *res=ivector(nalg) , *cres=ivector(nalg) , *active = ivector(nalg) ;
  int *win=ivector(nalg),*tie=ivector(8),*count=ivector(n) , *truncarr=0 ;
  double q,total,qdist,qbal,qsd=-1,qscale=-1, *qlos = vector(nalg) , *qtrunc ;
  double *qres = vector(nalg) , *dist = vector(m) , **d2 = matrix(m,m) , qr,qs ; 
  char *tok , buf[50] , rf , *optname[]={"sincere","com","cyc","bur","lis",0} ;
  ull *x , *y , *xt ;
  bitem **bal ; 
  if(argc<=1) 
  { printf("condorcet dim ncandidates nvoters ntests options\n") ; return 0 ; }
  if(m>12) throw up("too many candidates (%d): max is 12",m) ; 

  /* -------------------------- extract parameters -------------------------- */

  truncopt = opt = 0 ; 
  trunc = m ; 
  if(argc>=6) for(tok=strtok(argv[5],"+-, ");tok;tok=strtok(0,"+-, "))
  { for(k=i=0;i<nmethod;i++) 
      if(!strcmp(tok,mlist[i].name)&&mlist[i].active==0)
        k = mlist[i].active = 1 ; 
    if(k) ; // don't reuse option
    else if(!strcmp(tok,"offset")) offset = 1 ; 
    else if(buf[8]=0,strncpy(buf,tok,8),!strcmp(buf,"gaussian")) 
    { if(strlen(tok)>9&&tok[8]==':') qscale = atof(tok+9) ; else qscale = 1 ; }
    else if(buf[5]=0,strncpy(buf,tok,5),!strcmp(buf,"gauss")) 
    { if(strlen(tok)>6&&tok[5]==':') qscale = atof(tok+6) ; else qscale = 1 ; }
    else if(buf[6]=0,strncpy(buf,tok,6),!strcmp(buf,"truncm")) 
    { if(strlen(tok)>7&&tok[6]==':') trunc = atoi(tok+7) ; else trunc = 3 ; 
      if(trunc>=m-1||trunc<0) throw up("illegal trunc: %d",trunc) ; 
    }
    else if(buf[6]=0,strncpy(buf,tok,6),!strcmp(buf,"trunca")) truncopt = 'a' ;
    else if(buf[6]=0,strncpy(buf,tok,6),!strcmp(buf,"truncc")) truncopt = 'c' ;
    else if(buf[7]=0,strncpy(buf,tok,7),!strcmp(buf,"trunci:")) 
    { qr = atof(tok+7) ; 
      for(i=8;tok[i]&&tok[i]!=':';i++) ; 
      if(tok[i]!=':') throw up("illegal trunci parms") ; 
      qs = atof(tok+i+1) ; 
      truncopt = 'i' ;
    }
    else if(buf[4]=0,strncpy(buf,tok,4),!strcmp(buf,"jury")) 
    { if(tok[4]==':') qsd = atof(tok+5) ; else qsd = 1 ; 
      if(qsd<=0) throw up("%.1e not a legal noise level for jury model") ; 
    }
    else if(buf[5]=0,strncpy(buf,tok,5),!strcmp(buf,"diag:"))
    { diag = getalg(tok+5) ; 
      if(diag<0||diag>=nalg) throw up("%s - method not present",tok) ;
    }
    else 
    { for(opt=1;optname[opt]&&strncmp(tok,optname[opt],3);opt++) ; 
      if(!optname[opt]) throw up("%s is an unrecognised option",tok) ;
    }
  }
  /* --------------------- set up mji and activity array -------------------- */

  if(qsd>0) for(i=0;i<nmethod;i++) mlist[i].active = 1 ; 
  if(opt) for(i=0;i<nmethod;i++) if(mlist[i].xflag) mlist[i].active = 0 ; 
  if(trunc<m||truncopt) 
  { for(i=0;i<nmethod;i++) if(mlist[i].yflag) mlist[i].active = 0 ; }
  else { for(i=0;i<nmethod;i++) if(mlist[i].Yflag) mlist[i].active = 0 ; }
  for(i=0;i<nmethod;i++) if(m<mlist[i].minm) mlist[i].active = 0 ; 
  for(i=0;i<nalg;i++) active[i] = 1 ; 
  for(mji=-1,resno=k=0;k<2;k++) for(i=0;i<nmethod;i++) if(mlist[i].line(k))
  { if(!strcmp(mlist[i].name,"mj")) mji = resno ; 
    if(mlist[i].active==0) active[resno] = 0 ; 
    resno += 1 ; 
  }
  if(opt) for(;k<5;k++) for(i=0;i<nmethod;i++) 
    for(l=mlist[i].line(k),j=0;j<l;j++)
  { if(!strcmp(mlist[i].name,"random")) active[resno] = 0 ; resno += 1 ; }

  if(opt&&mji>=0&&active[mji]) throw up("can\'t do tactical voting for mj") ; 
  if((offset||qscale>0)&&qsd>0) throw up("illegal options for jury model") ; 

  for(j=i=0;i<nmethod;i++) if(!mlist[i].active) if(!mlist[i].xflag||opt<=0)
    if(strcmp(mlist[i].name,"clower")&&strcmp(mlist[i].name,"cupper"))
  { if(j==0) { printf("optional methods not requested:") ; j = 1 ; }
    printf(" %s",mlist[i].name) ; 
  }
  if(j) printf("\n") ; 

  x  = ui64vector(n) ; 
  xt = ui64vector(n) ; 

  if(opt>0) y = ui64vector(n) ; 
  if(truncopt=='a') truncarr = ivector(n) ; 
  else if(truncopt=='c') truncarr = ivector(m) ; 
  else if(truncopt=='i') truncarr = (int *) ( qtrunc = vector(m) ) ; 
  if(!truncopt) truncopt = trunc ; 
  if((truncarr||trunc<m)&&opt==4) 
    throw up("list voting is incompatible with truncation.") ; 

  /* --------------------------- loop over tests ---------------------------- */

  for(qbal=qdist=ndiag=total=testno=0;testno<ntests;testno++)
  { ranset(testno) ; 
    if(truncopt=='i') for(i=0;i<m;i++) qtrunc[i] = betav(qr,qs) ; 
    else if(truncopt=='c') 
    { for(i=0;i<m;i++) truncarr[i] = 1+i ; 
      for(i=1;i<m;i++) if(rani(2)) swap(truncarr[0],truncarr[i]) ; 
    }

    ranelection(x,dim,m,n,dist,d2,mji>=0&&active[mji]?&mj:0,
                truncopt=='a'?truncarr:0,offset,qsd,qscale) ; 
    for(q=t=0;t<m;t++) if(t==0||dist[t]<q) { rightful = t ; q = dist[t] ; }
    qdist += q ; // add mean dist of rightful winner from voters 

    nbal = truncate(x,xt,n,m,truncopt,truncarr) ; 
    if(truncopt) 
    { for(k=i=0;i<n;i++) k += xt[i] & 15 ; qbal += k / (double) n ; }
    total += nbal = repack(xt,nbal,m,&bal,&count) ; 
    battery(bal,count,nbal,m,res,tie) ;
    for(i=0;i<nalg;i++) if(res[i]<0)
    { mno = -(1+res[i]) ; 
      if(!strcmp(mlist[mno].name,"mj")) res[i] = mj ; 
      else if(!strcmp(mlist[mno].name,"clower")) res[i] = -1 ; 
      else if(!strcmp(mlist[mno].name,"cupper")) res[i] = rightful ; 
    }
    freebmatrix(bal) ; free(count) ; 
    if(opt>0) // if we're doing tactical voting
    { if(diag>=0) resdiag = res[diag] ; 
      // loop over candidate pairs to find most damaging successful subversion
      for(k=-1,c0=0;c0<m;c0++) // supporters of c0 will vote tactically
        for(clim=(opt==4?factorial(m):m),c1=0;c1<clim;c1++) 
          if(opt==4||c0!=c1) 
      { if(truncarr&&truncopt=='a')
        { nbal = truncate(x,y,n,m,truncopt,truncarr) ; 
          votetactically(y,xt,m,c0,c1,opt,nbal) ; 
        }
        else
        { votetactically(x,y,m,c0,c1,opt,n) ; 
          nbal = truncate(y,xt,n,m,truncopt,truncarr) ;
        }
        nbal = repack(xt,nbal,m,&bal,&count) ;
        battery(bal,count,nbal,m,cres,0) ;
        freebmatrix(bal) ; free(count) ; 
        for(i=0;i<nalg;i++) if(active[i]&&cres[i]!=res[i]) 
          if( dist[cres[i]]>dist[res[i]] && d2[c0][cres[i]]<d2[c0][res[i]] )
        // the test "dist[cres[i]]>dist[res[i]]" finds whether cres[i] is 
        // worse than the current worst successful subversion
        { res[i] = cres[i] ; if(i==diag) k = c0 | (c1<<6) | (res[i]<<26) ; }
      } 
      if(k>=0&&ndiag<100) // print diagnostics if requested [no longer works]
      { c0 = k & 0x3f ;
        c1 = (k>>6) & 0xfffff ;
        printf("%c -> %c: supporters of %c ",resdiag+'a',(k>>26)+'a',c0+'a') ; 
        if(opt==4) printf("submit a fixed ballot\n") ; 
        else if(opt==3) printf("demote %c\n",c1) ;
        else printf("promote %c\n",c1) ;
        votetactically(x,y,m,c0,c1,opt,n) ; 
        for(i=0;i<n;i=j) 
        { for(j=0;j<trunc;j++) printf("%c",(int)((x[i]>>(4*j))&15)+'a') ; 
          printf(" -> ") ;
          for(j=0;j<trunc;j++) printf("%c",(int)((y[i]>>(4*j))&15)+'a') ; 
          for(num=1,j=i+1;x[j]==x[i]&&y[j]==y[i];j++) num += 1 ; 
          printf(" | %d   votes\n",num) ;
        }
        printf("\n") ; 
        ndiag += 1 ; 
      }
    }

    for(i=0;i<nalg;i++) if(active[i]&&res[i]>=0) 
    { qlos[i] += dist[res[i]] ; if(res[i]==rightful) win[i] += 1 ; }
  }   
  if(opt>0) free(y) ; 
  if(truncopt) free(truncarr) ; 
  free(x,xt) ; 

  /* ---------------------------- print results ----------------------------- */

  printf("%d tests (%d:%d->%.1f)\n",ntests,m,n,total/(double)ntests) ; 
  if(opt==0)
  { printf("number of Condorcet cycles = %d = %.2f%%\n",
           tie[0],tie[0]*100.0/ntests) ; 
    printf("average size of Llull/Smith set when there is a Condorcet "
           "cycle = %.2f/%.2f\n",
           tie[4]/(double)tie[0],tie[5]/(double)tie[0]) ; 
    printf("number of llull/smith/minimax ties =  %d/%d/%d = "
           "%.2f%%/%.2f%%/%.2f%%\n",tie[1],tie[2],tie[3], 
           tie[1]*100.0/ntests,tie[2]*100.0/ntests,tie[3]*100.0/ntests) ; 
    printf("number of minimax winners who are not in the Llull set = %d\n",
           tie[7]) ; 
  }
  if(truncopt) printf("avge length of truncated ballots = %.1f\n",qbal/ntests) ;
  if(diag>=0) for(i=0;i<nalg;i++) if(i!=diag) active[i] = 0 ; 

  for(metric=0;metric<2;metric++) // loop over %age/euclidean loss
  { if(metric==0) printf("percentages:") ; else printf("\nmean losses x100:") ; 
    printf("             || %d %d %d %d ",dim,m,n,ntests) ; 
    if(qsd>=0) printf("jury(%.1f) ",qsd) ; 
    if(qscale>0) printf("gauss(%.1f) ",qscale) ; 
    printf("%s%s\n",offset?"(offset) ":"",optname[opt]) ;

    if(metric==0) for(k=0;k<nalg;k++) qres[k] = win[k] * 100.0/ntests ; 
    else for(k=0;k<nalg;k++) qres[k] = (qlos[k]-qdist) * 100.0/ntests ; 
    
    for(resno=lino=0;lino<5;lino++)      // loop over the 5 lines of output
    { for(l=resno,i=0;i<nmethod;i++) if((k=mlist[i].line(lino)))
      { if(active[l]) break ; if(k==2&&active[l+1]) break ; l += k ; }
      if(i==nmethod) { resno = l ; continue ; } // skip inactive line

      if(lino<2) printf("          ") ; 
      else if(lino==2) printf("condorcet+") ; 
      else if(lino==3) printf("    llull+") ; 
      else printf("    smith+") ; 

      for(i=0;i<nmethod;i++) if((k=mlist[i].line(lino)))
      { if(k==1&&lino<3) mlist[i].print(0) ; 
        else if(k==1) 
        { if(mlist[i].argtype==9) rf = 0 ; else rf = mlist[i].rflag?'r':'f' ;
          mlist[i].print(rf) ; 
        }
        else { mlist[i].print('f') ; mlist[i].print('r') ; }
      }
      printf("\n          ") ; 
      for(i=0;i<nmethod;i++) if((k=mlist[i].line(lino))) for(j=0;j<k;j++) 
      { if( active[resno]==0
         || (!strcmp(mlist[i].name,"clower")&&(metric>0||opt>0)) ) 
          printf("    -    ") ; 
        else printf("%8.4f ",qres[resno]) ; 
        resno += 1 ; 
      }
      printf("\n") ; 
    }
    if(resno!=nalg) throw up("logic error: %d %d",resno,nalg) ; 
  } // end loop over metric (print type)
  freematrix(d2) ; 
  free(res,cres,active,win,tie,qres,dist,qlos) ; 
}
/* -------------------------------------------------------------------------- */

ranelection generates a random election and returns the implied ballots and some associated statistics. It could be used outside condorcet. The prototype is rather long:

void ranelection(ull *x,int dim,int m,int n,
                double *dist,double **d2,int *mj,
                double shift,double qsd,double qscl)

where a ull is an unsigned long long and:

x is an array of ulls predimentsioned to length n to receive the ballots;
dim is the dimension of the space;
m is the number of candidates;
n is the number of voters;
dist is an array to receive the distances of candidates from voters;
d2 is a matrix to receive the distances of candidates from each other;
mj is a pointer to a variable to receive the MJ winner;
shift is the offset to apply to the candidate distribution relative to the voters;
qsd is the noise standard deviation for jury models; and
qscl is a taper factor for Gaussians.

dist is an array of reals which you should predimension to size m. dist[i] will be returned as the average distance of voters from candidate i in spatial models. In a jury model it will be returned as the difference in merit between candidate i and the best candidate.

d2 is a matrix of reals which you should predimension to m×m. d2[i][j] will be returned as the distance between candidates i and j (and so is symmetric). For a jury model, d[i][i] = 0, d[i][j] = 1 for i≠j. If you supply a null pointer, no distance matrix will be returned.

mj is a pointer to a variable which will receive the MJ winner. A null pointer tells ranelection not to perform the calculation (which is expensive).

shift is the magnitude of the offset, which can requested via the offset argument to condorcet and is described in the section on strategic nomination above. However whereas the offset argument is a boolean flag requesting a fixed offset, the shift parameter is a multiplier to this fixed value. Zero means not to impose an offset.

qsd should be zero for a spatial model.

qscl is a taper factor for Gaussian models as described under the corresponding program argument above. A negative value requests a GMM.

• genpt • rankprefs • ranelection

#include "memory.h"
#include <math.h>
#include "condorcet.h"
#include "random.h"

static void genpt(double *x,int dim,double **offs,double qscl)
{ int t , cpt=rani(3) ; 
  double q ; 
  for(q=1,t=0;t<dim;t++) 
  { x[t] = gaussv() ; 
    if(offs) x[t] += offs[cpt][t] ; 
    if(qscl>=0) { x[t] *= q ; q *= qscl ; }
  }
}
static ull rankprefs(xi *pref,int m,int *trunc) // note: clobbers pref
{ int i,imax,vote[25] ; 
  double max,del ; 
  xisort(pref,m) ;                       // sort the distances to candidates
  if(trunc)
  { for(i=0;i<m-1;i++) 
    { del = pref[i+1].x - pref[i].x ;
      if(i==0||del>max) { imax = i ; max = del ; }
    }
    trunc[0] = imax + 1 ; 
  }
  for(i=0;i<m;i++) vote[i] = pref[i].i ;      // thus find voter's ranking
  return compress(vote,m) ;                   // compress ranking to an int
}
// generate a random election under a parametric model

void ranelection(ull *x,int dim,int m,int n,double *dist,double **d2,int *mj,
                 int *trunc,double shift,double qsd,double qscl)
{ double q,r,**judg ;
  int i,j,k,t,nbal,cpt,bal0, *vote = ivector(m) ;
  if(mj) judg = matrix(m,n) ; 

  for(i=0;i<m;i++) dist[i] = 0 ; 
  xi *pref = xivector(m) ;

  if(qsd>0) // jury model
  { double *C = vector(m) ; 
    for(i=0;i<m;i++) C[i] = gaussv() ; 
    for(j=0;j<n;j++)
    { for(i=0;i<m;i++)
      { pref[i] = xi(qsd*gaussv()-C[i],i) ; if(mj) judg[i][j] = pref[i].x ; }
      x[j] = rankprefs(pref,m,trunc?trunc+j:0) ; 
    }
    for(q=i=0;i<m;i++) if(i==0||C[i]>q) q = C[i] ; 
    for(i=0;i<m;i++) dist[i] = q - C[i] ; 
    if(d2) for(i=0;i<m;i++) for(j=0;j<m;j++) d2[i][j] = (i!=j) ; 
    free(C) ; 
  }
  else 
  { // generate candidates
    double **C = matrix(m,dim) , *V = vector(m) , **offs = matrix(3,dim) ;
    if(qscl>=0) for(i=0;i<m;i++) { genpt(C[i],dim,0,qscl) ; C[i][0] += shift ; }
    else // mixture of 3 gaussians
    { for(cpt=0;cpt<3;cpt++) for(t=0;t<dim;t++) offs[cpt][t] = gaussv() ; 
      if(shift) 
      { for(q=t=0;t<dim;t++) q += offs[0][t] * offs[0][t] ;
        for(r=(1+shift/(2*sqrt(q))),i=0;i<m;i++) for(t=0;t<dim;t++)
          C[i][t] = gaussv() + r*offs[0][t] ; 
      }
      else for(i=0;i<m;i++) genpt(C[i],dim,offs,-1) ; 
    }
    for(j=0;j<n;j++) // generate voters
    { genpt(V,dim,offs,-1) ; 
      for(i=0;i<m;i++) 
      { for(q=t=0;t<dim;t++) q += (C[i][t]-V[t]) * (C[i][t]-V[t]) ;
        dist[i] += q = sqrt(q) ;        // distance
        pref[i] = xi(q,i) ; 
        if(mj) judg[i][j] = q ; 
      }
      x[j] = rankprefs(pref,m,trunc?trunc+j:0) ; 
    }
    for(i=0;i<m;i++) dist[i] /= n ; 
    if(d2) for(i=0;i<m-1;i++) for(j=i+1;j<m;j++)
    { for(q=t=0;t<dim;t++) q += (C[i][t]-C[j][t]) * (C[i][t]-C[j][t]) ;
      d2[i][j] = d2[j][i] = sqrt(q) ;
    } 
    freematrix(C,offs) ; free(V) ; 
  }
  for(i=0;i<n;i++) x[i] = (x[i]<<4) | m ; 

  if(mj) 
  { for(q=mj[0]=i=0;i<m;i++) // have to find mj winner here
    { realsort(judg[i],n) ;         // a radix sort would be nice
      if(i==0||judg[i][n/2]<q) { mj[0] = i ; q = judg[i][n/2] ; }
    }
    freematrix(judg) ; 
  } 
  free(vote,pref) ; 
}

truncate truncates the ballots under one of several models. It returns the ballots packed into ulls with an extra value, the ballot length, in the low order bits.

It contains the subroutine repack which takes a list of ballots as output by truncate and converts them into standard ballot format.

bal is a matrix of ballots stored as integers: bal[i][j] will be voter i’s j^th preference. You should predimension bal to n×m prior to the call (i.e. bal = imatrix(n,m)).

count is an array of counts which should likewise be predimensioned to size n.

• neq • truncate • repack • ballottactically • votetactically

#include "memory.h"
#include "random.h"
#include "condorcet.h"
void ui64radixsort(ull *x,int n) ;

static int neq(bitem *a,int *b,int m) 
{ for(int i=0;i<m-1;i++) if(a[i].c!=b[i]||!a[i].flag) return 1 ; 
  if(a[m-1].c!=b[m-1]||a[m-1].flag) return 1 ; else return 0 ; 
}
int truncate(ull *x,ull *xt,int nbal,int m,int trunc,int *truncarr)           
{ int i,j,k,len,c,tbal=nbal ;
  double *qtrunc=(double *) truncarr ; 
  ull mask,r,xi ; 

  if(!truncarr) for(i=0;i<nbal;i++) // constant truncation
  { len = min(trunc,(int)(x[i]&15)) ; 
    mask = ( ((ull) 1) << (4*len) ) - 1 ;
    xt[i] = ( x[i]&(mask<<4) ) | len ; 
  }
  else if(trunc=='a') for(i=0;i<nbal;i++) // approval truncation
  { len = min(truncarr[i],(int)(x[i]&15)) ; 
    mask = ( ((ull) 1) << (4*len) ) - 1 ;
    xt[i] = ( x[i]&(mask<<4) ) | len ; 
  }
  else if(trunc=='c') for(i=0;i<nbal;i++) // candidate-specific truncation
  { len = min(truncarr[(x[i]>>4)&15],(int)(x[i]&15)) ;
    mask = ( ((ull) 1) << (4*len) ) - 1 ;
    xt[i] = ( x[i]&(mask<<4) ) | len ; 
  }
  else if(trunc=='i') // ignorance
  { for(tbal=i=0;i<nbal;i++) // ignorance truncation
    { for(len=x[i]&15,xi=x[i]>>4,r=k=j=0;j<len;j++) 
      { c = ( xi>>(4*j) ) & 15 ; 
        if(ranf()<qtrunc[c]) { r |= ((ull) c)<<(4*k) ; k += 1 ; }
      }
      if(k) xt[tbal++] = ( r << 4 ) | (ull) k ;
    }
    ui64radixsort(xt,tbal) ;
  }
  return tbal ; 
}
/* -------------------------------------------------------------------------- */

int repack(ull *blist,int nbal,int m,bitem ***obal,int **ocount)
{ int i,j,k,l,num,len,*count, flen=blist[0]&(ull)15 , *first = ivector(flen) ; 
  ull r ; 
  bitem **bal ; 

  decompress(blist[0]>>4,first,flen) ; 
  ui64radixsort(blist,nbal) ; 
  for(k=i=0;i<nbal;i=j) { for(j=i+1;j<nbal&&blist[j]==blist[i];j++) ; k += 1 ; }
  obal[0] = bal = bmatrix(k,m) ;
  ocount[0] = count = ivector(k) ; 

  for(k=i=0;i<nbal;i=j)
  { for(r=blist[i],num=1,j=i+1;j<nbal&&blist[j]==r;j++) num += 1 ; 
    len = ( r & (ull)15 ) ;
    r >>= 4 ; 
    for(l=0;l<len;l++) 
      bal[k][l] = bitem((r>>(4*l))&((ull) 15),(l<len-1)?'>':0) ;
    count[k++] = num ; 
  }
  for(i=0;i<k&&neq(bal[i],first,flen);i++) ; // keep the first ballot "random"
  if(i==k) throw up("logic error") ; 
  if(i) 
  { for(j=0;j<m;j++) swap(bal[i][j],bal[0][j]) ; swap(count[i],count[0]) ; }
  free(first) ; 
  return k ;
}
/* ----------------------------- votetactically ----------------------------- */

static ull ballottactically(ull ibal,int m,int c0,int c1,int opt) 
{ int i,j,k,set[25],r,len=(int)(ibal&15) ; 
  ull obal = ibal , bal = ibal>>4; 
  if((bal&15)!=c0) return obal ; 

  if(opt==4) 
  { if(len!=m) throw up("can\'t do list tactics with incomplete ballots") ; 
    ithperm(c1,set,m) ; 
    return (compress(set,m)<<4)+m ; 
  }

  decompress(bal,set,len) ; 
  if(opt==1) // compromising
  { for(i=len;i>0;i--) set[i] = set[i-1] ; // shift all candidates down ballot
    set[0] = c1 ; 
    for(k=i=1;i<=len;i++) if(set[i]!=c1) set[k++] = set[i] ; 
    return (compress(set,k)<<4) | k ; 
  }
  else if(opt==2) // false cycle
  { if(set[1]==c1) return obal ;           // false cycle is in fact true
    for(i=len;i>1;i--) set[i] = set[i-1] ; // shift all candidates down ballot
    set[1] = c1 ; 
    for(k=i=2;i<=len;i++) if(set[i]!=c1) set[k++] = set[i] ; 
    return (compress(set,k)<<4) | k ; 
  }
  // else opt==3 // burying: truncate the candidate away
  for(i=0;i<len&&set[i]!=c1;i++) ; // find c1 in set
  if(i==len) return obal ; 
  for(;i<len-1;i++) set[i] = set[i+1] ;
  return (compress(set,len-1)<<4) | (len-1) ; 
}
void votetactically(ull *x,ull *y,int m,int c0,int c1,int opt,int n) 
{ int i,j ;
  for(i=0;i<n;i=j) 
  { y[i] = ballottactically(x[i],m,c0,c1,opt) ; 
    for(j=i+1;j<n&&x[j]==x[i];j++) y[j] = y[i] ;
  }
}
/* -------------------------------------------------------------------------- */

Header file for voting methods.

• bitem • factorial • parseballot1 • unparseballot • expandballot • parseballot • squeezeballot • compress • decompress • ithperm • ballotise

#ifndef MEMORY_H
#include "memory.h"
#endif
#define ull unsigned long long
struct bitem 
{ unsigned short int c ; char flag ; 
  bitem() { c = flag = 0 ; }
  bitem(unsigned short int x,char y) { c = x ; flag = y ; }
} ; 
genmatrix(bitem,bvector,bmatrix,freebmatrix) ; 
genvector(ull int,ui64vector) ; 
void ui64radixsort(ull *x,int n) ;

int notify(void *func,char *n,char *t,int a) ;
int notify(int (*f)(bitem **,int *,int,int),char *name,char *opts) ;
int notify(int (*f)(bitem **,int *,int,int,int **),char *name,char *opts) ;
int notify(int (*f)(bitem **,int *,int,int,double **),char *name,char *opts) ;
int notify(int (*f)(bitem **,int *,int,int,double *),char *name,char *opts) ;
int notify
  (int (*f)(bitem **,int *,int,int,int **,double *),char *name,char *opts) ;
int notify
  (int (*f)(bitem **,int *,int,int,double **,double *),char *name,char *opts) ;
int notify(int (*f)(bitem **,int *,int,int,int **,int *,int),char *n,char *o) ;
int notify(int (*f)(int,int **),char *name,char *opts) ; // 11
int notify(int (*f)(int,double **),char *name,char *opts) ; // 14
int notify(int (*f)(int,int **,double **),char *name,char *opts) ; // 16
int notify(int (*f)(int,int **,double *),char *name,char *opts) ; // 13
int notify(int (*f)(int,double **,double *),char *name,char *opts) ; // 15

int smithset(int m,int **r,int *llullscore,int *set) ;
double **genposcounts(bitem **bal,int *count,int nbal,int m) ;
int **genmargins(bitem **bal,int *count,int nbal,int m) ;
int **genbeatcounts(bitem **bal,int *count,int nbal,int m) ;
int **marginalise(int **r,int m) ;

// note the general restriction that the number of candidates must be small 
// enough for its factorial to be stored in an int
static int factorial(int m) 
{ int i,t ; for(t=i=1;i<=m;i++) t *= i ; return t ; }

static int parseballot1(bitem *bal,int m,int **res)
{ int i,j,rowno,colno ; 
  for(colno=rowno=i=0;i<m;i++) 
  { res[rowno][colno++] = bal[i].c ; 
    if(bal[i].flag==0) { res[rowno][colno] = -1 ; break ; }
    else if(bal[i].flag=='>') 
    { res[rowno][colno] = -1 ; colno = 0 ; rowno += 1 ; }
  }
  return rowno+1 ;
}
static void unparseballot(bitem *bal,int m,int **mat,int nrow)
{ int t,i,tau,rowno ; 
  for(t=rowno=0;rowno<nrow;rowno++) 
  { for(tau=t,i=0;mat[rowno][i]>=0;i++) bal[t++] = bitem(mat[rowno][i],'=') ; 
    if(t>tau&&tau>0) bal[tau-1].flag = '>' ;
  }
  if(t) bal[t-1].flag = 0 ;
  for(;t<m;t++) bal[t] = bitem() ;
}
static void expandballot(bitem *a,bitem *b,int m)
{ int i,j,seen[25],nseen ;
  for(i=0;i<m;i++) seen[i] = 0 ; 
  for(nseen=i=0;i<m;i++) 
  { b[i] = a[i] ; seen[a[i].c] = 1 ; nseen += 1 ; if(a[i].flag==0) break ; } 
  if(nseen<m) 
  { if(nseen) b[nseen-1].flag = '>' ;
    for(j=0;j<m;j++) if(seen[j]==0) b[nseen++] = bitem(j,'=') ; 
    b[m-1].flag = 0 ; 
  }
}
static int parseballot(bitem *bal,int m,int **res)
{ static bitem b[25] ; expandballot(bal,b,m) ; return parseballot1(b,m,res) ; }

static void squeezeballot(bitem *a,bitem *b,int mleft,int loser)
{ int t,tau ; 
  for(tau=t=0;t<mleft;t++) 
    if(a[t].c!=loser) b[tau++] = a[t] ;
    else if(t>0&&a[t].flag!='=') b[tau-1].flag = a[t].flag ; 
}
static ull compress(int *x,int m)
{ ull r ; 
  short int i ; 
  for(r=i=0;i<m;i++) r |= ((ull) x[i])<<(4*i) ;
  return r ; 
}
static void decompress(ull r,int *x,int m) 
{ for(int i=0;i<m;i++) x[i] = 15 & (r>>(4*i)) ; }

static void ithperm(int r,int *x,int m) // find the ith permutation of 0...m-1
{ int i,j,k,buf[25] ;                   // in lexical order
  div_t res ; 
  for(i=0;i<m;i++) buf[i] = i ; 
  for(k=m-m+1,i=0;i<m;i++) 
  { res = div(r,i+k) ; r = res.quot ; x[m-i-1] = res.rem ; }
  for(i=0;i<m;i++)
  { k = buf[x[i]] ; for(j=x[i];j<m-i-1;j++) buf[j] = buf[j+1] ; x[i] = k ; }
}

static void ballotise(int *x,bitem *y,int n)
{ for(int i=0;i<n;i++) y[i] = bitem(x[i],'>') ; if(n) y[n-1].flag = 0 ; }

• genbeatcounts • marginalise • genmargins • genposcounts • randomcandidate • fptp • dblv • bucklin • borda • nauru • sbc2 • seq • contingent • condorcet • minimax • minimaxwv • minisum • knockout • spe • btrav • av • btr • benham • coombs • nansonbaldwin • nanson • baldwin • approvalsm • sinkhorn • schulze • simplenotifier

#include <math.h>
#include "memory.h"
#include "condorcet.h"

/* --------------------- precompute comparison matrices --------------------- */

int **genbeatcounts(bitem **bal,int *count,int nbal,int m) 
{ int i,j,ii,jj,ni,nj,v,balno,**rmat=imatrix(m,m),**ballot=imatrix(m,m+1),nrow ;
  for(balno=0;balno<nbal;balno++) 
  { nrow = parseballot(bal[balno],m,ballot) ; 
    v = count[balno] ;
    // for every row, for every subsequent row, every candidate in the first
    // row beats every candidate in the second, so increment the beat count
    for(i=0;i<nrow-1;i++) for(j=i+1;j<nrow;j++) 
      for(ii=0;ii<m&&ballot[i][ii]>=0;ii++) 
        for(jj=0;jj<m&&ballot[j][jj]>=0;jj++) 
          rmat[ballot[i][ii]][ballot[j][jj]] += v ;
  }
  freeimatrix(ballot) ; 
  return rmat ;
}
int **marginalise(int **r,int m)
{ int i,j,v,**rdash=imatrix(m,m) ; 
  for(i=0;i<m-1;i++) for(j=i+1;j<m;j++) 
  { v = r[i][j] - r[j][i] ; rdash[i][j] = v ; rdash[j][i] = -v ; }
  return rdash ;
}
// rmat[i][j] contains i's signed victory margin over j 
int **genmargins(bitem **bal,int *count,int nbal,int m) 
{ int **r=genbeatcounts(bal,count,nbal,m),**rdash=marginalise(r,m) ; 
  freeimatrix(r) ;
  return rdash ;
}
double **genposcounts(bitem **bal,int *count,int nbal,int m)
{ int i,j,k,c,nj,nvote,balno,pos,**ballot=imatrix(m,m+1),nrow ;  
  double v,**pmat=matrix(m,m) ;

  for(balno=0;balno<nbal;balno++) 
    for(nrow=parseballot(bal[balno],m,ballot),pos=i=0;i<nrow;i++,pos+=nj) 
  { for(nj=0;ballot[i][nj]>=0;nj++) ; 
    for(v=count[balno]/(double)nj,j=0;j<nj;j++) 
      for(c=ballot[i][j],k=pos;k<pos+nj;k++) pmat[c][k] += v ;
  }
  freeimatrix(ballot) ;
  return pmat ;
}
/* --------------------------- positional methods --------------------------- */

int randomcandidate(int m,double **r) { return 0 ; }

int fptp(int m,double **p,double *score) 
{ int i,imax ;
  double s,v ;
  for(i=0;i<m;i++) 
  { s = score[i] = p[i][0] ; if(i==0||s>v) { imax = i ; v = s ; } }
  return imax ; 
}
int dblv(int m,double **p,double *score) 
{ int i,imax ; 
  double v,s ; 
  for(i=0;i<m;i++) 
  { s = score[i] = p[i][0] + p[i][1] ; if(i==0||s>v) { imax = i ; v = s ; } }
  return imax ; 
}
int bucklin(int m,double **p)
{ int imax,i,k ;
  double *score=vector(m),qn,v ; 
  for(qn=i=0;i<m;i++) qn += p[0][i] ; 
  for(v=k=0;2*v<qn;k++)
  { for(i=0;i<m;i++) score[i] += p[i][k] ; 
    for(v=imax=i=0;i<m;i++) if(i==0||score[i]>v) { imax = i ; v = score[i] ; }
  }
  free(score) ; 
  return imax ; 
}
int borda(int m,double **p,double *qscore)
{ int i,j,imax ; 
  double v ; 
  for(i=0;i<m;i++) for(qscore[i]=j=0;j<m;j++) qscore[i] += ((m-1)-j)*p[i][j] ;
  for(v=imax=i=0;i<m;i++) if(i==0||qscore[i]>v) { imax = i ; v = qscore[i] ; }
  return imax ;   
}
int nauru(int m,double **p)
{ int i,j,imax ; 
  double q,v ; 
  for(i=0;i<m;i++) 
  { for(q=j=0;j<m;j++) q += p[i][j]/(1.0+j) ;
    if(i==0||q>v) { imax = i ; v = q ; } 
  }
  return imax ;   
}
int sbc2(int m,double **p)
{ int i,j,imax ; 
  double q,v,*w ; 
  static double w2[] = {1,0} ;
  static double w3[] = {2,0.89,0} ;
  static double w4[] = {3,1.82,0.82,0} ;
  static double w5[] = {4,2.75,1.71,0.84,0} ;
  static double w6[] = {5,3.71,2.61,1.66,0.86,0} ;
  static double w7[] = {6,4.69,3.54,2.54,1.68,0.89,0} ;
  static double w8[] = {7,5.66,4.49,3.46,2.56,1.75,0.93,0} ;
  static double w9[] = {8,6.64,5.41,4.34,3.41,2.57,1.76,0.92,0} ;
  static double wx[] = {9,7.65,6.38,5.27,4.28,3.39,2.58,1.81,0.96,0} ;
  if(m==2) w = w2 ; 
  else if(m==3) w = w3 ; 
  else if(m==4) w = w4 ; 
  else if(m==5) w = w5 ; 
  else if(m==6) w = w6 ; 
  else if(m==7) w = w7 ; 
  else if(m==8) w = w8 ; 
  else if(m==9) w = w9 ; 
  else if(m==10) w = wx ; 
  else throw up("m=%d not permitted for sbc2",m) ; 
  for(v=i=0;i<m;i++) 
  { for(q=j=0;j<m;j++) q += p[i][j] * w[j] ;
    if(i==0||q>v) { imax = i ; v = q ; } 
  }
  return imax ;   
}
/* -------------------------- other crude methods --------------------------- */

int seq(bitem **bal,int *count,int nbal,int m)
{ int lo,mid,hi,i,j,**ballot=imatrix(m,m+1),balno,nsel,nrow ;
  double v,qlo,qhi ; 

  for(lo=0,hi=m;hi>lo+1;)
  { mid = (lo+hi)/2 ; 
    for(qlo=qhi=balno=0;balno<nbal;balno++)
    { nrow = parseballot(bal[balno],m,ballot) ; 
      for(i=0;i<nrow;i++) 
      { for(nsel=j=0;ballot[i][j]>=0;j++) 
          if(ballot[i][j]>=lo&&ballot[i][j]<hi) nsel += 1 ; 
        if(nsel) break ; 
      }
      if(i<nrow) for(v=count[balno]/(double)nsel,j=0;ballot[i][j]>=0;j++) 
        if(ballot[i][j]>=lo&&ballot[i][j]<hi) 
      { if(ballot[i][j]<mid) qlo += v ; else qhi += v ; }
    }
    if(qlo>=qhi) hi = mid ; else lo = mid ; 
  }
  freeimatrix(ballot) ; 
  return lo ; 
}
int contingent(int m,int **r,double **p)
{ int i,f0,f1 ; 
  if(m==1) return 0 ; 
  for(f1=f0=-1,i=0;i<m;i++)
    if(f0<0||p[i][0]>p[f0][0]) { f1 = f0 ; f0 = i ; }
    else if(f1<0||p[i][0]>p[f1][0]) f1 = i ; 
  if(r[f0][f1]>=0) return f0 ; else return f1 ;
}
/* ------------------------- simple margin methods -------------------------- */

int condorcet(int m,int **r)
{ int i,j ; 
  for(i=0;i<m;i++) 
  { for(j=0;j<m&&(j==i||r[i][j]>0);j++) ; if(j==m) return i ; }
  return -1 ;
}
int minimax(int m,int **r,double *qscore)
{ int i,j,imax,v,flag ; 
  for(i=0;i<m;i++) for(flag=j=0;j<m;j++) 
    if(i!=j&&(flag==0||r[i][j]<qscore[i])) { qscore[i] = r[i][j] ; flag = 1 ; }
  for(v=imax=i=0;i<m;i++) if(i==0||qscore[i]>v) { imax = i ; v = qscore[i] ; }
  return imax ;  
}
int minimaxwv(int m,int **r)
{ int i,j,flag,most,minmost,winner ; 
  for(winner=-1,minmost=i=0;i<m;i++) 
  { for(most=flag=j=0;j<m;j++) if(i!=j)
      if(r[j][i]>r[i][j]&&(!flag||r[j][i]>most)) { flag = 1 ; most = r[j][i] ; }
    // so most is the max prefs over i given to any candidate j who is 
    // preferred to i
    if(winner<0||most<minmost) { winner = i ; minmost = most ; }
  }
  return winner ;  
}
int minisum(int m,int **r)           // should redefine in terms of margin by 
{ int i,j,imax,v,*iscore=ivector(m) ;// which a candidate falls short of victory
  for(i=0;i<m;i++) for(iscore[i]=0,j=0;j<m;j++) 
    if(i!=j&&r[i][j]<0) iscore[i] += r[i][j] ; 
  for(v=imax=i=0;i<m;i++) if(i==0||iscore[i]>v) { imax = i ; v = iscore[i] ; }
  free(iscore) ; 
  return imax ;
}
int knockout(int m,int **r)
{ int i,winner ; 
  for(winner=0,i=1;i<m;i++) if(r[i][winner]>0) winner = i ; 
  return winner ;
}
int spe(bitem **bal,int *count,int nbal,int m,int **r)
{ int i,j,nj,balno,**ballot=imatrix(m,m+1),nrow,winner ; 
  double q ;
  xi *list=xivector(m) ; 
  for(i=0;i<m;i++) list[i] = xi(0,i) ;

  for(balno=0;balno<nbal;balno++)
  { nrow = parseballot(bal[balno],m,ballot) ; 
    for(nj=0;ballot[0][nj]>=0;nj++) ; 
    for(q=1.0/nj,j=0;j<nj;j++) list[ballot[0][j]].x += q ; 
  }
  xisort(list,m) ; 
  for(winner=list[0].i,i=1;i<m;i++) 
    if(r[list[i].i][winner]>0) winner = list[i].i ; 
  freeimatrix(ballot) ; free(list) ; 
  return winner ;
}
/* --------------------------------- btr/av --------------------------------- */

int btrav(bitem **bal,int *count,int nbal,int m,int **r,double *avscr,int opt)
{ int t,tau,balno,winner,loser,lose2,mleft,i,j,nj,*alive=ivector(m) ;
  double v,*qscore=vector(m) ; 
  bitem **b = bmatrix(nbal,m) ;
  for(balno=0;balno<nbal;balno++) expandballot(bal[balno],b[balno],m) ;
  for(i=0;i<m;i++) alive[i] = i ; 

  for(mleft=m;mleft>1;mleft--) // mleft is the number of remaining candidates
  { if(opt==2)                 // benham
    { for(i=0;i<mleft;i++)     // is alive[i] a condorcet winner among remainers
      { for(t=j=0;j<mleft;j++) if(j!=i&&r[alive[i]][alive[j]]>0) t += 1 ; 
        if(t==mleft-1) break ; // if this is satisfied then b[0][i] is winner 
      }
      if(i<mleft) { alive[0] = alive[i] ; break ; }
    }
    for(balno=0;balno<m;balno++) qscore[balno] = 0 ; 
    for(balno=0;balno<nbal;balno++) 
    { for(nj=1;b[balno][nj-1].flag=='=';nj++) ; 
      for(v=count[balno]/(double)nj,j=0;j<nj;j++) qscore[b[balno][j].c] += v ;
    }
    for(v=loser=t=0;t<mleft;t++) if(t==0||qscore[alive[t]]<v) 
    { loser = alive[t] ; v = qscore[loser] ; }
    if(opt==1)
    { for(v=lose2=-1,t=0;t<mleft;t++) if(alive[t]!=loser) 
        if(v<0||qscore[alive[t]]<v) { lose2 = alive[t] ; v = qscore[lose2] ; }
      if(r[loser][lose2]>0) loser = lose2 ; 
    }
    if(avscr) avscr[loser] = m-mleft ; 
    for(balno=0;balno<nbal;balno++) 
      squeezeballot(b[balno],b[balno],mleft,loser) ; 
    for(j=i=0;i<mleft;i++) if(alive[i]!=loser) alive[j++] = alive[i] ; 
  }
  winner = alive[0] ;
  if(avscr) avscr[winner] = m-1 ; 
  free(qscore,alive) ; freebmatrix(b) ; 
  return winner ;
}
int av(bitem **bal,int *count,int nbal,int m,double *avscr) 
{ return btrav(bal,count,nbal,m,0,avscr,0) ; }
int btr(bitem **bal,int *count,int nbal,int m,int **r) 
{ return btrav(bal,count,nbal,m,r,0,1) ; }
int benham(bitem **bal,int *count,int nbal,int m,int **r) 
{ return btrav(bal,count,nbal,m,r,0,2) ; }

/* --------------------------------- coombs --------------------------------- */

int coombs(bitem **bal,int *count,int nbal,int m)
{ int i,j,ni,nj,tau,n,balno,winner,loser,mleft,nrow,*alive=ivector(m) ; 
  double v,*qscore=vector(m) ;
  bitem **b=bmatrix(nbal,m) ;
  for(balno=0;balno<nbal;balno++) expandballot(bal[balno],b[balno],m) ; 

  for(n=balno=0;balno<nbal;balno++) n += count[balno] ; 
  for(i=0;i<m;i++) alive[i] = i ; 

  for(mleft=m;mleft>0;mleft--)
  { for(balno=0;balno<m;balno++) qscore[balno] = 0 ; 
    for(balno=0;balno<nbal;balno++) 
    { for(nj=1;b[balno][nj-1].flag=='=';nj++) ; 
      for(v=count[balno]/(double)nj,j=0;j<nj;j++) qscore[b[balno][j].c] += v ;
    }
    for(v=winner=i=0;i<mleft;i++) if(i==0||qscore[alive[i]]>v) 
    { winner = alive[i] ; v = qscore[winner] ; }
    if(2*v>n) break ; 
    for(i=0;i<m;i++) qscore[i] = 0 ; 
    for(balno=0;balno<nbal;balno++) 
    { for(j=mleft-1;j>0&&b[balno][j-1].flag=='=';j--) ;
      for(v=count[balno]/(double)(mleft-j);j<mleft;j++) 
        qscore[b[balno][j].c] += v ;
    }
    for(v=loser=i=0;i<mleft;i++) if(i==0||qscore[alive[i]]>v) 
    { loser = alive[i] ; v = qscore[loser] ; }
    for(balno=0;balno<nbal;balno++) 
      squeezeballot(b[balno],b[balno],mleft,loser) ; 
    for(j=i=0;i<mleft;i++) if(alive[i]!=loser) alive[j++] = alive[i] ; 
    winner = alive[0] ;
  }
  free(qscore,alive) ; freebmatrix(b) ; 
  return winner ;
}
/* --------------------------------- nansen --------------------------------- */

int nansonbaldwin(bitem **bal,int *count,int nbal,int m,
                  double *bordascore,int flag)
{ int i,j,k,t,balno,mleft,*ind=ivector(m),*set=ivector(m),nset,nrow ;  
  int **ballot=imatrix(m,m+1) ;  
  double v,*score=vector(m),**pmat ;
  bitem **b=bmatrix(nbal,m) ;
  for(i=0;i<m;i++) { score[i] = bordascore[i] ; set[i] = i ; }
  for(i=0;i<nbal;i++) expandballot(bal[i],b[i],m) ; 

  for(mleft=m;;mleft=nset) // mleft is the number of remaining candidates in set
  { if(flag) // baldwin
    { for(v=i=0;i<mleft;i++) if(i==0||score[i]<v) { k = i ; v = score[i] ; }
      for(nset=i=0;i<mleft;i++) if(i!=k) ind[nset++]= set[i] ; 
    }
    else // nanson
    { for(v=i=0;i<mleft;i++) v += score[i] ;
      for(nset=i=0;i<mleft;i++) if(score[i]*mleft>v) ind[nset++] = set[i] ;
      if(nset==0) { ind[0] = set[0] ; nset = 1 ; } // all borda scores equal
    }
    for(i=0;i<nset;i++) set[i] = ind[i] ; 
    if(nset==mleft||nset==1) { k = set[0] ; break ; }
    for(i=0;i<m;i++) ind[i] = -1 ; // ind gives the indices of candidates in set
    for(k=i=0;i<nset;i++) ind[set[i]] = k++ ; 

    for(balno=0;balno<nbal;balno++) 
    { nrow = parseballot(bal[balno],m,ballot) ; 
      for(i=0;i<nrow;i++) 
      { for(t=j=0;ballot[i][j]>=0;j++)
        { k = ind[ballot[i][j]] ; if(k>=0) ballot[i][t++] = k ; } 
        ballot[i][t] = -1 ; 
      }
      unparseballot(b[balno],m,ballot,nrow) ; 
    }
    pmat = genposcounts(b,count,nbal,nset) ; 
    borda(nset,pmat,score) ; 
    freematrix(pmat) ; 
  }
  free(score,set,ind) ; freebmatrix(b) ; freeimatrix(ballot) ; 
  return k ;
}
int nanson(bitem **bal,int *count,int nbal,int m,double *bordascore)
{ return nansonbaldwin(bal,count,nbal,m,bordascore,0) ; }
int baldwin(bitem **bal,int *count,int nbal,int m,double *bordascore)
{ return nansonbaldwin(bal,count,nbal,m,bordascore,1) ; }

/* ----------------------------------- asm ---------------------------------- */

int approvalsm(bitem **bal,int *count,int nbal,int m,int **A)
{ int i,j,nj,iter,balno,imax,D,*r=ivector(m),nrow,nseen,u ;
  int **ballot=imatrix(m,m+1) ;
  double *T=vector(m),v ; 
  xi *pref=xivector(m) ;  

  for(balno=0;balno<nbal;balno++) 
  { nrow = parseballot(bal[balno],m,ballot) ; 
    for(nseen=i=0;i<nrow&&nseen<m/2;i++,nseen+=nj)
    { for(nj=0;ballot[i][nj]>=0;nj++) ; 
      v = count[balno] ;
      if(nseen+nj>m/2) v *= (m/2-nseen) / (double) nj ;
      for(j=0;j<nj;j++) T[ballot[i][j]] += v ;
    }
  }
  for(i=0;i<m;i++) pref[i] = xi(T[i],i) ; 
  xisortdown(pref,m) ; 
  for(i=0;i<m;i++) r[i] = pref[i].i ;
  for(iter=0;;iter++)
  { for(u=imax=-1,i=0;i<m-1;i++) if(A[r[i]][r[i+1]]<0)
    { D = T[r[i]] - T[r[i+1]] ; if(imax<0||D<u) { imax = i ; u = D ; } }
    if(imax>=0) swap(r[imax],r[imax+1]) ; else break ; 
  }
  imax = r[0] ; 
  free(T,r,pref) ; freeimatrix(ballot) ; 
  return imax ; 
}
/* --------------------------------- sinkhorn ------------------------------- */

// this depends on the margins plus the total number of voters

int sinkhorn(bitem **bal,int *count,int nbal,int m,int **margin)
{ int i,j,iter,i0,i1,nv ;
  double q,rho,orho,**u=matrix(m,m),*r=vector(m),*c=vector(m),*s=vector(m) ; 

  for(nv=i=0;i<nbal;i++) nv += count[i] ; 
  for(i=0;i<m;i++) for(j=0;j<m;j++) u[i][j] = (margin[i][j]+nv)/2.0 + 1 ; 
  for(i=0;i<m;i++) r[i] = c[i] = 1 ; 

  for(iter=0;iter<10||fabs((rho/orho)-1)>fabs(rho-1)*1e-6;orho=rho,iter++) 
  { // balance the rows
    for(i=0;i<m;i++) { for(s[i]=j=0;j<m;j++) s[i] += u[i][j] ; s[i] = 1/s[i] ; }
    for(i=0;i<m;i++) { r[i] *= s[i] ; for(j=0;j<m;j++) u[i][j] *= s[i] ; }
    // balance the cols
    for(j=0;j<m;j++) { for(s[j]=i=0;i<m;i++) s[j] += u[i][j] ; s[j] = 1/s[j] ; }
    for(j=0;j<m;j++) { c[j] *= s[j] ; for(i=0;i<m;i++) u[i][j] *= s[j] ; }
    // compute the scores and find the best two candidates
    for(i1=i0=-1,i=0;i<m;i++) 
    { s[i] = c[i] / r[i] ;
      if(i0<0||s[i]>s[i0]) { i1 = i0 ; i0 = i ; }
      else if(i1<0||s[i]>s[i1]) i1 = i ; 
    }
    rho = s[i0]/s[i1] ; // will terminate when rho is barely moving
  }

  freematrix(u) ; free(r,c,s) ; 
  return i0 ; 
}
/* --------------------------------- schulze -------------------------------- */

/* Based on Warren D. Smith's code at https://rangevoting.org/IEVS/IEVS.c
   m = number of candidates, margin = matrix of victory margins
   winner = X st. beatpath strength over rivals Y exceeds strength from Y 
*/
int schulze(int m,int **margin)
{ int i,j,k,**strength=imatrix(m,m) ;
  for(i=0;i<m;i++) for(j=0;j<m;j++) strength[i][j] = margin[i][j] ;
  for(i=0;i<m;i++) for(j=0;j<m;j++) if(i!=j) for(k=0;k<m;k++) if(k!=i&&k!=j)
    strength[j][k] = max(strength[j][k],min(strength[j][i],strength[i][k])) ;

  // if there's no (j,i) stronger than (i,j) then i is the winner
  for(i=0;i<m;i++) { for(j=0;j<m&&strength[i][j]>=0;j++) ; if(j==m) break ; }
  if(i==m) throw up("logic error in schulze: no winner found") ; 
  freeimatrix(strength) ; 
  return i ;
}
/* ------------------------------ simplenotifier ---------------------------- */

int rankedpairs(bitem **bal,int *count,int nbal,int m,int **margin) ;
int river(int m,int **r) , wbc(int m,double **p) ;
int tideman(bitem **,int *count,int nbal,int m,int **rmat,int *set,int nset) ;

int simplenotifier()
{ notify(randomcandidate,"random","rC") ; 
  notify(fptp,"fptp","frC") ; 
  notify(dblv,"dblv","fC2") ; 
  notify(seq,"seq","x") ; 
  notify(contingent,"conting","2Cr") ; 
  notify(nauru,"nauru","") ; 
  notify(borda,"borda","Cfr") ; 
  notify(sbc2,"sbc2","o") ;         // optional because limited to 10 candidates
  notify(bucklin,"bucklin","") ; 
  notify(sinkhorn,"sinkhorn","o") ; // optional because expensive
  notify((void *)0,"mj","oxy",-1) ;
  notify(av,"av","oCrf") ;          // optional because expensive tactically
  notify(coombs,"coombs","o") ;     // optional because expensive tactically

  notify((void *)0,"clower","cx",-1) ;
  notify(knockout,"knockout","c") ; 
  notify(spe,"spe","c") ; 
  notify(benham,"benham","c") ; 
  notify(btr,"btr-irv","c") ; 
  notify(baldwin,"baldwin","cb") ; 
  notify(nanson,"nanson","cb") ; 
  notify(minimax,"minimax","cfr") ;
  notify(minimaxwv,"minimaxwv","ceY") ;
  notify(minisum,"minisum","c") ;
  notify(rankedpairs,"rp","co") ;    // optional because expensive when trunked
  notify(river,"river","c2") ;   
  notify(schulze,"schulze","c") ; 
  notify(approvalsm,"asm","c") ; 
  notify((void *)0,"cupper","cx",-1) ;
  notify(tideman,"tideman","c") ; 
  return 0 ; 
}
/* -------------------------------------------------------------------------- */

• tideman • setdom • rprec • rankedpairs • river

#include "memory.h"
#include "condorcet.h"
#include <stdlib.h>

/* --------------------------- tideman's alternative ------------------------ */

int tideman(bitem **bal,int *count,int nbal,int m,int **rmat,int *set,int nset)
{ if(nset==1) return set[0] ; 
  int i,j,nj,balno,ns=nset,imin,*s=ivector(nset),**ballot=imatrix(m,m+1) ;
  int nseen,nrow,*map=ivector(m),**r=imatrix(nset,nset),*lscore=ivector(m) ;
  double v,*score=vector(m) ;
  for(i=0;i<ns;i++) s[i] = set[i] ; 

  while(ns>1) 
  { for(i=0;i<m;i++) score[i] = map[i] = 0 ; 
    for(i=0;i<ns;i++) map[s[i]] = 1 ; 
    for(balno=0;balno<nbal;balno++)
    { nrow = parseballot(bal[balno],m,ballot) ;
      for(nseen=i=0;i<nrow&&nseen==0;i++)
      { for(nj=0;ballot[i][nj]>=0;nj++) if(map[ballot[i][nj]]) nseen += 1 ; 
        if(nseen) for(v=count[balno]/(double)nseen,j=0;j<nj;j++) 
          if(map[ballot[i][j]]) score[ballot[i][j]] += v ;
      } 
    }
    for(i=0;i<ns;i++) if(i==0||score[s[i]]<score[s[imin]]) imin = i ; 
    for(j=i=0;i<ns;i++) if(i!=imin) s[j++] = s[i] ; 
    ns -= 1 ; 
    if(ns==1) break ; 
    // now we have to recompute the smith set - first compute the margins
    for(i=0;i<ns;i++) for(lscore[i]=j=0;j<ns;j++) 
    { r[i][j] = rmat[s[i]][s[j]] ; if(r[i][j]>0) lscore[i] += 1 ; }
    ns = smithset(ns,r,lscore,map) ; // map gets the smithset of the reduced fld
    for(i=0;i<ns;i++) lscore[i] = s[map[i]] ; // find the elts of the smith set
    for(i=0;i<ns;i++) s[i] = lscore[i] ;      // and put them in s
    isortup(s,ns) ;                           // keep them in random order
  }
  i = s[0] ;
  free(s,score,map,lscore) ; freeimatrix(r,ballot) ; 
  return i ; 
}
/* -------------------------------- ranked pairs ---------------------------- */

#define setdom(a,b,c) { a[b][c] = 1 ; a[c][b] = -1 ; }

int rprec(xi *maj,int m,int npair,int level,int fixed,int **idom)
{ int i,j,k,hi,lo,mi,mx,n,*set,*ind,res,**dom=imatrix(m,m) ; 
  if(idom) for(i=0;i<m;i++) for(j=0;j<m;j++) dom[i][j] = idom[i][j] ; 
  for(k=level;k<npair;k++)   
  { mx = maj[k].x ; 
    mi = maj[k].i ;
    if(k<fixed||k==npair-1||maj[k+1].x<mx) // easy case  
    { hi = mi >> 8 ; 
      lo = mi & 0xff ; 
      if(dom[hi][lo]==0) 
      { setdom(dom,hi,lo) ; 
        for(i=0;i<m;i++) 
        { if(dom[i][hi]>0) setdom(dom,i,lo) ; 
          if(dom[lo][i]>0) setdom(dom,hi,i) ; 
        }
      }
    }
    else // several equal majorities - need to recurse over possible orders
    { set = ivector(npair-k) ;
      ind = ivector(npair-k) ;
      for(set[0]=mi,n=1;k+n<npair&&maj[k+n].x==mx;n++) set[n] = maj[k+n].i ; 
      if(n>12) throw up("too many tied majorities (%d) in rankedpairs",n) ;
      for(res=0,i=factorial(n)-1;i>=0;i--)
      { ithperm(i,ind,n) ; 
        for(j=0;j<n;j++) maj[k+j].i = set[ind[j]] ; 
        res |= rprec(maj,m,npair,k,k+n,dom) ; 
      }
      free(ind,set) ;
      break ;
    }
  }
  if(k==npair) for(res=i=0;i<m;i++) // reached a leaf - find possible winners
  { for(j=0;j<m&&dom[j][i]<=0;j++) ; if(j==m) res |= 1<<i ; }
  freeimatrix(dom) ; 
  return res ; 
}
int rankedpairs(bitem **bal,int *count,int nbal,int m,int **margin)
{ int i,j,k,npair,res ;
  xi *maj = xivector((m*(m-1))/2) ; 
  for(npair=i=0;i<m-1;i++) for (j=i+1;j<m;j++)
    if(margin[i][j]>0) maj[npair++] = xi(margin[i][j],(i<<8)|j) ; 
    else if(margin[i][j]<0) maj[npair++] = xi(-margin[i][j],(j<<8)|i) ; 
  xisortdown(maj,npair) ; 
  res = rprec(maj,m,npair,0,0,0) ;
  free(maj) ; 
  for(k=-1,i=0;k<0&&i<m;i++) 
  { j = bal[0][i].c ; if(res&(1<<j)) k = j ; if(bal[0][i].flag==0) break ; }
  if(k>=0) return k ; else return 0 ; 
}
/* ----------------------------------- river -------------------------------- */

int river(int m,int **r)
{ int i,j,k,npair,res,**dom=imatrix(m,m),hi,lo,mi,iter ;
  xi *maj = xivector((m*(m-1))/2) ; 
  for(npair=i=0;i<m;i++) 
  { for(k=npair,j=0;j<m;j++) 
      if(r[i][j]<0) maj[npair++] = xi(-r[i][j],(j<<8)|i) ; 
    if(npair>k) { xisortdown(maj+k,npair-k) ; npair = min(npair,k+2) ; }
  }
  xisortdown(maj,npair) ; 

  for(i=0;i<npair;i++)   
  { mi = maj[i].i ;
    lo = mi >> 8 ; 
    hi = mi & 0xff ; 
    if(dom[hi][lo]==0) 
    { setdom(dom,hi,lo) ; 
      for(j=0;j<m;j++) 
      { if(dom[j][hi]>0) setdom(dom,j,lo) ; 
        if(dom[lo][j]>0) setdom(dom,hi,j) ; 
      }
    }
  }
  for(k=-1,i=0;k<0&&i<m;i++) for(j=0;k<0&&j<m;j++) if(dom[i][j]>0) k = j ; 
  for(iter=i=0;i>=0&&iter<=m;iter++) 
  { for(i=-1,j=0;i<0&&j<m;j++) if(dom[k][j]>0) i = k = j ; }
  if(iter==m) throw up("infinite loop in river") ; 
  free(maj) ; freeimatrix(dom) ; 
  return k ; 
}

condorcetformat is a standalone program to convert condorcet output to HTML for inclusion in this page. You put the output from condorcet into a file, say res.txt, and run

condorcetformat res.txt [option]

where the option can be “links” to provide links for the voting methods or “borda” to highlight borda results rather than minimax.

#include "memory.h"
#include <string.h>
#include <ctype.h>

int main(int argc,char **argv)
{ char *href[] = 
    { "fptp" , "https://en.wikipedia.org/wiki/First-past-the-post_voting" ,
      "dblv" , "#dblv" ,
      "seq" , "#seq" ,
      "conting" , "#conting" ,
      "nauru" , 
          "https://en.wikipedia.org/wiki/Borda_count#Dowdall_system_(Nauru)" ,
      "borda" , "https://en.wikipedia.org/wiki/Borda_count" ,
      "sbc2" , "#sbc2" ,
      "spe" , "#spe" ,
      "bucklin" , "https://en.wikipedia.org/wiki/Bucklin_voting" ,
      "sinkhorn" , 
          "https://rangevoting.org/WarrenSmithPages/homepage/sinkhornv.pdf" ,
      "mj" , "https://en.wikipedia.org/wiki/Majority_judgment" ,
      "av" , "https://en.wikipedia.org/wiki/Instant-runoff_voting" ,
      "coombs" , "https://en.wikipedia.org/wiki/Coombs%27_method" ,
      "clower" , "#condorcetdef" ,
      "knockout" , "#knockout" ,
      "benham" , "https://electowiki.org/wiki/Benham%27s_method" ,
      "btr-irv" , "https://electowiki.org/wiki/Bottom-Two-Runoff_IRV" ,
      "baldwin" , 
          "https://en.wikipedia.org/wiki/Nanson%27s_method#Baldwin_method" ,
      "nanson" , "https://en.wikipedia.org/wiki/Nanson%27s_method" ,
      "minimax" , "https://en.wikipedia.org/wiki/Minimax_Condorcet_method" ,
      "minisum" , "#minisum" ,
      "rp" , "https://en.wikipedia.org/wiki/Ranked_pairs" ,
      "river" , "https://electowiki.org/wiki/River" ,
      "schulze" , "https://en.wikipedia.org/wiki/Schulze_method" ,
      "asm" , "https://electowiki.org/wiki/Approval_Sorted_Margins" ,
      "tideman" , "https://en.wikipedia.org/wiki/Tideman_alternative_method" ,
      "cupper" , "#condorcetdef" ,
      "condorcet+" , "https://en.wikipedia.org/wiki/Condorcet_method" ,
      "llull+" , "https://en.wikipedia.org/wiki/Copeland%27s_method" ,
      "smith+" , "https://en.wikipedia.org/wiki/Smith_set" , 0 , 0 } ; 

  char *l,*ll,**line[20],*cminimax="minimax",cl,*hdr[2] ; 
  int nline,flag,i,j,k,ntoken,iter,iminimax,lino,len[20],base,minx,links=0 ; 
  double q,qminimax,qmax ; 
  if(argc<2) { printf("%s filename",argv[0]) ; return 0 ; }
  FILE *ifl=fopenread(argv[1]) ; 
  if(argc>=3)
  { if(strcmp(argv[2],"links")==0) links = 1 ; 
    else if(strcmp(argv[2],"borda")==0) cminimax = "borda" ; 
  }

  for(flag=nline=0;(l=freadline(ifl))&&nline<20;) // collect data
  { if(!strncmp(l,"percentages",11)) { hdr[0] = l ; flag = 1 ; continue ; }
    if(!strncmp(l,"mean loss",9)) { hdr[1] = l ; continue ; }
    if(flag==0) continue ; 
    for(i=0;l[i]&&isspace(l[i]);i++) ; 
    if(l[i]==0) { free(l) ; continue ; }
    line[nline] = strvector(strlen(l)) ;
    line[nline][0] = l = strtok(l," \n") ;
    for(ntoken=1;l;) line[nline][ntoken++] = l = strtok(0," \n") ;
    len[nline++] = ntoken-1 ;
  }

  for(iter=0;iter<2;iter++) // shift tideman
  { base = 2 + 10*iter ;
    for(i=0;i<len[base+6]&&strcmp(line[base+6][i],"tideman");i++) ;
    if(i==len[base+6]) continue ; 
    for(j=0;j<2;j++,base++) 
    { line[base][len[base]] = line[base][len[base]-1] ;
      line[base][len[base]-1] = line[base+6][i-j] ; 
      len[base] += 1 ; 
      for(k=i-j;k<len[base+6]-1;k++) line[base+6][k] = line[base+6][k+1] ;
      len[base+6] -= 1 ; 
    }
  }

  for(iter=0;iter<2;iter++) 
  { if(strcmp(cminimax,"borda")==0) minx = 0 ; else minx = 2 ;
    minx += base = 10 * iter ;
    for(qminimax=i=0;i<len[minx]&&strcmp(line[minx][i],cminimax);i++) ;
    iminimax = i ; 
    qminimax = atof(line[minx+1][iminimax]) ; 
    for(qmax=iter*1000000,lino=1+base;lino<11+base;lino+=2) 
      for(i=0;i<len[lino];i++) if(strcmp(line[lino][i],"-")) 
        if(lino!=3+base||i<len[lino]-1)
    { q = atof(line[lino][i]) ;
      if((iter==0&&q>qmax)||(iter>0&&q<qmax)) qmax = q ; 
    }
    printf("<p><table cellpadding=0 cellspacing=0>\n") ; 
    if((l=strstr(hdr[iter],"||"))) 
    { if((ll=strchr(l+3,'\n'))) ll[0] = 0 ; printf("<!-- %s -->\n",l+3) ; }
    for(lino=base;lino<10+base;lino++) 
    { printf("<tr>") ; 
      if(lino%2==0) 
      { if(lino!=base&&lino!=base+2) k = 0 ; 
        else { k = -1 ; printf("<td class=c>&nbsp; ") ; }
        for(i=0;i<len[lino];i++)
        { l = line[lino][i] ; 
          if(i>0) if((i-k)%4==0) printf("    ") ;
          if(i==0&&lino>=2) 
          { printf("<td class=r>") ; 
            if(links)
            { for(k=0;href[2*k]&&strcmp(l,href[2*k]);k++) ;
              if(href[2*k]) 
              { printf("<a href=\"%s\">%s</a>\n",href[2*k+1],l) ; l = 0 ; }
            }
          }
          else if(iter==0&&links&&(lino==0||lino==2)) 
          { printf("<td class=c>") ; 
            for(k=0;href[2*k]&&strcmp(l,href[2*k]);k++) ;
            if(href[2*k]) 
            { printf("<a href=\"%s\">%s</a>\n",href[2*k+1],l) ; l = 0 ; }
          }
          else printf("<td class=c>") ;
          if(l) printf("%s ",l) ; 
          if(l) if((i-k)%4==3||i==len[lino]-1) printf("\n") ; 
        }
      }
      else for(i=-1;i<len[lino];i++)
      { if(i>0) if(i%4==3) printf("    ") ;
        cl = 0 ;
        if(i>=0)
        { if(!strcmp(line[lino][i],"-")) cl = 'c' ;
          else if(strcmp(line[lino-1][i],"cupper")) 
          { q = atof(line[lino][i]) ;
            if(q!=qmax) if((iter==0&&q>qminimax)||(iter>0&&q<qminimax))
              cl = 'x' ;
            if(lino==1+minx&&i==iminimax) cl = 'm' ;
          }
        }
        if(cl) printf("<td class=%c>",cl) ; else printf("<td>") ; 
        if(i<0) printf("&nbsp; ") ; 
        else if(!strcmp(line[lino][i],"-")) printf("&ndash; ") ; 
        else if(q==qmax) printf("<u>%s</u> ",line[lino][i]) ; 
        else printf("%s ",line[lino][i]) ; 
        if(i>=0) if(i%4==2||i==len[lino]-1) printf("\n") ; 
        if(lino!=9+base&&i==len[lino]-1) printf("\n") ;
      }
    }
    printf("</table>\n\n") ; 
  }
}

During the first year I made occasional modifications as the need arose without taking much care to record them.

This was quite a large revision. I added the option to force truncation. This is partly because it seems to be of some significance, but also because it tied in with a change to my ballot format. I originally ensured that all ballots would be strict orderings, and expected voting methods to be written on that assumption. However that limits their flexibility, so I changed the format to allow ties (with truncation being an example); consequently voting methods which can be evaluated by condorcet will be written in a more general (but admittedly more onerous) way.

I added ‘spe’.

I added ‘wbc’. Ranked pairs had been dropped by mistake from the list of notifications (because it’s slow when there is truncation). I reinstated it as optional.

Another large revision. Its purpose was to move the utility functions to a separate utils page while adding a couple of new methods, sbc2 and conting as a tie-break. At the same time I broke out ranelection into a separate file and wrote condorcetformat to relieve the pain of tabulating new results. ranelection was considerably restructured. I added dim as a program argument. Some of the newly available options have not been tested.

When rerunning my tests I found that an anomalously good result for Tideman’s alternative had disappeared, and this it now behaves more consistently. This must have been the consequence of an earlier change, and I couldn’t be bothered to pursue it.

I added a slew of variable truncation methods and ‘minimaxwv’ as a voting method. These changes required some code reorganisation.

Redefine minisum.
Write a radix sort for doubles.
Rethink random tie breaks.
Rethink the tactical voting condition “dist[cres[i]]>dist[res[i]]”.

	random	fptp	dblv	seq	conting	nauru	borda	sbc2	bucklin	sinkhorn	mj	av	coombs
	11.1027	30.9728	45.4295	41.4320	50.6048	57.0026	84.1508	88.9993	70.6870	81.8214	85.6950	53.0478	90.1082
	clower	knockout	spe	benham	btr-irv	baldwin	nanson	minimax	minisum	rp	river	schulze	asm	tideman	cupper
	93.3844	93.6063	93.6547	93.5641	93.6363	93.6424	93.7199	93.7514	93.7502	93.7344	93.7344	93.5845	93.6520	93.5395	94.0696
condorcet+	random	fptp	dblv	conting	borda	av
	93.4574	93.5176	93.5837	93.5469	93.7325	93.5647
llull+	randomr	fptpf	fptpr	dblvf	contingr	bordaf	bordar	avf	avr	minimaxf	minimaxr
	93.6238	93.6249	93.6684	93.6608	93.5700	93.7353	93.7430	93.6168	93.5700	93.7475	93.7134
smith+	randomr	fptpf	fptpr	dblvf	contingr	bordaf	bordar	avf	avr	minimaxf	minimaxr
	93.5845	93.5978	93.6667	93.6351	93.5405	93.7350	93.7925	93.5870	93.5386	93.7515	93.7515