# A Longstaff and Schwartz Approach to the Early Election Problem

Authors: Elliot Tonkes; Dharma Lesmono
Journal: Advances in Decision Sciences
 (2012)

---

## Abstract

In many democratic parliamentary systems, election timing is an important decision availed to governments according to sovereign political systems. Prudent governments can take advantage of this constitutional option in order to maximize their expected remaining life in power. The problem of establishing the optimal time to call an election based on observed poll data has been well studied with several solution methods and various degrees of modeling complexity. The derivation of the optimal exercise boundary holds strong similarities with the American option valuation problem from mathematical finance. A seminal technique refined by Longstaff and Schwartz in 2001 provided a method to estimate the exercise boundary of the American options using a Monte Carlo method and a least squares objective. In this paper, we modify the basic technique to establish the optimal exercise boundary for calling a political election. Several innovative adaptations are required to make the method work with the additional complexity in the electoral problem. The transfer of Monte Carlo methods from finance to determine the optimal exercise of real-options appears to be a new approach.


---

## Body

## 1. Introduction

This paper is concerned with a new approach for establishing the optimal decision criteria for calling an early election within an electoral environment which permits a government such an option. The problem is predicated on the assumption that a government endures a stochastic level of popularity, and that popularity can be translated into a probability distribution for the likelihood of being returned to government at a general election. This problem has been studied in [1–5].Intuitively, as the government rises higher in the popular opinion polls, it should become more beneficial to call an early election, as a successful election outcome will yield the government another full term in power. However, the decision is not entirely trivial, because calling an election (even when high in the polls) is not entirely risk free, and the government puts in jeopardy their remaining (certain) term in power for an (uncertain) extended period in power. As the popularity polls become higher and the electoral term grows closer to an end, the decision becomes clear to call an early election; as the government’s popularity diminishes, it becomes clear to defer an election. The optimal boundary is the distinct transition point at which the decision is made to call or defer the election, depending on the state.Approaches to establish the optimal boundary for the early election have been treated by various methods. Balke [6] approached it with a PDE (partial differential equation), but for the PDE to remain tractable certain assumptions are required on the problem, such as the concurrency of exercising and holding the election. There have been variations to the problem, such as including measures of confidence [7–9], a lead time [1], and active controls such as policy announcements [4, 5].Optimal exercise and free boundary problems occur frequently in physical and decision sciences. Depending on the particular context, the problem can be phrased as a free boundary problem, a moving boundary problem, or an optimal-stopping problem. The Stefan problem in physical sciences [10] and the American option problem in finance [11–14] have each received considerable research attention with various methods to establish both the solution to the problem on the interior of the domain, as well as identifying the free boundary itself.In the decision sciences, the American option problem has been solved numerically with binary, tertiary, and multinodal trees [15]. There are also approaches using PDE to price American options such as in [16, 17]. The technique of SDP (stochastic dynamic programming) has also been applied with considerable success [18]. Recent advances by Zhu [19] have been successful in establishing a closed form solution to the problem.However, all of the techniques are computationally intensive and are best suited for a problem structured with a single state variable (i.e., an option which is written on a single underlying).Under the fundamental theorem of financial calculus, the problem of option pricing reverts to the calculation of conditional expectations for a payoff under particular probability measures. Monte Carlo techniques have been applied with great success for valuing standard and exotic financial options. Until recently, it was widely held that the Monte Carlo approach was not applicable for options with a control such as an exercise decision.Longstaff and Schwartz [20] pioneered a successful Monte Carlo technique which refuted the assertion. The method constructs Monte Carlo simulations to simulate the random outcomes of the underlying price processes. However, the value of the option is assessed at discrete points in time by conducting a regression of the option value assessed against the value at the next time step, where the statistically optimal exercise decision is executed at each time step. At its core, the method combines the characteristics of the Monte Carlo approach with the systematic back-stepping technique of discrete stochastic dynamic programming.The practical benefits become apparent as Monte Carlo simulations are only required tosample the state space, while the direct SDP requires a complete enumeration of all states. Consequently, the approach reduces computational time and memory requirements and enables the optimal boundary to become tractable for options with nonstandard structures.Analytical studies [21] have confirmed that the method remains mathematically rigorous, while at the same time it has proven a powerful method to implement in industry.The problem of establishing the optimal exercise boundary for political elections has been successfully attacked using several of the standard free boundary approaches from applied mathematics. Publications such as [3, 6] have developed PDE formulations of the stochastic problem via the Kolmogorov equations. Stochastic dynamic programming has been applied in [1, 2, 4, 5].This paper applies the basic philosophy of the Monte Carlo method of Longstaff-Schwartz adapted to the particular subtleties of the election problem. It is our understanding that the approach in [20] has found widespread use in financial analysis, but it has not extended greatly to other real-world decision problems. We attack the problem with a single state variable to show the suitability, accuracy, and computational efficiency of the approach. The method has not been applied to a system represented by multiple states (e.g., a state variable for each political seat), but we believe that such extensions are entirely feasible, in a similar manner to [22].In the current paper, the novel extensions of the standard Longstaff-Schwartz method are summarized as follows.(i)
The random process describing the stochastic behaviour is governed by a different SDE compared to the geometric Brownian motion typically applied for American option pricing on assets.(ii)
The payoff for the option is not a deterministic quantity. For the American option, the payoff upon exercise is known precisely according to the standard payoff formula for the put or call option. In the present context, if an election is called (i.e., the option is exercised), then government is still subject to the uncertainty of the electoral polls and a win is never guaranteed. The election outcome, and therefore the payoff are random variables because there remains a positive probability that the party will lose government, even from very high in the polls.(iii)
Once an election is called, there is a delay until the exercise date. This differs from the American option in which the call yields an immediate exercise. This element contributes a source of randomness described in the previous point. However, we must adapt the Longstaff-Schwartz method in order to accommodate the subtleties.(iv)
Most importantly, the recursive nature of the payoff makes the implementation of a MLS more complex than the original implementation in [20] and the variants thereof. Upon exercising the option, and achieving a return to power, the value function (expected time in power) returns to the expected time in power from the poll state, which is an unknown function. The length of time in government returns us recursively to the original problem. In some sense, there are similarities with the perpetual American put option.The structure of the remainder of this paper is as follows. In Section2, we introduce our problem formulation and notation. Section 3 describes and calibrates the stochastic process governing the poll process and the probability of reelection. Our case study is based on elections in the Australian Federal Election for House of Representatives. Section 4 provides the algorithm for the implementation of the Longstaff-Schwartz method. Numerical results, which include the expected remaining life in power, and exercise boundaries are contained in Section 5. Conclusions and future work are in the last section.


