Technical Summary: A Lagrangian Approach to Optimal Randomization

1. Problem Statement

The paper addresses the computational challenge of solving non-convex constrained optimization problems pervasive in economics, such as contracting under moral hazard, optimal taxation, and fiscal policy. In these environments, deterministic solutions are often difficult to compute because first-order conditions are insufficient to characterize global optima, and they may be suboptimal.

Existing literature establishes that allowing for randomization (or "lotteries") over allocations can improve welfare by relaxing non-convexities. However, the standard approach to computing these optimal lotteries—Linear Programming (LP)—suffers from a severe curse of dimensionality. As the action and consumption spaces grow, the number of variables in the LP formulation (representing probabilities over the joint space of actions and outcomes) increases exponentially, rendering many complex economic models computationally intractable.

2. Methodology

The authors propose a Lagrangian Iteration method that avoids optimizing directly over the high-dimensional probability simplex. Instead, the method solves a sequence of deterministic subproblems and reconstructs the optimal lottery from the history of these solutions.

Theoretical Framework

The core theoretical insight is an equivalence between the lottery problem (primal) and the dual of the deterministic problem.

1. Lagrangian Formulation: The authors define a Lagrangian function for the lottery system in the space of probability measures, $P(A \times C)$.
2. Equivalence of Values: They prove that under Slater's condition, the value of the saddle point of the lottery Lagrangian equals the value of the dual of the deterministic problem. Specifically:
   $$\max_{x \in P(A \times C)} \min_{\lambda, \gamma} L(x; \lambda, \gamma) = \min_{\lambda, \gamma} \max_{a \in A, c \in C} L(a, c; \lambda, \gamma)$$
   This implies that the optimal lottery solution assigns positive probability only to the deterministic allocations that maximize the Lagrangian for the optimal multipliers.
3. Recovery of Randomization: The optimal lottery is not found by solving a high-dimensional LP but is recovered as the weighted empirical distribution of the deterministic optima generated along the iterations of the algorithm.

The Algorithm

The proposed Algorithm 1 proceeds as follows:

1. Initialization: Start with initial Lagrange multipliers $(\lambda^1, \gamma^1)$.
2. Step 1 (Deterministic Maximization): Solve the unconstrained maximization of the Lagrangian in the pure strategy space:
   $$(a^k, c^k) \in \arg\max_{a \in A, c \in C} L(a, c; \lambda^k, \gamma^k)$$
   Crucially, this step exploits economic structure (decomposability and partial concavity) to solve a much simpler problem than the original lottery formulation.
3. Step 2 (Multiplier Update): Update the multipliers using projected sub-gradient descent:
   $$\lambda^{k+1}_i = \max\{\lambda^k_i + \mu_k g_i(a^k, c^k), 0\}$$
   $$\gamma^{k+1}_{j, a^k} = \max\{\gamma^k_{j, a^k} + \mu_k h_j(a^k, c^k), 0\}$$
   Multipliers for actions not selected in the current iteration remain unchanged.
4. Step 3 (Lottery Construction): Construct the approximate lottery solution $x_N$ as a weighted average of the Dirac measures of the iterates:
   $$x_N := \frac{1}{\sum \mu_k} \sum_{k=1}^N \mu_k \delta_{(a^k, c^k)}$$

3. Key Contributions

Theoretical Contributions

• Equivalence Proof: The paper establishes that the optimal value of the lottery problem is identical to the dual value of the deterministic problem, bridging the gap between randomized solutions and standard Lagrangian duality.
• Convergence: The authors prove that under standard conditions on learning rates (step sizes), the sequence of constructed lotteries converges to an $\epsilon$-optimal solution of the original lottery problem.
• Complexity Bounds: They provide worst-case complexity bounds showing that the number of iterations required grows polynomially with the number of constraints, rather than exponentially with the dimension of the action/consumption space.

Computational Contributions

• Exploitation of Structure: The method leverages two key properties common in economic models:
  1. Decomposability: The Lagrangian often separates across agents or states, allowing high-dimensional problems to be broken into smaller, independent subproblems.
  2. Partial Concavity: In many dimensions (e.g., consumption), the Lagrangian is concave or pseudo-concave, allowing the use of first-order conditions (FOCs) rather than grid search. This avoids the need to discretize continuous variables, a major bottleneck for LP.
• Efficiency: The algorithm replaces the optimization over an exponentially large probability simplex with repeated solutions of deterministic subproblems that are often tractable.

4. Results and Applications

Principal-Agent Example

The authors illustrate the method using a textbook moral hazard problem.

• Performance: The Lagrangian iteration method solved the problem in 0.05 seconds for 4,000 iterations, whereas the LP approach took 1.69 seconds.
• Scalability: When the action space was refined (finer grid $\Delta a$), the LP solver failed due to memory limits (exceeding 122,000 variables), while the Lagrangian method remained efficient and required significantly less memory. The method successfully recovered the optimal lottery probabilities (e.g., $\pi(a=0.050) \approx 0.0917$) matching LP results.

Optimal Taxation with Multidimensional Types

The paper applies the method to a Mirrleesian optimal taxation problem with 25 types (combinations of productivity $\omega$ and Frisch elasticity $\eta$) and 600 incentive constraints.

• Feasibility: The problem, which is NP-hard for global constrained optimization, becomes computationally tractable because the Lagrangian decomposes across types.
• Economic Findings:
  • Non-degenerate Randomization: Heterogeneity in productivity and labor supply elasticity naturally leads to optimal randomization.
  • Welfare Gains: Randomization reduces "bunching" (where different types receive identical allocations) and smooths consumption toward the full-information benchmark.
  • Quantitative Impact: In the limit of large labor supply caps, lotteries eliminate approximately 27.23% of the welfare loss caused by asymmetric information. Even with tighter constraints ($a_{max}=1.2$), a relative welfare gain of 3.49% is observed.
  • Mechanism: Lotteries primarily function by introducing rare, high-labor realizations that are disproportionately costly for low-elasticity agents, thereby relaxing incentive constraints without significantly reducing aggregate welfare.

5. Significance and Claims

The paper claims that its method makes previously intractable "lottery problems" feasible for analysis. By decoupling the optimization of the allocation from the enforcement of constraints via Lagrange multipliers, the approach transforms a difficult non-convex problem into a series of simpler deterministic problems.

The authors emphasize that while the worst-case complexity of the underlying maximization step can still be high without economic structure, the standard assumptions in economics (concavity, decomposability) allow the method to outperform Linear Programming by orders of magnitude. This enables the study of complex economic environments with multi-dimensional heterogeneity and non-convexities that were previously beyond computational reach. The method is presented as a general tool applicable to a wide class of planning problems, including dynamic settings with recursive contracts.