The collection

Every essay — page 50

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

How often a game picked at random has a core. n=3: 0.20:1.000 0.24:1.000 0.28:1.000 0.32:1.000 0.36:1.000 0.40:1.000 0.44:1.000 0.48:1.000 0.52:1.000 0.56:1.000 0.60:1.000 0.64:1.000 0.68:1.000 0.72:0.997 0.76:0.993 0.80:0.980 0.84:0.958 0.88:0.933 0.92:0.899 0.96:0.872 1.00:0.833; n=4: 0.20:1.000 0.24:1.000 0.28:1.000 0.32:1.000 0.36:1.000 0.40:1.000 0.44:1.000 0.48:1.000 0.52:0.991 0.56:0.937 0.60:0.843 0.64:0.737 0.68:0.634 0.72:0.517 0.76:0.424 0.80:0.323 0.84:0.258 0.88:0.182 0.92:0.134 0.96:0.091 1.00:0.066; n=5: 0.20:1.000 0.24:1.000 0.28:1.000 0.32:1.000 0.36:1.000 0.40:1.000 0.44:0.994 0.48:0.904 0.52:0.725 0.56:0.438 0.60:0.245 0.64:0.116 0.68:0.059 0.72:0.022 0.76:0.009 0.80:0.002 0.84:0.002 0.88:0.001 0.92:0.001 0.96:0.000 1.00:0.000

A core is a rare thing to find at random

One weak element drags both procedures down. p1=0.55: premise 0.6331, verdict 0.5607; p1=0.6: premise 0.7535, verdict 0.6834; p1=0.7: premise 0.9218, verdict 0.8754; p1=0.8: premise 0.9883, verdict 0.9717; p1=0.9: premise 0.9997, verdict 0.9978

The element the judges are worst at

How often each rule finds the Condorcet winner. n=3: 0.8824/0.9412/0.9559/0.6471; n=5: 0.8259/0.9751/0.9378/0.6866; n=7: 0.8281/0.9578/0.9278/0.6833; n=11: 0.8054/0.9656/0.9179/0.7079; n=21: 0.7941/0.9619/0.9097/0.7205; n=51: 0.7804/0.9624/0.9046/0.7339; limit 0.7572±0.0009/0.9629±0.0004/0.9011±0.0006/0.7563±0.0009; P(CW) limit 0.9116.

How often the rules find the majority favourite

The number of stable matchings in a random market. n=10 (400): mean 3.03±0.10, median 3, 10-90% 1-5, max 20, e^-1 n ln n 8.5; n=20 (400): mean 6.34±0.18, median 6, 10-90% 3-10, max 33, e^-1 n ln n 22.0; n=40 (400): mean 15.51±0.48, median 13, 10-90% 7-26, max 87, e^-1 n ln n 54.3; n=70 (400): mean 33.10±0.92, median 29, 10-90% 16-56, max 147, e^-1 n ln n 109.4; n=100 (400): mean 54.84±1.46, median 48, 10-90% 26-90, max 230, e^-1 n ln n 169.4; n=150 (400): mean 93.47±2.51, median 79, 10-90% 49-164, max 350, e^-1 n ln n 276.5; n=200 (200): mean 144.33±5.75, median 128, 10-90% 71-229, max 589, e^-1 n ln n 389.8; n=300 (100): mean 239.96±12.32, median 203, 10-90% 128-409, max 669, e^-1 n ln n 629.5; n=500 (40): mean 409.55±24.38, median 410, 10-90% 212-663, max 799, e^-1 n ln n 1143.1; n=700 (16): mean 648.44±83.83, median 573, 10-90% 323-1286, max 1504, e^-1 n ln n 1687.0; n=1000 (10): mean 1053.30±211.84, median 807, 10-90% 458-2467, max 2467, e^-1 n ln n 2541.2

How many stable matchings a market has

Sellers in a square town

An optimal way to divide 9 soldiers among three battlefields. Colonel Blotto with 9 soldiers each on three fields: 55 allocations, optimal mixture on 7: 6-3-0:0.143 5-0-4:0.143 4-4-1:0.143 3-1-5:0.143 2-5-2:0.143 1-2-6:0.143 0-6-3:0.143.

Two colonels and a linear programme

An arrival order that punishes a plain rule. Upper triangular instance with 6 workers and 6 jobs: a rule that takes the last suitable job matches 3, the best matching in hindsight 6.

Matching workers who will not wait

Whose vote counts in a two-tier election. Relative chance a voter decides a two-tier vote, districts 9,25,49,81,121,169,225. one vote per district: 2.319 1.367 0.971 0.754 0.616 0.521 0.452. weight in proportion to voters: 0.501 0.296 0.630 0.815 1.466 1.240 2.051. weight in proportion to √voters: 1.021 1.003 0.998 0.996 0.995 0.994 0.994.

A vote worth a square root

Everything that beats one proposal. Five voters in the plane and the set of points beating the proposal (0.5, 0.6) by a majority, area 1.842.

A chain of majorities leads anywhere

Ten stable matchings on four a side. The market of four a side made by doubling, with all 10 of its stable matchings joined by the rotations that lead from one to the next, 18 in all.

The market with the most stable matchings

Three widows and the Mishna's table. The Mishna's division of estates of 100, 200 and 300 among claims of 100, 200 and 300: 33⅓ each; 50, 75, 75; 50, 100, 150.

The debts the Mishna divided

6 figures · new

Six goods, three people, and no envy. Three people's random values for six goods, with an envy-free allocation shaded: Ada values the bundles at 0.86, 0.85, 0.34; Ben values the bundles at 0.64, 1.83, 0.75; Cy values the bundles at 1.05, 1.24, 1.29.

Twice as many goods as people

6 figures · new