## 2. Problem Formulation and Notation

Define a time-varying state variableSt as the difference in popularity of the two-party-preferred data between the government and the opposition at time t. It necessarily follows that -1<S<1 as popularity cannot exceed 100%. Let the maximum period between elections be constrained by the sovereign constitution at Y years. In Australia, Y=3 years while in the UK, Y=5 years. In the US, there is a fixed term of 4 years for presidential and 2 years for congressional elections, and consequently, the optimal stopping problem has no relevance in such domains.Constitutionally, there is also a positive period between announcing and holding the election, which we call thecampaign time. Typically, during the campaign time each party enters an election campaign mode to garner popular support. According to the Australian Constitution and Commonwealth Electoral Act 1918, it must lie between 33 and 68 days and is further restricted as an election must be held on a Saturday.Define astrategy by describing a set Ω⊂[0,Y]×[-1,1] such that the government will call an election if ever (t,St)∈Ω. For a given strategy, the remaining lifein power is the mathematical expectation of the residual time which the current government will enjoy. The remaining life includes the current term of government until the next election, and then includes recursively subsequent terms in power to the extent that repeated elections are won.The statement of the optimal election problem is(a)
to determine an optimal strategy which maximizes theremaining life,(b)
to establish the expected remaining life.The optimal election problem is couched in an environment which does not accommodate real or financial hedging as is conducted in derivative markets. While the analogous problem for American options is developed under a risk-neutral measure [19], the notion of expectation here is meant in the frame of real world measures.


## 3. Governing Random Processes

### 3.1. Poll Process

We modelSt as a mean-reverting random process and fit a SDE to describe its behavior. The SDE and its calibration is now a well-studied problem, and publications such as in [23] perform the analysis of the SDE while in [1, 2, 4, 5] contain the calibration by maximum likelihood estimation (MLE) or regression.We assume that opinion polls are driven by random processes and obey a Markov property, where the current state depends only upon the last observed polls. This underlying process consists of increments driven by the current state and a Gaussian process. The parametric formulation of the SDE forSt is expressed as:
(3.1)dSt=-μ(St1-St2)dt+σdWt,
where Wt is a Wiener process; μ and σ are constants. The nature of the solution is detailed in [23] confirming that it obeys a mean-reverting behavior around St=0.The boundaries {-1} and {1} are entrance boundaries which means that these values cannot be reached from the interior of (-1,1). The model relates to observed poll outcomes by exhibiting random fluctuations reflecting the way that voter sentiment ebbs and flows for each major party depending on their performance and external factors such as the economy. When a party’s popularity begins to significantly deteriorate, that party takes policy actions or reforms to regather popularity, justifying the mean reversion characteristic of the model.


### 3.2. Sampling and Response Error

The state of the polls,S,at time t represents the difference between the intended two-party-preferred vote for a sample (of around 2000) voters across all electorates and lies between −1 and +1. A useful quantity to measure the decisiveness of the election is the proportion of seats won, Nw∈[0,1]. Winning the election follows surely if Nw>0.5. Without the representative system and exaggerated majorities, it would follow that Nw=0.5S+0.5. We assume that the randomness arising from response error (see [24–26]) is contained within the sampling error parameters.The sampling errorQij between the sample poll state Si and true voting intentions Sj is estimated using the standard approach to sampling error Kmietowicz [27]. With a sample size of around 2000 individuals, we have a standard error in S arising from sampling of 2.2%.


### 3.3. Calibration of the Poll Process and Winning Probabilities

The model (3.1) has been calibrated using the MLE in article [1]. Using the same methodology over the historical time period, we have found the estimated values of μ^ and σ^ are 3.49 and 0.35, respectively.Article [4] has derived a model for the conditional probability of winning a proportion of seats based on observed poll outcomes and incorporating sampling error. Using data from the Australian Electoral Commission over 1949 to 2010, a regression between observed S and the resultant proportion of seats won Nw yield the following model:
(3.2)Nw=0.5223+1.4708S+ε,
where ε~N(0,0.03632). It follows that Pr(W|S)=Pr(X>0.5), where X~N(0.5223−1.4708S, 0.03632). The diagrammatic representations are shown in Figure 1 below, and the graph has similarities with Balke’s polynomial function for the probability of winning the election (see [6]) and Smith’s probit function for the probability of reelection (see [7]).Proportion of seats won depending on nationwide proportion of votes won. Resultant probability of winning majority of seats as a function of nationwide vote.
(a)
(b)


## 3.1. Poll Process

We modelSt as a mean-reverting random process and fit a SDE to describe its behavior. The SDE and its calibration is now a well-studied problem, and publications such as in [23] perform the analysis of the SDE while in [1, 2, 4, 5] contain the calibration by maximum likelihood estimation (MLE) or regression.We assume that opinion polls are driven by random processes and obey a Markov property, where the current state depends only upon the last observed polls. This underlying process consists of increments driven by the current state and a Gaussian process. The parametric formulation of the SDE forSt is expressed as:
(3.1)dSt=-μ(St1-St2)dt+σdWt,
where Wt is a Wiener process; μ and σ are constants. The nature of the solution is detailed in [23] confirming that it obeys a mean-reverting behavior around St=0.The boundaries {-1} and {1} are entrance boundaries which means that these values cannot be reached from the interior of (-1,1). The model relates to observed poll outcomes by exhibiting random fluctuations reflecting the way that voter sentiment ebbs and flows for each major party depending on their performance and external factors such as the economy. When a party’s popularity begins to significantly deteriorate, that party takes policy actions or reforms to regather popularity, justifying the mean reversion characteristic of the model.


## 3.2. Sampling and Response Error

The state of the polls,S,at time t represents the difference between the intended two-party-preferred vote for a sample (of around 2000) voters across all electorates and lies between −1 and +1. A useful quantity to measure the decisiveness of the election is the proportion of seats won, Nw∈[0,1]. Winning the election follows surely if Nw>0.5. Without the representative system and exaggerated majorities, it would follow that Nw=0.5S+0.5. We assume that the randomness arising from response error (see [24–26]) is contained within the sampling error parameters.The sampling errorQij between the sample poll state Si and true voting intentions Sj is estimated using the standard approach to sampling error Kmietowicz [27]. With a sample size of around 2000 individuals, we have a standard error in S arising from sampling of 2.2%.


