Matpic
mathematics, in pictures
Concept

Majority

The rule that accepts a proposition when more than half of those voting do. It is the only anonymous rule treating acceptance and rejection alike, and on an agenda whose propositions imply one another it can produce a collectively inconsistent verdict.

Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.

3 consistent judges, and a majority that is not. A table of judges against three questions, every judge's row internally consistent, with the majority answer to each question underneath forming a combination no judge holds.

The court that contradicts itself

Three judges each answer three questions, and each answers them consistently. Take the majority on each question separately and the answers no longer hang together — the body as a whole endorses a combination no member of it holds, and no rearrangement of the procedure removes the problem.

applied · Judgement aggregation 16 rules, and none that survives. A table of every systematic anonymous aggregation rule for 3 judges: one row per rule, showing the verdict it gives at each count of yes-votes, whether it decides every proposition, and whether it is consistent. No row has both.

No rule escapes the doctrinal paradox

A court whose members each hold a consistent position can reach an inconsistent verdict by majority. One such case is easy to build, which invites the hope that a better rule would avoid it — and every rule that responds to the votes at all fails somewhere.

applied · Judgement aggregation Where the two procedures part company. A table of 3 judges' verdicts on two premises and the conclusion each is committed to, with the two majorities at the foot disagreeing about the conclusion.

Deciding the premises or the conclusion

A body that cannot be both decisive and coherent has to choose which. The two live options are to vote on the reasons and let the verdict follow, or to vote on the verdict and let the reasons look after themselves — and they reach opposite answers on exactly the profiles the impossibility identifies.

applied · Judgement aggregation A local rule taking a vote. A space-time diagram of the GKL rule on 149 cells from a random row with 69 ones. Black and white regions grow and meet along slanting boundaries, and after 69 steps the whole ring is 0.

No local rule can count the votes

A ring of cells, each holding 0 or 1, has to agree on whichever value is in the majority — every cell seeing only its neighbours. The best-known rule gets it right most of the time and wrong near a tie; no rule of any radius gets it right always. Yet two rules run one after the other do, on every ring, and the first of them is the traffic rule.

dynamics · Cellular automata Smallest circuits for four functions of three letters. Four small circuit diagrams, each with three inputs feeding a few two-input gates, computing parity, a selector, majority and exactly-one-true with two, three, four and four gates.

How many gates a truth table needs

Every truth function can be built from gates, and the natural measure of a function is the fewest gates that build it. For three letters the whole answer can be computed: no function needs more than four. For n letters, a count shows that almost every function needs about 2ⁿ/n gates, and a construction shows that none needs more. And for any function anyone can actually write down, the best proof in fifty years says it needs 3.1n.

logic · Truth functions

Named alongside it

The objects these essays reach for when they reach for this one.

AggregationConsistencyExhaustive searchImpossibilityVoting ruleJudgement aggregationLogicAxiomBoolean circuitCellular automatonCircuit complexityComputation

All concepts