Robust Dynamic Hedging
Henry Lam
Boston University
khlam@math.bu.edu

Zhenming Liu
Princeton University
zhenming@cs.princeton.edu

Abstract
We consider a robust approach to price European and American options by modeling the market dynamic as a repeated game between the nature (adversary) and the investor. This adversarial approach has
been recently studied as a alternative to the traditional area of stochastic finance. In this paper, we build asystematic framework to study as well as to connect between two important questions in the adversarial
setup: 1) the relation to classical models such as Black-Scholes and its extensions, and 2) the design ofefficient pricing algorithms. The starting point of our analysis is an elementary characterization of the
optimal strategy for each round of the option game, which gives explicit trading strategies in replicating
options in the case of convex payoff, and allows to design and analyze a simple discretization-based
approximation algorithm for non-convex payoffs. We further use the characterization to obtain limiting
representation for options with general payoffs as diffusion processes with controlled volatilities, which
reduce to the Black-Scholes price for convex payoff and a degenerate price for the concave counterpart.
Our framework can also be adapted to American options, as well as a semi-adversary model that incorporates rare shocks in asset prices. The latter extension serves as the analog in robust pricing theory to
so-called “jump processes” in stochastic studies on option pricing.

01Introduction

In the financial market, an option is a contract that gives the holder the right, but not the obligation,
to buy or sell an underlying asset or instrument [Hul09]. Consider the “vanilla” European call option as an
example. This contract is controlled by three parameters: the underlying asset S, say a stock traded at the
New York Stock Exchange, the strike price K, and the time to expiration T . A holder of a European call
option has the right to purchase the stock at time T at the prefixed strike price K, regardless of the price ofthe stock at that time. Suppose that the stock price at time T , say S(T ) (we shall abuse notation to denote
S(t) as the price and S as the stock for convenience), exceeds K, the holder will exert his/her right, andexercise the option. In the opposite event that S(T ) submerges below K, a rational holder will initiate noaction. Assuming the market is liquid, since the holder who decides to exercise the option can sell the stock
immediately at market price, the payoff of this option at time T can be summarized as max{S(T ) − K, 0}.
In general, any single-instrument European-type option has a payoff function g(S(T )) on an underlying
asset S, depending on the terms of the contract. An American-type option, on the other hand, gives theholder the right to exercise the option at any time before maturity.
The study of the fair prices of different options has not only been a core area in financial economics, but
is also important for market practitioners, given the gigantic volume of options being traded at any trading
day [FIA12]. The area bloomed after the groundbreaking discovery of Black and Scholes [BS73], which
was later expanded by Merton [Mer73]. In order to find the fair price of an option, their main idea is tohedge against the movement of the underlying asset. Consider for example a European call option. If thepurchaser of the option, at time 0, chooses to concurrently short a portfolio that consists of the underlying
asset and cash, in such a way that the portfolio’s value at time T is exactly max{S(T ) − K, 0}, then theportfolio must cost the same as the European option; otherwise the option holder can construct an arbitrage
that generates positive profit at no downside risk, a scenario that is economically prohibited. In this way
the fair price of the option is exactly the value of the replicating portfolio. We shall elaborate this concept
further in Section 3.
Since then, there has been a huge body of literature on the pricing of options under various stochastic
models of the underlying asset. In the original work in [BS73], it was shown that a unique price can be
determined using the no-arbitrage principle if the underlying asset’s price follows a geometric Brownian
motion. Other stochastic models may or may not succumb to a unique price (the latter case is known asincomplete market). For example, a jump diffusion market, which we shall discuss later on in this paper,is incomplete, and a unique price can be obtained only under diversification [Mer76] or additional utility
structure [REK00]. See for example [CT12, HF11] for comprehensive reviews of the literature.
In this paper we shall consider a non-stochastic framework to price and hedge options. We model it
as a repeated game between the trader of the option and the “adversary” nature that controls the movementof stock price. Broadly speaking, our goal in this paper is to build a systematic framework that allows one
to answer fundamental questions that have been around in the stochastic finance community. Two suchquestions are:
Q1. What is the feature of a non-stochastic model that allows one to relate to the traditional
Black-Scholes model, the “Holy Grail” in option pricing?
Q2. Can we design efficient pricing algorithms under the non-stochastic framework and whatis the explicit hedging strategy implied by such algorithms?
These interrelated questions are motivated from both theoretical and practical viewpoint. With anunderstanding of the similarity to the well-established Black-Scholes model, one can take advantage ofexisting hedging strategies to design good pricing algorithms. On the other hand, if the non-stochastic
1

model is provably far from Black-Scholes, we want to be still able to design pricing algorithms, especiallywhen the model is capable of capturing certain salient features of the financial market. We point out that, inpractice, explicit hedging strategy is as important as the option price itself. It is only with such a strategy
that the trader can replicate a portfolio, thereby realizing the value of the option.
While the posted questions are important and natural, there appears to exist limited amount of work.
Moreover, the scopes of these works are each confined to quite specific settings and lack the ability togeneralize; in fact, even for the simplest case of convex European options, the analysis involved can becomplicated and non-constructive. For example, the work of Abernethy et al. [AFW12] provides a convergence result to Black-Scholes for convex options, but the proof is non-constructive, and hence is noteasily generalizable to non-convex payoffs or American options. Regarding algorithmic results, DeMarzoet al. [DKM06] and more recently Gofer and Mansour [GM11] focus on the adaptive adversary setting andpropose regret minimization algorithms; however, their technique is confined to convex payoff functions;the same holds for the line of work in [RES05, Ber05a, Ber05b, Kol11], which is also limited to analysis onconvex options. Chen et al. [Che10] and Bandi and Bertsimas [BB12], on the other hand, consider general
options (both European and American), but they model the nature as oblivious. Taking into account theseprevious limitations, our goal in this paper is to give the first comprehensive study on a non-stochastic modelthat can address both of the posted questions, for both European and American options, and with possibly
non-convex payoff.
Our work and contribution. We consider a model in which the stock price movement at each step isrestricted to a bounded deterministic set. Our choice of this model is two-fold. First, from the practical
viewpoint, an estimate of the worst-case upper and lower bound of price movement is very attainable (relative to, say, the worst-case moments). Secondly, as we shall see, this simple model allows us to analyze
options that are structurally difficult (such as non-convexity, and American-type), and to propose efficientpricing algorithms. It also allows us to draw insight from some previously considered settings through simplified analysis, which can be subsequently generalized to more complex situations. The following are a
few key algorithmic results that we contribute:
1. We start with analyzing the equilibrium of the European option game per round based on elementary
techniques. Such result enables us to connect with the standard Black-Scholes model at the limit andgives us explicit hedging strategy, when the payoff function is convex.
2. We further leverage this technique and design constructive algorithm for more complex financial
derivatives. In particular, we analyze an approximation algorithm to robustly price any options whose
payoff function is monotonic and Lipschitz continuous.
3. We show that, for non-convex option, convergence to Black-Scholes is not guaranteed. The limitingbound on the price, instead, is the optimal value of a continuous-time control problem with volatility
constraint.
4. We generalize the above results to two other important settings. First, we extend our algorithmic andconvergence results to American-type options. Second, we adapt our model and algorithmic result
to incorporate rare jumps in the financial market. The latter is important because non-smooth pricemovement is ubiquitous in financial markets, e.g., it can model “volatility smile” [Kou02].
In the supplementary material, we complement our algorithmic contribution with two hardness results: 1)
exactly computing the option price’s upper bound in a finite round hedging game is #P -hard even forconvex functions, when the uncertainty sets across different rounds are non-uniform; 2) our algorithm’s
approximation quality is near-optimal when we access the payoff function through an oracle. Figure 1
summarizes the contribution of this paper.
Our techniques.

The subject of option pricing has traditionally been an interdisciplinary area, drawing
2

European
Convex(Lipschitz)
European
NonConvex (Lipschitz)
AmericanJump1

Convergence
Yes (simplified)
Yes (new)Yes (generalized)
Yes (new)

Algorithm
Approximation(new)Approximation(new)Approximation(generalized)
Approximation(new)

Explicit Hedging
Yes
(was
open
in [AFW12])
Yes (new)Complexity#P -Hard (new)Yes (generalized)

Tight in the oracle
model (new)Same as above

Yes (new)Same as above

Figure 1: Summary of our contribution.
interest from the finance, operations research, statistics, and more recently the computer science community.
The development of algorithms and their analysis should, unsurprisingly, blend together ideas originatingfrom inside and outside computer science, most notably from convex optimization and stochastic analysis.
Consequently, we shall also follow this interdisciplinary nature in this paper, while taking an algorithmiccentric view. The advantage of this is two-way: algorithmic tools can help us gain better insight on the
problem of option pricing; on the other hand, these “exotic” ideas can help us develop new methods foranalyzing algorithms and formulating new and natural theoretical questions. Below we highlight a numberof conceptually new techniques and problem formulations that result from such idea-synthesization:
1. Construction of artificial probability measure in analyzing a deterministic algorithm. As will beseen later on, we design a deterministic algorithm for pricing non-convex options, and the challenge
lies in the analysis of the algorithm. Here, we attach an “artificial” probabilistic measure to thedeterministic algorithm so that the movement of the algorithm can be characterized by the statistics
under this artificial measure. At the end, analyzing the performance of this deterministic algorithm
reduces to understanding the behavior of a standard martingale. This way of analyzing a deterministic
algorithm appears to be new.
2. An online algorithm where the adversary is allowed to withdraw. In the case of American put
option, the adversary is allowed to exercise the option early. From the viewpoint of online learning
problem (which aims to maximize the payoff), this is equivalent to the feature that the adversary
can “withdraw” from the game. Allowing the adversary to behave in this way appears to be new inthe literature. Our formulation here gives the first natural problem under such setting and the first
non-trivial analysis.
3. Analysis of a limiting process inspired by the underlying combinatorial structure. Understanding
the limiting behavior of financial derivatives is not often a focus in computer science. Nevertheless,
we present a major convergence result for non-convex options, for two reasons. First, such result isa coherent part of our robust dynamic hedging framework. Second, we want to convey the message
that the combinatorial techniques and insight we develop can lead to “broader consequences” to otherimportant areas.
Along the discussion above, we shall close our introduction by mentioning two important concepts in classical option pricing theory that are intimately related to this paper. The first is the celebrated binomial treemodel [CRR79], as a discrete-time analog of the approach in Black-Scholes, whereby the market at eachtime step can only go to two levels, up or down. This model is computationally convenient and converges tothe Black-Scholes price in continuous-time limit. Its extensions, such as trinomial and general multinomial
tree models, are also well studied [MMS89, He90]. We will demonstrate how our robust framework reduces
to these models under convexity conditions of the option payoffs. Next, the second important concept is thenotion of risk-neutral measure, as a convenient probabilistic tool to compute option prices. The so-called
fundamental theorem of asset pricing asserts that under no-arbitrage condition, the fair option price can3be computed as the expectation under an artificial probability measure, the risk-neutral measure, when themarket is complete [Duf05]. The concept has also been extended to incomplete market by imposing various
risk/utility structures [Shr04]. As we shall see, this notion of risk-neutral measure will appear as the optimal solution of a dual problem in our formulation, and will also serve as an important proof vehicle in our
deterministic setup.
Organization. We describe our model in Section 2. Section 3 analyzes the equilibrium of our minimax
game and gives convergence results for convex payoff functions. Section 4 and Section 5 present algorithmand convergence result for pricing options with general payoff functions. Section 6 discusses how our model
can incorporate price jumps. Section 7 generalizes our results to American options. In the appendices, we
present hardness results as well as an alternative way to prove Black-Scholes convergence from a control
formulation derived in Section 5.

2

Our model

Discrete game. We now describe our model, which has a similar spirit to [Ber05b, AFW12]. Throughout
the paper we shall focus on a discrete-time setting, i.e., the trader only has the chance to trade at discrete time
points. Continuous-time implications of our models will be discussed in Section 3. Specifically, consider an
option that expires T days from now. We denote time 0 as the time when a transaction of the option occurs,i.e., a trader either buys or sells the option. We assume that, before the option expires, the trader has in total
τ time points that allow trade execution. Let these time points be t = Tτ , 2T
τ , ...., T . Notice that as soon asτ is decided, the value T is not a parameter in the game (but will reappear in our continuous-time limit lateron). Throughout our analysis we assume no transaction costs and the market is liquid (i.e., the trader canalways buy or sell any volume of the asset at the market price at the τ time points).
We shall model the dynamic of the financial market from time 0 to T as a τ -round two-player gamebetween the trader and nature. Consider an option on the underlying asset S, with initial price S0 and theprice at the t-th round denoted as St (= S(tT /τ )). For each round t, where 1 ≤ t ≤ τ , the adversary hascomplete freedom to choose the return of S, given by Rt , St /St−1 − 1, within a pre-specified uncertainty
set Utτ (we will often drop the τ in Utτ and use the notation Ut when no confusion arises). On the other hand,at the beginning of each round, the trader can choose to long2 ∆t dollars’ worth of the asset (a negative ∆twill imply a short position). At this point we do not impose any capital capacity on the trader, i.e., ∆t can beas large or small as possible; however, we shall soon see from our analysis that the optimal ∆t is bounded
and can be explicitly found.
Let us first describe what should be the upper and lower bounds of the option price under no arbitrage
assumption in our model. To better illustrate our ideas, all of our analysis will assume the risk-free interest
rate is 0. But all our results can be adapted easily to non-zero interest rates.
Upper bound. Suppose the trader shorts the option at time 0. To hedge his/her position, at each round of thegame, the trader decides toP
buy ∆t dollars’ worthQof the underlying asset. The cumulated payoff to the traderat time T is then given by τt=1 (Rt ∆t ) − g (S0 τt=1 (1 + Rt )), plus the option price that he/she gets fromselling the option at time 0. Since a rational trader will strive to maximize gain, against an adversarythatP
strives to minimize so, the outcome of this game to the trader will be max∆t ,t∈[τ ] minRt ∈Ut ,t∈[τ ] τt=1 (Rt ∆t )−Q
g (S0 τt=1 (1 + Rt )), again plus
Now, if the option price is strictly higher than
P the initial option price.
Q− max∆t ,t∈[τ ] minRt ∈Ut ,t∈[τ ] τt=1 (Rt ∆t ) − g (S0 τt=1 (1 + Rt )), then shorting the option and carryingout the optimal hedging strategy gives the trader a positive gain at time 0 with no risk, i.e., an arbitrage
1
2