## 3.3. Calibration of the Poll Process and Winning Probabilities

The model (3.1) has been calibrated using the MLE in article [1]. Using the same methodology over the historical time period, we have found the estimated values of μ^ and σ^ are 3.49 and 0.35, respectively.Article [4] has derived a model for the conditional probability of winning a proportion of seats based on observed poll outcomes and incorporating sampling error. Using data from the Australian Electoral Commission over 1949 to 2010, a regression between observed S and the resultant proportion of seats won Nw yield the following model:
(3.2)Nw=0.5223+1.4708S+ε,
where ε~N(0,0.03632). It follows that Pr(W|S)=Pr(X>0.5), where X~N(0.5223−1.4708S, 0.03632). The diagrammatic representations are shown in Figure 1 below, and the graph has similarities with Balke’s polynomial function for the probability of winning the election (see [6]) and Smith’s probit function for the probability of reelection (see [7]).Proportion of seats won depending on nationwide proportion of votes won. Resultant probability of winning majority of seats as a function of nationwide vote.
(a)
(b)


## 4. Modified Longstaff-Schwartz (MLS) Algorithm

### 4.1. Introduction

This section develops the algorithm for establishing the value function and the optimal exercise boundary by modifying the Longstaff-Schwartz method. We term it the Modified Longstaff-Schwartz (MLS) method, as adapted for the optimal election exercise problem. The main stages in the MLS algorithm are described here. The details on each individual component are explained in the next subsections. The main stages in the MLS algorithm are described in Table1.Table 1
Step
Summary
Description
0
Develop initial estimate for the value function (Detail Section4.6)
Establish an estimate for the valueV(0,S) function at time t=0 across all poll states -1≤S0≤1.
1
Simulation of the poll process(Detail Section 4.2)
Generate trajectories of the SDE (4.6) by simulating solutions. Denote each of the N simulated poll process as Stn.
2
Simulation of electoral outcome if calling an election (Detail Section4.4)
At each decision pointtj, and poll state Stjn, we establish the expectation of the value function from a decision to call an election. The electoral result arises from:  (i) Continue the diffusion to time tj+TL   (ii) Simulate a sampling error for the poll state  (iii) Simulate the randomness in relationship in Section 3.3 for the imperfect relationship between nationwide polling and the distribution of seats.
3
Simulation of electoral outcome if not calling an election
The alternative to the step 2 is to NOT call an election. In that case, the polls will diffuse to the next timesteptj+dt and the decision experiment is repeated.
4
Perform regression (Detail Section4.5)
Regress over allN simulations the value function conditioned upon the poll state Stjn under the scenario that an election IS called (step 2).Regress over all N simulations the value function conditioned upon the poll state Stjn under the scenario that an election IS NOT called (step 3).
5
Establish max and strategy
Establish the maximum arising from steps 3 or 4; if 3 then assign the optimal strategy as CALL, else CONTINUE. Assign the value function to each of the points(tj,S), -1≤S≤1, from the maximum between the two regressions.
6
Repeat over all timesteps
Repeat over all time steps stepping backwards fromt=Y to t=0.
7
Update initial value estimate
When time zero is reached, the value function will disagree with the estimate from step 0.Update with the derived initial value and recommence from step 0 until convergence of the initial estimate is achieved.The solution space is discretised{t0,t1,…,tM}⊂[0,Y] in time over with equally spaced intervals. A number of simulations N is selected for the algorithm.


### 4.2. Simulations of the Poll Trajectory

At the heart of the Monte Carlo approach is the simulation of solutions to the SDE (3.1), and this section describes our approach to generating random trajectories of the poll process. A theoretical investigation in [23] of the governing equation (3.1) demonstrated convergence of polygonal approximations to the solution. Consequently, the Euler Maruyama [28] approximations are guaranteed to converge to the true solution in the limiting case of diminishing step sizes.Sample trajectories of the poll process are modeled using the Euler Maruyama formulation expressed in (4.1). Let dt represent small time step discretisations over the electoral term [0,Y]. Let S(j) represent the value of the poll process in the jth time step. Then, we write
(4.1)S(j+1)=S(j)-μS(j)(1-S(j)2)dt+σdtN(j),
where N(j) is a standard independent Gaussian variable. We next discuss how the election process is simulated. At any exercise point (i.e., an election is called), the electoral cycle passes through the following stages. Suppose that an election is called at time τ. (i)
Campaign time: the election passes into a campaigning period and the government into a “caretaker” mode. The poll process St continues to diffuse over the period [τ,τ+TL].(ii)
Sampling error: at time τ+TL an election is held, and the true proportion of votes won by each party is revealed. However, this may deviate from the poll state measured by Sτ+TL owing to sampling and response error. The simulation process incorporates sampling error by conducting an additional transition at time τ+TL:
(4.2)Sτ+TLactual=Sτ+TL+N(0,ε2),
where ε is calibrated in Section 3.2 as 0.022.(iii)
Regional representation error: for each simulation, at the election time, we establish the chance of winning an election by conducting a Bernoulli experiment. While the calibration (3.2) yields a small systematic bias between parties, we have renormalized with a symmetric distribution for the model. Following the variance calibration in (3.2), the chance of winning is conditioned upon the actual voting state as:
(4.3)Pr(Win∣Sτ+TLactual)=Pr(Z>0-1.4708S0.0363),
where Z is a standard Gaussian variable.


### 4.3. Value Function and the Optimality Principle

