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 25, 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.
Halim et al. (Thu,) studied this question.