# Optimal Stopping Problem for Uniswap V3

This notes explore the optimal stopping problem for *liquidity providers (LPs)* within the context of *decentralized finance (DeFi)* and *automated market makers (AMMs)*, with a specific focus on *Uniswap v3*.

* DeFi has emerged as a transformative force in finance, leveraging blockchain technology to offer decentralized alternatives to traditional financial services.
* AMMs are a critical component of DeFi, enabling the trading of digital assets without the need for traditional order books.
* Uniswap v3 introduces the innovative concept of *concentrated liquidity*, allowing LPs to allocate their capital within specific price ranges, thereby enhancing capital efficiency.

However, this also introduces complexities in determining the optimal time for LPs to withdraw their liquidity. This study aims to determine the optimal time to withdraw liquidity to maximize profits, considering crucial factors such as market volatility, price movements, and accumulated fees. Understanding these dynamics is essential for LPs to make informed decisions and optimize their returns in the dynamic DeFi ecosystem.

## Uniswap v3 Dynamics
Uniswap v3 introduces the novel concept of *concentrated liquidity*, enabling LPs to allocate capital to a specific price range $[p_l, p_r]$. This contrasts with previous versions, where liquidity was distributed uniformly along the entire bonding curve. Concentrated liquidity allows LPs to increase capital efficiency and potentially earn higher fees within their chosen range. However, it also exposes them to increased risk if the price moves outside their active interval.

As shown in the graph, LPs can concentrate their liquidity within a specific price range (shaded area). This allows for greater capital efficiency compared to previous versions (dotted line), in which liquidity was spread across the entire bonding curve.


### Dynamics of Token Holdings
An LP's token holdings in a Uniswap v3 pool are dynamic, changing with price fluctuations within their defined range. Let $x$ and $y$ represent the quantities of token 0 and token 1 held by the LP, respectively. These quantities are functions of the current price $P$ and the chosen price range:

\begin{split}
x(p) &= L\left\{ \left(\frac1{\sqrt p} - \frac1{\sqrt{p_r}} \right)^+ - \left(\frac1{\sqrt p} - \frac1{\sqrt{p_l}} \right)^+ \right\} \\
y(p) &= L\left\{ \left(\sqrt p - \sqrt{p_l} \right)^+ - \left(\sqrt p - \sqrt{p_r} \right)^+ \right\}
\end{split}

where $L$ is the liquidity level.

### Imperminant Loss
Recall that **Impermanent Loss (IL)** (or *divergent loss*) for a Liquidity Provider (LP) is defined as the opportunity cost, which is the loss incurred by providing liquidity compared to simply holding the underlying assets.

The Impermanent Loss at a future pool price $P_1$, given the entry price $P_0$ and liquidity $L$, can be expressed as:

$$
{\rm IL}(P_1|P_0, L)
:= \ \left(x(P_0)P_1 + y(P_0)\right) - \left(x(P_1)P_1 + y(P_1)\right)
$$

## Modelling Fee Income via Local Time
As trading activity occurs, LPs earn fees in two tokens, which are proportional to the trading volume within their active range.

The rationale for **modeling** the fee flow $\text{Fee}_t$ using *Local Time* stems from the mechanism of AMMs. An LP earns a transaction fee every time a trade moves the pool price.

* Consider an extreme case where an LP's liquidity profile is a Dirac delta function at price $q_0$, scaled by a constant $C$ (i.e., $L(q) = C \delta(q-q_0)$). In this scenario, the LP essentially collects a transaction fee, $\gamma C q_0$, whenever the price \textit{crosses} $q_0$.
* For standard diffusion models of the price process $P_t$, the number of times the price crosses a specific level $q_0$ within a finite time interval $[0, T]$ is *infinite*. This makes simple counting impossible.
* To define the fee collected, we utilize *Local Time*, $\mathcal{L}_T^{q}$, which measures the **density of occupation time** at a given level. The local time of a continuous semimartingale $P_t$ at level $q$ is formally defined by: $$\mathcal{L}_t^q = \lim_{\epsilon\to0^+}\frac{1}{2\epsilon} \int_0^T \mathbf{1}_{(q-\epsilon, q+\epsilon)}(P_t)d\langle P \rangle_t$$

### Dimensionally Consistent Fee Model
A dimensionally consistent fee model requires the fee density $\text{fee}_T(q)$ to be the product of liquidity, fee rate, and price movement density. Specifically, the instantaneous fee density at price $q$ should be proportional to the liquidity provided at that price, $L(q)$, and the density of price movement, $\mathcal{L}_T^q$. The total fee collected within $[0, T]$ is obtained by integrating this fee density over all possible prices:

$$
{\rm Fee}_T = \gamma \int_{p_r}^{p_l} L \mathcal{L}_T^q(P) dq,
$$

where $\gamma$ is the fee coefficient.

## Optimal Stopping Problem

### Problem Formulation
The optimal dynamic strategy for an LP can be **modeled** as an optimal stopping problem where the decision is whether to remain in the pool (collecting fees) or exit (realizing the current IL payoff). We consider a problem inspired by Capponi-Zhu, where the LP seeks an optimal stopping rule $\tau$ to maximize the expected value $v(p)$.

The value function $v(p)$ is defined as the supremum of the expected discounted net terminal payoff:

$$
v(p):=\sup_{\tau} \mathbb{E}^{{\mathbb Q}}\left[\left. -e^{-r\tau} {\rm IL}(P_\tau|P_0) + \int_0^\tau e^{-rt} d(\text{Fee}_t) \right|P_0 = p\right].
$$

Here, the first term represents the discounted loss realized upon exit at time $\tau$. The integral term $\int_0^\tau e^{-rt} d(\text{Fee}_t)$ represents the discounted fees collected from liquidity provision up to the exit time $\tau$.

By applying the *Occupation Time Formula* (which equates the integral of a function with respect to local time to an integral with respect to time and quadratic variation), the time integral in the optimal stopping problem can be simplified:

$$
\int_0^\tau e^{-rt} d(\text{Fee}_t) = \gamma \int_0^\tau e^{-rt} L \pmb{1}_{[p_l,p_r]} d\langle P \rangle_t.
$$

This final form provides the instantaneous fee collection flow required for the HJB equation, ensuring the collected fees are directly proportional to the liquidity profile $L$ and the rate of quadratic variation $d\langle P \rangle_t$.

### Hamilton-Jacobi-Bellman (HJB) Equation
Assume the price $P_t$ follows the risk-neutral SDE:

$$
\frac{dP_t}{P_t} = (r-\delta) dt + \sigma(P_t) dW_t.
$$

where $r$ is the risk-free rate and $\delta$ is the **dividend yield (or convenience yield)** on the asset, often representing a staking rate or loan rate in the DeFi context.

The value function $v(p)$ satisfies the HJB variational inequality in the continuation region $\{p: v(p) > -{\rm IL}(p|P_0, L)\}$. The HJB variational inequality is given by:

$$
\max\left\{\mathcal{A}v(p) + \gamma L \pmb{1}_{[p_l,p_r]}(p) p^2 \sigma^2(p) - rv(p), \ -{\rm IL}(p|P_0) - v(p)\right\} = 0.
$$

Here, $\mathcal A$ is the infinitesimal generator

$$
\mathcal{A}v(p) = (r-\delta)p v'(p) + \frac{1}{2} p^2\sigma^2(p) v''(p),
$$

and the second term is the instantaneous rate of fee collection:

$$
\mathbb{E}\left[ d(\text{Fee}_t) \right] = \mathbb{E}\left[ \gamma L \pmb{1}_{[p_l,p_r]}(p) d\langle P \rangle_t \right] = \gamma \pmb{1}_{[p_l,p_r]}(p) p^2 \sigma^2(p).
$$

For the special case of the *Black-Scholes model* where $\sigma$ is a constant, this simplifies substantially, making the problem tractable.

## Numerical Scheme: Fixed-Point Iteration
The optimal stopping problem for the Perpetual American Option model is characterized by the time-independent HJB Variational Inequality (VI) for the value function $v(p)$:

$$
\max\left\{\mathcal{A}v(p) + R(p) - rv(p), \ G(p) - v(p)\right\} = 0.
$$

where $R(p) = \gamma \pmb{1}_{[p_l,p_r]}(p) p^2 \sigma^2(p)$ is the instantaneous fee collection rate, and $G(p) = -{\rm IL}(p|P_0)$ is the stopping payoff function. Since this is a time-independent (perpetual) problem, the solution $v(p)$ is the steady-state solution, which is typically found using a **fixed-point iteration** scheme.

### Discretization and Fixed-Point Method
We discretize the price variable $P$ on a computational domain $[\underline{P}, \overline{P}]$.

* **Price Grid:** We define a uniform grid $p_i$ for $i = 1, \ldots, N_P$. The boundaries must be set far enough from the expected optimal stopping boundary to minimize boundary effects.
* **Differential Operator $\mathcal{A}$:** The infinitesimal generator $\mathcal{A}v(p)$ is discretized using *second-order central differences* for the second derivative $v''(p)$ and a combination of central or upwind/downwind differences for the first derivative $v'(p)$, depending on the sign of the drift term $(r-\delta)p$. The VI is solved by finding a fixed point of the operator $T(v)$: $$v = T(v) \quad \text{where} \quad T(v) = \max \left\{ \mathcal{C}(v), G \right\} $$ where $\mathcal{C}(v)$ is the continuation value derived from the PDE component ($\mathcal{A}v(p) + R(p) - rv(p) = 0$).

