Improving and benchmarking of algorithms for decision making with lower previsions

DOI10.1016/J.IJAR.2019.06.008MaRDI QIDQ2302769zbMATH OpenOpenAlexWikidataFDO

Authors Nawapon Nakharutai, Matthias C. M. Troffaes, Camila C. S. Caiado

Publication date 26 February 2020

Published in International Journal of Approximate Reasoning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.12215, http://dro.dur.ac.uk/28576/1/28576.pdf

zbMATH Keywords

algorithmdecisionbenchmarkingimprecise probabilityprimal-dualmaximality

Mathematics Subject Classification ID

Decision theory (91B06) Mathematical economics and fuzziness (91B86)

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.

Recommendations

• Towards optimal algorithms for prediction with expert advice
• scientific article; zbMATH DE number 956599
• Algorithmic complexity bounds on future prediction errors
• Fast, Optimal, and Targeted Predictions Using Parameterized Decision Analysis
• Comparison of the performances of decision aimed algorithms with Bayesian and beliefs basis
• Data-based decisions under imprecise probability and least favorable models
• scientific article; zbMATH DE number 176085
• Decision making under uncertainty and reinforcement learning. Theory and algorithms

Cites work

• scientific article; zbMATH DE number 439946 (Why is no real title available?)
• scientific article; zbMATH DE number 5359577 (Why is no real title available?)
• scientific article; zbMATH DE number 48344 (Why is no real title available?)
• A Definition of Subjective Probability
• A survey of the theory of coherent lower previsions
• Computation
• Decision making
• Decision making under uncertainty using imprecise probabilities
• Decision theory meets linear optimization beyond computation
• Improved linear programming methods for checking avoiding sure loss
• Introduction to imprecise probabilities
• Lower Previsions
• Lower previsions
• Notes on conditional previsions
• Sequential decision making with partially ordered preferences

Cited in

(3)

• Improving and benchmarking of algorithms for \(\Gamma \)-maximin, \( \Gamma \)-maximax and interval dominance
• Decision making under severe uncertainty on a budget
• Regret-based budgeted decision rules under severe uncertainty

This page was built for publication: Improving and benchmarking of algorithms for decision making with lower previsions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302769)