PaperlayerView exact revision on arXiv

Source-linked AI summary

The Value of Human Expertise

Bradley Sturt

arXiv:2608.26051v1math.OCcs.AI

TL;DR

The paper studies optimization with unknown parameters when human knowledge suggests that the nominal optimum is unlikely to be large. It proposes nominal curves to evaluate policies under this belief, and shows that under convex worst-case evaluation, the value of human expertise equals a minimax gap.

  • Problem

    The paper addresses how to use human beliefs that the nominal optimum is unlikely to be large when datasets alone do not determine reliable decisions.

  • Method

    It evaluates policies with nominal curves and defines the value of human expertise through robust optimization problems incorporating bounds on the nominal optimal value.

  • Results

    The value of human expertise equals the gap between min-max and max-min robust formulations when worst-case policy evaluation is convex, with substantial gaps illustrated in assortment optimization and shortest path problems.

  • Takeaways & Limitations

    Human beliefs about the nominal problem can yield improved worst-case performance guarantees in applications where minimax duality does not hold.

  • Takeaways & Limitations

    The assumptions used for the simple bounds do not by themselves guarantee minimax theorems or saddle points, and empirical testing remains future work.

Abstract

from arXiv · show

We consider optimization applications with unknown parameters where the decision maker believes that the optimal value of the nominal problem-the optimization problem they would have solved if the true parameters were known-is unlikely to be large. This belief derives from information that humans have that is not captured in datasets, obtained from domain knowledge and interacting with the physical world. We propose an approach to evaluating policies that provides tighter performance guarantees if the decision maker's belief happens to be correct. Our main result shows that if computing a policy's worst-case performance is a convex program, then the value of human expertise-the maximum improvement in performance guarantees that can be obtained from the belief about the nominal problem-is equal to the minimax gap of a max-min problem. We illustrate our developments in assortment optimization and shortest path problems.

1 Introduction

The paper studies optimization problems where human knowledge suggests the nominal optimum is unlikely to be large, despite limited or incomplete data. It introduces nominal curves and characterizes when such beliefs improve robust performance guarantees.

  • Motivation: Limited historical assortments can prevent accurate store-specific choice modeling, while managers’ private customer knowledge provides information absent from transactional datasets.This motivates hyperlocal assortment optimization as a representative application.
  • Motivation: Optimization with human expertise uses domain knowledge and physical-world interactions to inform beliefs about unknown-parameter optimization problems.The belief concerns the optimal value of the nominal problem, which is the problem solved if the true parameters were known.
  • Approach: Nominal curves provide policy-specific worst-case guarantees across possible upper bounds on the nominal optimum, allowing decision makers to use subjective beliefs without fixing one numerical bound.They also retain guarantees when the belief about the nominal problem is incorrect.
  • Theory: The value of human expertise measures the maximum improvement in robust guarantees obtained by excluding parameters associated with large nominal optimal values.It is equivalently represented through differences involving the upper bound curve.
  • Theory: If worst-case policy evaluation is convex, the value of human expertise equals the gap between the min-max and max-min robust formulations.The result applies to infinite-dimensional policy and parameter spaces and identifies minimax duality as the relevant boundary.
  • Applications: The paper illustrates the framework in hyperlocal assortment optimization and provides numerical evidence that data-consistent uncertainty sets can support improved guarantees.The examples also include shortest path problems.

2 Optimization with Human Expertise

The framework combines a data-derived uncertainty set with a belief that the nominal optimum is unlikely to be large. It evaluates policies through nominal curves whose structure supports robust, belief-sensitive comparisons.

  • Model: The model uses feasible policies, an unknown objective parameter, and a compact uncertainty set summarizing dataset information about the true parameter.The feasible policy and parameter spaces may be infinite-dimensional.
  • Model: The decision maker seeks policies that perform well throughout the uncertainty set and better when the nominal problem’s optimal value is small.The belief comes from domain knowledge and interactions with the physical world rather than datasets alone.
  • Nominal curves: For each threshold η, the reduced uncertainty set removes parameters whose nominal problem would have an optimal value above η.The nominal curve evaluates a policy’s worst-case performance over these reduced sets.
  • Nominal curves: Nominal curves provide usual worst-case guarantees for sufficiently large η and potentially less pessimistic guarantees when the true nominal optimum is at most η.They let decision makers assess several plausible scenarios instead of converting a subjective belief into one precise bound.
  • Policy selection: Policies can be generated by solving reduced robust optimization problems for different η values and comparing the resulting nominal curves.Because no policy need be universally optimal across all η, the approach offers a menu of policies for judgment-based selection.
  • Nominal curves: Nominal curves are nonincreasing, convex, and continuous under the stated assumptions.For fixed policies, these properties make the curves easier to visualize and interpret.
  • Value of human expertise: The value of human expertise is the maximum improvement in robust performance from eliminating parameters associated with large nominal optimal values.A zero value means nominal curves cannot improve on ordinary robust optimization guarantees, whereas a larger value guarantees the existence of better-performing policies under the belief.
  • Value of human expertise: The theory asks when this value is strictly positive and how it relates to the structure of traditional robust optimization.These questions motivate the paper’s subsequent characterization results.

