Saddle Point
Back to the cover

Part I · Foundations

  1. 0 Mathematical Foundations
  2. 1 Observation, Beliefs, and Decision

Part II · Engines

  1. 2 Competing for Allocation: The Blotto Game
  2. 3 Bargaining, Commitment, and Repeated Cooperation
  3. 4 Signals, Disclosure, and Persuasion
  4. 5 Different Models of One Game
  5. 6 Leadership and Rules: Inspection
  6. 7 Decisions in Time
  7. 8 Many Agents
  8. 9 Networks, Dependence, and Resilience
  9. 10 Aggregating Information

Part III · Systems

  1. 11 Architecture of Decision Support
  2. 12 Simulation and Wargaming with AI Agents

Part IV · Limits

  1. 13 Where the Mathematics Stops

Engine · Chapter 9, Networks, Dependence, and Resilience

Flow and cut

How much can pass through a network, and what limits it?

Maximum flow from source to demand

15of 15 intact

The minimum cut has capacity 15: the arcs P1-T1, T2-M1, T2-M2, T3-M2 separate {s, P1, P2, T2, T3} from the rest, and no flow can exceed what crosses them. Equality of flow and cut is the certificate.

D The book certifies flow 15, cut {P1-T1, T2-M1, T2-M2, T3-M2}, and interdiction values 10, 6, 3 for budgets 1, 2, 3. Agreement, exactly.

Interdiction with a budget

Best (exhaustive)flow falls to 6; 4 optimal sets: {P1-T1, P2-T3}; {P1-T1, T3-M2}; {P2-T3, T1-M1}; {T1-M1, T3-M2}
Greedy by flow carriedP1-T1 → 10; P1-T2 → 8
Greedy by capacityP1-T1 → 10; P2-T3 → 6

A simple ranking can miss the best set: what matters is which arcs are removed together.

9/106/100/35/54/42/44/50/25/53/33/34/48/107/10ssourceP1plant 1P2plant 2T1route AT2route BT3route CM1market 1M2market 2tdemand
Arc width is the flow it carries; the label is flow / capacity. Red arcs form the minimum cut; dark nodes are on its source side. Click a transit arc to remove it (and again to restore).

The model it runs

Model K1 · p. 372

How much can pass, and what limits it?

1Decision-makers
one planner (no opponent yet)
2Time
one period, steady state
3Information
complete: the graph and the capacities are known
4Commitment
none
5Payoffs
the value of the flow
6Strategies
feasible flows

Analysis contract

(i) concept
maximum of a linear program
(ii) deviations
all feasible flows
(iii) beliefs
none
(iv) selection
the value is unique; a maximum flow and a minimum cut need not be, and one of each is reported
(v) attainment
attained; exact certificate: a flow and a cut of equal value