We will study two natural jump models, and the contributions depend on the specific models we study.
We adopt the terminology in finance: to “long” means to buy, and to “short” means to sell a product.

4

opportunity arises. In other words, the option price at time 0 cannot be higher than
min

max

∆t ,t∈[τ ] Rt ∈Ut ,t∈[τ ]

g S0

τ
Y

!
(1 + Rt )

t=1

−

τ
X

(Rt ∆t ).

(1)

t=1

Lower bound. The no-arbitrage lower bound can be obtained by reversing the action of the trader fromshorting to longing the option at time 0. SupposeQthe trader shorts ∆Pt dollars’ worth of the underlying asset
at the t-th round, and strives to maximize g (S0 τt=1 (1 + Rt )) − τt=1 (Rt ∆t ). It can be argued similarlythat the option price cannot be lower than
!
τ
τ
Y
X
(Rt ∆t )(2)max
min g S0 (1 + Rt ) −∆t ,t∈[τ ] Rt ∈Ut ,t∈[τ ]

t=1

t=1

or otherwise arbitrage opportunity arises.
We note that this model is closely related to the one studied in [AFW12]. There, they impose a roundwise second moment constraint on the adversary. When the payoff function is convex, both constraints areequivalent algorithmically (see Section 3.4). When the payoff function is non-convex, the adversary may
want to impose sparse jumps in its optimal strategy in [AFW12]’s model (and thus violating our uncertainty set constraints) but then second moment would not be a natural constraint for jumps (see discussions
in [CT12]). Section 6 discusses how we incorporate price jumps in our model.
Interpretation of bounds. We remark that the definition of upper and lower bounds here is different fromwhat one often sees in Computer Science. When there is a “gap” between upper and lower bounds, it does
not mean the bounds are not “tight”. Instead, we shall interpret our bounds as follows: let u be the upperbound from (1) and ` be the lower bound from (2). We have:• When an option price does not fall into [`, u], then there exists a trading strategy so that under any
adversarial scenarios the overall payoff of the strategy is strictly positive (arbitrage exists). Economically speaking, this is a “wrong” price of the option.
• When an option price is in [`, u], then for any trading strategy, there exists an adversary so that thepayoff is non-positive (arbitrage does not exist). This price can be the “fair” price of the option.
Oracle model for payoff functions. We assume we have oracle access to the payoff function g(·) (whichis possibly non-convex). Also, when saying g(·) is Lipschitz continuous, we mean that for any real values
x, y, we have |g(y) − g(x)| ≤ L|y − x| for some constant L.
Continuous time limit. To take continuous-time limit, we fix T and take τ → +∞. Let {Utτ }t≤τ τ ≥1 be
a sequence of uncertainty
set collections. We say an option’s upper (lower) bound has continuous-time limit τwith respect to {Ut }t≤τ τ ≥1 when the upper (lower) bound with uncertainty sets {Utτ }t≤τ converges asτ → ∞.
We remark that the user of the model should not interpret the discrete-time multi-round model as only
a “discrete approximation” of the continuous time case. Instead, the user can choose an arbitrary τ and thenestimate the uncertainty sets accordingly. So long as the uncertainty sets accurately bound the movementof the stock price, our upper and lower bounds will be legitimate. It is expected that the upper and lower
bounds we derive here have the highest quality when τ is suitably large and Utτ can be accurately estimated.
When τ is too large, it might become more difficult to estimate Utτ , and the quality of the corresponding
upper (lower) bound could be worse. The practical choice of such an optimal τ is out of the scope of thispaper.
We also remark that we leave the choice of the uncertainty set Utτ to depend on the round t. A reasonable approach to construct uncertainty sets is of course to set all Utτ to be equal over time, in which
5case we shall merely denote U τ (or even U). Putting time dependence on the uncertainty sets neverthelessallows modeling flexibility, and is indicative of state-dependent model, i.e., the uncertainty set can dependon the current underlying asset price. The latter is the robust analog of continuous-time models that havestate-dependent volatilities, such as the Heston model [Hes93].

3

Explicit characterization of equilibrium for the hedging gameIn this section we will analyze the equilibrium between the trader and the nature in every single round.
In particular, we will obtain an explicit optimal hedging strategy for the trader. It then follows from standard
results that the continuous-time limit of the equilibrium is the Black-Scholes price.
We will start with the standard binomial tree model and connect its analysis to our adversary model.
Doing so gives us insight on how we shall “battle” against the adversary in more general scenarios.

3.1

Binomial tree as a weak adversary model

Single-round case. Suppose there is only one round of the game, i.e., τ = 1. Here the trader needs only to
decide ∆, the amount of the underlying asset S to hold for hedging. In the standard single-round binomial
model (see Chapter 12 in [Hul09]), the stock price either goes up by a factor of (1+u) or down by a factor of(1 − d) (see Figure 2). In the literature, it is typically assumed that the movement of S is stochastic, i.e. withcertain probability S goes up and another probability it goes down. The idea of perfect hedging [CRR79] is
to pick ∆ such that the total payoff at time 1 is constant, regardless of the movement of S. In other words,
set ∆ that satisfies
g(S0 (1 + u)) − ∆u = g(S0 (1 − d)) − ∆(−d),
which gives ∆ = (g(S0 (1 + u)) − g(S0 (1 − d)))/(u + d). Under this hedging strategy ∆, there is no risk
for the trader to be compensateddug(S0 (1 + u)) +g(S0 (1 − d)).
(3)
u+d
u+d
Suppose the option price is different from (3), then an arbitrage opportunity must exist. If the price is higher,
the trader shorts the option and longs ∆ dollars’ worth of the underlying asset, whereas if the price is lower,
the trader longs the option and shorts the same amount of the underlying asset. Both cases lead to risk-freegain to the trader.
Let us now go back to our model described in Section 2, with an uncertainty set U = {u, −d}. Thisis the same as the standard binomial model except that stochasticity of the underlying asset price is now
replaced by adversarial movement. The upper bound (1) becomesg(S0 (1 + u)) − ∆u = g(S0 (1 − d)) − ∆(−d) =

min

max

∆ R∈{u,−d}g(S0 (1 + R)) − R∆.

%

+10

(4)

B
$11.0

A
$10.0

−10
%

C
$9.0

Figure 2: A one step binomial tree model. The uncertainty set in this example is {−10%, 10%}. The priceof the underlying asset is $10. At the end of the game, the price can either move to $11 or $9.
6

It is easy to observe that (4) reaches optimum when we set ∆ such thatg(S0 (1 + u)) − ∆u = g(S0 (1 − d)) − ∆(−d),(5)

or ∆ = (g(S0 (1 + u)) − g(S0 (1 − d)))/(u + d), leading to the same hedging strategy as the standard(stochastic) binomial model. The same argument works for the lower bound (2) and gives rise to the same
hedging strategy. We thus have our first basic conclusion: If the uncertainty set in our hedging game isbinomial, the upper bound of the option price matches the lower bound; moreover, this unique price is thesame as the price concluded from the standard (stochastic) binomial model.
We also make another observation on the form of our optimal value i.e., the equilibrium. Since theoptimal hedging amount ∆ for (1) and (2) are both equal to the standard binomial model, their corresponding
optimal values are both given by (3), which can be written as
min

max

∆ R∈{u,−d}g(S0 (1 + R)) − R∆ = max∆

minR∈{u,−d}g(S0 (1 + R)) − R∆ = EΣ [g(S0 (1 + R))](6)

where Σ assigns probability d/(u + d) to upward movement u and probability u/(u + d) to downward
movement d. It is easily observed that Σ is “risk-neutral”, i.e., ER←Σ [R] = 0. Hence in this particular caseour upper and lower bounds of the option price are both characterized by the same risk-neutral probability
measure on the option payoff. We will see that in more general scenarios, the option price bounds can still
be characterized by risk-neutral measures, but the measures can be different from each others, and also they
can be both different from the measure used in standard binomial pricing. Note that these risk-neutral measures act as analytical artifacts and do not have a real-world correspondence; they will play a key role in our
analysis in the rest of this paper.
Multi-round case. Keeping in mind the result above for the single-round case, our price bounds for themulti-round setting can be obtained through straightforward backward induction (dynamic programming).
Suppose the game has τ rounds and each round entails either an up or a down movement for the stock, i.e.
Ut = {u, −d}. The upper bound (1) can be written as

min

max

∆t ,t∈[τ ] Rt ∈{u,−d},t∈[τ ]

= min

max

!
τ
τ
X
Y
(Rt ∆t )g S0 (1 + Rt ) −{· · · min∆1 R1 ∈{u,−d}

t=1

t=1

max

{· · · min∆τ −1 Rτ −1 ∈{u,−d}max{g (Sτ −1 (1 + Rτ )) − Rτ ∆τ }∆τ Rτ ∈{u,−d}−Rτ −1 ∆τ −1 } · · · − R1 ∆1 }(7)

The quantity (7) can be solved by iteratively computing gτ (S) = g(S) and
gt−1 (S) = minmax∆t Rt ∈{u,−d}gt (S(1 + Rt )) − Rt ∆t .

for t = τ, τ − 1, . . . , 1. By our result above, the solutions to each of these minimax problems are given byEΣ [gt (S(1 + R))]. Hence our upper bound again matches the lower bound, and they both match the priceaccording to the standard binomial tree model.
Figure 3 illustrates an example with two rounds. A denotes the state at time 0, B and C at time 1 andso on. We first compute the price of the option at B, by analyzing the one-stage game assuming B is theinitial time point. The same argument applies to state C. We then price the option with initial state A by
7

D
$12.1

%
+10

B
$11.0

%
+10
−10
%
E
$9.9

A
$10.0

−10
%

C
$9.0

%
+10
−10
%
F
$8.1

Figure 3: A two-step binomial tree model.
taking into account the maximal gain the trader can make in the future when the next states are in B or C.
Observe that there are in total 3 states in this example, instead of 22 = 4, at the end of the second round. In
general, the number of states at the final level of a binomial tree grows linearly with the depth of the tree,
which makes it a feasible device for option pricing.
Binomial tree at the limit. Since our adversary binomial tree model is in effect the same as the standard model, the continuous-time limit converges to the Black-Scholes price under appropriate scaling. The
following result is a rephrase of the well-known result in the literature:
Proposition 3.1. Consider the τ -round European option game. Let the uncertainty set for each round be√√
U τ = {u/ τ , −d/ τ }. Let g(·) be an arbitrary Lipschitz continuous payoff function. The upper and lower
bounds of the option with respect to U τ are the same for any τ and they both converge to the Black-Scholes
price as τ → ∞.

3.2

A general characterization of equilibrium

We now state our characterization results for a single-round game under very general conditions on theuncertainty set and the payoff function. We will concentrate on the upper bound (1) in our analysis; thelower bound (2) can be obtained easily merely by replacing g by −g, and will be discussed at the end of thissection.
Suppose τ = 1, and let U be a (Borel) measurable set. Our goal is to find the optimal solution ofmin∆ maxR∈U g(S0 (1 + R)) − R∆. The following result provides an optimality characterization for any
payoff function g and any uncertainty set U:
Proposition 3.2. Let τ = 1 and S0 be the initial price. Consider a bounded uncertainty set U and acontinuous payoff function g. We havemin max g(S0 (1 + R)) − R∆ =
∆

R∈U

max

Pf ∈P(U ),ER←Pf [R]=0

EPf [g(S0 (1 + R))],(8)

where P(U) denotes the set of all probability measures Pf that have support on U. The maximization
problem in the right hand side above is over all such probability measures that satisfy EPf [R] = 0.
The optimal value of (8) is finite only when U contains at least a point larger than 0 and a point smaller
than 0, e.g., when U is an interval that covers 0; otherwise risk-neutral measure cannot be constructed.
8

Proof. To illustrate the key idea in our analysis, let us start with analyzing a “discrete” version of the
problem, i.e., let U = {r1 , r2 , ..., rn } be a discrete set on R. We can write min∆ maxR∈U g(S0 (1+R))−R∆
as the following linear program (LP):
min p
min p
≡
s.t. g(S0 (1 + ri )) − ri ∆ ≤ p for i ∈ [n]s.t. p + ri ∆ ≥ g(S0 (1 + ri )) for i ∈ [n],(9)where the decision variables are p and ∆. The formulations in (9) follow simply by the definition ofminimax problem, with the optimal p representing the option price’s upper bound. Now we invoke thestandard primal-dual theorem for LP on (9) and obtain the following equivalent LP in dual form:Pmaximizew g(S0 (1 + ri ))Pi∈[n] i
subject tow =1Pi∈[n] ii∈[n] wi ri = 0
wi ≥ 0 for i ∈ [n](10)Here wi ’s are the decision variables.
P Observe that {wi }i∈[n] can be interpreted as a probability distribution
on the uncertainty set U since
wi = 1. CallPthis distribution Pf . This is a risk-neutral probability
distribution since the expected return EPf [R] =wiPri = 0. Moreover, note that the objective function
under this probability interpretation can be rewritten as i∈[n] wi g(S(1 + ri )) = ER←Pf [g(S(1 + R))]. We
thus have proved (8).
It is straightforward to generalize this argument to general uncertainty set, with slightly more function
space technicalities. For general uncertainty set U, we can generalize (9) as:
minimize p
subject to p + r∆ ≥ g(S0 (1 + r)) for r ∈ U(11)Next, note that the dual cone of C + (U), the set of non-negative continuous functions on U, is P + (U), theset of positive measures on U. Since g is assumed to be continuous, the Lagrangian of (11) isZ
L(p, ∆, w) = p + (g(S0 (1 + r)) − r∆ − p)dw(r)Uwhere w(·) ∈ P + (U) (see [Lue97]). The dual function is defined asZ`(w) = inf p + (g(S0 (1 + r)) − r∆ − p)dw(r)
p,∆
U
Z

Z
= inf
g(S0 (1 + r))dw(r) + (1 − w(U))p +rdw(r)∆
p,∆

U

(12)

U

R
Suppose w(·) does not satisfy either w(U) = 1 or U rdw(r) = 0, then one can always find p or ∆ thatgives arbitrarily large objective value in (12). Hence the dual problem maxw∈P + (U ) `(w) can be written as
Rmaximize RU g(S0 (1 + r))dw(r)subject to U rdw(r) = 0(13)w(U) = 1
w ∈ P + (U)Finally, it is easy to see that the constraint set in (11) has non-empty interior (by picking large enoughp for example). Hence strong duality holds and the dual optimal value in (13) equals the primal counterpart(see e.g., Chapter 8 in [Lue97]). By identifying w as a probability measure on U, we conclude that (13) isthe same as (8). This completes our proof.
9

3.3

Convex payoff function

When the payoff function g(·) is convex and the uncertainty set is an interval, i.e., U = [−ζ, ζ] withζ, ζ > 0, we are able to find an analytic form for (8). Specifically, we will show that it is sufficient toconsider risk-neutral probability distributions that have point masses concentrated only on the extremes,
namely −ζ and ζ, i.e.,
Corollary 3.3. When the payoff function g(·) is convex and U = [−ζ, ζ], we havemin max g(S0 (1 + R)) − R∆ =
∆

R∈U

max
Pf ∈P({−ζ,ζ}),ER←Pf [R]=0

EPf [g(S0 (1 + R))]

(14)

where P({−ζ, ζ}) is the set of probability distributions that have support only on −ζ and ζ. Furthermore,since Pf ∈ P({−ζ, ζ}) and EPf [R] = 0 uniquely defines Pf , the max operator is redundant. Hence (14)can be rewritten as
EPf [g(S0 (1 + R)],

where Pf ∈ P({−ζ, ζ}) and EPf [R] = 0.

(15)

An immediate implication of Corollary 3.3 is that the upper bound of the option price collides with thebinomial model for a single-round game.
Proof. We can prove (14) by analyzing either the primal program (11) in the proof of Proposition 3.2 or thecharacterization (8) directly. Let us consider the former as this is more elementary. We argue that, in thecase of convex g and U = [−ζ, ζ], the program (11) is equivalent tominimize p
subject to p − ζ∆ ≥ g(S(1 − ζ))
p + ζ∆ ≥ g(S(1 + ζ))(16)

In other words, all other constraints p + r∆ ≥ g(S(1 + r)) for r ∈ (−ζ, ζ) are redundant. To prove this,consider any −ζ < r < ζ. One can write r = q(−ζ) + qζ where q + q = 1, q, q > 0. Suppose theinequalities p − ζ∆ ≥ g(S(1 − ζ)) and p + ζ∆ ≥ g(S(1 + ζ)) hold. Thenp + r∆ = q(p − ζ∆) + q(p + ζ∆)≥ qg(S(1 − ζ)) + qg(S(1 + ζ))≥ g(S(1 + r)) (by the convexity of g)
Therefore, all other constraints are redundant. Now by the same argument as the proof of Proposition 3.2 (fordiscrete uncertainty set), we immediately get (14). The other statement in the corollary follows trivially.

3.4

Analysis for the multi-round model

For our multi-round game, the trader has the discretion to choose τ rounds of hedging amount {∆t }t∈[τ ]against the nature who controls the τ rounds of returns {Rt }t∈[τ ] . We assume a uniform uncertainty set

10U = [−ζ, ζ] across time. The upper bound of the option price is then
!
τ
τ
Y
X
(Rt ∆t )min
max g S0 (1 + Rt ) −∆t ,t∈[τ ] Rt ∈U ,t∈[τ ]

t=1

t=1

= min max {· · · min max {· · · min max {g (Sτ −1 (1 + Rτ )) − Rτ ∆τ }∆1 R1 ∈U∆τ −1 Rτ −1 ∈U∆τ Rτ ∈U−Rτ −1 ∆τ −1 } · · · − R1 ∆1 }(17)

The following lemma is a consequence of the result for the single-round game in Proposition 3.2.
Lemma 3.4. Consider the τ -round hedging game with the same uncertainty set UQ= [−ζ, ζ] across timeand convex payoff function g(·). The upper bound of the option price is EPf [g(S0 τt=1 (1 + Rt ))], where
Pf is the unique risk-neutral probability distribution on {−ζ, ζ} for all {Rt }t∈[τ ] , i.e., Pf ∈ ({−ζ, ζ}) andEPf [Rt ] = 0 for all t ∈ [τ ]. In other words, it coincides with the price computed from a binomial tree modelwith u = ζ and d = ζ.
The proof is a direct application of dynamic programming, coupled with the preservation of convexity
across iterations of the value functions. First, observe the following:
Lemma 3.5. Let h(·) be an arbitrary convex function. Then EP [h(S(1 + R))] is convex in S, where P isan arbitrary distribution for R.
Proof. The statement is immediate by using linearity of expectations and the assumption that h(·) is convex.
Proof of Lemma 3.4. We can write (17) as a dynamic program, given by gτ (x) = g(x) and
gt−1 (x) = min max gt (x(1 + Rt )) − Rt ∆t∆t Rt ∈U

for t = τ, τ − 1, . . . , 1. The price upper bound is then given by g0 (S0 ). We prove by induction that gt (·) are
all convex and gt−1 (x) = EPf [gt (x(1 + Rt ))]. The statement is obvious for gτ (·). Now, supposing gt (·) isconvex, we have from Corollary 3.3 that gt−1 (x) = EPf [gt (x(1 + Rt ))], and from Lemma 3.5 that gt−1 (·)
is convex. Hence the induction holds.
Explicit hedging strategy. When the uncertainty sets are uniform intervals and the payoff function isconvex, the optimal hedging strategy is straightforward (and is identical to the binomial model): ∆t =g(St−1 (1+ζ))−g(St−1 (1−ζ))ζ+ζ

dollar on S for each round t.

Non-uniform uncertainty sets. When the uncertainty sets are non-uniform, say Ut , [−ζ t , ζ t ], Corollary 3.3, Lemma 3.5 and the form of the hedging strategy all still hold with the natural modification. Thismeans at each round we need only consider the two points {−ζ t , ζ t }. However, from a computational pointof view, the number of states we need to keep track of in the backward induction could grow exponentiallyin τ (See Figure 4 for an illustration). Thus, a naive application of dynamic programming algorithm will
not be efficient. In Appendix A we show that exact computation of the option’s upper bound with nonuniform uncertainty sets is #P -hard, and in Section 4 we shall design an approximation algorithm to solve
the problem.
Algorithmic equivalence to [AFW12]. We remark that this backward induction approach is also applicable to the model in [AFW12], in which second moment constraints are imposed on Rt . In particular,
11

%
+10

B
$11.0

−6%

D
$11.66+6%E$10.34

+6%

F
$9.54

−6%

G
$8.46

A
$10.0

−10
%

C
$9.0

Figure 4: An example of an option hedging game with non-uniform uncertainty sets. U1 = [−10%, 10%]and U2 = [−6%, 6%]. The number of states for the dynamic program can grow exponentially in τ .
our stepwise dual characterization can be derived in a similar manner under their moment constraint, byapplying (with a small modification) the primal-dual theorem to find the optimal solution for one-roundgame, followed by using Lemma 3.5 to show the preservation of convexity over rounds (so that the primaldual theorem can be applied recursively). Thus, the results here and techniques developed in Section 4also give efficient pricing algorithm and an explicit hedging strategy for the model and problems considered in [AFW12]. But we also remark that the convergence result developed below does not directly imply
convergence in [AFW12]’s model.
Convergence. Since the price from the binomial tree model converges to Black-Scholes [CRR79], an√√
immediate consequence is the convergence of our upper bound, with uncertainty sets Utτ = [−ζ/ τ , ζ/ τ ],also to the Black-Scholes price. Here we state a convergence result that is more general: as long as the(possibly non-uniform) collection of uncertainty sets follow a “bounded quadratic variation” condition, we
obtain convergence to the Black-Scholes price for European-type options:
Corollary 3.6. Consider the τ -round hedging game with Lipschitz continuous convex payoff
Pfunctionτ g(·).
τ
Let {{Utτ }t≤τ }τ ≥1 be the sequence of uncertainty sets and let Utτ = [−ζ τt , ζ t ]. If limτ →∞ τt=1 ζ τt ζ t = ντfor a positive number ν, and supt∈[τ ] max{ζ τt , ζ t } → 0, the upper bound of the European option price con√verges to E[g(S0 exp{ νN (0, 1) − ν/2})], where N (0, 1) is standard Gaussian variable, i.e., it converges
to the option price for a geometric Brownian motion with zero drift.
PτWe remark that if ν = σ 2 T for a positive constant σ 2 , then the condition limτ →∞ τt=1 ζ τt ζ t = νimitates the quadratic variation of a Brownian motion, and the result recovers the Black-Scholes price. Theτ
uniform convergence condition supt∈[τ ] max{ζ τt , ζ t } → 0 is necessary; there is no guarantee of Gaussian
convergence in the limit if one uncertainty set keeps constant size as τ → ∞.
Q
Proof. From Lemma 3.4, the upper bound of the option price, for any τ , is EPf [g(S0 τt=1 (1 + Rtτ ))]where Rtτ is the t-th round return in a τ -round game, and Pf (which also depends on τ ) is the uniqueτ
probability measure that satisfies EPf [Rtτ ] = 0 and has support {−ζ τt , ζ t } on Rtτ for any t ∈ [τ ]. Simpleττττ
calculation reveals that Pf puts weights ζ t /(ζ τt + ζ t ) on −ζ τt and ζ τt /(ζ τt + ζ t ) on ζ t . This implies that
EPf [(Rtτ )2 ] = ζζ.
We shall prove thatlog(S0τY
t=1(1 + Rtτ )) = log S0 +

τ
X
t=1

12

Rtτ −

τ
X
(Rτ )2
t

t=1

2

+

τ
X
ξ(Rτ )
t

t=1

3

(18)

where ξ(Rt ) satisfies |ξ(Rtτ )| ≤ C|Rtτ |3 for a constant C,
in distribution
to log S0 +N1)−ν/2.
P(0,Pτconverges
Pτ
τ
τ
τ
2
τ
Now consider each term in (18), and we start with t=1 Rt . Since t=1 EPf [(Rt ) ] = t=1 ζ τt ζ t →Pτ
as τ → ∞, for any  > 0, by Lindeberg-Feller
ν, and t=1 EPf [(Rtτ )2 ; |Rtτ | > ] is eventuallyPτ zero√τ
Theorem (p. 114, (4.5) in [Dur10]), we have t=1 Rt → νN (0, 1) in distribution.
PPτ(Rτ )2
Next consider the term τt=1 2t . By our condition supt∈[τ ] max{ζ τt , ζ t } → 0, since τt=1 Pr(|Rtτ | >PP) is eventually zero as τ → ∞, for any  > 0, and also τt=1 EPf (Rtτ )4 ≤ τt=1 EPf (Rtτ )2 ·supt∈[τ ] (Rtτ )2 →PτP0, the Weak Law for Triangular Arrays hold (p. 40, (5.5) in [Dur10]), and t=1 (Rtτ )2 → τt=1 EPf [(Rtτ )2 ] =ν in probability.
PP
For the last term, we have | τt=1 ξ(Rtτ )| ≤ C τt=1 (Rtτ )2 supt∈[τ ] |Rtτ | → 0 in probability.QCombining all these terms, by Slutsky’s Theorem (see e.g., p. 19 in [Ser80]), we conclude that log(S0 τt=1 (1 +√Rtτ )) → νN (0, 1) − ν/2 in distribution.
Lastly, we will conclude our result by checking a uniform integrability condition (see e.g., p.
Qτ 14
in [Ser80]). First, since g is√continuous, the Continuous Mapping Theorem [Bil09] stipulates that g(S0
t=1 (1+Q
Rtτ )) converges to g(exp{ νN (0, 1) − ν/2}) in distribution. We shall show that supτ EPf [g(S0 τt=1 (1 +Q
integrable, which will then conclude
Rtτ ))2 ] < ∞. This will imply Q
that g(S0 τt=1 (1 + Rtτ )) is uniformly√
the convergence in L1 of g(S0 τt=1 (1 + Rtτ )) into g(S0 exp{ νN (0, 1) − ν/2}) and conclude our result.
To this end, note that"EPf g(S0τY#(1 + Rtτ ))2

t=1≤ C1 EPf S0

τY2(1 + Rtτ )

+ C2

t=1

(for some constants C1 , C2 > 0, since g is assumed to be Lipschitz continuous)τY= C1 S0
EPf (1 + Rtτ )2 + C2 (by independence of Rtτ )= C1 S0

t=1
τ
Y

τ

(ζ τt ζ t + 1) + C2

t=1
τ
X
τ
≤ C1 S0 exp{ζ τt ζ t } + C2
t=1

<

C3

for some constant C3 > 0, by our assumption thatτ τ
t=1 ζ t ζ t → ν.

PτConcave payoffs. We have a simple characterization of the hedging game’s equilibrium when the payoff
function is concave, under general conditions on Ut :Corollary 3.7. Consider a τ -round game. When the payoff function g(·) is concave, with uncertainty sets{Ut }t∈[τ ] each of which contains the point 0, the option price’s upper bound is
!
τ
τ
Y
X
min
max g S0 (1 + Rt ) −(Rt ∆t ) = g(S0 )(19)∆t ,t∈[τ ] Rt ∈Ut ,t∈[τ ]

t=1

t=1

Proof. Consider a single-round game i.e., τ = 1. Recall Proposition 3.2, which states that the upper boundis maxPf ∈P(U ):EP [R]=0 EPf [g(S0 (1 + R))]. By Jensen’s inequality, EPf [g(S0 (1 + R))] ≤ g(S0 (1 +f
EPf [R])) = g(S0 ) for any Pf ∈ P(U) such that EPf [R] = 0. The result is then immediate for τ = 1.
13

The conclusion from multi-round game follows exactly the same as the argument for Lemma 3.4 (nowconcavity is preserved in every step in the backward induction).
Lower bounds. By replacing g with −g in all analysis above, we immediately get results for lower bounds.
The following is analogous to Proposition 3.2:
Proposition 3.8. Let τ = 1 and S0 be the initial price. Consider a bounded uncertainty set U and acontinuous payoff function g. The lower bound of the option price ismax min g(S0 (1 + R)) − R∆ =
∆

R∈U

min

Pf ∈P(U ),ER←Pf [R]=0

EPf [g(S0 (1 + R))],(20)

where P(U) denotes the set of all probability measures Pf that have support on U. The maximization
problem in the right hand side above is over all such probability measures that satisfy EPf [R] = 0.
The following summarizes the characterizations for convex and concave payoffs:
Corollary 3.9. Consider the τ -round European option hedging game, with uncertainty sets {Ut }t∈[τ ] . The
following results hold:
1. Suppose the payoff function gQis concave. If the uncertainty sets Ut = [−ζ t , ζ t ] for all t ∈ [τ ], thenthe lower bound is EPf [g(S0 τt=1 (1 + Rt ))], where Pf is the unique risk-neutral measure supportedon {−ζ t , ζ t } for each Rt , i.e. EPf [Rt ] = 0.
2. Suppose the payoff function g is convex, and the uncertainty sets Ut all contain the point 0. Then thelower bound is g(S0 ).

4

Algorithms for non-convex payoffs

This section presents an approximation algorithm for computing the price upper bounds for general
payoff functions under the oracle model; the lower bound’s algorithm and its analysis is similar and so
is omitted here. Throughout this section, we will assume the size of the uncertainty set U = [−ζ, ζ] is
uniform across time steps and ζ, ζ > 0 are polynomials in τ ; at the end of this section we will discuss thenon-uniform uncertainty set case. We also assume that the payoff function g is Lipschitz continuous andmonotonically non-decreasing, and without loss of generality that g(0) = 0.
Our main result is an approximation algorithm that has δS0 additive error with running time being
polynomial in 1δ and τ (we also say such algorithm is δ-additive approximation).
Our algorithm. We use a fairly natural algorithm to approximate the upper bound: we discretize theuncertainty set U, i.e., instead of allowing the adversary to choose an arbitrary value from U, we only allow
it to choose from the discrete set Û , {−ζ, −ζ + , −ζ + 2, ...., ζ}, where  is a parameter of our algorithm.
In other words, we consider a multinomial tree approximation of the problem.
We shall briefly address two important properties of our algorithm regarding the discretization. First,
since at each step the adversary may choose multiple ways to move the price, it could be worrying that the
number of possible states under consideration is exponential in τ . However, so long as  remains uniform
over the rounds, the number of states we need to keep track of at the t-th round is t(ζ + ζ)/ (and thus linearin t). This is also an elegant property of multinomial tree (as well as binomial tree) that makes these models
useful in practice. However, note that at the final round, the price Sτ could be any value in an interval of
exponential length (i.e., in the range [(1 − ζ)τ S, (1 + ζ)τ S]), while our multinomial tree algorithm only
“samples” polynomial number of points from the function g(x). This implies that on average the distance14

between any two sampled points is exponential. This is a surprising feature of our algorithm: while a large
portion of internal states in the multinomial tree have additive errors being  δS0 , the error shrinks overtime to give an accurate final output. This feature is a consequence of the probabilistic interpretation in ourdual formulation, which we will further elaborate when we discuss the challenges of our analysis shortly.
Second, our discretization scheme and backward induction is related to the so-called stochastic meshmethod in the area of financial engineering [BG04]. First, to compute the price upper bound for the multinomial tree, one can use a dynamic program based on the recursive formula discussed in Section 3. Specifically,
let ĝt (x) be the approximate price upper bound of the option at the t-th round. Also, let b = (ζ + ζ)/ be
the total number of choices an adversary has for each move, and the choices of the return are ri = −ζ + ifor i ∈ [b]. We compute ĝt (x) by finding the optimal solution of the LP:
minimize p
subject to ĝt+1 (x(1 + ri )) − ri ∆ ≤ p for i ∈ [b](21)This idea resembles the stochastic mesh method in pricing options, most notably American-type, when
the underlying asset’s price movement is assumed to be stochastic. Assuming a well-defined risk-neutral
measure, the stochastic mesh method calculates each gt (x) through backward induction via Monte Carlosimulation on the return Rt . However, since the state space of Rt is typically assumed to be unboundedin stochastic models, the stochastic mesh algorithm does not use -spacings to construct a tree but rather
generates the nodes randomly from some convenient distributions. The number of nodes at each level (i.e.,time point) is kept constant to avoid exponential computational burden, and each node at each level is“connected” to all the nodes at the neighboring two levels. The backward induction step then utilizes all thenodes in the successive level, and relies on importance sampling to calculate unbiased probability weights
at each step. Hence, in a sense, our algorithm replaces this importance sampling with an LP in obtaining theweights. As such, our analysis also differs and, in fact, it avoids some hard-to-verify moment conditions on
the transition probability thanks to our assumption of bounded uncertainty sets.
Our key contribution in this section is to analyze the difference between ĝt (x) and gt (x). We face thefollowing two challenges.
Local error due to discretization. The first challenge is to understand how much error we make per step.
For instance, let us assume that we are able to accurately compute gt+1 (x) for the (t + 1)-st round. If we use(21) to find an approximation function ĝt (x), we need to quantify the difference between gt (x) and ĝt (x).
The propagation of errors. In our backward induction, the value of g0 (S0 ) depends on the values of
g1 (x1 ) for x1 ∈ [(1 − ζ)S0 , (1 + ζ)S0 ] and the value of g1 (x1 ) for any x1 depends on the values ofg2 (x2 ) for x2 ∈ [(1 − ζ)x1 , (1 + ζ)x1 ]. Thus, if we look two steps forward, g0 (S0 ) depends on g2 (x) forx ∈ [(1−ζ)2 S0 , (1+ζ)2 S0 ]. In general, for any t, g0 (S0 ) depends on gt (x) for x ∈ [(1−ζ)t S0 , (1+ζ)t S0 ],which is an exponentially growing interval. This could cause the error to propagate at an exponential rate:
if our solution g0 (S0 ) (indirectly) depends on gt ((1 + ζ)t S0 ), then even an -additive approximation ofgt ((1 + ζ)t S0 ), i.e., ĝt ((1 + ζ)t S0 ) ≈ gt ((1 + ζ)t S0 ) ± (1 + ζ)t S0 can potentially lead to the same errorof (1 + ζ)t S0 for computing g0 (S0 ) i.e., an (1 + ζ)t -additive error, which is prohibitively huge as τ
becomes large. Thus, the challenge here is to accurately analyze and control the error when the algorithm
uses information from a lot of highly noisy internal states. Moreover, as discussed before, the fact that apolynomial number of points are sampled in the multinomial tree algorithm from an exponential length ofuncertainty set as time progresses can also result in huge error. The combination of the magnitude of errors
from the sources and their propagation needs to be addressed.
Our techniques. Our analysis consists of four major components to address the above two issues. First,
we need to show that Lipschitz continuity of gt (x) is preserved in each backward induction step over time;15

this property will be used later on. Second, we need to show that when gt+1 (x) is Lipschitz and when we
discretize the uncertainty set, the approximate solution we get at each step is sufficiently accurate. This canbe done by analyzing the geometric structure of both the primal and the dual LP (for the non-discretizedversion). This will give us a convenient form of the solutions in terms of their binding constraints, whichhelps quantify the difference between approximate solutions and the exact solutions locally.
Next, we need to control the error propagation rate. As discussed above, if we only focus on the“dependency graph” of the dynamic program, there will be no way for us to control the error propagation
rate. The crux to our analysis is to view the solutions in the dual spaces and express our recursive solutions
probabilistically. These probability measures, attached “artificially” to our deterministic algorithm, would
bestow martingale property on {Rt }t≤τ that helps to address g0 (S0 )’s pathological dependency on gτ ((1 +ζ)τ S0 ): while g0 (S0 ) could potentially depend on gτ ((1 + ζ)τ S0 ), it is unlikely that the random walk{Rt }t≤τ will hit the price (1 + ζ)τ S0 , and hence g0 (S0 )’s dependence on gτ ((1 + ζ)τ S0 ) will also be
weak probabilistically. Our deterministic error can be expressed in terms of the expectation of the priceprocess under one of these probability measures. We will see that our choice of the most suitable probability
measure for analysis is, interestingly, neither the maximal risk-neutral measure for the original problem nor
the discretized problem, but in some sense a problem in between.
Finally, we need to “glue” our local analysis and the control of error propagation together. We use astandard telescoping technique to do so.
Now we explain all our building blocks in detail.

4.1

Preservation of Lipschitz continuity for the value functions
We start with the first building block. We have the following lemma.

Lemma 4.1. Suppose the payoff function g(·) is Lipschitz continuous and monotonically non-decreasing,i.e. g(x) − g(y) ≤ L(x − y) for x ≥ y. Then the value function gt (·) at the t-th round is also Lipschitz
continuous with the same Lipschitz constant for all t.
Proof. We prove by (backward) induction. Obviously gτ (x) = g(x) satisfies the Lipschitz condition. Suppose gt+1 (x) satisfies gt+1 (x) − gt+1 (y) ≤ L(x − y) for x ≥ y. We prove gt (x) − gt (y) ≤ L(x − y) forx ≥ y by contradiction.
Assuming this is not true, thenmax

P ∈P(U ):E[R]=0E[gt+1 ((x + δ)(1 + R))] >max

P ∈P(U ):E[R]=0E[gt+1 (x(1 + R))] + Lδfor some x ∈ U and δ > 0. Now let P̃f be an optimal solution for E[gt+1 ((x + δ)(1 + R))] (the existenceof an optimal solution will be seen immediately in the next lemma). Then
EP̃f [gt+1 ((x + δ)(1 + R))] =>max

E[gt+1 ((x + δ)(1 + R))]max

E[gt+1 (x(1 + R))] + Lδ

Pf ∈P(U ):E[R]=0
Pf ∈P(U ):E[R]=0≥ EP̃f [gt+1 (x(1 + R))] + Lδ.
But since gt+1 (x) is assumed to be Lipschitz continuous, we haveEP̃f [gt+1 ((x + δ)(1 + R))] − EP̃f [gt+1 (x(1 + R))] ≤ EP̃f [Lδ(1 + R)] = Lδby the risk-neutral property of P̃f . This leads to a contradiction.
16

4.2

Analysis of local errors through binding constraints
Next we analyze the local error of each induction step. We shall first show that the primal formulation
minimize p
subject to p + r∆ ≥ gt+1 (x(1 + r)) for all r ∈ U(22)

has the following property in terms of “binding constraints”:
Lemma 4.2. For any t and x, there exists an optimal solution for (22), say (p∗ , ∆∗ ), such that either:
1. p∗ = gt+1 (x) or
2. There are exactly two binding constraints, corresponding to r(1) and r(2) , such that r(1) > 0 andr(2) < 0. These two constraints uniquely define (p∗ , ∆∗ ).
Proof. First, there must be at least one binding constraint for (22), because if not, one can always decrease
p to achieve lower objective value while preserving all constraints. On the other hand, there must be at most
two binding constraints for (22); otherwise, there will be three linearly independent equations p∗ + ri ∆∗ =gt+1 (x(1 + ri )) for some ri , i = 1, 2, 3 that (p∗ , ∆∗ ) satisfies, which is impossible.
Next, let us move to the case where there are two binding constraints. We need to show that r(1) < 0 <r(2) . Suppose r(1) , r(2) > 0. We can see that the dual program of (22) is infeasible, which means the primal
LP is either infeasible or unbounded. Infeasibility is easily ruled out since one can put ∆ = 0 and a large
enough p to construct a feasible solution. To show that unboundedness is also impossible, we will showthat all p that are smaller than a negative threshold are infeasible, implying the minimization problem (22)is finite. To this end, consider any r̃1 > 0 and −r̃2 < 0 that lie in U. Suppose p + r̃1 ∆ ≥ gt+1 (x(1 + r̃1 )).
This implies ∆ ≥ (gt+1 (x(1 + r̃1 )) − p)/r̃1 . Now, if we choose p to be very negative, then
gt+1 (x(1 + r̃1 )) − pr̃1r̃2
p − r̃2 ∆ ≤ p − r̃2= 1+
p − gt+1 (x(1 + r̃1 )) < gt+1 (x(1 − r̃2 ))
r̃1
r̃2
r̃1
and hence (p, ∆) does not satisfy p − r̃2 ∆ ≥ gt+1 (x(1 − r̃2 )). Hence the set of feasible p must be boundedfrom below. Similarly, we can show that it is impossible to have r(1) , r(2) < 0. It is trivial to see that thetwo binding constraints uniquely define (p∗ , ∆∗ ).
Finally, suppose there is exactly one binding constraint. When r in the corresponding binding constraint
is non-zero, the dual LP is again infeasible, which will result in a contradiction again as above.
Now we are ready to present the major building block in our local analysis. To encapsulate the effectof local errors due to discretization, we need to introduce an intermediate quantity gtm (x), for each t ∈ [τ ],defined as the optimal solution of the following linear program:
minimize p
subject to gt+1 (x(1 + ri )) − ri ∆ ≤ p for i ∈ [b](23)

The difference between gtm (x) and ĝt (x) is that the calculation of gtm (x) assumes accurate access tothe function gt+1 (·). Thus, we may view gtm (·) as a “hybrid variable” that sits in between gt (·) and ĝt (·).
The following gives a bound for gt (·) − gtm (·):
Lemma 4.3. With gtm (x) defined in (23), we have0 ≤ gt (x) − gtm (x) ≤p
2Lgt (x)x + Lx

where  is the discretization parameter in the algorithm.
17

(24)

The main device we use in the proof is a convenient dual characterization of the optimal solution
obtained through the binding constraints in Lemma 4.2. From this characterization, Lipschitz continuity isthen used to bound the magnitude of the local errors.
Proof. Recall that we use the following LP to compute gt (x):minimize p
subject to gt+1 (x(1 + r)) − r∆ ≤ p for r ∈ U(25)

Let (p∗ , ∆∗ ) be the optimal solution. By Lemma 4.2, we have either 1) p∗ = gt+1 (x) or 2) there exists
a pair r(1) and r(2) such that r(1) < 0 < r(2) andp∗ + r(i) ∆∗ = gt+1 (x(1 + r(i) ) for i = 1, 2.
Let us focus on the second case, as the first case follows similarly. In this case, we can express p∗ = gt (x)in terms of r(1) and r(2) as follows:
gt (x) =

r(2)
r(1)
(1)
g
(x(1
+
r
))
−
gt+1 (x(1 + r(2) ))t+1
r(2) − r(1)r(2) − r(1)(26)

Since the discretization length is , there exist r̂(1) < 0 < r̂(2) ∈ Û such that 0 ≤ r(1) − r̂(1) <  and0 ≤ r̂(2) − r(2) < , i.e., we can define r̂(1) as the closest ri that is at least as large as r(1) and r̂(2) as theclosest ri that is at least as small as r(2) . Note that a lower bound of gtm (x) is given by the optimal solutionof the following linear program:
minimize p
subject to gt+1 (x(1 + r̂(1) )) − xr̂(1) ∆ ≤ p
gt+1 (x(1 + r̂(2) )) − xr̂(2) ∆ ≤ p(27)

This LP can be solved analytically, which gives us
gtm (x) ≥

r̂(2)
r̂(1)
(1)
g
(x(1
+
r̂
))
−
gt+1 (x(1 + r̂(2) )).
t+1
r̂(2) − r̂(1)r̂(2) − r̂(1)Now let η >  be a parameter to be decided later. We consider two cases.
Case 1. r(2) − r(1) ≥ η. First we can see that (detailed calculation appears in Appendix C)


r̂(2)
r(2)

1−
≥ (2)
.
η
r̂(2) − r̂(1)r − r(1)

(28)

(29)

Similarly, we have
r̂(1)
r(1)
≥
−
− (2)
r̂ − r̂(1)r(2) − r(1)

18




1−
.
η

(30)

Hence we may continue (28) and get:gtm (x) ≥r̂(2)gt+1 (x(1 + r̂r̂(2) − r̂(1)r(2)(2)
r − r(1)

(1)

)) −

r̂(1)

gt+1 (x(1 + r̂r̂(2) − r̂(1)

(2)

))





 
gt+1 (x(1 + r(1) )) − xL(r(1) − r̂(1) )
η


(1)

r
1−
− (2)
gt+1 (x(1 + r(2) ))ηr − r(1)(by Lipschitz continuity of gt+1 , and Eq. (29) and (30))





r(2)

r(1)

(1)
(2)
g
(x(1
+
r
g
(x(1
+
r
=
1−
))
−
))
−
xL
1
−
t+1
t+1
η
η
r(2) − r(1)r(2) − r(1)= gt (x)(1 − ) − xL (by Eq. (26)).
η≥

1−Case 2. When r(2) − r(1) < η. This implies r(2) < η and r(1) > −η. We shall first show that |gt+1 (x) −gt (x)| is small. Specifically,|gt+1 (x) − gt (x)|


r(1)
r(2)
(1)
(2)
g
(x(1
+
r
))
−
g
(x(1
+
r
))
= gt+1 (x) −t+1
t+1
r(2) − r(1)r(2) − r(1)
≤
≤

r(2)
r(2) − r(1)gt+1 (x) − gt+1 (x(1 + r(1) )) −|r(1) · r(2) |2Lx (2)r − r(1)r(1)r(2) − r(1)gt+1 (x) − gt+1 (x(1 + r(2) ))(by Lipschitz continuity of gt+1 (·))
(2)

≤ 2Lx|r(1) | (since r(2)r−r(1) ≤ 1)
≤ 2Lxη

We next use the above inequality to compute a lower bound for gtm (x):gtm (x)
≥
≥

r̂(2)
r̂(1)
(1)
g
(x(1
+
r̂
))
−
gt+1 (x(1 + r̂(2) )) (by Eq.(28))t+1r̂(2) − r̂(1)r̂(2) − r̂(1)2Lx|r̂(1) r̂(2) |r̂(2) − r̂(1)g(x)−(Lipschitz condition)
t+1
r̂(2) − r̂(1)r̂(2) − r̂(1)(2)≥

gt+1 (x) − 2Lx|r̂(1) | (again use the fact that r̂(2)r̂−r̂(1) ≤ 1)≥

gt (x) − (2η + 2)Lx. (since |r̂(1) | ≤ |r̂(1) − r(1) | + |r(1) | ≤  + η)Summarizing both cases, we have≤ min max gt (x) + xL, (2η + 2)Lx
η>
η



≤ min max gt (x) , 2Lxη + 2Lx
η>
η
p
≤
gt (x)2Lx + 2Lxppp
by setting η = gt (x)/(2Lx) when  ≤ gt (x)/(2Lx), and η =  when  > gt (x)/(2Lx).
gt (x) − gtm (x)



19

4.3

Error propagation control and telescoping
We now move to the final stage of our analysis. The following is our main result.

Theorem 4.4. The approximation g0 (S0 ) − ĝ0 (S0 ) satisfies√
0 ≤ g0 (S0 ) − ĝ0 (S0 ) ≤ C1 Lτ S0 .

(31)

for some constant C1 .
The proof of this theorem relies heavily on the “artificial” risk-neutral probability measures that define
the optimal dual solutions of the several different value functions, gt (x), gtm (x) and ĝt (x), for each step ofbackward induction. Although these probability measures have no real-world correspondence, as discussed
in Section 3, they confer “artificial” martingale properties on the underlying asset’s price movement. Moreover, we are in fact granted with some freedom in choosing the measure to work under, and we will see thatthe one associated with gtm (x) is the most effective in truncating the propagation of error. We will now lay
out the arguments precisely.
Proof. We first apply a standard telescoping trick (see, e.g., [BG04]) to “decouple” the local error from theglobal error, i.e., let dt (x) = gt (x) − ĝt (x) and we havedt (x) = (gt (x) − gtm (x)) + (gtm (x) − ĝt (x)).
The first term represents the local error at each induction step, whereas the second term comes from error
propagation from the future. The first term gt (x) − gtm (x) is handled by Lemma 4.3. For the second termgtm (x) − ĝt (x), we recall the dual characterization in Proposition 3.2 to write
gtm (x) − ĝt (x) =max

E [gt+1 (x(1 + Rt+1 ))] −P ∈P(Û )EP [Rt+1 ]=0max

E [ĝt+1 (x(1 + Rt+1 ))]P ∈P(Û )EP [Rt+1 ]=0

Notice that Rt+1 in both expectations above share the same support Û, the discretized uncertainty set. Let usmwrite Emx,t as the expectation under Px,t := arg max{E [gt+1 (x(1 + Rt+1 ))] | P ∈ P(Û), EP [Rt+1 ] = 0}.
The above equation becomesEm
x,t [gt+1 (x(1 + Rt+1 ))] −max[ĝt+1 (x(1 + Rt+1 ))]P ∈P(Û )EP [Rt+1 ]=0≤ Em
x,t [gt+1 (x(1 + Rt+1 )) − ĝt+1 (x(1 + Rt+1 ))]m(since Px,tis feasible for the maximization in the second term above)= Em
x,t [dt+1 (x(1 + Rt+1 ))]m:
Hence, dt (x) can be bounded recursively under the probability measure Px,tdt (x) ≤p
2Lgt (x)x + Lx + Em
x,t+1 [dt+1 (x(1 + Rt+1 ))].

(32)

Q
Now, let us define a probability measure PSm0 on the process {St }t∈[τ ] , where St = S0 ti=1 (1 + Ri )is the price of the underlying asset at the t-th round. This measure PSm0 is defined by the stepwise transition20

m on each R , t ∈ [τ ]. From (32), we can expand d (S ) recursively:
probability Px,tt
0 0p2Lgt (S0 )S0  + LS0  + Em
S0 ,1 [d1 (S1 )]ppmm≤ 2Lgt (S0 )S0  + LS0  + Em
S0 ,1 [ 2Lg1 (S1 )S1  + LS1 ] + ES0 ,1 ES1 ,2 [d2 (S2 )]d0 (S0 ) ≤(by expanding d1 (S1 ) by (32) again)
..
.
≤ Em
S0

" τ
X np

#
o
2Lgt (St )St  + LSt  .

(33)

t=1

Next, observe that {St }t≤τ is a martingale under PSm0 and the filtration Ft = σ(R1 , . . . , Rt ), sincem
Em
S0 [Rt+1 |Ft ] = Et,St [Rt+1 ] = 0. We leverage this fact to bound both terms in (33). First, notice that
τ
τ
X
X
Em
[
LS
]
=
L
Em
t
S0
S0 [St ] = Lτ S0
t=1

t=1

For the other term in Eq. (33), note that by Lemma 4.1 we have gt (x) ≤ Lx for any t and x. Hence we canwrap up the analysis for (33):
" τ
#
τ
q
o
X np
X
m
m
ES0
2Lgt (St )St + LSt≤
ES0 [ 2L2 St2 ] + Lτ S0
t=1

t=1

=
=

√
√

2L

τ1
X

Em
S0 [St ] + Lτ S

t=1√
2Lτ S0 + Lτ S0 ≤ C1 Lτ S0 ,for some constant C1 . This completes the proof of Theorem 4.4.
Thus we have the following corollary:
Corollary 4.5. Let δ be an arbitrary constant. Consider using the multinomial tree approximation algorithm
to find the price upper bound. When  = cδ 2 /(L2 τ 2 ) for some constant c, the algorithm gives a ĝ0 (S0 ) suchthat g0 (S0 ) − δS0 ≤ ĝ0 (S0 ) ≤ g0 (S0 ).
Tightness of the performance. We shall show in Appendix A.2 that as long as  is a polynomial in τ , anadditive error term that is linear in L and S0 will be unavoidable under the oracle model. This means thatthe running time of our algorithm necessarily depends on L and the additive dependency on S is essentiallytight.
Non-uniform uncertainty set. When the uncertainty sets are non-uniform, we can still use the multinomial
tree algorithm to find the approximate solution so long as the largest uncertainty set is still polynomial in τ .
We remark, though, that the parameter  has to remain unchanged even if the uncertainty sets change over
the time, i.e., our  is still set to  = cδ 2 /(L2 τ 2 ).

21

5Convergence to controlled diffusion process

In this section, we show that our minimax upper bound of the option price, with possibly non-convex
payoff, converges to the price based on a controlled diffusion process when the uncertainty sets are appropriately scaled. To facilitate discussion, for this section we let the time steps be 0, δ, 2δ, . . . , T (for simplicity√√δδ
let T be a multiple of δ), and thus τ = Tδ . Let U δ = [−ζ δ , ζ ], where −ζ δ , −ζ δ and ζ , ζ δ. Let us
recall that we write S(t) as the continuous-time price of the underlying asset at time t, with S(0) = S0 (thisprocess is decided by nature). We have the following theorem:
Theorem 5.1. Let g be a Lipschitz continuous payoff function. As δ → 0, the upper bound of the option
price defined by
!
τ
τ
Y
X
δ
min
max g S0 (1 + Ri ) −∆i Riδ
(34)∆1 ,∆2 ,...,∆τ Rδ ,...,Rτδ ∈U δ
1

i=1

i=1

converges toG(0, S0 ) := max E[g(S(T ))].

(35)

dS(t) = σ(u)S(t)dw(t)

(36)

ξ

Here S(t) follows the dynamic
where w(t) is a standard Brownian motion, σ(u) = u is the controlled volatility, and ξ = {u(t), 0 ≤ t ≤T : u(t) ∈ U } is an adapted control sequence. The domain of control U = [0, ζζ].
Intuitively, this theorem asserts that the continuous-time limit of the option price’s upper bound for nonconvex payoff is Gaussian in nature, similar to the case of convex payoff and Black-Scholes model. The
crucial difference with those cases, however, is that nature now has the additional power to choose (to reduce)
the volatility at any point of time, and this is only helpful to nature in the case of non-convex payoff. Since weknow from Section 4 that in the discrete-time setting with non-convex payoff, the nature does not necessarilychoose the extremal point in the uncertainty set, it is not surprising that there is reduction in volatility at
certain points of time in the continuous-time counterpart. In Appendix B we will also demonstrate how
Theorem 5.1 can be easily reduced to Black-Scholes model in the case of convex payoff.
The way to show Theorem 5.1 is to view the diffusion process (36) as the starting object, and argue
that the discrete-time game is an approximating Markov chain of (36) [KD01]. The following is the key toprove Theorem 5.1:
Rt
Theorem 5.2. Consider x(t) = x0 + 0 σ(w(s), u(s))dw(s) where w(t) is a standard Brownian motion,and u(t) is an adapted control sequence on a compact set U . Let V (t, x) = max E(t,x) [h(x(T ))], where his continuous and E(t,x) denotes the expectation conditional on x(t) = x.
Consider a Markov chain approximation as follows. Divide the time into steps of size δ. Define aMarkov chain {X δ (t)}t=0,δ,2δ,...,T with transition pδ (x, y|α). Let V δ (T, x) = h(x). For each step backward, solveV δ (t, x) = max Eδ,α[V δ (t + δ, X δ (t + δ))](t,X δ (t)=x)α∈U

where Eδ,αis the expectation taken using the transition pδ (x, y|α) for X δ (t+δ). Then we interpolate(t,X δ (t)=x)
X δ (·) and V δ (·, x) such that they are piecewise constant on t ∈ [0, T ], i.e., X δ (s) = X δ (iδ) and V δ (s, x) =V δ (iδ, x) for iδ ≤ s < (i + 1)δ.
Suppose that
1. σ(x, α) is Lipschitz continuous in x, uniformly in U .
22

2. The transition is locally consistent, i.e., Eδ,α[X δ (t + δ) − X δ (t)] = o(δ), Eδ,α(X δ (t +(t,X δ (t)=x)(t,X δ (t)=x)a.s.

δ) − X δ (t))2 = σ(x, α)2 δ + o(δ) for any α ∈ U , and sup0≤t≤T |X δ (t + δ) − X δ (t)| → 0 as δ → 0.
δδ
3. h is uniformly integrable, i.e., limη→∞ supδ Eδ,α(t,x) [|h(X (T ))|; |h(X (T ))| > η] < ∞ for any t, x.
Then V δ (t, x) → V (t, x) pointwise on t ∈ [0, T ], x ∈ R+ .
Outline of proof. The proof is adapted from that of [KD01], p. 356, Theorem 1.4. As such we only provide
an outline here. The proof calls on machinery in weak convergence analysis. Since there is no regularity
condition on the control u(t) in (36), the first step is to enlarge the space of the process to measure-valued
space. Namely, for any given control sequence {u(t)}t∈[0,T ] , we can write
Z tZ
σ(α)x(v)M (dαdv)

x(t) = S0 +
0

(37)

U

where M (dαdv) is a real measure-valued continuous random process defined with, roughly speaking, thefollowing properties: For any fixed measurable subset A in U , M (A, t) is a martingale that has quadratic
variation m(A, t) (so-called martingale measure; see [KD01], p. 352, (1.9)). The quantity m(·, ·) is theso-called relaxed control, and is a measure that puts a delta mass if the control u(t) ∈ A at time t ( [KD01],
p. 263, (5.1)). Under Lipschiz continuity of σ(·, ·) and compact control set U , there is a unique weak sense
solution to (37) ( [KD01], p. 353, discussion under A1.1).
RtR
Now, one can similarly define xδ (t) = S0 + 0 U σ(α)xδ (v)M δ (dαdv) under the relaxed controlmδ that is discretized and interpolated through the time steps 0, δ, 2δ, . . . , T , and M δ (A, t) has quadratic
variation mδ (A, t). By p. 356, Theorem 1.3 in [KD01], under the conditions of Lipshitz continuity of σ(·, ·)and local consistency (i.e., conditions 1) and 2) in our theorem), there exists a subsequence (M δ , mδ ) thatconverges weakly to (M, m). By uniform integrability (i.e., condition 3)), we then have lim inf δ V δ (t, x) ≥V (t, x) for any t, x [AK94]. The final step is to argue that the inequality is in fact matched by some control.
This consists of choosing a so-called -optimal solution of the relaxed control by using a finite-dimensional
Wiener process and a finite-valued and piecewise constant control, and arguing that this solution provides
an -approximation to the optimal value ( [KD01], p. 355, Theorem 13.1.2).
Proof of Theorem 5.1. We will show that our hedging game is an approximating Markov chain to the control
problem given in (35), and has the three listed properties in Theorem 5.2. First, the σ(x, α) in Theorem 5.2
equals xα in (36), where α is the control lying in the compact set U = [0, ζζ].
Second, we check the local consistency property. Define {Gδ (t, x)}t=0,δ,2δ,...,T as the value functionin each step of the backward induction in the discrete-time hedging game defined in (34). Note that by
Proposition 3.2, Gδ (iδ, S δ (iδ)) = maxP ∈P([−ζ δ ,ζ δ ]) E[Gδ ((i + 1)δ, S δ (iδ)(1 + Riδ ))], where we defineQ
S δ (iδ) = S0 ij=1 (1 + Rjδ ) for i ∈ [τ ], and piecewise constant interpolation of S δ (t) for other t. In fact,
we can rewrite this as
maxp1 ,p2 ,r1 ,r2
subject to

p1 G(t + δ, S δ (t)(1 + r1 )) + p2 G(t + δ, S δ (t)(1 + r2 ))p1 r1 + p2 r2 = 0
p1 + p2 = 0
δp1 , p2 ≥ 0, −ζ δ ≤ r1 ≤ r2 ≤ ζ(38)

where we encode the maximal probability distribution in (38) by {p1 , p2 , r1 , r2 }. Let α2 δ = p1 r12 + p2 r22 .
δ
Then the range of α is [0, ζ δ ζ /δ] = [0, ζζ]. We then have Eδ,α[S δ (t + δ) − S δ (t)] = 0 and(t,S δ (t)=x)
23

Eδ,α
(S δ (t + δ) − S δ (t))2 = Eδ,α[(S δ (t))2 (Rδ )2 ] = (S δ (t))2 α2 δ (here Rδ denotes i.i.d copy(t,S δ (t)=x)(t,S δ (t)=x)
δ

of Riδ in (34)). Moreover, |S δ (t + δ) − S δ (t)| ≤ max{ζ δ , ζ } = max{ζ, ζ} · δ and so sup0≤t≤T |S δ (t +a.s.
δ) − S δ (t)| → 0. (One can see the policy defined in terms of α above is not unique; nevertheless it does notaffect local consistency.)
Finally, we claim that g is uniformly integrable. We use an argument similar to the proof of Corolδ
2lary 3.6, and conclude that supδ Eδ,α(t,x) [g(S (T )) ] ≤ C1 S0 exp{T ζζ} + C2 < ∞ for some constants
C1 , C2 > 0, by Lipschitz continuity of g and that α ∈ [0, ζζ]. This will imply that g is uniformly integrable.

6

Integration with jumps

A natural extension to the Black-Scholes framework is to allow “shocks” in the movement of the stock
price, typically modeled by the stochastic community as Poisson arrivals of jumps on top of a continuous
geometric Brownian motion on the asset price. In this section we will adopt our adversary framework toincorporate price jumps.
There can be various ways to model when and how much the adversary can control the price to jump.
Below we analyze two natural examples that can be extended from our framework in the previous sections.
In the first example, we assume the adversary has no control over the occurrence and magnitude of jumps.
We will show that the price upper bound is exactly the same as the price in the standard jump diffusion
model, when the payoff function is convex. In the second example, the adversary can control when thejump happens, subject to a constraint on the total number of jumps. The magnitude of the jumps can also be
assumed to be controllable by the adversary, and we will see that only small modifications to the algorithm
presented in Section 4 are needed.
Example 1. The random jump model. This model assumes a convex payoff function and that thenature performs a jump with a prefixed small probability q at each step. If a jump occurs, the nature moves
according to a return Y that is random (whose distribution is given). Otherwise, with 1 − q probability, thenature will have freedom to choose its path inside the uncertainty set U. We also assume q is sufficiently
small (this will be specified precisely in the sequel).
Consider first a single-round game, with initial price of the underlying asset S0 . The upper boundformulation ismin max(1 − q)[(g(S0 (1 + R))) − ∆R] + qEY [g(S0 (1 + Y )) − ∆Y ],
∆

R

(39)

where R is the return that nature can choose, if a jump does not occur. The expectation EY is with respect
to the jump magnitude variable Y .
The formulation (39) can be written as
minimize p
subject to (1 − q)[(g(x(1 + r))) − ∆r] + qEY [g(x(1 + Y )) − ∆Y ] ≤ p for all r ∈ U

(40)

or
minimize p
subject to p + ∆((1 − q)r + qEY [Y ]) ≥ (1 − q)g(x(1 + r)) + qEY [g(x(1 + Y ))] for all r ∈ U
(41)

24

The dual of (41) ismax(1 − q)E[g(x(1 + r))] + qEY [g(x(1 + Y ))]subject to (1 − q)E[r] + qEY [Y ] = 0
P ∈ P(U)(42)

where P(U) denotes the set of all probability measures supported on U.
We can use the same convexity argument as in Section 3.2 to argue that the optimal measure must beconcentrated at the two extreme points of U, namely −ζ and ζ, when q is small enough i.e., (1 − q)(−ζ) +qEY [Y ] > 0 and (1 − q)ζ + qEY [Y ] < 0. Let the weights of these two extreme points be w1 and w2 . The
constraints (1 − q)(w1 (−ζ) + w2 ζ) + qEY [Y ] = 0 and w1 + w2 = 1 completely determine
w1 =Y [Y ]
ζ + qE1−q

ζ +ζ

, w2 =Y [Y ]
ζ + −qE
1−qζ +ζTherefore, the upper bound is
ζ−qEY [Y ]Y [Y ]
ζ + qE1−q
1−q(1 − q) g(x(1 + ζ)) +g(x(1 + ζ)) + qEY [g(x(1 + Y ))].
ζ +ζ
ζ −ζ

(43)

(44)

For a τ -round game, the formulation follows analogously as in Section 3.4, with the optimal value being
the value function of a dynamic program, with gτ (x) = g(x) and gt (x) equal to (44) but with g replacedby gt+1 . This characterization is exactly the same as a discrete jump diffusion process, studied in [Ami93],
which also demonstrated the continuous-time limit under appropriate scaling of the jump probability andthe binomial return rates. This leads immediately to the following:
Proposition 6.1. Consider the random jump model with jump probability q τ = q/τ for a constant q, jump√√magnitude random variable Y (not scaled with τ ), and uncertainty set U τ = [−ζ/ τ , ζ/ τ ] at each stept ∈ [τ ]. Assume a convex payoff g(·). The upper bound of the option price converges to E[g(S(T ))], where
S(t) follows a jump diffusion process given by
S(t) = S0 exp{νw(t) − ν/2 +J(t)Xlog Y (j)}.

j=1Here ν = ζζ, J(t) is a Poisson process with rate p, and Y (j) are i.i.d. copies of Y .
Example 2. The adversarial jump model. In this model, we allow the adversary to make no more than `jumps throughout the τ rounds of game. When the adversary decides to make a jump, it can choose a returnfrom the uncertainty set W; Otherwise, it can only choose from the ordinary uncertainty set U. We assume
the sizes of U and W are both polynomial in τ . Typically W ⊃ U, but it is not required in the analysis.3
We now explain how our analysis in Section 3 and our algorithm in Section 4 can be extended to this
scenario. Define gt (x, `) as the price upper bound at the t-th round when the underlying asset’s price is x
and the nature still has ` number of jump quota. At the t-th round, if ` ≥ 1, the adversary may choose touse a jump, in which case the relevant price upper bound at the next round will be gt+1 (x(1 + R), ` − 1),
3
For simplicity, we assume the uncertainty sets when jumps are present and absent are both uniform. This condition can easily
be relaxed.

25

where R ∈ W; suppose the adversary chooses not to jump, then the relevant price upper bound becomes
gt+1 (x(1 + R), `), where R ∈ U. The LP formulation for each round is thus
minimize p
subject to gt+1 (x(1 + r), `) − r∆ ≤ p for r ∈ U
gt+1 (x(1 + r), ` − 1) − r∆ ≤ p for r ∈ W, if ` ≥ 1.

(45)

By an argument similar to Proposition 3.2, we can introduce a risk-neutral measure that characterizes
the optimal dual solution for (45). The additional feature here is that the risk-neutral measure comprises of a
mixture between the ordinary uncertainty set and the enlarged uncertainty set, depending on whether a jump
is initiated. The dual formulation can be written asmax

q∈[0,1],Pf ∈P(U ),PJ ∈P(W):qEf [Rt+1 ]+(1−q)EJ [Rt+1 ]=0

qEPf [gt+1 (x(1 + Rt+1 ), `)] + (1 − q)EPJ [gt+1 (x(1 + Rt+1 ), ` − 1)]

Here q is the mixture probability of the occurrence of jump, and Pf and PJ are the conditional distributions
supported on U and W respectively, depending on whether a jump occurs. When ` = 0, then the dual
formulation reduces to the case in Section 4, and we merely havemax

Pf ∈P(U )Ef [Rt+1 ]EPf [gt+1 (x(1 + Rt+1 ), 0)]

The dynamic program has the terminal value gτ (x, `) = g(x) for all ` and gt (x, 0) = gt (x) for all t, wheregt (x) is defined in Section 4.
From this characterization, we can use a multinomial approximation scheme similar to that in Section 4
to compute the price upper bound for general payoff functions. In this algorithm we discretize the uncertainty sets U and W into Û and Ŵ so that the step length in each discrete set is . The new feature is that ineach backward induction step, we compute ĝt (x, m) for m ∈ {0, 1, . . . , `}, where x can take on polynomial
number of distinct values (we can discretize U and W in a coherent way to achieve this). Here, we pay afactor of ` in the running time and the space comlexity compared to the algorithm in Section 4 because of
the exhaustive enumeration regarding `. We have the following analogous performance bound:
Corollary 6.2. Let δ be an arbitrarily small constant. By setting  = cL2 τ 2 /δ 2 for some constant c, ouralgorithm gives ĝ0 (S0 ) such that g0 (S0 ) − δS0 ≤ ĝ0 (S0 ) ≤ g0 (S0 ).
Proof. The proof can be adapted easily from that of Theorem 4.4, hence we shall highlight the main steps
here. First, we extend, in a straightforward manner, the argument in Lemma 4.1 to prove that gt (x, `) is
Lipschitz continuous for any t ∈ [τ ] and p`. Next, the same binding constraint argument as in Lemma 4.3
will reveal that 0 ≤ gt (x, `) − gtm (x, `) ≤ 2L max{gt (x, `), gt (x, ` − 1)}S + Lx for any t and `, wherefor convenience we use the convention that gt (x, −1) = gt (S, 0). Then, since gt (x, `) ≤ Lx for any `by an argument similar to Lemma 4.1, we can use the “artificial” probabilistic machinery to arrive at theconclusion.

7

American options

This section generalizes our results to American-type option. We will give a dual characterization
using risk-neutral measure, and from there we will obtain convergence and algorithmic results similar toEuropean-type options. As before, let us first consider the single-round game.

26

7.1

Single-round American option gameThe upper bound of an American option can be expressed as:
min max ((g(S0 (1 + R)) − R∆)(1 − θ) + g(S0 )θ) ,(46)∆ θ∈{0,1}
R∈U

where θ is the decision made by the adversary in exercising the option prematurely: θ = 1 if early exercise
is prompted, otherwise θ = 0. We remark that it is the adversary, not the trader, to have the right to exercise
early in upper bound evaluation. It is because the upper bound comes from a short-option argument (seeSection 2) that endows nature as the holder of the option and hence the early exercise right. For lower boundevaluation, the bound ismin ((g(S0 (1 + R)) − R∆)(1 − θ) + g(S0 )θ) .

max

(47)

∆,θ∈{0,1} R∈U

Let us focus on the upper bound (46), which can be rewritten as:
min max max ((g(S0 (1 + R)) − ∆R)(1 − θ) + g(S0 )θ) .

(48)∆ θ∈{0,1} R∈U

We shall argue that the min and the first max operators can be interchanged, namely
min max max ((g(S0 (1 + R)) − ∆R)(1 − θ) + g(S0 )θ)∆ θ∈{0,1} R∈U=

max min max ((g(S0 (1 + R)) − ∆R)(1 − θ) + g(S0 )θ) .

θ∈{0,1} ∆R∈U

To simplify notation, let us write Φ(∆, θ) , maxR∈U ((g(S0 (1 + R)) − ∆R)(1 − θ) + g(S0 )θ). Thus,
we need to show min∆ maxθ Φ(∆, θ) = maxθ min∆ Φ(∆, θ). The direction min∆ maxθ Φ(∆, θ) ≥maxθ min∆ Φ(∆, θ) is straightforward. To show that min∆ maxθ Φ(∆, θ) ≤ maxθ min∆ Φ(∆, θ), themain observation is that ∆ is only influential if θ = 0. More precisely, consider maxθ min∆ Φ(∆, θ). When
θ = 1, min∆ Φ(∆, θ) = g(S0 ), independent of the choice of ∆; when θ = 0, we have min∆ Φ(∆, θ) =maxP ∈P(U ) E[g(S0 (1 + R))] by Proposition 3.2, with ∆∗ = arg max∆ g(S0 (1 + R)) − ∆R. Hence
E[R]=0max min Φ = max
θ

∆









max E[g(S0 (1 + R))], g(S0 )P ∈P(U )(49)

E[R]=0Consider using ∆∗ in maxθ Φ(∆, θ). We then havemin max Φ(∆, θ) ≤ max Φ(∆∗ , θ) = max
∆

θ

θ









max E[g(S0 (1 + R))], g(S0 ) .

P ∈P(U )(50)

E[R]=0Thus, we have min∆ maxθ Φ(∆, θ) = maxθ min∆ Φ(∆, θ), which renders the single-round price upperbound (46) as






min max ((g(S0 (1 + R)) − R∆)(1 − θ) + g(S0 )θ) = max
max E[g(S0 (1 + R))], g(S0 )(51)∆ θ∈{0,1}
P ∈P(U )R∈U

E[R]=027

Analogously, the lower bound ismax

min ((g(S0 (1 + R)) − R∆)(1 − θ) + g(S0 )θ) = max∆,θ∈{0,1} R∈U









min E[g(S0 (1 + R))], g(S0 )P ∈P(U )E[R]=0

7.2

Multi-round gameWith Eq. (51), we can get characterization and convergence results for American options for convex
payoff for multi-round game:
Lemma 7.1. Consider a τ -round American option hedging game with convex payoff function g(·) anduniform uncertainty set U = [−ζ, ζ]. The option price’s upper bound is the same as the τ -round binomial
tree model. Moreover, if U has the same scaling as Corollary 3.6 as τ → ∞, the upper bound converges tothe Black-Scholes price.
Proof. The proof follows similarly as that for European-type options. We will argue that gt (x) is convex forany t and






E[gt+1 (x(1 + R))], g(x) .
(52)
gt (x) = max
max



P ∈P({−ζ,ζ})E[R]=0by induction. First, as in Corollary 3.3, when gt+1 (·) is convex, the optimal risk-neutral measure for thedual problem at the t-th round, assuming the option is not exercised, has probability masses only at {−ζ, ζ}.
Second, when gt+1 (·) is convex, maxP ∈P({−ζ,ζ}) E[gt+1 (S(1 + R))] is also convex by Lemma 3.5. Since
E[R]=0the maximum of convex functions is still convex, we conclude the induction.
The algorithm for computing American options over binomial trees can be found in, for example, [Hul09].
It is known that under the binomial tree model, it is always optimal to exercise at the terminal time for American call option, but not the case for put option. These results immediately carry over to our model.
For non-convex payoff in upper bound calculation, or any payoff in lower bound calculation, the reduction to binomial tree does not necessarily hold. One can resort to our multinomial tree algorithm presented
in Section 4 to approximate, for instance the upper bound, using the following recursive formula:






ĝt (x) = max
max E[ĝt+1 (x(1 + R))], ĝ(x) ,(53)
P ∈P(Û )E[R]=0where Û is the discretized uncertainty set with step length . The performance can be analyzed by using thesame techniques presented in Section 4, which gives the following corollary:
Corollary 7.2. Let δ be an arbitrary constant. Consider using the multinomial tree approximation algorithm
to find the American option’s upper bound. When  = cδ 2 /(L2 τ 2 ) for some constant c, the algorithm gives
an ĝ0 (S0 ) such that g0 (S0 ) − δS0 ≤ ĝ0 (S0 ) ≤ g0 (S0 ).

28

7.3

Continuous-time exercise right

One arguably unsatisfying feature in our model for the upper bound of American options is that thenature can only exercise the option at discrete rounds, i.e., at the times when the trader can execute tradedecisions. There is a natural formulation to relax this constraint, and it turns out that this relaxation does notchange our existing model.
Definition 7.3 (American option hedging game with continuous-time exercise right.). We model the dynamics for an American option, with payoff g(·) and expiration T , by considering a τ -round game between
the trader and the nature. The time length for each round is γ , T /τ . Let {−ζ i , ζ i } be the uncertainty
parameters for the i-th round. In this game,• the investor is only allowed to trade at the beginning of each round, i.e., at time 0, γ, 2γ, ..., T .
• the adversary is allowed to exercise the option at any time. The adversary also decides the (continuous) trajectory of the price movement subject to the following constraints specified by the uncertainty
parameters: let t = iγ + δ, where δ < γ; we require −ζ i+1 · δ/γ ≤ St /Siγ − 1 ≤ ζ i+1 · δ/γ for any
δ < γ.
Intuitively, the price movement lies in the uncertainty set in the form of a “cone” that extends from timeiγ to (i + 1)γ. By using a simple change of variable trick, we have the following observation:
Corollary 7.4. In the model in Definition 7.3, the upper bound of an American option’s price is the same as
the upper bound from the ordinary hedging game introduced in Section 7.2.

References[AB09]

S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University
Press, 2009.

[AFW12] Jacob Abernethy, Rafael M. Frongillo, and Andre Wibisono. Minimax option pricing meetsblack-scholes in the limit. In STOC, pages 1029–1040, 2012.
[AK94]

Kaushik Amin and Ajay Khanna. Convergence of american option values from discrete-to
continuous-time financial models1. Mathematical Finance, 4(4):289–304, 1994.

[Ami93]K. I. Amin. Jump diffusion option valuation in discrete time. Journal of Finance, pages 1833–
1863, 1993.

[BB12]

Chaithanya Bandi and Dimitris Bertsimas. Tractable stochastic analysis in high dimensions via
robust optimization. Mathematical programming, 134(1):23–70, 2012.

[Ber05a] P. Bernhard. A robust control approach to option pricing including transaction costs. Annals of
the ISDG, 7:391–416, 2005.
[Ber05b] Pierre Bernhard. The robust control approach to option pricing and interval models: an overview.
In Michèle Breton and Hatem Ben-Ameur, editors, Numerical Methods in Finance, pages 91–
108. Springer, New York, 2005.
[BG04]Mark Broadie and Paul Glasserman. A stochastic mesh method for pricing high-dimensional
american options. Journal of Computational Finance, 7:35–72, 2004.

[Bil09]Patrick Billingsley. Convergence of Probability Measures. Wiley Series in Probability and Statistics, 2009.
29

[BS73]Fischer Black and Myron Scholes. The Pricing of Options and Corporate Liabilities. The Journalof Political Economy, 81(3):637–654, 1973.

[Che10]Si Chen. Robust option pricing : An -arbitrage approach. Master’s thesis, MIT, 2010.

[CHW11] Qi Cheng, Joshua E. Hill, and Daqing Wan. Counting value sets: Algorithm and complexity.
CoRR, abs/1111.1224, 2011.
[CRR79] John C. Cox, Stephen A. Ross, and Mark Rubinstein. Option pricing: A simplified approach.
Journal of Financial Economics, 7(3):229–263, September 1979.
[CT12]

R. Cont and P. Tankov. Financial Modelling with Jump Processes, Second Edition. Chapman &Hall/Crc Financial Mathematics Series. CRC PressINC, 2012.

[DKM06] Peter DeMarzo, Ilan Kremer, and Yishay Mansour. Online trading algorithms and robust option
pricing. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing,
STOC ’06, pages 477–486. ACM, 2006.
[Duf05]

D. Duffie. Dynamic Asset Pricing Theory. New Age International (P) Limited, 2005.

[Dur10]R. Durrett. Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic
Mathematics. Cambridge University Press, 2010.

[FIA12]FIA. http://www.futuresindustry.org/volume-.asp. Trading Volume Statistics, 2012.

[FS06]W. H. Fleming and H. M. Soner. Controlled Markov Processes and Viscosity Solutions. Springer,
2006.

[GM11]

Eyal Gofer and Yishay Mansour. Regret minimization algorithms for pricing lookback options.
In Proceedings of the 22nd international conference on Algorithmic learning theory, ALT’11,
pages 234–248. Springer-Verlag, 2011.

[He90]

Hua He. Convergence from discrete-to continuous-time contingent claims prices. Review of
Financial Studies, 3(4):523–546, 1990.

[Hes93]

Steven L. Heston. A closed-form solution for options with stochastic volatility with applications
to bond and currency options. Review of Financial Studies, 6:327–343, 1993.

[HF11]

Alexander Schied Hans Follmer. Stochastic Finance: An Introduction in Discrete Time. Walterde Gruyter, 2011.

[Hul09]J. Hull. Options, Futures, & Other Derivatives. Prentice Hall finance series. Prentice Hall, 2009.

[KD01]

H.J. Kushner and P. Dupuis. Numerical Methods for Stochastic Control Problems in Continuous
Time. Applications of Mathematics Series. Springer, 2001.

[Kol11]

Vassili Kolokoltsov. Game theoretic analysis of incomplete markets: emergence of probabilities,
nonlinear and fractional black-scholes equations. CoRR, abs/1105.3053, 2011.

[Kou02]

Steven G Kou. A jump-diffusion model for option pricing. Management science, 48(8):1086–
1101, 2002.

30

[Lue97]

D.G. Luenberger. Optimization by Vector Space Methods. Series in Decision and Control. Wiley,1997.

[Mer73]Robert C. Merton. Theory of Rational Option Pricing. Bell Journal of Economics and Management Science, 4(1):141–183, 1973.

[Mer76]

Robert C Merton. Option pricing when underlying stock returns are discontinuous. Journal of
financial economics, 3(1):125–144, 1976.

[MMS89] Dilip B Madan, Frank Milne, and Hersh Shefrin. The multinomial option pricing model and its
brownian and poisson limits. Review of Financial Studies, 2(2):251–265, 1989.
[REK00] Richard Rouge and Nicole El Karoui. Pricing via utility maximization and entropy. Mathematical
Finance, 10(2):259–276, 2000.
[RES05] Berend Roorda, Jacob Engwerda, and Johannes M. Schumacher. Performance of hedging strategies in interval models. Kybernetika, 41(5):[575]–592, 2005.
[Ser80]R. J. Serfling. Approximation Theorems of Mathematical Statistics. John Wily & Sons, Inc.,
1980.

[Shr04]

Steven Shreve. Stochastic Calculus for Finance II: Continuous-Time Models. Springer Finance,
2004.

[Ste01]

M. J. Steele. Stochastic calculus and financial applications. Springer, 2001.

A

Hardness results

A.1

Computational lower bound: #P -hard result for non-uniform uncertainty sets

This section proves that the problem of exactly computing the price upper bound is #P -hard for nonuniform uncertainty sets, even when the payoff function is convex.
We reduce our problem from the counting subset sum problem. Let A = {a1 , ..., aτ } be a set of
positive integers. The counting problem here is to count the number of subsets T ⊆ A such that the sum ofintegers in T equals to b. This problem is known to be #P -hard [CHW11].
We use a Cook-Reduction (see e.g., Chapter 17 in [AB09]) and our reduction proceeds as follows.
Given a counting subset sum instance {A, b}, we construct the price upper bound for a τ -round Europeanaoption hedging game such that the uncertainty set Ui at the i-th round is [−ζ i , ζ i ], where ζ i = ζ i = eeaii −1+1 .
+The payoff function is the ordinary call option with strike K, i.e., g(x) = (x − K) . Since the payoff isconvex, the optimal risk-neutral probability measure only has uniform probability mass on {−ζ i , ζ i } at eachround, i.e., the price moves up by a factor (1 + ζ i ) with probability 12 and moves down by a factor (1 − ζ i )with probability 12 for each round.
Let P ∗ be this optimal probability measure. We next build a natural coupling between sampling a
subset T ⊆ A and moving a price trajectory in the binomial tree: an element ai ∈ T if and only if theprice trajectory moves up at the i-th round. Under this probability measure, the total number of subsets T in
which the elements sum up to b isX
2τ Pr ∗ [ai = b].
T ←P

ai ∈T

31

P
We next express the probability PrT ←P ∗ [ ai ∈T ai = b] in terms of option prices. When T is sampled fromP ∗ , the coupled trajectory’s final price is


Y
Y
Y
Y
Y
X
2
2
S0
(1 + ζ i )(1 − ζ i ) = S0
eai = S0exp 
ai  .
eai + 1eai + 1ai ∈T

Let C =

ai ∈A

ai ∈T
/

Q

ai ∈T

ai ∈A

ai ∈T

2
ai ∈A eai +1 . We can see from the above equation thatPr ∗ [T ←P

X

ai = b] = Pr∗ [Sτ = S0 C exp(b)].
P

ai ∈T

Let us consider options with three different strike prices K1 = S0 C exp(b − 1), K2 = S0 C exp(b), andK3 = S0 C exp(b + 1). Let their corresponding prices be V1 , V2 , and V3 . We can compute V1 as follows:
Z
X
X
V1 = (Sτ − K)+ dP ∗ =Pr[ai = j](S0 C exp(j) − K1 ).
ai ∈T

j≥b

Similarly, we have
V2 =

X
j≥b+1

Pr[

X

ai = j](S0 C exp(j) − K2 ),

ai ∈T

and
V3 =

X
j≥b+2

Pr[

X

ai = j](S0 C exp(j) − K3 ).

ai ∈TFrom the above equalities, we haveP
V1 − V2 = Pr[ ai ∈T ai ≥ b]S0 C(exp(b) − exp(b − 1))P
V2 − V3 = Pr[ ai ∈T ai ≥ b + 1]S0 C(exp(b + 1) − exp(b)).
Therefore, we havePr[X

ai = b] =ai ∈TV1 − V2
V2 − V3−,
S0 C(exp(b) − exp(b − 1)) S0 C(exp(b + 1) − exp(b))

which completes our reduction.

A.2

Information theoretic lower bound: additive dependencies on S0

We now present a lower bound under the oracle model to justify the necessity of our algorithm’s additive
dependency on the stock’s initial price S0 and the Lipschitz parameter L, even for a single-round model.
Specifically, we shall show that in a single-round hedging game, if the number of queries to the oracle is b,then there exists two payoff functions g(x) and h(x) such that:
1. Both functions are monotonic, L-Lipschitz, and have the same values at the queried points.
2. There exists an S0 such that the difference between the price upper bounds at S0 for the functions isΘ(LS0 /b).
In other words, so long as the number of queries is only polynomial in τ , there will be an additive error thatis linear in S0 and L.
We now explain our construction. Let u be the size of the uncertainty set. Let the query points be
q1 < q2 < ... < qi < 0 < ... < qb , where qb − q1 ≤ u. For expositional purpose, let us assume there are at32

least two queried points on the negative axis. Also, let us assume U is symmetric, i.e., U = [− u2 , u2 ]. Bothassumptions can easily be relaxed.
u
By using an averaging argument, we see that there exists i and j such that (qi < 0 and qi − qi−1 ≥ 2b)u
and (qj > 0 and qj+1 − qj ≥ 2b ). Now we define g(x) and h(x) as follows:
Definition of g(x): Let C be a sufficiently large number, e.g., C = (1 + 100u)S0 .
 Lx
x≤C
2
g(x) =
Lx x > C.
Definition of h(x): Let I1 = [(1 + qi−1 )S0 , (1 + qi )S0 ] and I2 = [(1 + qj )S0 , (1 + qj+1 )S0 ].

g(x)
x∈
/ I1 , I2 .





x ∈ [(1 + qi−1 )S0 , (1 + qi−12+qi )S0 ] Lx
L(1 + qi )S0 /2
x ∈ [(1 + qi−12+qi )S0 , (1 + qi )S0 ]h(x) =
q +qx ∈ [(1 + qj )S0 , (1 + j 2 j+1 )S0 ]
 Lx

q +q

L(1 + qj+1 )S0 /2 x ∈ [(1 + j 2 j+1 )S0 , (1 + qj+1 )S0 ].

(54)

(55)

We can see that the price upper bound for g(S0 ) in this single-round model is LS0 /2. For h(x), we cansee that in the dual characterization of its optimal solution, the corresponding risk-neutral measure hasq+q
probability masses only at r1 , qi +q2i−1 and r2 , j+12 j . Thus, the price upper bound for h(S0 ) is at least
S0 ( L2 + uL
2b ), which completes our argument.

B

Reduction to Black-Scholes model from controlled diffusion processThis section elaborates on Section 5 and provides an alternative proof for the continuous-time convergence of our price upper bound to the Black-Scholes model when the payoff function is convex. We
shall derive a heuristic partial differential equation (PDE) that characterizes the solution for the controlled
diffusion in Theorem 5.1. Then, under additional convexity assumption, we will demonstrate that our PDE
is rigorously defined and coincides with the PDE for the Black-Scholes model.
To begin, let us write down a Hamilton-Jacobi-Bellman (HJB) equation informally using (35) and (36).
Define G(t, x) = maxξ E(t,x) [g(S(T ))], where E(t,x) denotes the expectation conditional on S(t) = x
and using the optimal control (and hence G(0, S(0)) is as defined in (35)). Assuming for the moment thatG ∈ C 2 , we can heuristically writeG(t, x) = max E(t,x) [G(t + δ, S(t + δ))]ξ1= max E(t,x) [G(t, x) + Gt (t, x)δ + Gx (t, x)xRδ + Gxx x2 (Rδ )2 + · · · ] (by Taylor’s series)ξ2
1= G(t, x) + Gt (t, x)δ + Gxx x2 max E(t,x) [(Rδ )2 ] + · · · (since E(t,x) [Rδ ] = 0)
ξ
2

2

∂
∂
where Rδ = S(t + δ)/S(t) − 1, Gx (t, x) = ∂x
G(t, x), Gxx (t, x) = ∂x
2 G(t, x) etc.
δ22Since U = [0, ζζ] and E(t,x) [(R ) ] = σ(u) δ, one can attempt to establish that G(t, x) is the solutionof the following PDE:
1
Gt (t, x) + max σ(u)2 x2 Gxx (t, x) = 0
(56)
2 u∈U

33

with the boundary condition G(T, x) = g(x). In general, the solution of this PDE may not exist in theclassical sense, and there is no guarantee to coincide with the optimal solution to the control problem in(35) [FS06]. The following theorem, nevertheless, presents a verification of the PDE’s solution as thecontrol problem’s optimum, under a priori smoothness condition on G:
Theorem B.1. Suppose G∗ ∈ C 2 is a solution for (56) (hence implying that the payoff function g must be inC 2 ), and that there exists an optimal u∗ (t, x) as the optimal solution to the max in (56). Then G∗ (0, x) is
the optimal solution to the control problem in (35), and u∗ (t, x) is the optimal control in (36).
Proof. The proof follows by a standard application of Ito’s lemma. For any t < t0 and x, we haveE∗(t,x) [G∗ (t0 , S(t0 ))] − G∗ (t, x)
"Z 0
#
Z t0
Z t0
t
1 ∗
∗
∗
∗
2 ∗
= E(t,x)
Gt (t, S(t))dt +Gx (t, S(t))dSt +G (t, S(t))σ (u (t, S(t)))dt
2 xx
t
t
t
"Z 0 
 #t1= E∗(t,x)G∗t (t, S(t)) + G∗xx (t, S(t))σ 2 (u∗ (t, S(t))) dt (since S(t) is a martingale)2t=0

by (56), where E∗(t,x) denotes the expectation taken when the control is u∗ . On the other hand, any control
u(t, x) must satisfy
1(57)
Gt (t, x) + σ(u(t, x))2 x2 Gxx (t, x) ≤ 0
2by the definition of (56). Hence the same argument leads toEu(t,x) [G(t0 , S(t0 ))] − G(t, x)
"Z 0
#
Z t0
Z t0
t
1
u
2
Gt (t, S(t))dt +Gx (t, S(t))dS(t) += E(t,x)Gxx (t, S(t))σ (u(t, S(t)))dt
t
t 2
t
≤0
where E∗(t,x) denotes the expectation taken when the control is u. Hence E∗(t,x) [G∗t (t0 , S(t0 ))] = G∗t (t, x) ≥Eu(t,x) [G(t0 , S(t0 ))] for any u. Take t = 0 and x = S0 , we obtain the result.
From Theorem B.1, we can obtain the Black-Scholes price when the payoff is convex. Observe that(56) can in fact be written as
1
Gt (t, x) + ζζx2 Gxx (t, x)I(Gxx (t, x) ≥ 0) = 0
2(58)

with boundary condition G(T, x) = g(x). Suppose G ∈ C 2 is convex in x and so Gxx (t, ·) ≥ 0, then theequation (58) reduces to
1
Gt (t, x) + ζζx2 Gxx (t, x) = 02
which is the ordinary Black-Scholes PDE with zero risk-free rate, whose solution is known to be convex
and lies in C 2 when the payoff g is convex and in C 2 [Ste01]. Hence by Theorem B.1 it is the solution to thecontrol problem in (35), which is the limit of our hedging game model.
Lastly, suppose that Gxx (t, ·) is concave, and so Gxx (t, x) < 0. The equation (58) then reduces to
Gt (t, x) = 0, which implies that the solution is g(x), constant over t ∈ [0, T ]. If the payoff g is concave,
we know again by Theorem B.1 that g(x) is the optimal value of (35). This also characterizes the limit in
Section 3.2 when the payoff is concave.
34

C

Missing calculation

Proof of (29)r(2)r̂(1) r(2) − r̂(2) r(1)
r̂(2)
=
+
r̂(2) − r̂(1)r(2) − r(1) (r̂(2) − r̂(1) )(r(2) − r(1) )=r(2) (r̂(1) − r(1) ) − r(1) (r̂(2) − r(2) )r(2)+r(2) − r(1)(r̂(2) − r̂(1) )(r(2) − r(1) )≥r(2)r(2) 
−(since −r̂(1) (r̂(2) − r(2) ) ≥ 0 and |r̂(1) − r(1) | < )r(2) − r(1) (r̂(2) − r̂(1) )(r(2) − r(1) )r(2)r(2) 
−(by construction we have r̂(2) − r̂(1) ≥ r(2) − r(1) )r(2) − r(1) (r(2) − r(1) )2


r(2)

≥ (2)
1−
η
r − r(1)≥35