3 The Value of Human Expertise and the Minimax Gap

The paper bounds the value of human expertise by a minimax gap and shows this bound is attained under an additional convexity assumption. Thus, beliefs that the nominal optimum is small can yield strictly better worst-case guarantees precisely when the minimax gap is positive.

  • 3.1 Simple Bounds: The analysis relates reduced robust optimization, robust optimization, and max-min formulations obtained by interchanging the maximum and minimum.The max-min value upper-bounds the robust value through the standard minimax inequality.
  • 3.1 Simple Bounds: The value of human expertise is at most the gap between the optimal values of the min-max and max-min problems.A positive improvement requires a gap between these two optimal values.
  • 3.2 Main Result: Theorem 1 identifies a policy performing best against all optimal solutions of the min-max problem, without requiring finite-dimensional policy or parameter spaces.It also does not require convexity in X or quasi-concavity of f(·, θ).
  • 3.2 Main Result: Under Assumptions 1 and 2, the upper bound is tight: the reduced robust problem’s improvement equals the gap between the min-max and max-min values.The result uses the smallest η for which the reduced uncertainty set is nonempty.
  • 3.2 Main Result: When the minimax gap is positive and the assumptions hold, some policies have worst-case guarantees strictly above the traditional robust optimum if the nominal optimum is small.Corollary 2 characterizes when nominal curves can be practically informative.

4 Identifiability in Data-Driven Assortment Optimization

The section shows that historical assortment data may not identify a universally safer or better new assortment, but beliefs about the nominal optimum can yield conditional performance guarantees.

  • 4.1 Problem Setup: $21 is the expected revenue of the store’s best past assortment, computed as max{$20.5, $21}.
  • 4.1 Problem Setup: Historical sales from two assortments are consistent with a broad set of RUM models, preventing reliable identification of a new assortment that beats the best past assortment in every model.The uncertainty set contains the true model under noiseless data when the true choice model is RUM.
  • 4.1 Problem Setup: No assortment satisfies the identification requirement, so no recommendation is guaranteed to increase expected revenue in the worst case.
  • 4.2 Optimization with Human Expertise: The proposed approach uses the belief that the past assortments were not highly suboptimal to evaluate new assortments through nominal curves indexed by the allowed nominal-optimality gap.The nominal curves are computed via a linear program with additional constraints tied to the gap parameter.
  • 4.3 Numerical Results: At η = $30, assortment {0, 2, 3, 4} is guaranteed to generate at least $22.097, a 5.223% increase over the $21 baseline when the best past assortment is within 30% of optimal.
  • 4.3 Numerical Results: If the belief is correct, the new assortment can improve worst-case expected revenue by 13.7%; if incorrect, its decrease is at most 2.38%.The 13.7% upside occurs at η = $23.875, while the downside bound compares against the best past assortment.

5 Combinatorial Optimization with Budget Uncertainty Sets

This section develops structural conditions showing when incorporating beliefs about a small nominal optimum reduces conservatism relative to robust optimization. It characterizes this improvement through reduced robust optimization, combinatorial structure, and shortest-path experiments.

  • Structural results: Theoretical conditions show that surprisingly loose beliefs about the nominal optimum can improve performance guarantees over robust optimization.The reduced robust problem can have a strictly smaller optimal value than the original robust problem.
  • Structural results: The non-robust problem’s optimal value lower-bounds the reduced robust problem, which is well defined and can differ from the original robust problem.
  • Structural results: Corollary 3 gives sufficient conditions for strict improvement based on support disjointness or a unique worst-case realization that does not affect a non-robust optimum.
  • Structural results: Theorem 2 characterizes when a fixed solution benefits from reduction: every worst-case realization must leave at least one optimal non-robust solution unaffected.
  • Structural results: As the belief threshold η increases, the reduced uncertainty set gains more and tighter constraints, enabling conditions based on the hitting-set number of relevant solutions.

6 Finding Policies and Controlling Disappointment

