December | 2010 | Rod Carvalho

Archive for December, 2010

Fixed-Odds Betting Arbitrage II

December 28, 2010

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.

__________

Arbitrage

Given the odds matrix $\Omega$ , the set of admissible $\theta$ vectors $\Theta \subseteq \mathbb{F}_2^m$ , and a budget $c > 0$ , we would like to find a money allocation matrix $X$ such that $1_{m n}^T \text{vec}(X) \leq c$ and

$P (\theta, X; \Omega) \geq 0, \quad{} \forall \theta \in \Theta$

so that, regardless of what $\theta$ vector fate happens to choose, we make a profit. Let us enumerate the $\theta$ vectors, $\Theta = \{\theta^{(1)}, \theta^{(2)}, \dots, \theta^{(|\Theta|)}\}$ , where $m \leq |\Theta|\leq 2^m$ . Since $P (\theta, X; \Omega) = \text{vec}^T \left( R (\theta; \Omega) \right) \text{vec}(X)$ , the $|\Theta|$ arbitrage inequalities can be written as

$\left[\begin{array}{c} \text{vec}^T \left( R (\theta^{(1)}; \Omega) \right) \\ \text{vec}^T \left( R (\theta^{(2)}; \Omega) \right)\\ \vdots \\ \text{vec}^T \left( R (\theta^{|\Theta|}; \Omega) \right)\end{array}\right] \text{vec}(X) \geq \left[\begin{array}{c} 0 \\ 0 \\ \vdots \\ 0\end{array}\right]$ .

Let $\tilde{x} := \text{vec}(X)$ . Hence, the inequality $1_{m n}^T \text{vec}(X) \leq c$ can be rewritten as $1_{m n}^T \tilde{x} \leq c$ . Let us define $q_k := \text{vec} \left( R (\theta^{(k)}; \Omega) \right)$ , and let

$Q := \left[\begin{array}{cccc} q_1 & q_2 & \ldots & q_{|\Theta|}\end{array}\right]$

be the $m n \times |\Theta|$ matrix whose $k$ -th column is $q_k$ . Thus, the $|\Theta|$ arbitrage inequalities can be written more compactly as $Q^T \tilde{x} \geq 0_{|\Theta|}$ or, equivalently, as $-Q^T \tilde{x} \leq 0_{|\Theta|}$ . Hence, so far, we have $1+|\Theta|$ inequality constraints

$\left[\begin{array}{c} 1_{mn}^T\\ -Q^T\end{array}\right] \tilde{x} \leq \left[\begin{array}{c} c \\ 0_{|\Theta|}\end{array}\right]$ .

Since the $m n$ entries of matrix $X$ must be non-negative, we have $m n$ additional inequality constraints $\tilde{x} \geq 0_{m n}$ or, equivalently, $- I_{m n} \tilde{x} \leq 0_{m n}$ , where $I_{m n}$ is the $m n \times m n$ identity matrix.

To make the model more realistic, let us suppose that the amount of money being betted on outcome $i \in [m]$ at bookmaker $j \in [n]$ is bounded above by $b_{ij} \geq 0$ , i.e., $0 \leq x_{ij} \leq b_{ij}$ . 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 $b_{ij} = 0$ one can make sure that no money will be betted on a certain outcome at a certain bookmaker. If bookmaker $j$ is not imposing any upper bound on $x_{ij}$ then we can make $b_{ij} = c$ , i.e., the most we can bet on outcome $i$ at bookmaker $j$ is our budget $c > 0$ . Let

$B = \left[\begin{array}{cccc}b_{11} & b_{12} & \ldots & b_{1n}\\b_{21} & b_{22} & \ldots & b_{2n}\\\vdots & \vdots & \ddots & \vdots\\b_{m1} & b_{m2} & \ldots & b_{mn}\\\end{array}\right]$

be the matrix of upper bounds, and let $\tilde{b} := \text{vec}\left(B\right)$ . Then, the $m n$ inequalities $x_{ij} \leq b_{ij}$ can be written more compactly as $\tilde{x} \leq \tilde{b}$ or, equivalently, as $I_{m n} \tilde{x} \leq \tilde{b}$ .

Finally, we have a total of $1+|\Theta| + 2 m n$ inequality constraints

