Saddle Point

Chapter 9 · begins on page 343

Networks, Dependence, and Resilience

Port, crane and containers back to it on the cover
Try it yourself Flow and cut How much can pass through a network, and what limits it? Open the engine →

The models

Each model in the book is stated on one card: who decides, when, with what information and commitment, what they get, what they may do, and the question it answers.

Model K1 · p. 372

How much can pass, and what limits it?

Model K1 · Chapter 9 · page 372

How much can pass, and what limits it?

A stylised supply network; Model K1


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

The 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
In the book: Chapter 9, Networks, Dependence, and Resilience, page 372Run this model →

Model K2 · p. 374

Which arcs matter most, and do simple rankings find them?

Model K2 · Chapter 9 · page 374

Which arcs matter most, and do simple rankings find them?

Interdiction with a budget; Model K2


1Decision-makers
interdictor (leader) and planner (follower); in K2 the planner protects first
2Time
sequential: removal, then routing (K2: protection, removal, routing)
3Information
complete; each mover sees the earlier moves
4Commitment
the removal is observed before routing: a -type order in pure strategies
5Payoffs
zero-sum: the residual maximum flow
6Strategies
sets of at most transit arcs; flows on the residual network

The analysis contract

(i) concept
min–max (bilevel) value of a perfect-information game
(ii) deviations
every set of transit arcs (exhaustive enumeration); every flow (by Theorem 9.2 (p. 373))
(iii) beliefs
none
(iv) selection
all optimal removal sets listed
(v) attainment
attained; every residual maximum flow certified by a cut
In the book: Chapter 9, Networks, Dependence, and Resilience, page 374

Model K3 · p. 376

What detection probability can the inspector guarantee, and where should it look?

Model K3 · Chapter 9 · page 376

What detection probability can the inspector guarantee, and where should it look?

Path inspection; Model K3


1Decision-makers
inspector and evader
2Time
one simultaneous move
3Information
the network and the detection probabilities are known; neither sees the other's choice
4Commitment
(zero-sum: announcing the optimal mixture is free, Theorem 0.6 (p. 7))
5Payoffs
zero-sum: probability of detection
6Strategies
mixtures over transit arcs; mixtures over – paths ( paths)

The analysis contract

(i) concept
value of a finite zero-sum game
(ii) deviations
every arc and every path
(iii) beliefs
none
(iv) selection
the value is unique; one optimal pair is reported
(v) attainment
attained; exact certificate checked against every path and every arc
In the book: Chapter 9, Networks, Dependence, and Resilience, page 376

Model K4 · p. 378

Which chokepoints decide connectivity, and where does added capacity buy resilience?

Model K4 · Chapter 9 · page 378

Which chokepoints decide connectivity, and where does added capacity buy resilience?

Routes through chokepoints; Model K4


1Decision-makers
an adversary choosing chokepoints to deny; a planner choosing where to add capacity; nature, failing nodes
2Time
one period
3Information
the routes and their nodes are known to all
4Commitment
the planner's investment is made before failures
5Payoffs
surviving capacity; the probability of staying connected
6Strategies
sets of nodes; one route to receive units

The analysis contract

(i) concept
exact worst case over node sets; exact probabilities over all node states
(ii) deviations
every node set of size ; every route for the investment
(iii) beliefs
the stated failure law
(iv) selection
all optimal sets reported
(v) attainment
exact
In the book: Chapter 9, Networks, Dependence, and Resilience, page 378

Model K5 · p. 379

What loss can protection guarantee to hold, and how does the guarantee move with predictability, the number of windows and the threat's strength?

Model K5 · Chapter 9 · page 379

What loss can protection guarantee to hold, and how does the guarantee move with predictability, the number of windows and the threat's strength?

Escorts over transit windows; Model K5


1Decision-makers
two: a protector assigning escort units (rows, maximises ships that pass) and a threat assigning strike units (columns), a worst case rather than a description of any party
2Time
one period, one shot
3Information
traffic plan and both budgets known to both; neither sees the other's allocation before choosing (variant: the threat sees the realised escort allocation)
4Commitment
; announcing the mixture is free (zero-sum); a fixed schedule is a pure strategy
5Payoffs
zero-sum: ships that pass, ; ties to the protector
6Strategies
mixtures over integer allocations of and of units to the windows, drawn independently

The analysis contract

(i) concept
value and optimal strategies of a finite zero-sum game (thm:ch00-minimax,thm:ch00-bridge)
(ii) deviations
every unilateral deviation to a pure allocation
(iii) beliefs
none needed
(iv) selection
none for the value; strategies are reported as one certified optimal pair (existence), not as the optimal set
(v) attainment
attained; exact certificate
In the book: Chapter 9, Networks, Dependence, and Resilience, page 379

