| paper | Two-Sided Matching Meets Fair Division |
| authors | Rupert Freeman, Evi Micha, Nisarg Shah |
| venue | IJCAI 2021 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Both feasibility problems are in \(\mathrm{P}\). Every admissible instance admits a regular pointwise SD-envy-free matching attaining every individual's MMS benchmark, with a compact representation constructible in time polynomial in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given atomless left and right populations with finitely many interchangeable types, rational type masses, degree parameters satisfying \(d_L\ell=d_Rr\), common rankings of counterpart types, and additive utilities consistent with those rankings, construct a compactly represented simple measurable \(d_L\)-/\(d_R\)-regular matching whose every individual bundle satisfies the pointwise SD-DEF1 prefix inequalities on both sides; in the degree-two variant, also require every individual to receive at least their continuous maximin-share value.
A repeated-role high-multiplicity market with type masses \(\mu\) and \(\nu\), integral bundles for each agent, type-edge masses \(X_{ab}\), and a compact decomposition of \(X\) into measure-preserving matching maps or cycles. Fairness is imposed pointwise for almost every individual over prefixes of the common type ranking, not merely on type averages.
The proposed measurable matching relation and compact decomposition lack a formal finite encoding and size guarantee, so the claimed efficient continuous computation is not yet fully specified.
fatal: False
The mirror covers the common-order constructive result in Theorem 2 and the degree-two SD-DEF1-plus-DMMS result in Theorem 8. It leaves the paper's impossibility results, heterogeneous-preference cases, and broader DMMS incompatibility results untreated.
The strongest honest positive case is a narrow Class A mirror. The paper contains no NP-hardness theorem, so the case cannot show discrete hardness dissolving. It can, however, mirror the paper’s constructive fair-matching results in a genuine high-multiplicity regime.
Consider a static, large two-sided market of repeated roles: for example, workers and projects, or students and course sections. There are masses \(\ell\) and \(r\) on the two sides. A left type \(a\) has mass \(\ell\mu_a\), and a right type \(b\) has mass \(r\nu_b\), where the type includes everything relevant to the problem: degree requirement, qualifications, utilities, and preferences over counterpart roles. The number of agents is enormous, while \(\tau_L\) and \(\tau_R\), the numbers of distinct types, are fixed or moderate. Agents of one type are genuinely interchangeable in the high-multiplicity sense.
Let every left agent receive \(d_L\) distinct right-side matches and every right agent receive \(d_R\) distinct left-side matches, with \(\ell d_L=r d_R\). The action is a measurable, simple, biregular matching relation \(\mathcal M\): every individual still receives an integral bundle of \(d_L\) or \(d_R\) actual counterpart agents. Only the population is continuous; the outcome is not a fractional bundle or lottery.
Its finite summary is the type-edge mass \(X_{ab}\), the total mass of matches between left type \(a\) and right type \(b\). It satisfies \(\sum_b X_{ab}=d_L\ell\mu_a\) and \(\sum_a X_{ab}=d_Rr\nu_b\). Crucially, \(X\) alone is not the fairness object: two matchings with the same \(X\) can give different individual bundles. The continuous problem therefore asks for \(X\) together with a compact decomposition into measure-preserving match maps or cycles.
For a left agent \(z\), let \(P\) be a prefix of the right-side roles in \(z\)'s ranking, and write \(\#_{\mathcal M}(z,P)\) for the number of \(z\)'s actual matches lying in \(P\). The natural continuous version of SD-DEF1 requires, for almost every pair \(z,z'\) of left agents and every such prefix \(P\), \(\#_{\mathcal M}(z,P)\geq \#_{\mathcal M}(z',P)-1\), with the symmetric condition on the right. Thus fairness is still pointwise over integral bundles, not merely a statement about type averages.
My lead anchor is Theorem 2, proved in this paper:
“When \(n^\ell d^\ell=n^r d^r\) and both groups of agents have identical ordinal preferences, a complete SD-DEF1 matching always exists and can be computed efficiently.”
The corresponding problem is Continuous Common-Order SD-DEF1 Completion. An instance consists of rational type masses \(\mu,\nu\), total masses \(\ell,r\), balanced degree parameters \(d_L,d_R\), and a common ordinal ranking of right-side roles shared by all left agents and a common ordinal ranking of left-side roles shared by all right agents. The task is to output a compact biregular matching \(\mathcal M\) in which every individual has the required degree and the pointwise continuous SD-DEF1 inequalities hold on both sides.
This is recognisably the same problem. It retains two-sided preferences, complete saturation, indivisible individual matches, and exactly the paper’s fairness guarantee. Only the electorate has been replaced by masses of repeated roles. Rational masses can be expanded into large finite cohorts, while normalized incidence measures of large finite matchings provide the converse direction.
I would expect this mirror to be tractable. The common-order assumption reduces the fairness constraints to prefix-balance conditions. In the atomless setting, cyclic interval matchings or finite cycle decompositions can balance every prefix to within one match, while a transportation calculation determines the type-edge masses. The algorithm is therefore naturally polynomial in the number of types, degree parameters, and input bit length. This is not merely “fractional matching is easy”: the continuous construction must still realize the aggregate plan as actual finite-degree matchings.
A second worthwhile anchor is Theorem 8, also proved here:
“For \(d=2\), a matching satisfying SD-DEF1 and DMMS exists and can be computed efficiently, when agents on both sides have identical preferences.”
Its continuous mirror is Continuous Degree-Two SD-DEF1-plus-DMMS. The input has balanced continuous populations, degree \(d_L=d_R=2\), common ordinal rankings on each side, and additive cardinal utilities consistent with those rankings. The question is to construct a complete \(2\)-regular matching that satisfies pointwise SD-DEF1 and gives every agent at least her continuous maximin share.
For a left type \(a\), the continuous MMS value is \(\sup_{\mathcal N}\operatorname*{ess\,inf}_{z'\in L}\sum_{y\in\mathcal N(z')}u_a(y)\), where \(\mathcal N\) ranges over complete measurable matchings and \(u_a\) is the utility function of type \(a\). The right-side value is defined symmetrically. A solution must meet these thresholds for almost every agent on both sides, not merely in expectation.
I would also expect this restricted problem to be Class A. The degree-two case permits a one-dimensional extreme-pairing or quantile construction: high-ranked and low-ranked counterpart mass is paired in a balanced way, while the two-sided degree constraints are enforced by a cycle decomposition. The paper’s finite reverse-pair construction is precisely the sort of structure that should have an atomless quantile analogue. This question is more substantive than the first because it asks the continuum to preserve both envy-freeness and a maximin guarantee simultaneously.
These mirrors generate useful boundary questions. Does the nonexistence phenomenon behind the paper’s Theorem 3 survive with positive-mass role types? Does exact DMMS remain possible for \(d\geq 3\), or does the finite obstruction survive the continuum? Can a general type-dependent version be reduced to a finite transportation or configuration LP, or can the required integral bundle decomposition itself be continuum-specifically hard? Finally, how much additive error is needed when a continuous solution is rounded to a finite high-multiplicity market?
The weakest point is that the paper’s original rankings are over named agents, whereas a fixed-type continuum necessarily groups agents into interchangeable role classes, usually creating ties within a class. If identity-sensitive strict rankings are essential, then the number of types grows with the population and the high-multiplicity interpretation weakens substantially. Also, the pointwise measurable matching and its compact decomposition are not supplied by the paper; they would need to be proved. If one kept only the matrix \(X\) and imposed fairness on averages, the mirror would be too easy and would no longer faithfully represent the paper.
Subject to that caveat, Theorem 2 gives a credible lead mirror, and Theorem 8 gives a stronger degree-two extension. I would not claim that the mirror covers the paper’s impossibility results or establishes any hardness transfer.
The strongest objection is that neither anchor survives the high-multiplicity test without changing the problem’s fairness object.
Theorem 2 is about a common strict ranking of named counterpart agents. Its round-robin proof exploits that serial order: the \(d\) consecutive individual turns, the coprimality of \(n\) and \(d\), and the resulting exact bundles of named agents. In a genuine finite-type population, repeated counterpart agents are indistinguishable. A type can rank counterpart types, but it cannot strictly rank the individual members of one type without making those members different types. Thus there is a basic fork:
The proposed edge-mass matrix \(X\) does not repair this. It records how much matching occurs between types but not which integral bundles individuals receive, while SD-DEF1 is precisely a constraint on those bundles. A “compact decomposition” into measure-preserving maps would therefore be an additional, nontrivial model and representation theorem, not something supplied by the paper. If the decomposition is made part of the answer, the resulting problem may be interesting, but it is a new continuum graph-realization problem rather than the paper’s computational result transported to high multiplicity.
The same objection applies more sharply to Theorem 8. The paper’s MMS value is defined by partitions into bundles belonging to named other agents, and its impossibility phenomena depend on the combinatorics of those individual bundles. In an atomless model, arbitrary mass can be split among bundle patterns and then realized through measurable maps. That may eliminate the finite obstruction—which would be a worthwhile discovery—but it means the continuous question is studying a different feasibility geometry. If instead one preserves the named bundle patterns closely enough to retain the theorem, the counterpart identities again prevent a genuine fixed-type limit.
These objections do not establish the requested universal negative conclusion. The programme explicitly permits integral bundles, measurable matching relations, and natural mass-level reformulations. A repeated-role market with finitely many worker and project types is a sensible high-multiplicity scenario, and the resulting questions about realizing \(X\) with pointwise fairness are recognisably problems in this paper’s domain. In particular, the degree-two DMMS question could produce a meaningful continuum-specific boundary result.
So the honest verdict is that the negative case is weak. The anchors are not defeated; at most, the proposed mirrors need a precise finite encoding and a careful decision about whether fairness is over named individuals, type classes, or utility levels. The paper therefore does have at least one credible continuous mirror, probably both.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.