Asian Options I

Today I’m going to introduce the first exotic option that I’ve looked at in my blog, the Asian option. There is quite a lot to be said about them so I’ll do it over a few posts. I’ll also be updating the pricers to price these options in a variety of ways.

The simplest form of Asian option has a payoff similar to a vanilla option, but instead of depending on the value of the underlying spot price at expiry, it instead depends on the average the underlying spot price over a series of dates specified in the option contract. That is, the value of the option at expiry C(T) is the payoff

    \[C(T) = \Big( {1\over N}\sum^{N}_{i=0} S_{t_i} - K\Big)^+\]

where K is the strike, N is the number of averaging dates, and S_t is the value of the spot that is realised at each of these dates.

First of all, what does it mean that this is an exotic option? From the market, we will be able to see the prices of vanilla options at or near each of the dates that the contract depends on. As I discussed in my post on Risk-Neutral Valuation, from these prices we can calculate the expected distribution of possible future spot prices at each date – shouldn’t we be able to use this to calculate a unique price of the Asian option consistent with the vanilla prices?

The answer, unfortunately, is no. Although we know the distribution at each time, this doesn’t tell us anything about the correlations between the price at time t_1 and time t_2, which will be critical for the Asian option. To illustrate this, let’s consider a simple Asian that only averages over two dates, t_1 and t_2, and we’ll take t_2 to be the payoff date for ease, and try to calculate its price via risk-neutral valuation. The price at expiry will be

    \[C(t_2) = \Big( {1\over 2}\big(S_{t_1} + S_{t_2}\big) - K\Big)^+\]

To calculate the price at earlier times, we use the martingale property of the discounted price in the risk-neutral measure

    \[C(0) = N(0)\cdot{\mathbb E}^{RN} \Bigl[ \ {C(t_2) \over N(t_2)}\ |\ {\cal F}_0\ \Bigr]\]

and expanding this out as an integral, we have

    \[C(0) = \delta_{0,t_2} \int \int \Big( {1 \over 2} \big( S_{t_1} + S_{t_2} \big) - K \Big)^+\ p(S_{t_1},S_{t_2})\ dS_{t_1} dS_{t_2}\]

where \delta denotes the discount factor to avoid confusion with the pdfs inside the integral. From the market, we know both p(S_{t_1}) and p(S_{t_2}), which are respectively the market-implied probability distributions of the spot price at times t_1 and t_2 calculated from vanilla call prices using the expression we derived before

    \[p(S_{t}) = {1 \over \delta_{0,t}}{\partial^2 C(t) \over \partial K^2}\]

But, we don’t know the JOINT distribution p(S_{t_1},S_{t_2}) which expresses the effect of the dependence of the two distributions. We know from basic statistics that

    \[p(S_{t_2},S_{t_1}) = p(S_{t_2} | S_{t_1}) \cdot p(S_{t_1})\]

and since the spot at the later time depends on the realised value of the spot at the earlier time p(S_{t_2} | S_{t_1}) \neq p(S_{t_2}), so we don’t have enough information to solve the problem from only the market information available from vanilla options.

What is this telling us? It is saying that the market-available information isn’t enough to uniquely determine a model for underlying price movements with time. There are a variety of models that will all re-create the same vanilla prices, but will disagree on the price of anything more exotic, including our simple Asian option. However, observed vanilla prices do allow us to put some bounds on the price of the option. For example, a careful application of the triangle inequality tells us that

    \[\Big( {1\over 2}\big(S_{t_1} + S_{t_2}\big) - K \Big)^+ \leq {1\over 2} \Big( S_{t_1} - K_1 \Big)^+ + {1\over 2} \Big( S_{t_2} - K_2 \Big)^+\]

for any K_1 + K_2 = 2K; the expressions on the right are the payoff at expiry of call options on S_{t_1} and S_{t_2} respectively, and we can see the prices of these on the market, which allow an upper bound on the asian price. This means that, while we can’t uniquely price the option using the market information alone, we CAN be sure that any model consistent with market vanilla prices will produce an asian price that is lower than the limit implied by this inequality.

