Efficient Algorithms for Checking Avoiding Sure Loss

Nawapon Nakharutai, Matthias C. M. Troffaes, Camila C. S. Caiado
Proceedings of the Tenth International Symposium on Imprecise Probability: Theories and Applications, PMLR 62:241-252, 2017.

Abstract

Sets of desirable gambles provide a general representation of uncertainty which can handle partial information in a more robust way than precise probabilities. Here we study the effectiveness of linear programming algorithms for determining whether or not a given set of desirable gambles avoids sure loss (i.e. is consistent). We also suggest improvements to these algorithms specifically for checking avoiding sure loss. By exploiting the structure of the problem, (i) we slightly reduce its dimension, (ii) we propose an extra stopping criterion based on its degenerate structure, and (iii) we show that one can directly calculate feasible starting points in various cases, therefore reducing the effort required in the presolve phase of some of these algorithms. To assess our results, we compare the impact of these improvements on the simplex method and two interior point methods (affine scaling and primal-dual) on randomly generated sets of desirable gambles that either avoid or do not avoid sure loss. We find that the simplex method is outperformed by the primal-dual and affine scaling methods, except for very small problems. We also find that using our starting feasible point and extra stopping criterion considerably improves the performance of the primal-dual and affine scaling methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v62-nakharutai17a, title = {Efficient Algorithms for Checking Avoiding Sure Loss}, author = {Nakharutai, Nawapon and Troffaes, Matthias C. M. and Caiado, Camila C. S.}, booktitle = {Proceedings of the Tenth International Symposium on Imprecise Probability: Theories and Applications}, pages = {241--252}, year = {2017}, editor = {Antonucci, Alessandro and Corani, Giorgio and Couso, Inés and Destercke, Sébastien}, volume = {62}, series = {Proceedings of Machine Learning Research}, month = {10--14 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v62/nakharutai17a/nakharutai17a.pdf}, url = {https://proceedings.mlr.press/v62/nakharutai17a.html}, abstract = {Sets of desirable gambles provide a general representation of uncertainty which can handle partial information in a more robust way than precise probabilities. Here we study the effectiveness of linear programming algorithms for determining whether or not a given set of desirable gambles avoids sure loss (i.e. is consistent). We also suggest improvements to these algorithms specifically for checking avoiding sure loss. By exploiting the structure of the problem, (i) we slightly reduce its dimension, (ii) we propose an extra stopping criterion based on its degenerate structure, and (iii) we show that one can directly calculate feasible starting points in various cases, therefore reducing the effort required in the presolve phase of some of these algorithms. To assess our results, we compare the impact of these improvements on the simplex method and two interior point methods (affine scaling and primal-dual) on randomly generated sets of desirable gambles that either avoid or do not avoid sure loss. We find that the simplex method is outperformed by the primal-dual and affine scaling methods, except for very small problems. We also find that using our starting feasible point and extra stopping criterion considerably improves the performance of the primal-dual and affine scaling methods.} }
Endnote
%0 Conference Paper %T Efficient Algorithms for Checking Avoiding Sure Loss %A Nawapon Nakharutai %A Matthias C. M. Troffaes %A Camila C. S. Caiado %B Proceedings of the Tenth International Symposium on Imprecise Probability: Theories and Applications %C Proceedings of Machine Learning Research %D 2017 %E Alessandro Antonucci %E Giorgio Corani %E Inés Couso %E Sébastien Destercke %F pmlr-v62-nakharutai17a %I PMLR %P 241--252 %U https://proceedings.mlr.press/v62/nakharutai17a.html %V 62 %X Sets of desirable gambles provide a general representation of uncertainty which can handle partial information in a more robust way than precise probabilities. Here we study the effectiveness of linear programming algorithms for determining whether or not a given set of desirable gambles avoids sure loss (i.e. is consistent). We also suggest improvements to these algorithms specifically for checking avoiding sure loss. By exploiting the structure of the problem, (i) we slightly reduce its dimension, (ii) we propose an extra stopping criterion based on its degenerate structure, and (iii) we show that one can directly calculate feasible starting points in various cases, therefore reducing the effort required in the presolve phase of some of these algorithms. To assess our results, we compare the impact of these improvements on the simplex method and two interior point methods (affine scaling and primal-dual) on randomly generated sets of desirable gambles that either avoid or do not avoid sure loss. We find that the simplex method is outperformed by the primal-dual and affine scaling methods, except for very small problems. We also find that using our starting feasible point and extra stopping criterion considerably improves the performance of the primal-dual and affine scaling methods.
APA
Nakharutai, N., Troffaes, M.C.M. & Caiado, C.C.S.. (2017). Efficient Algorithms for Checking Avoiding Sure Loss. Proceedings of the Tenth International Symposium on Imprecise Probability: Theories and Applications, in Proceedings of Machine Learning Research 62:241-252 Available from https://proceedings.mlr.press/v62/nakharutai17a.html.

Related Material