Linear programming algorithms for lower previsions

Abstract

The thesis begins with a brief summary of linear programming, three methods for solving linear programs (the simplex, the affine scaling and the primal-dual methods)
and a brief review of desirability and lower previsions. The first contribution is to improve these algorithms for efficiently solving these linear programming problems
for checking avoiding sure loss. To exploit these linear programs, I can reduce their size and propose novel improvements, namely, extra stopping criteria and direct
ways to calculate feasible starting points in almost all cases. To benchmark the improvements, I present algorithms for generating random sets of desirable gambles
that either avoid or do not avoid sure loss.

Overall, the affine scaling and primal-dual methods benefit from the improvements, and they both outperform the simplex method in most scenarios. Hence, I conclude that the simplex method is not a good choice for checking avoiding sure loss. If problems are small, then there is no tangible difference in performance between all methods. For large problems, the improved primal-dual method performs
at least three times faster than any of the other methods.

The second contribution is to study checking avoiding sure loss for sets of desirable gambles derived from betting odds. Specifically, in the UK betting market, bookmakers usually provide odds and give a free coupon, which can be spent on betting, to customers who first bet with them. I investigate whether a customer can exploit these odds and the free coupon in order to make a sure gain, and if that
is possible, how can that be achieved. To answer this question, I view these odds and the free coupon as a set of desirable gambles and present an algorithm to check
whether and how such a set incurs sure loss. I show that the Choquet integral and complementary slackness can be used to answer these questions. This can inform
the customers how much should be placed on each bet in order to make a sure gain.

As an illustration, I show an example using actual betting odds in the market where all sets of desirable gambles derived from those odds avoid sure loss. However,
with a free coupon, there are some combinations of bets that the customers could place in order to make a guaranteed gain.

I also consider maximality which is a criterion for decision making under uncertainty, using lower previsions. I study two existing algorithms, one proposed by Troffaes and Hable (2014), and one by Jansen, Augustin, and Schollmeyer (2017). For the last contribution in the thesis, I present a new algorithm for finding max-
imal gambles and provide a new method for generating random decision problems to benchmark these algorithms on generated sets.

To find all maximal gambles, Jansen et al. solve one large linear program for each gamble, while in Troffaes and Hable, and also in our new algorithm, this can be
done by solving a larger sequence of smaller linear programs. For the second case, I apply efficient ways to find a common feasible starting point for this sequence of
linear programs from the first contribution. Exploiting these feasible starting points, I propose early stopping criteria for further improving efficiency for the primal-dual method.

For benchmarking, we can generate sets of gambles with pre-specified ratios of maximal and interval dominant gambles. I investigate the use of interval dominance
at the beginning to eliminate non-maximal gambles. I find that this can make the problem smaller and 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.