This section develops computational methods for generating policies and controlling disappointment when beliefs about the nominal problem may be wrong. It presents exact reformulations, cutting-plane methods, and parameterized alternatives that trade performance guarantees against confidence in the belief.

  • Policy generation: Policies can be generated by solving the reduced robust optimization problem over multiple η values and comparing their nominal curves.The nominal curves support decision-maker comparison across policies.
  • Computational methods: Two computational methods solve the reduced robust optimization problem: an exact reformulation for certain mixed-integer linear-fractional programs and a more general cutting-plane method.
  • Applications and examples: The value of human expertise can be strictly positive even when the convexity conditions of the main characterization fail in multinomial-logit assortment optimization.An example reports Δ = 3/5 − 1/2 = 1/10.
  • Exact reformulations: Strong duality twice yields a polynomial-size mixed-integer linear-program reformulation for the stated class of problems.It constructs an extended formulation of the reduced uncertainty set and dualizes the inner robust problem.
  • Cutting-plane method: The two-level cutting-plane method targets finite but large policy spaces when the reduced uncertainty set lacks a compactly representable dual.It is motivated by traveling salesman and large assortment optimization problems.
  • Controlling disappointment: Larger λ can make optimal policies less conservative, but their performance degrades when η is not an upper bound on the nominal optimum.Varying λ produces tradeoffs between performance guarantees and confidence in η.

7 Conclusion and Open Questions

The paper concludes that nominal curves can incorporate beliefs about small nominal optima while retaining guarantees when those beliefs are wrong. It identifies empirical testing, case studies, and extensions to other application domains as future work.

  • Conclusion: Nominal curves translate beliefs about unlikely-large nominal optima into performance guarantees that remain valid when the belief is incorrect.
  • Conclusion: The value of human expertise equals the gap between min-max and max-min robust optimization problems under the paper’s stated mild assumptions.
  • Conclusion: The paper reports substantial gaps in assortment optimization and shortest path problems, including improved guarantees under relatively loose beliefs.
  • Open questions: Future work includes empirical testing, case studies, decision-theory connections, and applications to mechanism design, chance-constrained stochastic programming, and human-AI collaboration.

A Review of Topology

The analysis relies on basic topology, which this appendix reviews before developing the paper’s results.

  • A Review of Topology: The appendix reviews basic topological facts used in the analysis.
  • A Review of Topology: Topology provides the preliminary results needed for the paper’s analysis in Sections 2 and 3.
  • A Review of Topology: The review establishes the mathematical background for subsequent arguments.

A.1 Compact sets and semicontinuity

This section uses compactness and semicontinuity to establish closedness, compactness, and attainment of optima in the paper’s optimization problems.

  • Compact sets and semicontinuity: Compactness of X and U, together with semicontinuity, implies that the relevant level sets are compact.
  • Compact sets and semicontinuity: Maxima of lower semicontinuous functions and minima of upper semicontinuous functions preserve the semicontinuity needed for the reduced uncertainty set.
  • Compact sets and semicontinuity: The Weierstrass extreme value theorem ensures that the inner and outer problems in formulations (4), (5), and (6) attain their optima.
  • Compact sets and semicontinuity: If an intersection of closed subsets of a compact set is empty, some finite subcollection already has an empty intersection.

A.2 Omitted details from the proof of Theorem 1

The proof establishes the structural properties needed for Theorem 1’s second case by analyzing minimizers over the worst nominal-value set. A finite subcollection of parameter-specific solution sets completes the omitted argument.

  • A.2 Omitted details from the proof of Theorem 1: For each θ in the minimizer set U∗, the corresponding set X_θ is closed and contained in X.These properties follow from upper semicontinuity and the appendix result on closedness.
  • A.2 Omitted details from the proof of Theorem 1: The proof’s Case 2 assumption is equivalent to there being no single x in X satisfying f(x, θ) = η for every θ in U∗.This reformulates the assumption using the parameter-specific sets X_θ.
  • A.2 Omitted details from the proof of Theorem 1: A finite collection of parameters θ1, …, θK from U∗ suffices to preserve the relevant intersection property of the closed sets X_θ.The finite collection is obtained using Proposition 10 from Appendix A.

B Proof of Proposition 1