$\left[\begin{array}{c} 1_{mn}^T\\ -Q^T\\ - I_{m n}\\ I_{m n}\end{array}\right] \tilde{x} \leq \left[\begin{array}{c} c \\ 0_{|\Theta|} \\ 0_{m n} \\ \tilde{b}\end{array}\right]$ .

If we can find an $m n$ -dimensional decision vector $\tilde{x}$ that satisfies the $1+|\Theta| + 2 m n$ inequality constraints above, then we conclude that an arbitrage opportunity does exist. This is a constraint satisfaction problem.

As we discussed before, the $1+|\Theta| + 2 m n$ inequality constraints define a polytope in $\mathbb{R}^{m n}$ . 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

$\begin{array}{ll} \displaystyle\min_{\tilde{x} \in \mathbb{R}^{mn}} & 0_{m n}^T \tilde{x} \\ \text{subject to} & \left[\begin{array}{c} 1_{mn}^T\\ -Q^T\\ - I_{m n}\\ I_{m n}\end{array}\right] \tilde{x} \leq \left[\begin{array}{c} c \\ 0_{|\Theta|} \\ 0_{m n} \\ \tilde{b}\end{array}\right]\end{array}$

where we chose $0_{m n}^T \tilde{x}$ , 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 $\alpha \geq 0$ regardless of what $\theta$ is chosen by fate, i.e.,

$P (\theta, X; \Omega) \geq \alpha c, \quad{} \forall \theta \in \Theta$ .

Hence, instead of the linear inequality constraints $Q^T \tilde{x} \geq 0_{|\Theta|}$ , we now have the linear inequality constraints $Q^T \tilde{x} \geq \alpha c 1_{|\Theta|}$ or, equivalently, $-Q^T \tilde{x} \leq -\alpha c 1_{|\Theta|}$ . Suppose also that the bookmakers impose no upper bounds on the $x_{ij}$ . Hence, we have $b_{ij} = c$ , and $\tilde{b} = c 1_{m n}$ . We then have the following $1+|\Theta| + 2 m n$ inequality constraints

$\left[\begin{array}{c} 1_{mn}^T\\ -Q^T\\ - I_{m n}\\ I_{m n}\end{array}\right] \tilde{x} \leq \left[\begin{array}{c} c \\ -\alpha c 1_{|\Theta|} \\ 0_{m n} \\ c 1_{m n}\end{array}\right]$ .

Yet once again, we have a constraint satisfaction problem that can be solved via linear programming with an arbitrary objective function

$\begin{array}{ll} \displaystyle\min_{\tilde{x} \in \mathbb{R}^{mn}} & 0_{m n}^T \tilde{x} \\ \text{subject to} & \left[\begin{array}{c} 1_{mn}^T\\ -Q^T\\ - I_{m n}\\ I_{m n}\end{array}\right] \tilde{x} \leq \left[\begin{array}{c} c \\ -\alpha c 1_{|\Theta|} \\ 0_{m n} \\ c 1_{m n}\end{array}\right]\end{array}$ .

Starting with a small $\alpha$ , say $\alpha = 0.01$ , 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 $\alpha$ until the linear program that solves the constraint satisfaction problem is no longer feasible, we can find the maximum $\alpha$ via optimization. Note that $Q^T \tilde{x} \geq \alpha c 1_{|\Theta|}$ can be rewritten as

$\alpha c 1_{|\Theta|} - Q^T \tilde{x} \leq 0_{|\Theta|}$ .

Hence, we can find the maximum $\alpha$ that yields a feasible linear program by solving the following maximization problem in $(\alpha, \tilde{x})$ with the additional inequality constraint $\alpha \geq 0$ or, equivalently, $-\alpha \leq 0$

$\begin{array}{ll} \displaystyle\max_{(\alpha, \tilde{x}) \in \mathbb{R}^{1 + mn}} & \left[\begin{array}{cc} 1 & 0_{m n}^T \end{array}\right]\left[\begin{array}{c} \alpha \\ \tilde{x}\end{array}\right] \\\\ \text{subject to} & \left[\begin{array}{cc} -1 & 0_{m n}^T\\ 0 & 1_{mn}^T\\ c 1_{|\Theta|} & -Q^T\\ 0_{m n} & - I_{m n}\\ 0_{m n} & I_{m n}\end{array}\right] \left[\begin{array}{c} \alpha \\ \tilde{x}\end{array}\right] \leq \left[\begin{array}{c} 0\\ c \\ 0_{|\Theta|} \\ 0_{m n} \\ c 1_{m n}\end{array}\right]\end{array}$

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 $\alpha$ is the same as minimizing $-\alpha$ , we can rewrite the maximization problem as a minimization problem, as follows