What is proved, in words

The book follows each result with one sentence that says what it means without symbols. The formal statement is a click away; the proofs are in the book.

Proposition 9.3 · Model K1 · p. 373

The stylised supply network carries , and four arcs whose capacities sum to prove that nothing more can pass.

Proposition 9.3 · Chapter 9 · page 373

Model K1

In words The stylised supply network carries , and four arcs whose capacities sum to prove that nothing more can pass.


At the capacities of Figure 9.1 (p. 345) the maximum flow is . A minimum cut separates from the rest; its arcs are P1–A, B–M1, B–M2 and C–M2, with total capacity . It is one of exactly two minimum cuts: the other has source side and arcs A–M1, B–M1, B–M2, C–M2.

The proof is in the book: Chapter 9, Networks, Dependence, and Resilience, page 373

Proposition 9.5 · Exact interdiction values · p. 374

An adversary removing one, two or three links cuts the flow to , and at best, by striking the routes that bypass the central node; protecting any single link does not change these losses (for three links, because no link lies in all eight optimal attacks).

Proposition 9.5 · Chapter 9 · page 374

Exact interdiction values

In words An adversary removing one, two or three links cuts the flow to , and at best, by striking the routes that bypass the central node; protecting any single link does not change these losses (for three links, because no link lies in all eight optimal attacks).


With budgets the interdictor can reduce the maximum flow from to , and . For the optimal targets are P1–A and A–M1, the two arcs of route A. For the optimal sets combine one arc of route A with one arc of route C, the two routes that do not pass through B. In K2, protecting any single transit arc leaves these values unchanged for and , and for as well: no transit arc lies in all eight optimal triples.

The proof is in the book: Chapter 9, Networks, Dependence, and Resilience, page 374

Proposition 9.6 · Rankings are not strategies · p. 375

On this network, removing links in the order of three natural scores — flow, capacity or centrality — ranked once or re-ranked after each removal, does worse than the optimal attack at some budget, and the most central link is not the best single target. Orders that are optimal at every budget exist; the scores do not find them.

Proposition 9.6 · Chapter 9 · page 375

Rankings are not strategies

In words On this network, removing links in the order of three natural scores — flow, capacity or centrality — ranked once or re-ranked after each removal, does worse than the optimal attack at some budget, and the most central link is not the best single target. Orders that are optimal at every budget exist; the scores do not find them.


Removing transit arcs one at a time in the order of a score falls short of the optimum at some budget, whether the score is ranked once on the intact network or recomputed after each removal. Ranked once: by flow carried, the residual flows are , , for ; by capacity, , , ; by betweenness — the sum, over all ordered pairs of nodes, of the share of the pair's shortest paths that use the arc — , , . Recomputed after each removal: , , ; , , ; , , . The arc of largest betweenness, B–M2, is not an optimal single target. Fixed orders that are optimal at every budget do exist (P1–A, then P2–C, then B–M1 is one of eight), so the failure is of these three scores, not of fixed orders as such.

The proof is in the book: Chapter 9, Networks, Dependence, and Resilience, page 375

Proposition 9.9 · The value is a reciprocal maximum flow · p. 376

In the game of watching links against an evader, the value is the reciprocal of a maximum flow: the inspector watches a minimum cut, and the evader spreads over the routes of a maximum flow.

Proposition 9.9 · Chapter 9 · page 376

The value is a reciprocal maximum flow

In words In the game of watching links against an evader, the value is the reciprocal of a maximum flow: the inspector watches a minimum cut, and the evader spreads over the routes of a maximum flow.


Give each watchable arc (a transit arc with ) the capacity and every other arc an unbounded capacity, and let be the maximum – flow; assume an – path exists and every one contains a watchable arc, so that . The value of the inspection game is . An optimal inspector watches the arcs of a minimum cut, arc with probability ; an optimal evader uses the paths of a decomposition of a maximum flow, each with probability equal to its flow divided by . In particular, if every transit arc detects with certainty, the value is divided by the smallest number of transit arcs whose removal disconnects from .

The proof is in the book: Chapter 9, Networks, Dependence, and Resilience, page 376

Proposition 9.10 · Model K3 · p. 377

With certain detection on the transit links the inspector watches the four links of the smallest transit cut a quarter of the time each; with the route-specific detection of the second instance the optimal watch moves to the route-to-market links, where detection is best; in general it sits on a minimum cut of the capacities , not on the single best link. The value is for the maximum flow of the capacities over the watchable arcs; which arcs are watchable is part of the model.

