An antifragile vote counting system should be open-source. Why not use Julia?

I posted an essay (No Abacus or Pillow) detailing how the manual counting of ballots can rival the speed of the automated counting of ballots … provided those ballots are sorted. In the essay’s appendix is a listing of a short Julia script demonstration. I appreciate the speed and clarity of Julia and, perhaps even more important, Julia has an excellent reputation among tinkerers. Tinkering seems to be the proper mindset to implement much needed innovations in vote counting software.

For example, to counter false claims about fraudulent votes getting entered in “big dumps” in the middle of the night or false claims about thousands of unregistered voters (some dead) voting, perhaps there can be a formal approach to clearly document the expected/actual timing of vote counting events and the expected/actual turnout of registered voters … something like double entry bookkeeping but for voting.

# in response to a cheeky question by Rachel Maddow in
# a news story about a locality's new voting regulation
# requiring all their voting ballots be counted manually:
# if they're not allowed to use automated ballot counting
# machines, what will they use? An abacus and a My Pillow?
# This nap.jl code is just a prototype to demonstrate
# that the sorting of ballots and the counting of duplicate
# ballots is faster than counting each ballot individually.
# Some tinkering with this prototype code would be needed
# to implement voting options such as
# 1. rank order voting,
# 2. random ordering of choices,
# 3. write-in ballots,
# 4. a double-entry accounting system for ballots,
# 5. ballot images taken with smartphone camera instead of
#    flatbed scanner.
# A ballot configuration text file specifies the largest
# possible value for each ballot item. For example, the
# following ballot.txt configuration file specifies that
# item 1's max value is 3, item 2's max value is 2, and
# item 3's max value is 4.
using DelimitedFiles
using Printf

