Second-order PDE’s and deterministic games
Robert V. Kohn and Sylvia Serfaty∗

Abstract. We provide a brief, expository introduction to our recent work on deterministicgame interpretations of second-order parabolic and elliptic PDE.
Mathematics Subject Classification (2000). Primary 49L20, 35J60, 35K55; Secondary 35C99, 49L25, 91A20.
Keywords. deterministic games, motion by curvature, fully nonlinear parabolic equations.

1. Introduction
This note gives a brief, expository introduction to our recent work concerning
deterministic game interpretations of some nonlinear second-order PDE’s. There
are two related but distinct themes:• Deterministic control interpretations of geometric evolution laws [10], and• Deterministic control interpretations of fully nonlinear PDE’s [11].

To capture the main ideas, we shall focus here on simple examples and heuristic
arguments. The discussions in [10, 11] are of course quite diﬀerent — much moregeneral and mathematically rigorous.

2. Deterministic control interpretations ofgeometric evolution laws
The “level-set method” was introduced in the 1980’s as a numerical method forthe simulation of geometric evolution laws [12]. Within a few years, it was also
recognized as a powerful tool for analyzing the existence and uniqueness of suchmotions [3, 7].
When the velocity of the moving surface depends only on the normal direction,
the level-set description of the motion is a first-order PDE (a Hamilton–Jacobi
equation). When the velocity depends on curvature, the level-set description is a
∗ The authors gratefully acknowledge support from NSF through grants DMS-0313744 (RVK)
and DMS-0239121 (SS), and from the Alfred P. Sloan Foundation through a Sloan Foundation
Fellowship (SS).

2

R.V. Kohn and S. Serfaty

second-order parabolic or elliptic PDE. We usually think of first-order and secondorder PDE’s as being quite diﬀerent. For example,• First-order equations have characteristics while second-order parabolic andelliptic equations do not.
• Hamilton–Jacobi equations have well-known links to deterministic control
problems (for example, this is the essence of the Hopf–Lax solution formula
for ut − H(∇u) = 0 when H is convex); for second-order equations theconventional control interpretations are quite diﬀerent, involving stochastic
rather than deterministic control.
The starting point of [10] was the observation that for geometric evolutions, thefirst and second-order cases are actually quite similar. To explain the core idea,
let us focus on two key examples:(i) Motion with constant velocity. Consider the evolution of a region Ω in theplane as its boundary moves inward with constant velocity 1 (Figure 1, left).
The evolution is completely characterized by the arrival timeu(x) = time that the moving boundary passes through x.
This function solves the stationary Hamilton–Jacobi equation|∇u| = 1 in Ω(1)with u = 0 at the boundary, and it is characterized by the optimizationu(x) = min dist(x, z).
z∈∂Ω

(2)

(ii) Motion by curvature. Now consider the evolution of a convex region Ω in theplane as its boundary moves with velocity equal to its curvature (Figure 1,
right). To track the evolution of the boundary as a parameterized curve wemust solve a nonlinear parabolic PDE. But if the region is initially convex
then it stays convex, so the evolution is again completely characterized by
its arrival time u. A moment’s thought reveals that −div (∇u/|∇u|) is thecurvature of a level set of u, and the velocity of the moving front is 1/|∇u|,so the arrival time of motion by curvature solves|∇u| div (∇u/|∇u|) + 1 = 0 in Ω(3)with u = 0 at the boundary. This PDE is to motion by curvature as theeikonal equation (1) is to motion with constant velocity.
We claim these evolutions are similar in the sense that motion by curvature
also has a deterministic control interpretation, analogous to (2). It involves a twoperson game with players Paul and Carol, and a small parameter ε. Paul is initiallyat some point x ∈ Ω; his goal is to exit as soon as possible, and Carol wants todelay his exit as long as possible. The rules are as follows:3

Second-order PDE’s and deterministic games

Figure 1. Left. Motion with constant velocity. Right. Motion by curvature.

