Imagine that we want to bet on an event with possible outcomes, and that there are bookmakers taking bets on those outcomes. Note that the odds are known at the time the bets are placed, i.e., we have fixed-odds betting instead of pari-mutuel betting.
We would like to know how to allocate our (limited) money, i.e., how much to bet on each outcome at each bookmaker. As we cannot foresee the future, we would very much like to lock in risk-less profits. In other words, we would like to find arbitrage opportunities (aka: “arbs”). In this post we discuss how, given the (fixed) odds posted by bookmakers, we can detect the existence of arbitrage opportunities.
Odds, Outcomes, and Profit
Let , and . Suppose that the decimal odds offered by bookmaker for outcome are . Let the odds matrix be the following
Let be the amount of money that we bet on outcome at bookmaker , and let
be the money allocation matrix. Since we have a limited amount of money available, , we must impose the inequality constraint
to ensure that we do not spend more than what we have. Let . We introduce binary variables , where
and we define . Let be the set of all admissible vectors. The outcomes are mutually exclusive if
If the outcomes are mutually exclusive, then there are only admissible vectors. If the outcomes are not mutually exclusive, then the number of admissible vectors is .
The odds for outcome offered by bookmaker are . Hence, if we bet on outcome at bookmaker and outcome does occur, then we get paid and make a profit of . However, if outcome does not occur, we make a profit of . Thus, our profit from betting on outcome at bookmaker is
Betting on all outcomes and at all bookmakers, our total profit is
where is chosen by fate, is our choice, and is the bookmakers’ choice. Note that and are variables, whereas the odds are parameters. Suppose we want to bet on the outcomes of a tennis match, say, Sharapova versus Kirilenko; as soon as the tennis match is over, vector is known and, thus, we know our profit / loss.
Let us define
and let be the diagonal matrix whose diagonal entries are the entries of vector . Moreover, let be the -dimensional vector of ones. Then, we can write in a more compressed form, as follows
Finally, we can write the total profit more economically, as follows
where is the Hadamard product (entry-wise matrix multiplication) of matrices and .
Let denote the vectorization operator, which stacks a given matrix’s columns in one large column vector. Note that if we apply operator to a scalar, we obtain the same scalar. Hence, we have that . Thus,
because . It can be shown that
and, hence, the total profit is
It’s not difficult to show that
and, thus, we obtain
which is the inner product of two -dimensional vectors. The usefulness of writing the profit as an inner product will be evident later on. Note that the inequality constraint
can be written in a rather more compressed form as . Or, using vectorization, as .
Given the odds matrix , the set of admissible vectors , and a budget , we would like to find a money allocation matrix such that and
In other words, we would like to allocate the money such that, no matter the outcomes, we do not lose money. This is a constraint satisfaction problem. To be more precise, we have to satisfy inequality constraints.
From a game-theoretic viewpoint, we are playing a sequential game with fate. We play first, by choosing . Fate plays next by choosing . We have an arbitrage opportunity when, no matter what fate does happen to choose, we make a profit. We want to “Dutch” fate.
Betting on Mutually Exclusive Outcomes
If , i.e., if only one entry in can take take the value , then the outcomes are mutually exclusive. Why is the case where the outcomes are mutually exclusive interesting? The reason is that when the outcomes are mutually exclusive, the set of admissible vectors has minimal cardinality, , and the elements of are easy to index.
If the outcomes are mutually exclusive, then
i.e., the elements of are the vectors of the canonical basis for . Let us denote
so that . Let be a -dimensional decision vector, and . Then, the arbitrage condition
can be written as inequality constraints
Let be the matrix whose -th column is , then the arbitrage inequalities can be written simply as , where is the -dimensional vector whose entries are all zero.
Due to our limited budget, we have the inequality . The arbitrage inequalities can also be written as . Hence, we have inequalities
If this polytope is empty, there are no arbitrage opportunities. If the polytope is non-empty, there is at least one arbitrage opportunity. Who would have thought that betting arbitrage could be studied using Discrete Geometry? ;-)
Determining whether the polytope is nonempty is as hard as solving as linear program (so says Peter Shor). Hence, we can determine if the polytope is non-empty by solving a linear program with an arbitrary objective function
If this linear program is feasible, then an arbitrage opportunity does exist. Any solution that the LP solver returns will be an “arb” :-)
We have considered mutually exclusive outcomes in this section. If the outcomes are not mutually exclusive, then and it gets harder to enumerate all the admissible vectors. However, the exact same approach can be used, although we will have more than arbitrage inequalities.
Example: Sharapova versus Kirilenko
Suppose that bookmakers are posting odds for the Sharapova versus Kirilenko tennis match we mentioned before. Suppose further that the bookies are offering odds for mutually exclusive outcomes: Sharapova wins, or Kirilenko wins. They can’t both win the match, of course. One thing that we do know beforehand is that the winner will be called Maria ;-)
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. The following Python 2.5 / CVXOPT script solves a linear program to determine whether there are arbitrage opportunities:
from cvxopt import matrix from cvxopt import solvers # available budget c = 100 # decimal odds posted by the bookies omega_11 = 1.25 omega_12 = 1.43 omega_21 = 3.90 omega_22 = 2.85 # build q vectors q1 = matrix([(omega_11 - 1.0), -1.0, (omega_12 - 1.0), -1.0]) q2 = matrix([-1.0, (omega_21 - 1.0), -1.0, (omega_22 - 1.0)]) # build 4x4 identity matrix Id = matrix([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]) # --------------- # linear program # --------------- # build objective vector f = matrix(0.0, (4,1)) # build inequality constraint matrices A = matrix([matrix(1.0, (1,4)), -q1.T, -q2.T, -Id]) b = matrix([c, matrix(0.0, (6,1))]) # solve linear program solvers.options['show_progress'] = True solution = solvers.lp(f, A, b) # print solution and profits x = solution['x'] print "\nMoney allocation:" 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: 0.0000e+000 -1.0000e+002 1e+002 2e-001 2e+000 1e+000 1: 0.0000e+000 -1.7972e+001 3e+001 4e-002 5e-001 3e+000 2: 0.0000e+000 -5.3598e-001 6e-001 1e-003 2e-002 3e-001 3: 0.0000e+000 -5.3759e-003 6e-003 1e-005 2e-004 3e-003 4: 0.0000e+000 -5.3757e-005 6e-005 1e-007 2e-006 3e-005 5: 0.0000e+000 -5.3757e-007 6e-007 1e-009 2e-008 3e-007 6: 0.0000e+000 -5.3757e-009 6e-009 1e-011 2e-010 3e-009 Optimal solution found. Money allocation: [ 1.09e+001] [ 2.07e+001] [ 4.86e+001] [ 2.21e-001] Profit if Sharapova wins: [ 2.71e+000] Profit if Kirilenko wins: [ 9.14e-001] Total amount at stake: 80.4618403492
Since a solution has been found, we conclude that the linear program is feasible and, therefore, at least one arbitrage opportunity exists. Note that the profit is positive regardless of who wins the match. The money allocation matrix is approximately
and the total amount at stake is approximately , for a budget of . Who is paying the “free lunch”? ;-)