# index VS to index D conversion
# arg iVS: row Index into Vote Sorted matrix
# arg VS: Vote Sorted matrix
# arg BVI: Ballot configuration Vector Incremented
function ivs2id(
	nItem = length(BVI)
	iD = 1
	nStep = 1
	for iItem=nItem:-1:1
		iD += VS[iVS,iItem]*nStep
		nStep *= BVI[iItem]
	return iD
end # ivs2id()

# index D to count matrix conversion
# arg iD: index into Duplicate count matrix
# arg D: Duplicate count matrix
# arg BVI: Ballot configuration Vector Incremented
# arg C: ballot Count matrix
function id2c(
	nItem = length(BVI)
	nDup = D[iD]
	iD -= 1
	for iItem = nItem:-1:1
		nStep = BVI[iItem]
		C[mod(iD,nStep)+1,iItem] += nDup
		iD = div(iD,nStep)
end # id2c()

# prototype of No Abacus or Pillow
# arg nVote: # of vote ballots generated and counted
# arg verbosity: level of debugging verbosity
#	0: minimal number of printouts
#	1: maximal number of printouts
# arg fn: filename of ballot.txt configuration file
function nap(
	# read ballot configuration text file
	B = readdlm(fn, Int8) # Ballot matrix
	print("B is "); display(B)
	# generate random votes
	nItem = size(B,1)
	V = rand(0:B[1],nVote) # Vote matrix
	for iItem = 2:nItem
		V = hcat(V, rand(0:B[iItem],nVote))
	V = Int8.(V)
	if verbosity > 0
		print("V is "); display(V)
		println("nVote: $nVote")
	# sort votes
	VS = sortslices(V,dims=1) # Vote matrix Sorted
	if verbosity > 0
		print("VS is "); display(VS)
	# count duplicates
	BVI = B[:,1] .+ Int8(1) # Ballot Vector Incremented
	nD = prod(BVI)
	D = zeros(Int64,1,nD) # Dup matrix
	iVSU = 1 # index of first (i.e., Unique) vote
			 # in set of duplicate votes
	iD = ivs2id(iVSU,VS,BVI)
	D[iD] += 1
	for iVS = 2:nVote
		if VS[iVSU,:] == VS[iVS,:]
			D[iD] += 1
			iVSU = iVS
			iD = ivs2id(iVSU,VS,BVI)
			D[iD] += 1
	print("D is "); display(D)
	# check for ballot counting mistakes
	sumD = sum(D)
	if sumD != nVote
		str = @sprintf(
			"ERROR: sum of duplicate vector (%d) should equal vote count (%d)", 
			sumD, nVote)
	C = zeros(Int64, maximum(BVI), nItem)
	for iVote = 1:nVote
		for iItem = 1:nItem
			C[V[iVote,iItem]+1,iItem] += 1
	print("C is "); display(C)
	CS = sum(C, dims=1)
	for iItem = 1:nItem
		if CS[iItem] != nVote
			str = @sprintf(
				"ERROR: C col %d does not sum to nVote",
	C2 = zeros(Int64, maximum(BVI), nItem)
	for iD = 1:nD
		if D[iD] > 0
	if C != C2
		print("ERROR: count matrices should match; C2 is "); display(C2)
end # nap()
julia> include("nap.jl")
nap (generic function with 4 methods)

julia> @time nap(50000,0)
B is 3×1 Matrix{Int8}:
nVote: 50000
D is 1×60 Matrix{Int64}:
 805  852  833  804  858  857  831  844  851  866  863  852  …  807  835  809  801  817  806  829  807  834  850  815
C is 5×3 Matrix{Int64}:
 12684  16723   9956
 12501  16580   9867
 12475  16697  10000
 12340      0  10056
     0      0  10121
  0.136220 seconds (1.14 M allocations: 32.175 MiB, 21.53% gc time, 4.84% compilation time)


not to get too political, but I think existing vote counting software is perfectly sufficient to counter such claims :slight_smile:

where the innovation is needed is in legislatures, city councils, executive offices, and most importantly the voters to be willing to try unfamiliar modes of governance. technology is not particularly a bottleneck in this domain


Tangentially, I think there are some non-standard voting methods with quite interesting properties, and have implemented a few in GitHub - tecosaur/Voting.jl: Count votes.


You may be interested in:


Oh that is interesting

There are a number of papers here about secure and privacy protected voting. It’s not only about open source.

It’s great to explore different types of ballots and their counting procedures, and it is an interesting opportunity to contribute to the PeaceFounder project, where votes are encoded plainly and signed pseudonymously. The challenge, particularly with more complex ballots, is to design a user experience that ensures unambiguous voting. Ballot types such as budget planning, quadratic voting, and cardinal voting with preferential setup are something one can explore. Additionally, the configuration file to specify these various ballot types is something to think about.

1 Like

EVoting is a very rich and fascinating field with various systems designs and peculiar attack vectors. Reading a bit on what you have written is hard to say what your idea is.

For example, to counter false claims about fraudulent votes getting entered in “big dumps” in the middle of the night or false claims about thousands of unregistered voters (some dead) voting

I think you may be interested in reading Ron Rivest work on software independence which can provide some grasp on the surface what to be scratched:


Having been a scrutineer in the past, and knowing that vote counting needs to be honest and have the appearance of integrity, I highly favour manual vote counting with each party having the option of having a scrutineer present at the counting.


The speed of manual vote counting would be greatly increased by sorting the ballots (because all duplicates can be grouped and counted at once). Do you think manual sorting of paper ballots is practical? If I recall correctly, there are some local voting regulations that prevent any vote counting until some official vote counting start time after the polls close. In that case, I wonder if sorting (but not counting) would be allowed before the official vote counting start time.

I’ve had a hobby interest in elections for a long time! I have a private package sitting around on an old computer where I implemented a full suite of committee selection rules, every single winner rule one can dream of, and some attempts at some agent-based models to compute strategic manipulations on various profiles.

To maintain both integrity and the appearance of integrity, the scrutineer would have to be able to see everything that happens to the votes, from when the box is opened to the final tally. Then the final tally is posted and can be viewed by the same scrutineer. Typically that happens after the polls close, which works well because the scrutineer is otherwise occupied before then. With many local polling stations it really does not take that long.


The (common) ballot types actually aren’t that complicated, I’ve implemented:

  • Pick-1 ballots
  • Approval ballots
  • Candidate-scoring ballots
  • Ranked choice ballots

I’d like to implement more vote-scoring methods, but I’m rather disposed towards ranked pairs for the properties it has.

It’s not feasible to do manually, but (thanks to the tie-breaking code being unimplemented :sweat_smile:) the implementation is actually rather straightforward:

function score(::RankedPairs, ballots::Vector{<:StrictlyRankedBallot}; winners::Int=0)
    winlist = Int[]
    prefmat = preferencematrix(ballots)
    preferences = Tuple{Pair{Int, Int}, Int}[]
    for i in axes(prefmat, 1), j in axes(prefmat, 2)
        push!(preferences, (i => j, prefmat[i, j]))
    filter!(>(0) ∘ last, preferences)
    sort!(preferences, by=last, rev=true)
    candidates = allcandidates(ballots)
    while length(winlist) < max(1, winners)
        edges = Set{Pair{Int, Int}}()
        children = Set{Int}()
        for ((i, j), _) in preferences
            if i ∉ children && (j => i) ∉ edges
                push!(children, j)
                push!(edges, i => j)
        thewinners = setdiff(candidates, children)
        if length(winlist) + length(thewinners) <= max(1, winners)
            append!(winlist, thewinners)
        elseif length(thewinners) != 1
            @warn "No single winner, tie between $thewinners"
            push!(winlist, first(winners))
            error("This shouldn't happen!")
        if length(winlist) < winners
            filter!(∉(thewinners) ∘ last ∘ first, preferences)
            filter!(∉(thewinners) ∘ first ∘ first, preferences)
            candidates = setdiff(candidates, thewinners)
    if winners == 0
        RankedPairsResult(first(winlist), preferences)
        RepeatedRankedPairsResult(winlist, preferences, prefmat)

if you like Ranked Pairs, I suspect you’ll like Stable Voting even more :eyes:

there is a still-open question on footnote 11 which I once tried to find a counterexample with some “blazingly fast Julia”

couldn’t find one! but can’t prove the truth of it either


I’ll just note that this thread has rekindled my interest in Voting.jl, expect to see a few commits pushed in the coming days :slight_smile:

1 Like

That does seem like a really nice voting method. They need to work on the explanation a bit, but it could probably be explained fairly simply.

1 Like

My best shot at explaining clearly is this…

Definition: we say that A defeats B if one cannot make a list of candidates starting with B and ending with A such that the margin of each candidate over the next is at least the margin of A over B. If one can make such a list, then A is not considered to defeat B, even if A wins head-to-head against B (i.e. has positive margin). If A is not defeated by any candidate, then we say that A is undefeated.

The Stable Voting procedure starts with all pairs of candidates (A, B). Then you:

  • Keep only pairs where A is undefeated.
  • Keep only pairs where A would win with B removed from all ballots.
  • Keep only pairs with maximal (possibly negative) margin of A over B.

The first candidates in each of the remaining pairs are the winners. If there’s more than one such candidate, then break the tie by some other mechanism.

looks about right! I’d say it’s probably important to emphasize that the second step where A would win with B removed from all ballots creates a recursion

I got the feeling that they were doing a bit of premature optimization in their definition. It’s easier to understand if the whole procedure is done in terms of sets of pairs rather than switching to iterating by descending margin midway. Of course, for efficiency, you’ll probably want to search that way, but that’s an optimization and shouldn’t bleed into the definition. I’m also pretty sure they “if there’s a single undefeated candidate, they win” part seems redundant with the rest, but I’m not certain. I guess it covers the case where there’s only one candidate, in which case there are no pairs of distinct candidates to consider.

Another thing I’m not certain about is whether it would be equivalent to eliminate all undefeated candidates at step 2—the description definitely has you keeping pairs where B is defeated, but does it matter? The spirit of stability seems to suggest that removing defeated candidates shouldn’t affect the outcome, but I’m not sure if they show that.

1 Like

my headcanon for the “cleanest” way to understand it, with the fewest special cases, is declaratively:

where (A, B) has the maximum margin among pairs such that
* A wins in P^{-B}
* B does not __defeat__ A (in the Split Cycle sense)

elect A

the whole subsetting business falls out of that

the open question is if that second condition is even needed on uniquely-weighted margin graphs, or if the first condition alone will return the same winner

1 Like