• Paul chooses a direction, i.e. a unit vector |v| = 1.
• Carol can either accept or reverse Paul’s choice, i.e. she chooses b = ±1.
√• Paul then√ moves distance 2ε in the possibly-reversed direction, i.e. from x
to x + 2εbv.
• This cycle repeats until Paul reaches ∂Ω.
For example, if Paul is near the top of the rectangle, one might think he shouldchoose v pointing north. But that’s a bad idea: if he does so, Carol will reverse
him and he’ll have to go south (Figure 2, left).

x

x

x

Figure 2. Left. Paul’s quandary – if he tries to go north, Carol will send him south.
Middle. Paul can exit from a well-chosen concentric circle in just one step. Right. The
construction can be repeated.

Can Paul exit? Yes indeed. This is easiest
to see when ∂Ω is a circle of radius√
R. The midpoints of secants of length 2 2ε trace a concentric circle, whose radius
is smaller by approximately ε2 /R. Paul can exit in one step if and only if he starts
on or outside this concentric circle (Figure 2, middle). This construction can be
repeated of course, producing a sequence of circles from which he can exit in a
fixed number of steps (Figure 2, right). Aside from the scale factor of ε2 they

4

R.V. Kohn and S. Serfaty

are shrinking with normal velocity 1/R = curvature. We have determined Paul’s
optimal strategy: if Ω = BR (0) and his present position is x then his optimal v
is perpendicular to x. And we have linked his minimum exit time to motion by
curvature.
This calculation is fundamentally local, so it is not really limited to balls. It
suggests that Paul’s scaled arrival time,!
"minimum number of steps Paul needs to exit startinguε (x) = ε2 ·(4)from x, assuming Carol behaves optimally,
converges as ε → 0 to the arrival-time function of motion by curvature. It evenprovides us with something resembling characteristics for the second-order PDE(3). In fact: Paul’s paths are like characteristics, in the sense that the PDE
becomes an ODE when restricted to the path (uε decreases by exactly ε2 at eachstep along Paul’s path).
The circle was too easy. How does one analyze more general domains? A key
tool is the dynamic programming principle:
$
#
√
(5)
uε (x) = min max uε (x + 2εbv) + ε2 .
|v|=1 b=±1

In words: starting from x, Paul selects the best direction v (taking account that
Carol is working against him), recognizing that after taking this step he will pursue
an optimal path. This principle captures the logic we used in passing from the
middle frame of Figure 2 to the right hand frame.
The degenerate-elliptic equation (3) is, in essence, the Hamilton–Jacobi–Bellman
equation associated with this dynamic programming principle. To explain why, we
use an argument that’s familiar from optimal control theory (see e.g. Chapter 10of [6]). Assume uε is smooth enough for Taylor expansion to be valid. Then (5)
gives
#
$
√
uε (x) ≈ min max uε (x) + 2εbv · ∇uε (x) + ε2 ⟨D2 uε (x)v, v⟩ + ε2 ,(6)|v|=1 b=±1

whence0 ≈ min max|v|=1 b=±1$#√2εbv · ∇uε (x) + ε2 ⟨D2 uε (x)v, v⟩ + ε2 .

Paul should choose v such that v · ∇uε (x) = 0, since otherwise this term will
dominate the right hand side and Carol will choose the sign of b to make it positive.
In the plane this forces v = ±∇⊥ u/|∇u|. Either choice is OK: the sign doesn’t
matter, since the next term is quadratic. We conclude (formally, in the limit ε → 0)that∇⊥ u ∇⊥ u⟨D2 u,⟩ + 1 = 0.
|∇u| |∇u|
A bit of manipulation reveals that this is the same as (3) in two space dimensions.
To summarize: motion by curvature is similar to motion with constant velocity in the sense that both evolutions can be described by deterministic control

Second-order PDE’s and deterministic games

5

