Source-linked AI summary
Decision making under uncertainty using imprecise probabilities
Matthias C. M. Troffaes
TL;DR
The paper asks how to choose decisions when uncertain gains and imprecise probabilities prevent a uniquely identified probability model. It compares several optimality criteria, generalizes an existence condition, and proposes an efficient computational approach. A numerical example demonstrates that expected-utility optima are not robust to arbitrary probability choices, while the criteria differ in how many decisions they retain and how efficiently they can be computed.
Problem
Uncertain gains and insufficient information to identify a precise probability measure make ordinary expected-utility maximization inadequate for representing optimality.
Method
The paper compares admissibility, expected utility, maximality, E-admissibility, Γ-maximax, and Γ-maximin, and develops existence and computational results for these criteria.
Results
Expected-utility optima are not robust to changes in µ when only 0.28 ≤µ(H) ≤0.7 is known, while the alternative criteria differ in selected decisions and computational cost.
Takeaways & Limitations
E-admissibility, maximality, and interval dominance retain fewer optimal decisions as beliefs become more determinate, whereas Γ-maximin and Γ-maximax target pessimistic or optimistic choices.
Takeaways & Limitations
Interval dominance cannot use dynamic programming in sequential decision problems, making maximality and E-admissibility preferable in that setting.
Abstract
from arXiv · showhide
Various ways for decision making with imprecise probabilities (admissibility, maximal expected utility, maximality, E-admissibility, $Γ$-maximax, $Γ$-maximin, all of which are well-known from the literature) are discussed and compared. We generalize a well-known sufficient condition for existence of optimal decisions. A simple numerical example shows how these criteria can work in practice, and demonstrates their differences. Finally, we suggest an efficient approach to calculate optimal decisions under these decision criteria.
1. Introduction
The paper frames decision-making under uncertainty as selecting optimal decisions when gains are gambles, beginning with point-wise dominance and then refining admissible choices using additional information about uncertainty.
- 1. Introduction: An optimal decision maximizes the real-valued gain induced over the available decision set.If gains are uncertain, each decision induces a bounded gain gamble over the possibility space.
- 1. Introduction: When gain values are uncertain, each decision’s outcome is modeled as a bounded gamble on a random variable X under act-state independence.The outcome x is assumed independent of the decision selected.
- 1. Introduction: Point-wise dominance removes any decision whose gain is never higher and is strictly lower in at least one state than another decision’s gain.The dominating decision guarantees at least as much utility for every realization of X.
- 1. Introduction: Admissible decisions are the remaining undominated choices, and they exist under a sufficient weak-compactness condition on the set of gain gambles.The paper notes that this condition is sufficient but not necessary.
- 1. Introduction: The paper compares established criteria for further reducing admissible decisions and generalizes a sufficient existence condition while addressing computational efficiency.The criteria include expected utility, maximality, E-admissibility, Γ-maximax, and Γ-maximin.
2. Maximising Expected Utility?
The paper examines expected-utility maximization when beliefs about uncertain outcomes are represented probabilistically. It shows that insufficient information about the probability measure can make this criterion non-robust, while assuming compact gain sets ensures optimal solutions exist.
- 2. Maximising Expected Utility?: Beliefs about X are modeled by a probability measure µ, and decisions are selected by maximizing the expected utility of their gain gambles.The measure may be finitely additive, with expected utility defined using an integral extending the usual textbook integral.
- 2. Maximising Expected Utility?: Optimal expected-utility solutions are guaranteed when the set of gain gambles is non-empty and compact under the supremum norm.The paper assumes this condition thereafter and states that a slightly weaker condition appears in the appendix.
- 2. Maximising Expected Utility?: Insufficient information to identify the probability of every event can make maximizing expected utility an inadequate representation of optimality.The issue arises when beliefs about X cannot be represented by a single probability measure.
- 2. Maximising Expected Utility?: With only 0.28 ≤ µ(H) ≤ 0.7 known, the expected-utility optimum is not robust to changes in the chosen probability measure.The coin-toss example uses six decisions and demonstrates sensitivity to the otherwise arbitrary choice of µ.
3. Generalising to Imprecise Probabilities
The paper models uncertain beliefs about X with a credal set of probability measures and compares several decision criteria for selecting optimal decisions. These criteria differ in how they treat worst-case, best-case, pairwise, and expected-utility preferences, producing different solution sets in the numerical example.
- Belief model: Beliefs are represented by a closed convex set M of finitely additive probability measures satisfying linear inequalities from lower-prevision assessments.This framework includes precise probabilities when M is a singleton and complete ignorance when M contains all finitely additive probability measures.
- Belief model: For finite X and K, lower and upper expected utilities can be computed by solving a linear program.Lower expected utility minimizes Eµ(g) subject to the constraints defining M, while upper expected utility is obtained from the corresponding maximization.
- Γ-maximin and Γ-maximax: Γ-maximin selects the decision with the greatest worst expected gain, yielding optE(D) = {5} in the example.Under complete ignorance, Γ-maximin coincides with maximin and ranks decisions by the infimum of their gain gambles.
- Maximality: Maximality robustifies pairwise expected-utility preferences over M and returns opt⊐P(D) = {1, 2, 3, 5} in the example.Its ordering interprets a positive lower expected utility for Jd − Je as a strict preference for d over e.
- Interval dominance: Interval dominance is weaker than maximality, producing opt⊐P(D) = {1, 2, 3, 5, 6}, a strictly larger solution set.The criterion compares lower and upper expected-utility intervals, retaining decisions whose intervals are not completely dominated.
- E-admissibility: E-admissibility selects admissible decisions that maximize expected utility for at least one probability measure in M, giving optM(D) = {1, 2, 3}.The paper presents this as a robustification of expected-utility optimization against changes in µ within M.
4. Which Is the Right One?
The paper compares decision criteria under imprecise probabilities and relates their choice to decision-maker goals and computational structure. It also identifies practical trade-offs and an efficient preprocessing step for computing maximal or E-admissible decisions.
- Comparing criteria: E-admissibility, maximality, and interval dominance select fewer options as beliefs become more determinate, unlike Γ-maximin and Γ-maximax.Γ-maximin and Γ-maximax may select a single decision even under complete ignorance.
- Computational trade-offs: Interval dominance generally returns more optimal options than maximality but requires fewer natural extensions and comparisons.For n decisions, interval dominance requires 2n natural extensions, whereas maximality requires n^2−n.
- Computational trade-offs: Interval dominance can efficiently eliminate decisions that are neither maximal nor E-admissible before applying those criteria.This preprocessing step reduces the subsequent computation without removing any maximal or E-admissible decision.
- Comparing criteria: E-admissibility and maximality coincide for decision sets with two decisions and for convex sets of gain gambles.E-admissibility is stronger than maximality and is not vulnerable to domination by randomized decisions.
- Algorithms: An algorithm for pure E-admissible options requires n linear programs in m variables with r+n constraints.With convexified decisions, the worst case becomes n! linear programs, but only ℓ!+n−ℓ are needed when there are ℓ E-admissible pure options.
- Choosing a criterion: The preferred criterion depends on the decision maker’s goals and, when relevant, the problem’s size and structure.For sequential problems, dynamic programming cannot be used with interval dominance, favoring maximality or E-admissibility in that setting.
Appendix A. Proofs
The appendix establishes the formal setting for decisions, gain gambles, lower previsions, natural extensions, and representing credal sets. It also states the integration framework used in the proofs.
- Formal setting: Each decision d induces a bounded gain gamble Jd in L(X), the set of all gambles on the possibility space X.The gain gambles and gambles in K are measurable with respect to a field F on X.
- Formal setting: The lower prevision is defined on K, assumed to avoid sure loss, and extended naturally to all F-measurable gambles.The proofs use properties of natural extension, including superadditivity.
- Formal setting: The credal set M represents the lower prevision P, while µ denotes an arbitrary finitely additive probability measure on F.Eµ is the Dunford integral, defined at least for all F-measurable gambles.
A.1. Connections between Decision Criteria.
The appendix proves relations among the decision criteria by ordering gain gambles through expectations and lower or upper envelopes. These results connect Γ-maximax and related criteria to maximality.
- Connections between Decision Criteria: Theorem 1 establishes relations among the optimality criteria discussed in the paper.The relations are used to connect the criteria formally and support the comparisons in the main text.
- Connections between Decision Criteria: If d is Γ-maximax, some µ in the credal set makes d maximize expected utility over maximal gain gambles, so d is optimal under the corresponding criterion.The proof uses the upper envelope of M and weak-* compactness.
- Connections between Decision Criteria: If d maximizes expected utility for a suitable µ over maximal gain gambles, then d must be maximal.The argument applies the lower-envelope inequality to each competing maximal gamble.
- Connections between Decision Criteria: If d is maximal, lower-envelope inequalities imply that it maximizes the relevant criterion over maximal gain gambles.The proof uses the lower envelope of M and the defining maximality relation.
A.2. Existence.
The appendix generalizes existence results for optimal decisions using preorder maximality and compactness. It shows that weak or stronger compactness conditions guarantee admissible and criterion-specific optimal decisions.
- Preorder lemma: A maximal element exists in any non-empty compact set when upper sets of a suitable preorder are closed.The proof uses compactness, the finite intersection property, and Zorn’s lemma.
- Topologies: The weak topology on L(X) is the topology of point-wise convergence.A net converges weakly when it converges at every x in X.
- Admissibility: If the set of gain gambles is non-empty and weakly compact, at least one admissible decision exists, and every decision is weakly dominated by an admissible one.Admissibility corresponds to maximality under point-wise gain comparison.
- Topologies: The τ-topology combines point-wise convergence with convergence of the relevant envelope quantities and is stronger than the weak topology but weaker than the supremum norm topology.For finite X, it coincides with the weak topology and the supremum norm topology.
- Existence theorem: If the gain set is non-empty and τ-compact, the theorem establishes non-emptiness for several optimality criteria, including expected utility and Γ-based criteria.The proof uses τ-continuity of integration and the existence of point-wise maximal gains.