### Backward Relaxation (Iterative Fixed-Point)
Since the HJB VI is an elliptic PDE with an obstacle (the stopping payoff $G(p)$), we can solve it numerically by iteratively applying the linear operator (the continuation value) and the non-linear constraint (the maximum operator). This approach is known as the *Policy Iteration* or *Successive Over-Relaxation (SOR) method*.

#### 1\. Discretizing the Continuation Value
The continuation value $\mathcal{C}(v)$ is the solution to the steady-state PDE:

$$
\mathcal{A}v(p) - rv(p) = -R(p)
$$

Discretizing this linear elliptic PDE yields a system of algebraic equations for the vector of unknown values $\mathbf{v}$:

$$
\mathbf{A}\mathbf{v} = -\mathbf{R}
$$

where $\mathbf{A}$ is a sparse matrix resulting from the finite difference scheme for the operator $\mathcal{A} - rI$, and $\mathbf{R}$ is the vector of instantaneous fee rates $R(p_i)$.

#### 2\. The Numerical Algorithm
The algorithm proceeds via an iterative scheme until the difference between successive approximations of the value function falls below a tolerance $\epsilon$.

1. *Initial Guess:* Set the initial guess for the value function $\mathbf{v}^{(0)}$ to the stopping payoff: $\mathbf{v}^{(0)} = \mathbf{G}$.
2. *Iterative Fixed-Point Loop ($k=0, 1, 2, \ldots$):*
* *Continuation Step:* Compute the continuation value $\mathcal{C}(\mathbf{v}^{(k)})$ by solving the linear system $\mathbf{A}\mathbf{v} = -\mathbf{R}$.
* Since $\mathbf{A}$ is time-independent, this system can be solved efficiently (e.g., using sparse matrix inversion or LU decomposition) to find the solution vector $\mathbf{C}^{(k)}$.
* *Stopping Constraint:* Update the value function approximation by applying the $\max$ operator: $$ \mathbf{v}^{(k+1)} = \max \left\{ \mathbf{C}^{(k)}, \mathbf{G} \right\}$$
* *Convergence Check:* If $\left\| \mathbf{v}^{(k+1)} - \mathbf{v}^{(k)} \right\| < \epsilon$, stop.
3. *Output:* The final grid $\mathbf{v}^*$ gives the value function, and the optimal stopping boundary is implicitly defined by the set of grid points where $\mathbf{v}^* = \mathbf{G}$.

### Pseudocode (Fixed-Point Iteration)

FUNCTION Solve_Perpetual_HJB_VI(P_grid, R_grid, G_grid, A_matrix, tolerance):
    """
    Solves the 2D Perpetual HJB Variational Inequality using a fixed-point iteration.

    Inputs:
        P_grid (array): Discretized price grid.
        R_grid (array): Vector of instantaneous fee rates R(p_i).
        G_grid (array): Vector of stopping payoff G(p_i) = -IL(p_i).
        A_matrix (matrix): Sparse matrix representation of the operator (A - rI).
        tolerance (float): Convergence criterion.

    Outputs:
        v_star (array): The converged Value Function v(p).
        Stopping_Boundary (array): Set of prices where v_star = G_grid.
    """

    # 1. Setup
    v_old = G_grid                      # Initial guess (Policy: always stop)
    RHS = -R_grid                       # Right Hand Side of the linear system

    # 2. Pre-calculate/factorize the A_matrix for efficiency (since it's constant)
    A_factorized = factorize(A_matrix)

    # 3. Iterative Fixed-Point Loop
    while (v_old not converged):
        v_current = v_old
        
        # A. Continuation Step (Solve the linear system for C = A^{-1} * RHS)
        # Note: In practice, R is sometimes moved to the LHS of the VI, 
        # but here we solve the PDE: Av - rv = -R
        C_new = solve(A_factorized, RHS)
        
        # B. Stopping Constraint
        v_new = max(C_new, G_grid) 
        
        # C. Convergence Check
        if norm(v_new - v_current) < tolerance:
            break
            
        v_old = v_new
        
    v_star = v_new

    # Output: The optimal stopping boundary is the set of points where the constraint is binding.
    Stopping_Boundary = find_indices(v_star == G_grid) 
    
    return v_star, Stopping_Boundary

## References
* Capponi, A., & Zhu, B. (2025). Optimal exiting for liquidity provision in constant function market makers. http://dx.doi.org/10.2139/ssrn.5148585