Matpic
mathematics, in pictures
The collection

Every essay — page 38

Page 38 of 38, continuing through the fields in the same order.

Geometry Analysis Algebra Discrete Topology Probability Number Dynamics Logic Computation Applied What's new Series Concepts Search

Applied

A rule for choosing, stated exactly, and what it forces on whoever adopts it.

The cheapest tree for a remote user between two near ones, and each user paying for its own link. A source and 3 users with link costs source–A 2, source–B 9, source–C 2, A–B 1, B–C 1, A–C 2; the cheapest tree costs 4 and Bird's rule charges 2, 1, 1.

Each user pays for its own last link

6 figures Every majority pattern on 5 candidates, and the fewest voters that make it. 12 tournaments on 5 candidates: wins 22222 needs 3; wins 32221 needs 3; wins 32221 needs 3; wins 32221 needs 3; wins 33211 needs 3; wins 33211 needs 3; wins 42211 needs 3; wins 43111 needs 3; wins 33220 needs 3; wins 42220 needs 3; wins 33310 needs 3; wins 43210 needs 1.

How few voters any majority needs

5 figures Dodgson's rule: the fewest swaps that make a Condorcet winner. Profile of 9 ballots with no Condorcet winner; Dodgson scores A 1, B 2, C 3, D 6; Borda scores A 15, B 16, C 14, D 9; Copeland A 1, B 1, C 1, D −3.

The fewest swaps to a winner

5 figures Two triangles and three paths: the relaxation against the shortest tour. k = 3: 12 cities; subtour relaxation 12 with 6 half-edges; shortest tour 14; ratio 1.167.

A bound that may be off by a third

5 figures Christofides' algorithm: tree, pairing, tour. 12 cities: tree 2.4441, 6 odd cities paired for 1.5306, tour 3.6069, shortest 3.4606.

Tours within half again of the best

5 figures What survives on each agenda, 3 judges. A table of four agendas with, for each, the size of its largest inconsistent set, the number of independent unanimous rules for 3 judges, how many are consistent on every profile, and how many of those are dictatorships, oligarchies and other rules: two unconnected questions 324 of 324; a chain of two thresholds 129 of 324; two premises and their conjunction 7 of 5,832; a ranking of three options 3 of 5,832.

What the agenda leaves standing

7 figures Three splits that between them beat every other. The triangle of splits of one pound among three players, with the three half-and-half splits marked and every other lattice point coloured by which of the three dominates it: 134, 134, 134 beaten by exactly one, 91 by more.

Three splits that answer every other

6 figures No prices clear a market for a pair worth 3. The plane of prices for items A and B, with the triangle pA + pB ≤ 3 where buyer 1 wants the pair and the square pA, pB ≥ 2 where buyer 2 wants neither; they do not meet.

Prices for things wanted only together

7 figures Every envy-free way to split one rent among three rooms. A triangle of rent splits of 90 with the envy-free hexagon (corners 30, 30, 30; 46.7, 21.7, 21.7; 50, 25, 15; 45, 35, 10; 35, 40, 15; 28.3, 33.3, 28.3) and the maximin, equal and grid splits marked.

A rent nobody envies is not one rent

6 figures What a seller collects under first-price and second-price rules. Histograms of 20000 simulated revenues with 3 uniform bidders: second-price mean 0.4988, variance 0.0497; first-price mean 0.4995, variance 0.0167.

Two auctions that earn the same

6 figures Luxembourg's votes and Luxembourg's power, 1958 to 1995. Paired bars for Luxembourg at five enlargements of the Council: vote share falling and power share rising from nothing in 1958 to 0.95% in 1973 and 3.02% in 1981.

A vote worth nothing until it was outnumbered

6 figures Three kinds of member, and a triple that breaks a grouping. Two copies of one market with three members of each of three kinds and cyclic preferences: on the left a grouping blocked by the triple B, 1, p; on the right a stable grouping.

A third kind of member

5 figures How often each procedure finds the right verdict, with 3 judges of competence 0.7. both true: liable: premises 61.5%, conclusion 48.5%; first only: not liable: premises 83.1%, conclusion 88.6%; second only: not liable: premises 83.1%, conclusion 88.6%; neither: not liable: premises 95.3%, conclusion 97.7%; average 80.7% against 80.9%.

Which vote finds the truth more often

6 figures · new What a left glove is worth as the market tips. For 20 players and L from 1 to 19: the core value of a left glove (1 below 10, any value at 10, 0 above) and the Shapley value, from 0.950 to 0.003.

One glove too many

5 figures · new