You are currently browsing the category archive for the ‘matching with contracts’ category.

In my salad days, school masters would assign boys returning from the summer hols an essay: What I did during the summer’. Yes, masters and boys. I served a portion of my youth in a misbegotten penal colony upon a wind blasted heath’. The only females present were master’s wives, matrons and the French mistress. No, not that kind, the kind that offers instruction in French. As you can see, to the lascivious minds of boys, there was no end to the double entendres. However, I digress.

Over the summer Thanh Nguyen and myself completed a paper about stable matchings. The abstract is reproduced below.

The National Resident Matching program strives for a stable matching of medical students to teaching hospitals. With the presence of couples, stable matchings need not exist. For any student preferences, we show that each instance of a stable matching problem has a nearby’ instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Specifically, given a reported capacity $k_h$ for each hospital $h$, we find a redistribution of the slot capacities $k'_h$ satisfying $|k_h-k'_h|\le 4$ for all hospitals $h$ and $\sum_h k_h\le \sum k'_h \le \sum_h k_h+9$, such that a stable matching exists with respect to $k'$. Our approach is general and applies to other type of complementarities, as well as matchings with side constraints and contracts.

In other words, with the addition of at most 9 additional slots, one can guarantee the existence of a stable matchings. This is independent of the size of the market or doctors preferences (it does assume responsive preferences on the part of hospitals). The key tool  is Scarf’s lemma which is a wonderful device for converting results about cardinal matching problems into results about ordinal matching problems. For more on this, consult the paper by Kiralyi and Pap, who should be credited with a formulation of Scarf’s lemma that makes its usefulness evident.

This is the second posts about stability and equilibrium in trading networks. The first post may be found here. In it I assumed a single homogenous divisble good being traded by agents with quasi-linear preferences. Each agent was associated with a vertex of a graph and the edges represented pairs of agents who were permitted to trade with each other. Furthermore, each agent was designated the role of buyer and seller. Buyers could only trade with sellers and vice-versa. This meant the underlying graph was bipartite. In this post I will drop the assumption that they trade a homogenous good and that it is dvisible.

As noted in the earlier post, when the utility of buyers and the costs of sellers are linear in quantity, total unimodularity of the underlying constraint matrix is sufficient to ensure the existence of Walrasian prices that support an efficient allocation that is integral. If buyer utility functions become concave or sellers’s cost functions become convex, this is no longer true.