$\begin{array}{ll} \displaystyle\min_{(\alpha, \tilde{x}) \in \mathbb{R}^{1 + mn}} & \left[\begin{array}{cc} -1 & 0_{m n}^T \end{array}\right]\left[\begin{array}{c} \alpha \\ \tilde{x}\end{array}\right] \\\\ \text{subject to} & \left[\begin{array}{cc} -1 & 0_{m n}^T\\ 0 & 1_{mn}^T\\ c 1_{|\Theta|} & -Q^T\\ 0_{m n} & - I_{m n}\\ 0_{m n} & I_{m n}\end{array}\right] \left[\begin{array}{c} \alpha \\ \tilde{x}\end{array}\right] \leq \left[\begin{array}{c} 0\\ c \\ 0_{|\Theta|} \\ 0_{m n} \\ c 1_{m n}\end{array}\right]\end{array}$

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 $\theta \in \Theta$ . Hence, we choose a money allocation matrix $X$ 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 $n = 2$ bookmakers are posting odds for a Sharapova versus Kirilenko match, and that the bookies are offering odds for $m = 2$ mutually exclusive outcomes: Sharapova wins, or Kirilenko wins. Imagine that the bookies posted the following decimal odds

$\Omega = \left[\begin{array}{cc} 1.25 & 1.43\\ 3.90 & 2.85\end{array}\right]$

which means that bookie #1 is offering odds $1.25$ for a Sharapova victory, whereas bookie #2 is offering odds $1.43$ for the same outcome. Note that $|\Theta| = 2$ and that the $Q$ matrix is

$Q = \left[\begin{array}{cc} 0.25 & -1\\ -1 & 2.90\\ 0.43 & -1\\ -1 & 1.85\end{array}\right]$ .

Assuming that the bookies impose no upper bounds on the $x_{ij}$ , then the maximin return and the maximin money allocation matrix can be found by solving the linear program

$\begin{array}{ll} \displaystyle\min_{(\alpha, \tilde{x}) \in \mathbb{R}^{5}} & \left[\begin{array}{cc} -1 & 0_{4}^T \end{array}\right]\left[\begin{array}{c} \alpha \\ \tilde{x}\end{array}\right] \\\\ \text{subject to} & \left[\begin{array}{cc} -1 & 0_{4}^T\\ 0 & 1_{4}^T\\ c 1_{2} & -Q^T\\ 0_{4} & - I_{4}\\ 0_{4} & I_{4}\end{array}\right] \left[\begin{array}{c} \alpha \\ \tilde{x}\end{array}\right] \leq \left[\begin{array}{c} 0\\ c \\ 0_{2} \\ 0_{4} \\ c 1_{4}\end{array}\right]\end{array}$

where $c > 0$ is our budget. The following Python 2.5 / CVXOPT script solves a linear program to determine whether there are arbitrage opportunities and, if so, what the maximin solution is:

 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[0]
 x = sol[1:5]

 # build money allocation matrix
 X = matrix([[sol[1], sol[2]],[sol[3], sol[4]]])

 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 $4.63\%$ and, hence, no matter what $\theta$ fate does happen to choose, we have a guaranteed profit of at least $4.63\%$ . Indeed, note that regardless of which Maria wins the tennis match, the profit will be $4.63$ for a budget of $c = 100$ . The money allocation matrix is approximately

$X = \left[\begin{array}{cc} 0.00 & 73.2\\ 26.8 & 0.00\end{array}\right]$ .

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 $3.37\%$ in case Sharapova wins, and a return of $1.14\%$ 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.

Tags:Arbitrage, Betting, Betting Arbitrage, CVXOPT, Fixed-Odds Betting, Linear Programming, Operations Research
Posted in Operations Research, Python | Leave a Comment »

Fixed-Odds Betting Arbitrage

December 20, 2010

Imagine that we want to bet on an event with $m \geq 2$ possible outcomes, and that there are $n \geq 2$ 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 $n$ bookmakers, we can detect the existence of arbitrage opportunities.

__________

Odds, Outcomes, and Profit

