7 ms·

Finding arbitrage opportunities with Linear Programming (includes Python script)

47 points by Nezvanov 16y ago

dansingerman 16y ago
Finding arbitrages is the easy bit. (Ok it's not that easy) The tricky bit is making sure you get both bets on before the arbitrage opportunity disappears. There are many bots already out there scooping up arbitrages, and the bookie price algorithms will rapidly close these as bets are made, leaving a small window of opportunity. Also, most price movements (and therefore arbitrages) are when events are in-running: in these cases bookies enforce a delay before your bet is processed, which makes it doubly hard that both bets of your arbitrage get successfully placed.
- notahacker 16y ago
  The other issue is the problem of successive gains being wiped out by a bookmaker reneging on the quoted odds; most bookies have a "palpable error" clause which allows them to void bets on inappropriate odds, at their own discretion Differences between bookmakers' rules in some markets regarding refunds for cancelled games, retirements, ties etc. can also leave you losing both sides of a bet in some instances. Human judgement is still better than algorithms at judging the risk of the above happening.
- noname123 16y ago
  This. Arbitrage is all about execution speed. Free-money by definition is scarce. Assume you just sold the put and need to buy the call on the other side, some one else may buy that cheap call and the next block of call's might be more expensive and force you to eat a loss on your trading. In options market, some brokers allows you to do a multi-leg execution although the execution might be poor and oftentimes you might just get the market price. A safer way to play sports betting is do a rebate arbitrage which is to find bookmakers with two different lines in really close games and ensure that you just break even. Most bookmakers have a 10% bonus that you could cash out if you bet more than 10 times (bonus for being a liquidity provider a la the stock exchange), but it's more tedious and you have to deal with parking your money in the Cayman Island's due to US ban on online sports betting.
  - bryanh 16y ago
    Isn't it possible to require the "scarcer" or most off-priced resource to be the first resource to be acquired? Only then would you purchase the opposite, more common resource. Is that feasible? (Pardon my ignorance if not...)
- Nezvanov 16y ago
  The author of the blog post considered bookmakers as the ones laying the outcomes. What if one considers the layers as other bettors in a betting exchange? This scenario would be more interesting than trying to arbitrage bookies. Many bettors do bet based on emotion or some voodoo magic. Betting exchanges like BetFair are not laying anything, so they don't care. If some smart bettor is arbitraging the other bettors, the betting exchange is more than happy to collect a fee off the arbitrageur's profits.
  - notahacker 16y ago
    Betting exchanges are also even more watched by people looking for arbitrage opportunities than the major bookmakers and more volatile in the short run (often they'll be used to form one side of an arbitrage bet). You're dealing with a more knowledgeable betting crowd and rates that are corrected more quickly by market forces (and a spread of unmatched bets/lay options that have already been placed). As the betting exchange fees/commissions still drive a wedge between effective market rates on the betting and laying side you have to be even quicker to snag the profit (or correctly predict the direction of the movement of odds between placing the bet and the lay)
- dedward 16y ago
  I dont' know about Europe - but "boookie price algorithms" is generally a few guys sitting behind some computers adjusting odds and prices to try to balance out their perceived risk against what the market wants to bet on - so they try ot balance the books and keep their customers.
ojbyrne 16y ago
I know this is a blog post but it seems weird not to have any academic references, which makes this look like it's new or novel research, which it isn't. Perhaps its just me.
- Nezvanov 16y ago
  If it were novel research, the author would have been an idiot to blog it instead of publishing it in some peer-reviewed journal. No one claimed that it was novel. I thought it was interesting, that's why I submitted it to HN.
  - ojbyrne 16y ago
    As I said, perhaps it was just me. But how hard is a footnote?
- RodCarvalho 16y ago
  I am the author of the post. Your criticism is valid. There are a number of academic papers on fixed-odds betting. Too many, in fact. Here are some: http://www.ncer.edu.au/papers/documents/WPNo48.pdf http://www.ncer.edu.au/papers/documents/WPNo48.pdf http://www.jstor.org/stable/2353237 http://www.jstor.org/stable/2353237 http://www.jstor.org/stable/2240227 http://www.jstor.org/stable/2240227 http://www.jstor.org/stable/2554281 http://www.jstor.org/stable/2554281 Unfortunately, betting is far from my research field and I don't have the time to read the relevant literature. Since I don't have the time to read the papers, it would be wrong to cite them. People do that in academia all the time for political reasons, but this is a blog post, and I am not trying to please any academics. As I never claimed that my approach was a novelty, I don't see anything unethical in not citing papers. I didn't read any papers, I just came up with a simple mathematical model that any undergrad who studied linear programming should be able to come up with. Although I do not cite papers, please note that I refer to Minka's cookbook on advanced matrix theory, and Shor's comment on MathOverflow on the feasibility of linear programs.
geuis 16y ago
This is fascinating, but I have literally no idea what 99% of that math is. Where would I begin studying to be able to understand what is being described in those formulae?
- RodCarvalho 16y ago
  The crux of the matter is the linear program. All that math using vec(), diag(), and Hadamard / Kronecker products serves only to build the Q matrix. If the numbers of bookies and outcomes are small, then you can build the Q matrix by hand (like I did in the example at the end of the post). However, if m and n are relatively large, then it's nice to have an algorithm that builds the Q matrix automatically. Note that vec() and diag() in MATLAB are reshape() and diag(). The Kronecker product in MATLAB is kron(). If one's acquainted with the esoteric matrix operations being used, then it's very easy to convert the math into code. If you know basic matrix theory, and you learn the basics of linear programming: http://en.wikipedia.org/wiki/Linear_programming http://en.wikipedia.org/wiki/Linear_programming then the following matrix cookbook should contain all the recipes (vec(), diag(), Kronecker / Hadamard products) you need to follow my blog post: http://research.microsoft.com/en-us/um/people/minka/papers/matrix/ http://research.microsoft.com/en-us/um/people/minka/papers/m... Any questions, feel free to ask.
  - geuis 16y ago
    Thanks. Wow, I still have next to no idea of what you're describing but I'll happily take a look at the links. It sounds like I should start by learning about basic matrix theory then?
    - RodCarvalho 16y ago
      The ideas are simple. Instead of having a double sum, we can have a matrix product of the form 1_m^T X 1_n, which is nothing more than a compact way of writing the sum of all the entries of matrix X. Note that vec(X) is a mn-dimensional vector that contains the n stacked columns of X. Hence, 1_m^T X 1_n = 1_mn^T vec(X) which is an inner product. Note that the equality 1_mn^T vec(X) = c defines a hyper-plane, whereas the inequality 1_mn^T vec(X) <= c defines a half-space: http://en.wikipedia.org/wiki/Half-space http://en.wikipedia.org/wiki/Half-space The intersection of half-spaces defines a polytope, which is nothing more than the higher dimensional equivalent of a polyhedron. Take a look at Boyd & Vanderberghe's book on Convex Optimization for details: http://www.stanford.edu/~boyd/cvxbook/ http://www.stanford.edu/~boyd/cvxbook/
geebee 16y ago
This is an aside... but does anyone know how well this python optimization library (cvxopt) performs relative to CPLEX?
- RodCarvalho 16y ago
  I don't know the answer to that. If somebody does, that person is probably Erwin: http://yetanothermathprogrammingconsultant.blogspot.com/ http://yetanothermathprogrammingconsultant.blogspot.com/
dedward 16y ago
That's the interesting theoretical bit. The reality bit is where you have to ensure that you can get both bets checked in with the bookie(s) involved at the price you wanted - and arbitrage opportunities tend to show up more when the market is moving fast. Further, just like the stock market, arbitrage acts to keep the market stable- this is why most bookies have more or less the same odds on the same games at the same price. One also must factor in the transactional costs in moving money around depending on who you are using for bookies, and also realize there are already lots of guys out there running software 24/7 looking for arbitrage across the entire bookmaker landscape globally - so such opportunities tend to not last for long. The more "fun" opportunity is the middle - when a line moves so much during the time leading up to a game that a guy can make a bet with the same bookie that he wins on no matter what, or at least can't lose on (at worst it's a push - no loss). To find those you have to bet early on what are likely to be fast moving lines, and then be quick enough to get your bets in (and have them accepted)

47 points by Nezvanov 16y ago

Finding arbitrages is the easy bit. (Ok it's not that easy) The tricky bit is making sure you get both bets on before the arbitrage opportunity disappears. There are many bots already out there scooping up arbitrages, and the bookie price algorithms will rapidly close these as bets are made, leaving a small window of opportunity. Also, most price movements (and therefore arbitrages) are when events are in-running: in these cases bookies enforce a delay before your bet is processed, which makes it doubly hard that both bets of your arbitrage get successfully placed.

notahacker 16y ago
The other issue is the problem of successive gains being wiped out by a bookmaker reneging on the quoted odds; most bookies have a "palpable error" clause which allows them to void bets on inappropriate odds, at their own discretion Differences between bookmakers' rules in some markets regarding refunds for cancelled games, retirements, ties etc. can also leave you losing both sides of a bet in some instances. Human judgement is still better than algorithms at judging the risk of the above happening.
noname123 16y ago
This. Arbitrage is all about execution speed. Free-money by definition is scarce. Assume you just sold the put and need to buy the call on the other side, some one else may buy that cheap call and the next block of call's might be more expensive and force you to eat a loss on your trading. In options market, some brokers allows you to do a multi-leg execution although the execution might be poor and oftentimes you might just get the market price. A safer way to play sports betting is do a rebate arbitrage which is to find bookmakers with two different lines in really close games and ensure that you just break even. Most bookmakers have a 10% bonus that you could cash out if you bet more than 10 times (bonus for being a liquidity provider a la the stock exchange), but it's more tedious and you have to deal with parking your money in the Cayman Island's due to US ban on online sports betting.
- bryanh 16y ago
  Isn't it possible to require the "scarcer" or most off-priced resource to be the first resource to be acquired? Only then would you purchase the opposite, more common resource. Is that feasible? (Pardon my ignorance if not...)
Nezvanov 16y ago
The author of the blog post considered bookmakers as the ones laying the outcomes. What if one considers the layers as other bettors in a betting exchange? This scenario would be more interesting than trying to arbitrage bookies. Many bettors do bet based on emotion or some voodoo magic. Betting exchanges like BetFair are not laying anything, so they don't care. If some smart bettor is arbitraging the other bettors, the betting exchange is more than happy to collect a fee off the arbitrageur's profits.
- notahacker 16y ago
  Betting exchanges are also even more watched by people looking for arbitrage opportunities than the major bookmakers and more volatile in the short run (often they'll be used to form one side of an arbitrage bet). You're dealing with a more knowledgeable betting crowd and rates that are corrected more quickly by market forces (and a spread of unmatched bets/lay options that have already been placed). As the betting exchange fees/commissions still drive a wedge between effective market rates on the betting and laying side you have to be even quicker to snag the profit (or correctly predict the direction of the movement of odds between placing the bet and the lay)
dedward 16y ago
I dont' know about Europe - but "boookie price algorithms" is generally a few guys sitting behind some computers adjusting odds and prices to try to balance out their perceived risk against what the market wants to bet on - so they try ot balance the books and keep their customers.

ojbyrne 16y ago

I know this is a blog post but it seems weird not to have any academic references, which makes this look like it's new or novel research, which it isn't. Perhaps its just me.

Nezvanov 16y ago
If it were novel research, the author would have been an idiot to blog it instead of publishing it in some peer-reviewed journal. No one claimed that it was novel. I thought it was interesting, that's why I submitted it to HN.
- ojbyrne 16y ago
  As I said, perhaps it was just me. But how hard is a footnote?
RodCarvalho 16y ago
I am the author of the post. Your criticism is valid. There are a number of academic papers on fixed-odds betting. Too many, in fact. Here are some: http://www.ncer.edu.au/papers/documents/WPNo48.pdf http://www.ncer.edu.au/papers/documents/WPNo48.pdf http://www.jstor.org/stable/2353237 http://www.jstor.org/stable/2353237 http://www.jstor.org/stable/2240227 http://www.jstor.org/stable/2240227 http://www.jstor.org/stable/2554281 http://www.jstor.org/stable/2554281 Unfortunately, betting is far from my research field and I don't have the time to read the relevant literature. Since I don't have the time to read the papers, it would be wrong to cite them. People do that in academia all the time for political reasons, but this is a blog post, and I am not trying to please any academics. As I never claimed that my approach was a novelty, I don't see anything unethical in not citing papers. I didn't read any papers, I just came up with a simple mathematical model that any undergrad who studied linear programming should be able to come up with. Although I do not cite papers, please note that I refer to Minka's cookbook on advanced matrix theory, and Shor's comment on MathOverflow on the feasibility of linear programs.

geuis 16y ago

This is fascinating, but I have literally no idea what 99% of that math is. Where would I begin studying to be able to understand what is being described in those formulae?

RodCarvalho 16y ago
The crux of the matter is the linear program. All that math using vec(), diag(), and Hadamard / Kronecker products serves only to build the Q matrix. If the numbers of bookies and outcomes are small, then you can build the Q matrix by hand (like I did in the example at the end of the post). However, if m and n are relatively large, then it's nice to have an algorithm that builds the Q matrix automatically. Note that vec() and diag() in MATLAB are reshape() and diag(). The Kronecker product in MATLAB is kron(). If one's acquainted with the esoteric matrix operations being used, then it's very easy to convert the math into code. If you know basic matrix theory, and you learn the basics of linear programming: http://en.wikipedia.org/wiki/Linear_programming http://en.wikipedia.org/wiki/Linear_programming then the following matrix cookbook should contain all the recipes (vec(), diag(), Kronecker / Hadamard products) you need to follow my blog post: http://research.microsoft.com/en-us/um/people/minka/papers/matrix/ http://research.microsoft.com/en-us/um/people/minka/papers/m... Any questions, feel free to ask.
- geuis 16y ago
  Thanks. Wow, I still have next to no idea of what you're describing but I'll happily take a look at the links. It sounds like I should start by learning about basic matrix theory then?
  - RodCarvalho 16y ago
    The ideas are simple. Instead of having a double sum, we can have a matrix product of the form 1_m^T X 1_n, which is nothing more than a compact way of writing the sum of all the entries of matrix X. Note that vec(X) is a mn-dimensional vector that contains the n stacked columns of X. Hence, 1_m^T X 1_n = 1_mn^T vec(X) which is an inner product. Note that the equality 1_mn^T vec(X) = c defines a hyper-plane, whereas the inequality 1_mn^T vec(X) <= c defines a half-space: http://en.wikipedia.org/wiki/Half-space http://en.wikipedia.org/wiki/Half-space The intersection of half-spaces defines a polytope, which is nothing more than the higher dimensional equivalent of a polyhedron. Take a look at Boyd & Vanderberghe's book on Convex Optimization for details: http://www.stanford.edu/~boyd/cvxbook/ http://www.stanford.edu/~boyd/cvxbook/

geebee 16y ago

This is an aside... but does anyone know how well this python optimization library (cvxopt) performs relative to CPLEX?

RodCarvalho 16y ago
I don't know the answer to that. If somebody does, that person is probably Erwin: http://yetanothermathprogrammingconsultant.blogspot.com/ http://yetanothermathprogrammingconsultant.blogspot.com/

dedward 16y ago

That's the interesting theoretical bit. The reality bit is where you have to ensure that you can get both bets checked in with the bookie(s) involved at the price you wanted - and arbitrage opportunities tend to show up more when the market is moving fast. Further, just like the stock market, arbitrage acts to keep the market stable- this is why most bookies have more or less the same odds on the same games at the same price. One also must factor in the transactional costs in moving money around depending on who you are using for bookies, and also realize there are already lots of guys out there running software 24/7 looking for arbitrage across the entire bookmaker landscape globally - so such opportunities tend to not last for long. The more "fun" opportunity is the middle - when a line moves so much during the time leading up to a game that a guy can make a bet with the same bookie that he wins on no matter what, or at least can't lose on (at worst it's a push - no loss). To find those you have to bet early on what are likely to be fast moving lines, and then be quick enough to get your bets in (and have them accepted)