Saddle Point

Chapter 11 · begins on page 431

Architecture of Decision Support

Lighthouse back to it on the cover

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 C1 · p. 453

What is a scorecard worth for the inspection decision, and when is one scorecard better than another for every decision?

Model C1 · Chapter 11 · page 453

What is a scorecard worth for the inspection decision, and when is one scorecard better than another for every decision?

A synthetic population and two scorecards; Model C1


1Decision-makers
one: the authority deciding which consignments to inspect
2Time
one period; one decision per consignment
3Information
the scorecard's signal (a class, or a cell); the population is fixed and non-strategic
4Commitment
none
5Payoffs
as in Model O1: inspection costs , a released violation ; or detections under a budget
6Strategies
maps from signals to inspection rates

The analysis contract

(i) concept
value of information (Proposition 1.2 (p. 55)); Blackwell's order (Theorem 0.14 (p. 15)), for two states the inclusion of optimal operating characteristics (Remark 1.4 (p. 56))
(ii) deviations
all signal-wise rules
(iii) beliefs
Bayes' rule from the counts; prior
(iv) selection
none needed: no ties in either cell order
(v) attainment
attained; exact rational arithmetic over the enumerated population
In the book: Chapter 11, Architecture of Decision Support, page 453

Model C2 · p. 455

What allocation should be announced, and what does the static rule lose once violators adapt?

Model C2 · Chapter 11 · page 455

What allocation should be announced, and what does the static rule lose once violators adapt?

Inspection allocation against adaptive violators; Model C2


1Decision-makers
the authority (leader); a mass of identical adaptive violators (follower); non-adaptive violators as a fixed population
2Time
one period: rates announced, then classes chosen
3Information
violators know the rates (learned or published), not the draw for their consignment
4Commitment
: announced rates, a mixed strategy over which consignments to open
5Payoffs
non-zero-sum: authority as in Model N, violator gain, penalty and disguise cost; abstaining
6Strategies
rates within the budget; follower options H, M, L, abstain

The analysis contract

(i) concept
leader-optimal commitment (strong Stackelberg); one linear program per follower option
(ii) deviations
all four follower options; all feasible rates
(iii) beliefs
none beyond the announced rates
(iv) selection
for the certified value; the worst tie reported at the same rates
(v) attainment
attained under ; under a supremum approached by margins; exact vertex enumeration
In the book: Chapter 11, Architecture of Decision Support, page 455

Model C3 · p. 461

Which scores of an automated component measure anything, and what can a finite audit certify about it?

Model C3 · Chapter 11 · page 461

Which scores of an automated component measure anything, and what can a finite audit certify about it?

Policies under test and audits; Model C3


1Decision-makers
the policy under test; the auditor (an evaluation procedure); the adaptive violators of Model C2
2Time
one period of decisions; one audit sample
3Information
the auditor sees sampled decisions, not the policy; violators see the implemented rates
4Commitment
the policy's rates are fixed during the period
5Payoffs
Model C2's loss
6Strategies
policies as rate vectors; audits as threshold tests

The analysis contract

(i) concept
backtest, loss against best-responding violators, exploitability gap (Remark 11.7 (p. 458)); exact binomial error probabilities
(ii) deviations
all four follower options
(iii) beliefs
none
(iv) selection
both tie conventions reported
(v) attainment
exact; binomial probabilities as exact rationals, printed truncated
In the book: Chapter 11, Architecture of Decision Support, page 461

Model C4 · p. 465

What does an override practice cost, and when does officer discretion add value rather than leak it?

Model C4 · Chapter 11 · page 465

What does an override practice cost, and when does officer discretion add value rather than leak it?

Override policies; Model C4


1Decision-makers
authority, officers (executing with discretion), violators
2Time
one period
3Information
the officer's alarm on selected consignments; violators observe implemented rates
4Commitment
announced selection rates; override practice as a fixed policy
5Payoffs
Model C2's
6Strategies
override policies (release share, hunches, filter); follower options as in Model C2

The analysis contract