Suppose instead that the buyers utility functions are M${^{\#}}$-concave and seller’s cost functions are M${^{\#}}$-convex (object to be defined soon), then, the efficient allocation (the precise formulation will appear below) is indeed integer valued and supporting Walrasian prices exist. The corresponding allocations and prices can be interpreted as stable outcomes which cannot be blocked. This result was established by Murota and Tamura (2001).

I’ll define M${^{\#}}$-concavity. For any integer valued vector ${x}$ in ${\Re^n}$ let ${supp^+(x) = \{i: x_i > 0\}}$ and ${supp^-(x) = \{i : x_i < 0\}}$. A real valued function ${f}$ defined on the integer vectors of ${\Re^n}$ (with non-empty domain) is M${^{\#}}$ -concave if for all ${x, y}$ in its domain and any index ${u \in supp^+(x-y)}$ there exists an index ${v}$ in ${\{0\} \cup supp^{-}(x-y)}$ such that

$\displaystyle f(x) + f(y) \leq f(x - \chi_u + \chi_v) + f(y + \chi_u - \chi_v).$

Here ${\chi_i}$ is the 0-1 vector with a zero in every component except component ${i}$. I describe three different ways one might interpret this notion.

First, one can think of M${^{\#}}$-concavity as trying to capture an essential feature of the basis exchange property of matroids. If you don’t know what a matroid is, skip to the next paragraph. Think of the vectors ${x}$ and ${y}$ as being 0-1 and representing subsets of columns of some given matrix, ${A}$, say. Define ${f(x)}$ to be the rank of the columns in the subset associated with ${x}$. What the definition of M${^{\#}}$-concavity captures is this: for any column, ${u}$ I remove from ${x}$, that is not in ${y}$ and add it to ${y}$, I can find (possibly) a column from ${y}$ (not in ${x}$) to add to ${x}$ and not diminish the sum of the ranks of the two sets. The argument is straightforward.

A second interpretation is to be had by comparing the definition of M${^{\#}}$-concavity to the following way of stating concavity of a function:

$\displaystyle f(x) + f(y) \leq f(x - \frac{x-y}{2}) + f(y + \frac{x-y}{2})$

If ${x}$ and ${y}$ were numbers with ${x > y}$, then, the first term on the right represents a step from ${x}$ closer to ${y}$ and the second term is a step from ${y}$ closer to ${x}$. M${^{\#}}$-concavity can be interpreted as a discrete analogy of this. Think of ${x}$ being above and to the left of ${y}$. A step closer to ${y}$ would means one step down in the ${u}$ direction and a step to the right in the ${v}$ direction., i.e. ${x - \chi_u + \chi_v}$. The vector ${y + \chi_u - \chi_v}$ has a similar interpretation.

The third interpretation comes from an equivalent definition of M${^{\#}}$-concavity, one that shows that it is identical to the notion of gross substitutes proposed by Kelso and Crawford (1982). Let ${p \in \Re^n}$ be a non-negative price vector. Let ${x}$ be a non-negative integer that maximizes ${f(x) - p \cdot x}$, i.e., a utility maximizing bundle. Consider a new price vector ${p' \geq p}$. Then there exists a new utility maximizing bundle ${y}$ such that ${y_i \geq x_i}$ for all ${i}$ such that ${p_i = q_i}$. In words, the demand for goods whose price did not change cannot go down.

The key result of Murota and Tamura is that the following linear program has an integer optimal solution when the ${U_i}$‘s are M${^{\#}}$-concave and the ${C_j}$‘s are M${^{\#}}$-convex.

$\displaystyle \max \sum_{i \in B}U_i(x_{ij}:\{j: (i,j) \in E\}) - \sum_{j \in S}C_j(x_{ij}: \{i:(i,j) \in E\})$

subject to

$\displaystyle 0 \leq x_{ij} \leq d_{ij}\,\, \forall (i,j) \in E$

Notice, that buyer’s utilities do not necessarily depend on the total amount consumed. They can depend on the vector of inflows from the various sellers (similarly for the sellers). We can interpret this to mean that the sellers sell different goods which are substitutes for each other and there is an upper limit, ${d_{ij}}$ on the amount of seller ${j}$‘s good that can go to seller ${i}$. Such a bound is necessary to make sure the problem is well defined. Consider the case when utilities and costs are linear in quantity. The problem could be unbounded then. A second interpretation is that seller’s sell the same good but under different contractual terms (payment plan, delivery date etc.) which make them, in the buyer’s eyes, imperfect substitutes. The only element of the contract not fixed is the price and that is what is determined in equilibrium.

This is the first of a series of posts about stability and equilibrium in trading networks. I will review and recall established results from network flows and point out how they immediately yield results about equilibria, stability and the core of matching markets with quasi-linear utility. It presumes familiarity with optimization and the recent spate of papers on matchings with contracts.

The simplest trading network one might imagine would involve buyers (${B}$) and sellers (${S}$) of a homogenous good and a set of edges ${E}$ between them. No edges between sellers and no edges between buyers. The absence of an edge in ${E}$ linking ${i \in B}$ and ${j \in S}$ means that ${i}$ and ${j}$ cannot trade directly. Suppose buyer ${i \in B}$ has a constant marginal value of ${v_i}$ upto some amount ${d_i}$ and zero thereafter. Seller ${j \in S}$ has a constant marginal cost of ${c_j}$ upto some capacity ${s_j}$ and infinity thereafter.

Under the quasi-linear assumption, the problem of finding the efficient set of trades to execute can be formulated as a linear program. Let ${x_{ij}}$ for ${(i,j) \in E}$ denote the amount of the good purchased by buyer ${i \in B}$ from seller ${j \in S}$. Then, the following program identifies the efficient allocation:

$\displaystyle \max \sum_{(i,j) \in E} (v_i - c_j)x_{ij}$

subject to

$\displaystyle \sum_{j \in S: (i,j) \in E}x_{ij} \leq d_i\,\, \forall i \in B$

$\displaystyle \sum_{i \in B:(i,j) \in E}x_{ij} \leq s_j\,\, \forall j \in S$

$\displaystyle x_{ij} \geq 0\,\, (i,j) \in E$

This is, of course, an instance of the (discrete) transportation problem. The general version of the transportation problem can be obtained by replacing each coefficient of the objective function by arbitrary numbers ${w_{ij}}$. This version of the transportation problem is credited to the mathematician F. J. Hitchcock and published in 1941. Hitchcock’s most famous student is Claude Shannon.

The continuous’ version of the transportation problem was formulated by Gaspard Monge and described in his 1781 paper on the subject. His problem was to split two equally large volumes (representing the initial location and the final location of the earth to be shipped) into infinitely many small particles and then match them with each other so that the sum of the products of the lengths of the paths used by the particles and the volume of the particles is minimized. The ${w_{ij}}$‘s in Monge’s problem have a property since called the Monge property, that is the same as submodularity/supermodularity. This paper describes the property and some of its algorithmic implications. Monge’s formulation was subsequently picked up by Kantorovich and the study of it blossomed into the specialty now called optimal transport with applications to PDEs and concentration of measure. That is not the thread I will follow here.

Returning to the Hitchcock, or rather discrete, formulation of the transportation problem let ${p_j}$ be the dual variables associated with the first set of constraints (the supply side) and ${\lambda_i}$ the dual variables associated with the second or demand set of constraints. The dual is

$\displaystyle \min \sum_{j \in S} s_jp_j + \sum_{i \in B}d_i\lambda_i$

subject to

$\displaystyle p_j + \lambda_i \geq [v_i-c_j]\,\, \forall (i,j) \in E$

$\displaystyle p_j, \lambda_i \geq 0\,\, \forall j \in S, i \in B$

We can interpret ${p_j}$ as the unit price of the good sourced from seller ${j}$ and ${\lambda_i}$ as the surplus that buyer ${i}$ will enjoy at prices ${\{p_j\}_{j \in S}}$. Three things are immediate from the duality theorem, complementary slackness and dual feasibility.

1. If ${x^*}$ is a solution to the primal and ${(p^*, \lambda^*)}$ an optimal solution to the dual, then, the pair ${(x^*, p^*)}$ form a Walrasian equilibrium.
2. The set of optimal dual prices, i.e., Walrasian prices live in a lattice.
3. The dual is a (compact) representation of the TU (transferable utility) core of the co-operative game associated with this economy.
4. Suppose the only bilateral contracts we allow between buyer ${i}$ and seller ${j}$ are when ${(i,j) \in E}$. Furthermore, a contract can specify only a quantity to be shipped and price to be paid. Then, we can interpret the set of optimal primal and dual solutions to be the set of contracts that cannot be blocked (suitably defined) by any buyer seller pair ${(i,j) \in E}$.
5. Because the constraint matrix of the transportation problem is totally unimodular, the previous statements hold even if the goods are indivisible.

As these are standard, I will not reprove them here. Note also, that none of these conclusions depend upon the particular form of the coefficients in the objective function of the primal. We could replace ${[v_i - c_j]}$ by ${w_{ij}}$ where we interpret ${w_{ij}}$ to be the joint gain gains from trade (per unit) to be shared by buyer ${i}$ and seller ${j}$.

Now, suppose we replace constant marginal values by increasing concave utility functions, ${\{U_i(\cdot)\}_{i \in B}}$ and constant marginal costs by ${\{C_j (\cdot)\}_{j \in S}}$? The problem of finding the efficient allocation becomes:

$\displaystyle \max \sum_{i \in B}U_i(\sum_{j: (i,j) \in E}x_{ij}) - \sum_{j \in S}C_j(\sum_{i: (i,j) \in E}x_{ij})$

subject to

$\displaystyle \sum_{j \in S: (i,j) \in E}x_{ij} \leq d_i\,\, \forall i \in B$

$\displaystyle \sum_{i \in B:(i,j) \in E}x_{ij} \leq s_j\,\, \forall j \in S$

$\displaystyle x_{ij} \geq 0\,\, (i,j) \in E$

This is an instance of a concave flow problem. The Kuhn-Tucker-Karush conditions yield the following:

1. If ${x^*}$ is a solution to the primal and ${(p^*, \lambda^*)}$ an optimal Lagrangean, then, the pair ${(x^*, p^*)}$ form a Walrasian equilibrium.
2. The set of optimal Lagrange prices, i.e., Walrasian prices live in a lattice.
3. Suppose the only bilateral contracts we allow between buyer ${i}$ and seller ${j}$ are when ${(i,j) \in E}$. Furthermore, a contract can specify only a quantity to be shipped and price to be paid. Then, we can interpret the set of optimal primal and dual solutions to be the set of contracts that cannot be blocked (suitably defined) by any buyer seller pair ${(i,j) \in E}$.

Notice, we lose the extension to indivisibility. As the objective function in the primal is now concave, an optimal solution to the primal may occur in the interior of the feasible region rather than at an extreme point. To recover integrality’ we need to impose a stronger condition on ${\{U_i\}_{i \in B}}$ and ${\{C_j\}_{j \in S}}$, specifically, they be ${M}$-concave and convex respectively. This is a condition tied closely to the gross substitutes condition. More on this in a subsequent post.