%%{init: {"theme": "base", "themeVariables": {"primaryColor": "#E8ECFF", "primaryBorderColor": "#4054B2", "primaryTextColor": "#16171B", "lineColor": "#3B4351", "edgeLabelBackground": "#FAF7F0", "clusterBkg": "#EFE9DC", "clusterBorder": "#766F65"}}}%%
flowchart TD
A(["Option A"])
B(["Option B"])
C(["Option C"])
A -->|"beats, 2 of 3<br/>(voters 1 and 3)"| B
B -->|"beats, 2 of 3<br/>(voters 1 and 2)"| C
C -->|"beats, 2 of 3<br/>(voters 2 and 3)"| A
13 Making Group Decisions: Voting, Social Choice, and Ensembles
Every multi-agent system, sooner or later, holds an election, and hardly any of them knows it. Sample a model five times and keep the most common answer: that is an election, with a franchise of five. Ask three reviewer agents whether the patch should merge: an election. Set a judge model over a panel of candidate outputs, average an ensemble’s predictions, break a tie between two subagents by asking a third — elections, every one, differing only in electorate and rule. The engineer who assembles these arrangements is practising social choice, the theory of how many voices become one decision, and is usually practising it the way M. Jourdain spoke prose — fluently, daily, and with no idea the discipline exists. This chapter is where the bill for that innocence is presented. The preface warned that engineers aggregate the votes of several models without knowing that Arrow proved something inconvenient about exactly that; what Arrow proved, what Condorcet proved a century and a half earlier — one result heartening, one dismaying, both operational — and what it all says about the ensembles and judges now running in production, is the business of the pages that follow.
Before any theorem can bite, one distinction has to be drawn, because it decides which theorems apply. Sometimes a group aggregates preferences: the agents want different things — this refactor or that one, this allocation of the budget or another — and there is no fact of the matter about which is right, only a decision to be reached that the group can live with. And sometimes a group aggregates judgements: there is a right answer — the patch does or does not contain a bug, the claim is or is not supported by the source — and the group’s disagreement is error, not taste. The two problems look alike on the ballot and could not differ more underneath. Judgement aggregation is trying to track truth, and can call on statistics for help; preference aggregation is trying to be fair, and statistics has nothing to say about fairness. Agent systems run both, usually through the same voting machinery and usually without noticing the difference — yet the difference is where the theory divides: the heartening results of this chapter belong mostly to judgement, and the dismaying ones mostly to preference, and knowing which regime a given vote lives in is the first diagnostic skill the chapter teaches.
The theory, for once, does not merely predate the agents by decades; it predates the telegraph. In the Paris of the 1780s, the Chevalier de Borda and the Marquis de Condorcet quarrelled before the Académie Royale over how France should elect its academicians, and between them laid out most of the subject: Borda his point-count method, Condorcet his principle that the winner should beat every rival head to head — along with his own discovery that no such winner need exist, majorities being perfectly capable of preferring A to B, B to C, and C to A, all at once. Condorcet also proved the theorem this book will lean on hardest, the jury theorem, an argument that majorities of competent, independent judges converge on the truth — an Enlightenment optimist’s result from a man who died in one of the Revolution’s prisons, hunted by the government of the republic he had helped to design. The modern subject begins in 1951, when Arrow put the subject’s accumulated paradoxes on an axiomatic footing and showed they were not accidents; May, Gibbard, and Satterthwaite sharpened the picture over the following quarter-century; and multi-agent systems research, recognising machinery it needed, built the field of computational social choice on top. The agents arrived, as ever, last — this time to an apparatus that had been waiting for them since before the storming of the Bastille.
One assumption does quiet work through the chapter’s first half, and honesty requires naming it now: that the voters vote sincerely, reporting their true preferences and honest judgements. For the reader of Chapter 12 this should already smell of trouble — a ballot is a message, a message among interested parties is a move (Section 12.5), and the moment an agent cares about the outcome it will be tempted to vote for what works rather than what it thinks; how badly that temptation undermines the enterprise is a theorem too, and it arrives on schedule. We proceed from the aggregation problem itself and the preference–judgement divide (Section 13.1); through the voting rules and the surprises they spring (Section 13.2); to the impossibility results that no rule escapes (Section 13.3); then to the good news — Condorcet’s jury, and the exact conditions under which crowds are wise (Section 13.4); onward to the modern machinery, where ensembles and self-consistency turn out to be convening juries (Section 13.5) and the judge model turns out to hold an office Arrow named precisely (Section 13.6); and finally to the design question the whole chapter exists to sharpen: how to choose how to choose (Section 13.7).
13.1 One Choice from Many: The Aggregation Problem
Strip any group decision to its skeleton and three things remain: a set of voters, a set of alternatives, and, from each voter, an expression of where it stands — a favourite named, a full ranking submitted, a score attached, a yes or a no. The collection of all the voters’ expressions is a profile, and the object at the centre of social choice is the aggregation rule: the function that takes a profile in and hands a collective verdict back (Brandt et al., 2016). The tradition distinguishes rules by what they return — a social choice function names a winner, a social welfare function returns a whole collective ranking — but the distinction to internalise is simpler and sharper: the rule is a designed artefact. The voters supply the inputs; everything else — what counts as winning, how ties break, whose voice weighs what — is decided by the function, which somebody chose. In a multi-agent system that somebody is the engineer, and the rule is not even metaphorically a function: it is a function, sitting in the codebase, usually unexamined and quite often unnamed.
Name a few, then. Self-consistency (Section 5.3) samples a model several times and returns the most common answer: that is plurality rule — most votes wins — over an electorate of samples. An ensemble that averages its members’ scores is running a scoring rule; one that takes the median is running a different rule with meaningfully different properties, notably its stubbornness towards outliers. The team’s merge gate — proceed only if all three reviewers approve — is a unanimity rule, whose known character is caution bought at the price of paralysis; relax it to two-of-three and you have majority rule, a different constitution with a different temperament. An orchestrator that breaks ties between two subagents by consulting a third has convened an electorate of one plus one plus one; and a judge model set over a panel of candidate outputs is a rule so distinctive that it has a technical name in the theory, which Section 13.6 will produce at the proper moment, with due ceremony. None of these arrangements is wrong. What is wrong, or at least what this chapter exists to end, is choosing among them by not noticing that a choice was made.
| Agent-system construct | The classical rule it is | The personality it inherits |
|---|---|---|
| Self-consistency: sample n times, keep the most common answer | Plurality over an electorate of samples | Blind to all but each voter’s top choice; vote-splitting unless ballots are clustered by meaning |
| Ensemble that averages its members’ scores | Score voting (a linear opinion pool); the Borda count only when the scores encode ranks | Consensual: rewards the broadly acceptable answer |
| Ensemble that takes the median | The median rule | Stubborn towards outliers |
| Merge gate: proceed only if all three reviewers approve | Unanimity rule | Cautious, bought at the price of paralysis |
| Two-of-three reviewer sign-off | Majority rule | May’s safe harbour: uniquely fair on a binary question |
| Tie broken by consulting a third agent | A three-voter election | Majority rule’s, inherited — including the correlation risk when the third shares the tied pair’s model |
| Judge model ranking a panel of candidates | Dictatorship (Section 13.6) | Transitive and cycle-free — but the judge’s biases become the group’s policy |
| Pairwise elimination of candidates by a judge | Sequential pairwise vote (a tournament) | Agenda-sensitive: when the judge’s verdicts cycle, the running order picks the winner |
Before any of those rules can be judged, though, one question must be put to the vote itself, because everything downstream turns on the answer: is there a right answer? Sometimes there is not. When the team must choose between two workable refactorings, or divide a budget between speed and safety, the agents’ votes express preferences — what each would like — and no measurement, however careful, could reveal the choice to be factually mistaken; the aggregation is answerable to standards of fairness: that no voice be ignored, that no voter dictate, that the outcome respect the profile in ways the next two sections will make precise. And sometimes there is a right answer. When three reviewers vote on whether the patch contains a bug, the patch either does or does not; their votes express judgements — estimates of a fact — disagreement signals error rather than diversity, and the aggregation is answerable to a standard fairness knows nothing of: accuracy, the probability of getting the fact right. Preference aggregation is politics; judgement aggregation is measurement. The ballots look identical, and the difference decides which mathematics applies — the impossibility theorems of Section 13.3 bite hardest on preferences, while the hopeful statistics of Section 13.4 belong to judgements — which is why misdiagnosing the species of a vote means consulting the wrong theory about it.
The diagnosis takes practice, because real votes are frequently hybrids. “Which of these five candidate patches should ship?” mixes fact (which ones are correct — a judgement) with taste (which style the team prefers — a preference); a reviewer’s quality score compresses both into one number. The working test is counterfactual: if an oracle revealed the truth, would the disagreement dissolve? Disagreement about whether the patch breaks the API dissolves under an oracle; disagreement about whether the API should exist does not. An engineer who runs this test on each vote a system takes will find, usefully, that most of them are closer to the judgement end — agent systems mostly aggregate estimates of facts — which is encouraging, since that is where the good news lives. But not all of it is good, and the classical demonstration of why deserves a place in every practitioner’s head.
Suppose the team’s policy is that a patch merges exactly when it is correct and adequately tested — a conclusion resting on two premises. Three reviewer agents vote on everything. The first finds it correct but poorly tested; the second finds it well tested but incorrect; the third finds it sound on both counts. Now count two ways. Premise by premise: a majority (first and third) says correct; a majority (second and third) says well tested; both premises pass, so the policy says merge. Conclusion by conclusion: only the third reviewer actually supports merging, so the vote is two-to-one against. The same three honest ballots yield opposite collective verdicts depending on which question was put to the vote — and nothing in logic or fairness singles out either count as the correct one. This is the discursive dilemma, and List and Pettit proved it is no curiosity: under mild conditions, no aggregation procedure can guarantee consistent collective judgements on logically connected propositions while treating voters and propositions even-handedly (2002). Judgement aggregation, in other words, has impossibility theorems of its own; the measurement species is the more hopeful of the two, not a paradox-free one. And the engineering moral is immediate: an orchestrator that polls its reviewers premise-wise and one that polls them verdict-wise are different constitutions that will, on honest inputs, sometimes ship different code — so the choice between them is substantive, deserves a moment’s thought, and is currently being made, in most systems, by whoever happened to write the prompt.
The aggregation problem, then, is posed: inputs from many, a verdict for all, a rule in between that somebody must design — and a species distinction that decides what the rule should even be for. What remains is to meet the rules themselves. The classical repertoire is rich, ingenious, and older than the French Revolution, and the reason it repays study is not antiquarian: every rule in it has a documented personality, complete with virtues, vices, and known ways of going wrong. Those personalities are the subject of the next section.
13.2 Counting Heads: Voting Rules and Their Surprises
In 1781, before the assembled Académie Royale des Sciences, the Chevalier de Borda rose to attack a method so obvious that nobody had thought it needed defending: give everyone one vote, and elect whoever gets the most (1781). His demonstration — that the method can crown a candidate whom a majority would defeat in any head-to-head contest — is the founding move of the whole subject, and it set the pattern every later discovery would follow: take a rule that looks like plain common sense, construct a profile of perfectly reasonable votes, and watch the rule do something indefensible. The lesson of two and a half centuries of such constructions is not that some rules are broken and others sound; it is that every rule has a personality — systematic dispositions, flattering and otherwise, that follow it into any system that adopts it. This section introduces the three oldest personalities, and the surprise, older than the French Republic, that upends them all.
13.2.1 Plurality and the Split Vote
Plurality — each voter names one favourite, the most-named wins — is the rule everyone reinvents first, and its vice is the one Borda exposed: it hears only first choices, so it is blind to everything else the voters think. Its signature failure is vote-splitting: let two similar alternatives divide their natural supporters, and a third that most voters rank last can win with a plurality neither rival could match — the spoiler effect, familiar from a century of political mishaps, in which the entry of a candidate who cannot win changes who does.
The failure travels straight into the machinery of Chapter 5. Self-consistency, we said, is plurality over an electorate of samples — and plurality’s blindness comes with it. Sample a model ten times on a hard problem and the correct answer may arrive phrased three different ways — “7”, “seven”, “the answer is 7” — while a tempting wrong answer arrives, each time, in identical form; count naively and the wrong answer wins on a technicality, its rivals having split the correct vote among themselves. This is why self-consistency implementations must cluster answers by meaning before counting — semantic equivalence as electoral reform — and why the clustering is not a preprocessing nicety but the difference between a working rule and a spoiler-prone one. An election is only as sound as its notion of which ballots name the same candidate.
13.2.2 The Borda Count
Borda’s remedy was to make the ballot say more. In the Borda count, each voter submits a full ranking; with m alternatives, a first place earns m-1 points, a second m-2, and so down to zero; the highest total wins. The rule listens to the whole of every ranking, and its personality is correspondingly consensual: it favours the alternative that is broadly acceptable over the one that is passionately supported and widely loathed — often exactly what a team of agents scoring candidate outputs wants, and a reasonable reading of what an ensemble is groping toward when it averages graded scores rather than counting favourites.
Its vices are two, and both will matter later. First, the count is exquisitely sensitive to the menu: add or remove an also-ran — a candidate with no hope of winning — and the points shift beneath the contenders, so that the collective choice between A and B can be reversed by the arrival of an irrelevant C. Second, the same sensitivity is a lever: a voter who buries a rival — ranking it last not from conviction but from tactics — moves real points, and Borda’s own airy reply to the objection, that his method was intended only for honest men, has been quoted back at him ever since by everyone who has met a voter who is not one. Among self-interested agents that reply is not a defence but a bug report, filed in advance; the theorem that makes it general arrives in the next section.
13.2.3 Condorcet’s Principle — and His Paradox
Condorcet, Borda’s colleague and rival at the Académie, proposed a sterner standard (1785): put every pair of alternatives to a head-to-head majority vote, and if some alternative beats every rival in these pairwise contests, it — the Condorcet winner — ought to win the election. The principle has a strong claim to be what majority rule means once there are more than two options, and it sharpens Borda’s original complaint into a criterion: plurality stands condemned precisely because it can elect a candidate who is not the Condorcet winner — and so, embarrassingly, can Borda’s own count, which is roughly where the two men’s civility ended.
Then Condorcet turned his method on itself and found the trapdoor. Three voters rank three options: the first says A \succ B \succ C; the second, B \succ C \succ A; the third, C \succ A \succ B. Now count the pairs. A beats B, two votes to one; B beats C, two to one; and C beats A, two to one. The majorities form a cycle — the group prefers A to B to C to A — and there is no Condorcet winner at all, every alternative being beaten by some other. Nothing is wrong with the voters, each of whom holds a perfectly consistent ranking; it is the collective preference that fails to be an ordering, majority-of-the-group turning out not to inherit the rationality of its members. The reader of Chapter 12 has seen this shape of result before — individually impeccable inputs assembling an indefensible aggregate — and the discursive dilemma of Section 13.1 is its judgement-flavoured sibling. It is the field’s founding humiliation, and Arrow will shortly explain why it cannot be tidied away.
13.2.4 The Rule Decides
The cycle’s practical sting is what it hands to whoever controls the order of business. Suppose the three options above are put to sequential pairwise votes — winner meets the remaining option, as committees and runoffs do everywhere. Start with A against B, and A wins, then loses the final to C: the outcome is C. Start instead with B against C, and B survives to lose the final to A: the outcome is A. Start with A against C, and the winner is B. Same voters, same preferences, three different collective decisions — chosen, in effect, by whoever set the agenda. The chair who understands cycles need never cast a vote to decide the outcome; the running order is the vote. And the modern instance is closer than it looks: an orchestrator that whittles candidate outputs down through pairwise comparisons by a judge model is running exactly this tournament, and whenever the judge’s pairwise verdicts cycle — nothing guarantees they will not, and the biases catalogued in Section 13.6 make intransitive verdicts an observed fact rather than a theoretical nicety — the bracket, not the judgement, is picking the winner.
Assemble the section’s specimens and the general lesson states itself: plurality, Borda, and pairwise majority, each a reasonable reading of “let the group decide”, can return three different winners from one and the same profile of honest votes. The rule is not a neutral pipe from preferences to outcomes; it is a co-author of the result, and the only question is whether its contribution was chosen deliberately or inherited from whichever example the framework documentation happened to use. At which point an optimist will ask the obvious question: these are three particular rules with three particular defects — so why not design a better one, a rule with the virtues and without the vices? It is an excellent question. It was asked, with full mathematical seriousness, in 1951, and the answer — which is no, and provably — is the next section’s business.
| Rule | Ballot it asks for | How the winner is chosen | Personality | Signature pathology |
|---|---|---|---|---|
| Plurality | One favourite named | The most-named alternative wins | The rule everyone reinvents first — so obvious it seems to need no defending | Vote-splitting / the spoiler effect; blind to all but first choices |
| Borda count | A full ranking | Points by rank (m-1 down to 0); highest total wins | Consensual — rewards broad acceptability over passionate support | Menu-sensitivity (an irrelevant also-ran can flip A versus B); rewards burying a rival |
| Pairwise majority (Condorcet) | A full ranking, read as head-to-head contests | The alternative that beats every rival (the Condorcet winner) | A sterner standard — arguably what majority rule means with more than two options | May name no winner at all: majorities can cycle (Condorcet’s paradox); agenda-sensitive |
13.3 Arrow’s Theorem: The Price of Consistency
Arrow’s contribution was to stop auditioning rules and change the question. A hundred and seventy years of the subject had proceeded specimen by specimen — propose a rule, find its embarrassment, propose another — and in 1951 Kenneth Arrow, in a doctoral thesis of unassuming size and immodest consequence, inverted the procedure (1951). Write down, first, the properties any acceptable rule must surely have — each so mild that refusing it seems perverse — and then ask what rules satisfy them all. The method is the axiomatic turn that modern social choice is built on, and its first application produced the most famous negative result in the social sciences.
13.3.1 Four Platitudes
The conditions deserve to be stated, informally but exactly, because each will sound like nothing at all. A rule — here, one that takes every voter’s full ranking of three or more alternatives and returns a collective ranking — should have universal domain: it must accept any profile of rankings the voters might submit, not merely the convenient ones. It should respect unanimity: if every single voter ranks A above B, the group had better do the same. It should satisfy independence of irrelevant alternatives: the collective verdict between A and B should depend only on how the voters compare A and B — not on where anyone ranks some third option C, whose comings and goings ought to be no business of the A-versus-B question. The reader met this condition’s violation in the wild a section ago, as the Borda count’s menu-sensitivity; here it is promoted to a requirement. And the rule should exhibit non-dictatorship: there must be no voter whose personal ranking simply is the collective ranking, whatever everyone else submits. Four conditions, each individually a platitude.
Arrow’s theorem is that no rule satisfies all four. Not none discovered so far: none, provably, in the space of all possible rules — any procedure meeting the first three conditions is a dictatorship, and any that avoids dictatorship must violate universality, unanimity, or independence somewhere. The pathologies of Section 13.2 were therefore never defects of craftsmanship awaiting a cleverer design. Condorcet’s cycle was the first sighting of a theorem; Borda’s menu-sensitivity is where his rule pays Arrow’s tax; and the optimist’s question that closed the last section — why not build a rule with the virtues and without the vices? — receives its final answer. There is no such rule, and the search that had run since the Académie was not unfinished but impossible.
13.3.2 Living with Impossibility
What should an engineer do with an impossibility theorem? Not despair, and not dismiss — the productive reading is the one this book gave the PPAD result of Section 12.2: a map of what cannot be bought, so that trade-offs are chosen rather than stumbled into. Every aggregation rule in every multi-agent system violates at least one Arrow condition; the design question is which one, and on purpose. Surrendering independence yields the Borda family — serviceable, consensual, and menu-sensitive, a fair trade where the menu is fixed and the voters are honest. Surrendering universal domain is subtler and often the engineer’s best move: Arrow’s theorem needs the awkward profiles to bite, and when preferences are known to share structure — every voter ranking the options along a single dimension, cheapest-to-dearest or safest-to-boldest — the cycles vanish, majority comparisons behave, and the alternative preferred by the median voter beats all others, a result owed to Black (1948) and standing as the standing reward for asking agents to express preferences on a scale rather than over an arbitrary menu. Domain restriction is impossibility-avoidance by design: shape what can be voted on, and the theorem’s premises quietly fail to apply.
13.3.3 May’s Safe Harbour
There is one more escape, and it is the clean one. Arrow’s theorem requires three or more alternatives; with exactly two, the whole edifice of cycles and independence collapses into triviality, and something better than possibility holds. May proved that for two alternatives, simple majority rule is not merely a good rule but the only rule satisfying anonymity (voters interchangeable), neutrality (alternatives interchangeable), and positive responsiveness (a vote gained never hurts) (1952) — a uniqueness theorem where its elders are impossibilities. This is the safe harbour, and it is why the binary gate is the aggregation this book keeps steering towards: merge or don’t, ship or hold, pass or fail are votes May underwrites, while choose among these five candidates is a vote Arrow haunts. Where a collective decision can honestly be decomposed into two-option questions, the theory’s blessing is unqualified — with the one caveat already served: chain binary votes through logically connected propositions and the discursive dilemma is waiting, so the decomposition itself must be chosen with the same care as the rule.
13.3.4 Everyone Manipulates
The second impossibility is the one Borda was warned about at the Académie and waved away. Gibbard and Satterthwaite, working independently, proved that for three or more alternatives every voting rule that is not a dictatorship — every rule under which each alternative has some chance of winning — is manipulable: there exist profiles at which some voter does strictly better by misreporting its preferences than by voting sincerely (1973; 1975). Not the Borda count specifically: every rule. Strategic voting is not a flaw that a cleverer ballot design will remove; it is a structural feature of aggregation among agents with stakes, and the reader of Chapter 12 will recognise the register at once — a ballot is a message, a message among interested parties is a move (Section 12.5), and the sincere-voting assumption this chapter has been running on is, among self-interested agents, exactly the cheap talk that chapter taught us to price. An agent that grades candidate patches learns, soon enough, that inflating its favourite’s score and burying the rival moves the outcome; nothing but indifference keeps a voting agent honest, and Gibbard–Satterthwaite says no rule can be built that changes this. What can be changed is the cost of the manoeuvre — manipulation can be made computationally hard, expensive to compute even when it exists, which is the founding trick of computational social choice and part of Section 13.7’s business.
The ledger of the last two sections is, on its face, grim: majorities that cycle, rules that co-author outcomes, an impossibility where the perfect rule should be, and a guarantee that whatever rule survives can be gamed. But every entry in that ledger belongs to the preference species of Section 13.1 — to aggregation answerable to fairness, where there is no fact of the matter to be right about. Change the species and the mathematics changes temper entirely. When the voters are estimating a truth, the question is no longer how to be fair to their rankings but how to be accurate about the world, probability replaces paradox as the operative discipline, and the very man whose cycle began the trouble proved the most optimistic theorem in the subject. Condorcet’s jury is where this chapter’s good news lives, and it is where we go next.
13.4 The Wise Crowd: Condorcet’s Jury Theorem
Put the two species-defining conditions of this chapter together — exactly two options, so that May’s harbour holds, and a fact of the matter, so that accuracy is the standard — and you arrive at the one corner of social choice where everything works, and works better than anyone has a right to expect. A jury votes on a question with a right answer: guilty or not, bug or no bug. Suppose each juror is competent — correct with some probability p greater than one half, however modestly — and that the jurors err independently, each one’s mistakes owing nothing to anyone else’s. Then — this is the jury theorem — the majority verdict is more likely to be correct than any single juror’s, its accuracy rises with every juror added, and as the jury grows it approaches certainty (1785). Not consensus, not compromise: truth, converged upon by counting. It is the most optimistic theorem in the book, published four years before the Revolution by the man whose paradox opened this chapter’s troubles, and it is the mathematical licence behind every ensemble the reader has ever run.
The magic is worth demystifying, because it is only the law of large numbers wearing a wig. Each juror’s vote is truth plus noise; the noise, being independent, points in no particular direction and cancels as votes accumulate, while the signal — the pull of the actual answer on each competent juror — points the same way every time and adds up. The numbers move quickly, and are computable exactly: with n jurors, n odd, each correct, independently, with probability p, the majority verdict is right precisely when at least (n+1)/2 jurors are, an event of probability
P_n \;=\; \sum_{k=(n+1)/2}^{n} \binom{n}{k} p^{k} (1-p)^{n-k},
a sum a few lines of Python will evaluate. Three jurors, each right sixty per cent of the time, deliver a majority verdict that is right about sixty-five per cent of the time — a modest gain; make it a hundred and one such jurors and the majority is right around ninety-eight times in a hundred. Mediocrity, aggregated, becomes excellence, provided only that the mediocrities are different mediocrities: each juror wrong in its own way, right in the same one. What every correct voter has in common is the truth; what the erring voters have in common, if independence holds, is nothing.
The promise is cheaply kept: with comb doing the counting, the sum P_n transcribes directly as
from math import comb
def p_majority(n: int, p: float) -> float:
return sum(comb(n, k) * p**k * (1 - p) ** (n - k)
for k in range((n + 1) // 2, n + 1))
p_majority(3, 0.6) # -> 0.648
p_majority(101, 0.6) # -> 0.979...whose two trailing calls replay the paragraph’s arithmetic — the modest gain at three jurors, the near-certainty at a hundred and one.
Hold the celebration, though, until the theorem’s dark twin has been read into the record. Run the same arithmetic with p below one half and every conclusion reverses sign: the majority is now more likely to be wrong than any single juror, and as the jury grows it converges — with the same implacable certainty — on the wrong answer. Aggregation is an amplifier, not a purifier: it takes whatever tendency the jurors share and turns the volume up. A committee of the systematically mistaken is not wiser than its members; it is merely more sure. And the engineering corollary deserves italics it will not get: adding more voters helps only if the voters are better than chance on this question. Scaling out a jury of agents that misunderstand the task buys not robustness but a unanimous, confident, and thoroughly aggregated mistake — at ten times the token cost of asking one of them.
The theorem’s empirical face was supplied, with some reluctance, by Francis Galton. At a livestock fair in Plymouth in 1906 he came upon a guess-the-weight competition: an ox, and 787 paid entries from a crowd of farmers, butchers, and amiable amateurs. Galton, no democrat, collected the cards expecting to document the vox populi’s foolishness; instead the middlemost estimate came to 1,207 pounds against a true dressed weight of 1,198 — within eight-tenths of one per cent — and he published the result in Nature under the title the finding deserved, Vox Populi, conceding that the verdict spoke rather better of democratic judgement than he had anticipated (1907). His version generalises the jury from verdicts to estimates — take the median of many independent guesses rather than the majority of many independent votes — and the moral, branded by a later century as the wisdom of crowds, survives the change of arithmetic intact: a crowd of the individually unremarkable, if its errors are independent, is collectively formidable. The italicised clause is the entire theory; everything else is bookkeeping.
Read as engineering, then, the theorem is a specification with two clauses, and they are of very different practical character. Competence is the tractable one: it is a measurable, per-voter, per-domain quantity — exactly the track record that reputation (Section 12.4) accumulates and provenance (Chapter 9) records — and the specification says only that it clear one half, while warning that the whole apparatus inverts below it. Independence is the treacherous one, because correlation creeps in by every door. Jurors who share a training, a briefing, or a bias share errors; jurors who see one another’s votes before casting their own stop being jurors at all and become a cascade, each ballot polluted by the ballots before it — which is why deliberation sits so uneasily beside the theorem: letting the jury talk pools its information and, in the same breath, correlates its errors, a trade this book takes up when the agents start arguing in Chapter 14. The theory of the correlated jury exists, and its headline is mercifully simple (Ladha, 1992): correlation does not abolish the theorem, but it taxes it — correlated jurors count for less than their number, as though the jury were smaller than it looks, and in the limit of perfect correlation a thousand jurors are one juror, photocopied.
A thousand jurors that are one juror photocopied: the reader has already met such a jury, and has probably run one this week. Samples drawn from a single model share its training, its biases, and its blind spots wholesale; the independence clause is precisely the one the modern machinery flunks, and how much of the jury theorem’s promise survives the flunking — in self-consistency, in ensembles, in the panels of the moment — is what the next section weighs.
13.5 Juries of Correlated Minds: Ensembles and Self-Consistency
Machine learning has been running Condorcet’s theorem as an engineering programme since before anyone thought to call it that. An ensemble — several models trained and then made to vote — outperforms its members under exactly two conditions, and Dietterich’s classic analysis names them without ceremony: the members must be accurate, better than chance on the task, and diverse, wrong in different places (2000). Competence and independence, relabelled for the laboratory. And the celebrated ensemble methods are, read through this chapter, so many devices for manufacturing the second condition: bagging retrains each member on a different resampling of the data, so that no two inherit quite the same accidents; random forests go further and hide a different subset of the features from each tree, decorrelating by enforced ignorance. The discipline never cited the Marquis, but it spent two decades learning to build what he specified: juries whose members err apart.
Now audit the modern instance against the specification. Self-consistency — Chapter 5’s device, plurality over an electorate of samples — draws every juror from a single model (2022): one training run, one set of weights, one prompt, and the only wedge of independence in the whole arrangement is the sampling temperature, which jiggles the path each juror takes through its reasoning. That wedge is real but thin, and seeing precisely what it decorrelates explains both why the method works and where it must stop. Temperature randomises the slips — the dropped carry, the wrong turn taken once and not again — so that flawed reasoning paths scatter across many different wrong answers while sound paths, pulled by the same truth, converge on the same right one; the majority then harvests the convergence, exactly as the jury theorem promises. What temperature cannot touch is the model’s convictions: a systematic misconception, learned in training and shared by every sample at any temperature, arrives in juror after juror wearing the same confident face. Against slips, self-consistency is Condorcet’s machine in good order; against convictions, it is the photocopied juror of Section 13.4 — a thousand ballots, one mind.
The signature of that shared mind is visible in the accuracy curve, and worth learning to read. Plot accuracy against the number of samples and it climbs, then flattens — and the height of the plateau is set not by how many jurors you can afford but by the correlated component of their error, the part no amount of counting cancels. This is Ladha’s tax collected in tokens (1992): past the knee of the curve, every further sample is spent purchasing a verdict already delivered, and a ten-to-nought vote extended to twenty-to-nought has cost twice as much to say the same thing. The engineering that follows is blunt. Measure the curve rather than assuming it; stop sampling at the knee; and when the plateau sits below the accuracy you need, hear what the flatness is telling you — the residual error is systematic, and the remedy is not a larger jury of the same mind but a jury of different minds.
Different minds must be procured, and the procurement options form a hierarchy of expense and decorrelation. Cheapest is prompt diversity: rephrase the question, reorder the options, vary the worked examples — decorrelating the errors that the framing induced, which (as the framing-sensitivity of Section 12.6 attests) are not few. Next, method diversity: set one agent to solve by writing and running code and another by reasoning in prose, and their failure modes barely overlap — the arithmetic slip and the mistranslated requirement are different species of error, and a vote across them cancels both. Dearest and strongest is model diversity: members from different laboratories, different architectures, different training recipes — the closest thing on offer to Condorcet’s independent jurors, though the honest caveat is that the frontier laboratories drink from heavily overlapping corpora, so even this independence is partial, purchased by the degree of divergence in training rather than by the difference in logo. The principle organising all three is the one bagging and random forests already knew: diversify at the level where your errors correlate. Correlated by phrasing, vary the phrasing; correlated by method, vary the method; correlated by world-view, vary the model — and accept that the last correlation can be thinned but not abolished.
One refinement remains before the section’s ledger closes, and the theory endorses it with unusual crispness. Jurors are rarely equal, and counting them equally wastes what is known about them: the optimal rule for unequal jurors weights each vote by the logarithm of the odds that its caster is right: for juror i of competence p_i, errors independent as before,
w_i \;\propto\; \log \frac{p_i}{1 - p_i},
so that a juror at ninety per cent deserves several times the ballot of a juror at sixty, and one at fifty is rightly weightless (Nitzan & Paroush, 1982). The result licenses the weighted ensembles and score-blended panels the frameworks already offer, with one warning this book has issued before and will not tire of: the weight must come from the measured track record — the reputation of Section 12.4, the provenance-backed standing of Chapter 9 — and never from the juror’s own announced confidence, which in a language model is calibrated to persuade rather than to predict (Section 5.6). Weighting by self-assurance does not sharpen a jury; it hands the gavel to whichever member bluffs most fluently.
Everything in this section has aggregated verdicts — answers to questions with answers, the jury species doing what juries do. But a great deal of what an agent team actually needs aggregated is not a verdict but a grading: which of five candidate drafts is best, whether this response beats that one, how a piece of work rates on a rubric — questions where fact and taste blend, and where practice has drifted away from panels altogether toward a single arbiter, one model set over the candidates to rank them. That arbiter now sits in half the evaluation pipelines in production. The theory of this chapter has a name for a lone voice whose ranking simply is the collective ranking; Section 13.1 promised the introduction would be made with due ceremony, and the ceremony is next.
13.6 The Model as Judge: Dictatorship by Design
The arrangement just described — one model set over the candidates, its ranking final — has a precise name in the theory of this chapter, and the introduction can at last be performed. A decision procedure in which one participant’s ranking simply is the collective ranking, whatever anyone else thinks, is what Arrow’s fourth condition exists to forbid: a dictatorship. The word arrives trailing connotations the design does not deserve — nobody seized power; an engineer made a sensible call — but the technical reading repays the discomfort, because it explains something the informal view misses. Recall that dictatorship is the one arrangement Arrow’s theorem permits: satisfy universal domain, unanimity, and independence, and a dictator is what you must have. Read constructively rather than as a curse, that says a dictatorship delivers exactly what aggregation cannot — a single mind’s ranking is automatically transitive, cycles are impossible, the menu-sensitivity of irrelevant alternatives never arises, and no agenda-setter can play the order of comparisons against it. The judge model is not a lazy shortcut around social choice. It is one of the two coherent responses to Arrow — buy consistency at the price of one voter’s everything — and this section is about what, precisely, the price contains.
One precision, before the word is allowed to do more work than it can bear. Arrow’s dictator is, strictly, a voter: a member of the profile whose ranking the rule copies while everyone else’s is collected and ignored. Where the candidates’ authors submit no rankings at all, the judge is not that — there is no profile, no aggregation rule, and nothing for the theorem to forbid, because the election has not been rigged but declined, a design move Section 13.7 will endorse on its own merits. The name earns its keep, and the theorem does its explaining, exactly where there was an electorate to overrule — graders whose verdicts exist and are set aside, the last section’s jury convened and then dismissed — and it is that comparison, judge where a jury might have stood, that this section prices. The constructive reading survives on either framing, since one mind’s ranking is transitive, menu-proof, and agenda-proof whether or not anyone else was asked.
The empirical case for paying it was made properly by Zheng and colleagues, whose study gave the pattern its field name — LLM-as-a-judge — and its licence (2023). Set a strong model to judge chat responses — pairwise or by rubric — and its verdicts agree with human preferences over eighty per cent of the time, which is about as often as the humans agree with each other; the judge is, by that unnerving standard, as good a proxy for the crowd as another member of the crowd. Add the operational virtues — one call where a jury costs n, availability at any hour and any scale, verdicts that arrive with reasons attached — and the design’s conquest of practice needs no further explaining. For grading at the volume an agent pipeline requires, there is usually no electorate worth convening; the choice is not judge-versus-jury but judge-versus-nothing.
But a dictator’s quirks are the constitution, and the same study that licensed the judge catalogued its tastes. Position bias: presented with two candidates, judges favour the one shown first — swap the order and a comfortable share of verdicts swaps with it, which is not a property one wants in a constitution. Verbosity bias: longer answers are graded better, at fixed correctness, brevity being penalised as if it were an admission. And self-preference: a judge rates work higher when it is its own — an effect Panickssery and colleagues traced to self-recognition, the models proving able to distinguish their own generations and inclined to favour what they recognise (2024), nepotism implemented in the weights. Set these beside the jury and the structural point emerges: a jury’s idiosyncrasies are noise, scattered across members and cancelled by the count, but a dictator’s idiosyncrasies are policy, applied uniformly to every case that ever comes before the court. And policy, once stable, is a target. Candidates tuned against a judge — by selection, by prompt iteration, by reinforcement — learn the judge’s tastes rather than the task’s truth, padding their answers and angling for the favoured slot: the manipulation of Section 13.3 again, made easy, since a would-be manipulator now has only one voter to study and that voter’s leanings are stable, documented, and in several cases published.
The remedies, fittingly, amount to constitutional law — constraints on the dictator’s discretion, each targeting a named taste. Position bias is dissolved by symmetrisation: judge each pair in both orders and accept only agreements, which converts a systematic lean into random noise and, in effect, convenes a two-member jury out of one judge’s two sittings. Verbosity is dampened by length norms and by rubrics that separate the qualities a holistic score smears together — and a rubric is worth pausing on, because it is the discursive dilemma deployed as a tool: premise-wise judgement (is it correct? is it tested? is it clear?) constrains the arbitrary discretion of verdict-wise judgement, replacing taste with something closer to written law, at the price already disclosed — the decomposition itself becomes the substantive choice. Self-preference is met by separation of powers, the oldest constitutional device of all: the judge must never be the author, nor share the author’s weights, of anything it grades. And beneath all of these sits the audit: a judge is a jury of one, so the jury theorem applies with n=1 — the system’s accuracy simply is the judge’s competence p on this distribution, a measurable quantity, to be measured against ground truth rather than assumed from fluency. An unaudited judge is not an evaluation pipeline; it is a preference pipeline with delusions of objectivity.
Dilute the dictatorship, then: convene several judges and let them vote. Panels genuinely help — but notice what convening one does. A panel needs an aggregation rule, so Arrow and his retinue return at the meta-level; its members, drawn from the same few laboratories, are correlated jurors, so Section 13.5‘s ceiling returns with them; and a panel whose members include interested parties reopens strategic voting one floor up. The aggregation problem is not dissolved by adding a layer of aggregators; it recurs at every layer, and the panel is wise exactly insofar as its judges are competent and diverse — the same two clauses, billed again. The going refinement, letting the candidates or their advocates argue before the panel votes, trades the last of the jurors’ independence for a pooling of their information, a bargain the jury theorem has already priced and Chapter 14 will weigh in full: whether letting the agents argue makes the verdict better or merely better-defended (2024).
The chapter’s inventory is now complete — two species of aggregation, a shelf of rules with documented personalities, the impossibilities that bound them, the jury that redeems them, and the two modern architectures, correlated jury and constitutional dictator, that between them cover nearly every collective verdict an agent system takes. What remains is the question all of it was for: given the inventory, how should an engineer actually choose? That synthesis is the final section’s work.
13.7 Choosing How to Choose
An engineer standing before the chapter’s inventory needs a procedure, and the inventory itself supplies one — three questions, asked in order, that turn “how should we aggregate this?” from a vibe into a diagnosis. First, which species? If there is a fact of the matter, the vote is a jury, accuracy is the standard, and the good statistics of Section 13.4 are available on their two conditions; if there is not, the vote is a constitution-writing exercise, fairness is the standard, and Arrow’s country must be entered with the map out. Second, how many options? Two, and May’s harbour holds — majority rule comes with a uniqueness theorem and no small print; three or more, and every rule pays one of Arrow’s taxes, so the question becomes which tax the application can best afford. Third, who has stakes? Disinterested voters can be counted at face value; interested ones must be assumed, per Gibbard–Satterthwaite, to vote for what works — and a rule that survives honest voters and collapses under strategic ones has been tested against the wrong species of electorate.
Run the team’s own votes through the checklist and the answers fall out with satisfying speed. Ship or hold is the strong case — binary, factual, put to testers with no stake in the answer — and majority rule over independent checks carries both May’s uniqueness and Condorcet’s convergence; this is the vote to lean on hardest, and the reason this book keeps steering collective decisions toward gates. Choose among five candidate patches is the weak case — multi-option and hybrid — and the remedy is to spend structure on it: decompose into binary gates where the logic allows (does it pass? is it safe?), rubric the remainder premise-wise, and remember from Section 13.1 that the decomposition is itself the substantive choice. Grade at scale means a judge, which means a constitution: symmetrise, separate powers, audit against ground truth (Section 13.6). And divide the budget fails the third question so decisively — pure preference, all parties interested — that it should scarcely be a vote at all; what it should be instead is two chapters away.
| The vote | Species | Options | Who holds the stakes | Prescription |
|---|---|---|---|---|
| Ship or hold | Judgement (a fact) | Two | Disinterested testers | Majority rule over independent checks — carries both May’s uniqueness and Condorcet’s convergence; the vote to lean on hardest. |
| Choose among five candidate patches | Hybrid (fact and taste) | Many | — | Spend structure: decompose into binary gates where the logic allows, then rubric the remainder premise-wise — the decomposition is itself the substantive choice. |
| Grade at scale | Grading (fact and taste) | Many | — | A judge, which is a constitution — symmetrise, separate powers, audit against ground truth (Section 13.6). |
| Divide the budget | Preference (a taste) | Many | All parties interested | Scarcely a vote at all — give intensity a price and make it a market (Chapter 15). |
Where stakes cannot be removed, manipulation must be managed rather than mourned, and the tools come in three grades. The bluntest is architectural: keep the voters disinterested — evaluators who do not author, juries whose members gain nothing by the verdict — which is the separation of powers of Section 13.6 generalised into a staffing principle. The subtlest is computational, and it is the founding trick of the field this chapter has been quietly visiting: Bartholdi, Tovey, and Trick observed that Gibbard–Satterthwaite only guarantees a profitable manipulation exists, not that it can be found, and exhibited a rule whose winners are easy to compute but whose manipulation is NP-hard (1989) — complexity conscripted as a shield, the theorem outflanked rather than overturned. The honest asterisk is that worst-case hardness is a picket fence rather than a wall — typical instances are often easy to manipulate even when the worst case is hard — so the shield is thickening rather than protection outright. And the most durable tool is the oldest: make voting histories visible and manipulation costly in reputation (Section 12.4), so that gaming the count, even where feasible, does not pay twice.
The deepest design freedom, though, is the one the checklist saves for last: not choosing a better rule but declining to hold the election. Voting compresses everything a voter knows into a mark on a ballot, and sometimes the compression is the mistake. When disagreement stems from information — each agent has seen different evidence — the remedy is to pool the evidence, not count the conclusions: let them argue, which trades away the jury’s independence for something richer and is the business of Chapter 14. When disagreement stems from interest — the budget, the allocation, the scarce slot — a ballot cannot express how much anyone cares, only which way; intensity wants a price, the count wants to be a market, and that is Chapter 15. And when one agent demonstrably knows best, the theory itself counsels deference: the log-odds weights of Section 13.5, pushed to their limit by a juror far more competent than the rest, concentrate the decision on the expert — a dictatorship again, but this time earned, held on a track record measured against the world (Section 12.5), and revocable the day the track record turns. The dictator the chapter began by forbidding returns at its end with a licence: legitimacy, for aggregation as for everything else in Part IV, is a matter of what the arrangement can show for itself.
So the chapter’s thesis can be paid in full. Every multi-agent system holds elections; the constitution is code; and the difference between a system whose collective judgements can be trusted and one whose cannot is rarely the brilliance of the voters — it is whether anyone chose the rule, checked the species, measured the competence, guarded the independence, and audited the judge. The engineer who has read this far practises social choice the way M. Jourdain spoke prose, but now knowingly, which changes what the practice is worth. One assumption, though, has quietly governed even the strategic corners of this chapter: the agents expressed their positions and the rule did the rest — nobody made an offer, granted a concession, or changed anyone’s mind. The moment the voters begin to talk — to bargain over the budget rather than ballot on it, to argue the patch’s merits rather than grade them — aggregation gives way to negotiation, and the question stops being how to count positions and becomes how positions move. That is Chapter 14, where the agents finally argue — and where we ask the evidence, rather than the enthusiasm, whether arguing makes them any cleverer.
13.8 Summary
- Every multi-agent system holds elections, acknowledged or not. Self-consistency sampling, ensemble averaging, reviewer sign-offs, tie-breaking, and judge models are all voting rules; an aggregation rule chosen by accident is still a rule, and it carries the theory’s consequences whether or not anyone read the theory.
- Preferences and judgements are different cargo. Aggregating what agents want is a fairness problem with no right answer to track; aggregating what agents believe is an estimation problem with one. The dismaying theorems mostly govern the first, the heartening ones the second — and knowing which regime a vote lives in is the chapter’s first diagnostic skill.
- Every voting rule has a documented pathology. Plurality splits votes, Borda rewards burying, and Condorcet’s own principle can fail to name any winner at all, since majorities happily prefer A to B to C to A. When cycles are possible, whoever controls the agenda controls the outcome — a lesson worth remembering when an orchestrator decides the order in which options are compared.
- Arrow proved the pathologies are not accidents. No rule for three or more options satisfies a short list of individually innocuous requirements at once; May’s theorem marks the safe harbour (for exactly two options, majority rule is uniquely fair); and Gibbard–Satterthwaite adds that every non-trivial rule is manipulable — among agents with stakes, the ballot is a move, exactly as Chapter 12 taught.
- Condorcet’s jury theorem is the good news, and its conditions are an engineering checklist. If each voter is better than chance and voters err independently, majorities converge on truth as the electorate grows — and if either condition fails, the same arithmetic amplifies error instead. Competence and independence are not assumptions to hope for but properties to build and measure.
- Self-consistency and ensembling are juries, and correlation is their ceiling. Samples from one model are jurors who attended the same school and read the same books — temperature is the only independence on offer — and the jury theorem’s growth curve flattens exactly as fast as the jurors’ errors correlate; ensemble diversity is independence engineering by another name, which is why it works when it does and why it quietly stops.
- A judge model is a dictatorship, adopted for convenience. A single arbiter over the panel holds the office Arrow’s fourth condition forbids a voter — the one ranking that is final whatever anyone else submits; where no one else ranks at all, the election has been declined rather than rigged. Cheap, consistent, and decisive, which is why the design is everywhere — but its position, verbosity, and self-preference biases are enthroned with it as the group’s taste, and a dictator’s quirks are the constitution. Judge panels dilute the dictatorship at the price of reopening the voting problem one level up.
- Choosing how to choose is a design act, not a default. There is no neutral aggregation rule, only trade-offs picked deliberately or inherited blindly; binary gates are the theorem-proof case; manipulation can be priced out but not abolished; and some collective decisions should not be votes at all — they should be arguments (Chapter 14), markets (Chapter 15), or deference to demonstrated competence.
13.9 Exercises
Exercise 1. The orchestrator puts three candidate refactorings, A, B, and C, to a panel of nineteen evaluation agents, each of which returns a full ranking, and the profile comes back: six rank A \succ C \succ B; four rank B \succ A \succ C; three rank B \succ C \succ A; four rank C \succ A \succ B; and two rank C \succ B \succ A. (a) Determine the plurality winner. (b) Determine the Borda winner, showing all three scores and checking that they sum to 3 \times 19 = 57 — say why they must. (c) Tally all three pairwise contests; identify the Condorcet winner, if one exists, and the candidate that loses every contest it enters. (d) The three rules return three different winners: explain each verdict from the rule’s personality in Section 13.2 — what each rule read in the ballots and what it ignored — and state the relation between the plurality winner and the pairwise tallies that makes this profile Borda’s 1781 complaint in its strongest form. (e) Suppose the orchestrator instead eliminated candidates by sequential pairwise comparison under some running order: show that here the agenda cannot matter, and state the general fact about sequential elimination that this profile instantiates and the next exercise’s does not.
Exercise 2. An orchestrator whittles four candidate patches, W, X, Y, and Z, through sequential pairwise elimination: the first two candidates on the agenda are compared by a judge model, the winner meets the third, that winner meets the fourth, and the last survivor ships. Careful probing shows the judge’s pairwise verdicts are stable: it prefers X to Y, Y to Z, Z to X, and each of X, Y, Z to W. (a) Show that no ranking of the four candidates is consistent with these verdicts, and that the profile has no Condorcet winner but does have a Condorcet loser. (b) There are 4! = 24 agendas; determine, by exhaustive enumeration in code or by hand with a symmetry argument, how many agendas crown each candidate. (c) The orchestrator privately favours Z: exhibit an agenda under which Z ships, trace the eliminations, and state the general recipe for crowning any chosen member of the cycle. (d) Prove that no agenda ships W. (e) A colleague proposes drawing the agenda uniformly at random, “to be neutral”: say exactly what lottery this implements, and draw the operational lesson for any pipeline in which a judge’s pairwise verdicts might cycle — which the biases catalogued in Section 13.6 make an observed fact, not a theoretical nicety.
Exercise 3. The team’s policy is that a patch merges exactly when it is correct and adequately tested. Three reviewer agents each assess both premises, and every premise-judgement is independently right with probability 4/5, independence holding across reviewers and across premises. Two constitutions are on the table: premise-wise — majority vote on each premise separately, merge iff both premises pass — and conclusion-wise — each reviewer votes to merge iff it judged both premises true, and the majority of merge-votes decides. (a) For a merge-worthy patch (both premises in fact true), compute each constitution’s probability of reaching the right verdict, in exact fractions. (b) Repeat for a patch that is in fact correct but inadequately tested. (c) Let \pi be the proportion of merge-worthy patches in the gate’s traffic, the remainder all being of the correct-but-poorly-tested kind: find the threshold value of \pi at which the two constitutions’ overall accuracies cross, and say which constitution the team should adopt, and by how many points, if roughly thirty-five per cent of its candidate patches are merge-worthy. (d) Explain the mechanism behind the flip — consider two reviewers whose single slips land on different premises — and reconcile the whole exercise with List and Pettit’s impossibility (Section 13.1): what exactly does the theorem forbid, and what does it leave the engineer free to measure and choose?
Exercise 4. The team must fix how aggressive the coming refactor will be, on a five-point scale from 1 (touch nothing but the bug) to 5 (rewrite the module). The five agents’ ideal points are 2, 2, 3, 5, 5; each agent prefers options nearer its ideal, and where two options are equidistant it prefers the safer, smaller one. (a) Write out all five rankings and verify that each is single-peaked with respect to the scale. (b) Tally all ten pairwise contests; show that the majority relation is a transitive linear order; and check Black’s promise from Section 13.3: the Condorcet winner is the median ideal. (c) Now let the group decide by the median mechanism — each agent reports an ideal point and the median report is adopted. Show by enumerating its five possible reports that the agent with ideal 5 cannot profit from any misreport, give the two-case argument that no agent ever can, and explain precisely why this does not contradict Gibbard–Satterthwaite. (d) Construct a three-agent, three-option profile on the same scale in which exactly one ranking fails single-peakedness and the majorities cycle; conclude in a sentence what the engineer buys, in Arrow’s terms, by putting a scale rather than an arbitrary menu on the ballot.
Exercise 5. Gibbard–Satterthwaite guarantees that profitable lies exist; measure how common and how findable they are on the smallest interesting electorate. Take three candidates, three voters, and deterministic alphabetical tie-breaking throughout. (a) Implement the Borda and plurality winner functions and a brute-force manipulation search, and count, over all 6^3 = 216 profiles, those at which voter 1 can obtain a strictly preferred winner by misreporting its ranking, under each rule. (b) For the profile in which voter 1 sincerely ranks A \succ B \succ C and the other two vote B \succ A \succ C and C \succ B \succ A, verify the Borda manipulation by hand: the sincere scores, the profitable lie, and the scores it produces. (c) Classify what the search found: under which rule does every profitable lie abandon the voter’s sincere favourite, under which does the typical lie keep the favourite on top while demoting a rival, and which documented personality of each rule (Section 13.2) do the two signatures express? (d) Relate the exercise to Section 13.7: what Gibbard–Satterthwaite asserts, what your census adds to the assertion, and what your search’s running time says about how much protection Bartholdi-style computational hardness offers at this scale.
Exercise 6. The ship-or-hold gate is to be manned by a jury of tester agents, each independently correct with probability p = 0.7, each costing 400 tokens per verdict; a wrong collective verdict costs an expected 40{,}000 tokens of rework. Write P_n for the majority accuracy of Section 13.4. This is Chapter 5’s self-consistency drill — the same P_n(0.7) and smallest-odd-n-to-a-threshold — recast as an economic optimum: not how many samples reach an accuracy, but how many jurors are worth their tokens. (a) Compute P_3 and P_5 exactly. (b) Find the smallest odd n for which P_n \ge 0.99. (c) The budget office proposes instead minimising the expected total cost \mathrm{cost}(n) = 400\,n + 40{,}000\,(1 - P_n): find the minimising odd n, and compare its cost with the lone-tester gate and with the jury of (b). (d) Show that the optimum in (c) obeys a marginal rule — enlarge the jury by two so long as the accuracy gain, priced in avoided rework, exceeds the 800 tokens the pair costs — exhibit the two marginal gains that bracket the optimum, and say in one sentence why “how many jurors?” is an economic question and not a purely statistical one.
Exercise 7. The gate’s questions are not all alike: a fraction h = 1/4 of them are hard, and each tester is right with probability p_{\mathrm{easy}} = 0.9 on the easy ones but only p_{\mathrm{hard}} = 0.4 on the hard ones. (a) Compute the testers’ marginal competence \bar{p} over the mixed stream, confirm it clears one half comfortably, and compute the accuracy that a naive reading of the jury theorem — P_n(\bar{p}), writing P_n(p) for the majority accuracy at competence p — promises at n = 21. (b) Justify the true accuracy A_n = (1-h)\,P_n(p_{\mathrm{easy}}) + h\,P_n(p_{\mathrm{hard}}) and compute it at n = 1, 3, 5, 7, 21. (c) Find \lim_{n \to \infty} A_n, the odd n at which A_n peaks, and the first odd n at which the jury is worse than a single tester. (d) Explain the shape: which half of Section 13.4 governs each slice of the stream, what should an engineer measure to detect the situation, what will the votes on the hard slice look like as n grows — and restate the italicised clause of the chapter that the comfortable marginal figure \bar{p} fails to honour.
Exercise 8. A self-consistency harness (Chapter 5) draws five samples. The tempting wrong answer always arrives as the same string, with probability 2/5 per sample; the correct answer arrives in one of three phrasings, each with probability 1/5. (a) With sound clustering — the three phrasings counted as one candidate — compute the exact probability that the majority verdict is correct. (b) Without clustering, the harness counts distinct strings and breaks ties uniformly at random among the leaders: compute the exact probability of a correct return by enumerating all 4^5 draws in exact fractions (fractions.Fraction over itertools.product does it in a dozen lines). (c) Set both figures beside the accuracy of a single sample, name the classical pathology of Section 13.2 that the naive count exhibits, and state the finding plainly: what did holding the election without electoral reform do to the harness? (d) Clustering is itself a rule about which ballots name the same candidate: say what happens to the reformed election if the clusterer fuses the wrong answer with one of the correct phrasings, and conclude what the equivalence judgement must protect for the reform to deserve the name.
Exercise 9. The companion repository’s foundations/algorithms/jury.py carries the chapter’s three tools: p_majority, the Nitzan–Paroush weights, and effective_jury_size, the design-effect heuristic n_{\mathrm{eff}} = n / (1 + (n-1)\rho). (a) For samples from one model with pairwise error correlation \rho = 1/4, compute n_{\mathrm{eff}} at n = 25 and its limit as n \to \infty; the n required to reach n_{\mathrm{eff}} = 3.5 and n_{\mathrm{eff}} = 3.9; and the \rho at which twenty-five samples would be worth ten independent jurors — say what the middle pair of answers prices. (b) Now give the correlation a structure: each juror, independently with probability c, copies one shared draw, and otherwise draws privately; shared and private draws are each correct with probability p. Show that the correlation between two jurors’ correctness indicators is c^2, then write a seeded simulation extending the module’s vocabulary and confirm the estimate empirically at c = 0.5 and c = 0.25. (c) Simulate majority accuracy at p = 0.7 for both values of c at n = 5, 25, 101, 1001; derive analytically the limiting accuracy as n \to \infty, including the threshold c^* at which its character changes; and reconcile the early peak and slow decline of the c = 0.5 column with Exercise 7. (d) Confront the heuristic with the structure: what plateau does n_{\mathrm{eff}} \to 1/\rho suggest at \rho = 1/4, what does the simulation deliver, which of the chapter’s claims about correlated juries survive the confrontation intact — and how do the copy events and the private draws map onto the slips and convictions of Section 13.5?
Exercise 10. Three review agents hold measured track records of p_1 = 0.9, p_2 = 0.7, and p_3 = 0.6 on binary bug calls, their errors independent. (a) Compute their Nitzan–Paroush weights w_i \propto \log\bigl(p_i/(1-p_i)\bigr). (b) Show exactly that the first agent’s weight exceeds the other two combined, conclude how the weighted rule behaves on every one of the eight vote patterns, verify by enumerating the patterns’ likelihoods that this rule is Bayes-optimal, and compute the accuracy of the weighted rule and of simple majority. (c) The two weaker agents are upgraded to a common competence q: derive the threshold value of q above which the pair, agreeing, outvotes the expert. (d) Compute the panel’s accuracy at q = 0.8 under the weights, and then read the whole exercise through the close of Section 13.7: in what precise sense is the rule of (b) a dictatorship, what makes it legitimate where the unaudited judge of Section 13.6 is merely convenient, and why must the p_i be measured track records rather than the agents’ own announced confidence?
Exercise 11. A judge model compares pairs of candidate patches, one of which is genuinely better. With probability 1/5 it endorses whichever candidate is listed first, regardless of merit; otherwise it judges on merit and names the better candidate with probability 3/4. (a) Compute its accuracy when the better candidate is listed first; when it is listed second; when the order is set by a fair coin; and when the order is set by an adversary — the author of the worse patch controls the listing. (b) The pipeline symmetrises (Section 13.6): the judge sits twice, once per order, with merit judgements independent across sittings, and disagreements are settled by a fair coin. Compute the probabilities of correct agreement, wrong agreement, and disagreement, and the resulting accuracy; compare with (a) and say precisely what symmetrisation has bought and what it has not. (c) Instead of the coin, disagreements are escalated to a stronger arbiter: compute the accuracy conditional on agreement and the fraction of pairs escalated, state what the arrangement costs, and say in what sense one judge has become a two-member jury — and which rule from Table 13.1 the agreement filter is. (d) Redo (b) and (c) assuming the merit judgement is perfectly correlated across the two sittings — the same conviction, delivered twice — and draw the moral: which clause of Section 13.4 do the two sittings satisfy with respect to the position lean but flunk with respect to the convictions?
Exercise 12 (lab). Audit a live judge for the dictator’s tastes of Section 13.6. Build at least twenty pairs of candidate answers whose ground truth you control — for instance, a correct and a subtly buggy implementation of small functions from the team’s repository, the bug planted by you — and have one model, at fixed settings, judge every pair in both orders, recording every verdict. Measure: the first-slot rate f over all judgements, and hence the position-lean estimate \hat{b} = 2f - 1 that the model of Exercise 11 implies; the flip rate — the fraction of pairs whose verdict reverses when the order does; and the accuracy of a single random-order sitting against symmetrised agreement-only judging, together with the escalation rate. Then, for at least ten triples of candidates, obtain all three symmetrised pairwise verdicts and count intransitive triples, connecting any you find to Exercise 2’s finding about who chooses the winner when verdicts cycle. Record the model identifier and the date beside every table: the durable finding is the pattern — whether a lean exists and in which direction, that symmetrisation restores order-invariance by construction, whether agreement-filtered verdicts beat single sittings — not any absolute rate; and note that at this sample size a lean smaller than roughly 0.16 in \hat{b} is indistinguishable from noise, so scale the pair count to the lean you care to detect.