The value function is defined in Section2 as the remaining life in power and quantifies the utility of holding government. The objective of the government, using the simple control of election exercise, is to maximize its undiscounted term in government. Bellman’s principle of optimality [29] provides proof for a Markov process that the strategy which maximizes the expected value is determined by a dynamic program.Figure2 illustrates the recursive nature of establishing the value function. In order to calculate the expected value function at state (t,S), we require an estimate for the value at time zero, V(0,S).Figure 2
Recursive nature of establishing the value function. The electoral cycle commences at time zero in government. As time progresses, the poll state (red curve) diffuses. The latest date for an election (compulsory election) is at timeY years. But a government can call an early election (1) when high in the polls. A campaigning time will occur, and polls diffuse until the election date at (2). Then either the government will win the election and return to the initial problem (3) or the government will lose the election (4) and have zero remaining life in power.In more formal terms, express the state of the system as the triple(t,S,andM*), where(i)
t∈[0,Y] is the time through the current term,(ii)
S∈(-1,1) is the poll state,(iii)
M*=∞ if an election has not yet been called,(iv)
M* = time remaining until the election, if an election has been called.In the case that the election has been already called and the system is in a campaign state, then there are no decisions to be made.LetQ be the strategy to call an election if (t,S)∈Ω and to continue without calling otherwise. Let the remaining time in power be L when applying strategy Q.The value functionV is then,
(4.4)V(t,S)=E(L∣(t,s)).The optimization problem is then a strategy selection problem:(4.5)max{V∣Q}.According to the Bellman principle of optimality [29], the problem for the value function and the optimal control can be written when M*=∞ as
(4.6)V(t,S)=max{dt+E(V(t+dt,St+dt)),tL+E(V(0,St+tL+ε))×Pr(Win∣S=St+TL+ε)}.The terminal condition is a forced election, that is,(4.7)V(t,Y)=E(V(0,SY+tL+ε))×Pr(Win∣S=SY+TL+ε).The first term in (4.6) represents continuing with certainty to time t+dt and reassessing the decision, while the second term represents calling an election, continuing in power with certainty over the campaign period and then extending the term in power only if the election is won. If the former is the larger, then the optimal decision Q is to continue, while if the latter dominates, then an exercise decision should be made.We initially assume a structure forV(0,S) which is iteratively refined as the algorithm proceeds. At the final available exercise time (Y-TL), we impose an exercise event upon the government. Consequently, there is a diffusion of the polls for period TL, a random error to the actual poll state, and an error between the poll state S* and the proportion of sets won, which consequently yields either an election as won or lost. We can subsequently calculate V(Y-TL,S), being the value of the remaining time in power, which will be V(0,S*) if the election is won and zero otherwise (here S* represents the poll state on election day).A stochastic dynamic program implements the principle of optimality by back stepping from the terminal condition, progressing through timestepsY-TL-dt,Y-TL-2dt,… and so on, and making the comparison (4.6).The MLS method does not enumerate all states explicitly but creates a regression to approximate the two terms in (4.6), based on simulated outcomes for the poll trajectory and election outcome.The method requires an estimate for the initial valueV(0,S),-1≤S≤1. The algorithm recursively step back to time zero, and derives an estimate for V*(S)=V(0,S) which will inevitably disagree with the original estimate. The technique assigns V(0,S) to be the solution V*(S) from the previous iteration. We iterate the process several times to achieve convergence for V(0,S).In contrast to the method on American options [20], at the point of calling an election, the payoff from the decision is unknown. For the MLS method, we must establish the expected life in power remaining if the election is called, which includes a time lag, an uncertainty of electoral outcomes, and a dependence on the initial condition V(0,S).


### 4.4. Simulation of the Exercise Decision

Unlike the typical American Option problem in finance, when the option holder (the government) exercises the option (calls an early election), the payoff is not known with certainty. Instead, there is a lag of around 55 days from calling to holding the election, during which time the polls can diffuse. The measured poll state at the final date is distorted from the actual poll state owing to sampling and response errors. And finally, the mapping of the proportion of votes to the number of parliamentary seats won is not certain and can result in an exaggerated majority.Consequently, at each decision point of call/continue, the MLS method requires to establish the expectation of the value function under the alternatives of calling an election or continuing to the next decision point. There following alternatives are available for the practical implementation to estimate those expectations:(i)
analytical approach: calculate the expectation of the value function from state (t,S) upon the assumption of calling an election, by deriving the solution to the SDE over (t,t+tL), analytically introducing the sampling error and the regional representation error,(ii)
regression approach: use Monte Carlo simulations to model the diffusion, and the other sources of uncertainty, and regress against the state variable S.In this paper, we will pursue theregression approach to fully promote the LS philosophy, and to demonstrate how the technique is capable of handling complex option structures, potentially on many variables, which are not amenable to analytical solution.


### 4.5. Regression Process

As the MLS proceeds, at each time step a regression is performed between the poll state and the payoff or value function. In the seminal paper of Longstaff and Schwartz on the American Option problem [20], a representative example is presented, where a quadratic function is applied for the regression. Since then a large number of papers have extended the concepts, and a key element has been advanced in the basic functions applied in the regression.Figure3 graphically illustrates how the regression is applied in the MLS. Suppose that we have N simulations of the poll process. Suppose that we have applied the MLS from t=Y backwards to time t. At time t, the simulated polls are scattered between -1<Stn<1. For each simulation, we evaluate the value function upon a decision to exercise, and the value function if not continuing.Figure 3
Value function regressions on basis of call or continue. Figure contains remaining life on each simulation under assumption of calling the election (blue scatterplot) and its regression (blue curve), remaining life under assumption of continuing without calling (red scatterplot) and its regression (red curve), and maximum outcome of the two decisions (broken black curve).If continuing, the value function for simulationn is
(4.8)V(t,Stn)=dt+V(t+dt,St+dtn).And if the process continues, the value function will be determined from the simulated election outcome:(i)
V(t,Stn)=TL+V(0,S*) if the election is won,(ii)
V(t,Stn)=TL+0 if the election is lost.The valueS* is the poll state at the commencement of the new term, based on the final poll state at time t+TL.Figure3 is generated from extracting the regressed data at point time around two years into a three-year term, in the first iteration of the algorithm. It illustrates the simulated outcomes under the assumption of calling an election at time t from the simulated poll states, here varying from −0.4 to +0.4. It can be seen that for high poll states, the probability of winning an election is high, and the resultant remaining life is around 6 years. If the polls are low, then there is a low probability of winning the election, and there are numerous outcomes, where the remaining life in power is simply TL.The figure illustrates the dichotomous nature of the electoral process: the outcome of the election is either a win (with a greatly extended life in power) or loss (with limited life in power remaining).The figure is also overlaid with the call decision outcome and with the continue decision outcomes. Under the strategy to continue until the next decision timet+dt, the polls will diffuse slightly. The value function V(S,t+dt) is a smooth function not exhibiting the discontinuous nature of the call decision.Comparing the two regressions, it becomes an optimal strategy for the government to select the alternative which maximizes the value function, which is a call decision if the polls are sufficiently high and a continue decision otherwise. The ability to defer the election decision delivers asymmetric benefit to the government, and with some imagination, the “kink”, the black curve atS=0.25, has some resemblance to a call option payoff from finance.In the present problem, we apply a polynomial fit for the regression. Some motivation for the polynomial fit is provided by the rapid speed of fitting a large number of points to a smooth curve: a task which must be done many times in the algorithm. Alternative fits such as sigmoidal functions provide other avenues of research.Intuitively, given the high mean reversion tendency of the process (μ=3.49), the value function near time zero should be near constant, and a polynomial accommodates this shape.The value function near the terminal time (t=Y) should be intuitively represented by an “S” shaped curve. If the poll state S is low (near −1), then the value function will be near zero as there is low chances of reelection (V≈0). If the poll state is high (near +1), then election victory is nearly assured. For S near zero, the probability of an election victory is approximately 0.5, and we can expect an intermediate value. Provided that the order of the polynomial exceeds a cubic, we are able to force this familiar “S” shaped curve expected of our solution.


