The collection

Every essay — page 49

Page 49 of 49, 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 trades a buyer and seller cannot make. Uniform private values: efficient surplus 1/6; best incentive-compatible, individually rational, budget-balanced mechanism trades iff b − s ≥ 1/4, surplus 9/64 = 27/32 of the efficient.

Some good trades cannot be made

The cheapest tree through forty points. n=40, seed 8: total 1.063675, largest edge 0.0605, ζ(3)=1.2020569.

The cheapest tree costs ζ(3)

A relaxation that answers in halves. x = ½,½,½,½,½,1,0,0,½,½,½; LP 5; whole cover 6.

A relaxation that answers in halves

A block of shares in an ocean of small holders. a=0.02: exact 0.0249, limit 0.0204; a=0.06: exact 0.0647, limit 0.0638; a=0.1: exact 0.1144, limit 0.1111; a=0.14: exact 0.1642, limit 0.1628; a=0.18: exact 0.2139, limit 0.2195; a=0.22: exact 0.2836, limit 0.2821; a=0.26: exact 0.3532, limit 0.3514; a=0.3: exact 0.4229, limit 0.4286; a=0.34: exact 0.5124, limit 0.5152; a=0.38: exact 0.6119, limit 0.6129; a=0.42: exact 0.7214, limit 0.7241; a=0.46: exact 0.8507, limit 0.8519; a=0.5: exact 0.9950, limit 1.0000; a=0.54: exact 1.0000, limit 1.0000; a=0.58: exact 1.0000, limit 1.0000

A block in an ocean of small holders

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

6 figures · new

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

6 figures · new