The collection

Every essay — page 33

Page 33 of 33, 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.

A majority of independent voters, more often right than any of them. The probability that a simple majority of n independent voters is right, for n from 1 to 201, when each voter is right with probability 0.45, 0.51, 0.55, 0.6, 0.7.

A majority wiser than its members

Who does well in a random market, as it grows. A log-log plot of the average rank of partner for the proposing side and the receiving side of random balanced markets against the market's size, with dashed curves for ln n and n over ln n.

One extra person on one side

15 stable matchings, by what each side pays. A scatter plot of every stable matching of one instance by the total rank each side receives, running from side one's best matching to side two's, with the median, the least-total and the most even matchings marked.

The matching in the middle

Envy-free up to one item, and up to any: three people, five items. A value matrix for three people, five items with two allocations beneath it: one envy-free up to one item but not up to any, and one envy-free; the counts over all 243 allocations beside it.

Envy that any single item would cure

Dividing a rent of 90 three ways, on a 9-step grid. A triangle of possible rent splits, triangulated into 81 small triangles, with each grid point coloured by the room its housemate would pick; 3 small triangles have all three rooms.

A rent nobody envies

An auction for 4 objects, bid by bid, with increment 1/5. A 4 by 4 table of values beside the log of 12 bids of an auction with increment 1/5: bidder, object, the raise, and the prices after each bid; it ends with total value 26.

Prices the bidders raise

The core of a market with two houses and two buyers. The core of an assignment game drawn in the plane of buyer A's payoff against buyer B's, a polygon with vertices (0, 1), (0, 0), (1, 0), (4, 3), (2, 3); the buyers' best corner is (4, 3).

The prices nobody can break away from

3 moves along the edges to the corner that maximises 2x₁ + 3x₂. The simplex method on a two-variable program with 5 constraints, started at the origin. It visits (0, 0), (0, 8), (1, 8), (5/2, 15/2), with objective values 0, 24, 26, 55/2, and stops where the prices on both binding constraints are non-negative.

Prices at every corner

Eight corners of a squashed cube, visited in order by the simplex method. Klee and Minty's program in 3 variables drawn as its own deformed cube and as a plain one. The simplex method with the largest-price rule visits all 8 corners, with objective values 0, 4, 6, 10, 15, 19, 21, 25; the optimum is one edge from the start.

The cube that takes every corner

The core of a group worth the square of its size: the outline of its six arrival orders. Splits of 9 among three players; core corners (1, 5, 3), (5, 1, 3), (1, 3, 5), (5, 3, 1), (3, 1, 5), (3, 5, 1); arrival-order splits (1, 3, 5), (1, 5, 3), (3, 1, 5), (5, 1, 3), (3, 5, 1), (5, 3, 1); average 3, 3, 3.

The corners are the orders of arrival

6 figures · new

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 · new

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 · new

The fewest swaps to a winner

5 figures · new