### 4.6. Selection of the Initial Value

In selecting the initial value, we choose a constant function. Motivation arrives from the following reasons.(i)
The mean reversion of the SDE dictates that the poll state tends to a stationary distribution.(ii)
The relatively high mean reversion tendency(μ=3.49) means that the poll state loses information quickly.(iii)
Under the assumption of a fast mean reversion rate and no systematic bias for one party to win an election, the unconditional probability at time zero of a party losing the next election without an ability for early exercise is 0.5 (i.e., life in power isY years). The probability of winning the first election but losing the second election is 0.52 (i.e., life in power is 2Y years), the probability of two wins then a loss is 0.53(i.e., life in power of 3Y years), and so on. This expected life arising from this pattern can be calculated explicitly as a progression. 											(4.9)Expected  life  in  power=∑n=1∞n×Y2n=2×Y.This becomes our starting estimate (i.e., 6 years).


## 4.1. Introduction

This section develops the algorithm for establishing the value function and the optimal exercise boundary by modifying the Longstaff-Schwartz method. We term it the Modified Longstaff-Schwartz (MLS) method, as adapted for the optimal election exercise problem. The main stages in the MLS algorithm are described here. The details on each individual component are explained in the next subsections. The main stages in the MLS algorithm are described in Table1.Table 1
Step
Summary
Description
0
Develop initial estimate for the value function (Detail Section4.6)
Establish an estimate for the valueV(0,S) function at time t=0 across all poll states -1≤S0≤1.
1
Simulation of the poll process(Detail Section 4.2)
Generate trajectories of the SDE (4.6) by simulating solutions. Denote each of the N simulated poll process as Stn.
2
Simulation of electoral outcome if calling an election (Detail Section4.4)
At each decision pointtj, and poll state Stjn, we establish the expectation of the value function from a decision to call an election. The electoral result arises from:  (i) Continue the diffusion to time tj+TL   (ii) Simulate a sampling error for the poll state  (iii) Simulate the randomness in relationship in Section 3.3 for the imperfect relationship between nationwide polling and the distribution of seats.
3
Simulation of electoral outcome if not calling an election
The alternative to the step 2 is to NOT call an election. In that case, the polls will diffuse to the next timesteptj+dt and the decision experiment is repeated.
4
Perform regression (Detail Section4.5)
Regress over allN simulations the value function conditioned upon the poll state Stjn under the scenario that an election IS called (step 2).Regress over all N simulations the value function conditioned upon the poll state Stjn under the scenario that an election IS NOT called (step 3).
5
Establish max and strategy
Establish the maximum arising from steps 3 or 4; if 3 then assign the optimal strategy as CALL, else CONTINUE. Assign the value function to each of the points(tj,S), -1≤S≤1, from the maximum between the two regressions.
6
Repeat over all timesteps
Repeat over all time steps stepping backwards fromt=Y to t=0.
7
Update initial value estimate
When time zero is reached, the value function will disagree with the estimate from step 0.Update with the derived initial value and recommence from step 0 until convergence of the initial estimate is achieved.The solution space is discretised{t0,t1,…,tM}⊂[0,Y] in time over with equally spaced intervals. A number of simulations N is selected for the algorithm.


## 4.2. Simulations of the Poll Trajectory

At the heart of the Monte Carlo approach is the simulation of solutions to the SDE (3.1), and this section describes our approach to generating random trajectories of the poll process. A theoretical investigation in [23] of the governing equation (3.1) demonstrated convergence of polygonal approximations to the solution. Consequently, the Euler Maruyama [28] approximations are guaranteed to converge to the true solution in the limiting case of diminishing step sizes.Sample trajectories of the poll process are modeled using the Euler Maruyama formulation expressed in (4.1). Let dt represent small time step discretisations over the electoral term [0,Y]. Let S(j) represent the value of the poll process in the jth time step. Then, we write
(4.1)S(j+1)=S(j)-μS(j)(1-S(j)2)dt+σdtN(j),
where N(j) is a standard independent Gaussian variable. We next discuss how the election process is simulated. At any exercise point (i.e., an election is called), the electoral cycle passes through the following stages. Suppose that an election is called at time τ. (i)
Campaign time: the election passes into a campaigning period and the government into a “caretaker” mode. The poll process St continues to diffuse over the period [τ,τ+TL].(ii)
Sampling error: at time τ+TL an election is held, and the true proportion of votes won by each party is revealed. However, this may deviate from the poll state measured by Sτ+TL owing to sampling and response error. The simulation process incorporates sampling error by conducting an additional transition at time τ+TL:
(4.2)Sτ+TLactual=Sτ+TL+N(0,ε2),
where ε is calibrated in Section 3.2 as 0.022.(iii)
Regional representation error: for each simulation, at the election time, we establish the chance of winning an election by conducting a Bernoulli experiment. While the calibration (3.2) yields a small systematic bias between parties, we have renormalized with a symmetric distribution for the model. Following the variance calibration in (3.2), the chance of winning is conditioned upon the actual voting state as:
(4.3)Pr(Win∣Sτ+TLactual)=Pr(Z>0-1.4708S0.0363),
where Z is a standard Gaussian variable.


