a voting simulator

the last chapter read a library. this one reads a whole program: a monte-carlo simulator that measures how well six election methods choose winners, modeled on jameson quinn's vse-sim. it is an entry, main.kso, and a module of ten small files, one for each idea in the chapter, about 180 lines in all. from the directory above the project, kanso run vse runs it.

the measure is voter satisfaction efficiency. each simulated election has a utilitarian-best candidate—the one whose victory would leave voters, in total, most satisfied. a method's vse is how much of that best-possible satisfaction its actual winner captures, normalized so that 1.0 means the ideal candidate won every time and 0.0 means the method did no better than drawing a candidate from a hat. average over many random elections and you get one number per method.

each method is implemented faithfully, from its own rules, and nothing downstream treats any of them specially. the driver hands all six the same electorate and records what happens. the ordering you will see at the end of the chapter—including the famous failure mode called the center squeeze—emerges from the simulation. it is not assumed anywhere in the code, and this chapter presents it the same way the program does: as a measurement.

the shape of the program

chapter 07 split a program into an entry and a module whose files share one namespace, and this program leans on that. the entry imports the module and does nothing else. inside the module, driver.kso calls plurality_winner from plurality.kso, which calls argmax from enumerable.kso, and none of them imports another. each file imports the standard-library modules it calls itself. enumerable.kso is the small vocabulary the rest is written in: argmax picks the position of the largest element, range counts from 1, and two helpers serve star and irv:

import "std/list"

fn argmax list
  fold (range (length list)) 1 (b i -> if (list[b] < list[i]) i b)

fn argmax_except list skip
  first = if (skip == 1) 2 1
  fold (range (length list)) first (b i -> better list skip b i)

fn better list skip b i
  if (i == skip) b (if (list[b] < list[i]) i b)

fn in? list x
  any? list (y -> y == x)

fn range n
  range_to n 1 []

fn range_to n i acc
  if (n < i) acc (range_to n (i + 1) (push acc i))

argmax folds over the positions, keeping whichever holds the larger value. the comparison is strict, so an equal later value never displaces an earlier one, and ties go to the lowest index. every method that picks a winner inherits that rule. fold, sum, mean, min, max, count and to_list come from std/list, called by their bare names, which an import also allows (chapter 07).

a spatial electorate

the electorate model is spatial: voters and candidates are points on a plane, and a voter likes a candidate more the nearer the candidate stands. the two axes are whatever you want them to be—tax policy and foreign policy, tradition and novelty—the model only cares about distance. a point is a list of coordinates, each drawn by math/random, and a population is a list of points. electorate.kso holds the model and its constants: twenty voters, five candidates, two dimensions.

import "std/list"
import "std/math"

fn cloud 0 _ acc
  acc

fn cloud n d acc
  point d [] .> (p -> cloud (n - 1) d (push acc p))

dims = 2

fn dist2 p q
  sum (list/map (range (length p)) (d -> sq (p[d] - q[d])))

ncand = 5

nvot = 20

fn point 0 acc
  acc

fn point d acc
  math/random 1000 .> (c -> point (d - 1) (push acc c))

fn sq x
  x * x

fn util vpos cpos
  0 - math/sqrt (dist2 vpos cpos)

fn utilities voters cands
  to_list (list/map voters (v -> to_list (list/map cands (c -> util v c))))

this is chapter 05's machinery doing real work. math/random 1000 is a description of a draw, so the coordinate arrives through a bind, .> (c -> ...), and the recursion continues inside the lambda, carrying the accumulator forward. point binds one coordinate per step until the dimension count reaches the 0 arm; cloud binds one whole point per step until the population count does. here is the same shape on its own, small enough to watch:

import "std/math"

fn cloud 0 acc
  acc

fn cloud n acc
  point 2 [] .> (p -> cloud (n - 1) (push acc p))

cloud 3 [] .> (voters -> print "three voters: {voters}")

fn point 0 acc
  acc

fn point d acc
  math/random 1000 .> (c -> point (d - 1) (push acc c))

three voters: [[876 612] [601 850] [662 624]]

run it again and the voters move, because a bare run seeds its random numbers from the clock. the book's runs set KANSO_SEED, which replays every draw exactly (chapter 06), so the numbers in this chapter are reproducible with that seed set.

utility is negative distance. a candidate standing on top of you is worth 0, and every step away costs. utilities, at the end of electorate.kso, turns a voter cloud and a candidate cloud into the matrix the rest of the program consumes: one row per voter, one column per candidate.

