pith. sign in

arxiv: 1906.12215 · v1 · pith:JJDGEE7Xnew · submitted 2019-06-28 · 🧮 math.OC · cs.DS· stat.CO

Improving and benchmarking of algorithms for decision making with lower previsions

Nawapon Nakharutai , Matthias C. M. Troffaes , Camila C. S. Caiado This is my paper

Pith reviewed 2026-05-25 13:52 UTC · model grok-4.3

classification 🧮 math.OC cs.DSstat.CO
keywords lower previsionsmaximal gamblesinterval dominancedecision making under uncertaintyprimal-dual interior point methodbenchmarkingimprecise probabilitieslinear programming
0
0 comments X

The pith

A new algorithm for finding maximal gambles under lower previsions outperforms prior methods in every benchmarked scenario even without interval dominance.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a new algorithm for identifying maximal gambles when decisions are based on lower previsions, which encode sets of probability distributions. It also supplies a generator that creates random test problems with fixed ratios of maximal and interval-dominant gambles. Benchmark comparisons show that the primal-dual interior point method, equipped with shared feasible starting points and early stopping rules, runs fastest. The authors' implementation beats the two earlier algorithms across all tested cases. Pre-filtering via interval dominance shrinks some problems but improves only one of the older codes and does not help the new method.

Core claim

The paper claims that its new algorithm for finding maximal gambles, built on the primal-dual interior point method together with common feasible starting points and early stopping criteria, outperforms both the Troffaes-Hable algorithm and the Jansen-Augustin-Schollmeyer algorithm in all scenarios, and that this superiority holds even when interval dominance is not used to reduce the set of gambles beforehand.

What carries the argument

The primal-dual interior point method applied to linear programs that test maximality of gambles, augmented by feasible starting points and early stopping criteria.

If this is right

  • The primal-dual interior point method with early stopping is the most efficient solver among the compared approaches for maximality checks.
  • Interval dominance pre-processing reduces problem size and speeds up only the Jansen et al. algorithm, not the other two.
  • The new random problem generator allows controlled experiments that fix the proportions of maximal and interval-dominant gambles.
  • The authors' algorithm delivers the lowest run times in all tested configurations without any interval dominance step.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The efficiency gains could allow maximality checks on decision problems with hundreds of gambles that were previously intractable.
  • The same starting-point and early-stopping techniques might be adapted to compute E-admissibility or other choice criteria under lower previsions.
  • If real applications exhibit different correlation structures among gambles than the synthetic generator produces, the observed ranking of run times could shift.

Load-bearing premise

The randomly generated decision problems with controlled ratios of maximal and interval-dominant gambles match the computational difficulty of real lower prevision decision tasks.

What would settle it

Run the four algorithms on a collection of decision problems taken from actual applications of lower previsions and check whether the new algorithm still requires the least total computation time in every case.

Figures

Figures reproduced from arXiv: 1906.12215 by Camila C. S. Caiado, Matthias C. M. Troffaes, Nawapon Nakharutai.