Proposition 9.10 · Chapter 9 · page 377

Model K3

In words With certain detection on the transit links the inspector watches the four links of the smallest transit cut a quarter of the time each; with the route-specific detection of the second instance the optimal watch moves to the route-to-market links, where detection is best; in general it sits on a minimum cut of the capacities , not on the single best link. The value is for the maximum flow of the capacities over the watchable arcs; which arcs are watchable is part of the model.


With certain detection on every transit arc the value is : the smallest transit cut has four arcs, and the inspector watches each of P1–A, P1–B, P2–B and P2–C with probability . With detection on the plant-to-route arcs and the link A–B and on the route-to-market arcs, the value is , and the inspector watches the four route-to-market arcs, each with probability (Figure 9.4 (p. 348)).

The proof is in the book: Chapter 9, Networks, Dependence, and Resilience, page 377

Proposition 9.13 · Ten cables are one corridor · p. 378

In this table, service at the threshold needs the classic corridor, so ten cables through it fail as one; the same four units of capacity buy nothing on the corridor, most on a route sharing none of its chokepoints, and a little less on a bypass that shares one; four routes share no chokepoint and four losses are needed to stop everything, while a single loss already breaks the service threshold.

Proposition 9.13 · Chapter 9 · page 378

Ten cables are one corridor

In words In this table, service at the threshold needs the classic corridor, so ten cables through it fail as one; the same four units of capacity buy nothing on the corridor, most on a route sharing none of its chokepoints, and a little less on a bypass that shares one; four routes share no chokepoint and four losses are needed to stop everything, while a single loss already breaks the service threshold.


(a) Losing one chokepoint can cut capacity from to ( or ); two, to ( or ); three, to . At most four routes are pairwise node-disjoint, and four nodes are needed to disconnect the regions completely; a single node ( or ) already breaks the service threshold. (b) The probability of staying connected is exactly : the regions are connected precisely when R1 survives, so the system behaves as two chokepoints in series. With the common shock it is . The cable view puts it at , and at if stays shared and only 's risk is split across the ten links. (c) Adding units to one route gives, with independent failures (and with the shock): R1 () — unchanged; R2 (); R3 (); R4, R5 or R6 ().

The proof is in the book: Chapter 9, Networks, Dependence, and Resilience, page 378

Proposition 9.15 · Escorts, the threshold and a visible draw · p. 380

Escorts lose nothing only when every window can be held against the threat's whole strength; below that threshold every plan loses something, and what a rotating schedule can guarantee survives its announcement but not the sight of its draw.

Proposition 9.15 · Chapter 9 · page 380

Escorts, the threshold and a visible draw

In words Escorts lose nothing only when every window can be held against the threat's whole strength; below that threshold every plan loses something, and what a rotating schedule can guarantee survives its announcement but not the sight of its draw.


In Model K5, for any traffic and budgets:

  • Threshold. The value of the loss is if and only if . If , it is at least .
  • Announcement and observation. An optimal mixture of the protector guarantees the value whether or not it is announced. If the threat sees the realised allocation before striking, the value of the loss rises to , the guarantee of the best fixed allocation.
The proof is in the book: Chapter 9, Networks, Dependence, and Resilience, page 380

Proposition 9.16 · Model K5 at the stylised values · p. 381

In the base case a rotating schedule holds the loss to four thirds of a ship where any fixed or visible schedule loses two, randomising is worth something only at the middle of the three threat strengths compared here, and whether gathering ships into fewer windows or spreading them over more is better depends on the number of escorts.

Proposition 9.16 · Chapter 9 · page 381

Model K5 at the stylised values

In words In the base case a rotating schedule holds the loss to four thirds of a ship where any fixed or visible schedule loses two, randomising is worth something only at the middle of the three threat strengths compared here, and whether gathering ships into fewer windows or spreading them over more is better depends on the number of escorts.


In Model K5:

  • Base case. The value is ships through, a loss of . It is certified by the protector's uniform mixture over , , and the threat's uniform mixture over , , : . Every fixed allocation loses at least ships against its best reply; the seven allocations with no window above lose exactly , the three that put every escort on one window lose ; if the threat sees the realised allocation the loss is . With the loss is , with a fixed allocation or without; with it is , with or without.
  • Traffic plans. With , and , the loss is in two windows; in three; and in six (Table 9.2 (p. 365)). For more windows give a lower loss; at fewer windows do.
The proof is in the book: Chapter 9, Networks, Dependence, and Resilience, page 381