import "std/math"

voter = [3 4]
print "candidate at the origin: {util voter [0 0]}"
  .> (_ -> print "candidate next door: {util voter [3 3]}")

fn sq x
  x * x

fn util v c
  0 - math/sqrt (sq (v[1] - c[1]) + sq (v[2] - c[2]))

candidate at the origin: -5.0
candidate next door: -1.0

a voter at (3, 4) rates a candidate at the origin −5.0—the 3-4-5 triangle—and a neighbor one step away −1.0. higher is better, and the best possible score is zero. what each method gets to see of that matrix is the next question.

honest ballots

a ballot is a lossy projection of a utility row, and each method defines its own projection. this simulation models honest voters: every ballot is derived straight from the voter's true utilities, with no strategy layered on. plurality sees the least—just argmax v, the single favorite. approval sees one bit per candidate: a voter approves everyone strictly above their own mean utility across the field. score sees the most, a 0–5 integer rating of each candidate:

import "std/list"
import "std/math"

fn score_ballot v c
  lo = min v
  hi = max v
  math/round (5.0 * (v[c] - lo) / (hi - lo))

fn score_col voters c
  sum (list/map voters (v -> score_ballot v c))

fn score_winner voters
  argmax (to_list (list/map (range ncand) (c -> score_col voters c)))

score_ballot stretches the voter's utility row so their favorite sits at the top of the scale and their least favorite at the bottom, scales by 5.0, and rounds. the round is the point: real score ballots hold integers, so the simulated ones do too: a candidate 63% of the way up a voter's range gets a 3, and whatever that costs the method is part of the measurement rather than an error smoothed away. irv and minimax skip ballots entirely and read rankings straight off the utility row: voter v ranks a over b exactly when v[b] < v[a].

counting: plurality, approval, score

score, above, totals each candidate's column and takes the argmax. plurality and approval have the same shape:

import "std/list"

fn plurality_winner voters
  firsts = list/map voters (v -> argmax v)
  argmax (to_list (list/map (range ncand) (c -> count firsts (x -> x == c))))

import "std/list"

fn approval_col voters c
  sum (list/map voters (v -> approves v c))

fn approval_winner voters
  argmax (to_list (list/map (range ncand) (c -> approval_col voters c)))

fn approves v c
  if (mean v < v[c]) 1 0

read plurality_winner from the inside out: map each voter to their favorite, count how many favorites landed on candidate c, do that for every candidate, take the argmax. approval_winner and score_winner are the same pipeline with a different column function. all three share one signature—a list of utility rows in, a candidate index out—and that shared signature is what lets the driver treat six methods as six interchangeable values.

star: the runoff is part of the method

star is score plus an automatic runoff. total the score ballots, take the top two, then hold an instant head-to-head between them: each ballot goes to whichever finalist it scored higher, and ballots scoring them equal count for neither.

import "std/list"

fn prefer_count voters a b
  sum (list/map voters (v -> if (score_ballot v b < score_ballot v a) 1 0))

fn star_winner voters
  totals = to_list (list/map (range ncand) (c -> score_col voters c))
  a = argmax totals
  b = argmax_except totals a
  pa = prefer_count voters a b
  pb = prefer_count voters b a
  if (pb < pa) a (if (pa < pb) b a)

argmax_except, from enumerable.kso, finds the runner-up by folding with a seed that dodges the skipped index—if the leader is candidate 1, start the scan at 2. and prefer_count compares score ballots, not raw utilities: the runoff counts the ballots voters actually cast, so a voter who scored both finalists 4 genuinely abstains from the runoff. the last line settles a tied runoff in favor of the score leader.

irv: elimination, one round at a time

instant-runoff voting repeats rounds: count first choices among the candidates still standing, stop if the leader holds a strict majority of all voters, otherwise eliminate the weakest and count again. the rounds are recursion; the per-round scans are folds:

import "std/list"

fn first_is v elim c
  if (rank_first v elim == c) 1 0

fn irv_counts voters elim
  counted = (c -> sum (list/map voters (v -> first_is v elim c)))
  to_list (list/map (range ncand) counted)

fn irv_go voters elim
  counts = irv_counts voters elim
  top = argmax counts
  if (nvot < 2 * counts[top]) top (irv_next voters elim counts)

