Matpic
mathematics, in pictures
The collection

Every essay — page 7

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

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

Applied

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

better for side one, worse for side twoM1 A4 B2 C1 D3side one's ranks 2, 2, 2, 2M2 A3 B2 C1 D4side one's ranks 3, 2, 2, 3M3 A4 B1 C2 D3side one's ranks 2, 4, 3, 2M4 A3 B1 C2 D4side one's ranks 3, 4, 3, 3join and meet, on every pairpairjoinmeetM1, M2M1M2M1, M3M1M3M1, M4M1M4M2, M3M1M4M2, M4M2M4M3, M4M3M44 of the 24 matchings are stable, drawn with the best for side one at the topevery one of the 16 ordered pairs was joined and met, and all 32 results were themselves stablethe top A4 B2 C1 D3 is what side one proposing returns; the bottom A3 B1 C2 D4 is what side two proposing returns

The side that proposes wins

An instance usually has several stable matchings, and the set of them is not a heap — it is a lattice, closed under taking the better partner and under taking the worse. The two ends of that lattice are exactly what deferred acceptance returns from the two sides, so whoever proposes decides which end the instance lands on.

8 figures 4's true ranking of side one, best firstCDAtruthfulBtruthfully: A4 B2 C1 D3one cell per ranking 4 could submit, labelled with the partner it returnsAAAAAABBBBBBAABBADAADDADthe true rankinga ranking that paysthe 4 profitable misreports, submitted ranking and partner obtainedsubmittedpartnertrue rankCDBAD2 of 4DBACD2 of 4DBCAD2 of 4DCBAD2 of 4the control: the same search, every member of both sides, 24 rankings eachside onepaysside twopaysA010B020C030D0444 truly ranks side one CDAB and gets A, its 3rd choiceof the 24 rankings it could submit instead, 4 return a partner it strictly prefersthe same sweep over every member of the proposing side searched 96 rankings and found none, which is whatmakes the 4 a finding

No stable rule is safe from a lie

A stable matching always exists, and the side that proposes gets the best one it could hope for. This essay closes the ladder with the result that spoils it — one participant's whole strategy space searched, four submissions found that beat the truth, and a theorem saying no rule anywhere escapes.

8 figures primal: max 3x₁ + 4x₂dual: min 12y₁ + 10y₂3x₁ + 2x₂ ≤ 12x₁ + 4x₂ ≤ 103y₁ + y₂ ≥ 32y₁ + 4y₂ ≥ 401234501234x₁x₂78/512100(14/5, 9/5)00.511.522.5301234y₁y₂78/53024(4/5, 3/5)05101520253078/51210078/53024they meet at 78/5primal vertex values, from belowdual vertex values, from aboveweak duality checked on all 12 pairs — each of the 4 feasible primal vertices against each of the 3 feasible dual vertices — andcᵀx ≤ bᵀy held every timestrong duality is the equality of the two optima: max 3x₁ + 4x₂ = 78/5 = min 12y₁ + 10y₂, one number reached from below andfrom abovethe dual region is unbounded upward and the drawing cuts it at the box; the enumeration ignores the cut

Two numbers that have to meet

Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.

8 figures 51015202530051015202530b₁max 3x₁ + 4x₂b₁ = 5b₁ = 30slope 2 = y₁slope 4/5 = y₁slope 0 = y₁one row per linear piecethe optimum sits onslope of the optimumdual variable y₁b₁ from 2 to 5b₁ from 5 to 30b₁ from 30 to 32row 1 and x₁ = 0(0, 5/4)22row 1 and row 2(1/5, 49/20)4/54/5row 2 and x₂ = 0(10, 0)00the optimum is piecewise linear in b₁ with 3 pieces, breaking at b₁ = 5 and 30on each piece the slope, taken from the optima at the two ends, equals the dual variable y₁ at the middleof that piece — 2, then 4/5, then 0 — and it changes exactly where a different vertex becomes optimal

What a constraint is worth

The rung below settled that a linear program and its dual reach the same number. This one asks what the dual's variables are, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

8 figures the row chooser mixes00.20.40.60.81-4-20246weight on row Apayoff to the row choosercol Xcol Ycol Z8/15 → 19/15the most the row chooser can guarantee: 19/15the column chooser mixes00.20.40.60.81-4-20246weight on col Xpayoff to the row chooserrow Arow B7/15 → 19/15the least the column chooser can concede: 19/15both sides name 19/15 = 1.267the value is 19/15 = 1.267, reached by the row chooser mixing 8/15 on A and by the column chooser mixing 7/15 on Xthe lower envelope of 3 lines peaks where two cross; the upper envelope of 2 bottoms out at that heightchecked against every pure reply on both sides, and over 61 mixtures on one side and 91 on the other

The value from both sides

Two choosers move at the same instant, and each asks the cautious question — how much can be guaranteed, whatever the other does. With pure choices the two answers are usually different numbers; allow a probability and they are forced to be the same one.

8 figures before the link A→B existsSABTcost 3flow 3cost 7flow 3cost 7flow 3cost 3flow 33 units each way, every traveller takes 10after the link A→B is addedSABTcost 6flow 6cost 7flow 0cost 7flow 0cost 6flow 6cost 0flow 6all 6 units one way, every traveller takes 12S→A and B→T cost 1 for each unit on them; A→T and S→B cost 7 whatever the trafficaverage travel time per traveller02468101214before the link10after the link12least possible119/12every traveller takes 10 before the zero-cost link exists and 12 after it doesthe least total travel time on the larger network is 119/2, an average of 119/12 = 9.917, so theequilibrium costs 144/119 = 1.210 times the least possiblechecked over every route at both flows, and against all 703 splits of the traffic on a lattice of sixths

The road that makes everyone later

An equilibrium is a state nobody can improve alone, which is a much weaker thing than a state anybody would choose. Adding a link that costs nothing to use makes every traveller in this network strictly slower, and the arithmetic says by exactly how much.

8 figures