(i) concept
Model C2's loss at implemented rates; leader-optimal recomputation for the designed filter
(ii) deviations
all follower options
(iii) beliefs
signal law of Chapter 6; no updating by officers
(iv) selection
; the designed filter deters strictly
(v) attainment
exact
In the book: Chapter 11, Architecture of Decision Support, page 465

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 11.2 · What the scorecards are worth · p. 454

A risk score is an experiment: two reasonable scorecards can each be the better one, depending on the decision they inform, and a misspecified score can still produce the right classes.

Proposition 11.2 · Chapter 11 · page 454

What the scorecards are worth

In words A risk score is an experiment: two reasonable scorecards can each be the better one, depending on the decision they inform, and a misspecified score can still produce the right classes.


In Model C1:

  • The per-feature likelihood ratios are for present or absent, for and for . The naive-Bayes score is not the true ratio — for the cell with all three features it is against — and it orders two pairs of cells differently from the true ratios (Table 11.1 (p. 454)).
  • Scorecard A's three classes hold , and consignments and , and violators, with violation densities , and ; they are H , M and L . Cutting the true ratio order at the same class sizes gives the same three classes: at this resolution the misspecification of the score is invisible.
  • Scorecards A and B are not comparable in Blackwell's order: their optimal operating characteristics cross (B is above at false-alarm rate , against ; A is above at , against ). Accordingly, in Model O1's decision with , the value of information per consignment is for A and for B when , and for A and for B when . Both are garblings of the full eight-cell table, which is worth at .
  • With a budget of inspections spent cell by cell in score order (the last cell partly, at random), the naive-Bayes order detects violators and the true order : the misordering costs detections once a budget splits a class.
The proof is in the book: Chapter 11, Architecture of Decision Support, page 454

Proposition 11.4 · The static rule is the best answer to history · p. 456

Inspecting the riskiest class first is exactly right if nobody reacts — it is the optimum of the backtest.

Proposition 11.4 · Chapter 11 · page 456

The static rule is the best answer to history

In words Inspecting the riskiest class first is exactly right if nobody reacts — it is the optimum of the backtest.


If no violator adapts (), the static rule is optimal: it minimises the loss, which is then the backtest, over all feasible rates. In Model C2 it inspects H at rate , M at and L not at all, with backtest loss .

The proof is in the book: Chapter 11, Architecture of Decision Support, page 456

Proposition 11.5 · The certified allocation · p. 457

The certified allocation inspects the riskiest class less than the static rule does and puts a tenth of the low-risk class under inspection — just enough that no adaptive violator gains from moving there.

Proposition 11.5 · Chapter 11 · page 457

The certified allocation

In words The certified allocation inspects the riskiest class less than the static rule does and puts a tenth of the low-risk class under inspection — just enough that no adaptive violator gains from moving there.


At base values, the leader-optimal announcement under leader-favourable ties is

which deters every adaptive violator, at expected loss . Class is deterred iff , that is iff for H, M, L; holds M and L exactly at their thresholds and spends the rest of the budget on H. The best announcements that instead accept the adaptive violators into H, M or L lose , and ; the last is the static rule. At the adaptive violators are indifferent between abstaining and presenting in M or L; if they resolve the tie against the authority (presenting in L), the loss is , exactly more.

The proof is in the book: Chapter 11, Architecture of Decision Support, page 457

Proposition 11.6 · Deter, then fill · p. 458

The certified allocation is built in two layers: a floor in every class that makes adaptation unprofitable, then the static rule applied to whatever budget is left.

Proposition 11.6 · Chapter 11 · page 458

Deter, then fill

In words The certified allocation is built in two layers: a floor in every class that makes adaptation unprofitable, then the static rule applied to whatever budget is left.


Write for the deterrence threshold of class and for the inspections needed to hold every class at its threshold. If and deterring all adaptive violators is optimal, the certified rates are , where fills the residual budget by the static rule: densest class first, each up to rate . At base values , , and the residual inspections all go to H.

The proof is in the book: Chapter 11, Architecture of Decision Support, page 458