fn irv_next voters elim counts
  irv_go voters (push elim (min_alive counts elim))

fn irv_winner voters
  irv_go voters []

fn keep_min counts elim b c
  if (in? elim c) b (if (b == 0) c (if (counts[c] < counts[b]) c b))

fn keep_top v elim b c
  if (in? elim c) b (if (b == 0) c (if (v[b] < v[c]) c b))

fn min_alive counts elim
  fold (range ncand) 0 (b c -> keep_min counts elim b c)

fn rank_first v elim
  fold (range ncand) 0 (b c -> keep_top v elim b c)

the state of an irv count is nothing but the elimination list. irv_winner starts it empty; each round either returns a winner or recurses with one more name pushed onto elim. the majority test is integer arithmetic—nvot < 2 * counts[top] is "top holds strictly more than half"—with no division to introduce a float. vote transfer costs no code at all: rank_first, behind first_is, folds over the candidates keeping the voter's best alive option, so when a candidate joins elim, every ballot that ranked them first simply resolves to its next surviving preference on the following count.

minimax: the least-bad worst defeat

minimax is a condorcet method: it looks at every head-to-head pairing. a candidate's margin against a rival is the number of voters preferring them minus the number preferring the rival; a candidate's worst margin is their most damaging pairing; the winner is the candidate whose worst is least bad.

import "std/list"

fn margin_or_high voters a b
  if (a == b) nvot (pair voters a b - pair voters b a)

fn minimax_winner voters
  argmax (to_list (list/map (range ncand) (c -> worst_margin voters c)))

fn pair voters a b
  sum (list/map voters (v -> if (v[b] < v[a]) 1 0))

fn worst_margin voters a
  min (list/map (range ncand) (b -> margin_or_high voters a b))

the one wrinkle is the diagonal: a candidate has no margin against themselves, so margin_or_high reports nvot there—at least as large as any real margin can be, which keeps the self-pairing from ever registering as anyone's worst. the structure buys a guarantee: when some candidate beats every rival head-to-head—a condorcet winner—all their margins are positive while every rival carries at least one negative, so minimax elects them.

the center squeeze, in miniature

before running four hundred random elections, it helps to watch the six methods disagree on one election small enough to hold in your head. the methods read only a list of utility rows and two constants, ncand and nvot, so a second small project can reuse them with a hand-built electorate: nine voters, three candidates, lopez on the left, chen in the center and reed on the right.

import "./squeeze"

print "plurality: {label (plurality_winner electorate)}"
  .> (_ -> print "irv:       {label (irv_winner electorate)}")
  .> (_ -> print "approval:  {label (approval_winner electorate)}")
  .> (_ -> print "score:     {label (score_winner electorate)}")
  .> (_ -> print "star:      {label (star_winner electorate)}")
  .> (_ -> print "minimax:   {label (minimax_winner electorate)}")

plurality: lopez
irv:       reed
approval:  chen
score:     chen
star:      chen
minimax:   chen

the squeeze module holds model.kso, the electorate and its constants, beside the simulator's helpers and six methods in one file, each winner marked pub so the entry can call it. four voters love lopez, three love reed, two love chen, and every voter rates chen a 4 or a 5. chen is the consensus candidate and beats either rival head-to-head. six faithful implementations give three different winners. plurality sees only first choices, so lopez's larger base wins. irv eliminates chen first, for having the fewest first choices, and the transfers hand the final round to reed. the four methods that see intensity or every pairing all elect chen. that is the center squeeze: the compromise candidate everyone can live with is the first one eliminated.

the vse metric

to score a winner you need a yardstick, and the yardstick is social utility: the sum of a candidate's column in the utility matrix—everyone's satisfaction with that candidate, added up. vse locates the winner on the line between two anchors, the average candidate and the best one:

import "std/list"

fn socutil voters c
  sum (list/map voters (v -> v[c]))

fn socutils voters
  to_list (list/map (range ncand) (c -> socutil voters c))

fn vse socs winner
  m = mean socs
  (socs[winner] - m) / (max socs - m)

if the method elected the utility-maximizing candidate, numerator equals denominator and the election scores 1.0. if it elected a candidate exactly as good as the field's average—what a random draw achieves in expectation—it scores 0.0. a method can score below zero in a given election by electing someone worse than average. average the per-election scores over many elections and the number becomes stable enough to compare methods.

the monte carlo driver