problems (the Paul–Carol game versus equation (2)). The PDE that describes thearrival time is, in either case, the associated Hamilton–Jacobi–Bellman equation,
derived from the control problem using the principle of dynamic programming.
There is, however, a diﬀerence: the Paul–Carol game has a small parameter ε,and we only get motion by curvature in the limit ε → 0; the optimal control
interpretation of the eikonal equation, by contrast, has no small parameter.
This discussion has been formal, and it has focused on just the simplest example. But these ideas can be justified and extended to other geometric motions. In
particular:• The convergence of Paul’s scaled arrival time uε to the arrival time of motion by curvature can be proved using the framework of “viscosity solutions,”
following [3, 7]. When u is smooth enough, one can alternatively use a “verification argument;” this gives a stronger result, by estimating the convergencerate. The required smoothness is valid for the arrival time of motion by
curvature in the plane; interestingly, however, it fails for the arrival time of
motion by mean curvature of a higher-dimensional hypersurface [16].
• The case when Ω is nonconvex is more subtle. Then limε→0 uε is the arrival
time of a diﬀerent motion law, namely the one with normal velocity κ+ whereκ is curvature and κ+ = max{κ, 0}. The proof depends on a uniquenessresult for viscosity solutions, due to Guy Barles and Francesca Da Lio, given
in Appendix C of [10].
• These ideas can be extended to higher space dimensions and other geometricevolutions; moreover, the method can be used for parabolic as well as elliptic representations of curvature-driven motion [10]. In addition, a similar
approach to some nonlocal geometric evolutions is developed in [9], and a
Neumann problem for motion by curvature is addressed in [8].
Our work in this area had important precursors. The Paul–Carol game isessentially a semi-discrete approximation scheme (continuous in space, discrete intime) for motion by curvature. Similar semi-discrete schemes had been consideredin the literature on computer vision (e.g. [2, 13, 14]), and in work on numerical
schemes for computing viscosity solutions of second-order PDE’s [5].
When Paul chooses optimally he becomes indiﬀerent to Carol’s choices. One
can ask: what happens if Carol just flips a fair coin, but Paul’s goal is to arrivewith probability one in the minimum possible time? A continuous-time version ofthis problem was studied in [1, 17], as a stochastic-control interpretation of motion
by curvature. Paul’s optimal choice of direction is same for this stochastic gameas in our deterministic setting – roughly speaking, because if he makes a diﬀerent
choice, Carol will take advantage of it with probability 1/2.
By the way, we didn’t invent the Paul–Carol game. It was introduced thirty
years ago by Joel Spencer, as a heuristic for the study of certain combinatorial
problems [18].

6

R.V. Kohn and S. Serfaty

3. Deterministic control interpretations of fully
nonlinear PDE’s
The preceding discussion seems strongly linked to the geometric character of the
problem. In particular, Paul’s value function uε converged to the level-set description of a geometric motion. It is natural to whether deterministic game interpretations can also be given for other (non-geometric) second-order PDE’s.
The answer is yes! Of course it requires a slightly diﬀerent perspective. The
following deterministic game approach to the 1D linear heat equation was suggested
to us by H. Mete Soner. As usual in control theory, we focus on solving a well-posed
PDE backward in time:
vt + vxx = 0 for t < T ,with v = φ at t = T .

(7)

The associated game has two players; we’ll call them Helen and Mark (for a reason
to be explained below). There’s a marker, that’s initially at position x ∈ R at timet. At each timestep• Helen chooses a real number α, then (after hearing Helen’s choice) Markchooses b = ±1.
√• Helen pays penalty 2εαb.
√• The marker moves from x to x + 2εb and the clock steps from t to t + ε2 .

The game continues this way until time T . At the√final time, Helen collects abonus φ(x(T )). We referred to Helen’s payment of 2εαb as a “penalty,” but if
this number is negative then it actually represents a gain.
We did not yet specify how Helen and Mark make their respective choices.
Helen’s goal is to maximize her bonus less accumulated penalties. Mark’s goal
is to give Helen the worst possible result (and Helen knows this). Helen’s valuefunction!
"her optimal final-time bonus minus accumulated penalty,vε (x, t) =(8)
if the marker starts at position x at time t,
is thus determined by the dynamic programming principle$#√√vε (x, t) = max min vε (x + 2εb, t + ε2 ) − 2εαbα∈R b=±1(9)along with the final-time condition vε (x, T ) = φ(x). This leads to the linear heat
equation as ε → 0 by the same (Taylor-expansion-based) argument used in the lastsection: proceeding as in (6) and dropping the subscript ε we get#$√v(x, t) ≈ max min v(x, t) + 2εb(vx − α) + ε2 (vt + vxx ) .
(10)α∈R b=±1