Theorem 9.2 · Maximum flow equals minimum cut · p. 373

How much a network can carry is set by its narrowest cut, and with whole-number capacities the best flow can be chosen in whole numbers.

Theorem 9.2 · Chapter 9 · page 373

Maximum flow equals minimum cut

In words How much a network can carry is set by its narrowest cut, and with whole-number capacities the best flow can be chosen in whole numbers.


In a finite network with nonnegative capacities, the maximum value of an – flow equals the minimum capacity of an – cut. With integer capacities there is an integer maximum flow.

The proof is in the book: Chapter 9, Networks, Dependence, and Resilience, page 373

Worked cases

Parallaxes in history

1888 · Chapter 9 · p. 359

A passage and a promise of passage

Then

Constantinople, 1888: nine powers declare Suez open to every flag, its fresh-water canal secure.

Now

Europe–Asia cables: a bypass of one chokepoint still crosses another (Section 9.7 (p. 353)).

1888 · Chapter 9 · page 359

A passage and a promise of passage

Then

Constantinople, 1888: nine powers declare Suez open to every flag, its fresh-water canal secure.

Now

Europe–Asia cables: a bypass of one chokepoint still crosses another (Section 9.7 (p. 353)).


What happened

On 29 October 1888 nine powers — Great Britain, Germany, Austria-Hungary, Spain, France, Italy, the Netherlands, Russia and Turkey — signed at Constantinople a convention on the Suez Canal D [Suez Canal Authority 1888; “The World and Japan” Database 1888, the treaty text]. Article I declares the Maritime Canal free and open, in time of war as in time of peace, to every vessel of commerce or of war without distinction of flag, and never subject to blockade. Article II records that the Fresh-Water Canal is indispensable to the Maritime Canal, takes note of the Khedive's engagements to the canal company concerning it in a convention of 18 March 1863, and binds the parties not to interfere with its security; Article III extends the undertaking to the plant, establishments, buildings and works of both canals. Article VIII charges the signatories' agents in Egypt with watching over the treaty's execution, and Article XIV provides that the engagements are not limited by the duration of the company's concession D [the treaty text, Articles I–III, VIII and XIV].

The model

The treaty draws the two graphs the worked case needs (Section 9.7 (p. 353), field 3 of the card): the passage itself, and the dependencies that keep it usable — the water supply, the works, and the right to pass. In Model K4 capacity belongs to routes, and a route is available only while every chokepoint it crosses is open: a chokepoint is a failure condition shared by the routes through it, not a capacity of its own. The convention's drafters, nearly seventy years before the max-flow min-cut theorem (Theorem 9.2 (p. 373)), listed the chokepoints that were not on the chart R.

What could be known

Whether the canal was open was, by 1888, something a telegram or a company notice could say; whether the promise of passage would hold was a matter of nine governments' conduct, observable only after the fact. A modern operator sees manifests, vessel positions and queue lengths within minutes and estimates from them usable capacity, delay and arrival. That information improves the use of capacity. It cannot create a right of passage, and it cannot make two routes independent when they share a water supply, a port process or an authority. The second drawing, of the dependencies, is made from documents, not from tracking data, and it is the one that decides what the first is worth.

Where the parallel stops

The treaty's text is not evidence that passage was continuously respected afterwards, and the box makes no claim about any later closure of the canal.

In the book: Chapter 9, page 359All sixteen parallaxes on the timeline →

1984–1988 · Chapter 9 · p. 367

The tanker war and convoy escort

Then

Gulf, 1984–88: attacks on merchant ships counted after the fact; from July 1987 escort for eleven reflagged tankers.

Now

Escorts over transit windows: an allocation seen before a strike is held to the guarantee of a fixed one (Section 9.8 (p. 360)).

1984–1988 · Chapter 9 · page 367

The tanker war and convoy escort

Then

Gulf, 1984–88: attacks on merchant ships counted after the fact; from July 1987 escort for eleven reflagged tankers.

Now

Escorts over transit windows: an allocation seen before a strike is held to the guarantee of a fixed one (Section 9.8 (p. 360)).


What happened