Proposition 11.8 · When adaptation changes the answer · p. 459

Once a little under six per cent of the violators adapt (), it pays to deter them all, and from then on the gap between the static rule and the certified allocation only widens.

Proposition 11.8 · Chapter 11 · page 459

When adaptation changes the answer

In words Once a little under six per cent of the violators adapt (), it pays to deter them all, and from then on the gap between the static rule and the certified allocation only widens.


For every follower option the polytope does not depend on , and the loss is affine in at each vertex. Hence the certified loss is a piecewise-linear function of with finitely many exactly computable breakpoints. Deterring all adaptive violators is optimal iff , where

where measures, in loss units, the detections that the deterrent allocation gives up on history. Below the certified allocation is the static rule and the adaptive violators present in L. The static rule's loss grows linearly with , while its backtest does not move (Figure 11.3 (p. 436)).

The proof is in the book: Chapter 11, Architecture of Decision Support, page 459

Proposition 11.9 · Deterrence is invisible in the data it produces · p. 459

A deterrent that works removes its own evidence: the data it leaves behind say the low-risk class is safe, and a model retrained on them undoes the deterrent, while the allocation built from incentives does not move.

Proposition 11.9 · Chapter 11 · page 459

Deterrence is invisible in the data it produces

In words A deterrent that works removes its own evidence: the data it leaves behind say the low-risk class is safe, and a model retrained on them undoes the deterrent, while the allocation built from incentives does not move.


Suppose the authority measures each class's violation density from one period's inspections, which are drawn at random within each class and so estimate without bias the density of the violators actually present. Under the certified allocation the measured densities are , and (, , ), against historical densities , and : the deterred violators appear in no class, and L looks safer than history said. Under the static rule L is never inspected, and its density is not measured at all. A static rule retrained on the certified period's measurements orders the classes as before, reproduces the static allocation exactly, and readmits the adaptive violators into L (loss ). The certified allocation recomputed with the measured counts in place of the historical ones is unchanged.

The proof is in the book: Chapter 11, Architecture of Decision Support, page 459

Proposition 11.11 · Two kinds of adaptive violator · p. 460

When violators differ, the cheapest disguise sets the floor once enough violators have it; below that, conceding the low-risk class to a few is cheaper than raising every floor for them.

Proposition 11.11 · Chapter 11 · page 460

Two kinds of adaptive violator

In words When violators differ, the cheapest disguise sets the floor once enough violators have it; below that, conceding the low-risk class to a few is cheaper than raising every floor for them.


Split the adaptive violators into with Model C2's disguise costs and with cheaper ones, , each type choosing its class separately; the authority knows the masses and commits to rates, as in a Bayesian Stackelberg game. For the certified allocation is : it deters the ordinary type and concedes L to the cheap type, at loss plus per cheap violator ( at , at ). For it deters both, with rates and loss , whatever the split. The switch is at .

The proof is in the book: Chapter 11, Architecture of Decision Support, page 460

Proposition 11.14 · Scores of black-box policies · p. 462

A replay of history rewards exactly the policies that adaptive violators exploit, and a policy that falls half a percentage point short of the certified rate in one class can still give away almost a hundred units of loss.

Proposition 11.14 · Chapter 11 · page 462

Scores of black-box policies

In words A replay of history rewards exactly the policies that adaptive violators exploit, and a policy that falls half a percentage point short of the certified rate in one class can still give away almost a hundred units of loss.


In Model C3 at base values (Table 11.2 (p. 463)):

  • The backtest ranks the static rule first () and the certified allocation third (), behind the imitation policy; against best-responding violators with leader-favourable ties the certified allocation loses least () and the static rule falls to third (), with gaps for the static rule and for the uniform rate.
  • The imitation policy keeps the M rate of , falls short of it in L and spends the released inspections in H, whose rate rises by (about points); it has a better backtest ( against ); against best-responding violators its loss is and its gap , because the shortfall in L moves the adaptive violators there.
  • The gap is not continuous in the implemented rates: as with the rest of fixed, the loss tends to , while at it is ; the jump, , equals the cost of the worst tie in Proposition 11.5 (p. 457) (Figure 11.4 (p. 439)a).