## 4.3. Value Function and the Optimality Principle

The value function is defined in Section2 as the remaining life in power and quantifies the utility of holding government. The objective of the government, using the simple control of election exercise, is to maximize its undiscounted term in government. Bellman’s principle of optimality [29] provides proof for a Markov process that the strategy which maximizes the expected value is determined by a dynamic program.Figure2 illustrates the recursive nature of establishing the value function. In order to calculate the expected value function at state (t,S), we require an estimate for the value at time zero, V(0,S).Figure 2
Recursive nature of establishing the value function. The electoral cycle commences at time zero in government. As time progresses, the poll state (red curve) diffuses. The latest date for an election (compulsory election) is at timeY years. But a government can call an early election (1) when high in the polls. A campaigning time will occur, and polls diffuse until the election date at (2). Then either the government will win the election and return to the initial problem (3) or the government will lose the election (4) and have zero remaining life in power.In more formal terms, express the state of the system as the triple(t,S,andM*), where(i)
t∈[0,Y] is the time through the current term,(ii)
S∈(-1,1) is the poll state,(iii)
M*=∞ if an election has not yet been called,(iv)
M* = time remaining until the election, if an election has been called.In the case that the election has been already called and the system is in a campaign state, then there are no decisions to be made.LetQ be the strategy to call an election if (t,S)∈Ω and to continue without calling otherwise. Let the remaining time in power be L when applying strategy Q.The value functionV is then,
(4.4)V(t,S)=E(L∣(t,s)).The optimization problem is then a strategy selection problem:(4.5)max{V∣Q}.According to the Bellman principle of optimality [29], the problem for the value function and the optimal control can be written when M*=∞ as
(4.6)V(t,S)=max{dt+E(V(t+dt,St+dt)),tL+E(V(0,St+tL+ε))×Pr(Win∣S=St+TL+ε)}.The terminal condition is a forced election, that is,(4.7)V(t,Y)=E(V(0,SY+tL+ε))×Pr(Win∣S=SY+TL+ε).The first term in (4.6) represents continuing with certainty to time t+dt and reassessing the decision, while the second term represents calling an election, continuing in power with certainty over the campaign period and then extending the term in power only if the election is won. If the former is the larger, then the optimal decision Q is to continue, while if the latter dominates, then an exercise decision should be made.We initially assume a structure forV(0,S) which is iteratively refined as the algorithm proceeds. At the final available exercise time (Y-TL), we impose an exercise event upon the government. Consequently, there is a diffusion of the polls for period TL, a random error to the actual poll state, and an error between the poll state S* and the proportion of sets won, which consequently yields either an election as won or lost. We can subsequently calculate V(Y-TL,S), being the value of the remaining time in power, which will be V(0,S*) if the election is won and zero otherwise (here S* represents the poll state on election day).A stochastic dynamic program implements the principle of optimality by back stepping from the terminal condition, progressing through timestepsY-TL-dt,Y-TL-2dt,… and so on, and making the comparison (4.6).The MLS method does not enumerate all states explicitly but creates a regression to approximate the two terms in (4.6), based on simulated outcomes for the poll trajectory and election outcome.The method requires an estimate for the initial valueV(0,S),-1≤S≤1. The algorithm recursively step back to time zero, and derives an estimate for V*(S)=V(0,S) which will inevitably disagree with the original estimate. The technique assigns V(0,S) to be the solution V*(S) from the previous iteration. We iterate the process several times to achieve convergence for V(0,S).In contrast to the method on American options [20], at the point of calling an election, the payoff from the decision is unknown. For the MLS method, we must establish the expected life in power remaining if the election is called, which includes a time lag, an uncertainty of electoral outcomes, and a dependence on the initial condition V(0,S).


## 4.4. Simulation of the Exercise Decision

Unlike the typical American Option problem in finance, when the option holder (the government) exercises the option (calls an early election), the payoff is not known with certainty. Instead, there is a lag of around 55 days from calling to holding the election, during which time the polls can diffuse. The measured poll state at the final date is distorted from the actual poll state owing to sampling and response errors. And finally, the mapping of the proportion of votes to the number of parliamentary seats won is not certain and can result in an exaggerated majority.Consequently, at each decision point of call/continue, the MLS method requires to establish the expectation of the value function under the alternatives of calling an election or continuing to the next decision point. There following alternatives are available for the practical implementation to estimate those expectations:(i)
analytical approach: calculate the expectation of the value function from state (t,S) upon the assumption of calling an election, by deriving the solution to the SDE over (t,t+tL), analytically introducing the sampling error and the regional representation error,(ii)
regression approach: use Monte Carlo simulations to model the diffusion, and the other sources of uncertainty, and regress against the state variable S.In this paper, we will pursue theregression approach to fully promote the LS philosophy, and to demonstrate how the technique is capable of handling complex option structures, potentially on many variables, which are not amenable to analytical solution.


## 4.5. Regression Process