In order to go further, we need to make a choice of model. Our choice will determine the price that we get for our option, and changing model may well lead to a change in price – analysing this ‘model risk’ is one of a quant’s main jobs. A very simple choice such as Black Scholes [but note that BS might not be able to re-create an arbitrary vanilla option surface, for example if there is a vol smile at some time slices] will allow us to solve the integral above by numerical integration or by Monte Carlo (this option form still doesn’t have a closed form solution even in BS).

In the coming posts I’m going to develop the Monte Carlo pricer on the blog to price asian options in BS, and look at a number of simplifying assumptions that can be made which will allow us to find closed form approximations to the price of Asian options.

 

Finally, a brief note on the naming and usage of Asian options. Opinion seems divided – some people believe they are called Asian options because they’re neither European nor American, while some people say it’s because they were first traded in Japan. They are often traded so that the days on which the averaging is done are the business days of the last month of the option’s life. As the look up period is spread out over a period, they are less susceptible to market manipulation on any particular date, which can be important in less liquid markets, although the theoretical prices of Asian options like this are usually very similar in price to vanilla options at any of the look up dates. More exotic Asians might average over the last day of a month for a year. This average is much less volatile than the underlying over the same period, so Asian options are much cheaper than a portfolio of vanillas, but it’s easy to imagine that they might well match the risk exposure of a company very well, since companies trading in two or more currency areas will probably be happy to hedge their average exchange rate over a period of time rather than the exchange rate at any one particular time.

Interview Questions V: The Lowest Unique Positive Integer Game

Today’s post will be quite an extended one, about an interesting game theory problem I’ve been thinking about recently. The game is a lottery that works as follows. Each of N players chooses a positive integer, and the player who picks the lowest integer that no-one else has selected wins. There are two variants of the game discussed in the literature, one in which the integers must be between 1 and N, and one in which they have no limit. Except in the specific case of only 3 players, this restriction seems to make no difference to the solution […unless I’ve got my algebra wrong, which is by no means impossible!].

Note that throughout this post, I’ll assume a basic familiarity with probability and knowledge of the formulae for infinite sums (given here, for example), particularly the sum to infinity of a geometric progression:

    \[\forall \; 0 \; \textless \; x \; \textless \; 1 \; : \; \sum^{\infty}_0 Ax^n = {A \over 1-x}\]

3-Player Case

I start with the N=3 case to illustrate the principles of the problem. Because going in to the problem we have exactly the same information as the other two players, there is no deterministic solution, and in order to maximise our chances of victory we need to adopt a ‘mixed strategy’ which involves selecting a random distribution that assigns a probability to the selection of each integer. This is explained a bit further at this website, although unfortunately the solution that they present is incorrect!

In the case that players are limited to selecting 1-N (so 1, 2 or 3), the problem is analysed in a paper on arXiv (although there’s also a mistake in this paper – this time the N=4 solution presented is incorrect, as I’ll show later), and my solution will follow the author’s.

We are trying to select a set of probabilities \{ p_1, p_2, p_3 \} such that when all players play this strategy, no player increases her chances of victory by adjusting her strategy (such a solution is called a Nash Equilibrium in game theory, as seen in A Beautiful Mind). Let’s assume player 2 and player 3 are both using these probabilities, and player 1 tries to increase her chance of victory by playing instead the strategy \{ q_1, q_2, q_3 \}.

If she chooses 1, she wins if the other players both play either 2 or 3; if she chooses 2 she wins only if the other players both play 1 or both play 3, and if she chooses 3 she wins only if both other players play 1 or both play 2. So, we can express her total probability of victory as the sum of these three terms

    \[p({\rm victory}) = q_1\cdot(p_2 + p_3)^2 + q_2\cdot(p_1^2 + p_3^2) + q_3\cdot(p_1^2 + p_2^2)\]

And subject to the normalisation condition

    \[\sum_1^3 p_n = \sum_1^3 q_n = 1\]