The proof is in the book: Chapter 11, Architecture of Decision Support, page 462

Proposition 11.15 · What an audit sample certifies · p. 463

An audit of one class can tell a rate with a safety margin from an exploitable rate in that class, at a price in sample size; it can never tell the exact certified allocation from its exploitable neighbours, and it says nothing about the classes it did not sample.

Proposition 11.15 · Chapter 11 · page 463

What an audit sample certifies

In words An audit of one class can tell a rate with a safety margin from an exploitable rate in that class, at a price in sample size; it can never tell the exact certified allocation from its exploitable neighbours, and it says nothing about the classes it did not sample.


  • No margin, no certificate. For any audit that observes independent decisions on class L — any test, not only threshold tests — the pass probability of a policy with rate is a polynomial in . Hence for every there are policies with , each exploitable by Proposition 11.14 (p. 462)(c), that pass with probability within of the certified allocation's. At with the threshold test, rates , , pass with probability , , , approaching the knife edge's .
  • With a margin, a computable certificate. Against the margin allocation (), with fixed so that a policy at the knife edge passes with probability at most (and every policy with with less): at the threshold is and the margin policy passes with probability ; at , and ; at , and . Probabilities are exact rationals, truncated.
The proof is in the book: Chapter 11, Architecture of Decision Support, page 463

Proposition 11.18 · What overrides cost · p. 466

The same discretion that leaks deterrence when nobody accounts for it buys deterrence when the allocation is computed with it: an alarm that clears most clean consignments lets the budget cover far more of the flow.

Proposition 11.18 · Chapter 11 · page 466

What overrides cost

In words The same discretion that leaks deterrence when nobody accounts for it buys deterrence when the allocation is computed with it: an alarm that clears most clean consignments lets the budget cover far more of the flow.


  • Unlogged release. At the certified allocation every moves the adaptive violators into L and the loss jumps from towards . At the margin allocation deterrence survives for under leader-favourable ties, and for under pessimistic ones — is the share at which , L's threshold — while the loss rises linearly on the way, from to , through missed detections of the non-adaptive violators in L (Figure 11.5 (p. 441)a).
  • Hunches. Inspecting all of H takes inspections from L, whose rate falls to , below its threshold: the adaptive violators move into L and the loss rises from to .
  • Release on a clear check. Unanticipated, the filter lowers the effective rate for violators in M to , below M's threshold; they move into M and the loss rises to , with the saved inspections unspent. Designed in, the recomputed selection rates are and the loss falls to , with every adaptive violator strictly deterred.
The proof is in the book: Chapter 11, Architecture of Decision Support, page 466

A parallax in history

1755–1756 · Chapter 11 · p. 442

Give distant witnesses the same questions

Then

Pombal's inquiry of 1756: thirteen fixed questions sent through the bishops to every parish.

Now

AI-assisted screening and rapid mapping: faster chains that still cannot fill an unobserved place (Section 11.7 (p. 447)).

1755–1756 · Chapter 11 · page 442

Give distant witnesses the same questions

Then

Pombal's inquiry of 1756: thirteen fixed questions sent through the bishops to every parish.

Now

AI-assisted screening and rapid mapping: faster chains that still cannot fill an unobserved place (Section 11.7 (p. 447)).


What happened

After the earthquake of 1 November 1755, the Portuguese Secretary of State, Sebastião José de Carvalho e Melo, later Marquis of Pombal, sent the bishops a questionnaire to be copied to every parish priest; the letter to the Cardinal-Patriarch of Lisbon reproduced by the Lisbon Quake Museum is dated 20 January 1756 (the museum's running text gives 26 January), the priests were given a month to answer, and the Bishop of Coimbra had the questions printed D [Lisbon Quake Museum n.d., the museum's transcription]. There were thirteen questions: the hour and duration of the shock, its direction, the houses ruined and the people killed, changes in the sea, springs and rivers, the behaviour of the tide, fissures in the ground, the measures taken by clergy, soldiers and ministers, aftershocks, earlier earthquakes remembered, the parish's population, shortages, and fire D [Lisbon Quake Museum n.d., the questionnaire as transcribed there]. The returns went to the Secretariat of State and are kept at the Torre do Tombo; a study of the Aveiro lagoon that uses them records that, within its study area, some parishes of the diocese of Coimbra and all of those of the diocese of Porto are missing from the collection, and fills the gaps from the distinct general inquiry of 1758, whose question 20 asked whether the parish had suffered ruin in 1755 and whether it had been repaired D [Sarmento and Cardoso 2006, pp. 94–95].