one trial is: draw a voter cloud, draw a candidate cloud, build the utility matrix, run all six methods on it, and add each method's vse for this election to a running sum. the driver is the same recursion-through-bind shape as cloud, one level up:

pub fn means sums
  print "plurality VSE {sums[1] / runs}"
    .> (_ -> print "approval  VSE {sums[2] / runs}")
    .> (_ -> print "score     VSE {sums[3] / runs}")
    .> (_ -> print "star      VSE {sums[4] / runs}")
    .> (_ -> print "irv       VSE {sums[5] / runs}")
    .> (_ -> print "minimax   VSE {sums[6] / runs}")

pub runs = 400

fn tally acc elec
  socs = socutils elec
  p = acc[1] + vse socs (plurality_winner elec)
  a = acc[2] + vse socs (approval_winner elec)
  s = acc[3] + vse socs (score_winner elec)
  st = acc[4] + vse socs (star_winner elec)
  i = acc[5] + vse socs (irv_winner elec)
  m = acc[6] + vse socs (minimax_winner elec)
  [p a s st i m]

pub fn trials 0 acc
  acc

pub fn trials k acc
  cloud nvot dims [] .> (vp -> with_voters k acc vp)

fn with_voters k acc vp
  cloud ncand dims [] .> (cp -> trials (k - 1) (tally acc (utilities vp cp)))

the accumulator is a six-slot list of running sums, one per method, seeded with floats and threaded through every trial. trials binds a voter cloud, with_voters binds a candidate cloud, and tally, which has no effects, runs all six methods against the resulting matrix and returns the updated sums. there are no channels and no mutable counters. the monte carlo loop is a recursion whose state rides in its arguments, and the only effects in the program are the coordinate draws and the final prints.

the measured result

the entry runs runs trials, four hundred, and hands the final sums to means with .>. means divides each sum by the number of runs and prints it. twenty voters, five candidates, two dimensions, four hundred elections:

import "./vse"

trials runs [0.0 0.0 0.0 0.0 0.0 0.0] .> means

plurality VSE 0.6861199412466163
approval  VSE 0.9143288760508763
score     VSE 0.979229551350013
star      VSE 0.9750463456028904
irv       VSE 0.8538681725012696
minimax   VSE 0.9696873187267149

sorted, the measurement reads: score 0.979, star 0.975, minimax 0.970, approval 0.914, irv 0.854, plurality 0.686. the top three are within a percentage point of each other, closer than the run-to-run spread of four hundred elections, so at this size they tie: the rated methods and the condorcet method all elect near-ideal winners under honest voting. the gaps below them are several times that spread. approval gives up about six points of efficiency to its one-bit ballot: a threshold keeps the shape of a voter's preferences but discards their intensities. irv lands below approval despite collecting full rankings—the squeeze from the previous section, happening at statistical scale: in electorates where the compromise candidate lacks a first-choice base, irv eliminates them early, exactly as it eliminated chen. plurality, seeing only first choices, captures about two-thirds of the available satisfaction.

these numbers are a measurement of this model: honest voters, a uniform two-dimensional electorate, twenty voters, five candidates. change the model and the numbers move—that is what the exercises are for. what does not move is the method: implement the rules faithfully, define the yardstick before the race, and report whatever comes out. the ordering above was not designed into the program anywhere you can point to; it fell out of four hundred elections that anyone can re-run.

what you can do now

you have read a complete kanso program, every declaration of it, and the parts were all familiar: literal-clause dispatch for base cases, folds for aggregation, bind for randomness and for the report, a directory for the module. more usefully, you have seen the shape of a simulation study: model the world as data, define the projection each method sees, implement the rules faithfully, fix the yardstick before running, and let the answer be whatever the run says. the ordering in the table is the program's output, and the program is yours to interrogate—which is what the exercises are about.

exercises

1. add borda count. a candidate's borda score is the number of (voter, rival) pairs where the voter ranks the candidate above the rival—which means pair already does the hard part. write borda_winner, give it a slot in tally and a line in means, and see where it lands in the table.
2. the electorate is a square. set dims to 1, then to 4, and re-run. which methods' numbers move most, and does the ordering itself change?
3. in squeeze/main.kso, add center voters one at a time. how many does chen need before irv stops eliminating them first? does plurality come around at the same point, or a different one?
4. pin the squeeze results: add a squeeze/methods_test.kso with six test_ constants asserting each method's winner, and run kanso test squeeze. now exercise 3 has a regression suite.