Maximising the victory probability is a natural problem for the method of Lagrange Multipliers. The Lagrange equation

    \[{\partial \over \partial q_n} \Big( p({\rm victory}) -\lambda \sum_1^3 q_n \Big) = 0\]

gives us the following three equations

    \[(p_2 + p_3)^2 = \lambda\]

    \[p_1^2 + p_3^2 = \lambda\]

    \[p_1^2 + p_2^2 = \lambda\]

And as in the paper above, we can solve these simultaneously along with the normalisation condition to give the probabilities

    \[p_1 = {2 \sqrt{3} - 3} = 0.46410\]

    \[p_2 = {2 -\sqrt{3}} = 0.26795\]

    \[p_3 = {2 -\sqrt{3}} = 0.26795\]

Her chances of victory are now 0.28719, regardless of her strategy – the equations above say that as long as two players play this solution, the other player can’t change her probability of winning by choosing ANY strategy. For example, if she switches her strategy to ALWAYS choosing 1, she will now win whenever the other two players play either 2 or 3, the chance of which is given by (1 - 0.46410)^2 – and this is still 0.28719.

Now what if we relax the restriction that bids be between 1 and 3?

We can see immediately that the solution presented in the first link above, p(x) = 0.5^x, is incorrect – in this case, if the third player plays always 1, she wins ¼ times (when both other players play more than 1), while if she plays always 1000, she wins almost a third of the times (whenever the other two players play the same number). But we said her victory probability should be independent of strategy for the Nash Equilibrium, so this can’t be correct. But it is along the right lines – the actual solution does decay rapidly as x increases.

Her chance of victory is now

    \[p({\rm victory}) = \sum_{i=1}^{\infty} q_i\cdot \Big\{ \sum_{j=1}^{i-1} p_j^2 + \Big(\sum_{j=i+1}^{\infty} p_j\Big)^2 \Big\}\]

And differentiating this with respect to each q_i in turn gives an infinite set of coupled equations

    \[\forall i:\quad\sum_{j=1}^{i-1} p_j^2 + \Big(\sum_{j=i+1}^{\infty} p_j\Big)^2 = \lambda\]

This turns out to be solvable, but difficult – a sketch of the solution is given at the bottom of the post. The solution is p(x) = A e^{-\alpha (x-1)}, A is given by the normalisation condition

    \[\sum_{n=1}^{\infty} A e^{-\alpha(n-1)} = 1\]

    \[A = (1-e^{-\alpha})\]

and we can use a trick to find the parameter \alpha. We’ve said that the third player’s odds of victory are independent of her strategy. Consider two strategies, one in which she plays the same as the other players, and another in which she always plays the same, very large number (say 10^{500}). In the first case, chances of victory are equal for all three players, so they must be equal to 1/3 times one minus the chances of NO-ONE winning (which happens when they all choose the same number)

    \[p({\rm victory}) = {1 \over 3}\Big( 1 - \sum_{i=1}^{\infty} p_i^3 \Big)\]

And in the second case, she wins whenever the other two players play the same number

    \[p({\rm victory}) = \sum_{i=1}^{\infty} p_i^2\]

We can combine these and substitute in the solution p_i = A e^{-\alpha (i-1)} with A = (1-e^{-\alpha}), and solve for \alpha:

    \[\sum_{i=1}^{\infty} p_i^2 = {1 \over 3}\Big( 1 - \sum_{i=1}^{\infty} p_i^3 \Big)\]

and using the summation formula

    \[{A^2 \over 1 - e^{-2\alpha}} = {1 \over 3}\Big( 1 - {A^3 \over 1 - e^{-3\alpha}} \Big)\]

    \[3(1 - e^{-3\alpha})A^2 = (1 - e^{-3\alpha})(1 - e^{-2\alpha}) - A^3 (1 - e^{-2\alpha})\]

    \[3(1 - e^{-3\alpha})(1 - e^{-\alpha})^2 = (1 - e^{-3\alpha})(1 - e^{-2\alpha}) - (1 - e^{-\alpha})^3 (1 - e^{-2\alpha})\]

