Congestion and Penalization in Optimal Transport

Optimal Transport (OT) (Villani,, 2009; Galichon,, 2016) is a mathematical technique that, in recent years, has been integrated into economic theory, particularly in the study of matching markets (Chiappori et al.,, 2010; Galichon,, 2021; Dupuy et al.,, 2019; Carlier et al.,, 2023; Echenique, Federico, Joseph Root and Feddor Sandomirskiy,, 2024). Unlike classical matching models (Gale and Shapley,, 1962; Hylland and Zeckhauser,, 1979; Kelso and Crawford,, 1982; Roth and Sotomayor,, 1990; Abdulkadiroğlu and Sönmez,, 2003; Hatfield and Milgrom,, 2005; Echenique, Federico and M. Bumin, Yenmez,, 2015), OT optimizes over distributions, providing a more flexible and general framework. Starting from the classical model, in which matching costs are represented by a linear function, various extensions have incorporated a regularization term in the objective function to obtain solutions with desirable properties such as sparsity. Notable examples include entropic regularization (Dupuy and Galichon,, 2014; Dupuy et al.,, 2019; Merigot and Thibert,, 2020; Galichon,, 2021) and quadratic regularization (Lorenz et al.,, 2019; González-Sanz and Nutz,, 2024; Wiesel and Xu,, 2024; Nutz,, 2024). Both classical OT and its regularized variants have been widely applied in analyzing matching markets, including marriage markets (Dupuy and Galichon,, 2014), migration dynamics (Carlier et al.,, 2023), labor markets (Dupuy and Galichon,, 2022), and school choice (Echenique, Federico, Joseph Root and Feddor Sandomirskiy,, 2024).

This paper introduces a new model built upon the quadratic regularization framework, similar to Nutz, (2024), but adopting the approach of Izmailov and Solodov, (2023) while introducing heterogeneity in the quadratic term. Our model captures elements absent in classical formulations and better aligns with real-world scenarios. Specifically, by replacing equality constraints with weighted penalization terms, the solution accommodates supply and demand imbalances, a feature particularly relevant in developing countries when modeling matching in education and healthcare markets.

Countries with developing economies often experience significant inefficiencies in education and healthcare due to excess demand, insufficient supply, mismatching, and systemic congestion. These structural issues have contributed to high mortality rates and service deficiencies, as demonstrated during the COVID-19 pandemic. For instance, Johns Hopkins University Coronavirus Resource Center, (2023) indicates that Peru recorded the highest per capita COVID-19 mortality rate globally, exceeding 6,400 deaths per million inhabitants. Similar inefficiencies have been observed across Latin America, where restricted healthcare access exacerbates disparities.

A key factor behind these inefficiencies is that individuals are not properly matched due to physical barriers, bureaucratic issues, and congestion (Anaya-Montes and Gravelle,, 2024; Velásquez,, 2020), compounded by excess demand. In countries such as Peru, India, and Brazil (Kikuchi and Hayashi,, 2020), congestion is particularly severe. For instance, World Bank, (2024) estimates that traffic congestion alone costs Peru 1.8% of its GDP annually. Given these conditions, accounting for congestion and excess demand is crucial when modeling these dynamics.

The model presented in this paper provides a framework for congestion costs while also capturing excess of demand across different institutional contexts. As such, it reflects the realities of many developing countries, contrasting with developed nations such as France or Switzerland, where robust transportation infrastructure, efficient bureaucratic systems, and policies ensure universal access to education and healthcare.

The remainder of this paper is structured as follows. Section 2 defines the fundamental concepts and notation. Section 3 introduces the proposed model and examines its theoretical properties. Section 4 presents illustrative examples that demonstrate the advantages of our approach. Due to data availability constraints, our empirical analysis focuses on the Peruvian health and education sectors. All proofs are provided in the Appendix.

We consider two sets, $X=\{x_{1},\ldots,x_{N}\}$ and $Y=\{y_{1},\ldots,y_{L}\}$. Each element $x_{i}$ $(y_{j})$ represents an individual or a group of individuals/entities that share certain properties and are grouped into the same cluster. For example, in the marriage market (where usually $N=L$), $X$ is the set of men and $Y$ is the set of women. In the case of school matching, $X$ consists of groups of students, grouped, for instance, according to their district, and $Y$ is the set of schools. We denote by $\mu_{i}$ the mass of $x_{i}$ and by $\nu_{j}$ the mass of $y_{j}$. For instance, in the marriage market, $\mu_{i}=\nu_{j}=1$, while in the case of schools, $\nu_{j}$ would represent the capacity of school $j$. Analogously, if $X$ were patients and $Y$ medical care centers, then parameters $\nu_{j}$ would represent the capacity of the medical care center. When referring to an element of $X$, instead of denoting it by $x_{i}$, we usually, to simplify the notation, refer to it by $i$. Analogously, the elements of $Y$ are referred to by the index $j$, instead of $y_{j}$. Moreover, we denote the set of indices $\{1,\ldots,N\}$ by $I$ and the set of indices $\{1,\ldots,L\}$ by $J$. Lastly, we denote by $\pi_{ij}$ the number of individuals of type $i$ matched with $j$.

