Two-Sided Matching Meets Fair Division (d4-conf-ijcai-2021-0073)

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 society is given by its support: the list of its \(\tau\) positive-mass types, each mass encoded as a binary rational; \(\tau\) is the support size, not the number of possible types. Write \(\tau=\tau_L+\tau_R\), \(m=\max\{\tau_L,\tau_R\}\), and let \(L\) be the total input bit length.
Realize the populations as disjoint Lebesgue intervals \(X=[0,\ell)\) and \(Y=[0,r)\), partitioned into half-open type intervals of the specified masses; \(\ell,r>0\) are not normalized. Input positive rational degree masses satisfying \(d_L\le r\), \(d_R\le\ell\), and \(d_L\ell=d_Rr\).
Each side has a common linear ranking of counterpart types. Each type has nonnegative binary-rational utility densities over counterpart types, weakly decreasing along that ranking; equal values use the supplied tie order. Utilities of measurable bundles are their density integrals.
A simple matching is a jointly measurable indicator \(W:X\times Y\to\{0,1\}\) with measurable sections \(B_x=\{y:W(x,y)=1\}\) and \(C_y=\{x:W(x,y)=1\}\). Validity means \(\lambda(B_x)\le d_L\) and \(\lambda(C_y)\le d_R\) for every individual; regularity means equality everywhere.
Pointwise SD-DEF1 means \(\lambda(B_x\cap P)\ge\lambda(B_{x'}\cap P)-1\) for all \(x,x'\in X\) and every union \(P\) of an initial segment of ranked right types, with the analogous inequalities for all \(y,y'\in Y\) and left-type prefixes.
For a left type \(a\), define \(\operatorname{MMS}_a=\sup_{V\text{ valid}}\inf_{x'\in X}\int_{B_{x'}^V}u_a(y)\,dy\), allowing all simple measurable valid matchings; define right-type benchmarks symmetrically. In the variant \(d_L=d_R=2\), require every individual's utility to reach their type's benchmark.
A compact output represents \(\{W=1\}\) by a finite Boolean formula of rational affine inequalities in the two population coordinates, including its boundary conventions.

Is feasibility of a regular pointwise SD-DEF1 matching in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard, both generally and with the degree-two MMS requirement? In any tractable case, can a compact matching be constructed in time polynomial in \(m,\tau,L\)?

For finite populations with balanced total degrees and common ordinal rankings on each side, a complete SD-DEF1 matching exists and is computable in polynomial time; the degree-two case also admits simultaneous DMMS [Freeman–Micha–Shah](https://www.rupertfreeman.com/Matching-Fair-Division-Full.pdf).
No result settling exactly the atomless problem specified here was identified in the literature search.

Result

Both feasibility problems are in \(\mathrm{P}\). Every instance satisfying the stated hypotheses admits a regular matching that is pointwise SD-envy-free, and every individual simultaneously attains their type’s MMS benchmark. A compact matching can be constructed in time polynomial in \(m,\tau,L\).

The construction works for arbitrary positive rational degree masses satisfying the hypotheses, including the degree-two variant.

1. A binary band with constant section lengths

Set
\[ p=\frac{d_L}{r}=\frac{d_R}{\ell}. \]
The equality follows from degree balance, and the degree bounds imply \(0<p\le 1\).

For \(s,t\in[0,1)\), define
\[ K_p(s,t)=1 \quad\Longleftrightarrow\quad 0\le s+t<p \ \text{ or }\ 1\le s+t<1+p. \]

Every horizontal and vertical section of this indicator has Lebesgue measure exactly \(p\), including sections at boundary coordinates.

To verify the horizontal assertion, fix \(s\in[0,1)\). If \(s\le p\), the permitted \(t\)-values are
\[ [0,p-s)\ \cup\ [1-s,1), \]
whose total length is \((p-s)+s=p\). Empty intervals at the endpoints cause no difficulty. If \(s>p\), the permitted interval is
\[ [1-s,1+p-s), \]
which lies inside \([0,1)\) and has length \(p\). Symmetry proves the vertical assertion. These calculations also cover \(p=1\).

2. Constructing the matching

Write the supplied left-type intervals as \(I_a=[\alpha_a,\alpha_a+A_a)\), where \(A_a>0\), and the right-type intervals as \(J_b=[\beta_b,\beta_b+B_b)\), where \(B_b>0\). Thus \(\sum_a A_a=\ell\) and \(\sum_b B_b=r\).

On each rectangle \(I_a\times J_b\), define
\[ W(x,y)=K_p\!\left(\frac{x-\alpha_a}{A_a}, \frac{y-\beta_b}{B_b}\right). \]

The half-open partitions assign every individual to exactly one interval. The formula therefore defines \(W\) everywhere on \(X\times Y\).

It is a binary indicator given by finitely many rational affine inequalities. Consequently it is jointly Borel measurable and has measurable sections.

By the section calculation in Section 1 and the change of scale, for every \(x\in X\) and every right type \(b\),
\[ \lambda(B_x\cap J_b)=pB_b. \]
Similarly, for every \(y\in Y\) and every left type \(a\),
\[ \lambda(C_y\cap I_a)=pA_a. \]

Summing over the counterpart types gives
\[ \lambda(B_x)=pr=d_L \quad\text{and}\quad \lambda(C_y)=p\ell=d_R. \]
Thus the matching is regular everywhere.

If \(P\) is any union of right-type intervals, then every left individual receives exactly \(p\lambda(P)\) mass from \(P\). Hence
\[ \lambda(B_x\cap P)=\lambda(B_{x'}\cap P) \]
for all \(x,x'\). The corresponding assertion holds on the right.

In particular, every ranked prefix has identical mass in every bundle on its side. This proves pointwise SD-envy-freeness, and therefore pointwise SD-DEF1. The common-ranking assumption is unnecessary for this construction.

3. Computing the MMS benchmarks exactly

Fix a left type \(a\), with utility density \(u_a\). I claim that
\[ \operatorname{MMS}_a=p\int_Y u_a(y)\,dy. \]

First, let \(V\) be any valid simple measurable matching, and put
\[ U_a^V(x)=\int_Y V(x,y)u_a(y)\,dy. \]
The density is bounded, nonnegative, and measurable because it is constant on finitely many types. The populations have finite measure. Fubini’s theorem therefore applies and yields
\[ \begin{aligned} \frac1\ell\int_X U_a^V(x)\,dx &=\frac1\ell\int_Y u_a(y)\left(\int_X V(x,y)\,dx\right)\,dy\\ &=\frac1\ell\int_Y u_a(y)\lambda(C_y^V)\,dy\\ &\le \frac{d_R}{\ell}\int_Y u_a(y)\,dy\\ &=p\int_Y u_a(y)\,dy. \end{aligned} \]
The inequality uses validity for every \(y\), together with nonnegativity of \(u_a\).

An infimum cannot exceed the average: integrating the pointwise inequality \(U_a^V(x)\ge\inf_{x'\in X}U_a^V(x')\) proves this directly. Hence every valid \(V\) satisfies
\[ \inf_{x'\in X}U_a^V(x') \le p\int_Y u_a(y)\,dy. \]
Taking the supremum over \(V\) gives the claimed upper bound.

For the constructed matching, let \(u_{ab}\) denote type \(a\)’s density on \(J_b\). For every \(x'\in X\),
\[ U_a^W(x') =\sum_b u_{ab}\lambda(B_{x'}\cap J_b) =p\sum_b u_{ab}B_b =p\int_Y u_a(y)\,dy. \]
The matching is valid, so it supplies the reverse inequality in the MMS definition. Thus the claimed equality holds, and its supremum is attained.

Repeating the argument with the sides exchanged gives, for every right type \(b\) with density \(v_b\),
\[ \operatorname{MMS}_b=p\int_X v_b(x)\,dx. \]

Consequently, every individual simultaneously receives utility exactly equal to their type’s benchmark.

In the degree-two variant, balance implies \(\ell=r\), and the bounds imply \(\ell=r\ge2\). Taking \(p=2/\ell\) in the same construction proves feasibility with all required MMS guarantees.

4. Compact representation and polynomial construction

The definition can be written without division in its affine inequalities. For each type pair, set
\[ H_{ab}(x,y)=B_b(x-\alpha_a)+A_a(y-\beta_b). \]
Its matching region is specified by the rectangle bounds
\[ \alpha_a\le x<\alpha_a+A_a, \qquad \beta_b\le y<\beta_b+B_b, \]
together with
\[ 0\le H_{ab}(x,y)<pA_aB_b \quad\text{or}\quad A_aB_b\le H_{ab}(x,y)<(1+p)A_aB_b. \]

Disjoin these formulas over all type pairs. This is precisely the required finite Boolean formula of rational affine inequalities. The displayed strict and non-strict inequalities specify all boundary conventions.

There are \(\tau_L\tau_R\le m^2\) blocks, each containing a constant number of inequalities. All interval endpoints and \(p\) are computed by rational sums and divisions. Their bit lengths are \(O(L)\): a common denominator for a sum can be chosen as the product of its input denominators, whose total bit length is bounded by the input length. The additional coefficients involve only a constant number of products and sums of these rationals, so they also have \(O(L)\) bit length.

The output therefore has \(O(\tau_L\tau_R L)\) bits, and exact rational arithmetic constructs it in polynomial time in \(m,\tau,L\). No expansion into unit-mass individuals is needed.

5. Conclusion

Both decision problems always answer yes on admissible inputs, and both have polynomial-time compact construction algorithms.

The [finite-population results of Freeman–Micha–Shah](https://www.rupertfreeman.com/Matching-Fair-Division-Full.pdf) concern indivisible counterparts. Here, subdivision inside each positive-mass type interval permits the identical type-mass profiles proved above.

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: proved. The output resolves both feasibility problems and establishes polynomial-time construction in the specified compact representation. I found no major or minor mathematical issues.

1. Normalization and section lengths

Degree balance gives \(d_L/r=d_R/\ell\). Positivity and the degree bounds therefore imply \(0<p\le1\), as claimed.

The horizontal-section calculation is correct:

• For \(0\le s\le p\), the two permitted intervals have lengths \(p-s\) and \(s\). They are disjoint, including when \(p=1\), because the first interval excludes its upper endpoint.
• For \(p<s<1\), the permitted interval has length \(p\), and both endpoints lie within the stated domain.

The cases \(s=0\), \(s=p\), and \(p=1\) are covered correctly by the half-open conventions. Symmetry establishes the same result for every vertical section. Thus the section lengths are exact for every coordinate, rather than merely almost everywhere.

2. Definition, measurability, and regularity

All type masses \(A_a\) and \(B_b\) are positive, so the normalized coordinates are well-defined. The half-open partitions assign each population coordinate to exactly one type interval, including internal partition boundaries.

Within each rectangle, the indicator is defined by rational affine inequalities. The finite union is therefore Borel measurable, and its sections are measurable. It is a simple matching in the required sense: its values belong to \(\{0,1\}\).

Scaling the verified section lengths gives, for every individual,
\[ \lambda(B_x\cap J_b)=pB_b, \qquad \lambda(C_y\cap I_a)=pA_a. \]

These are pointwise statements because the band calculation covered every normalized coordinate. Summing over the finite partitions gives degrees \(pr=d_L\) and \(p\ell=d_R\). Regularity holds everywhere.

3. Pointwise SD-DEF1

For any union \(P\) of counterpart-type intervals, finite additivity gives the identical mass \(p\lambda(P)\) in every bundle on the relevant side.

Every ranked prefix is such a union. Consequently, the two quantities compared in each SD-DEF1 inequality are equal, which establishes the required inequality with slack \(1\).

The stronger claim of pointwise SD-envy-freeness is therefore justified. The observation that the construction does not require common rankings is also correct: equality holds separately for every counterpart type.

4. MMS upper bound

For a fixed left type \(a\), the integrand \(V(x,y)u_a(y)\) is measurable, nonnegative, and bounded on a finite-measure domain. It is integrable, so the stated use of Fubini’s theorem is justified.

Validity supplies \(\lambda(C_y^V)\le d_R\) for every \(y\). Nonnegativity of \(u_a\) gives the claimed average-utility bound
\[ \frac{1}{\ell}\int_X U_a^V(x)\,dx \le p\int_Y u_a(y)\,dy. \]

The actual infimum over all individuals cannot exceed this average. This applies to the pointwise infimum in the task, without replacing it by an essential infimum. Utilities are finite and nonnegative, so the infimum and the integration argument are well-defined.

The resulting bound holds for every valid matching \(V\); taking the supremum therefore establishes the claimed MMS upper bound. The argument correctly allows competitors that are valid but not regular.

5. MMS attainment and simultaneous guarantees

For the constructed matching, the constant density on each counterpart type and the pointwise type-mass identities give
\[ U_a^W(x')=p\sum_b u_{ab}B_b =p\int_Y u_a(y)\,dy \]
for every \(x'\in X\).

Thus this valid matching attains the upper bound in the benchmark definition. The equality for \(\operatorname{MMS}_a\), including attainment of its supremum, follows.

Exchanging the sides verifies the right-type benchmark by the same argument. The constructed matching is independent of the utility densities, so these guarantees hold simultaneously for every type and every individual. Zero utility densities cause no exception.

For the degree-two variant, balance gives \(\ell=r\), and the degree bounds give \(\ell=r\ge2\). Hence the stated choice \(p=2/\ell\) lies in the verified range and satisfies every additional requirement.

6. Compact representation and complexity

The affine expression satisfies
\[ \frac{H_{ab}(x,y)}{A_aB_b} =\frac{x-\alpha_a}{A_a}+\frac{y-\beta_b}{B_b}. \]

Because \(A_aB_b>0\), the displayed affine inequalities are equivalent to the original band inequalities. The rectangle constraints and strict versus non-strict inequalities preserve the boundary conventions exactly.

There are \(\tau_L\tau_R\le m^2\) blocks, each with a constant number of affine inequalities.

The bit-length argument is valid. Rational sums forming endpoints and total masses have bit length \(O(L)\); division to obtain \(p\), followed by the constant number of rational operations forming each block’s coefficients, preserves that bound. Expanding the affine expressions also requires only a constant number of operations per block.

Consequently, the stated output-size bound and polynomial-time exact construction follow. The algorithm uses the listed support types and does not expand masses into individual agents.

7. Scope and required clarification

Both general feasibility and degree-two feasibility with simultaneous MMS guarantees are settled on all admissible inputs.

The cited finite-population paper concerns finite agents and binary matching matrices, consistent with the prover’s contextual distinction. Its results are not used to justify the continuous construction. [Freeman–Micha–Shah](https://www.rupertfreeman.com/Matching-Fair-Division-Full.pdf)

Required repairs or additional clarification: none.

⟨structured verdict parsed — rendered above⟩