Expanding out and cancelling terms where possible, then taking out factors:

(1)   \begin{eqnarray*} 3 - 6e^{-\alpha} + 3e^{-2\alpha} - 3e^{-3\alpha} + 6e^{-4\alpha} -3e^{-5\alpha} \\ \quad = 3e^{-\alpha} - 3e^{-2\alpha} - 3e^{-3\alpha} + 3e^{-4\alpha} \end{eqnarray*}

    \[1 - 3e^{-\alpha} + 2e^{-2\alpha} + e^{-4\alpha} -e^{-5\alpha}= 0\]

    \[(1 - e^{-\alpha})^2 \cdot (e^{-3\alpha} + e^{-2\alpha} + e^{-\alpha} - 1) = 0\]

So e^{-\alpha} is the real root of the equation x^3 + x^2 + x = 1, which is given by x = 0.543689. A quick wikipedia search reveals that this is the reciprocal of something called the tribonacci constant, vital in the construction of the Snub Cube. I don’t know if this has some deeper resonance, but I’d love to hear from anyone who thinks it does! So, the full symmetric Nash Equilibrium in the 3-player, no upper bid limit case is

    \[p_i = (1 - e^{-\alpha})\cdot e^{-\alpha (i-1)}\]

with \alpha = 0.609378. Note that the (incorrect) form given in the linked-to website can also be expressed in the same form, but with \alpha = 0.693147.

 

4-Player Case

In the case of 4 players and above, the maximisation equation is

    \[p({\rm victory}) = \sum_{i=1}^{\rm UL} q_i\cdot \Big\{ \sum_{j=1}^{i-1} p_j^3 + 3\Big(\sum_{j=i}^{i-1} p_j^2\ \cdot \sum_{j=i+1}^{\infty} p_j \Big)+ \Big(\sum_{j=i+1}^{\infty} p_j\Big)^3 \Big\}\]

where the new term in the middle of the expression comes from the victory scenario in which two players both choose the same lower integer than our player and so are not unique, while the third player chooses one that is larger. This is the term that is missing in the paper linked to above that leads to the incorrect solution.

In the case that UL = 4, we have four equations and the normalisation condition to solve. The equations feature cubic equations, so the solution for these is required. It’s uncommon enough for me to have had to refer to wikipedia, the solution can be found here – we are saved some hassle because the relevant cubic equations don’t have a quadratic term.

Once again, a sketch of the solution in the unrestricted scenario is presented at the bottom of the post, but it seems to make very little difference whether the upper limit UL is set to 4 or infinity. In both cases, I find that

    \[p_1 = 0.447737\]

    \[p_2 = 0.424873\]

    \[p_3 = 0.125655\]

    \[p_4 = 0.001736\]

    \[p_n \simeq 0.0 \quad \forall n \textgreater 4\]

Why does the upper limit no longer make any difference? We only want to choose a higher number if there is a significant chance of the lower numbers being ‘crowded out’ by the other players. That is, we sometimes choose 4 because there is a small chance that the other three players will all select either 1, 2 or 3. Similarly, we would only choose 5 if there was a significant chance that 4 wasn’t high enough, because there was also a significant chance of all of the other three playing 4 – but from looking at the values, we see that p_4 is very small already, and (p_4)^3 is truly tiny. Consequently, in the general case p_n for n \textgreater 4 is going to be negligibly small.

 

N-player Case

The problem rapidly becomes hard to compute for large N, but there is a body of literature on the subject, in particular this 2010 paper points out the mistake in the paper I linked to before, and presents a general solution for N players. Note from their graphs that the probability of choosing a number greater than N is essentially 0 for higher numbers of players, so whether or not we impose this restriction doesn’t change the equilibrium materially.

Derivations

I hope you’ve enjoyed my take on this problem, the sketches of my method of solution for the 3- and 4-player cases are given below but can probably be skipped on a first reading.