The problem addressed in the classic literature, from the perspective of a central planner, is to decide how many individuals from group $i$ should be matched with $j\in J$ and so forth for each $i$, minimizing the matching cost¹¹1Matching individuals incurs a cost that is not limited solely to ¡¡physical¿¿ transportation costs, which certainly accounts for both ways (round trip), but also encompasses implicit costs linked to specific characteristics of $i$ and $j$ such as tuition fee, entrance exam, languages, sex, age, etc. This is why we refer to them as matching costs instead of transportation costs., which is given by means of a function $C:\mathbb{R}_{+}^{N,L}\times\mathbb{R}^{P}\to\mathbb{R}$ depending on the matching $\pi=[\pi_{ij}]\in\mathbb{R}_{+}^{N,L}$²²2In this work, we will mostly assume that the number of individuals matched can take values in the real positive line and not only in the positive integers. Note that this is the same issue that arises when one solves the utility maximization problem in the classical framework assuming divisible goods. Later on, we will address again this issue and explain why considering $\pi_{ij}\in\mathbb{R}_{+}$ allows drawing solid conclusions from an economic perspective., and a vector of parameters $\theta\in\mathbb{R}^{P}$. Moreover, the central planner must ensure that there are neither excesses of demand nor supply. Hence, the central planner solves

where

A solution to (1) will be from now referred to as an optimal matching or optimal (transport) plan, and will be denoted by $\pi^{*}$. In the standard optimal transport model, separable linear costs are assumed (Galichon,, 2016). This is, $C(\pi,\theta)=\sum_{i,j}c_{ij}\pi_{ij}$. It is therefore assumed that the marginal cost of matching one more individual from $i$ with $j$ is always the same, regardless of how many people are already matched and independent of any other variable. Hence, the central planner seeks to solve

To solve $\mathcal{P}_{O}$, one typically employs linear programming techniques, such as the simplex method. As discussed in the classical literature, the most general form of the OT problem allows for the existence of infinite types, and in such a case, the optimization is done over continuous distributions. In this paper, however, we are not going to study continuous distributions. What we do focus on, in line with the entropic regularization problem (see, for example, Carlier et al., (2023) and Peyré and Cuturi, (2019)), is working with a variation of the optimization problem in the discrete setting. In the case of entropic regularization (3), the problem addressed is

with $\sigma>0$. Given the strict convexity of $f(x)=x\ln x$, $f(0)=0$ and $\lim_{x\downarrow 0^{+}}f^{\prime}(x)=-\infty$, the solution is interior, i.e. $\pi_{ij}^{*}>0$. Another variation is the quadratic regularization, where the problem becomes

Unlike the problem (3), in the case of (4), interior solutions cannot be guaranteed³³3This is a common feature with our model, it is not straightforward to determine if the solution is interior.. In the model we present in the following section, we build upon the problem (4), making a considerable number of modifications that allow us to adapt to specific economic contexts of countries with structural problems. Before concluding this section, let us briefly note that, by a combinatorial argument, it is possible to conclude that the number of matchings is bounded by $L^{M}$ in the case where $\pi_{ij}\in\mathbb{Z}_{+}$. However, for the case $\pi_{ij}\in\mathbb{R}_{+}$, considering $\mu_{i},\nu_{j}>0$ for all $(i,j)\in I\times J$, the compactness of $\Pi(\mu,\nu)$ and continuity of the objective functions, ensure the existence of a solution to $\mathcal{P}_{O}$ and its variants by Weierstrass Theorem.

In this section, we present the model that we propose, inspired by the optimal transport problem with quadratic regularization, but following the approach of Izmailov and Solodov, (2023). The model is derived from the very characteristics of the observed reality in certain locations. This will be explored in more detail in Section 4.