As the MLS proceeds, at each time step a regression is performed between the poll state and the payoff or value function. In the seminal paper of Longstaff and Schwartz on the American Option problem [20], a representative example is presented, where a quadratic function is applied for the regression. Since then a large number of papers have extended the concepts, and a key element has been advanced in the basic functions applied in the regression.Figure3 graphically illustrates how the regression is applied in the MLS. Suppose that we have N simulations of the poll process. Suppose that we have applied the MLS from t=Y backwards to time t. At time t, the simulated polls are scattered between -1<Stn<1. For each simulation, we evaluate the value function upon a decision to exercise, and the value function if not continuing.Figure 3
Value function regressions on basis of call or continue. Figure contains remaining life on each simulation under assumption of calling the election (blue scatterplot) and its regression (blue curve), remaining life under assumption of continuing without calling (red scatterplot) and its regression (red curve), and maximum outcome of the two decisions (broken black curve).If continuing, the value function for simulationn is
(4.8)V(t,Stn)=dt+V(t+dt,St+dtn).And if the process continues, the value function will be determined from the simulated election outcome:(i)
V(t,Stn)=TL+V(0,S*) if the election is won,(ii)
V(t,Stn)=TL+0 if the election is lost.The valueS* is the poll state at the commencement of the new term, based on the final poll state at time t+TL.Figure3 is generated from extracting the regressed data at point time around two years into a three-year term, in the first iteration of the algorithm. It illustrates the simulated outcomes under the assumption of calling an election at time t from the simulated poll states, here varying from −0.4 to +0.4. It can be seen that for high poll states, the probability of winning an election is high, and the resultant remaining life is around 6 years. If the polls are low, then there is a low probability of winning the election, and there are numerous outcomes, where the remaining life in power is simply TL.The figure illustrates the dichotomous nature of the electoral process: the outcome of the election is either a win (with a greatly extended life in power) or loss (with limited life in power remaining).The figure is also overlaid with the call decision outcome and with the continue decision outcomes. Under the strategy to continue until the next decision timet+dt, the polls will diffuse slightly. The value function V(S,t+dt) is a smooth function not exhibiting the discontinuous nature of the call decision.Comparing the two regressions, it becomes an optimal strategy for the government to select the alternative which maximizes the value function, which is a call decision if the polls are sufficiently high and a continue decision otherwise. The ability to defer the election decision delivers asymmetric benefit to the government, and with some imagination, the “kink”, the black curve atS=0.25, has some resemblance to a call option payoff from finance.In the present problem, we apply a polynomial fit for the regression. Some motivation for the polynomial fit is provided by the rapid speed of fitting a large number of points to a smooth curve: a task which must be done many times in the algorithm. Alternative fits such as sigmoidal functions provide other avenues of research.Intuitively, given the high mean reversion tendency of the process (μ=3.49), the value function near time zero should be near constant, and a polynomial accommodates this shape.The value function near the terminal time (t=Y) should be intuitively represented by an “S” shaped curve. If the poll state S is low (near −1), then the value function will be near zero as there is low chances of reelection (V≈0). If the poll state is high (near +1), then election victory is nearly assured. For S near zero, the probability of an election victory is approximately 0.5, and we can expect an intermediate value. Provided that the order of the polynomial exceeds a cubic, we are able to force this familiar “S” shaped curve expected of our solution.


## 4.6. Selection of the Initial Value

In selecting the initial value, we choose a constant function. Motivation arrives from the following reasons.(i)
The mean reversion of the SDE dictates that the poll state tends to a stationary distribution.(ii)
The relatively high mean reversion tendency(μ=3.49) means that the poll state loses information quickly.(iii)
Under the assumption of a fast mean reversion rate and no systematic bias for one party to win an election, the unconditional probability at time zero of a party losing the next election without an ability for early exercise is 0.5 (i.e., life in power isY years). The probability of winning the first election but losing the second election is 0.52 (i.e., life in power is 2Y years), the probability of two wins then a loss is 0.53(i.e., life in power of 3Y years), and so on. This expected life arising from this pattern can be calculated explicitly as a progression. 											(4.9)Expected  life  in  power=∑n=1∞n×Y2n=2×Y.This becomes our starting estimate (i.e., 6 years).


## 5. Results

### 5.1. Sample Trajectories

Figure4 illustrates sample trajectories generated from the solution to SDE (3.1). The solutions exhibit mean reversion and in practical terms exist in a range around -0.4≤St≤0.4. The trajectories visually compare with the historical polls data with a similar qualitative structure.Figure 4
Sample trajectories (grey) and historical polls April 1993–March 2012 (blue).


### 5.2. Convergence Behaviour

The algorithm described in Section4 has been applied with the parameterisation described in Section 3. The method has been applied with(i)
10,000 simulations,(ii)
campaign time 55 days,(iii)
daily exercise decisions,(iv)
iterating the algorithm until a practical level of convergence of the initial conditionV(0,S).Owing to the random nature of the algorithm, perfect convergence of the initial condition is not expected, and we have set a threshold of achieving no more than 1% error (in norm) ofV(0,S) in successive iterations to establish a practical fixed-point solution. The number of iterations required to achieve practical convergence was achieved in around 20 iterations.Figure5 represents the value function at time t=0 upon each iteration from 1 to 100. We can see the initial value at 6 years. With each iteration, note the improvements to a converged level. The solution indicates that with the benefit of calling early elections, the expected life in power is enhanced to around 10 years.Figure 5
Progressive updates to estimate of initial valueV(0,S) demonstrating convergence of the algorithm.


### 5.3. Call Exercise Boundary

The call boundary is generated by the algorithm to maximize the value function. In reality, because the approach is based on a statistical regression, the exercise boundary will not be a smooth contour.Articles [4, 5] have also generated the optimal boundary applying stochastic dynamic programming. The solutions qualitatively compare well.The algorithm generates a collection of sample points in the state space which are all distinguished ascall or continue points. The exercise boundary is defined as the manifold which divides the state space between these two strategies. In other words, for each t, it is the minimum over all S which warrants exercise, or the maximum over all S which warrants continuation.Figure6 illustrates the outcome of all call decisions made in the simulation. That is, when the simulations ever arrived at these state spaces, the optimal decision was to exercise. Calculation for each trajectory, the position in state space (t*,S*) the first time at which exercise is warranted, is given in Figure 7 below.Figure 6
Outcome of all call decisions.Figure 7
Calculation for each trajectory and the position in(t*,S*) the first time at which exercise is warranted.Figure8 establishes the minimum level S at each time interval over each of the time steps. Figure 9 performs a fit over the minimum values to illustrate a smooth fit to the simulated boundary of the form:
(5.1)boundary=a0+a1t-3+a1t+a2t2+a3t3.Figure 8
The minimum levelS at each time interval over each of the time steps.Figure 9
A fit over the minimum values with polynomial and square root.The behavior of the boundary near the terminal time att=Y fits closely with a square-root process, which is also a familiar feature of financial options nearing maturity.Figure10 below illustrates an intensity plot of binary variables representing the call or exercise decisions of the final iteration. The x-axis represents the discretised states S from −0.3 to +0.3 while the y-axis represents time, with t=0 at the top of the plot and the expiry of the term t=Y along the bottom of the plot.Figure 10
Intensity plot of exercise decisions.


### 5.4. Value Function

