A Lagrangian Approach to Optimal Randomization

Chengfeng Shen, Felix Kübler, Yucheng Yang, Zhennan Zhou · 2025

Read A Lagrangian Approach to Optimal Randomization by Chengfeng Shen, Felix Kübler, Yucheng Yang, Zhennan Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15997.txt.

Introduction

Chengfeng Shen and co-authors present a 2025 method for solving hard optimization problems where the best answer uses randomness. Such non-convex problems are common in economics. Their answers often come as lotteries rather than fixed choices. The team works through a Lagrangian lens.

They prove the saddle point of the random problem equals the value of a plain dual problem. An algorithm descends the dual and rebuilds the random answer from plain optima along the way. For many problems it runs far faster than linear programming. A tax design case with mixed worker types shows the power. Random tax schedules there beat every fixed schedule.

Catalog record

CREATORChengfeng Shen, Felix Kübler, Yucheng Yang, Zhennan Zhou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE160 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15997

Browse the full library · About the Tower of Babel