On 1 June 1984 the Security Council condemned recent attacks on commercial ships en route to and from the ports of Kuwait and Saudi Arabia and asked the Secretary-General to report; his report of 31 December summarised replies from governments and communications from the International Maritime Organization about incidents D [United Nations Security Council 1984, paras. 4, 7; United Nations Secretary-General 1984]. Counts depended on the counter: for 1984–87 a tabulation from Lloyd's Shipping Intelligence Unit and the Center for Defense Information gives , , and ships attacked, in all; one compiled from the Secretary-General's reports gives , , and , in all D [O'Rourke 1988, Tables 1–2]. On 7 March 1987 the United States offered to reflag eleven Kuwaiti tankers and to provide US Navy protection; escort began in July, and on 24 July, on the first convoy, the reflagged tanker Bridgeton struck a mine. Three tankers struck mines that month D [Department of the Navy, Office of the Chief of Naval Operations 1991, p. 4; Mobley 2016, pp. 3–4]. The Bridgeton reached Kuwait with its escorts following in its wake, and further convoys were postponed while mine-warfare helicopters were deployed D [Cox 2018]. Resolution 598 of 20 July 1987 deplored attacks on neutral shipping and demanded a ceasefire between Iran and Iraq, which came into effect on 20 August 1988 D [United Nations Security Council 1987; United Nations Peacekeeping n.d.].

The model

Fields 3 and 4 of Model K5's card R. Escort was attached to a declared set of ships, recognisable by their flag: visibility of that kind bears on field 3. If the whole realised allocation were observed before an attack could be chosen, Proposition 9.15 (p. 380)(b) would hold it to the guarantee of the best fixed one, whatever plan lay behind it; the cited record establishes recognisable convoys, not the observation of a full draw. Gathering ships into convoys is a choice of fewer windows, worth more or less according to the escorts available against the threat (Proposition 9.16 (p. 381)(b)). A mine does not choose its ship: it is a hazard of the lane, outside the allocation game and closer to the shared interruption of Exercise 9.10 (p. 371); the order in which the first convoy finished its voyage, the tanker ahead of its escorts, fits that reading R.

What could be known

The record of attacks consisted of compilations made after the fact, whose totals for 1984 differed by nearly a factor of two. Since the end of 2004 ships of gross tonnage and upwards on international voyages have been required to carry an automatic identification system, which broadcasts the ship's identity, type, position, course and speed D [International Maritime Organization n.d.]; in 2026 transits through the strait are counted daily from these broadcasts, with a warning about jamming, spoofing and ships going dark (Section 9.8 (p. 360)). Tracking shortens the delay to the record. It does not settle what counts as an attack or who counts, the choices on which two counts of one war can differ, and it shows where ships are, not where mines are.

Where the parallel stops

The box takes no position on who attacked which ship, on who laid the mines, on any party's aims, or on whether escort changed the number of attacks; no count enters the model.

In the book: Chapter 9, page 367All sixteen parallaxes on the timeline →

The people

Chapter 9 · Networks, Dependence, and Resilience

Lester R. Ford Jr.

1927 – 2017

Mathematician who worked at the RAND Corporation in the 1950s. With D. R. Fulkerson he proved the max-flow min-cut theorem and gave the augmenting-path algorithm for maximum flows; his name is also attached to the Bellman–Ford shortest-path algorithm and, with S. M. Johnson, to the Ford–Johnson merge-insertion sorting method.

The life, in moments →

Main works

  • “Maximal flow through a network”, with D. R. Fulkerson (Canadian J. Math. 8, 1956)
  • Flows in Networks, with D. R. Fulkerson (1962)

Chapter 9 · Networks, Dependence, and Resilience

D. Ray Fulkerson

1924 – 1976

Mathematician at the RAND Corporation from 1951 and, from 1971, at Cornell University. He worked on network flows, combinatorial optimisation and the theory of blocking and anti-blocking polyhedra; with George Dantzig and Selmer Johnson he solved a 49-city travelling-salesman problem by the cutting-plane method. A prize in discrete mathematics bears his name.

The life, in moments →

Main works

  • “Solution of a large-scale traveling-salesman problem”, with G. B. Dantzig and S. M. Johnson (Operations Research 2, 1954)
  • Flows in Networks, with L. R. Ford Jr. (1962)
  • “Blocking and anti-blocking pairs of polyhedra” (Mathematical Programming 1, 1971)

Chapter 9 · Networks, Dependence, and Resilience

Theodore E. Harris

1919 – 2005

Mathematician at the RAND Corporation (1947–66) and then at the University of Southern California. He worked on branching processes and on interacting particle systems, and Harris recurrence of Markov chains is named after him. With F. S. Ross he wrote the RAND report on the capacity of a rail network, whose object of interest was a minimum cut.

The life, in moments →

Main works

  • “Fundamentals of a method for evaluating rail net capacities”, with F. S. Ross (RAND RM-1573, 1955)
  • The Theory of Branching Processes (1963)
  • “Contact interactions on a lattice” (Annals of Probability 2, 1974)