A Lagrangian Approach to Optimal Randomization
Authors:
- Chengfeng ShenCSChengfeng Shen
- Felix KublerFKFelix Kubler
- Yucheng YangYYYucheng Yang
- Zhennan ZhouZZZhennan Zhou
Preprint
- 1 June 2026
- preprint
- Published by Elsevier in SSRN Electronic Journal
Abstract
We develop an efficient method for solving non-convex constrained optimization problems that are pervasive in economics. The optimal solution to these problems often involves randomization. We employ a Lagrangian framework and prove that the value of the saddle point characterizing the optimal random solution equals the value of the deterministic dual problem. Our algorithm solves this dual via subgradient descent and recovers the optimal random solution directly from deterministic optima computed along the iterations. For many non-convex economic problems, our method is orders of magnitude faster than linear programming, making previously intractable lottery problems feasible. As an application, we solve for optimal Mirrleesian income taxation with multi-dimensional types. We show that heterogeneity in productivity and Frisch elasticity can make randomization welfare-improving over the optimal deterministic schedule.Keywords
This publication has 24 references indexed in Scilit:
- On the value of randomizationJournal of Economic Theory, 2014
- Dynamic mechanism design with hidden income and hidden actionsJournal of Economic Theory, 2006
- Lotteries, Sunspots, and Incentive ConstraintsJournal of Economic Theory, 2002
- Lagrangian Relaxation2001
- Convergence Rate of Incremental Subgradient Algorithms2001
- A Recursive Formulation for Repeated Agency with History DependenceJournal of Economic Theory, 2000
- Randomization in optimal income tax schedulesJournal of Public Economics, 1995
- Indivisible labor, lotteries and equilibriumJournal of Monetary Economics, 1988
- Optimal coordination mechanisms in generalized principal–agent problemsJournal of Mathematical Economics, 1982
- Subjectivity and correlation in randomized strategiesJournal of Mathematical Economics, 1974