The model

The inquiry is the data stage of Figure 11.1 (p. 434) in an early form: a fixed schema (the thirteen questions), a transmission chain (ministry, bishop, priest, parishioner), a provenance record (which parish answered and which did not), and a second instrument to repair coverage. Model C1 takes its feature space as given; the inquiry shows the feature space being chosen, and the missing cells travelling with the data R.

What could be known

What the ministry could know in 1756 was bounded by the chain: a question had to be copied, carried, answered by someone who had been there and returned, at the pace of the post and of the Church's administration, and a parish that did not answer was a blank that no analysis could fill. Satellite imagery, multilingual transcription and automated extraction have changed the scale and the latency of that chain beyond recognition (the two situations at the end of Section 11.7 (p. 447)); they have not changed the two things the inquiry got right — that testimony is comparable only when the witnesses were asked the same question, and that the omissions must be recorded next to the answers. A common questionnaire was an information technology; faster processing does not repair an unobserved location.

Where the parallel stops

The account rests on one published study and a museum's reproductions of the documents. The box claims nothing about what the inquiry achieved for the science of earthquakes.

In the book: Chapter 11, page 442All sixteen parallaxes on the timeline →

The people

Chapter 11 · Architecture of Decision Support

Herbert A. Simon

1916 – 2001

Trained in political science at the University of Chicago (doctorate, 1943), he began with studies of municipal administration that he later classed as operations research, taught at the Illinois Institute of Technology from 1942, and from 1949 helped to develop the Graduate School of Industrial Administration at the Carnegie Institute of Technology, now Carnegie Mellon University. In Administrative Behavior and later works he described decision-makers in organisations whose capacity for rational action is limited and who settle for a satisfactory alternative; “bounded rationality” and “satisficing” are his terms for this. With Charles Holt, Franco Modigliani and John Muth he developed linear decision rules for production and inventory planning; with Allen Newell, whom he met at RAND in 1952, he wrote early computer programs that simulated human problem solving. He shared the 1975 Turing Award with Newell and received the 1978 Nobel Memorial Prize in Economic Sciences for research on decision-making in economic organisations.

The life, in moments →

Main works

  • Administrative Behavior (1947)
  • Models of Man (1957)
  • Planning Production, Inventories, and Work Force, with C. C. Holt, F. Modigliani and J. F. Muth (1960)
  • The Sciences of the Artificial (1969)
  • Human Problem Solving, with A. Newell (1972)

Chapter 11 · Architecture of Decision Support

Milind Tambe

living

Computer scientist; doctorate from the School of Computer Science at Carnegie Mellon University. At the University of Southern California, where he held the Helen N. and Emmett H. Jones Professorship in Engineering and was founding co-director of the Center for Artificial Intelligence in Society, his group built deployed scheduling systems on Stackelberg security games: ARMOR began randomising checkpoints and canine patrols at Los Angeles International Airport in 2007, and later systems were used by the US Coast Guard and the Federal Air Marshal Service, and against wildlife poaching. He is Gordon McKay Professor of Computer Science at Harvard, where he directs the Center for Research on Computation and Society, and director for “AI for Social Good” at Google. He is a fellow of AAAI and ACM and received the IJCAI John McCarthy Award.

The life, in moments →

Main works

  • “Deployed ARMOR protection”, with J. Pita et al. (2008)
  • “Playing games for security”, with P. Paruchuri et al. (2008)
  • Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned (2012)