Title: InkMaths / Decision Mathematics 2: allocation, flow and games
On every note of this deck, unless a note says otherwise:
Footer: Continue on InkMaths · © 2026 InkMaths. All rights reserved.

Front: DEFINE
Define: capacity of a cut.
Back: The total capacity of the arcs directed from the source side to the sink side only. Arcs crossing back towards the source contribute nothing at all.

Front: RECALL
State the minimum lines test and what to do when it fails.
Back: If the fewest horizontal and vertical lines that cover every zero equals the size of the matrix, a complete allocation of zeros exists. If it is fewer, subtract the smallest uncovered entry from every uncovered entry and add it to every doubly covered one, then test again.

Front: DEFINE
Define: dominance.
Back: A row is dominated when another is at least as good in every column; a column is dominated when another is at least as small in every row. Dominated options are deleted outright, often reducing a game to a two by two.

Front: SPOT THE ERROR
Say what is wrong with this claim:
The entering cell is the unused cell with the lowest cost in the table.
Back: It is the cell with the most negative improvement index. The index accounts for what the rest of the plan must change, which the raw cost ignores, so a cell can be cheapest in the table and still have a positive index.

Front: DEFINE
Define: north-west corner method.
Back: Fill the top-left cell as far as supply and demand allow, cross off whichever runs out, repeat. It never looks at a cost, so the plan it produces is usually poor. Its job is to be feasible, not to be good.

Front: STANDARD RESULT — LEARN IT
Improvement index:
index of an unused cell = ?\(\text{index of an unused cell} = ?\)index of an unused cell = ?
Back: cost - R - K, where R + K = cost at every cell in use\(\text{cost} - R - K, \text{ where } R + K = \text{cost at every cell in use}\)cost - R - K, where R + K = cost at every cell in use

Front: RECALL
Explain how to maximise an allocation.
Back: Subtract every entry from the largest entry in the matrix, then minimise as usual. The biggest profit becomes the smallest cost, so the allocation found is the one of greatest total.

Front: STANDARD RESULT — LEARN IT
Max-flow min-cut theorem:
maximum flow = ?\(\text{maximum flow} = ?\)maximum flow = ?
Back: capacity of the minimum cut\(\text{capacity of the minimum cut}\)capacity of the minimum cut

Front: SPOT THE ERROR
Say what is wrong with this claim:
Once every route from source to sink contains a full arc, the flow is maximal.
Back: An augmenting path may run backwards along an arc that already carries flow, freeing capacity elsewhere. Only the absence of any augmenting path settles it, proved by a cut of the same capacity as the flow.

Front: DEFINE
Define: expected monetary value.
Back: The probability-weighted average of the outcomes reachable from a chance node, so the long-run average pay-off of taking that branch.

Front: DEFINE
Define: Hungarian reduction.
Back: Subtract each row's minimum from that row, then each column's from that column. Every complete allocation loses the same total, so the cheapest one is unchanged and the zeros mark the bargains.

Front: RECALL
Explain play safe and stable solutions.
Back: The row player takes the row whose worst entry is best, the maximin; the column player takes the column whose largest is smallest, the minimax. The game is stable exactly when the two agree, and that number is its value.

Front: RECALL
State the m + n − 1 rule for a transportation problem.
Back: The number of cells a non-degenerate solution to an m by n transportation problem uses, which is exactly enough to fix the shadow costs. Fewer means degeneracy, fixed by recording a zero allocation.

Front: RECALL
Explain the stepping-stone loop.
Back: From the entering cell, trace a closed route through cells in use, alternating plus and minus. The value moved is the smallest minus-cell allocation, that cell exits, and the cost falls by that value times the index.

Front: CHECK YOURSELF
Why might a firm reject the option with the highest expected monetary value?
Back: Expected monetary value is an average over many repetitions, and a one-off decision is not many repetitions. If the bad outcome would ruin the firm, a smaller certain gain is the better choice, which is what utility measures.

Front: DEFINE
Define: flow-augmenting path.
Back: A route from source to sink using spare capacity forwards or existing flow backwards. It carries the smallest of those numbers along it, and at least one arc becomes saturated.

Front: DEFINE
Define: Bellman's principle of optimality.
Back: Any part of an optimal path is itself optimal between its own two ends. That is what licenses working backwards from the final stage, quoting values already found.

Front: RECALL
Explain how to solve a mixed game.
Back: Play the first row with probability p, write the expected pay-off against each column as a line in p, and take the highest point of the lower boundary. That point is a crossing or an end, so equate the pair meeting there and test p = 0 and p = 1 as well. A peak at an end is a pure strategy, and a dominated row you should have deleted first.

Front: RECALL
State how to work back through a decision tree.
Back: Start at the far right. A chance node takes the expected monetary value of its branches, a decision node takes the best figure available and you cross out the branches you rejected. Costs come off along the branch where they are actually met, not at the end.