7. Multi-Objective Optimization and Decision Analysis
Every model in the previous chapters had a single objective and, apart from Chapter 6's MDPs, known data. Real decisions rarely fit that mold: a plan must be cheap and clean and reliable, and its payoff depends on a future nobody knows. This chapter covers the three toolkits OR uses when "maximize one number" is not enough: multi-objective optimization (finding the efficient trade-offs of a model with several objectives), decision theory (choosing well when the outcome depends on an uncertain state of the world), and multi-criteria decision making (ranking a short list of alternatives scored on many criteria). In each case the mathematics does not remove the need for judgment. It makes the judgment explicit, consistent and open to scrutiny.
<a id="71-multi-objective-optimization"></a>
7.1 Multi-Objective Optimization
When a model has several objectives that conflict, there is usually no solution that is best for all of them at once. The task changes from "find the optimum" to "find the set of efficient trade-offs, then help someone choose among them". This subchapter defines efficiency (Pareto optimality) and presents the four classic ways to turn a multi-objective problem into one or more single-objective problems that ordinary solvers can handle: weighted sums, epsilon-constraints, goal programming and lexicographic optimization.
Two running examples are used throughout:
- Server configurations (discrete). Nine cloud configurations, each with a monthly cost and a p95 latency. Both are minimized.
- Energy mix (continuous LP). Supply exactly 100 MWh from three sources, minimizing both cost and CO2 emissions:
| Source | Cost ($/MWh) | CO2 (t/MWh) | Capacity (MWh) |
|---|---|---|---|
| Coal | 30 | 1.0 | 60 |
| Gas | 50 | 0.5 | 60 |
| Wind | 80 | 0.0 | 50 |
Pareto Optimality
Why it matters. With two or more objectives, "optimal" has no meaning until someone says how the objectives should be traded. Before that conversation can happen, one requirement is uncontroversial: never recommend a solution that could be improved in one objective without getting worse in any other. Pareto optimality formalizes exactly this requirement. It shrinks the set of candidates, often dramatically, without asking anyone for preferences.
Theory. A multi-objective problem is
$$ \min_{x \in X} ; F(x) = \big( f_1(x), f_2(x), \dots, f_k(x) \big), $$
where $X$ is the feasible set (the decision space) and $F(X) \subset \mathbb{R}^k$ is the set of attainable objective vectors (the objective space). Maximized objectives are handled by minimizing their negatives.
A solution $x$ dominates $y$ (written $x \prec y$) if it is no worse in every objective and strictly better in at least one:
$$ f_i(x) \le f_i(y) ;; \forall i \qquad \text{and} \qquad f_j(x) < f_j(y) ;; \text{for some } j. $$
A feasible $x^$ is Pareto optimal (or efficient, or non-dominated) if no feasible solution dominates it. Its image $F(x^)$ lies on the Pareto front. A weaker notion is also used: $x^*$ is weakly Pareto optimal if no feasible solution is strictly better in every objective. Weakly optimal points can still be improved in some objective for free, so they are not acceptable final answers, but some methods below can return them.
An everyday analogy: when buying a laptop, you would never buy one that is both more expensive and slower than another on the shelf. After discarding every such laptop, the ones left are the Pareto set. Choosing among them requires knowing how much you value speed against money, and that is a preference, not a calculation.
| Relation between $x$ and $y$ | Condition | Example (cost, latency) |
|---|---|---|
| $x$ dominates $y$ | no worse everywhere, better somewhere | (120, 95) vs (140, 110) |
| $x$ weakly dominates $y$ | no worse everywhere | (150, 60) vs (150, 60) |
| incomparable | each is better in some objective | (150, 60) vs (200, 45) |
Two reference points summarize the range of the front:
- The ideal point $z^I$ has, in each coordinate, the best value of that objective over $X$: $z^I_i = \min_{x \in X} f_i(x)$. It is usually not attainable, which is exactly why the problem is hard.
- The nadir point $z^N$ has, in each coordinate, the worst value of that objective over the Pareto set. It tells you how bad an objective can get if you accept an efficient solution. With two objectives it is read from the two single-objective optima. With three or more it is hard to compute exactly.
Shape matters for what follows:
| Problem class | Shape of the Pareto front |
|---|---|
| Multi-objective LP | piecewise linear, connected, made of faces of the polyhedron |
| Convex objectives and feasible set | the attainable set $F(X) + \mathbb{R}^k_{+}$ is convex, so the front "bulges" toward the ideal point |
| Integer, combinatorial or nonconvex | may have gaps and dents; some Pareto points lie inside the convex hull of others |
Points in a dent are called unsupported: they are Pareto optimal, but no weighted sum of the objectives selects them (next topic).
Example: filtering server configurations. The code checks every pair for dominance, which costs $O(N^2 k)$. For two objectives, sorting by $f_1$ and sweeping while tracking the best $f_2$ seen so far gives the front in $O(N \log N)$.
# Candidate server configurations: name -> (monthly cost in $, p95 latency in ms)
# Both objectives are minimized.
CONFIGS = {"A": (120, 95), "B": (150, 60), "C": (200, 45), "D": (260, 40),
"E": (180, 70), "F": (300, 38), "G": (140, 110), "H": (230, 47),
"I": (170, 58)}
def dominates(p, q):
"""p dominates q: no worse in every objective and strictly better in one."""
return all(a <= b for a, b in zip(p, q)) and any(a < b for a, b in zip(p, q))
pareto = {n: v for n, v in CONFIGS.items()
if not any(dominates(w, v) for w in CONFIGS.values() if w != v)}
for n, v in CONFIGS.items():
killers = [m for m, w in CONFIGS.items() if dominates(w, v)]
print(f"{n} {v}: " + ("Pareto-optimal" if not killers else f"dominated by {', '.join(killers)}"))
front = sorted(pareto.values())
ideal = tuple(min(v[k] for v in front) for k in range(2)) # best value of each objective
nadir = tuple(max(v[k] for v in front) for k in range(2)) # worst value ON the front
print("front:", front)
print("ideal:", ideal, " nadir:", nadir)
# A (120, 95): Pareto-optimal
# B (150, 60): Pareto-optimal
# C (200, 45): Pareto-optimal
# D (260, 40): Pareto-optimal
# E (180, 70): dominated by B, I
# F (300, 38): Pareto-optimal
# G (140, 110): dominated by A
# H (230, 47): dominated by C
# I (170, 58): Pareto-optimal
# front: [(120, 95), (150, 60), (170, 58), (200, 45), (260, 40), (300, 38)]
# ideal: (120, 38) nadir: (300, 95)
latency (ms) UPPERCASE = Pareto-optimal, lowercase = dominated
110 | g
95 | A
70 | e
60 | B
58 | I
47 | h
45 | C
40 | D
38 | F
+----------------------------------------------------> cost ($/month)
100 140 180 220 260 300
Three of nine configurations are eliminated without any preference information. G is beaten by A on both axes. E is beaten by both B and I. H is beaten by C. The six survivors run from the cheapest (A, $120) to the fastest (F, 38 ms), and moving along the front always trades money for latency: going from C to D buys 5 ms for $60, while going from D to F buys only 2 ms for $40. These local exchange rates are what a decision maker needs to see. A point where the rate changes sharply (a knee, here around B and C) is often a good compromise, because moving away from it in either direction is expensive.
Key takeaways
- $x$ dominates $y$ if it is no worse in every objective and strictly better in one. Pareto-optimal solutions are those no feasible solution dominates.
- The Pareto front is the set of efficient trade-offs. Choosing a point on it requires preferences, which the mathematics cannot supply.
- The ideal point (best of each objective) bounds the front from one side, the nadir point (worst of each objective on the front) from the other.
- Convex problems have convex fronts. Discrete and nonconvex problems can have unsupported Pareto points in dents of the front.
Practice
- (Beginner) Add configuration J = (190, 50). Is it Pareto-optimal? Does it dominate any configuration that was Pareto-optimal before? Recompute the ideal and nadir points.
- (Intermediate) Implement the $O(N \log N)$ sort-and-sweep filter for two objectives and check it against the pairwise version on 10,000 random points. Then explain why the sweep does not extend directly to three objectives.
- (Interview) "A product manager asks you for the optimal server configuration, minimizing both cost and latency. What do you deliver?" Hint: the Pareto set with its exchange rates, a knee point as a candidate, and one or two questions that reveal the manager's preferences (for example, a latency SLA or a budget cap).
Weighted Sum Method
Why it matters. The weighted sum is the most common way to handle several objectives, because it turns the problem back into a single-objective one that any LP, MIP or nonlinear solver can handle. It is also the method whose limitations are most often misunderstood: weights are not "importance percentages", uniform weight grids do not give uniform coverage of the front, and some Pareto points can never be found this way.
Theory. Choose weights $w_i \ge 0$ with $\sum_i w_i = 1$ and solve
$$ \min_{x \in X} ; \sum_{i=1}^{k} w_i , f_i(x). $$
Two theorems describe what this produces:
- Sufficiency. If every $w_i > 0$, any optimal solution is Pareto optimal. (If some $w_i = 0$, the solution is only guaranteed to be weakly Pareto optimal.) Proof sketch: if $y$ dominated the optimum $x$, then $\sum w_i f_i(y) < \sum w_i f_i(x)$, contradicting optimality.
- Necessity, convex case only. If the problem is convex, every Pareto-optimal point is optimal for some nonnegative weight vector. Without convexity this fails: unsupported points are never optimal for any weights.
Geometry. In objective space, the level sets of $w_1 f_1 + w_2 f_2$ are straight lines with slope $-w_1 / w_2$. Solving the weighted problem means sliding such a line from the ideal point outward until it first touches the attainable set. A straight line can only touch the set at points of its convex hull, so a point in a dent is never touched first:
f2 (latency)
| A
| \
| \
| B . . I I is Pareto-optimal, but it lies above the segment B-C.
| `. Any line touching I has already touched B or C first.
| `.
| C
| `- D
| `-- F
+--------------------------- f1 (cost)
Normalization. The weights multiply objectives measured in different units. A weight of 0.5 on dollars and 0.5 on tonnes means nothing unless the objectives are first scaled to comparable ranges. A standard choice uses the ideal and nadir points:
$$ \tilde f_i(x) = \frac{f_i(x) - z^I_i}{z^N_i - z^I_i} \in [0, 1]. $$
The ratio $w_1 / w_2$ is an exchange rate: how many units of $\tilde f_2$ you are willing to give up for one unit of $\tilde f_1$. In unnormalized form, minimizing $\text{cost} + \lambda \cdot \text{CO2}$ is exactly pricing carbon at $\lambda$ dollars per tonne.
LP behavior. For an LP, the weighted problem is an LP, so its optimum is a vertex (Section 2.2). As the weights move, the solution stays at one vertex and then jumps to the next. Non-vertex points on an edge of the front are only returned at the single tie weight, and even then the solver picks an arbitrary point.
Example: energy mix and server configurations. The code sweeps 1,001 weight values and records the weight interval that produces each solution. It then repeats the sweep on the discrete server front.
import numpy as np
from scipy.optimize import linprog
# Energy mix: supply 100 MWh from coal, gas and wind
cost = np.array([30, 50, 80]) # $ per MWh
emis = np.array([1.0, 0.5, 0.0]) # t CO2 per MWh
cap = [(0, 60), (0, 60), (0, 50)] # capacity of each source (MWh)
A_eq, b_eq = [[1, 1, 1]], [100] # meet demand exactly
def solve(c):
return linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=cap).x
# Single-objective optima give the ranges used to normalize each objective
x_c, x_e = solve(cost), solve(emis)
f_lo = np.array([cost @ x_c, emis @ x_e]) # ideal point
f_hi = np.array([cost @ x_e, emis @ x_c]) # nadir point (exact for 2 objectives)
print("ideal", f_lo, " nadir", f_hi)
found = {} # point -> weights that produced it
for w in np.linspace(0, 1, 1001):
c = w * cost / (f_hi[0] - f_lo[0]) + (1 - w) * emis / (f_hi[1] - f_lo[1])
x = solve(c)
key = (round(cost @ x), round(emis @ x, 1), tuple(int(v) for v in np.round(x)))
found.setdefault(key, []).append(w)
for (fc, fe, mix), ws in found.items():
print(f"w in [{min(ws):.3f}, {max(ws):.3f}] mix={list(mix)} cost={fc} CO2={fe}")
# Discrete case: which Pareto-optimal server configs can EVER win a weighted sum?
front = {"A": (120, 95), "B": (150, 60), "I": (170, 58), "C": (200, 45),
"D": (260, 40), "F": (300, 38)}
winners = set()
for w in np.linspace(0, 1, 1001):
score = {n: w * (c - 120) / 180 + (1 - w) * (l - 38) / 57 for n, (c, l) in front.items()}
winners.add(min(score, key=score.get))
print("supported:", sorted(winners), " never chosen:", sorted(set(front) - winners))
# ideal [3800. 25.] nadir [6500. 80.]
# w in [0.000, 0.450] mix=[0, 50, 50] cost=6500 CO2=25.0
# w in [0.451, 0.495] mix=[0, 60, 40] cost=6200 CO2=30.0
# w in [0.496, 0.551] mix=[40, 60, 0] cost=4200 CO2=70.0
# w in [0.552, 1.000] mix=[60, 40, 0] cost=3800 CO2=80.0
# supported: ['A', 'B', 'C', 'D', 'F'] never chosen: ['I']
The LP front has four vertices, and each one is optimal for a whole interval of weights. In cost-per-tonne terms, the edges between consecutive vertices have slopes of $400/10 = 40$, $2000/40 = 50$ and $300/5 = 60$ dollars per tonne. Pricing carbon below $40/t gives the cheapest mix, above $60/t gives the cleanest, and the two intermediate mixes need a price between those values. Two practical lessons follow. First, the vertex (6200, 30) only appears for $w \in [0.451, 0.495]$: an evenly spaced grid of 11 weights ($0, 0.1, \dots, 1$) misses it completely. Second, the mix (30 coal, 60 gas, 10 wind) with 60 t of CO2 is Pareto-optimal (the epsilon-constraint topic finds it), but it lies in the middle of an edge, so no weight returns it. In the discrete case the result is worse: configuration I is Pareto-optimal but never selected for any weight, as the geometry predicted.
Key takeaways
- The weighted sum turns a multi-objective problem into one problem per weight vector. With strictly positive weights the result is Pareto optimal.
- It finds every Pareto point only for convex problems. Unsupported points of discrete or nonconvex problems are invisible to it.
- Normalize objectives before weighting. Weight ratios are exchange rates, not importance percentages.
- On LPs it returns vertices only, and uniform weight grids can skip parts of the front.
Practice
- (Beginner) Without running code, find the carbon price $\lambda$ (dollars per tonne) at which the solution of $\min ; \text{cost} + \lambda \cdot \text{CO2}$ switches from (4200, 70) to (6200, 30). Convert it to the normalized weight $w$ and compare with the printed interval.
- (Intermediate) Build a two-variable LP in which the weights $(1, 0)$ have several optimal solutions, some of them dominated. Show that a solver may return a dominated one, and that the weights $(1, \varepsilon)$ with a small $\varepsilon > 0$ fix the problem.
- (Interview) "Users of our planning dashboard complain that moving the 'cost vs. sustainability' slider slightly makes the recommended plan jump to something completely different. Why, and what would you change?" Hint: vertices of an LP, flat regions in weight space, and alternatives such as an epsilon-constraint slider in natural units.
Epsilon-Constraint Method
Why it matters. The epsilon-constraint method fixes both weaknesses of the weighted sum: it can reach every Pareto point, including unsupported ones and points in the middle of LP edges, and its parameters are expressed in natural units ("emissions at most 50 t") that decision makers understand. It is the standard way to draw a trade-off curve for an executive.
Theory. Keep one objective, $f_j$, and turn every other objective into a constraint with an upper bound $\varepsilon_i$:
$$ \min_{x \in X} ; f_j(x) \qquad \text{s.t.} \quad f_i(x) \le \varepsilon_i \quad \forall i \ne j. $$
Varying the vector $\varepsilon$ traces the front. Three facts make the method work:
- Completeness. Every Pareto-optimal $x^$ is optimal for the problem with $\varepsilon_i = f_i(x^)$, convex or not.
- Weak optimality. Every optimal solution is at least weakly Pareto optimal. If the optimum is unique, it is Pareto optimal. When there are ties, the solver may return a point that is dominated in the constrained objectives. Two remedies are common: a second stage that minimizes $\sum_{i \ne j} f_i$ while keeping $f_j$ at its optimum, or the augmented version (AUGMECON), which adds slack variables $s_i$ with $f_i(x) + s_i = \varepsilon_i$ and minimizes $f_j(x) - \delta \sum_i s_i / r_i$ for a tiny $\delta > 0$ and objective ranges $r_i$.
- Trade-off rates for free. The dual value of the constraint $f_i(x) \le \varepsilon_i$ is the marginal rate at which $f_j$ improves when $\varepsilon_i$ is relaxed by one unit (Section 2.5). On the energy problem, it is the marginal cost of abatement in dollars per tonne.
Choosing $\varepsilon$. Useful values lie between the ideal and the nadir values of the constrained objectives. Below the ideal value the problem is infeasible. Above the nadir value the constraint never binds. A grid of 10 to 20 values is typical. Each grid point is a full solve, so for large MIPs warm starts and parallel solves matter.
| Weighted sum | Epsilon-constraint | |
|---|---|---|
| Finds unsupported points | no | yes |
| Finds non-vertex LP points | only at tie weights | yes |
| Parameter meaning | exchange rates (needs normalization) | caps in natural units |
| Output quality | Pareto optimal (positive weights) | weakly Pareto optimal unless augmented |
| Problem structure | unchanged, only the objective | adds constraints (can hurt MIP structure) |
| Extra information | none | dual values = trade-off rates |
Example: the abatement curve. The code minimizes cost for a sequence of emission caps and prints the dual value of the cap. It then applies the method to the discrete server front.
import numpy as np
from scipy.optimize import linprog
cost = np.array([30, 50, 80]) # $ per MWh: coal, gas, wind
emis = np.array([1.0, 0.5, 0.0]) # t CO2 per MWh
cap = [(0, 60), (0, 60), (0, 50)]
A_eq, b_eq = [[1, 1, 1]], [100]
# epsilon-constraint: minimize cost subject to emissions <= eps
print(" eps coal gas wind cost CO2 dual($/t)")
for eps in [80, 70, 60, 50, 40, 30, 25, 20]:
r = linprog(cost, A_ub=[emis], b_ub=[eps], A_eq=A_eq, b_eq=b_eq,
bounds=cap, method="highs")
if r.status == 2: # 2 = infeasible
print(f"{eps:4} infeasible: no mix emits that little")
continue
price = -r.ineqlin.marginals[0] # extra cost of 1 t less CO2
x = np.round(r.x, 1)
print(f"{eps:4} {x[0]:5} {x[1]:4} {x[2]:4} {r.fun:5.0f} {emis @ r.x:4.0f} {price:6.1f}")
# Discrete server configs: epsilon-constraint on latency finds the unsupported config I
configs = {"A": (120, 95), "B": (150, 60), "I": (170, 58), "C": (200, 45),
"D": (260, 40), "F": (300, 38)}
for eps in [100, 59, 58, 50, 45, 40, 38]:
ok = {n: c for n, (c, l) in configs.items() if l <= eps} # latency <= eps
best = min(ok, key=ok.get)
print(f"latency <= {eps:3}: choose {best} {configs[best]}")
# eps coal gas wind cost CO2 dual($/t)
# 80 60.0 40.0 0.0 3800 80 0.0
# 70 40.0 60.0 0.0 4200 70 40.0
# 60 30.0 60.0 10.0 4700 60 50.0
# 50 20.0 60.0 20.0 5200 50 50.0
# 40 10.0 60.0 30.0 5700 40 50.0
# 30 0.0 60.0 40.0 6200 30 60.0
# 25 0.0 50.0 50.0 6500 25 60.0
# 20 infeasible: no mix emits that little
# latency <= 100: choose A (120, 95)
# latency <= 59: choose I (170, 58)
# latency <= 58: choose I (170, 58)
# latency <= 50: choose C (200, 45)
# latency <= 45: choose C (200, 45)
# latency <= 40: choose D (260, 40)
# latency <= 38: choose F (300, 38)
Every cap between the ideal (25 t) and the nadir (80 t) gives a point of the front, including the three mixes in the middle of the 70-30 edge that no weight could produce. The dual column is a marginal abatement cost curve: the first 10 t of reduction cost $40/t (replacing coal by gas), the next 40 t cost $50/t (replacing coal by wind), and the last 5 t cost $60/t (replacing gas by wind). At the breakpoints, 70 t and 30 t, the cost curve has a kink and the dual is not unique: the solver reports one of the two one-sided slopes. In the discrete case, the cap "latency $\le$ 59" returns configuration I, the unsupported point the weighted sum could never find.
Key takeaways
- Optimize one objective and cap the others: $\min f_j$ subject to $f_i \le \varepsilon_i$. Varying the caps traces the whole front, convex or not.
- Solutions are weakly Pareto optimal in general. Use a second stage or the augmented version to guarantee efficiency.
- Caps are in natural units, and their dual values are the trade-off rates between objectives.
- Choose caps between the ideal and nadir values. Each cap is a full solve.
Practice
- (Beginner) Using only the printed dual values, predict the cost of the cheapest mix that emits at most 45 t. Then run the model with
eps = 45to check your prediction.- (Intermediate) Add configuration J = (200, 52) to the server list. With the cap "latency $\le$ 55", show that a plain epsilon-constraint solve may return J, which is dominated by C. Fix it once with a second stage and once with the augmented objective.
- (Interview) "Leadership wants a cost vs. emissions curve for our network-design MIP, which takes 20 minutes per solve. How do you produce it?" Hint: compute the ideal and nadir points first, choose a small grid of caps, warm-start each solve from its neighbor, run solves in parallel, and report the marginal cost between points.
Goal Programming
Why it matters. Managers usually think in targets: "stay within a $5,000 budget, keep emissions under 40 t, buy at least 45 MWh of wind". Written as hard constraints, conflicting targets make a model infeasible, which tells the manager nothing. Goal programming (Charnes and Cooper, 1961) treats targets as soft and finds the plan that misses them by the least, in a sense the manager chooses.
Theory. Each goal $g_i(x)$ with target $t_i$ becomes an equality with two nonnegative deviation variables:
$$ g_i(x) + d_i^- - d_i^+ = t_i, \qquad d_i^-, d_i^+ \ge 0, $$
where $d_i^-$ measures underachievement and $d_i^+$ overachievement. Only the unwanted deviation is penalized:
| Goal type | Meaning | Penalize |
|---|---|---|
| $g_i(x) \le t_i$ | do not exceed (budget, emissions) | $d_i^+$ |
| $g_i(x) \ge t_i$ | reach at least (output, service level) | $d_i^-$ |
| $g_i(x) = t_i$ | hit exactly (staffing level) | $d_i^- + d_i^+$ |
Constraints that must hold, such as physical capacities and meeting demand, stay as hard constraints. The three main variants differ in how they combine the deviations:
| Variant | Objective | Behavior |
|---|---|---|
| Weighted GP | $\min \sum_i w_i , d_i / t_i$ | total (percentage) miss. Tends to meet some goals exactly and sacrifice others |
| Minmax (Chebyshev) GP | $\min D$ with $D \ge w_i d_i / t_i ;\forall i$ | balances the misses. Minimizes the worst one |
| Preemptive (lexicographic) GP | minimize priority-1 deviations, then priority 2, ... | strict priorities (see the next topic) |
Dividing by $t_i$ (or another scale) is essential, for the same reason as normalization in the weighted sum: without it, a deviation of one dollar and one tonne count the same.
GP has one known pitfall: once a target is met, the model has no incentive to improve that goal further. If the targets are too easy, the GP solution can be Pareto-inefficient (another plan is better on every goal). Check efficiency afterwards, or add a tiny penalty on the objectives themselves.
Example: three conflicting targets. The energy model has a budget goal ($5,000), an emissions goal (40 t) and a renewable goal (45 MWh of wind). The code builds the deviation variables generically and solves three versions.
import numpy as np
from scipy.optimize import linprog
cost = np.array([30, 50, 80]) # $ per MWh: coal, gas, wind
emis = np.array([1.0, 0.5, 0.0]) # t CO2 per MWh
wind = np.array([0, 0, 1]) # MWh of wind
goals = [ # (name, coefficients, target, which deviation is unwanted)
("budget", cost, 5000, "over"), # spend at most $5000
("CO2", emis, 40, "over"), # emit at most 40 t
("wind", wind, 45, "under"), # buy at least 45 MWh of wind
]
def goal_program(weights, minmax=False):
# variables: x1 x2 x3 | d1- d1+ d2- d2+ d3- d3+ | (t for minmax)
k = len(goals); n = 3 + 2 * k + (1 if minmax else 0)
A_eq = [[1, 1, 1] + [0] * (n - 3)]; b_eq = [100] # hard constraint: demand
c = np.zeros(n); A_ub, b_ub = [], []
for i, (name, a, target, bad) in enumerate(goals):
row = list(a) + [0] * (n - 3)
row[3 + 2 * i], row[4 + 2 * i] = 1, -1 # a.x + d- - d+ = target
A_eq.append(row); b_eq.append(target)
j = 4 + 2 * i if bad == "over" else 3 + 2 * i # unwanted deviation
coef = weights[i] / target # percentage normalization
if minmax: # t >= weighted % deviation
r = [0] * n; r[j] = coef; r[-1] = -1
A_ub.append(r); b_ub.append(0)
else:
c[j] = coef
if minmax:
c[-1] = 1
bounds = [(0, 60), (0, 60), (0, 50)] + [(0, None)] * (n - 3)
r = linprog(c, A_ub=A_ub or None, b_ub=b_ub or None, A_eq=A_eq, b_eq=b_eq,
bounds=bounds, method="highs")
x = r.x[:3]
devs = [f"{name} {a @ x - t:+.0f}" for name, a, t, _ in goals]
return np.round(x, 1), devs
for label, w, mm in [("weighted 1:1:1", [1, 1, 1], False),
("weighted 5:1:1", [5, 1, 1], False),
("minmax 1:1:1", [1, 1, 1], True)]:
x, devs = goal_program(w, mm)
print(f"{label}: mix={x} deviations from targets: {', '.join(devs)}")
# weighted 1:1:1: mix=[25. 30. 45.] deviations from targets: budget +850, CO2 +0, wind +0
# weighted 5:1:1: mix=[60. 0. 40.] deviations from targets: budget +0, CO2 +20, wind -5
# minmax 1:1:1: mix=[29.2 31.2 39.6] deviations from targets: budget +603, CO2 +5, wind -5
The targets conflict: with 40 t of CO2 the cheapest mix already costs $5,700 (epsilon-constraint table), so not all three goals can be met. Weighted GP with equal weights meets the CO2 and wind goals exactly and puts the entire miss on the budget ($850, or 17%). Raising the budget weight to 5 makes the solution jump to a different vertex that meets the budget exactly but misses CO2 by 50% and wind by 11%. Weighted GP behaves like the weighted sum: it moves from extreme to extreme. Minmax GP spreads the pain evenly instead: each goal is missed by about 12% ($603 of $5,000, 4.8 of 40 t, 5.4 of 45 MWh). Which answer is right depends on whether the organization prefers to fully protect some goals or to compromise on all of them.
Key takeaways
- Each goal gets deviation variables $d^-$ and $d^+$. Penalize only the unwanted one, and keep true requirements as hard constraints.
- Normalize deviations (for example as percentages of the target) before adding them.
- Weighted GP tends to satisfy some goals fully and sacrifice others. Minmax GP balances the misses. Preemptive GP imposes strict priorities.
- GP solutions can be Pareto-inefficient when targets are easy. Check efficiency.
Practice
- (Beginner) Write the goal constraints and the penalized deviation variables for: "deliver at least 95% of orders on time", "use exactly 40 hours of overtime" and "keep inventory below 500 units".
- (Intermediate) Change the budget target to $7,000 and rerun the weighted GP. All goals are met, so the objective is zero. Is the plan returned Pareto optimal for (cost, CO2, wind)? Add a small penalty on cost and CO2 and compare.
- (Interview) "Why do practitioners normalize the deviations in weighted goal programming, and what goes wrong if they don't?" Hint: compare a goal in dollars with a goal in tonnes, and consider what changing the unit of one goal (dollars to thousands of dollars) does to the solution.
Lexicographic Optimization
Why it matters. Some objectives are not traded at any rate: patient safety before cost, covering every shift before honoring preferences, complying with regulations before maximizing profit. Lexicographic optimization models such strict priorities directly. Approximating them with huge weights in a single objective (for example $10^6 f_1 + 10^3 f_2 + f_3$) causes numerical trouble and silently fails when the magnitudes are misjudged.
Theory. Objectives are ranked $f_1 \succ f_2 \succ \dots \succ f_k$. A solution $x$ is lexicographically better than $y$ if it is better in $f_1$, or equal in $f_1$ and better in $f_2$, and so on, the same rule a dictionary uses to order words. The sequential algorithm solves one problem per priority level:
$$ \begin{aligned} f_1^* &= \min_{x \in X} f_1(x), \ f_2^* &= \min_{x \in X} { f_2(x) : f_1(x) \le f_1^* }, \ f_3^* &= \min_{x \in X} { f_3(x) : f_1(x) \le f_1^, ; f_2(x) \le f_2^ }, \quad \dots \end{aligned} $$
The final solution is Pareto optimal: it is the extreme point of the front that the priority order points to. Three practical points:
- Ties drive everything. Lower-priority objectives only matter if the higher stages leave several optimal solutions. If stage 1 has a unique optimum, the remaining stages change nothing.
- Tolerances. In practice each optimum is locked in with a tolerance, $f_k(x) \le f_k^* + \tau_k$. This prevents floating-point failures (an LP may report $f_1^* = 25.0000001$) and lets a lower-priority objective improve substantially at a negligible cost to a higher one. Relative tolerances ($f_k^* (1 + \rho)$) fail when $f_k^* = 0$, so absolute tolerances are often safer.
- Solver support. Commercial solvers such as Gurobi and CPLEX accept several objectives with priorities and tolerances and run the stages internally. Preemptive goal programming is the same algorithm applied to deviation variables.
Example: supply security first. The utility now ranks its objectives as: minimize gas purchases (exposure to volatile gas prices), then cost, then CO2.
import numpy as np
from scipy.optimize import linprog
cost = np.array([30, 50, 80]) # $ per MWh: coal, gas, wind
emis = np.array([1.0, 0.5, 0.0]) # t CO2 per MWh
gas = np.array([0, 1, 0]) # MWh bought from gas (price-risk exposure)
cap = [(0, 60), (0, 60), (0, 50)]
A_eq, b_eq = [[1, 1, 1]], [100]
def lexicographic(objectives, tolerances):
"""Optimize objectives in priority order. After stage k, add the constraint
f_k(x) <= f_k* + tol_k so later stages cannot spoil earlier ones (beyond tol_k)."""
A_ub, b_ub = [], []
for (name, f), tol in zip(objectives, tolerances):
r = linprog(f, A_ub=A_ub or None, b_ub=b_ub or None, A_eq=A_eq, b_eq=b_eq,
bounds=cap, method="highs")
x = r.x + 0.0 # + 0.0 turns -0.0 into 0.0
print(f" {name:4} optimum {r.fun:6.0f} mix={np.round(x, 1)} "
f"cost={cost @ x:.0f} CO2={emis @ x:.0f} gas={gas @ x:.0f}")
A_ub.append(f); b_ub.append(r.fun + tol) # lock in this level
return x
order = [("gas", gas), ("cost", cost), ("CO2", emis)]
print("strict priorities (gas > cost > CO2):")
lexicographic(order, [0, 0, 0])
print("with tolerances (+10 MWh gas, +$250):")
lexicographic(order, [10, 250, 0])
# strict priorities (gas > cost > CO2):
# gas optimum 0 mix=[50. 0. 50.] cost=5500 CO2=50 gas=0
# cost optimum 5000 mix=[60. 0. 40.] cost=5000 CO2=60 gas=0
# CO2 optimum 60 mix=[60. 0. 40.] cost=5000 CO2=60 gas=0
# with tolerances (+10 MWh gas, +$250):
# gas optimum 0 mix=[50. 0. 50.] cost=5500 CO2=50 gas=0
# cost optimum 4700 mix=[60. 10. 30.] cost=4700 CO2=65 gas=10
# CO2 optimum 60 mix=[55. 10. 35.] cost=4950 CO2=60 gas=10
Stage 1 has many optima: any mix of 50 to 60 MWh of coal plus wind avoids gas entirely. Stage 2 picks the cheapest of these (60 coal, 40 wind, $5,000). After stage 2 the optimum is unique, so stage 3 cannot reduce CO2 below 60 t. With tolerances, accepting 10 MWh of gas lets stage 2 reach $4,700, and accepting $250 above that lets stage 3 bring CO2 back to 60 t. The final plan costs $4,950: cheaper than the strict plan with the same CO2, paid for by 10 MWh of gas exposure. Tolerances are how a strict hierarchy becomes a negotiable one, and choosing them is a business decision, not a technical detail.
Key takeaways
- Lexicographic optimization ranks objectives strictly and solves one problem per priority, locking in each optimum as a constraint.
- Lower priorities only matter when higher ones leave ties. The result is a Pareto-optimal extreme point of the front.
- Use tolerances when locking in optima, both for numerical robustness and to allow small sacrifices with large benefits. Prefer absolute tolerances near zero.
- Avoid emulating priorities with huge weights in a single objective.
Practice
- (Beginner) Rerun the code with the order CO2, cost, gas and no tolerances. Explain why stages 2 and 3 have no effect.
- (Intermediate) Emulate the strict order gas, cost, CO2 with one weighted objective $10^6 \cdot \text{gas} + 10^3 \cdot \text{cost} + \text{CO2}$ and check that it gives the same plan. Then express cost in cents instead of dollars and see whether the emulation still works.
- (Interview) "A nurse-rostering model must first cover every shift, then respect nurses' preferences, then balance workload. How would you structure the objective, and what happens if full coverage is impossible?" Hint: hierarchical objectives, slack variables for uncovered shifts at the top level so stage 1 is always feasible, and tolerances between levels.
<a id="72-decision-theory"></a>
7.2 Decision Theory
Subchapter 7.1 assumed that each decision has known consequences. Decision theory handles the other difficulty: the consequence depends on a state of nature that is unknown when the decision is made. This subchapter classifies decision environments, presents the classic criteria for decisions without probabilities, the expected value criterion for decisions with them, decision trees for sequential decisions, the value of information, and utility theory for decision makers who care about risk.
All examples use one capacity decision. A company must choose a plant size before it knows whether demand will be low, medium or high. Profits are in thousands of dollars:
| Alternative | Low demand | Medium demand | High demand |
|---|---|---|---|
| Small plant | 200 | 250 | 300 |
| Medium plant | 100 | 400 | 500 |
| Large plant | -200 | 300 | 800 |
| Outsource | 150 | 230 | 280 |
When probabilities are used, they are $P(\text{low}) = 0.3$, $P(\text{medium}) = 0.5$, $P(\text{high}) = 0.2$.
Decision Making Under Certainty, Risk and Uncertainty
Why it matters. The right way to choose depends on what you know about the future. Treating an uncertain problem as certain (plugging in "the expected demand") is one of the most common modeling errors in practice. Classifying the decision environment is therefore the first modeling step, before any criterion is chosen.
Theory. A decision problem in normal form has three elements:
- a set of alternatives $a_1, \dots, a_m$ (what we control),
- a set of states of nature $s_1, \dots, s_n$ (what we do not control), mutually exclusive and exhaustive,
- a payoff $v_{ij}$ for each pair, arranged in a payoff table (or a cost table if smaller is better).
The three classic environments differ in what is known about the states:
| Environment | What is known | Typical tools | Example |
|---|---|---|---|
| Certainty | the state that will occur | deterministic optimization (Chapters 2 to 6) | route planning with known travel times |
| Risk | the probability $p_j$ of each state | expected value, expected utility, decision trees | pricing car insurance from actuarial tables |
| Uncertainty | only the list of possible states | maximin, maximax, Hurwicz, minimax regret | investing in an unprecedented technology |
The distinction between risk and uncertainty goes back to Frank Knight (1921). In practice the boundary is soft. Probabilities can come from historical frequencies, from a model, or from expert judgment (subjective probabilities). Once an expert is willing to state probabilities, an uncertainty problem becomes a risk problem, and sensitivity analysis can show how much the decision depends on them.
One filter applies in every environment: dominance. If alternative $a_k$ pays at least as much as $a_i$ in every state and strictly more in at least one, then $a_i$ can be discarded whatever the probabilities and whatever the decision maker's attitude to risk. This is the Pareto dominance of Section 7.1, with states playing the role of objectives.
It is also important to separate the quality of a decision from the quality of an outcome. A good decision under risk can turn out badly (the large plant when demand happens to be low). Decisions should be judged by the information available when they were made, not in hindsight.
Example: the same table, three environments.
import numpy as np
# Payoff table (profit in $k): rows = alternatives, columns = states of nature
states = ["low", "medium", "high"]
alts = ["small", "medium", "large", "outsource"]
P = np.array([[ 200, 250, 300], # small plant
[ 100, 400, 500], # medium plant
[-200, 300, 800], # large plant
[ 150, 230, 280]]) # outsource production
# Step 0 (any environment): drop alternatives dominated in every state
keep = [i for i in range(len(alts))
if not any(np.all(P[j] >= P[i]) and np.any(P[j] > P[i])
for j in range(len(alts)) if j != i)]
print("non-dominated:", [alts[i] for i in keep])
P, alts = P[keep], [alts[i] for i in keep]
# Certainty: the state is known, so pick the best entry of that column
for s, name in enumerate(states):
print(f"certainty, demand={name:6}: build {alts[P[:, s].argmax()]:6} -> {P[:, s].max()}")
# Risk: probabilities are known -> rank by a probability-weighted criterion
p = np.array([0.3, 0.5, 0.2])
print("risk, expected payoff: ", {a: round(float(v)) for a, v in zip(alts, P @ p)})
# Uncertainty: no probabilities -> need a criterion such as maximin (next topic)
print("uncertainty, worst case:", {a: int(v) for a, v in zip(alts, P.min(axis=1))})
# non-dominated: ['small', 'medium', 'large']
# certainty, demand=low : build small -> 200
# certainty, demand=medium: build medium -> 400
# certainty, demand=high : build large -> 800
# risk, expected payoff: {'small': 245, 'medium': 330, 'large': 250}
# uncertainty, worst case: {'small': 200, 'medium': 100, 'large': -200}
Outsourcing is dominated by the small plant in every state, so it is removed before anything else. Under certainty the problem is trivial: read the best entry of the known column. Under risk, the probabilities give a single number per alternative, and the medium plant is best. Under uncertainty there is no single natural number per alternative: the worst-case row shown is only one of several possible summaries, and the next topic compares them.
Key takeaways
- A decision problem has alternatives, states of nature and payoffs. The environment depends on what is known about the states.
- Certainty means deterministic optimization. Risk means known probabilities (expected value, utility). Uncertainty means no probabilities (maximin, regret and similar criteria).
- Remove dominated alternatives first: they are never optimal under any criterion.
- Judge decisions by the information available when they were made, not by their outcomes.
Practice
- (Beginner) Classify each situation as certainty, risk or uncertainty, and justify your answer: (a) scheduling a production run with confirmed orders, (b) deciding how many spare parts to stock using five years of failure data, (c) choosing a strategy for a market that does not exist yet.
- (Intermediate) Add the alternative "phased build" with payoffs (180, 350, 550). Is it dominated? Does it change the decision under certainty (for each state) and under risk?
- (Interview) "A stakeholder says: 'We can't estimate the probabilities, so expected value is useless here.' How do you respond?" Hint: subjective probabilities, ranges instead of point estimates, and break-even probabilities (next topics) that show how wrong the estimates would have to be to change the decision.
Maximin, Maximax and Minimax Regret
Why it matters. When no probabilities are available, the decision still has to be made. The classic criteria for decisions under uncertainty each encode a different attitude: protect against the worst, bet on the best, or avoid looking foolish in hindsight. Knowing what each one assumes, and how each one can mislead, matters more than memorizing formulas, because different criteria often recommend different alternatives for the same table.
Theory. For a payoff table $v_{ij}$ (larger is better):
| Criterion | Score of alternative $a_i$ | Choose | Attitude | Main weakness |
|---|---|---|---|---|
| Maximin (Wald) | $\min_j v_{ij}$ | max score | pessimist: assume the worst state | ignores everything except the worst case |
| Maximax | $\max_j v_{ij}$ | max score | optimist: assume the best state | ignores the downside entirely |
| Hurwicz | $\alpha \max_j v_{ij} + (1 - \alpha) \min_j v_{ij}$ | max score | between the two, $\alpha \in [0, 1]$ = optimism | still ignores intermediate states |
| Laplace | $\frac{1}{n} \sum_j v_{ij}$ | max score | all states equally likely | depends on how states are listed |
| Minimax regret (Savage) | $\max_j r_{ij}$ | min score | minimize the worst missed opportunity | adding an irrelevant alternative can change the choice |
The regret (or opportunity loss) of choosing $a_i$ when state $s_j$ occurs is the difference between the best payoff in that state and the payoff obtained:
$$ r_{ij} = \max_k v_{kj} - v_{ij} ;\ge; 0. $$
Regret measures how bad you would feel looking back: "had I known demand would be high, I would have earned 800 instead of 300". The minimax regret alternative keeps the worst such disappointment as small as possible. The same idea appeared as the penalty in Vogel's method (Section 3.6).
For cost tables the roles flip: maximin becomes minimax (minimize the worst cost), and regret is $v_{ij} - \min_k v_{kj}$.
Each criterion can be criticized with a small example. Maximin prefers $(1, 1, 1)$ to $(0, 1000, 1000)$. Laplace changes its answer if "high demand" is split into "high" and "very high". Minimax regret violates the independence of irrelevant alternatives: an option that is never chosen can still change the column maxima and therefore the ranking of the others. Maximin is also the basis of two-person zero-sum games against an adversary (Chapter 8) and of robust optimization, where "nature" is assumed to choose the worst case.
Example: five criteria, three different answers.
import numpy as np
alts = ["small", "medium", "large"]
P = np.array([[ 200, 250, 300], # payoff ($k) under low / medium / high demand
[ 100, 400, 500],
[-200, 300, 800]])
def report(name, scores, best=max):
pick = best(range(len(alts)), key=lambda i: scores[i])
vals = " ".join(f"{a}={s:7.1f}" for a, s in zip(alts, scores))
print(f"{name:22} {vals} -> {alts[pick]}")
report("maximin (pessimist)", P.min(axis=1))
report("maximax (optimist)", P.max(axis=1))
alpha = 0.6 # Hurwicz optimism coefficient
report("Hurwicz alpha=0.6", alpha * P.max(axis=1) + (1 - alpha) * P.min(axis=1))
report("Laplace (equal p)", P.mean(axis=1))
R = P.max(axis=0) - P # regret = best in column - payoff
print("regret table:\n", R)
report("minimax regret", R.max(axis=1), best=min)
# Adding an irrelevant alternative can flip minimax regret
P2 = np.vstack([P, [650, 100, 100]]) # "lease" option, never chosen
R2 = P2.max(axis=0) - P2
print("max regret with 'lease' added:", dict(zip(alts + ["lease"], R2.max(axis=1).tolist())))
# maximin (pessimist) small= 200.0 medium= 100.0 large= -200.0 -> small
# maximax (optimist) small= 300.0 medium= 500.0 large= 800.0 -> large
# Hurwicz alpha=0.6 small= 260.0 medium= 340.0 large= 400.0 -> large
# Laplace (equal p) small= 250.0 medium= 333.3 large= 300.0 -> medium
# regret table:
# [[ 0 150 500]
# [100 0 300]
# [400 100 0]]
# minimax regret small= 500.0 medium= 300.0 large= 400.0 -> medium
# max regret with 'lease' added: {'small': 500, 'medium': 550, 'large': 850, 'lease': 700}
The pessimist builds small, the optimist builds large, and the Hurwicz criterion with 60% optimism also picks large. Laplace and minimax regret pick medium, which is never the worst in any state and never more than 300 short of the best. The last line shows the irrelevant-alternative effect: adding a "lease" option with a high payoff under low demand (which would never be chosen, since its maximum regret is 700) raises the low-demand column maximum from 200 to 650. Medium's worst regret rises from 300 to 550, and the minimax regret choice flips from medium to small.
Key takeaways
- Maximin protects against the worst state, maximax bets on the best, Hurwicz interpolates with an optimism coefficient $\alpha$, Laplace averages.
- Regret is $r_{ij} = \max_k v_{kj} - v_{ij}$. Minimax regret minimizes the largest regret.
- Different criteria encode different attitudes and often disagree. State the criterion and its rationale explicitly.
- Every criterion has a known flaw. Minimax regret, for example, depends on irrelevant alternatives.
Practice
- (Beginner) Write the Hurwicz score of each plant as a linear function of $\alpha$ and find the ranges of $\alpha$ for which small, medium and large are chosen.
- (Intermediate) Write a version of the
reportcode that works on cost tables (minimax, minimin, regret relative to the column minimum) and apply it to a table of your choice with three suppliers and four price scenarios.- (Interview) "Minimax regret violates basic rationality axioms, yet managers like it. Why?" Hint: think about how decisions are evaluated after the fact, accountability, and what "regret" means to someone who has to explain a decision to a board.
Expected Value Criterion
Why it matters. When probabilities are available, the expected value (EV) criterion uses all of the information in the table, not just the extremes. It is the right criterion for decisions that are repeated many times, and for organizations large enough to absorb the variability of individual outcomes. It is also the starting point for decision trees, the value of information and stochastic programming.
Theory. The expected value of alternative $a_i$ is
$$ \mathrm{EV}(a_i) = \sum_{j=1}^{n} p_j , v_{ij}, $$
and the EV criterion chooses the alternative with the largest one. Its justification is the law of large numbers: if the same decision is repeated many times, the average payoff per decision converges to EV. An equivalent formulation uses the expected opportunity loss $\mathrm{EOL}(a_i) = \sum_j p_j r_{ij}$. Because $\mathrm{EV}(a_i) + \mathrm{EOL}(a_i) = \sum_j p_j \max_k v_{kj}$ is the same for all alternatives, maximizing EV and minimizing EOL always choose the same alternative.
EV has two important limitations:
- It ignores spread. Two alternatives with the same EV can have very different risks: a standard deviation of 35 versus 350, or a 30% chance of a loss. For a one-off decision that can bankrupt the company, the spread matters. Utility theory (the last topic of this subchapter) handles this.
- It depends on the probabilities. Because $\mathrm{EV}$ is linear in $p$, the set of probability vectors for which a given alternative is optimal is a convex polygon, and the boundaries are found by equating EVs. These break-even probabilities are the most useful output of a decision analysis: they tell the decision maker how wrong the probability estimates would have to be to change the decision.
EV of a decision is not the same as the decision based on expected data. Replacing random demand by its mean and optimizing ("flaw of averages") can give a different and worse decision, as the newsvendor example in Chapter 1 showed. Stochastic programming (Section 9.4) builds on this distinction.
Example: EV, risk measures and sensitivity.
import numpy as np
alts = ["small", "medium", "large"]
P = np.array([[ 200, 250, 300],
[ 100, 400, 500],
[-200, 300, 800]])
p = np.array([0.3, 0.5, 0.2]) # P(low), P(medium), P(high)
ev = P @ p
sd = np.sqrt(((P - ev[:, None]) ** 2) @ p) # spread of the outcome around its mean
for a, m, s, row in zip(alts, ev, sd, P):
print(f"{a:6} EV={m:5.0f} SD={s:5.1f} P(loss)={p[row < 0].sum():.1f}")
# Sensitivity: let q = P(high) vary; low and medium share the rest in the ratio 3:5
print("\n q(high) best EVs")
for q in np.arange(0, 0.61, 0.1):
pq = np.array([0.375 * (1 - q), 0.625 * (1 - q), q])
e = P @ pq
print(f" {q:.2f} {alts[e.argmax()]:6} {np.round(e).astype(int)}")
# EV is linear in q, so the switch point solves EV_medium(q) = EV_large(q)
base = lambda q: np.array([0.375 * (1 - q), 0.625 * (1 - q), q])
d0, d1 = (P[2] - P[1]) @ base(0), (P[2] - P[1]) @ base(1)
print(f"large beats medium when q > {-d0 / (d1 - d0):.3f}")
# small EV= 245 SD= 35.0 P(loss)=0.0
# medium EV= 330 SD=155.2 P(loss)=0.0
# large EV= 250 SD=350.0 P(loss)=0.3
#
# q(high) best EVs
# 0.00 medium [231 288 112]
# 0.10 medium [238 309 181]
# 0.20 medium [245 330 250]
# 0.30 medium [252 351 319]
# 0.40 large [259 372 388]
# 0.50 large [266 394 456]
# 0.60 large [272 415 525]
# large beats medium when q > 0.368
The medium plant has the highest EV (330) and is also never loss-making. The large plant has almost the same EV as the small plant (250 against 245) but ten times the standard deviation and a 30% chance of a loss. The sensitivity table varies $P(\text{high})$ while keeping the ratio of low to medium at 3:5. The decision is quite robust: the probability of high demand would have to rise from 0.20 to above 0.368 before the large plant beats the medium one. This is the kind of statement a management team can discuss ("do we really believe high demand is more than 37% likely?") far more productively than a single EV number.
Key takeaways
- $\mathrm{EV}(a_i) = \sum_j p_j v_{ij}$. Choose the maximum. Minimizing expected opportunity loss gives the same choice.
- EV is justified for repeated decisions or risk-neutral decision makers. It ignores the spread of outcomes.
- EV is linear in the probabilities, so break-even probabilities can be computed exactly. Report them along with the decision.
- Do not confuse the expected value of a decision with the decision based on expected data.
Practice
- (Beginner) Compute the expected opportunity loss of each plant from the regret table of the previous topic. Check that the smallest EOL belongs to the alternative with the largest EV, and that EV + EOL is the same for all three.
- (Intermediate) Over a grid of $(P(\text{low}), P(\text{high}))$ with $P(\text{medium}) = 1 - P(\text{low}) - P(\text{high}) \ge 0$, mark which plant maximizes EV and print the result as an ASCII map of the probability triangle. Verify that each region is convex.
- (Interview) "Your analysis shows the large plant has the highest expected profit under the new forecast, but the CFO refuses to approve it. Is the CFO being irrational?" Hint: one-shot decisions, probability and size of losses, financial distress, and what a utility function would say.
Decision Trees
Why it matters. Real decisions are often sequential: act, observe something, act again. Should we run a market survey before choosing the plant size? Should we launch a pilot before the full rollout? A payoff table cannot represent "decide, then learn, then decide". A decision tree can, and it computes the best strategy: what to do now and how to react to each possible observation.
Theory. A decision tree has three kinds of nodes:
| Node | Symbol | Meaning | Rollback rule |
|---|---|---|---|
| Decision | square $\square$ | the decision maker chooses a branch | take the maximum of the branch values |
| Chance | circle $\bigcirc$ | nature chooses a branch with given probabilities | take the expected value of the branch values |
| Terminal | triangle $\triangle$ | end of a scenario | its payoff (net of all costs along the path) |
The tree is drawn left to right in chronological order: a decision node appears only where the decision maker actually chooses, using only information available at that time. It is solved right to left by rollback (also called folding back or averaging out and folding back): replace each chance node by its expected value and each decision node by its best branch, until the root is reached. This is backward induction, the same principle as the backward DP recursion of Chapter 6 and as sequential games (Section 8.2).
When an observation (a survey result, a test outcome) arrives before a decision, the probabilities after the observation are not the prior ones. They are updated with Bayes' rule:
$$ P(s_j \mid z) = \frac{P(z \mid s_j) , P(s_j)}{P(z)}, \qquad P(z) = \sum_k P(z \mid s_k) , P(s_k), $$
where the likelihoods $P(z \mid s_j)$ describe how reliable the observation is. The tree uses $P(z)$ on the branches of the observation node and the posteriors $P(s_j \mid z)$ on the state branches that follow.
Example: should we pay for a market survey? A survey costs 20 and reports "favorable" or "unfavorable". From past experience, it reports favorable with probability 0.2 when demand will be low, 0.6 when medium and 0.9 when high.
low (.3) 200
small ----O--med (.5) 250
/ \-high (.2) 300
no survey ---[ ]-- medium ---O ... (prior probabilities)
/ \
/ large ----O ...
[ ] low (.111) 200 - 20
\ small ----O-- med (.556) 250 - 20
\ / \-high (.333) 300 - 20
survey ---O--fav (.54)--[ ]-- medium ---O ... (posterior | favorable)
\ \
\ large ---O ...
\
unfav (.46)--[ ]-- small / medium / large ...
(posterior | unfavorable)
[ ] decision node O chance node leaves: payoff net of survey cost
The code represents the tree as nested tuples and rolls it back recursively. It records the best branch at every decision node, which is the optimal strategy.
import numpy as np
alts = ["small", "medium", "large"]
P = np.array([[200, 250, 300], [100, 400, 500], [-200, 300, 800]])
prior = np.array([0.3, 0.5, 0.2]) # P(low), P(medium), P(high)
lik = np.array([0.2, 0.6, 0.9]) # P(survey favorable | state)
SURVEY = 20 # survey cost ($k)
# Tree nodes: ("decision", {label: child}), ("chance", [(prob, label, child)]), number = payoff
def build_plant_choice(probs, paid):
return ("decision", {a: ("chance", [(q, s, P[i, j] - paid)
for j, (q, s) in enumerate(zip(probs, ["low", "med", "high"]))])
for i, a in enumerate(alts)})
def rollback(node, path="root", plan=None):
"""Return the expected value of node; record the best choice at each decision node."""
if not isinstance(node, tuple):
return node # terminal payoff
kind, children = node
if kind == "chance": # average over outcomes
return sum(q * rollback(c, f"{path}/{s}", plan) for q, s, c in children)
values = {lbl: rollback(c, f"{path}/{lbl}", plan) for lbl, c in children.items()}
best = max(values, key=values.get) # decision: take the max
plan[path] = (best, values)
return values[best]
# Bayes' rule: probability of each survey result and posterior over states
p_fav = lik @ prior
post_fav = lik * prior / p_fav
post_unfav = (1 - lik) * prior / (1 - p_fav)
print(f"P(favorable) = {p_fav:.2f}")
print("posterior | fav :", np.round(post_fav, 3))
print("posterior | unfav:", np.round(post_unfav, 3))
tree = ("decision", {
"no survey": build_plant_choice(prior, 0),
"survey": ("chance", [(p_fav, "fav", build_plant_choice(post_fav, SURVEY)),
(1 - p_fav, "unfav", build_plant_choice(post_unfav, SURVEY))]),
})
plan = {}
value = rollback(tree, plan=plan)
for path, (best, vals) in sorted(plan.items()):
print(f"{path:22} -> {best:9} " + " ".join(f"{k}={v:.1f}" for k, v in vals.items()))
print(f"value of the tree: {value:.1f}")
# P(favorable) = 0.54
# posterior | fav : [0.111 0.556 0.333]
# posterior | unfav: [0.522 0.435 0.043]
# root -> no survey no survey=330.0 survey=316.0
# root/no survey -> medium small=245.0 medium=330.0 large=250.0
# root/survey/fav -> large small=241.1 medium=380.0 large=391.1
# root/survey/unfav -> medium small=206.1 medium=227.8 large=40.9
# value of the tree: 330.0
After a favorable survey, the posterior probability of high demand rises from 0.2 to 0.333 and the large plant becomes the best choice (391.1). After an unfavorable one, the medium plant remains best. Averaging over the two results, the survey branch is worth $0.54 \times 391.1 + 0.46 \times 227.8 = 316$, net of the survey cost. Building the medium plant immediately is worth 330, so the survey is not worth buying: it is worth $316 + 20 = 336$ before its cost, only 6 more than deciding now, and it costs 20. The next topic turns this comparison into a general tool.
Key takeaways
- Decision trees model sequences of decisions and observations. Decision nodes take the maximum, chance nodes the expected value.
- Draw left to right in chronological order. Solve right to left by rollback (backward induction).
- Observations change probabilities. Use Bayes' rule to compute the probability of each observation and the posterior probabilities of the states.
- The solution is a strategy: a decision for every decision node that can be reached, not a single action.
Practice
- (Beginner) Compute $P(\text{favorable})$ and the three posteriors after an unfavorable survey by hand, and check them against the printed values.
- (Intermediate) Add an "expandable small plant" alternative to the tree: build small now (same payoffs as small), and if demand turns out high, pay 150 to expand and earn 800 instead of 300. Extend the code and find the new optimal strategy with and without the survey.
- (Interview) "How is rolling back a decision tree related to dynamic programming, and when does the tree representation become impractical?" Hint: identical subtrees, states that summarize the history, and how the number of leaves grows with the number of stages.
Value of Perfect Information
Why it matters. Information costs money: surveys, pilots, prototypes, consultants, medical tests. The value of information tells you the most you should pay for it, before you pay. Its central lesson is simple and often ignored: information is worth something only if it could change what you do.
Theory. The expected value with perfect information (EVwPI) assumes a clairvoyant tells you the state before you decide. You would then choose the best alternative in each state, so
$$ \mathrm{EVwPI} = \sum_j p_j \max_i v_{ij}. $$
The expected value of perfect information is the gain over deciding now:
$$ \mathrm{EVPI} = \mathrm{EVwPI} - \max_i \sum_j p_j v_{ij} ;\ge; 0. $$
It equals the smallest expected opportunity loss, $\min_i \mathrm{EOL}(a_i)$: the expected regret of the best decision is exactly what a perfect forecast would remove. No real source of information can be worth more than EVPI, so it is an upper bound on what any survey, test or study is worth.
Real information is imperfect. The expected value of sample information (EVSI) uses the decision tree of the previous topic: for each possible signal $z$, decide optimally with the posterior probabilities, then average over signals.
$$ \mathrm{EVSI} = \sum_z P(z) \max_i \sum_j P(s_j \mid z) , v_{ij} ;-; \max_i \sum_j p_j v_{ij}. $$
Useful derived quantities are the efficiency of the information, $\mathrm{EVSI} / \mathrm{EVPI}$, and the expected net gain, $\mathrm{EVSI} - \text{cost}$. Buy the information only if the net gain is positive.
The same idea reappears in stochastic programming (Section 9.4), where EVPI is the gap between the wait-and-see value and the value of the recourse problem.
Example: what is information about demand worth?
import numpy as np
P = np.array([[200, 250, 300], [100, 400, 500], [-200, 300, 800]])
prior = np.array([0.3, 0.5, 0.2])
ev_no_info = (P @ prior).max() # decide now: best expected payoff
ev_perfect = P.max(axis=0) @ prior # learn the state, then decide
evpi = ev_perfect - ev_no_info
print(f"EV without info = {ev_no_info:.0f}, EV with perfect info = {ev_perfect:.0f}, EVPI = {evpi:.0f}")
R = P.max(axis=0) - P
print("expected regret:", {a: round(float(r)) for a, r in zip(["small", "medium", "large"], R @ prior)}) # min = EVPI
def evsi(lik_matrix):
"""lik_matrix[k, j] = P(signal k | state j). Value of deciding after seeing the signal."""
joint = lik_matrix * prior # P(signal k and state j)
ev_with = sum((P @ row).max() for row in joint) # sum_k P(k) * max_a E[payoff | k]
return ev_with - ev_no_info
# A survey with two results; "accuracy" interpolates between useless and the earlier survey
fav_useless, fav_survey = np.array([0.5, 0.5, 0.5]), np.array([0.2, 0.6, 0.9])
for t in [0.0, 0.5, 1.0]:
fav = (1 - t) * fav_useless + t * fav_survey
v = evsi(np.vstack([fav, 1 - fav]))
print(f"two-result survey, t={t:.1f}: EVSI = {v:5.1f} efficiency = {v / evpi:.0%}")
# A three-result study that names the most likely state correctly 80% of the time
lik3 = np.full((3, 3), 0.1) + np.eye(3) * 0.7 # columns sum to 1
v = evsi(lik3)
print(f"three-result study (80% accurate): EVSI = {v:.1f} efficiency = {v / evpi:.0%}")
# EV without info = 330, EV with perfect info = 420, EVPI = 90
# expected regret: {'small': 175, 'medium': 90, 'large': 170}
# two-result survey, t=0.0: EVSI = 0.0 efficiency = 0%
# two-result survey, t=0.5: EVSI = 0.0 efficiency = 0%
# two-result survey, t=1.0: EVSI = 6.0 efficiency = 7%
# three-result study (80% accurate): EVSI = 46.5 efficiency = 52%
A perfect forecast is worth at most 90: in each state the best plant is chosen (small, medium, large), giving 420 instead of 330. The expected regrets confirm it: the smallest, 90, belongs to the medium plant. The market survey of the previous topic ($t = 1$) is worth only 6, an efficiency of 7%, so paying 20 for it is a mistake. A survey halfway between useless and the real one ($t = 0.5$) is worth exactly zero, even though it is informative: under both of its results the medium plant stays optimal, so knowing the result changes nothing. A study with three outcomes that identifies the correct demand level 80% of the time is worth 46.5, about half of the perfect-information bound, because it can distinguish all three situations and can therefore change the decision in both directions.
Key takeaways
- $\mathrm{EVPI} = \sum_j p_j \max_i v_{ij} - \max_i \mathrm{EV}(a_i)$, which equals the minimum expected opportunity loss. It bounds the value of any information.
- EVSI is the value of imperfect information, computed by deciding optimally for each signal with Bayesian posteriors.
- Information has value only if some signal would change the decision. Informative but irrelevant information is worth zero.
- Buy information only if EVSI exceeds its cost. Efficiency $\mathrm{EVSI} / \mathrm{EVPI}$ compares sources.
Practice
- (Beginner) Recompute EVPI with the probabilities $(0.2, 0.5, 0.3)$. Did the optimal decision without information change? Did EVPI go up or down, and why?
- (Intermediate) For a three-result study whose diagonal likelihood is $r$ and whose off-diagonal likelihoods are $(1 - r) / 2$, tabulate EVSI for $r$ from $1/3$ to $1$. Find the smallest $r$ at which the study is worth its cost of 20, and check that EVSI equals EVPI at $r = 1$.
- (Interview) "A team wants to spend $50k on an A/B test before deciding whether to launch a feature. How would you decide whether the test is worth running?" Hint: start from EVPI as an upper bound, then ask whether any plausible test result would actually change the launch decision.
Utility Theory
Why it matters. Expected value treats a sure $330k and a 50-50 gamble between $0 and $660k as equally good. Very few people or firms see them that way. Utility theory provides a consistent way to include the decision maker's attitude to risk, and it explains insurance, diversification and why a firm's "optimal" project may be one its owners rightly reject.
Theory. Von Neumann and Morgenstern (1944) showed that if a decision maker's preferences among lotteries satisfy four axioms (completeness, transitivity, continuity and independence), then there is a utility function $u$ such that one lottery is preferred to another exactly when it has a higher expected utility:
$$ \mathrm{EU}(a_i) = \sum_j p_j , u(v_{ij}). $$
The shape of $u$ encodes the attitude to risk:
u(x)
| _______ concave (risk averse)
| _.--'
| .-' .' linear (risk neutral)
| .' .'
| .' ..-' convex (risk seeking)
| / __..-'
+-------------------------------- x
| Shape of $u$ | Attitude | Certainty equivalent vs EV |
|---|---|---|
| concave | risk averse | CE < EV |
| linear | risk neutral | CE = EV |
| convex | risk seeking | CE > EV |
The certainty equivalent CE of a lottery is the sure amount with the same utility: $u(\mathrm{CE}) = \mathrm{EU}$. The risk premium $\mathrm{EV} - \mathrm{CE}$ is what the decision maker would give up to remove the risk. Insurance works because a risk-averse customer's risk premium exceeds the insurer's margin.
A widely used family is the exponential utility
$$ u(x) = 1 - e^{-x / R}, \qquad \mathrm{CE} = -R \ln \Big( \sum_j p_j , e^{-v_j / R} \Big), $$
where $R > 0$ is the risk tolerance, measured in money. Small $R$ means strong risk aversion. As $R \to \infty$ the decision maker becomes risk neutral and CE tends to EV. Exponential utility has constant absolute risk aversion: adding the same amount to every outcome does not change preferences, which keeps decision trees easy to roll back (roll back certainty equivalents instead of expected values).
Eliciting a utility function. Two standard techniques are:
- Standard gamble (probability equivalence). Set $u(\text{best}) = 1$ and $u(\text{worst}) = 0$. For an intermediate amount $x$, ask for the probability $p$ at which the decision maker is indifferent between $x$ for sure and a lottery giving the best outcome with probability $p$ and the worst otherwise. Then $u(x) = p$.
- Risk tolerance question. For exponential utility, ask for the largest $G$ such that a 50-50 gamble "win $G$ or lose $G/2$" is still acceptable. Then $R \approx G$.
Real people violate the axioms in systematic ways (the Allais paradox, framing effects). Prospect theory (Kahneman and Tversky, 1979) describes these behaviors, with loss aversion and distorted probability weights. Expected utility remains the normative standard: it describes how one should choose to be consistent, not always how people do choose.
Example: plant choice for different risk tolerances.
import numpy as np
alts = ["small", "medium", "large"]
P = np.array([[200, 250, 300], [100, 400, 500], [-200, 300, 800]])
prior = np.array([0.3, 0.5, 0.2])
def certainty_equivalent(row, R):
"""Exponential utility u(x) = 1 - exp(-x / R), R = risk tolerance ($k).
CE is the sure amount with the same expected utility as the lottery."""
eu = prior @ (1 - np.exp(-row / R))
return -R * np.log(1 - eu), eu
for R in [100, 300, 1000, 1e9]: # R = 1e9 is practically risk neutral
ce = [certainty_equivalent(row, R)[0] for row in P]
best = alts[int(np.argmax(ce))]
cells = " ".join(f"{a}={c:6.1f}" for a, c in zip(alts, ce))
print(f"R={R:>10.0f}: CE {cells} -> {best}")
# Risk premium = EV - CE: what the decision maker would pay to remove the risk
ev = P @ prior
ce = np.array([certainty_equivalent(row, 300)[0] for row in P])
print("risk premium at R=300:", {a: round(float(x), 1) for a, x in zip(alts, ev - ce)})
# Eliciting R with one question: find the largest G such that the 50-50 gamble
# "win G or lose G/2" is still acceptable, i.e. 0.5 u(G) + 0.5 u(-G/2) >= u(0) = 0
def gamble_eu(G, R):
return 0.5 * (1 - np.exp(-G / R)) + 0.5 * (1 - np.exp(G / 2 / R))
lo, hi = 1.0, 1000.0
for _ in range(60): # bisection on G
mid = (lo + hi) / 2
lo, hi = (mid, hi) if gamble_eu(mid, 300) > 0 else (lo, mid)
print(f"R=300: largest acceptable gamble is +{lo:.1f} / -{lo / 2:.1f} (G/R = {lo / 300:.3f})")
# R= 100: CE small= 239.0 medium= 211.3 large= -80.7 -> small
# R= 300: CE small= 243.0 medium= 286.7 large= 73.7 -> medium
# R= 1000: CE small= 244.4 medium= 317.6 large= 190.3 -> medium
# R=1000000000: CE small= 245.0 medium= 330.0 large= 250.0 -> medium
# risk premium at R=300: {'small': 2.0, 'medium': 43.3, 'large': 176.3}
# R=300: largest acceptable gamble is +288.7 / -144.4 (G/R = 0.962)
A very risk-averse owner ($R = 100$) prefers the small plant: its certainty equivalent (239) is almost its EV (245), while the medium plant's CE falls to 211 because of its exposure to low demand. At $R = 300$ and above the medium plant wins, and as $R$ grows all certainty equivalents approach the expected values of the previous topic. The large plant is the clearest case: its EV is 250, but at $R = 300$ its certainty equivalent is only 74, a risk premium of 176. The elicitation step confirms the rule of thumb: with $R = 300$, the largest acceptable gamble "win $G$ or lose $G/2$" is $G = 288.7 \approx 0.96 R$.
Key takeaways
- Under the von Neumann-Morgenstern axioms, rational choice under risk maximizes expected utility.
- Concave utility means risk aversion: the certainty equivalent is below EV, and the difference is the risk premium.
- Exponential utility $u(x) = 1 - e^{-x/R}$ has one parameter, the risk tolerance $R$, which can be elicited with a single 50-50 gamble question.
- Expected utility is normative. Real behavior deviates from it (prospect theory), which is a reason to make the utility function explicit.
Practice
- (Beginner) A manager is indifferent between 300 for sure and a lottery paying 800 with probability 0.7 and -200 otherwise. With $u(800) = 1$ and $u(-200) = 0$, what is $u(300)$? Is the manager risk averse, neutral or seeking?
- (Intermediate) Find, by bisection, the risk tolerance $R$ at which the owner is indifferent between the small and the medium plant. Explain in words what kind of owner prefers each.
- (Interview) "Insurance has a negative expected value for the buyer. Why is buying it rational, and why might a large company choose to self-insure instead?" Hint: concave utility and risk premium, and how risk tolerance $R$ scales with the size of the company.
<a id="73-multi-criteria-decision-making"></a>
7.3 Multi-Criteria Decision Making
Multi-criteria decision making (MCDM, also called multi-criteria decision analysis) deals with a different shape of problem from Section 7.1: instead of a model with continuous decisions, there is a short, explicit list of alternatives (suppliers, sites, projects, candidates) scored on several criteria, some of them qualitative. The methods differ in how they aggregate the scores: AHP and TOPSIS compute one overall value per alternative and allow a strength in one criterion to compensate a weakness in another. ELECTRE and PROMETHEE build "outranking" relations that limit this compensation. DEA measures efficiency without asking anyone for weights.
The first three topics use one supplier-selection problem. Price and lead time are minimized, quality and reliability are maximized:
| Supplier | Price ($/unit) | Quality (score 1-10) | Lead time (days) | Reliability (% on time) |
|---|---|---|---|---|
| A | 25 | 7 | 10 | 92 |
| B | 22 | 6 | 14 | 88 |
| C | 30 | 9 | 8 | 95 |
| D | 27 | 8 | 12 | 90 |
No supplier is dominated: B is the cheapest, C is the best on the three other criteria, and A and D are in between. Choosing requires weighing the criteria.
Analytic Hierarchy Process
Why it matters. Asking a manager "what is the weight of price, as a percentage?" rarely gets a reliable answer. Asking "is price more important than quality, and by how much?" usually does. The Analytic Hierarchy Process (AHP, Saaty, 1970s) turns such pairwise judgments into weights, measures how consistent the judgments are, and combines everything into an overall score. It is one of the most widely used MCDM methods in procurement, public policy and engineering.
Theory. AHP has four steps.
1. Build the hierarchy. The goal is at the top, criteria (and possibly sub-criteria) in the middle, alternatives at the bottom:
Select a supplier
____________/ | | \____________
/ | | \
Price Quality Lead time Reliability
| | | |
A B C D A B C D A B C D A B C D
2. Compare pairwise. For each group of siblings, fill a matrix $A$ in which $a_{ij}$ states how much more important (or better) element $i$ is than element $j$, on Saaty's 1-9 scale:
| $a_{ij}$ | Meaning |
|---|---|
| 1 | equal importance |
| 3 | moderate importance of $i$ over $j$ |
| 5 | strong importance |
| 7 | very strong importance |
| 9 | extreme importance |
| 2, 4, 6, 8 | intermediate values |
The matrix is reciprocal: $a_{ji} = 1 / a_{ij}$ and $a_{ii} = 1$, so only $n(n-1)/2$ judgments are needed.
3. Derive priorities. If the judgments were perfectly consistent, every entry would be a ratio of true weights, $a_{ij} = w_i / w_j$. Then $A w = n w$: the weight vector is an eigenvector of $A$ with eigenvalue $n$. Real judgments are not perfectly consistent, so AHP takes the principal eigenvector (the one belonging to the largest eigenvalue $\lambda_{\max}$), normalized to sum to 1. A simpler approximation is the normalized geometric mean of each row.
4. Check consistency. Since $\lambda_{\max} \ge n$, with equality only for consistent matrices, the deviation measures inconsistency:
$$ \mathrm{CI} = \frac{\lambda_{\max} - n}{n - 1}, \qquad \mathrm{CR} = \frac{\mathrm{CI}}{\mathrm{RI}_n}, $$
where $\mathrm{RI}_n$ is the average CI of random reciprocal matrices of size $n$ (0.58 for $n = 3$, 0.90 for $n = 4$, 1.12 for $n = 5$). The usual rule accepts $\mathrm{CR} < 0.10$. A larger value means the judgments contradict each other (for example $A \succ B$, $B \succ C$ and $C \succ A$) and should be revisited.
5. Synthesize. Each alternative's global priority is the weighted sum of its local priorities: $\text{score}(a) = \sum_c w_c , \ell_c(a)$. For criteria with reliable measurements, the local priorities can be computed from the data instead of pairwise judgments (for example, proportional to the value for a benefit, or to its reciprocal for a cost).
AHP has known criticisms. The 1-9 scale makes "strong importance" mean a ratio of 5, which may not be what the judge intended. The number of comparisons grows quadratically. And in its standard (distributive) form, adding or removing an alternative can reverse the ranking of the others (rank reversal, Belton and Gear, 1983).
Example: weights from judgments, scores from data. Criteria weights and the quality ratings come from pairwise matrices. Price, lead time and reliability use the measured data directly.
import numpy as np
RI = {1: 0.0, 2: 0.0, 3: 0.58, 4: 0.90, 5: 1.12, 6: 1.24, 7: 1.32, 8: 1.41, 9: 1.45}
def ahp_priorities(A):
"""Principal eigenvector of a pairwise comparison matrix + consistency ratio."""
vals, vecs = np.linalg.eig(A)
k = np.argmax(vals.real) # Perron eigenvalue lambda_max >= n
w = np.abs(vecs[:, k].real); w /= w.sum() # normalize weights to sum to 1
n = len(A)
ci = (vals[k].real - n) / (n - 1) # consistency index
cr = ci / RI[n] if RI[n] else 0.0 # consistency ratio (accept if < 0.10)
return w, vals[k].real, cr
# Criteria: price, quality, lead time, reliability (Saaty 1-9 scale, a_ji = 1 / a_ij)
criteria = ["price", "quality", "lead", "reliab"]
C = np.array([[1, 2, 4, 3 ],
[1/2, 1, 3, 2 ],
[1/4, 1/3, 1, 1/2],
[1/3, 1/2, 2, 1 ]])
w, lam, cr = ahp_priorities(C)
print("criteria weights:", dict(zip(criteria, np.round(w, 3).tolist())), f"lambda_max={lam:.3f} CR={cr:.3f}")
# Local priorities of the suppliers A, B, C, D under each criterion
suppliers = ["A", "B", "C", "D"]
Q = np.array([[1, 2, 1/3, 1/2], # quality: judged by pairwise comparison
[1/2, 1, 1/5, 1/3],
[3, 5, 1, 2 ],
[2, 3, 1/2, 1 ]])
q, _, cr_q = ahp_priorities(Q)
price = np.array([25, 22, 30, 27]); lead = np.array([10, 14, 8, 12])
rel = np.array([92, 88, 95, 90])
local = np.column_stack([
(1 / price) / (1 / price).sum(), # measured cost criterion: lower is better
q, # subjective criterion from pairwise matrix
(1 / lead) / (1 / lead).sum(),
rel / rel.sum(), # measured benefit criterion
])
print(f"quality matrix CR={cr_q:.3f}")
score = local @ w # synthesis: weighted sum of local priorities
for s, row, v in sorted(zip(suppliers, local, score), key=lambda t: -t[2]):
print(f"supplier {s}: local={np.round(row, 3)} global={v:.3f}")
# Flip one judgment: reliability now 3x as important as price, although price
# beats quality (2) and quality beats reliability (2). The cycle breaks consistency.
C_bad = C.copy(); C_bad[0, 3], C_bad[3, 0] = 1/3, 3
print(f"inconsistent matrix: CR={ahp_priorities(C_bad)[2]:.3f}")
# criteria weights: {'price': 0.467, 'quality': 0.277, 'lead': 0.095, 'reliab': 0.16} lambda_max=4.031 CR=0.011
# quality matrix CR=0.005
# supplier C: local=[0.214 0.483 0.329 0.26 ] global=0.307
# supplier D: local=[0.238 0.272 0.219 0.247] global=0.247
# supplier A: local=[0.257 0.157 0.263 0.252] global=0.229
# supplier B: local=[0.292 0.088 0.188 0.241] global=0.217
# inconsistent matrix: CR=0.244
The criteria matrix is very consistent ($\mathrm{CR} = 0.011$) and gives price almost half of the total weight. The quality comparisons ("C is strongly better than B", value 5) give C a quality priority of 0.483 against B's 0.088, and this large gap makes C the winner despite its price. Flipping a single judgment so that the criteria form a cycle raises the CR to 0.244, well above the 0.10 threshold: AHP detects that the judge has contradicted themselves.
Key takeaways
- AHP builds a hierarchy (goal, criteria, alternatives) and derives priorities from reciprocal pairwise comparison matrices on a 1-9 scale.
- Priorities are the normalized principal eigenvector. The consistency ratio $\mathrm{CR} = \mathrm{CI} / \mathrm{RI}$ should be below 0.10.
- The global score is the weighted sum of local priorities. Measured criteria can use normalized data instead of judgments.
- Beware of the meaning of the 1-9 scale and of rank reversal when alternatives are added or removed.
Practice
- (Beginner) Approximate the criteria weights with the normalized geometric mean of each row of
Cand compare them with the eigenvector weights.- (Intermediate) Add a fifth supplier E identical to D (in data and in quality judgments) and recompute the global priorities. Does the ranking of A to D change? Relate the result to rank reversal.
- (Interview) "One stakeholder's pairwise comparisons have CR = 0.25. What do you do?" Hint: find the triple $(i, j, k)$ where $a_{ij}$ differs most from $a_{ik} a_{kj}$, show it to the stakeholder and let them revise it, rather than editing the numbers yourself.
TOPSIS
Why it matters. TOPSIS (Technique for Order of Preference by Similarity to Ideal Solution, Hwang and Yoon, 1981) is simple, works directly on the data table and has an intuitive geometric meaning: the best alternative is the one closest to an ideal alternative and farthest from the worst possible one. It needs only weights and the direction of each criterion, which makes it a popular default.
Theory. Given a decision matrix $X$ ($m$ alternatives, $n$ criteria) and weights $w$:
- Normalize each column so that criteria in different units can be compared. TOPSIS uses vector normalization: $r_{ij} = x_{ij} / \sqrt{\sum_k x_{kj}^2}$.
- Weight: $v_{ij} = w_j , r_{ij}$.
- Ideal and anti-ideal: $A^+_j$ is the best value of column $j$ (the maximum for a benefit criterion, the minimum for a cost criterion) and $A^-_j$ is the worst. These are the ideal and nadir points of Section 7.1, restricted to the list of alternatives.
- Distances: $D_i^+ = \lVert v_i - A^+ \rVert_2$ and $D_i^- = \lVert v_i - A^- \rVert_2$.
- Relative closeness: $C_i = D_i^- / (D_i^+ + D_i^-) \in [0, 1]$. Rank by decreasing $C_i$.
criterion 2 (weighted, normalized)
^
| A+ = ideal *
| . \
| D+ . \
| . x alternative i C_i = D- / (D+ + D-)
| . close to A+ and far from A- -> C_i near 1
| D- .
| .
| * A- = anti-ideal
+------------------------------------------> criterion 1
Using both distances matters: an alternative can be close to the ideal and also close to the anti-ideal when the criteria disagree. TOPSIS is compensatory: a very good score on one criterion can make up for a very bad one on another. Because the normalization and the ideal points depend on the set of alternatives, TOPSIS also suffers from rank reversal.
Example: TOPSIS with the AHP weights.
import numpy as np
suppliers = ["A", "B", "C", "D"]
# price quality lead reliability
X = np.array([[25, 7, 10, 92],
[22, 6, 14, 88],
[30, 9, 8, 95],
[27, 8, 12, 90]], dtype=float)
w = np.array([0.467, 0.277, 0.095, 0.160]) # weights from the AHP example
benefit = np.array([False, True, False, True]) # price and lead time are costs
def topsis(X, w, benefit):
R = X / np.sqrt((X ** 2).sum(axis=0)) # 1) vector normalization per column
V = R * w # 2) apply weights
ideal = np.where(benefit, V.max(axis=0), V.min(axis=0)) # 3) best value per criterion
anti = np.where(benefit, V.min(axis=0), V.max(axis=0)) # worst value per criterion
d_pos = np.sqrt(((V - ideal) ** 2).sum(axis=1)) # 4) Euclidean distances
d_neg = np.sqrt(((V - anti) ** 2).sum(axis=1))
return d_neg / (d_pos + d_neg), d_pos, d_neg # 5) relative closeness in [0, 1]
cc, dp, dn = topsis(X, w, benefit)
for i in np.argsort(-cc):
print(f"supplier {suppliers[i]}: D+={dp[i]:.4f} D-={dn[i]:.4f} closeness={cc[i]:.3f}")
# Rank reversal: add a poor supplier E and recompute (normalization changes)
X2 = np.vstack([X, [21, 3, 20, 80]])
cc2, _, _ = topsis(X2, w, benefit)
print("with E added:", " > ".join(f"{s}({c:.3f})" for s, c in
sorted(zip(suppliers + ["E"], cc2), key=lambda t: -t[1])))
# supplier B: D+=0.0607 D-=0.0714 closeness=0.540
# supplier A: D+=0.0462 D-=0.0512 closeness=0.526
# supplier D: D+=0.0513 D-=0.0461 closeness=0.473
# supplier C: D+=0.0714 D-=0.0607 closeness=0.460
# with E added: A(0.644) > D(0.640) > C(0.606) > B(0.602) > E(0.394)
With the same weights, TOPSIS ranks B first and C last, the opposite of AHP. The reason lies in the inputs, not in an error. AHP's quality judgments turned scores of 9 and 6 (a ratio of 1.5) into priorities of 0.483 and 0.088 (a ratio of 5.5). TOPSIS uses the raw scores, so quality differences are much smaller, and price, with almost half of the weight, decides. The two methods encode different beliefs about how much "9 versus 6" matters. Adding a fifth supplier E, which is cheaper than B but poor on every other criterion, makes B no longer the ideal on price and reshuffles the ranking of the original four to A > D > C > B. A ranking that changes this easily should be reported with a sensitivity analysis, not as a single verdict.
Key takeaways
- TOPSIS normalizes and weights the decision matrix, then ranks alternatives by their relative closeness $D^- / (D^+ + D^-)$ to the ideal.
- It is compensatory and uses the data directly. Results depend on normalization, weights and the set of alternatives.
- Different MCDM methods can rank the same alternatives differently because they interpret scores differently. Compare methods and test sensitivity before deciding.
Practice
- (Beginner) By hand, compute the vector-normalized and weighted price value of supplier A, and the price coordinates of $A^+$ and $A^-$.
- (Intermediate) Replace the quality column by the AHP local quality priorities (0.157, 0.088, 0.483, 0.272) and rerun TOPSIS. Does the ranking now agree with AHP? What does this say about where the disagreement came from?
- (Interview) "A TOPSIS ranking of vendors changed after a weak new vendor was added to the shortlist. Explain to the procurement team what happened and how to prevent it." Hint: the normalization and the ideal points depend on the set of alternatives. Consider fixed reference values for the ideal and anti-ideal points.
ELECTRE and PROMETHEE Methods
Why it matters. In compensatory methods, an excellent price can cancel a catastrophic delivery record. Many decision makers do not accept that, especially in public decisions with environmental or safety limits. Outranking methods, developed in the "European school" of decision aid (Bernard Roy for ELECTRE in the late 1960s, Jean-Pierre Brans for PROMETHEE in the 1980s), compare alternatives pair by pair, limit compensation, allow vetoes, and admit that two alternatives can be incomparable rather than forcing a complete ranking.
Theory. Both families build an outranking relation: "$a$ outranks $b$" ($a , S , b$) means there are enough arguments to say that $a$ is at least as good as $b$, and no strong argument against it.
ELECTRE I (selection) uses two indices for each ordered pair:
- Concordance: the total weight of the criteria on which $a$ is at least as good as $b$, $C(a, b) = \sum_{j : g_j(a) \succeq g_j(b)} w_j$.
- Discordance: the worst disadvantage of $a$ against $b$, normalized by the range of each criterion, $D(a, b) = \max_j \big( g_j(b) - g_j(a) \big)^+ / \text{range}_j$ (for benefit criteria. Signs flip for cost criteria).
Then $a , S , b$ if $C(a, b) \ge \hat c$ (a large enough majority agrees) and $D(a, b) \le \hat d$ (no single criterion vetoes it). The alternatives that no other alternative outranks form the kernel: the short list for the final choice. Later versions handle ranking (ELECTRE II and III, with indifference, preference and veto thresholds) and sorting into ordered categories (ELECTRE TRI).
PROMETHEE turns each pairwise difference into a degree of preference. For each criterion $j$ a preference function $P_j(d) \in [0, 1]$ maps the advantage $d = g_j(a) - g_j(b)$ to a strength of preference. The common linear form uses an indifference threshold $q$ and a preference threshold $p$:
P(d)
1 | ________________
| /
| /
| /
0 |____________/
+-----------+------+---------------> d = g(a) - g(b)
q p
no preference linear full preference
The aggregated preference of $a$ over $b$ is $\pi(a, b) = \sum_j w_j P_j(d_j)$. Summing over all other alternatives gives the flows:
$$ \phi^+(a) = \frac{1}{m - 1} \sum_{b \ne a} \pi(a, b), \qquad \phi^-(a) = \frac{1}{m - 1} \sum_{b \ne a} \pi(b, a), \qquad \phi(a) = \phi^+(a) - \phi^-(a). $$
The positive flow $\phi^+$ measures how strongly $a$ outranks the others, and the negative flow $\phi^-$ how strongly it is outranked. PROMETHEE I ranks $a$ above $b$ only when both flows agree (a partial order with incomparabilities). PROMETHEE II ranks by the net flow $\phi$ (a complete order).
| ELECTRE I | PROMETHEE II | |
|---|---|---|
| Output | kernel (short list) | complete ranking by net flow |
| Compensation | limited by the discordance veto | partial, through bounded preference functions |
| Parameters | weights, concordance and discordance thresholds | weights, preference function and thresholds per criterion |
| Incomparability | yes | no (PROMETHEE I: yes) |
| Strength | vetoes, honesty about incomparability | intuitive thresholds, visual tools (GAIA plane) |
Example: outranking the four suppliers. The thresholds are expressed in the units of each criterion. For price, for example, a difference up to $1 is ignored, and $6 or more counts as full preference.
import numpy as np
suppliers = ["A", "B", "C", "D"]
X = np.array([[25, 7, 10, 92], # price, quality, lead, reliability
[22, 6, 14, 88],
[30, 9, 8, 95],
[27, 8, 12, 90]], dtype=float)
w = np.array([0.467, 0.277, 0.095, 0.160])
sign = np.array([-1, 1, -1, 1]) # -1 = minimize (cost criterion)
q = np.array([1.0, 0.5, 1.0, 1.0]) # indifference thresholds
p = np.array([6.0, 2.0, 5.0, 5.0]) # preference thresholds
n = len(X)
# ---------- PROMETHEE II ----------
# Linear preference function: 0 below q, 1 above p, linear in between
def pref(d):
return np.clip((d - q) / (p - q), 0, 1)
Pi = np.zeros((n, n)) # aggregated preference of a over b
for a in range(n):
for b in range(n):
if a != b:
d = sign * (X[a] - X[b]) # advantage of a over b, per criterion
Pi[a, b] = w @ pref(d)
phi_plus = Pi.sum(axis=1) / (n - 1) # how much a outranks the others
phi_minus = Pi.sum(axis=0) / (n - 1) # how much the others outrank a
phi = phi_plus - phi_minus # net flow (PROMETHEE II)
print("PROMETHEE II:")
for i in np.argsort(-phi):
print(f" {suppliers[i]}: phi+={phi_plus[i]:.3f} phi-={phi_minus[i]:.3f} net={phi[i]:+.3f}")
# ---------- ELECTRE I ----------
c_hat, d_hat = 0.65, 0.5 # concordance and veto (discordance) levels
span = X.max(axis=0) - X.min(axis=0)
Cm, Dm = np.zeros((n, n)), np.zeros((n, n))
for a in range(n):
for b in range(n):
if a == b: continue
d = sign * (X[a] - X[b])
Cm[a, b] = w[d >= 0].sum() # weight of criteria where a >= b
Dm[a, b] = max(0, (-d / span).max()) # worst normalized loss of a vs b
S = (Cm >= c_hat) & (Dm <= d_hat) # S[a, b]: "a outranks b"
np.fill_diagonal(S, False)
print("ELECTRE I concordance:\n", np.round(Cm, 2))
print("discordance:\n", np.round(Dm, 2))
print("outranking pairs:", [f"{suppliers[a]} S {suppliers[b]}" for a, b in zip(*np.nonzero(S))])
kernel = [suppliers[a] for a in range(n) if not S[:, a].any()] # not outranked by anyone
print("kernel (not outranked):", kernel)
# PROMETHEE II:
# C: phi+=0.412 phi-=0.342 net=+0.070
# A: phi+=0.271 phi-=0.220 net=+0.051
# B: phi+=0.342 phi-=0.385 net=-0.043
# D: phi+=0.207 phi-=0.285 net=-0.078
# ELECTRE I concordance:
# [[0. 0.53 0.47 0.72]
# [0.47 0. 0.47 0.47]
# [0.53 0.53 0. 0.53]
# [0.28 0.53 0.47 0. ]]
# discordance:
# [[0. 0.38 0.67 0.33]
# [0.67 0. 1. 0.67]
# [0.62 1. 0. 0.38]
# [0.33 0.62 0.71 0. ]]
# outranking pairs: ['A S D']
# kernel (not outranked): ['A', 'B', 'C']
PROMETHEE II ranks C first, followed by A, B and D, with C and A close. Because the preference functions saturate at the preference threshold, B's price advantage over C ($8) counts no more than a $6 advantage would, so it can no longer dominate the comparison as it did in TOPSIS. ELECTRE I is more cautious: the only outranking it accepts is A over D, so the kernel contains A, B and C. B and C, for example, do not outrank each other because each beats the other by the full range of some criterion: the discordance is 1.0 in both directions (C's lead time, quality and reliability against B, B's price against C). The method's message is that the data and the chosen thresholds do not justify a single winner among the three. In a real study, that is a prompt to collect more information or ask the decision maker sharper questions.
Key takeaways
- Outranking methods compare alternatives pairwise and build a relation "$a$ is at least as good as $b$" instead of a single score.
- ELECTRE uses concordance (weighted majority) and discordance (veto). Its kernel is a short list of non-outranked alternatives, and incomparability is allowed.
- PROMETHEE uses preference functions with thresholds and ranks by positive, negative and net flows.
- These methods limit compensation, which suits decisions where a severe weakness should not be bought off by strengths elsewhere.
Practice
- (Beginner) By hand, compute $\pi(C, B)$ from the linear preference functions, weights and thresholds in the code. Which criteria contribute?
- (Intermediate) Lower the concordance threshold to 0.5 and raise the discordance threshold to 0.7. List the new outranking pairs, check whether the relation contains a cycle, and recompute the kernel.
- (Interview) "For choosing the site of a waste treatment plant, why might an outranking method be preferred over a weighted-sum score?" Hint: non-compensation (a cheap site next to a school), vetoes as legal or environmental limits, transparency to stakeholders, and accepting incomparability.
Data Envelopment Analysis
Why it matters. A bank wants to compare its branches, a ministry its hospitals, a utility its regional depots. Each unit uses several inputs (staff, budget, floor space) to produce several outputs (transactions, patients treated, loans issued), and there are no agreed prices to combine them. Data Envelopment Analysis (DEA, Charnes, Cooper and Rhodes, 1978) measures each unit's relative efficiency with linear programming, without asking anyone for weights, and tells inefficient units which efficient peers to learn from.
Theory. There are $n$ decision-making units (DMUs). Unit $j$ uses inputs $x_j \in \mathbb{R}^m$ and produces outputs $y_j \in \mathbb{R}^s$. With weights $v$ for inputs and $u$ for outputs, its efficiency would be the ratio $u^\top y_j / v^\top x_j$. DEA lets each unit choose the weights that make it look as good as possible, under the condition that no unit scores above 1 with those weights:
$$ \max_{u, v \ge 0} ; \frac{u^\top y_o}{v^\top x_o} \qquad \text{s.t.} \quad \frac{u^\top y_j}{v^\top x_j} \le 1 \quad \forall j. $$
A unit that scores below 1 even with its own best weights is inefficient by any standard. The Charnes-Cooper transformation (fix $v^\top x_o = 1$) turns this fractional program into an LP, the multiplier form of the CCR model:
$$ \max ; u^\top y_o \qquad \text{s.t.} \quad v^\top x_o = 1, \quad u^\top y_j - v^\top x_j \le 0 ;; \forall j, \quad u, v \ge 0. $$
Its LP dual (Section 2.4) is the envelopment form, which has a direct operational meaning:
$$ \min_{\theta, \lambda \ge 0} ; \theta \qquad \text{s.t.} \quad \sum_j \lambda_j x_j \le \theta , x_o, \qquad \sum_j \lambda_j y_j \ge y_o. $$
Read it as: build a composite unit as a nonnegative combination of real units that produces at least the outputs of unit $o$ using at most the fraction $\theta$ of its inputs. The optimal $\theta^* \in (0, 1]$ is the efficiency score. The units with $\lambda_j > 0$ are the peers (reference set) of unit $o$, and $\sum_j \lambda_j x_j$ gives its input targets. A unit is fully efficient when $\theta^* = 1$ and all slacks are zero: this is Pareto efficiency (Section 7.1) in the space of inputs and outputs.
input 2 per unit of output
^
| *P1 Illustration with one output and two inputs.
| \ Efficient units P1, P2, P3 form the frontier.
| \ o U Unit U is inefficient: shrinking both of its
| *P2 / inputs in proportion (toward the origin) reaches
| \ / the frontier at T, so theta = |0T| / |0U|.
| \ T T is a mix of P2 and P3: they are U's peers.
| *-------*P3---------
| /
| /
+----------------------------------> input 1 per unit of output
0
Main variants:
| Model | Returns to scale | Extra constraint | Use |
|---|---|---|---|
| CCR | constant | none | units of similar size, or overall efficiency |
| BCC | variable | $\sum_j \lambda_j = 1$ | units of very different size. Separates pure technical efficiency from scale |
| Input-oriented | how much can inputs shrink at the same outputs | ||
| Output-oriented | how much can outputs grow with the same inputs |
DEA's strengths (no weights, no functional form, actionable peers) come with limitations. The frontier is defined by the best observed units, so measurement errors and outliers directly shift it. With few units and many inputs and outputs, too many units look efficient. A common rule of thumb asks for at least $\max(m \cdot s, ; 3(m + s))$ units. Efficiency is relative to the sample and says nothing about quality not captured in the outputs.
Example: six bank branches. Inputs are staff (FTE) and operating cost ($k). Outputs are transactions (thousands) and new loans. The code solves the envelopment LP once per branch.
import numpy as np
from scipy.optimize import linprog
branches = ["B1", "B2", "B3", "B4", "B5", "B6"]
X = np.array([[ 8, 300], [10, 380], [ 6, 260], # inputs: staff (FTE), operating cost ($k)
[12, 420], [ 9, 400], [ 7, 250]], dtype=float)
Y = np.array([[50, 120], [60, 110], [45, 70], # outputs: transactions (k), new loans
[70, 160], [40, 90], [48, 100]], dtype=float)
n, m, s = len(X), X.shape[1], Y.shape[1]
def ccr_input(o):
"""Envelopment form, input orientation, constant returns to scale:
min theta s.t. sum_j lam_j x_j <= theta x_o, sum_j lam_j y_j >= y_o, lam >= 0."""
c = np.r_[1, np.zeros(n)] # variables: [theta, lam_1..lam_n]
A_in = np.c_[-X[o], X.T] # sum lam x - theta x_o <= 0
A_out = np.c_[np.zeros(s), -Y.T] # -sum lam y <= -y_o
r = linprog(c, A_ub=np.r_[A_in, A_out], b_ub=np.r_[np.zeros(m), -Y[o]],
bounds=[(0, None)] * (n + 1), method="highs")
return r.x[0], r.x[1:]
print("branch theta peers (lambda) target inputs")
for o in range(n):
theta, lam = ccr_input(o)
peers = ", ".join(f"{branches[j]}({lam[j]:.2f})" for j in range(n) if lam[j] > 1e-6)
target = lam @ X # composite branch built from peers
print(f"{branches[o]:6} {theta:6.3f} {peers:30} staff={target[0]:5.2f} cost={target[1]:6.1f}")
# branch theta peers (lambda) target inputs
# B1 1.000 B1(1.00) staff= 8.00 cost= 300.0
# B2 0.851 B3(0.43), B6(0.85) staff= 8.51 cost= 323.4
# B3 1.000 B3(1.00) staff= 6.00 cost= 260.0
# B4 0.952 B1(0.89), B6(0.53) staff=10.84 cost= 400.0
# B5 0.681 B1(0.42), B6(0.39) staff= 6.13 cost= 225.0
# B6 1.000 B6(1.00) staff= 7.00 cost= 250.0
Branches B1, B3 and B6 define the frontier. B2 scores 0.851: a combination of B3 and B6 produces at least B2's outputs using 85.1% of its staff and cost. B5 is the least efficient branch (0.681), with peers B1 and B6, and its targets (about 6.1 staff and $225k) show what an efficient branch with its output mix would use. B4's targets reduce cost exactly by the radial factor ($0.952 \times 420 = 400$) but reduce staff further, to 10.84 instead of $0.952 \times 12 = 11.4$: the difference is a slack, an extra inefficiency in one input that the radial score alone does not reveal. Note that this example has only six units for four inputs and outputs, below the rule of thumb (12), so half of the branches being efficient should be read with caution.
Key takeaways
- DEA measures the relative efficiency of comparable units with multiple inputs and outputs, letting each unit choose its most favorable weights.
- The CCR envelopment LP finds the smallest $\theta$ such that a combination of peers produces at least the unit's outputs with $\theta$ times its inputs.
- Peers ($\lambda_j > 0$) and targets ($\sum_j \lambda_j x_j$) make the results actionable. Check slacks in addition to $\theta$.
- Use BCC ($\sum \lambda_j = 1$) for units of different sizes. Beware of outliers and of too few units for the number of inputs and outputs.
Practice
- (Beginner) Using B5's peers and $\lambda$ values, compute the outputs of its composite unit and check that they are at least B5's outputs (the printed $\lambda$ values are rounded, so allow for small differences).
- (Intermediate) Add the constraint $\sum_j \lambda_j = 1$ to obtain the input-oriented BCC model. Compare the scores with CCR and explain why a BCC score can never be lower than the CCR score.
- (Interview) "A hospital group wants to use DEA to rank its hospitals and cut the budgets of the inefficient ones. What concerns would you raise?" Hint: the choice of inputs and outputs, differences in case mix and patient severity, noise and outliers on the frontier, the number of units, and the difference between efficiency and quality of care.
<a id="8-game-theory"></a>