Matching with transfers under distributional constraints

Yes, the paper admits a credible continuous mirror. The strongest case is Class A: the paper’s polymatroid matching results become genuinely high-multiplicity problems over masses of worker and firm types. The case is algorithmic rather than hardness-based: the paper contains no new named NP-hardness theorem. The NP-completeness mentioned in related work concerns non-transferable-utility matching and is not an anchor for this paper.

The natural regime is a large standardized labor or housing market. There are many workers but relatively few complete worker types: for example, qualification, location, demographic category, and a common preference/value vector over employer types. There are also many firms or housing providers, but relatively few firm types, each type specifying its values for worker types, capacity, and quota structure. A type therefore includes every parameter used by the model. Agents with idiosyncratic values are different types; they are not silently grouped.

Let \(I\) be worker types and \(J\) firm types. Let \(\mu_i\) be the mass of worker type \(i\), and \(\nu_j\) the mass of firm type \(j\). Let \(a_{ij}\) be the worker-side value and \(c_{ij}\) the firm-side value, with total match surplus \(\alpha_{ij}=a_{ij}+c_{ij}\). For each firm type \(j\), let \(\mathcal H_j\) be an intersecting family of subsets of worker types, and let \(g_j\) be an integer-valued submodular quota function.

The decision variable is \(x_{ij}\), the mass of workers of type \(i\) assigned to firms of type \(j\). It is not a fractional assignment of an individual: it is aggregate mass, and a sufficiently large finite replication can implement rational \(x\) by integral assignments. Feasibility is

\(x_{ij}\ge0\), \(\sum_jx_{ij}\le\mu_i\), and \(\sum_{i\in D}x_{ij}\le\nu_jg_j(D)\) for every \(j\) and \(D\in\mathcal H_j\).

The factor \(\nu_j\) is the required co-modification: quotas scale with the mass of identical firms. The objective is total match surplus \(\sum_{i,j}\alpha_{ij}x_{ij}\).

My lead anchor is Theorem 3, “Linear Programming and Stable Arrangements,” proved in this paper. Its full content is: if, for every firm \(f\), the constraint family \(\mathcal H_f\) is intersecting and the upper quotas are generated by a submodular function \(g_f\), then a stable arrangement exists, and one can compute such an arrangement by linear programming in time polynomial in the number of firms, workers, and constraints. The theorem is proved here, although it relies on the cited polymatroid-intersection theorem. Corollary 1 gives the hierarchical-constraint special case.

The corresponding continuous problem is:

\(\mathrm{HM\text{-}Polymatroid\text{-}Stable}_\infty\). Given \((\mu,\nu,a,c,\{\mathcal H_j,g_j\}_{j\in J})\), find a feasible mass assignment \(x\) and transfers supporting a stable arrangement.

A convenient certificate consists of worker payoffs \(u_i\ge0\) and nonnegative quota prices \(\eta_{jD}\) satisfying \(u_i+\sum_{D\ni i}\eta_{jD}\ge\alpha_{ij}\), together with primal-dual equality between the welfare of \(x\) and \(\sum_i\mu_i u_i+\sum_j\nu_j\sum_{D\in\mathcal H_j}g_j(D)\eta_{jD}\). Define the per-firm-type payoff \(v_j=\sum_Dg_j(D)\eta_{jD}\). For every firm-type mass \(q\le\nu_j\) and every feasible worker bundle \(y\in qP_j\), where \(P_j=\{z\ge0:\sum_{i\in D}z_i\le g_j(D)\}\), the certificate guarantees

\(\sum_i\alpha_{ij}y_i\le\sum_i u_iy_i+qv_j\).

Thus no mass coalition of firms of type \(j\) and workers can make every participant weakly better off and someone strictly better off. On used edges, salaries can be recovered as \(s_{ij}=u_i-a_{ij}\); on unused edges, salaries can be chosen sufficiently low. This is the underlying matching-and-stability problem, not merely an LP encoding of it.

I would expect \(\mathrm{HM\text{-}Polymatroid\text{-}Stable}_\infty\) to be tractable. The LP has \(O(|I||J|)\) assignment variables and one constraint per displayed type-level quota. Its running time is polynomial in \(|I|\), \(|J|\), \(|\mathcal H|\), and the encoding length of the rational masses and values, rather than in the potentially enormous number of individual workers and firms. This is exactly the high-multiplicity gain the programme is looking for.

The mirror is faithful to the paper’s question. It retains transferable utility, many-to-one matching, distributional quotas, total surplus, stable coalition deviations, and the dual construction of salaries. What changes is only the population representation: identical workers and firms are represented by mass, and quotas are interpreted per unit of firm mass. The authors should recognize this as their problem at a larger multiplicity scale, not as an unrelated fractional-allocation problem.

My second, narrower anchor is Theorem 6, “Linear Programming and r-Stable Arrangements,” also proved in the paper. It says that if each constraint family is intersecting and the lower and upper quota functions \(\rho_f\) and \(g_f\) are respectively supermodular and submodular, satisfying \(\rho_f(D)-\rho_f(D\setminus D')\le g_f(D')-g_f(D'\setminus D)\), then an \(r\)-stable arrangement exists and can be computed in polynomial time by linear programming. Here \(r\)-stability requires feasibility and worker individual rationality but does not require firms to receive nonnegative payoff.

The matching continuous problem is:

\(\mathrm{HM\text{-}GenPoly\text{-}rStable}_\infty\). Given the same type masses and values, together with generalized-polymatroid quota data \((\rho_j,g_j)\), find a mass assignment \(x\) satisfying

\(\nu_j\rho_j(D)\le\sum_{i\in D}x_{ij}\le\nu_jg_j(D)\)

for every \(j\) and \(D\in\mathcal H_j\), together with transfers making the arrangement \(r\)-stable. Thus all firm-type mass must satisfy its lower and upper quotas, worker payoffs must be nonnegative, firm payoffs may be negative, and no feasible mass coalition can weakly improve for everyone with one strict improvement.

I would again expect Class A. The generalized-polymatroid intersection structure supplies an integral finite implementation after clearing denominators, while the continuum formulation naturally permits the aggregate masses themselves to be fractional. The question it generates is whether the generalized-polymatroid boundary is sharp: can ordinary stability be recovered under additional conditions, or do lower bounds inherently require \(r\)-stability? A further computational question is whether arbitrary lower-bound families produce continuum-specific hardness once the polymatroid condition is dropped.

This mirror covers Theorem 3, Corollary 1, and Theorem 6. It deliberately does not claim to mirror the paper’s arbitrary one-firm existence theorem or its Proposition 1 non-existence example. Proposition 1 is useful as a boundary: arbitrary upper-quota structures can destroy stable arrangements even with linear preferences, so the positive mirror must preserve the paper’s structural assumptions rather than erase them.

The weakest point is that Theorem 3 already solves a finite LP, so a sceptic may call the continuous version merely an aggregation or rescaling. There is also a substantive modelling choice in replacing constraints over named workers by constraints over worker types. The answer is that this is precisely the high-multiplicity regime: the type includes preferences, values, and quota-relevant attributes, and the mass formulation removes dependence on the number of identical copies. Still, this is a Class A mirror whose contribution is compact population-scale computation and a clean discrete-to-continuous dictionary, not a dramatic new hardness phenomenon.