Helen must choose α = vx to neutralize the term that’s linear in ε (otherwise Mark
will choose b to make this term negative). This choice of α makes Helen indiﬀerent
to Mark’s choice of b, so (10) becomesv(x, t) ≈ v(x, t) + ε2 (vt + vxx ).

7Second-order PDE’s and deterministic games

Subtracting v(x, t) from both sides and dividing by ε2 we conclude that vt +vxx = 0,
as desired.
This “game” interpretation of the linear heat equation may seem mysterious,
but actually it is rather familiar. In fact it is closely related to the well-known factthat European options can be perfectly hedged in a binomial tree market. In thisfinancial interpretation, with ε > 0,x = the stock price−α = the amount of stock in Helen’s hedge portfolio%√
2εαj bj = Helen’s profit or loss on the hedge portfoliojvε (x, t) = time-t value of the option with payoﬀ φ at time T ,with the convention that αj and bj are Helen’s choice of α and Mark’s choice of b attime tj = t + jε2 . Our players’ names come from this interpretation: Helen is thehedger, Mark controls the market. The stock prices are√restricted to an (additive)
binomial tree, since x increases or decreases by exactly 2ε at each timestep. The
key assertion of perfect hedging is that for a suitable choice of αj ,vε (x0 , t0 ) +%√2εαj bj = φ(x(T ))

(11)

j

regardless of how bj = ±1 are chosen. Helen is very risk-averse; she always assumes
the market (Mark) will move to her detriment. Her optimal αj are therefore theones that make (11) true.
The preceding discussion was formal, but (like the arguments in Section 2) it
can be fully justified. The rigorous version places a weak upper bound on α (ofthe form |α| ≤ ε−a where a > 0). The main result is that limε→0 vε (x, t) exists
and solves the linear heat equation.
Something similar can be done for a large class of fully nonlinear parabolic andelliptic equations. To explain the main idea, consider a final-value problem of theform
vt + f (Dv, D2 v) = 0 for t < T , with v = φ at t = T(12)
on all Rn . We assume the PDE is (degenerate) parabolic, in the sense thatf (p, Γ) ≤ f (p, Γ′ )if Γ ≤ Γ′ as symmetric matrices.

(13)

The game still has two players (whom we still call Helen and Mark), but the rules
are a bit diﬀerent from before.
1. Helen chooses a vector p ∈ Rn and a symmetric n × n matrix Γ; then (after
hearing Helen’s choice) Mark chooses a vector w ∈ Rn .
2

2. Helen pays penalty εp · w + ε2 ⟨Γw, w⟩ − ε2 f (p, Γ).
3. The marker moves from x to x + εw and the clock steps from t to t + ε2 .

8

R.V. Kohn and S. Serfaty

The game continues this way until the final time T , when Helen collects a bonus
φ(x(T )). Her goal is again to maximize her (worst-case) bonus minus accumulated
penalties. Mark does all he can to work against her. Helen’s value function vε (x, t)
now satisfies the dynamic programming principle
"
!
ε2
2
2
(14)
vε (x, t) = max min vε (x + εw, t + ε ) − εp · w − ⟨Γw, w⟩ + ε f (p, Γ)w
p,Γ
2
along with the final-time condition vε (x, T ) = φ(x). To identify (12) as its
Hamilton–Jacobi–Bellman equation (in the limit ε = 0) we proceed as usual: using
Taylor expansion and dropping the subscript ε, (14) gives&v(x, t) ≈ max min v(x, t) + εw · (∇v − p)
w
p,Γ
(15)
'
()
+ ε2 12 ⟨(D2 v − Γ)w, w⟩ + f (p, Γ) + vt .

