Multi-to one-dimensional screening and semi-discrete optimal transport

Omar Abdul Halim, Brendan Pass · 2025

Read Multi-to one-dimensional screening and semi-discrete optimal transport by Omar Abdul Halim, Brendan Pass (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-2506-21740.txt.

Introduction

Omar Abdul Halim and Brendan Pass solve screening problems with semi-discrete transport tools in a 2025 paper. A monopolist faces consumers varying in many dimensions. The goods on offer vary along just one dimension. Pricing menus must sort buyers without seeing their types.

Solutions often satisfy a simplifying nestedness property. General conditions guaranteeing it are established here. Under nestedness, a general solution method becomes available. Some cases solve in closed form directly. Others need only simple numerical work. Examples illustrate the machinery in action. Both discrete product sets and full continua are treated. The discrete case adds a uniqueness result. Optimal transport theory supplies the mathematical engine. Semi-discrete versions match the one-dimensional goods space. Economic mechanism design gains cleaner characterizations. The results simplify a classically hard problem family.

Catalog record

CREATOROmar Abdul Halim, Brendan Pass
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-21740

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multi-to one-dimensional screening and semi-discrete optimal transport Thanks: The work of OAH was completed in partial fulfillment of the requirements for a doctoral degree in mathematics at the University of Alberta. BP is pleased to acknowledge the support of Natural Sciences and Engineering Research Council of Canada Discovery Grant numbers 04658-2018 and 04864-2024. Omar Abdul Halim, Brendan Pass Abstract . We study the monopolist’s screening problem with a multi-dimensional distribution of consumers and a one-dimensional space of goods. We establish general conditions under which solutions satisfy a structural condition known as nestedness, which greatly simplifies their analysis and characterization. Under these assumptions, we go on to develop a general method to solve the problem, either in closed form or with relatively simple numerical computations, and illustrate it with examples. These results are established both when the monopolist has access to only a discrete subset of the one-dimensional space of products, as well as when the entire continuum is available. In the former case, we also establish a uniqueness result. 1. Introduction The monopolist’s, or principal-agent, problem plays a crucial role in economic theory. Following, for example, Wilson [ 23 ] , the problem can be described as follows (although other interpretations are possible as well): a monopolist sells goods from a set Y to a collection of consumers X . Knowing the cost c(y) to produce each good y\in Y , the preference b(x,y) of each potential consumer x\in X for each good y\in Y and the relative frequency f(x) of consumer types, her goal is to choose which goods to produce, and the prices to charge for them so as to maximize her profits. This nonlinear pricing problem is well understood when both consumer types and goods have only one dimension of heterogeneity, at least under the celebrated Spence-Mirrlees condition on preferences [ 17 , 12 , 18 ] . In contrast, scenarios where consumers and/or goods exhibit multi-dimensional heterogeneity, known as multi-dimensional screening problems in the literature, are much more challenging, and despite considerable efforts and achievements by many authors, are still not well understood. A general result of Carlier ensures existence of an optimal pricing strategy [ 4 ] . Among an expansive literature, we mention a seminal contribution of Rochet-Chone [ 21 ] introducing a complicated general approach to the problem when preferences are linear in types, and proposing a solution to an example where both consumer types and products are two-dimensional. In the process, they discovered the bunching phenomena in which different types choose the same good at optimality. McCann-Zhang [ 15 ] developed delicate duality and free boundary tools, leading to a refinement of the Rochet-Chone solution, while, in another direction, work of Figalli-Kim-McCann [ 9 ] uncovered conditions under which the problem is a concave maximization for general preferences. Noldeke-Samuelson [ 19 ] and McCann-Zhang [ 14 ] have also extended existence and uniqueness results to problems where consumers’ utilities are non-linear in prices. Much of this research exploits, either directly or indirectly, a connection to the mathematical problem of optimal transport (or, equivalently, the economic problem of matching under transferable utility) [ 22 , 10 ] . We focus here on the case where consumer types are multi-dimensional (in fact, two-dimensional in the majority of the paper) but goods are one-dimensional. Such models have already seen a fair bit of attention in the literature [ 7 , 11 , 2 ] , likely because they are the simplest setting in which one can explore the effects of consumers’ multi-dimensional heterogeneity, and, as highlighted by Basov [ 3 ] , it is natural to consider problems where types are higher dimensional than goods, reflecting the high degree of idiosyncrasy in consumers’ tastes. In the simpler setting of optimal transport (OT), the second named author, together with Chiappori and McCann recently developed a condition, known as nestedness , under which the solution to the OT problem between a high dimensional source measure and a one-dimensional target can be characterized in a very simple way, and in fact be solved almost explicitly [ 6 ] . As solutions to the monopolist’s problem indeed solve an optimal transport problem between the distribution \mu=f(x)dx of agents and the distribution \nu of purchased goods at optimality, with surplus given by their preference function b(x,y) , one might hope that nestedness is present in the monopolist’s problem as well, and expect it to greatly simplify the analysis if so. However, checking nestedness is far from straightforward; in the standard OT problem, it depends on the interaction between the two measures \mu and \nu to be matched and the surplus function b . Since in the monopolist’s problem \nu is endogenous , it is not possible to check nestedness directly. The main contribution of this paper is to establish conditions under which solutions to the monopolist’s problem are nested, and to exploit the resulting structure to analyze the solution. We begin by working in a semi-discrete setting, where we only allow a finite number of goods, chosen from the original one-dimensional space of allocations (although, as mentioned below, several results will eventually be translated back to the continuous goods setting). Though problems with a finite allocation space have certainly been considered before, they do not seem to have been explored in our multi-to one-dimensional setting. As a first step, we develop a theory of optimal transport in this setting analogous to [ 6 ] , including a condition (named discrete nestedness) under which the problem can be solved nearly explicitly. This theory is, we believe, of independent interest. Turning back to the monopolist’s problem, the semi-discrete framework has significant technical advantages, as it makes perturbation arguments, commonplace in the mathematical calculus of variations, much simpler. We believe that it also makes the economic interpretation of the nested structure more transparent; in the monopolist’s setting, discrete nestedness essentially means that while a consumer may be indifferent between two goods, they will never be indifferent among three or more. Alternatively, discrete nestedness can be expressed as follows: when faced with an optimal pricing schedule, whenever an agent prefers the i th good to the i+1 -th one, (s)he will necessarily also prefer the j th to the j+1 -th one as well, for all j\geq i . This is an easy consequence of the Spence-Mirrlees condition when types are one-dimensional, but does not hold in general in higher dimensions. We show that, under our conditions, solutions may often be found in closed form, and, when this is not possible, they can be found extremely easily numerically. We also develop a uniqueness result; this is particularly notable, as uniqueness of solutions in multi-dimensional monopolist problems is a fairly delicate issue. Indeed, strict concavity of the problem (a useful tool for establishing uniqueness, if present) requires very strong conditions on b ; in fact, these conditions essentially cannot hold in the unequal dimensional setting we work in [ 20 ] . We also show by an approximation argument that a nested solution to the continuous problem also exists, and closed form solutions can sometimes be obtained by discrete approximations as well. We pause now briefly to discuss the connection between our work and other

Read the complete text