First, we need to allow the number of individuals of $X$ who belong to $i$ and are matched with $j=1,...,L$, to not necessarily be $\mu_{i}$⁴⁴4We anticipate that $\mu_{i}$ will no longer be the mass of individuals of group $i$ but rather a targeted quota for individuals of group $i$.. Similarly, it may be the case that not all those matched with $j$ sum up to $\nu_{j}$. This model allows for the possibility of excess supply or demand, which is reasonable in some contexts, as we will see. Indeed, underdeveloped countries may not be able to ensure full coverage in education and health, making it more realistic for them to face a trade-off. However, it is natural for the central planner to seek to minimize these excesses: ensuring that children attend school, that schools or hospitals do not become overcrowded, etc.

Mathematically, we model this by replacing the equality constraints defined by $\Pi(\mu,\nu)$ with penalties in the objective function. Moreover, we introduce weights for each penalty. That is, the constraint $\sum_{i=1}^{N}\pi_{ij}=\nu_{j}$ is replaced by the penalty term $\delta_{j}\left[\sum_{i=1}^{N}\pi_{ij}-\nu_{j}\right]^{2}$, with $\delta_{j}>0$, and the constraint $\sum_{j=1}^{L}\pi_{ij}=\mu_{i}$ is replaced by $\epsilon_{i}\left[\sum_{j=1}^{L}\pi_{ij}-\mu_{i}\right]^{2}$, with $\epsilon_{i}>0$. The parameters $\epsilon_{i},\delta_{j}$ are weights. We could use any $p\geq 1$ norm for the penalization. However, the quadratic structure yields mathematical simplifications and fulfills the desired role. Then, by allowing deviations, as we will see in the examples, we better approximate the reality of developing countries that cannot fully ensure that demand perfectly matches supply.

Secondly, as is natural in some environments (see the next section), congestion costs are present. These costs reflect the fact that matching more individuals from $i$ with the same $j$ becomes increasingly costly. For example, from the perspective of physical transportation costs, in countries with high vehicular traffic congestion, the effect of increasing from $x$ cars to $x+1$ passing through a certain avenue is less or equal to increasing from $x+n$ to $x+n+1$ with $n\geq 1$. Therefore, clustering groups based on geographic location means that matching many individuals from the same group to a single $j$ congests the access route (which is the same). Hence, we introduce the term $\sum_{i,j}a_{ij}\pi_{ij}^{2}$ in the cost structure. The coefficient $a_{ij}$ captures heterogeneity⁵⁵5In some situations, the coefficient might be large, but in others—such as cases where there are few schools or hospitals, lightly congested streets, good traffic lights, etc.—the coefficient is small. Moreover, one could question whether adding a car still marginally increases costs when a route is already saturated. However, this effect would only arise when the number of travelers is excessively high relative to the route’s capacity. For simplicity, we omit this case, as modeling a function that is initially quadratic and later constant would overly complicate the analysis when applying first order conditions., while the quadratic term represents the previously described phenomenon⁶⁶6Instead of using $\pi_{ij}^{2}$, we could consider a general strictly increasing and convex function $\psi$, such as $\psi(\pi_{ij})=e^{\pi_{ij}}$ or $\pi_{ij}^{3}$. However, the quadratic structure facilitates quantitative analysis and preserves the consistency of the results and modeling.. Note that quadratic costs are not limited to physical transportation costs but can also represent bureaucratic costs. A hospital receives patients of the same type. As more patients of this type arrive, the system must process a greater number of cases. Since they share the same characteristics, it is assumed that the same computer or system will handle their processing. Given the precarious conditions in developing countries, increasing from $x$ to $x+1$ patients may not significantly affect the system, but increasing from $x+n$ to $x+n+1$ with $n>1$ might (e.g., leading to system freezes, delays, etc.).

Finally, we certainly have $\pi_{ij}\geq 0$, for all $(i,j)\in I\times J$. However, we do not impose upper bounds since we consider a population or universe that is arbitrarily large (a subpopulation of a sufficiently large country)⁷⁷7This considerably simplify our analysis and does not affect the logic of the model.. Hence, the optimization is carried out over the entire space $\mathbb{R}_{+}^{NL}$. This phenomenon also explains the penalties: we no longer assume a fixed number of individuals of type $i$, and $\mu_{i}$ represents now a target that the central planner aims to achieve (how many individuals of type $i$ should ideally be matched). Similarly, the parameters $\nu_{j}$ are also targets of the central planner.

Therefore, following the described scenario, the central planner seeks to minimize costs while taking into account the objective of reaching the targets $\mu_{i}$ and $\nu_{j}$. The tradeoff is controlled through a parameter $\alpha\in[0,1]$. According to what has been specified, the problem is:

where $\epsilon_{1},...,\epsilon_{N}$, $\delta_{1},...,\delta_{L}$ and $\mu_{1},\cdots,\mu_{N}$, $\nu_{1},\cdots,\nu_{L}$ are all non negative, and

In Equation 6, despite its practical relevance, the term $d_{ij}$, representing fixed costs, does not influence the resolution of the problem. For this reason, when considering the parameter vector $\theta_{ij}\in\mathbb{R}^{2}$, we think of it as $(c_{ij},a_{ij})$. Unlike more recent models in the quadratic regularization literature, we allow heterogeneity in the quadratic structure.

Having now established the model, which, to the best of our knowledge, is new in the literature⁸⁸8Quadratic regularization does not involve penalization terms and assumes $a_{ij}=\varepsilon$ for all $(i,j)\in I\times J$. With respect to the classical optimal transport problem, linear costs are considered. On the other hand, entropic regularization involves Inada’s conditions, which do not appear in our model. Finally, in Izmailov and Solodov, (2023), only general results concerning penalization are given and this particular problem is not studied at all., we focus in this section on the following theoretical problems: (i) ensuring the existence of a solution, (ii) analyzing uniqueness, (iii) addressing why optimization in $\mathbb{R}_{+}^{NL}$ is reasonable and why we do not resort to integer optimization, (iv) studying how to compute interior solutions, and (v) analyzing particular cases both from the analytical and numerical perspective. In the next section, we compare our model with previous ones from the literature and highlight its advantages and the new insights it provides.

Therefore, the linear system $A\pi=b$ has a unique solution. What we still don’t know is whether or not this solution belongs to $\mathbb{R}_{++}^{NL}$. If so, given the strict convexity of $F$, we would have determined, through an ex-post analysis, the unique solution to $\mathcal{P}_{CP}$. However, it may not always be the case that $A^{-1}b\in\mathbb{R}_{++}^{NL}$, and it is not a trivial matter to determine. Under specific cases, we will be able to do this. We propose both an analytical and a computational method to solve $A\pi=b$. The analytical method allows us, in special cases, to derive important theoretical conclusions, such as closed-form solutions, bounds, and perform comparative statics. From a computational perspective, we compare our algorithm, which exploits the structure of the matrix $A$, with others for solving linear systems.

This paper introduces a novel framework for analyzing mismatching, congestion effects, and supply-demand imbalances in developing economies matching markets. Our model extends the classical optimal transport framework by incorporating heterogeneous quadratic regularization and penalty terms for deviations from target allocations. Unlike traditional approaches that impose strict equality constraints, our formulation allows for more realistic depictions of inefficiencies, capturing excess demand, underutilization, and the role of heterogenous congestion costs. We have also analyzed the resulting optimization problem in detail, establishing conditions for the existence and uniqueness of solutions. Furthermore, we propose both analytical and computational methods to effectively compute interior solutions. Our approach provides not only theoretical insights but also practical tools for addressing real-world mismatching and congestion issues.

In summary, our model provides considerable flexibility, allowing for heterogeneity in congestion costs, i.e., some $a_{ij}$ could be very small. Removing restrictions enables a better approximation of the reality in developing countries, where equilibrium equations $\Pi(\mu,\nu)$ do not hold uniformly.

Applying our model to Peru’s healthcare sector highlights its ability to explain observed inefficiencies, and provide more flexibility to the central planner when they cannot ensure matching the entire population adequately, which is common in developing or poor countries. The fragmented nature of the public insurance system exacerbates mismatching, leading to suboptimal patient distribution and increased congestion in specific medical centers. Our framework captures these distortions by introducing quadratic congestion costs and penalizing deviations from optimal allocations. Although we have focused on the Peruvian case due to the aforementioned data availability constraints, the model can be applied to centralized matching situations with heterogeneous congestion costs and excess supply and demand.

Future research could extend this framework to dynamic settings, stochastic environments where parameters evolve over time (e.g., Markov Jump Linear Systems, since at different times of the day, traffic is less sensitive to new cars), and empirical validation using real-world matching data. Determining whether the solution is interior in terms of the parameters is not a trivial matter and remains to be explored. Furthermore, exploring policy implications, such as optimal subsidy structures or decentralized decision-making mechanisms, could provide valuable information to address inefficiencies in public service delivery.

Our model aims to provide central planners with a mathematically flexible tool to approximate allocation problems (without restricting solutions to the integer domain), while allowing for imbalances between supply and demand and incorporating congestion costs. This is particularly relevant in contexts where congestion costs are significant and where, unlike in highly developed countries, ensuring universal access to healthcare and education, as well as preventing the saturation of these services, remains a major challenge.