Helen must choose p = ∇v to neutralize the term that’s linear in ε (otherwise
Mark will choose w to make this term dominant, working against her). She also
needs Γ ≤ D2 v (otherwise Mark can drive ⟨(D2 v − Γ)w, w⟩ to −∞ by a suitablechoice of w). For such p and Γ, the right hand side of (15) reduces to&)max2 v(x, t) + ε2 (f (Dv, Γ) + vt ).
Γ≤D v

The optimal Γ is D2 v, as a consequence of the parabolicity condition (13), leading
as asserted to the formal HJB equation vt + f (Dv, D2 v) = 0.
For the linear heat equation (7) Helen had only to choose α ∈ R. For the
fully nonlinear equation (12) she had to choose both a vector p and a matrix Γ.
Reviewing the arguments, we see why. When the equation is nonlinear, we needseparate proxies for Dv and D2 v. The vector p is a proxy for the former, while
the matrix Γ is a proxy for the latter.
The calculations presented here are of course purely formal. The solution ofa fully nonlinear PDE like (12) need not be smooth, nor even C 1 . The rigorous
analysis uses viscosity-solution methods, showing that the “semi-relaxed limits”
v(x, t) = lim supy→x, s→t,ε→0 vε (y, s)v(x, t) = lim inf y→x, s→t,ε→0 vε (y, s)

are respectively a subsolution and a supersolution of the PDE. If f is such that
the PDE has a comparison principle, then it follows that v = v.
Our two-person game for the linear heat equation was related to hedging in abinomial market. It can thus be viewed as a discrete-time, deterministic versionof the Black-Scholes approach to option pricing. Our game for the fully nonlinear
parabolic equation (12) is, in a similar sense, a discrete-time, deterministic versionof the stochastic representation formula developed in [4].

4. Discussion
The following table encapsulates some well-known connections between PDE’s andapplications. Hamilton–Jacobi equations frequently come from optimal control

9Second-order PDE’s and deterministic games

problems. The linear heat equation is steepest descent for the Dirichlet integral,and motion by curvature is steepest descent for perimeter. The linear heat equationis also linked to Brownian motion, and the value function of a stochastic control
problem solves a nonlinear parabolic PDE.
deterministic
controlstochastic
control

1st order
nonlinear

Hamilton–Jacobi

2nd order
linear***random walk2nd order
nonlinear***

controlled diﬀusion

steepest
descent*|∇u|2

perimeter

Our contribution has been to add two additional connections, corresponding to theasterisks in the table:(1) We have shown that motion by curvature has a deterministic control interpretation; indeed, its level-set representation is roughly speaking the Hamilton–
Jacobi–Bellman equation of a two-person game. Our discussion focused forsimplicity mainly on the motion of convex curves in the plane, but the viewpoint is much more general.
(2) We have shown that many nonlinear PDE’s have deterministic control interpretations. The main requirement is that the PDE have a comparison
principle (and therefore a unique viscosity solution). When restricted to thelinear heat equation, our interpretation is closely connected to the pricing
and hedging of options in a binomial tree market.
These connections are, we think, of intrinsic interest. Perhaps they may also havepractical value. We close with two questions about possible directions for further
work.
• Can our deterministic control interpretations be used to prove new results
about PDE? Here the games in Section 2 seem more promising. In fact, ourpaper [10] includes a modest application of this type: a “waiting-time” result
for motion with velocity κ+ (Theorem 7). The games in Section 3 seem lesspromising, because they are virtually equation-independent. Of course, if thegoal is to derive new PDE results, there is no reason to restrict attention todeterministic games. The recent paper [15] provides a fine example of how
an equation-dependent (but stochastic) control interpretation can be used toderive new results about a nonlinear PDE (namely the “infinity-Laplacian”).

10

