d4-journals-geb-2022-0054

The strongest mirror is a large matching market or cooperative in which millions of people fall into a few profile types: for example, workers with the same qualifications, location, and availability, where compatibility and surplus depend only on the two types. A type is that complete profile; its mass \(\mu_t\) is the fraction of the population with that profile. The regime is \(n\gg\tau\), with many agents but relatively few types. A coalition is any measurable subpopulation. This keeps the paper’s central question intact: how should transferable profit be divided when coalitions can secede and form their own matches?

The anchor is Theorem 14, proved in the paper. It states that the allocation \(c\) produced by Mechanism 13 is in the \(2/3\)-approximate core of any general graph matching game: its total allocation is at most the worth of the grand coalition, and every coalition receives at least \(2/3\) of the worth it could generate by matching internally. The mechanism starts from an optimal half-integral matching and cover; it scales the cover payments for vertices on a half-integral odd cycle of length \(2k+1\) by \(2k/(2k+1)\), and leaves other payments unchanged. The theorem is a constructive approximation guarantee, though it does not state a formal running-time bound; the construction uses standard efficient matching routines. The paper offers no hardness result to anchor on.

Here is a continuous problem in the same cooperative matching model. Call it Continuous Matching Core Computation. An instance is a finite type set \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), and a graph of compatible type pairs with nonnegative rational surpluses \(w_e\). Include a loop at \(t\) when two distinct agents of type \(t\) may match. For any coalition described by masses \(0\le q_t\le\mu_t\), define its worth \(P(q)\) as the maximum of \(\sum_e w_e x_e\), subject to each type’s mass being used at most once: a cross-type match of mass \(x_{st}\) uses \(x_{st}\) from each type, and a within-type match of mass \(x_{tt}\) uses \(2x_{tt}\).

The problem is to find the largest \(\alpha\in[0,1]\) and nonnegative per-agent type payments \(c_t\) such that \(\sum_t\mu_t c_t\le P(\mu)\) and, for every coalition \(q\), \(\sum_tq_tc_t\ge\alpha P(q)\). A solution is the pair \((\alpha,c)\), with these guarantees. Individuals still receive whole matches or remain unmatched; fractional values describe how a nonatomic mass of otherwise identical agents is divided among partner types.

I expect this problem to be tractable, with \(\alpha=1\). Solve the dual cover LP: minimize \(\sum_t\mu_tc_t\), subject to \(c_s+c_t\ge w_{st}\) for each cross-type edge, \(2c_t\ge w_{tt}\) for each loop, and \(c_t\ge0\). By LP duality its optimum is \(P(\mu)\). The resulting cover also bounds every smaller coalition’s worth: \(\sum_tq_tc_t\ge P(q)\) for all \(q\le\mu\). With \(\tau\) types, this is an explicit LP with at most \(O(\tau^2)\) edge constraints, so it is polynomial in \(\tau\) and the input bit length.

This is a co-modification of the population, not a switch to continuous outcomes. The paper’s finite matching game can have an integrality gap on odd cycles; with nonatomic type masses, the portions of each type can be paired across the needed type pairs while each individual still has one partner at most. Thus the \(2/3\) guarantee of Theorem 14 becomes an exact core guarantee in this regime. The authors should recognize the mirror: it retains the same matching worth, transferable utility, coalition secession, and profit allocation, while the continuum changes the feasible aggregate matching patterns.

The weak point is the regime restriction. An arbitrary graph with idiosyncratic compatibility or pair-specific surplus may require almost as many types as agents, so this mirror would not cover it efficiently. Its case rests on a plausible class of high-multiplicity instances where agents with the same profile are interchangeable. Further questions include how quickly finite high-multiplicity markets approach the continuous core, what additive error is needed when rounding back to a finite electorate, and how the guarantee changes when transfers are restricted.