The value function is calculated from 10,000 simulations with a 3-year term. There are 20 recursive iterations to converge on the starting value at time = 0. The “kink” in the value function is apparent in the surface plot in Figure11 where the exercise boundary delineates the continue strategy from the call boundary. An indication with an arrow is provided to guide the reader directly.Figure 11
Value function surface plot.The 2-d and surface plots actually represent the period 0 toY-TL, as there is no decision to be made in the final TL period. As expected, as time proceeds and the polls are in a poor state, the value function decays and similar to financial option prices appears to decay with the square root of time. At the final time, the diffusion equation (running backwards) does not converge to a sharply defined value like a financial option payoff, owing to the fact that residual randomness arises at the point of calling an election due to (a) the diffusion in polls until the election date, (b) the sampling and response error, and (c) the effect of the exaggerated majority. The shape and quantum of the value function all concur with the results generated by different solution methods, such as SDP [4].Timing performance of the algorithm was very good, with the algorithm as described executing in around 20 seconds on a standard 32 bit desktop PC, which represents an order of magnitude in improved speed over a SDP. However, the nature of the Monte Carlo yields nonsmoothness in the estimated boundary and requires a high volume of simulations to deliver the accuracy of a SDP.


## 5.1. Sample Trajectories

Figure4 illustrates sample trajectories generated from the solution to SDE (3.1). The solutions exhibit mean reversion and in practical terms exist in a range around -0.4≤St≤0.4. The trajectories visually compare with the historical polls data with a similar qualitative structure.Figure 4
Sample trajectories (grey) and historical polls April 1993–March 2012 (blue).


## 5.2. Convergence Behaviour

The algorithm described in Section4 has been applied with the parameterisation described in Section 3. The method has been applied with(i)
10,000 simulations,(ii)
campaign time 55 days,(iii)
daily exercise decisions,(iv)
iterating the algorithm until a practical level of convergence of the initial conditionV(0,S).Owing to the random nature of the algorithm, perfect convergence of the initial condition is not expected, and we have set a threshold of achieving no more than 1% error (in norm) ofV(0,S) in successive iterations to establish a practical fixed-point solution. The number of iterations required to achieve practical convergence was achieved in around 20 iterations.Figure5 represents the value function at time t=0 upon each iteration from 1 to 100. We can see the initial value at 6 years. With each iteration, note the improvements to a converged level. The solution indicates that with the benefit of calling early elections, the expected life in power is enhanced to around 10 years.Figure 5
Progressive updates to estimate of initial valueV(0,S) demonstrating convergence of the algorithm.


## 5.3. Call Exercise Boundary

The call boundary is generated by the algorithm to maximize the value function. In reality, because the approach is based on a statistical regression, the exercise boundary will not be a smooth contour.Articles [4, 5] have also generated the optimal boundary applying stochastic dynamic programming. The solutions qualitatively compare well.The algorithm generates a collection of sample points in the state space which are all distinguished ascall or continue points. The exercise boundary is defined as the manifold which divides the state space between these two strategies. In other words, for each t, it is the minimum over all S which warrants exercise, or the maximum over all S which warrants continuation.Figure6 illustrates the outcome of all call decisions made in the simulation. That is, when the simulations ever arrived at these state spaces, the optimal decision was to exercise. Calculation for each trajectory, the position in state space (t*,S*) the first time at which exercise is warranted, is given in Figure 7 below.Figure 6
Outcome of all call decisions.Figure 7
Calculation for each trajectory and the position in(t*,S*) the first time at which exercise is warranted.Figure8 establishes the minimum level S at each time interval over each of the time steps. Figure 9 performs a fit over the minimum values to illustrate a smooth fit to the simulated boundary of the form:
(5.1)boundary=a0+a1t-3+a1t+a2t2+a3t3.Figure 8
The minimum levelS at each time interval over each of the time steps.Figure 9
A fit over the minimum values with polynomial and square root.The behavior of the boundary near the terminal time att=Y fits closely with a square-root process, which is also a familiar feature of financial options nearing maturity.Figure10 below illustrates an intensity plot of binary variables representing the call or exercise decisions of the final iteration. The x-axis represents the discretised states S from −0.3 to +0.3 while the y-axis represents time, with t=0 at the top of the plot and the expiry of the term t=Y along the bottom of the plot.Figure 10
Intensity plot of exercise decisions.


## 5.4. Value Function

The value function is calculated from 10,000 simulations with a 3-year term. There are 20 recursive iterations to converge on the starting value at time = 0. The “kink” in the value function is apparent in the surface plot in Figure11 where the exercise boundary delineates the continue strategy from the call boundary. An indication with an arrow is provided to guide the reader directly.Figure 11
Value function surface plot.The 2-d and surface plots actually represent the period 0 toY-TL, as there is no decision to be made in the final TL period. As expected, as time proceeds and the polls are in a poor state, the value function decays and similar to financial option prices appears to decay with the square root of time. At the final time, the diffusion equation (running backwards) does not converge to a sharply defined value like a financial option payoff, owing to the fact that residual randomness arises at the point of calling an election due to (a) the diffusion in polls until the election date, (b) the sampling and response error, and (c) the effect of the exaggerated majority. The shape and quantum of the value function all concur with the results generated by different solution methods, such as SDP [4].Timing performance of the algorithm was very good, with the algorithm as described executing in around 20 seconds on a standard 32 bit desktop PC, which represents an order of magnitude in improved speed over a SDP. However, the nature of the Monte Carlo yields nonsmoothness in the estimated boundary and requires a high volume of simulations to deliver the accuracy of a SDP.


## 6. Conclusions and Future Work

In this paper we have developed adaptations of a technique which has proven to be successful in financial engineering and applied it to find the optimal exercise boundary in the early political election problem. Our technique was based on the Longstaff-Schwartz method used in estimating the exercise boundary for American options. The solution method is fast, and the results compare favourably with traditional methods such as SDP and PDE.The solutions clearly display some inaccuracies in the fit for poll outcomes in the extreme. We expect (and can prove) that solutionsV(t,S) must be monotone in S at each t, but the solutions, particularly near t=Y exhibit inflections at the extreme. The cause of this modeling inaccuracy is owing to the section of a polynomial fit and the fact that the strong mean reversion of the model (4.6) yields few solution trajectories in this zone. In other words, the polynomial fit successfully achieves an accurate representation of the value function, weighted according to the frequency of observations, which are concentrated roughly over S⊂[-0.2,0.2].The use of a sigmoidal or logistic function for the regression is likely to introduce a superior fit, at the cost of additional computation time. This is another avenue to pursue for further research.



---

*Source: 287579-2012-10-18.xml*