In the three-player case, the Lagrange equations are

    \[\forall i:\quad\sum_{j=1}^{i-1} p_j^2 + \Big(\sum_{j=i+1}^{\infty} p_j\Big)^2 = \lambda\]

For i=1, and using normalisation, this gives

    \[\Big(\sum_{j=2}^{\infty} p_j\Big)^2 = (1-p_1)^2 = \lambda\]

Which means for i greater than 1 we have

    \[i \; \textgreater \; 1 : \quad \sum_{j=1}^{i-1} p_j^2 + \Big(1 - \sum_{j=0}^{i} p_j\Big)^2 = (1 - p_1)^2\]

and with a little re-arrangement

    \[\sum_{j=0}^{i} p_j = 1 - \sqrt{(1 - p_1)^2 - \sum_{j=1}^{i-1} p_j^2}\]

    \[p_i = 1 - \sum_{j=0}^{i-1} p_j - \sqrt{1 - 2p_1 - \sum_{j=2}^{i-1} p_j^2}\]

This gives a ‘step-up’ formula for the construction of later terms from the sum of earlier terms. An engineering-style solution is to write a script (or an excel spreadsheet) that calculates p_2 to p_{n} from an initial guess of p_1, and then varying the initial guess to satisfy the normalisation condition. Alternatively, we can show by induction that the expression above is satisfied for our solution p_i = A e^{-\alpha (i-1)}. First of all, assuming the relationship holds for p_i, lets see what it implies for p_{i+1} (for notational simplicity, I’m going to write e^{-\alpha} below as x

    \[{p_{i+1}\over p_i} = x = {1 - \sum_{j=0}^{i} p_j - \sqrt{1 - 2p_1 - \sum_{j=2}^{i} p_j^2} \over Ax^{i-1} }\]

    \[Ax^i = 1 - A {1-x^i \over 1-x} - \sqrt{1 - 2A - A^2 x^2 {1-x^{-2(i-1)}\over 1-x^2}}\]

and remembering that from our normalisation condition A = 1-x

    \[(1-x)x^i = x^i - \sqrt{1 - 2(1-x) - (1-x) x^2 {1-x^{-2(i-1)}\over 1+x}}\]

    \[x^{2(i+1)}(1+x) = (2x - 1)(1+x) - (1-x) x^2 (1-x^{-2(i-1)})\]

    \[x^{2i+2}+x^{2i+3} + x^{2i+1} - x^{2i} = 2x^2 + x - 1 - x^2 +x^3\]

    \[(x^{2i} - 1) (x^3+x^2+x - 1) = 0\]

so we see that the ratio demonstrated above satisfies the step-up equation for every p_i. The first term is a special case, so I show this separately

    \[{p_2 \over p_1} = x = {1 - p_1 - \sqrt{1 - 2p_1} \over p_1}\]

And now setting p_1 = A:

    \[x = {x - \sqrt{2x - 1} \over 1-x}\]

    \[x(1-x) - x = \sqrt{2x - 1}\]

    \[x^4 - 2x + 1 = 0\]

    \[(x-1)(x^3 + x^2 + x - 1) = 0\]

so we see that the first term is satisfied by the expression.

A similar expression for 4 players is given by the solution to

    \[\Big(1-\sum_{j=0}^{i} p_j\Big)^3 + 3p_1^2\cdot\Big(1-\sum_{j=0}^{i} p_j\Big) = (1-p_1)^3 - p_1^3\]

which gives

    \[p_i = 1 - \sum_{j=0}^{i-1} p_j - \sqrt[3]{-{q\over 2} + \sqrt{{q^2 \over 4} + p_1^6}} - \sqrt[3]{-{q\over 2} - \sqrt{{q^2 \over 4} + p_1^6}}\]

with

    \[q = (1-p_1)^3 - p_1^3 = 1 - 3p_1 + 3p_1^2 - 2p_1^3\]

I’ve not found an analytical solution for general p_n to this yet, and had to proceed by the variational technique discussed above, giving the answers in the body of the post. If you can solve this exactly for me I’d be very interested to hear!