A Lagrangian Approach to Optimal Lotteries in Non-Convex Economies

We develop a new method to efficiently solve for optimal lotteries in models with non-convexities. To employ a Lagrangian framework, we prove that the value of the saddle point that characterizes the optimal lottery is the same as the value of the dual of the deterministic problem. Our algorithm solves the dual of the deterministic problem via sub-gradient descent. We prove that the optimal lottery can be directly computed from the deterministic optima that are computed along the iterations. We analyze the computational complexity of our algorithm and show that the worst-case complexity is orders of magnitude better than the one arising from a linear programming approach. We apply the method to two canonical problems with private information. First, we solve a principal-agent moral-hazard problem, demonstrating that our approach delivers substantial improvements in speed and scalability over traditional linear programming methods. Second, we study an optimal taxation problem with multidimensional hidden types, which was previously considered computationally challenging, and examine under which conditions the optimal tax schedule will involve lotteries.