Answer: Polynomial-time solvable: rational type-consistent utilities can be constructed, or nonexistence determined, in time polynomial in \(m,\tau,L\).
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf an assignment is ex-post stable at a strict preference profile, then there is a utility profile u consistent with the preference profile such that π ∈C(V u).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given atomless unit-mass populations with finite male and female type sets, rational type masses, strict rankings over counterpart types, and an ex-post-stable mass assignment \(x\) represented by stable measurable matchings, can one construct type-consistent utilities such that \(x\) lies in the transferable-utility core against every coalition taking equal masses from both sides and rematching internally?
Let \(A,B\) be nonempty finite male and female type sets in two atomless populations, each of total mass \(1\). A society is given by its support: the list of its \(\tau=|A|+|B|\) types with positive binary-rational masses \(p_a,q_b\); \(\tau\) is the support size, not the number of possible types. Set \(m=\max\{|A|,|B|\}\), and let \(L\) be the total input bit length.
Each type has a strict complete ranking of counterpart types; individuals are indifferent between partners of the same type. All individuals must be matched, and there is no outside option.
The input includes a nonnegative rational mass matrix \(x\) with row sums \(p_a\) and column sums \(q_b\). Every individual of type \(a\) receives counterpart-type probabilities \(x_{ab}/p_a\), and every individual of type \(b\) receives probabilities \(x_{ab}/q_b\).
A measurable perfect matching is stable if there are no types \(a,b\) for which positive mass of type \(a\) strictly prefers \(b\) to its assigned counterpart type and positive mass of type \(b\) strictly prefers \(a\) to its assigned counterpart type. Null sets are ignored.
It is promised that \(x\) is ex-post stable: it is the expectation of the type-mass matrices induced by a probability distribution over stable measurable perfect matchings. A decomposition is not supplied.
Type-consistent utilities are unrestricted real numbers \(u_a(b),v_b(a)\) that represent the specified strict rankings; utilities are quasilinear in money. Define baseline expected utilities \(U_a=p_a^{-1}\sum_b x_{ab}u_a(b)\) and \(V_b=q_b^{-1}\sum_a x_{ab}v_b(a)\).
A coalition selects arbitrary real masses \(0\le s_a\le p_a\), \(0\le t_b\le q_b\) with \(\sum_a s_a=\sum_b t_b\), and may rematch internally using any nonnegative matrix \(z\) with row sums \(s_a\) and column sums \(t_b\).
The assignment is in the transferable-utility core precisely when every such coalition and rematching satisfies \(\sum_{a,b}z_{ab}(u_a(b)+v_b(a))\le\sum_a s_aU_a+\sum_b t_bV_b\); baseline utilities involve no additional transfers.
Is there an algorithm polynomial in \(m,\tau,L\) that constructs rational type-consistent utilities satisfying this core condition or determines that none exist, or is deciding existence \(\mathrm{NP}\)-hard on these promised inputs?
For finite populations with strict rankings of individual partners, every ex-post-stable probabilistic assignment admits consistent utilities placing it in the transferable-utility core; this is an existence theorem, not a complexity classification ([Doğan–Yıldız, 2016](https://repository.bilkent.edu.tr/bitstreams/ab1e598d-f6e8-4833-9cb3-2786f7332c02/download)).
For a different fractional matching model with given cardinal utilities and money, competitive equilibria exist and their allocations belong to the core ([Manjunath, 2016](https://www.sciencedirect.com/science/article/pii/S089982561630121X)). No result settling the exact construction problem stated here was identified in the search.
The problem is polynomial-time solvable. There is an algorithm polynomial in \(m,\tau,L\) that constructs rational type-consistent utilities satisfying the stated core condition, or correctly determines that none exist.
The algorithm works for every input with the specified positive masses and marginal sums. It does not require the ex-post-stability promise or a stable decomposition.
Fix any utilities and their baseline expectations. Write
\[
\]
For clarity, define \(w_{ab}=u_a(b)+v_b(a)\).
Lemma. The stated core condition holds if and only if
\(w_{ab}\le U_a+V_b\) for every \(a\in A\) and \(b\in B\).
Proof of necessity. Fix a pair \(a,b\). Since both masses are positive, \(\varepsilon=\min\{p_a,q_b\}>0\). Consider the coalition with \(s_a=t_b=\varepsilon\), all other selected masses zero, and rematching \(z_{ab}=\varepsilon\), with all other entries zero. This is admissible. The core condition gives
\(\displaystyle \varepsilon w_{ab}\le \varepsilon U_a+\varepsilon V_b.\)
Division by \(\varepsilon\) proves the required inequality.
Proof of sufficiency. Suppose every pairwise inequality holds. For any admissible coalition and rematching, nonnegativity of \(z\) gives
\(\displaystyle \sum_{a,b}z_{ab}w_{ab}\le \sum_{a,b}z_{ab}(U_a+V_b)=\sum_a s_aU_a+\sum_b t_bV_b.\)
The equality uses the prescribed row and column sums of \(z\). This is precisely the core condition. \(\square\)
Thus the infinitely many coalition constraints are equivalent to \(|A||B|\) linear inequalities.
For each \(a\), list the female types from best to worst as \(b^a_1,\ldots,b^a_{|B|}\). For each \(b\), list the male types from best to worst as \(a^b_1,\ldots,a^b_{|A|}\).
Strict consistency is equivalent to positivity of every adjacent utility difference in these lists. We may strengthen these constraints to
\(\displaystyle u_a(b^a_i)-u_a(b^a_{i+1})\ge 1\qquad(1\le i<|B|),\)
and
\(\displaystyle v_b(a^b_j)-v_b(a^b_{j+1})\ge 1\qquad(1\le j<|A|).\)
Justification. Suppose strictly consistent real utilities satisfying the core condition exist. If there are any adjacent differences, their minimum \(\delta\) is positive because there are finitely many of them. Multiply every utility by the same positive scalar \(1/\delta\). Every adjacent difference becomes at least \(1\).
Baseline expectations scale by that same scalar. Consequently, the pairwise core inequalities, which are homogeneous, remain valid. If there are no adjacent differences, both type sets are singletons and no normalization is needed.
Conversely, adjacent differences of at least \(1\) imply the specified strict rankings: the utility difference between any earlier and later entries is the sum of positive adjacent differences.
This scaling argument establishes equivalence of the two feasibility questions; the algorithm does not need to know \(\delta\).
Let \(r=|A|\) and \(c=|B|\). Introduce unrestricted real variables
\(\displaystyle u_{ab},v_{ba}\quad(a\in A,\ b\in B),\qquad U_a\quad(a\in A),\qquad V_b\quad(b\in B).\)
Here \(u_{ab}\) represents \(u_a(b)\), and \(v_{ba}\) represents \(v_b(a)\).
Use the following linear feasibility system.
Baseline equations:
\(\displaystyle p_aU_a=\sum_{b\in B}x_{ab}u_{ab}\qquad(a\in A),\)
\(\displaystyle q_bV_b=\sum_{a\in A}x_{ab}v_{ba}\qquad(b\in B).\)
Pairwise core inequalities:
\(\displaystyle u_{ab}+v_{ba}\le U_a+V_b\qquad(a\in A,\ b\in B).\)
Normalized ranking inequalities:
\(\displaystyle u_{a,b^a_i}-u_{a,b^a_{i+1}}\ge 1\qquad(a\in A,\ 1\le i<c),\)
\(\displaystyle v_{b,a^b_j}-v_{b,a^b_{j+1}}\ge 1\qquad(b\in B,\ 1\le j<r).\)
Because \(p_a,q_b>0\), the baseline equations enforce exactly the expectations in the question. Sections 1 and 2 therefore prove:
Proposition. This rational linear system is feasible if and only if there exist real type-consistent utilities satisfying the stated core condition.
In particular, infeasibility of this system rules out utilities with arbitrarily small positive ranking gaps, not merely utilities satisfying some extra cardinal restriction.
Use the standard exact rational linear-programming theorem: feasibility of a finite system of rational linear equalities and non-strict inequalities can be decided in time polynomial in its binary encoding length; when feasible, a rational feasible point of polynomial encoding length can be produced. This is the polynomial-time linear-programming result established by [Khachiyan](https://www.mathnet.ru/eng/zvmmf5239).
Its hypotheses hold here:
Equalities can be replaced by two inequalities, and unrestricted variables can be replaced by differences of nonnegative variables; both transformations preserve polynomial encoding length.
The algorithm constructs this system and solves it exactly. If it is infeasible, it reports that no desired utilities exist. Otherwise, it returns the rational coordinates \(u_{ab},v_{ba}\). The baseline equations, ranking inequalities, and pairwise lemma prove that the returned utilities meet every requirement.
Thus both decision and rational construction take polynomial time in \(m,\tau,L\).
Any feasible utility profile necessarily satisfies equality on every positive entry of \(x\).
Indeed, let \(d_{ab}=U_a+V_b-u_{ab}-v_{ba}\). Pairwise feasibility gives \(d_{ab}\ge 0\), while the marginal and baseline equations imply
\(\displaystyle \sum_{a,b}x_{ab}d_{ab}=\sum_a p_aU_a+\sum_b q_bV_b-\sum_{a,b}x_{ab}(u_{ab}+v_{ba})=0.\)
Every summand is nonnegative. Hence \(x_{ab}>0\) implies \(d_{ab}=0\), or
\(\displaystyle u_a(b)+v_b(a)=U_a+V_b.\)
This is a consequence of the feasibility system, so no additional support constraints or stable decomposition are needed. The argument settles the requested computational classification without asserting that every promised input must be feasible.
⟨structured verdict parsed — rendered above⟩
The prover resolves the requested construction problem correctly: the stated core condition and strict utility rankings reduce to a rational linear feasibility problem of polynomial encoding length. No substantive gaps or false steps were found.
The pairwise characterization is correct in both directions.
For necessity, fix any \(a\in A\) and \(b\in B\). Positivity of the input masses ensures that \(\varepsilon=\min\{p_a,q_b\}>0\). The proposed coalition selects admissible masses, has equal total male and female mass, and admits the specified rematching. Its core inequality is precisely
\[ \varepsilon\bigl(u_a(b)+v_b(a)\bigr)\le \varepsilon(U_a+V_b). \]
Division by the positive number \(\varepsilon\) is valid. This establishes the inequality for every pair, including pairs with \(x_{ab}=0\).
For sufficiency, multiplying each pairwise inequality by \(z_{ab}\ge 0\) preserves its direction. Summation and the row and column constraints give exactly the required coalition inequality. This covers arbitrary real coalition masses and arbitrary admissible rematchings, including the zero-mass coalition.
The reduction uses the coalition baseline specified in the task. It does not introduce transfers into the baseline or assume a different model of coalition participation.
Assessment: Correct and complete.
Strict consistency is equivalent to strictly positive adjacent differences because each ranking is a finite strict total order.
When at least one adjacent difference exists, their minimum \(\delta\) is positive. Scaling every utility on both sides by the same positive scalar preserves rankings, scales both baseline expectations by that scalar, and preserves all homogeneous pairwise inequalities. Thus every strictly feasible profile yields one whose adjacent differences are at least \(1\).
Conversely, the normalized inequalities imply every required strict comparison by summing adjacent differences.
The exceptional case is handled correctly: because both type sets are nonempty, there are no adjacent differences exactly when both sets are singletons. If only one set is a singleton, the differences belonging to the other side remain available for normalization.
The potentially irrational value of \(\delta\) causes no problem: this argument establishes equivalence of real feasibility questions; it is not an algorithmic computation of \(\delta\).
Assessment: Correct and complete.
The variables and indices correctly represent all utilities and baseline expectations.
Since \(p_a,q_b>0\), the baseline equations uniquely enforce the expectations specified in the task. The pairwise constraints enforce exactly the core condition by Section 1, and the ranking constraints enforce the normalized strict rankings by Section 2.
Consequently, both directions of the proposition follow:
Infeasibility therefore excludes all strictly consistent utility profiles, including profiles with arbitrarily small positive ranking gaps.
Assessment: Correct and complete.
The invoked theorem is stated sufficiently precisely: feasibility of rational linear equalities and non-strict inequalities is decidable in polynomial binary encoding time, with a rational feasible point of polynomial encoding length obtainable whenever feasible. This is a standard exact rational linear-programming result; the linked reference is Khachiyan’s [*Polynomial algorithms in linear programming*](https://www.mathnet.ru/eng/zvmmf5239).
Its hypotheses are satisfied here. In particular, the system has rational coefficients and contains no strict inequalities after normalization. Unboundedness or a feasible set of lower dimension does not invalidate this feasibility theorem.
The dimension counts are correct:
All coefficients are input rationals or fixed integers. The bound \(rc\le m\tau\) is valid. Even a dense encoding has polynomially many coefficient positions, and every coefficient has bit length bounded by the input length or a constant. Hence the total system encoding length is polynomial in \(m,\tau,L\).
The stated conversions of equalities and unrestricted variables preserve feasibility and increase encoding length only polynomially. Recovering unrestricted utility coordinates from differences of rational coordinates also preserves polynomial output length.
Assessment: Correct; both decision and rational construction are established.
The support consequence is also correct. Pairwise feasibility gives \(d_{ab}\ge 0\). The marginal equations and baseline equations give the displayed identity
\[ \sum_{a,b}x_{ab}d_{ab}=0. \]
Every summand is nonnegative, so \(x_{ab}>0\) forces \(d_{ab}=0\). No equality is asserted for zero entries.
Assessment: Correct, although not needed for the algorithm.
The algorithm applies to the promised inputs because it applies to every input with the stated positive masses and marginals. It therefore need not verify ex-post stability or obtain a decomposition.
The prover correctly distinguishes deciding utility existence from asserting existence on every promised input. The former fully answers the polynomial-algorithm alternative in the task.
No mathematical repair or additional clarification is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.