My recent post on fixed-odds betting arbitrage left some rather intriguing questions unanswered. Although I used Linear Programming to find an arbitrage opportunity, the focus was on constraint satisfaction, rather than optimality. But, then, if betting can be viewed as playing a sequential game with fate, what would the word “optimal” even mean in this context?
In this post, I will focus on optimality. I will assume the reader is already acquainted with my previous post and, therefore, for convenience I will abstain from “beginning at the beginning”. In other words, this post is not self-contained.
Given the odds matrix , the set of admissible vectors , and a budget , we would like to find a money allocation matrix such that and
so that, regardless of what vector fate happens to choose, we make a profit. Let us enumerate the vectors, , where . Since , the arbitrage inequalities can be written as
Let . Hence, the inequality can be rewritten as . Let us define , and let
be the matrix whose -th column is . Thus, the arbitrage inequalities can be written more compactly as or, equivalently, as . Hence, so far, we have inequality constraints
Since the entries of matrix must be non-negative, we have additional inequality constraints or, equivalently, , where is the identity matrix.
To make the model more realistic, let us suppose that the amount of money being betted on outcome at bookmaker is bounded above by , i.e., . This is useful not only because bookmakers impose upper bounds on how much money one can bet, but also because it may happen that not all bookmakers are posting odds on the very same outcomes. By making one can make sure that no money will be betted on a certain outcome at a certain bookmaker. If bookmaker is not imposing any upper bound on then we can make , i.e., the most we can bet on outcome at bookmaker is our budget . Let
be the matrix of upper bounds, and let . Then, the inequalities can be written more compactly as or, equivalently, as .
Finally, we have a total of inequality constraints
If we can find an -dimensional decision vector that satisfies the inequality constraints above, then we conclude that an arbitrage opportunity does exist. This is a constraint satisfaction problem.
As we discussed before, the inequality constraints define a polytope in . If this polytope is non-empty, then there exists at least one arbitrage opportunity. We can determine if the polytope is non-empty by solving a linear program with an arbitrary objective function
where we chose , the most nihilistic of all linear objective functions. If this linear program is feasible, then an arbitrage opportunity does exist. In other words, we solve the constraint satisfaction problem via linear programming.
Minimum Guaranteed Profit
We can go beyond mere arbitrage. Suppose we want to guarantee a minimum return of regardless of what is chosen by fate, i.e.,
Hence, instead of the linear inequality constraints , we now have the linear inequality constraints or, equivalently, . Suppose also that the bookmakers impose no upper bounds on the . Hence, we have , and . We then have the following inequality constraints
Yet once again, we have a constraint satisfaction problem that can be solved via linear programming with an arbitrary objective function
Starting with a small , say , and increasing it in a successive fashion until the linear program is no longer feasible, one can obtain money allocation matrices that yield higher and higher minimum guaranteed profits.
Beyond Constraint Satisfaction
Instead of trying various values of until the linear program that solves the constraint satisfaction problem is no longer feasible, we can find the maximum via optimization. Note that can be rewritten as
Hence, we can find the maximum that yields a feasible linear program by solving the following maximization problem in with the additional inequality constraint or, equivalently,
Note that now we do have an actual optimization problem, i.e., the linear program above is a maximization problem, not merely a constraint satisfaction problem. Since maximizing is the same as minimizing , we can rewrite the maximization problem as a minimization problem, as follows
The solutions of the maximization / minimization problems are maximin solutions, i.e., we are maximizing the minimum profit. In other words, we are pessimists and assume that fate will always choose the most damaging . Hence, we choose a money allocation matrix such that the minimum profit will be maximized. We are looking for the best worst-case scenario.
Example: Sharapova versus Kirilenko
Let us revisit the tennis match we considered previously. Suppose that bookmakers are posting odds for a Sharapova versus Kirilenko match, and that the bookies are offering odds for mutually exclusive outcomes: Sharapova wins, or Kirilenko wins. Imagine that the bookies posted the following decimal odds
which means that bookie #1 is offering odds for a Sharapova victory, whereas bookie #2 is offering odds for the same outcome. Note that and that the matrix is
Assuming that the bookies impose no upper bounds on the , then the maximin return and the maximin money allocation matrix can be found by solving the linear program
from cvxopt import matrix from cvxopt import spmatrix from cvxopt import solvers # available budget c = 100 # build (decimal) odds matrix Omega = matrix([[1.25, 3.90], [1.43, 2.85]]) # build q vectors and Q matrix q1 = matrix([0.25, -1.0, 0.43, -1.0]) q2 = matrix([-1.0, 2.90, -1.0, 1.85]) Q = matrix([[q1], [q2]]) # build 4x4 identity matrix Id = spmatrix(1.0, range(4), range(4)) # --------------- # linear program # --------------- # build objective vector f = matrix([-1.0, matrix(0.0, (4,1))]) # build inequality constraint matrices A = matrix([[-1.0, 0.0, c*matrix(1.0, (2,1)), matrix(0.0, (8,1))], [matrix(0.0, (1,4)), matrix(1.0, (1,4)), -Q.T, -Id, Id]]) b = matrix([0.0, c, matrix(0.0, (6,1)), c*matrix(1.0, (4,1))]) # solve linear program solvers.options['show_progress'] = True solution = solvers.lp(f, A, b) # print solution and profits sol = solution['x'] alpha = sol x = sol[1:5] # build money allocation matrix X = matrix([[sol, sol],[sol, sol]]) print "\nMaximin return (%):" print 100 * alpha print "\nMaximin money allocation matrix:" print X print "Profit if Sharapova wins:" print q1.T * x print "Profit if Kirilenko wins:" print q2.T * x print "Total amount at stake:" print sum(x)
The output of this script is the following:
pcost dcost gap pres dres k/t 0: 1.7194e-002 -5.0054e+002 7e+002 4e-001 2e+002 1e+000 1: 1.9534e-001 -1.7513e+001 2e+001 2e-002 7e+000 1e+000 2: 1.3994e-001 -2.3748e+000 2e+000 2e-003 1e+000 2e-001 3: 1.4821e-002 -8.9421e-001 9e-001 8e-004 4e-001 7e-002 4: -1.7326e-002 -9.9421e-002 7e-002 7e-005 3e-002 9e-004 5: -3.8136e-002 -5.1946e-002 1e-002 1e-005 6e-003 3e-004 6: -4.6244e-002 -4.6469e-002 2e-004 2e-007 9e-005 8e-006 7: -4.6340e-002 -4.6343e-002 2e-006 2e-009 9e-007 8e-008 8: -4.6341e-002 -4.6341e-002 2e-008 2e-011 9e-009 8e-010 Optimal solution found. Maximin return (%): 4.63414537166 Maximin money allocation matrix: [ 2.31e-006 7.32e+001] [ 2.68e+001 1.53e-006] Profit if Sharapova wins: [ 4.63e+000] Profit if Kirilenko wins: [ 4.63e+000] Total amount at stake: 99.999998456
Since a solution has been found, we conclude that at least one arbitrage opportunity exists. Moreover, the maximin return is and, hence, no matter what fate does happen to choose, we have a guaranteed profit of at least . Indeed, note that regardless of which Maria wins the tennis match, the profit will be for a budget of . The money allocation matrix is approximately
As we have rounded off the money allocation matrix produced by the CVXOPT script, the profits will deviate slightly from the maximin ones:
Profit if Sharapova wins: [ 4.68e+000] Profit if Kirilenko wins: [ 4.52e+000] Total amount at stake: 100.0
Note that the profit in case Sharapova wins is slightly increased, whereas the profit in case Kirilenko wins is slightly decreased.
How “good” is the maximin solution? Let us compare the maximin solution we have just obtained with the mere constraint-satisfying solution we found before:
Profit if Sharapova wins: [ 2.71e+000] Profit if Kirilenko wins: [ 9.14e-001] Total amount at stake: 80.4618403492
where we have a return of in case Sharapova wins, and a return of in case Kirilenko wins. It is clear that the maximin solution is superior, not only because the returns are higher, but also because the variance of the returns is considerably lower.