Technical Summary: The Value of Human Expertise

Problem Statement

This paper addresses a class of optimization problems under uncertainty where a decision maker possesses an uncertainty set of parameters derived from data, but also holds a "human belief" that the optimal value of the nominal problem (the problem solvable if true parameters were known) is unlikely to be large. This belief stems from domain knowledge or private information not captured in datasets, such as a store manager's intuition about local consumer preferences.

The core challenge is that traditional robust optimization, which seeks a policy performing best under the worst-case parameters in the uncertainty set, often yields overly conservative solutions. Conversely, standard inverse optimization or Bayesian approaches typically require precise numerical bounds or specific parametric assumptions that are difficult to elicit from human experts. The paper seeks to formalize how to incorporate these vague, subjective beliefs—specifically the belief that the nominal optimal value is bounded above—into the optimization process to improve performance guarantees without sacrificing robustness if the belief is incorrect.

Methodology

The Nominal Curve

The author proposes a new framework for evaluating policies called the nominal curve. Instead of providing a single worst-case performance guarantee, a policy is evaluated by a curve defined as:
$$\left\{ \left( \eta, \min_{\theta \in U_\eta} f(x, \theta) \right) : \eta \geq \bar{\eta} \right\}$$
where:

• $x$ is a policy.
• $f(x, \theta)$ is the objective function with unknown parameter $\theta$.
• $U$ is the original uncertainty set.
• $U_\eta = \{ \theta \in U : \max_{x' \in X} f(x', \theta) \leq \eta \}$ is a reduced uncertainty set that excludes any parameters which would result in a nominal optimal value exceeding $\eta$.
• $\bar{\eta}$ is the smallest $\eta$ for which $U_\eta$ is non-empty.

The nominal curve provides a worst-case performance guarantee for a policy under every possible upper bound $\eta$ on the nominal optimal value. If the decision maker's belief that the nominal optimal value is small (i.e., $\leq \eta$) is correct, the curve provides a less conservative guarantee than standard robust optimization. If the belief is incorrect (the true optimal value is large), the curve reverts to the standard worst-case guarantee (since $U_\eta$ eventually equals $U$ for large $\eta$).

The Value of Human Expertise

To quantify the benefit of this approach, the paper introduces the value of human expertise ($\Delta$), defined as the maximum improvement in the optimal value of a robust optimization problem achievable by incorporating the belief:
$$\Delta = \max_{\eta \geq \bar{\eta}} \left( \max_{x \in X} \min_{\theta \in U_\eta} f(x, \theta) \right) - \max_{x \in X} \min_{\theta \in U} f(x, \theta)$$

Theoretical Characterization

The paper establishes a fundamental connection between the value of human expertise and the minimax gap.

• Assumption 1: $X$ and $U$ are compact, non-empty; $f$ is bounded, upper semicontinuous in $x$, and lower semicontinuous in $\theta$.
• Assumption 2: $U$ is convex, and $\theta \mapsto f(x, \theta)$ is convex for all $x$.

Main Result (Corollary 2): Under Assumptions 1 and 2, the value of human expertise is exactly equal to the gap between the optimal values of the min-max and max-min formulations:
$$\Delta = \min_{\theta \in U} \max_{x \in X} f(x, \theta) - \max_{x \in X} \min_{\theta \in U} f(x, \theta)$$
This result implies that human expertise is valuable precisely in settings where minimax duality does not hold (i.e., where pure strategies are suboptimal compared to mixed strategies). The proof relies on a novel theorem (Theorem 1) regarding max-min problems with convex inner functions, showing that a pure strategy can achieve the min-max value if the uncertainty set is constrained by the optimal value of the min-max problem.

Computational Approaches

The paper proposes methods to generate a "menu" of policies (pointwise optimal policies) to allow decision makers to select based on their confidence in their beliefs:

1. Exact Reformulation: For specific classes of problems (e.g., zero-one network flow, cardinality-constrained assortment optimization under MNL with polyhedral uncertainty), the reduced robust optimization problem can be reformulated as a compact Mixed-Integer Linear Program (MILP) using strong duality.
2. Cutting Plane Method: A two-level cutting plane algorithm is proposed for general settings where exact reformulation is not feasible. This method iteratively approximates the reduced uncertainty set and the policy space.
3. Alternative Approaches: The paper also suggests "globalized robust optimization" formulations and constrained optimization approaches to generate policies that balance performance guarantees with the risk of incorrect beliefs.

Key Results and Applications

Assortment Optimization

In a hyperlocal revenue management setting, the author demonstrates that data-driven uncertainty sets (based on random utility maximization models consistent with historical sales) can contain models implying that a store's past assortments were highly suboptimal.

• Finding: Standard robust optimization fails to find a new assortment guaranteed to outperform the best past assortment.
• Result: By applying nominal curves, the author identifies a new assortment that, in the worst case, performs only slightly worse than the past best, but is guaranteed to strictly outperform it if the past assortment was within a reasonable percentage (e.g., 20-30%) of the true optimum. This illustrates how "loose" beliefs can induce a phase transition from overly conservative to practically useful solutions.

Combinatorial Optimization (Shortest Path)

The paper analyzes combinatorial problems (e.g., shortest path, bipartite matching) with budget uncertainty sets.

• Finding: Theoretical conditions are established under which the value of human expertise is strictly positive. Specifically, if the optimal solution to the robust problem is structurally different from the non-robust (nominal) solution, beliefs about the nominal optimal value can significantly tighten performance guarantees.
• Numerical Experiments: Experiments on randomly generated shortest path problems show that in 19 out of 20 instances, there is a strictly positive value of human expertise, with the gap between robust and reduced robust optimal values averaging a ratio of 1.389.

Significance and Claims

The paper claims to offer a rigorous framework for integrating human expertise into algorithm-driven decision-making without requiring precise numerical bounds or parametric assumptions. Its significance lies in:

1. Bridging Robust and Inverse Optimization: It occupies a middle ground, utilizing partial information about the nominal problem's optimal value (too crude for inverse optimization to recover parameters) to improve robust optimization outcomes.
2. Quantifying Expertise: It provides a precise mathematical characterization of the "value of human expertise" as the minimax gap, linking it to the failure of minimax duality in pure strategies.
3. Practical Utility: It demonstrates that even vague beliefs (e.g., "the past policy wasn't terrible") can be transformed into actionable, less conservative policies with rigorous worst-case guarantees that hold even if the belief is wrong.
4. Novel Theoretical Contribution: The paper introduces a new theorem on max-min problems (Theorem 1) that extends minimax theory to settings where standard conditions (like convexity of the outer set or quasi-concavity) are not met, showing that constraining the uncertainty set by the min-max value allows pure strategies to achieve mixed-strategy performance.

The author concludes that this approach is particularly relevant for high-stakes applications where decision makers are risk-averse and randomized policies are undesirable, offering a way to leverage domain intuition to escape the conservatism of traditional robust optimization.