Figure 1
Figure 1. Figure 1: Early stopping criterion 3.3. Fast evaluation of natural extensions inside algorithms. We can also speed up the process of evaluating the natural extension through (P1) or (D1). To do so, we exploit the fact that we only need to find the sign of E(g − f), and not its exact value, to verify whether f is dominated by g or not. As we minimize the objective function in (P1), the optimal value of (P1) is less o… view at source ↗
Figure 2
Figure 2. Figure 2: Ranges for α such that h−α satisfies either of the situations described in theorem 1. Let K be a set of gambles. Given any gamble h, lemma 1 shows for which α, h − α is a maximal gamble in K ∪ {h − α}. Lemma 1. Let K be a set of gambles and let h be another gamble and α ∈ R. Then h − α is maximal in K ∪ {h − α} if and only if (21) min f∈opt (K) E(h − f) ≥ α. Lemma 1 provides an upper bound on α for which h… view at source ↗
Figure 3
Figure 3. Figure 3: The area of m ≤ n ≤ k and 10 options label the different m and n that we consider in the simulation (see table 1) Options |K| = 24 |K| = 26 |K| = 28 m n m n m n a 1 1 1 1 1 1 b 1 5 1 21 1 85 c 1 11 1 42 1 170 d 1 16 1 64 1 256 e 5 5 21 21 85 85 f 5 11 21 42 85 170 g 5 16 21 64 85 256 h 11 11 42 42 170 170 i 11 16 42 64 170 256 j 16 16 64 64 256 256 [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison plots of the average computational time for al￾gorithms 1, 2, 3 and 4 for finding maximal gambles and for algorithm 5 for finding interval dominant gambles. The number of outcomes in left column is 22 and 26 in the right column. Each row represents a differ￾ent number of gambles with vary options of the numbers of maximal gambles and interval dominant gambles in the set (see table 1 for each opt… view at source ↗
Figure 5
Figure 5. Figure 5: Comparison plots of the average computational time for algo￾rithms 1 and 2 for finding maximal gambles and algorithm 5 for finding interval dominant gambles. In the left column, | dom P| = 22 and in the right column, | dom P| = 26 . Each row represents different numbers of gambles and outcomes with vary options of the numbers of maximal gambles and interval dominant gambles in the set (see table 1 for each… view at source ↗
read the original abstract

Maximality, interval dominance, and E-admissibility are three well-known criteria for decision making under severe uncertainty using lower previsions. We present a new fast algorithm for finding maximal gambles. We compare its performance to existing algorithms, one proposed by Troffaes and Hable (2014), and one by Jansen, Augustin, and Schollmeyer (2017). To do so, we develop a new method for generating random decision problems with pre-specified ratios of maximal and interval dominant gambles. Based on earlier work, we present efficient ways to find common feasible starting points in these algorithms. We then exploit these feasible starting points to develop early stopping criteria for the primal-dual interior point method, further improving efficiency. We find that the primal-dual interior point method works best. We also investigate the use of interval dominance to eliminate non-maximal gambles. This can make the problem smaller, and we observe that this benefits Jansen et al.'s algorithm, but perhaps surprisingly, not the other two algorithms. We find that our algorithm, without using interval dominance, outperforms all other algorithms in all scenarios in our benchmarking.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces improvements to algorithms for identifying maximal gambles under lower previsions, including a new primal-dual interior-point method with feasible starting points and early stopping criteria. It develops a new random generator for decision problems that controls the ratios of maximal and interval-dominant gambles, then benchmarks the new algorithm against Troffaes-Hable (2014) and Jansen et al. (2017), reporting that the proposed method outperforms the others in every scenario even without interval dominance.

Significance. If the empirical results hold under representative instances, the work supplies practical efficiency gains for decision making with lower previsions. Credit is due for the controllable random generator and the exploitation of feasible starts to enable early stopping; these are concrete, reusable contributions to computational lower-prevision theory.

major comments (2)
  1. [Benchmarking section] Benchmarking section: the claim that the new algorithm 'outperforms all other algorithms in all scenarios' is load-bearing and rests entirely on instances generated by the new random procedure that enforces pre-specified ratios of maximal and interval-dominant gambles. No external validation (theoretical or against published real-world lower-prevision problems) is supplied showing that the resulting LPs match the sparsity, conditioning, or dependency structure of actual applications; if they do not, the observed ranking can reverse.
  2. [Section on interval dominance] Section on interval dominance: the differential effect that interval dominance reduces problem size and benefits only Jansen et al.'s algorithm (but not the other two) is reported as an empirical observation. Because this reduction is presented as an optional preprocessing step whose utility depends on the solver, the lack of any analysis explaining the asymmetry undermines the practical recommendation about when to apply it.
minor comments (1)
  1. The description of the early-stopping criteria derived from the feasible starting points would benefit from an explicit statement of the numerical tolerance used and how it interacts with the reported timing results.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address the two major points below, agreeing where the manuscript is limited and outlining targeted revisions.

read point-by-point responses

  1. Referee: [Benchmarking section] Benchmarking section: the claim that the new algorithm 'outperforms all other algorithms in all scenarios' is load-bearing and rests entirely on instances generated by the new random procedure that enforces pre-specified ratios of maximal and interval-dominant gambles. No external validation (theoretical or against published real-world lower-prevision problems) is supplied showing that the resulting LPs match the sparsity, conditioning, or dependency structure of actual applications; if they do not, the observed ranking can reverse.

    Authors: We acknowledge that all reported comparisons rely on instances from the new controllable generator and that no real-world lower-prevision decision problems are used for external validation. The generator's value lies in its ability to enforce prescribed ratios of maximal and interval-dominant gambles, enabling systematic testing across regimes that previous generators could not isolate. We will revise the benchmarking section and add a dedicated limitations paragraph that (i) states the absence of published real-world test sets, (ii) explains the design choices that make the synthetic instances representative of varying sparsity and dominance ratios, and (iii) qualifies the performance claims accordingly. This constitutes a partial revision. revision: partial

  2. Referee: [Section on interval dominance] Section on interval dominance: the differential effect that interval dominance reduces problem size and benefits only Jansen et al.'s algorithm (but not the other two) is reported as an empirical observation. Because this reduction is presented as an optional preprocessing step whose utility depends on the solver, the lack of any analysis explaining the asymmetry undermines the practical recommendation about when to apply it.

    Authors: The manuscript reports the asymmetric benefit as an empirical observation without supplying an explanatory analysis. We will expand the relevant section with a short discussion that links the observed behavior to the algorithmic structures: Jansen et al.'s method repeatedly solves many small linear programs whose total work scales directly with the number of gambles, whereas the primal-dual interior-point method and the Troffaes-Hable algorithm incur fixed overhead per problem that does not decrease proportionally with size reduction. This addition will support clearer guidance on when interval dominance should be applied as preprocessing. revision: yes

Circularity Check

0 steps flagged

No circularity; empirical benchmarking is self-contained

full rationale

The paper's claims consist of algorithmic improvements (feasible-start heuristics, early stopping for primal-dual interior-point method) and direct empirical timing comparisons on a new random-problem generator that controls ratios of maximal and interval-dominant gambles. No derivation chain exists that reduces a prediction or result to its own inputs by construction, no fitted parameters are relabeled as predictions, and no load-bearing self-citation justifies the outperformance result; the benchmarking measurements stand independently of the cited baseline algorithms.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard convex optimization theory and the established definition of lower previsions; no new free parameters, axioms, or invented entities are introduced beyond those in the cited literature.

axioms (1)
  • domain assumption Decision problems under lower previsions can be solved via linear programming or interior-point methods as formulated in prior work.
    The algorithms compared all presuppose this modeling choice.

pith-pipeline@v0.9.0 · 5745 in / 1181 out tokens · 38588 ms · 2026-05-25T13:52:16.332649+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    F. J. Anscombe and R. J. Aumann. A definition of subjective probability. Annals of Mathematical Statistics, 34 0 (1): 0 199--205, March 1963

    work page 1963

  2. [2]

    Thomas Augustin, Frank P. A. Coolen, Gert De Cooman, and Matthias C. M. Troffaes, editors. Introduction to Imprecise Probabilities. Wiley Series in Probability and Statistics. Wiley, 2014. ISBN 978-0-470-97381-3. URL http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0470973811.html

    work page 2014

  3. [3]

    Linear Optimization and Extensions: Theory and Algorithms

    Shu-Cherng Fang and Sarat Puthenpura. Linear Optimization and Extensions: Theory and Algorithms. Springer Science+Business Media New York, 1993

    work page 1993

  4. [4]

    Nash, and Ariela Sofer

    Igor Griva, Stephen G. Nash, and Ariela Sofer. Linear and Nonlinear Optimization Second edition. SIAM, Philadelphia, 2009

    work page 2009

  5. [5]

    Nathan Huntley, Robert Hable, and Matthias C. M. Troffaes. Introduction to Imprecise Probabilities, chapter Decision making, pages 190--206. Wiley, 2014. doi:10.1002/9781118763117.ch8

    work page doi:10.1002/9781118763117.ch8 2014

  6. [6]

    Decision theory meets linear optimization beyond computation

    Christoph Jansen, Thomas Augustin, and Georg Schollmeyer. Decision theory meets linear optimization beyond computation. In Alessandro Antonucci, Laurence Cholvy, and Odile Papini, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty, pages 329--339, Cham, 2017. Springer International Publishing. ISBN 978-3-319-61581-3

    work page 2017

  7. [7]

    Cozman, and Cassio P

    Daniel Kikuti, Fabio G. Cozman, and Cassio P. De Campos. Partially ordered preferences in decision trees: computing strategies with imprecision in probabilities. In In IJCAI Workshop on Advances in Preference Handling, pages 118--123, 2005

    work page 2005

  8. [8]

    Sequential decision making with partially ordered preferences

    Daniel Kikuti, Fabio Gagliardi Cozman, and Ricardo Shirota Filho. Sequential decision making with partially ordered preferences. Artificial Intelligence, 175 0 (7): 0 1346 -- 1365, 2011. ISSN 0004-3702. doi:https://doi.org/10.1016/j.artint.2010.11.017. URL http://www.sciencedirect.com/science/article/pii/S0004370210002067. Representing, Processing, and Le...

    work page doi:10.1016/j.artint.2010.11.017 2011

  9. [9]

    version 9.4.0.813654 (R2018a)

    MATLAB. version 9.4.0.813654 (R2018a). The MathWorks Inc., Natick, Massachusetts, 2018

    work page 2018

  10. [10]

    A survey of the theory of coherent lower previsions

    Enrique Miranda. A survey of the theory of coherent lower previsions. International Journal of Approximate Reasoning, 48 0 (2): 0 628--658, 2008. doi:10.1016/j.ijar.2007.12.001

    work page doi:10.1016/j.ijar.2007.12.001 2008

  11. [11]

    Introduction to Imprecise Probabilities, chapter Lower prevision, pages 28--55

    Enrique Miranda and Gert de Cooman. Introduction to Imprecise Probabilities, chapter Lower prevision, pages 28--55. Wiley, 2014. doi:10.1002/9781118763117.ch2

    work page doi:10.1002/9781118763117.ch2 2014

  12. [12]

    Nakharutai, M

    N. Nakharutai, M. C. M. Troffaes, and C. C. S. Caiado. Improved linear programming methods for checking avoiding sure loss. International Journal of Approximate Reasoning, 101: 0 293--310, 2018. doi:10.1016/j.ijar.2018.07.013

    work page doi:10.1016/j.ijar.2018.07.013 2018

  13. [13]

    Matthias C. M. Troffaes. Decision making under uncertainty using imprecise probabilities. International Journal of Approximate Reasoning, 45 0 (1): 0 17--29, may 2007. doi:10.1016/j.ijar.2006.06.001

    work page doi:10.1016/j.ijar.2006.06.001 2007

  14. [14]

    Matthias C. M. Troffaes and Gert de Cooman. Lower Previsions. Wiley Series in Probability and Statistics. Wiley, 2014. ISBN 978-0-470-72377-7. URL http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0470723777.html

    work page 2014

  15. [15]

    Matthias C. M. Troffaes and Robert Hable. Introduction to Imprecise Probabilities, chapter Computation, pages 329--337. Wiley, 2014. doi:10.1002/9781118763117.ch16

    work page doi:10.1002/9781118763117.ch16 2014

  16. [16]

    Utkin and Thomas Augustin

    Lev V. Utkin and Thomas Augustin. Powerful algorithms for decision making under partial prior information and general ambiguity attitudes. In ISIPTA, 2005

    work page 2005

  17. [17]

    Statistical Reasoning with Imprecise Probabilities

    Peter Walley. Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London, 1991

    work page 1991

  18. [18]

    Williams

    Peter M. Williams. Notes on conditional previsions. Technical report, School of Math. and Phys. Sci., Univ. of Sussex, 1975

    work page 1975

  19. [19]

    Williams

    Peter M. Williams. Notes on conditional previsions. International Journal of Approximate Reasoning, 44 0 (3): 0 366--383, 2007. doi:10.1016/j.ijar.2006.07.019

    work page doi:10.1016/j.ijar.2006.07.019 2007

  20. [20]

    Reliable diagnoses of dementia by the naive credal classifier inferred from incomplete cognitive data

    Marco Zaffalon, Keith Wesnes, and Orlando Petrini. Reliable diagnoses of dementia by the naive credal classifier inferred from incomplete cognitive data. Artificial Intelligence in Medicine, 29 0 (1--2): 0 61--79, 2003

    work page 2003