Semi-discrete multi-to-one dimensional variational problems

University of Alberta, Edmonton, Alberta, Canada

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 13 August 2025
Accepted: 25 March 2026

Abstract

We study a class of semi-discrete variational problems that arise in economic matching and game theory, where agents with continuous attributes are matched to a finite set of outcomes with a one dimensional structure. Such problems appear in applications including Cournot-Nash equilibria, and hedonic pricing, and can be formulated as problems involving optimal transport between spaces of unequal dimensions. In our discrete strategy space setting, we establish analogues of results developed for a continuum of strategies in Nenna and Pass [J. Math. Pures Appl. 139 (2020) 83–108], ensuring solutions have a particularly simple structure under certain conditions. This has important numerical consequences, as it is natural to discretize when numerically computing solutions. We adapt standard semi-discrete optimal transport techniques to the variational setting in which the target measure is unknown. By leveraging discrete nestedness when it holds, our sequential algorithms improve robustness and achieve computational gains, together with rigorous convergence guarantees, as demonstrated through numerical experiments.