R.V. Kohn and S. Serfaty• Can our deterministic control interpretation be the basis of a numerical solution scheme? As noted in Section 2, our interpretation of motion by curvature
is closely connected to the numerical solution schemes for curvature-driven
motion studied in [2, 5, 13, 14]. Concerning Section 3: the dynamic programming principle (14) amounts to a semidiscrete time-stepping scheme for (12).
When the solution is smooth it amounts to explicit Euler, since the optimal
p and Γ are Dv and D2 v respectively. So (14) is a version of explicit Euler
that works even if the solution is not C 1 . Can this time-stepping scheme beapproximated numerically in a spatially discrete setting?
Acknowledgement. Much of Section 2 appeared previously in an article “Parabolic
PDE’s and Deterministic Games,” by Robert V. Kohn, SIAM News 40, no. 8(Oct. 2007).

References[1] Buckdahn, R., Caraliaguet, P., Quincampoix, M., A representation formula for themean curvature motion, SIAM J. Math. Anal. 33 (2001), 827–846.
[2] Catté, F., Dibos, F., Koepfler, G., A morphological scheme for mean curvature motion and applications to anistropic diﬀusion and motion of level sets, SIAM J. Numer.
Anal. 32 (1995), 1895–1909.
[3] Chen, Y.G., Giga, Y., Goto, S., Uniqueness and existence of viscosity solutions ofgeneralized mean curvature flow equations, J. Diﬀ. Geom. 33 (1991), 749–786.
[4] Cheridito, P., Soner, H.M., Touzi, N., Victoir, N., Second-order backward stochastic
diﬀerential equations and fully nonlinear parabolic PDE’s, Comm. Pure Appl. Math.
60 (2006), 1081–1110.
[5] Crandall, M., Lions, P.L., Convergent diﬀerence schemes for nonlinear parabolic
equations and mean curvature motion, Numer. Math. 75 (1996), 17–41.
[6] Evans, L.C., Partial Diﬀerential Equations, American Mathematical Society, 1997.
[7] Evans, L.C., Spruck, J., Motion of level sets by mean curvature I, J. Diﬀ. Geom. 33(1991), 635–681.
[8] Giga, Y., Liu, Q., A billiard-based game interpretation of the Neumann problem forthe curve shortening equation, preprint.
[9] Imbert, C., Serfaty, S., in preparation.
[10] Kohn, R.V., Serfaty, S., (with an appendix by G. Barles and F. Da Lio), A
deterministic-control-based approach to motion by curvature, Comm. Pure Appl.
Math. 59 (2006), 344–407.
[11] Kohn, R.V., Serfaty, S., A deterministic-control-based approach to fully nonlinear
parabolic and elliptic equations, in preparation.
[12] Osher, S., Sethian, J.A., Fronts propagating with curvature-dependent speed – Algorithms based on Hamilton–Jacobi formulations, J. Comp. Phys. 79 (1988), 12–49.
[13] Guichard, F., Thèse, Université de Paris – Dauphine, Paris, 1994.

Second-order PDE’s and deterministic games

11[14] Pasquignon, D., Approximation of viscosity solutions by morphological filters,
ESAIM: Control Optim. and Calc. of Var. 4 (1999), 335–359.
[15] Peres, Y., Schramm, O., Sheﬃeld, S., Wilson, D., Tug of war and the infinity Laplacian, J. Amer. Math. Soc. 22 (1) (2009), 167–210.
[16] Sesum, N., Rate of convergence of the mean curvature flow, Comm. Pure Appl. Math.
61 (2007), 464–485.
[17] Soner, H.M., Touzi, N., A stochastic representation for mean curvature type geometric flows, Ann. Prob. 31 (2003), 1145–1165.
[18] Spencer, J., Balancing games, J. Combinatorial Th., Ser B 23 (1977), 68–74.

Robert V. Kohn, Courant Institute of Mathematical Sciences, 251 Mercer Street, New
York, NY 10012
E-mail: kohn@cims.nyu.edu
Sylvia Serfaty, Courant Institute of Mathematical Sciences, 251 Mercer Street, New
York, NY 10012
E-mail: serfaty@cims.nyu.edu