The proof shows that the policy value function v_x(η) is nonincreasing, continuous, and convex over its relevant domain. These properties follow from nested uncertainty sets, compactness, semicontinuity, and convexity assumptions.

  • B Proof of Proposition 1: v_x(η) is nonincreasing because the reduced uncertainty sets satisfy U_η1 ⊆ U_η2 whenever η1 ≤ η2.The minimum over the larger uncertainty set cannot increase the worst-case value.
  • B Proof of Proposition 1: The reduced uncertainty set U_η is convex and nonempty for every η in [η̄, ∞).This is implied by Assumption 2 and Proposition 2.
  • B Proof of Proposition 1: Convexity of v_x follows by combining convex combinations of optimal parameters with convexity of f(x, ·).For η̂ = λη1 + (1 − λ)η2, the constructed parameter θ̂ is feasible for U_η̂ and yields the convexity inequality.
  • B Proof of Proposition 1: v_x(η) is continuous on (η̄, ∞) because every finite convex function is continuous on the interior of its domain.The proof then establishes continuity at the endpoint η̄ using compactness and lower semicontinuity.
  • B Proof of Proposition 1: v_x(η̄) = lim_k→∞ v_x(η_k) for sequences η_k decreasing to η̄, completing continuity on [η̄, ∞).Monotonicity and boundedness provide the limiting argument at the boundary.

C Omitted Proofs From §5.2

The omitted proofs characterize when robust and non-robust solutions satisfy the key support condition and derive consequences for reduced uncertainty sets. They use optimal-solution structure, budget uncertainty, and hitting-set properties.

  • C Omitted Proofs From §5.2: Theorem 2 relates condition (19) to the existence of a non-robust optimum whose support is disjoint from a worst-case realization.Both directions are proved by comparing optimal solutions of the robust and non-robust problems.
  • C Omitted Proofs From §5.2: If an optimal robust solution has size at least Γ and is disjoint from a non-robust optimum, every worst-case realization is supported within the robust solution.The budget constraint and positive deviations imply the support inclusion, which yields condition (19).
  • C Omitted Proofs From §5.2: A unique worst-case realization also suffices for condition (19) when it is disjoint from a non-robust optimum.The proof uses uniqueness directly through Theorem 2.
  • C Omitted Proofs From §5.2: Under the sufficient conditions, the robust solution satisfies the relevant strict comparison for every η in H and therefore for the reduced robust problem.The inequalities follow from robust optimality, condition (19), and feasibility for the reduced problem.
  • C Omitted Proofs From §5.2: If HittingSetNum(I_η) > Γ, then Z_η contains no binary vector, and a unique worst-case realization cannot belong to Z_η.The unique realization is an extreme point of the budget uncertainty set and hence binary.

D Extended Numerical Results from §4.3

Figure 3 expands the numerical example by plotting nominal curves for all assortments containing product 4. It identifies the assortment {0, 2, 3, 4} as optimal over a specified η interval, with the y-axis clipped at $15.

  • D Extended Numerical Results from §4.3: Figure 3 shows nominal curves for every assortment S satisfying 4 ∈ S.Only these assortments are considered because adding the most expensive product does not decrease performance.
  • D Extended Numerical Results from §4.3: {0, 2, 3, 4} is optimal for the reduced robust optimization problem for all $23.875 ≤ η ≤ η̃, where η̃ ≈ $33.778.The figure reports this interval for the expanded collection of assortments.
  • D Extended Numerical Results from §4.3: The y-axis in Figure 3 is clipped at $15.This clipping applies to the displayed numerical results.

E Omitted Proofs from §6.1.1

The appendix proves reformulations for the §6.1.1 setting under polyhedral assumptions, using strong duality and linear programming structure. It also derives a special case and applies McCormick envelopes to handle a bilinear term.

  • Assumptions: The setting assumes a binary feasible region whose convex hull has the stated linear description and a nonempty bounded polyhedral uncertainty set.The appendix specifies the dimensions of the associated matrices and vectors.
  • Reformulation: Strong duality reformulates the reduced uncertainty set as a polyhedron with a polynomial number of constraints.The reformulation introduces nonnegative γ satisfying b^Tγ ≤ ηλ − µ and A^Tγ = (U − ηL)θ.
  • Reformulation: The resulting extended formulation relies on the convex-hull assumption, the fundamental theorem of linear programming, and strong duality.These assumptions justify the successive equivalences in the proof.
  • Lemma 3: The proof of Lemma 3 represents the bilinear term by setting z = tx after combining the relevant constraints.This yields the stated reformulation using the polyhedral representation of the reduced uncertainty set.
  • Propositions 6 and 7: Proposition 6 is obtained as a special case with n = p, L = 0, U equal to the identity matrix, λ = 1, and µ = 0.Under these substitutions, the optimization problem from Lemma 3 specializes to the formulation used in Proposition 6.
  • Propositions 6 and 7: For Proposition 7, a bounded optimal value interval permits replacing the bilinear term with McCormick envelope constraints.The proof then substitutes those constraints and obtains the desired reformulation.
Loading 2608.26051v1…