Let $[m] := \{1, 2, \dots, m\}$ , and $[n] := \{1, 2, \dots, n\}$ . Suppose that the decimal odds offered by bookmaker $j \in [n]$ for outcome $i \in [m]$ are $\omega_{ij} \geq 1$ . Let the $m \times n$ odds matrix be the following

$\Omega = \left[\begin{array}{cccc}\omega_{11} & \omega_{12} & \ldots & \omega_{1n}\\ \omega_{21} & \omega_{22} & \ldots & \omega_{2n}\\\vdots & \vdots & \ddots & \vdots\\ \omega_{m1} & \omega_{m2} & \ldots & \omega_{mn}\\\end{array}\right]$ .

Let $x_{ij} \geq 0$ be the amount of money that we bet on outcome $i \in [m]$ at bookmaker $j \in [n]$ , and let

$X = \left[\begin{array}{cccc}x_{11} & x_{12} & \ldots & x_{1n}\\x_{21} & x_{22} & \ldots & x_{2n}\\\vdots & \vdots & \ddots & \vdots\\x_{m1} & x_{m2} & \ldots & x_{mn}\\\end{array}\right]$

be the $m \times n$ money allocation matrix. Since we have a limited amount of money available, $c > 0$ , we must impose the inequality constraint

$\displaystyle\sum_{i \in [m]} \sum_{j \in [n]} x_{ij} \leq c$

to ensure that we do not spend more than what we have. Let $\mathbb{F}_2 := \{0,1\}$ . We introduce binary variables $\theta_1, \dots, \theta_m \in \mathbb{F}_2$ , where

$\theta_i = \begin{cases} 1, & \text{if outcome } i \text{ occurs}\\ 0, & \text{otherwise}\end{cases}$

and we define $\theta := \left(\theta_1, \theta_2, \ldots, \theta_m\right) \in \mathbb{F}_2^m$ . Let $\Theta \subseteq \mathbb{F}_2^m$ be the set of all admissible $\theta$ vectors. The $m$ outcomes are mutually exclusive if

$\theta_i = 1 \Rightarrow \theta_k = 0, \quad{} \forall k \in [m] \setminus \{i\}$ .

If the $m$ outcomes are mutually exclusive, then there are only $m$ admissible $\theta$ vectors. If the $m$ outcomes are not mutually exclusive, then the number of admissible $\theta$ vectors is $m \leq |\Theta|\leq 2^m$ .

The odds for outcome $i \in [m]$ offered by bookmaker $j \in [n]$ are $\omega_{ij}$ . Hence, if we bet $x_{ij} > 0$ on outcome $i$ at bookmaker $j$ and outcome $i$ does occur, then we get paid $\omega_{ij} x_{ij}$ and make a profit of $(\omega_{ij} - 1) x_{ij}$ . However, if outcome $i$ does not occur, we make a profit of $-x_{ij}$ . Thus, our profit from betting on outcome $i$ at bookmaker $j$ is

$p_{ij} = (\theta_i \omega_{ij} - 1 ) x_{ij}$ .

Betting on all outcomes and at all bookmakers, our total profit is

$P (\theta, X; \Omega) = \displaystyle\sum_{i \in [m]}\sum_{j \in [n]} p_{ij} = \displaystyle\sum_{i \in [m]}\sum_{j \in [n]} (\theta_i \omega_{ij} - 1 ) x_{ij}$

where $\theta$ is chosen by fate, $X$ is our choice, and $\Omega$ is the bookmakers’ choice. Note that $\theta$ and $X$ are variables, whereas the odds $\Omega$ 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 $\theta$ is known and, thus, we know our profit / loss.

Let us define

$R (\theta; \Omega) := \left[\begin{array}{cccc}(\theta_1\omega_{11} - 1) & (\theta_1\omega_{12} - 1) & \ldots & (\theta_1\omega_{1n} - 1)\\ (\theta_2\omega_{21} - 1) & (\theta_2\omega_{22} - 1) & \ldots & (\theta_2\omega_{2n} - 1)\\\vdots & \vdots & \ddots & \vdots\\ (\theta_m\omega_{m1} - 1) & (\theta_m\omega_{m2} - 1) & \ldots & (\theta_m\omega_{mn} - 1)\\\end{array}\right]$

and let $\text{diag}(\theta)$ be the $m \times m$ diagonal matrix whose $m$ diagonal entries are the entries of vector $\theta$ . Moreover, let $1_m = (1,1,\dots,1)$ be the $m$ -dimensional vector of ones. Then, we can write $R (\theta; \Omega)$ in a more compressed form, as follows

