REVIEW 2 major objections 2 minor
A Lagrangian Approach to Optimal Randomization
T0 review · 2 major / 2 minor · reviewed 2026-05-22 · grok-4.3
Pith's one-line read The saddle-point value for the optimal random solution equals the value of the deterministic dual problem.
desk verdict This paper gives a Lagrangian dual method plus recovery from subgradient iterates that makes optimal randomization computable for multi-dimensional Mirrlees problems where LP was too slow. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The Lagrangian saddle-point formulation whose value for randomized solutions equals the deterministic dual value, from which the optimal lottery is recovered via subgradient iterates.
What would settle it
Take a small non-convex problem whose optimal lottery is already known by exhaustive search; run the subgradient method on its dual and verify whether the randomization recovered from the iterates achieves exactly the same objective value as the known optimum.
Extended reading notes
Core claim
We 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 and show that heterogeneity in productivity and Frisch elasticity can make randomization welfare-improving over the optimal deterministic.
Load-bearing premise
The non-convex problems admit a Lagrangian formulation whose saddle-point value is attained and whose dual can be solved by subgradient descent without the iterates failing to produce a valid randomization recovery.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a Lagrangian framework for non-convex constrained optimization problems in economics where randomization is optimal. It proves that the saddle-point value of the randomized problem equals the value of the deterministic dual problem. The algorithm solves the dual via subgradient descent and recovers the optimal lottery directly from the sequence of deterministic argmax points generated along the iterations. An application to Mirrleesian income taxation with multi-dimensional types (productivity and Frisch elasticity) shows that randomization can be welfare-improving relative to the optimal deterministic schedule.
Significance. If the equivalence result and recovery procedure hold with the stated conditions, the method supplies an efficient computational route to optimal lotteries that is orders of magnitude faster than linear programming for many economic problems. This could make previously intractable multi-dimensional mechanism-design and taxation problems feasible while preserving the ability to characterize when randomization improves welfare.
major comments (2)
- [§4] §4 (Algorithm and recovery procedure): The manuscript states that the optimal random solution is recovered directly from the deterministic optima x_t computed along the subgradient iterations on the dual. However, for non-convex feasible sets, standard subgradient theory guarantees dual convergence but does not automatically ensure that the (possibly set-valued) sequence of x_t yields a feasible lottery in the limit without an explicit ergodic averaging scheme or proof that last-iterate or uniform averaging drives expected constraint violations to zero. This step is load-bearing for the claim that the algorithm produces a valid optimal randomization.
- [Theorem 1] Theorem 1 (saddle-point equivalence): The proof relies on linearity of the Lagrangian in the probability measure, which correctly implies that the randomized sup equals the deterministic sup for fixed λ. The manuscript should explicitly state the compactness or continuity conditions that guarantee attainment of the saddle point when the type space is continuous and the constraint set is non-convex; without these, the equality between randomized saddle value and deterministic dual value may fail to hold.
minor comments (2)
- [§2] The notation for the dual function and subgradient should be introduced with a short table or explicit definition in §2 to improve readability for readers unfamiliar with the specific economic applications.
- [Application section] In the taxation application, the welfare comparison between randomized and deterministic schedules would be strengthened by reporting the magnitude of the welfare gain and the fraction of types that receive a lottery.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments, which will help improve the clarity and rigor of the manuscript. We address each major comment below and plan to incorporate revisions accordingly.
read point-by-point responses
-
Referee: [§4] §4 (Algorithm and recovery procedure): The manuscript states that the optimal random solution is recovered directly from the deterministic optima x_t computed along the subgradient iterations on the dual. However, for non-convex feasible sets, standard subgradient theory guarantees dual convergence but does not automatically ensure that the (possibly set-valued) sequence of x_t yields a feasible lottery in the limit without an explicit ergodic averaging scheme or proof that last-iterate or uniform averaging drives expected constraint violations to zero. This step is load-bearing for the claim that the algorithm produces a valid optimal randomization.
Authors: We agree with the referee that additional justification is needed for the recovery procedure in non-convex settings. While dual convergence holds under standard subgradient assumptions, ensuring the limiting lottery satisfies the constraints in expectation requires care. In the revision we will introduce an explicit ergodic averaging scheme (weighted averages of the deterministic argmax points x_t) and add a supporting proposition showing that expected constraint violations converge to zero under the maintained compactness and continuity conditions. This will be presented in the revised Section 4, preserving the computational advantages while addressing the feasibility concern. revision: yes
-
Referee: [Theorem 1] Theorem 1 (saddle-point equivalence): The proof relies on linearity of the Lagrangian in the probability measure, which correctly implies that the randomized sup equals the deterministic sup for fixed λ. The manuscript should explicitly state the compactness or continuity conditions that guarantee attainment of the saddle point when the type space is continuous and the constraint set is non-convex; without these, the equality between randomized saddle value and deterministic dual value may fail to hold.
Authors: The referee correctly identifies that attainment of the saddle point requires additional regularity when the type space is continuous. In the revised manuscript we will explicitly add the necessary assumptions—compactness of the type space and joint continuity of the objective and constraint functions—to the statement of Theorem 1. We will also include a brief discussion of how these conditions ensure existence of the saddle point via standard arguments from convex analysis, thereby closing the gap noted by the referee. revision: yes
Circularity Check
No significant circularity; derivation uses standard duality
full rationale
The paper's core equivalence between randomized saddle-point value and deterministic dual value is presented as following from the linearity of the Lagrangian with respect to the probability measure, a standard result in convex analysis that does not reduce to any fitted parameter, self-citation chain, or input-by-construction tautology within this work. The subgradient algorithm and recovery procedure are described as direct applications of existing optimization methods without load-bearing self-references or ansatz smuggling. The manuscript is self-contained against external benchmarks for its mathematical claims.
Assumptions & free parameters
assumptions (1)
- domain assumption The non-convex constrained problems admit a Lagrangian whose saddle-point value equals the deterministic dual value.
Cite this review
Pith. "Pith review of A Lagrangian Approach to Optimal Randomization." pith.science (2026). https://pith.science/paper/2504.15997
@misc{pith2026250415997,
author = {Pith},
title = {Pith review of: A Lagrangian Approach to Optimal Randomization},
year = {2026},
howpublished = {\url{https://pith.science/paper/2504.15997}},
note = {Machine review of arXiv:2504.15997}
}
read the original 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.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We prove that the value of the saddle point characterizing the optimal random solution equals the value of the deterministic dual problem... recovers the optimal random solution directly from deterministic optima computed along the iterations.
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 2.3... max_x L(x;λ,γ) = max_{a,c} L(a,c;λ,γ)
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reviewed May 22, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.