Last time I discussed how the Kelly criterion optimizes your investment by maximizing your expected growth rate. The previous example was based on a coin tossing game. This time I will implement the optimization in a Haskell program to illustrate a more sophisticated example.
> module KellyCriterion where > > import qualified Data.Map as M
To do this I will leverage the power of Haskell blogs. One thing I need to do is compute expected values. Eric Kidd implements a probability monad. Unfortunately it doesn’t come with an expected value function, So instand I grab Martin Erwig and Steve Kollmansberger’s PFP library that Eric refers to.
> import Probability hiding (expected) -- pfp-jun06
Unfortunately even PFP’s expected value function isn’t quite general enough. Because this is just a blog post, I won’t bother fixing it right now. I will just write my own later. I did, however, replace all Floats with Doubles.
Next up, I need to optimize functions. For that I use automatic differentiation with Netwon’s method. Lennart Augustsson shows how this is can be done, but I will use my own implementation based on Vlad Andreev’s post.
> import Diff
For this example I am going to optimize a portfolio of claims in a 2008 U.S. Presidential Nomination Market. In particular, the 2008 Democratic Nomination Winner-Takes-All Market. At the time of writing there are four mutually exclusive claims available: CLIN_NOM, EDWA_NOM, OBAM_NOM, for Clinton, Edwards, and Obama winning the democratic nomination respectively, and DROF_NOM for some other candidate winning.
I define a Portfolio to be a collection of a number of claims, along with an amount of cash.
> data Portfolio a = Portfolio
> {cash :: a
> ,claims :: M.Map Claim a}
> deriving Show
>
> newPortfolio :: a -> Portfolio a
> newPortfolio cash = Portfolio cash M.empty
I abstract the portfolio over the type to represent the number of claims and cash. Normally I would use an integer type here, but I will need a Floating class to do continuous optimization later. So it is just easiest to leave this type abstract for now.
> type Claim = String
I identify claims with strings. If you know your list of claims at compile time, feel free to make an enumeration instead.
After the democratic nomination is over, this market closes and one of these 4 claims will pay out $1 per share. If one knows the winner one can compute the final value of the portfolio.
> close :: (Num a, Ord a) => Portfolio a -> Claim -> a > close portfolio winner = > cash portfolio + sum (map value (M.toList (claims portfolio))) > where > value (claim,held) | 0 <= held = if claim == winner > then held else 0 > | otherwise = if claim == winner > then 0 else -held
Some future markets, such as the Foresight Exchange, allow one to hold a negative number of claims by short selling a claim. This is allowed, so long as one covers one’s position by leaving $1 per share on deposit. If the claim sold short ends up winning, one’s deposit is used to cover that claim; however, if the claim does not win, the deposit is returned.
The IEM doesn’t allow shorting, but it can be simulated by purchasing a bundle of claims for $1 (analogous to the deposit), and then selling the one claim you want to short. In either case the interpretion of the value of negative numbers of claims is the same.
Given a winner, the growth rate is
log ((close portfolio winner) / initial_investment). One question I struggled with was what value to use for the initial_investment. By rearrange the above formula one gets log (close portfolio winner) - log initial_investment. The trick is to realize that one only cares about what the optimal portfolio is, not what the optimal growth rate is. Because log initial_investment is a constant, one can just drop it from the expression, and it will not affect where the optimal point occurs.
> growthRate :: (Floating a, Ord a) => Portfolio a -> Claim -> a > growthRate portfolio winner = log (close portfolio winner)
Given a probability distribution of each claim winning, one can compute a probability distribution of growth rates by using the probability functor. From this one can compute the expected growth rate of a portfolio.
> expectedGrowthRate :: > (Floating a, Ord a) => Dist Claim -> Portfolio a -> a > expectedGrowthRate distribution portfolio = > expected $ growthRate portfolio `fmap` distribution
Unfortunately the expected function from the PFP library always returns a Float and I need an arbitrary Floating value. The quick and dirty solution is to steel a sliver of code from them and tweak it to return an arbitrary Floating type. This is only a blog posting after all.
> expected :: (Floating a) => Dist a -> a > expected = sum . map (\(x,p)->x*(fromReal p)) . unD > > fromReal :: (Real a, Fractional b) => a -> b > fromReal = fromRational . toRational
The next step is to optimize the expected growth rate. To do this one needs the ability to adjust a portfolio by buying or selling claims at a particular price. The fact that one can short claims by covering one’s position throws a small wrinkle into an otherwise trivial computation. So to simplify things, I first wrote a function to sell one’s entire stake (positive or negative) in a claim.
> sellAll :: (Floating a, Ord a) => > Portfolio a -> Claim -> a -> Portfolio a > sellAll portfolio claim price = > Portfolio cash' claims' > where > shares = M.findWithDefault 0 claim (claims portfolio) > cash' = cash portfolio + shares `valueAtPrice` price > claims' = M.delete claim (claims portfolio)
The value of a stake is the number of shares times the price when holding a positive number of shares. When holding a short position one has to buy back all the shares. This costs money, but for each share you buy back, you also get your deposit back, so overall you gain money when buying back your short position. The value of stake at a given price is the following.
> valueAtPrice :: (Floating a, Ord a) => a -> a -> a > shares `valueAtPrice` price | 0 <= shares = price*shares > | otherwise = (1-price)*(-shares)
To compute a new portfolio after increasing or decreasing one’s (positive or negative) position in a claim, I find it simplest to imagine selling everything and then buying into the new position. This avoids having to dance around the change in behaviour when moving from a positive to a negative position or vice versa.
> adjustPortfolio :: (Floating a, Ord a) => > Portfolio a -> Claim -> a -> a -> Portfolio a > adjustPortfolio portfolio claim price delta = > Portfolio cash' claims' > where > newAmt = delta + M.findWithDefault 0 claim (claims portfolio) > portfolio' = sellAll portfolio claim price > cash' = cash portfolio' - valueAtPrice newAmt price > claims' = M.insert claim newAmt (claims portfolio')
Finally, I am able to a function to find the optimal adjustment to a single claim of a portfolio given a price that you can buy and sell at and a distribution of winners. To do this I create a function from delta the change in number of shares, to the expected growth rate. Then I use Newton’s method to find the optimal adjustment by using an initial guess of 0.
> optimizePortfolio distribution portfolio claim price = > f `optimizeNear` 0 > where > f delta = expectedGrowthRate distribution portfolio' > where > portfolio' = adjustPortfolio portfolio claim price delta
At the time of writing, the quotes for the 2008 Democratic Nomination Winner-Takes-All Market is the following:
Quotes current as of 10:30:00 CST, Sunday, August 19, 2007.
Symbol Bid Ask Last Low High Average CLIN_NOM 0.665 0.669 0.672 --- --- --- EDWA_NOM 0.058 0.063 0.056 --- --- --- OBAM_NOM 0.205 0.221 0.220 --- --- --- DROF_NOM 0.063 0.070 0.070 --- --- ---
These prices can be interpreted as the probability of these events occurring. Suppose you disagree with these probabilities. Suppose you think Clinton has a 65% chance of winning, Edwards has a 6% chance, Obama has a 22% chance and a 7% chance of someone else. Starting with an investment of $200, how much should you short sell CLIN_NOM? To answer this question one can load up the KellyCriterion module in GHCi
*KellyCriterion> let d = mkD [("CLIN",0.65),("EDWA",0.06),("OBAM",0.22),("DROF",0.07)]
*KellyCriterion> optimizePortfolio d (newPortfolio 200) "CLIN" 0.665
-13.466502076085735
According to the Kelly criterion, you should short sell about 13.5 shares of CLIN_NOM. I usually round my shares towards 0 (to reduce variance), and so I would sell 13 shares.
How many shares of EDWA_NOM should you sell. The bid price is $0.058, so the optimal value is:
*KellyCriterion> optimizePortfolio d (newPortfolio 200) "EDWA" 0.058 7.321180174243999
The recommendation is to buy 7 shares. Of course one cannot buy at the bid price, one can only buy at the ask price of $0.063.
*KellyCriterion> optimizePortfolio d (newPortfolio 200) "EDWA" 0.063 -10.164151039284278
But the recommendation at the ask price is to sell 10 shares. This isn’t so surprising because the given probability of Edwards winning, 6%, lies between the bid and ask price. Therefore you should not execute any trades for EDWA_NOM.
Suppose you manage to execute your sale of 13 shares at the market price of $0.665.
*KellyCriterion> :set -fno-monomorphism-restriction
*KellyCriterion> let portfolio1 = adjustPortfolio (newPortfolio 200) "CLIN" 0.665 (-13)
*KellyCriterion> portfolio1
Portfolio {cash = 195.645, claims = fromList [("CLIN",-13.0)]}
Let’s ask how many shares of EDWA_NOM one should sell at the bid price now.
*KellyCriterion> optimizePortfolio d portfolio1 "EDWA" 0.058 -1.843864491964051
Now it is recommending that you sell 1 share of EDWA_NOM. What has changed?
All the claims in this market are correlated because they are mutually exclusive outcomes. When you have correlated claims it is possible to hedge your bets buy buying (or in this case, selling) both. The intuitive idea is that if Clinton does win the nomination, then you can at least make some money back on Edwards losing the nomination. Hedging your bets is what smart investors do, and the Kelly criterion automatically quantifies how to hedge your bets. In this case you can increase portfolio’s growth rate even though the odds are against you.
Automatic differentiation works by performing computations on infinitesimals. This allows me to define a derivative even when I use case analysis in value and valueAtPrice. Whether a left or right derivative is taken depends on whether I use a strict or non-strict inequality in the case analysis.
There is (presumably) a kink in my functions where my computation switches branches of the case analysis; however there is only one optimal portfolio. Newton’s method seems to work fine for me in this situation, but one cannot always rely on optimizeNear when one’s function is not smooth. Not that Newton’s method is reliable for smooth functions either.
The probability library isn’t extensively used in this example, but it would be more useful in more complex situations.