$R (\theta; \Omega) = \text{diag}(\theta) \Omega - 1_m 1_n^T$ .

Finally, we can write the total profit $P (\theta, X; \Omega)$ more economically, as follows

$P (\theta, X; \Omega) = 1_m^T \left(R (\theta; \Omega) \circ X\right) 1_n$

where $R (\theta; \Omega) \circ X$ is the Hadamard product (entry-wise matrix multiplication) of matrices $R (\theta; \Omega)$ and $X$ .

Let $\text{vec}(\cdot)$ denote the vectorization operator, which stacks a given matrix’s columns in one large column vector. Note that if we apply operator $\text{vec}(\cdot)$ to a scalar, we obtain the same scalar. Hence, we have that $\text{vec}(P (\theta, X; \Omega)) = P (\theta, X; \Omega)$ . Thus,

$P (\theta, X; \Omega) = \text{vec}\left(1_m^T \left(R (\theta; \Omega) \circ X\right) 1_n\right) = 1_{mn}^T \text{vec} \left(R (\theta; \Omega) \circ X\right)$

because $1_n^T \otimes 1_m^T = 1_{mn}^T$ . It can be shown that

$\text{vec} \left(R (\theta; \Omega) \circ X\right) = \text{diag}\left( \text{vec} \left( R (\theta; \Omega)\right) \right) \text{vec}(X)$

and, hence, the total profit is

$P (\theta, X; \Omega) = 1_{mn}^T \text{diag}\left( \text{vec} \left( R (\theta; \Omega)\right) \right) \text{vec}(X)$ .

It’s not difficult to show that

$1_{mn}^T \text{diag}\left( \text{vec} \left( R (\theta; \Omega)\right) \right) = \text{vec}^T \left( R (\theta; \Omega) \right)$

and, thus, we obtain

$P (\theta, X; \Omega) = \text{vec}^T \left( R (\theta; \Omega) \right) \text{vec}(X)$

which is the inner product of two $m n$ -dimensional vectors. The usefulness of writing the profit as an inner product will be evident later on. Note that the inequality constraint

$\displaystyle\sum_{i \in [m]} \sum_{j \in [n]} x_{ij} \leq c$

can be written in a rather more compressed form as $1_m^T X 1_n \leq c$ . Or, using vectorization, as $1_{m n}^T \text{vec}(X) \leq c$ .

__________

Arbitrage

$P (\theta, X; \Omega) \geq 0, \quad{} \forall \theta \in \Theta$ .

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 $|\Theta| + 1$ inequality constraints.

From a game-theoretic viewpoint, we are playing a sequential game with fate. We play first, by choosing $X$ . Fate plays next by choosing $\theta \in \Theta$ . We have an arbitrage opportunity when, no matter what $\theta$ fate does happen to choose, we make a profit. We want to “Dutch” fate.

__________

Betting on Mutually Exclusive Outcomes

If $1_m^T \theta = 1$ , i.e., if only one entry in $\theta$ can take take the value $1$ , then the $m$ 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 $\theta$ vectors $\Theta \subseteq \mathbb{F}_2^m$ has minimal cardinality, $|\Theta| = m$ , and the $m$ elements of $\Theta$ are easy to index.

If the outcomes are mutually exclusive, then

$\Theta = \left\{ \left[\begin{array}{c} 1 \\ 0 \\ \vdots \\ 0\end{array}\right], \left[\begin{array}{c} 0 \\ 1 \\ \vdots \\ 0\end{array}\right], \dots, \left[\begin{array}{c} 0 \\ 0 \\ \vdots \\ 1\end{array}\right] \right\}$

i.e., the $m$ elements of $\Theta$ are the vectors of the canonical basis for $\mathbb{R}^m$ . Let us denote

$\mathrm{e}_1 := \left[\begin{array}{c} 1 \\ 0 \\ \vdots \\ 0\end{array}\right], \quad{} \mathrm{e}_2 := \left[\begin{array}{c} 0 \\ 1 \\ \vdots \\ 0\end{array}\right], \dots, \quad{} \mathrm{e}_m := \left[\begin{array}{c} 0 \\ 0 \\ \vdots \\ 1\end{array}\right]$

so that $\Theta = \{\mathrm{e}_1, \mathrm{e}_2, \dots, \mathrm{e}_m\}$ . Let $\tilde{x} := \text{vec}(X)$ be a $m n$ -dimensional decision vector, and $q_i := \text{vec}\left( R (\mathrm{e}_i; \Omega)\right)$ . Then, the arbitrage condition

$P (\theta, X; \Omega) = \text{vec}^T \left( R (\theta; \Omega) \right) \text{vec}(X) \geq 0, \quad{} \forall \theta \in \Theta$

can be written as $m$ inequality constraints

$q_1^T \tilde{x} \geq 0, \quad{} q_2^T \tilde{x} \geq 0, \dots, \quad{} q_m^T \tilde{x} \geq 0$ .

Let $Q := \left[\begin{array}{cccc} q_1 & q_2 & \ldots & q_m\end{array}\right]$ be the $m n \times m$ matrix whose $i$ -th column is $q_i$ , then the $m$ arbitrage inequalities can be written simply as $Q^T \tilde{x} \geq 0_m$ , where $0_m$ is the $m$ -dimensional vector whose entries are all zero.

Due to our limited budget, we have the inequality $1_{mn}^T \tilde{x} \leq c$ . The $m$ arbitrage inequalities can also be written as $-Q^T \tilde{x} \leq 0_m$ . Hence, we have $1+m$ inequalities

$\left[\begin{array}{c} 1_{mn}^T\\ -Q^T\end{array}\right] \tilde{x} \leq \left[\begin{array}{c} c \\ 0_m\end{array}\right]$ .

From a geometric viewpoint, these $1+m$ inequalities correspond to the intersection of $1+m$ closed half-spaces in $\mathbb{R}^{mn}$ , which defines a polytope

$\left\{ \tilde{x} \in (\mathbb{R}_0^+)^{mn} : \left[\begin{array}{c} 1_{mn}^T \\ -Q^T\end{array}\right] \tilde{x} \leq \left[\begin{array}{c} c \\ 0_m\end{array}\right] \right\}$ .

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

$\begin{array}{ll} \displaystyle\min_{\tilde{x} \in \mathbb{R}^{mn}} & 0_{m n}^T \tilde{x} \\ \text{subject to} & \left[\begin{array}{c} 1_{mn}^T\\ -Q^T\end{array}\right] \tilde{x} \leq \left[\begin{array}{c} c \\ 0_m\end{array}\right], \quad{} \tilde{x} \geq 0_{m n}\end{array}$

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 $|\Theta| > m$ and it gets harder to enumerate all the admissible $\theta$ vectors. However, the exact same approach can be used, although we will have more than $m$ arbitrage inequalities.

__________

Example: Sharapova versus Kirilenko

Suppose that $n = 2$ bookmakers are posting odds for the Sharapova versus Kirilenko tennis match we mentioned before. Suppose further that the bookies are offering odds for $m = 2$ 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

$\Omega = \left[\begin{array}{cc} 1.25 & 1.43\\ 3.90 & 2.85\end{array}\right]$

which means that bookie #1 is offering odds $1.25$ for a Sharapova victory, whereas bookie #2 is offering odds $1.43$ 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

$X = \left[\begin{array}{cc} 10.9 & 48.6\\ 20.7 & 0.22\end{array}\right]$

and the total amount at stake is approximately $80.46$ , for a budget of $100$ . Who is paying the “free lunch”? ;-)

Tags:Arbitrage, Betting Arbitrage, CVXOPT, Fixed-Odds Betting, Linear Programming, Operations Research
Posted in Operations Research, Python | 10 Comments »

Rod Carvalho

Archive for December, 2010

Fixed-Odds Betting Arbitrage II

Fixed-Odds Betting Arbitrage

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Blogs

Haskell

Math Blogs

MATLAB

Python

Robotics

Software

Symbolic Computation

Powered by FeedBurner

Meta

Follow “Rod Carvalho”

December 2010
S	M	T	W	T	F	S
« Nov				Jan »
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Rod Carvalho

Archive for December, 2010

Fixed-Odds Betting Arbitrage II

Fixed-Odds Betting Arbitrage

Pages

Categories

Top Posts

Recent Posts

Recent Comments

Tag Cloud

Archives

Blog Stats

Artists

Blogs

Haskell

Math Blogs

MATLAB

Python

Robotics

Software

Symbolic Computation

Category Cloud

Powered by FeedBurner

Meta

Follow “Rod Carvalho”