Answer: Polynomial-time solvable in \(m,\tau,L\), with exact rational separation certificates supported on at most two types whenever a coalition inequality fails.
Theorem 13 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of deciding whether an allocation is in the core of a mul- tiple partners assignment game is co-NP-complete if b ≡3 and w ≡1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite bipartite type graph \(H=(T_L\cup T_R,F)\), rational masses \(\mu_t\ge0\) with \(\sum_t\mu_t=1\), and rational per-agent allocations \(q_t\), decide whether \(q\) is in the continuous core: \(\sum_t\mu_tq_t=V(\mu)\) and \(\sum_tz_tq_t\ge V(z)\) for every \(0\le z\le\mu\), where \(V(z)\) is the maximum \(\sum_{(t,u)\in F}x_{tu}\) subject to \(\sum_u x_{tu}\le3z_t\), \(\sum_t x_{tu}\le3z_u\), and \(x_{tu}\ge0\); if not, output a violating \(z\) and feasible \(x\).
Let \(H=(T_L\cup T_R,F)\) be a finite simple bipartite graph, with \(m=|F|\). A society is given by its support: the list of its \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. The graph has exactly these types as vertices. Input also includes per-agent allocations \(q_t\in\mathbb{Q}\); let \(L\) be the total binary input length.
For every real coalition-mass vector \(0\le z\le\mu\), define \(V(z)=\max\{\sum_{(t,u)\in F}x_{tu}:x\in\mathbb{R}_{\ge0}^{F},\ \sum_{u:(t,u)\in F}x_{tu}\le3z_t\ (t\in T_L),\ \sum_{t:(t,u)\in F}x_{tu}\le3z_u\ (u\in T_R)\}\). Each unit of matched mass has value \(1\); there are no additional edge-capacity constraints.
Continuous core membership means \(\sum_t\mu_tq_t=V(\mu)\) and \(\sum_tz_tq_t\ge V(z)\) for every \(0\le z\le\mu\). The separation problem decides membership and, upon rejection, reports failure of efficiency or returns rational \(z\) and feasible rational \(x\) with \(\sum_{(t,u)\in F}x_{tu}>\sum_tz_tq_t\).
Is this continuous core-membership and separation problem polynomial-time solvable in \(m,\tau,L\), or NP-hard?
For finite agents on a simple bipartite graph, coalition value is the maximum cardinality of a \(3\)-matching in the induced graph: discrete core membership is co-NP-complete, and detecting a blocking coalition is NP-complete ([source](https://arxiv.org/pdf/1508.06420)).
No result settling precisely the support-mass problem defined above was identified in the literature search.
1. Result
The continuous core-membership and separation problem is polynomial-time solvable in \(m,\tau,L\).
More precisely, an allocation \(q\) belongs to the continuous core if and only if all three conditions hold:
Every failure of a coalition inequality has a rational blocking certificate supported on at most two types.
2. Necessity of the local conditions
Assume that \(\sum_tz_tq_t\ge V(z)\) for every real vector \(0\le z\le\mu\). Every listed type has \(\mu_t>0\), by the support convention.
If \(q_t<0\), choose \(z_t=\mu_t\), with all other coordinates zero, and choose \(x=0\). This matching vector is feasible, and its value satisfies \(\sum_{e\in F}x_e=0>\mu_tq_t=\sum_vz_vq_v\). Thus nonnegative allocations are necessary. This construction also provides the required rational certificate.
Now suppose an edge \((t,u)\) satisfies \(q_t+q_u<3\). Let \(a=\min\{\mu_t,\mu_u\}>0\). Choose \(z_t=z_u=a\), with all other coordinates zero, and choose \(x_{tu}=3a\), with all other edge coordinates zero.
The vector \(z\) lies in the prescribed box. At each of \(t,u\), the matching uses exactly \(3a=3z_t=3z_u\); every other vertex has zero incident matching mass. Hence \(x\) is feasible. Moreover, \(\sum_{e\in F}x_e=3a>a(q_t+q_u)=\sum_vz_vq_v\).
Therefore every edge must satisfy \(q_t+q_u\ge3\). Again, the construction is a rational blocking certificate.
3. Sufficiency for every real coalition
Assume \(q_t\ge0\) for every type and \(q_t+q_u\ge3\) for every edge.
Fix any real \(z\) satisfying \(0\le z\le\mu\), and any feasible matching vector \(x\). Define the incident matching mass by \(d_t(x)=\sum_{e\in F:\,t\in e}x_e\). Feasibility gives \(d_t(x)\le3z_t\).
Since \(q_t\ge0\), multiplying these inequalities by \(q_t/3\) and summing yields
\(\sum_tz_tq_t\ge\frac13\sum_tq_td_t(x)\).
Each edge has precisely its two endpoints, so
\(\frac13\sum_tq_td_t(x)=\frac13\sum_{(t,u)\in F}(q_t+q_u)x_{tu}\ge\sum_{(t,u)\in F}x_{tu}\),
where the last inequality uses \(q_t+q_u\ge3\) and \(x_{tu}\ge0\).
Consequently, \(\sum_tz_tq_t\ge\sum_{(t,u)\in F}x_{tu}\) for every feasible \(x\). Taking the maximum gives \(\sum_tz_tq_t\ge V(z)\).
The maximum exists: the feasible set is nonempty because it contains zero, is closed, and is bounded because each edge variable satisfies \(x_{tu}\le3\min\{z_t,z_u\}\).
This proves the coalition inequalities for all real \(z\) in the box, including irrational vectors. Together with efficiency, it proves the stated characterization.
4. Exact efficiency computation
Construct a directed network with source \(s\), sink \(r\), and the types as its other vertices. Its arcs and capacities are:
The capacity \(3\) on a middle arc imposes no additional restriction: any feasible matching already satisfies \(x_{tu}\le3\mu_t\le3\).
A feasible matching \(x\) defines a feasible flow by assigning \(x_{tu}\) to each middle arc and assigning the corresponding incident sums to the source and sink arcs. Its flow value is \(\sum_{(t,u)\in F}x_{tu}\).
Conversely, flow conservation implies that the values on the middle arcs satisfy precisely the matching constraints for \(\mu\). The flow value equals their sum. Thus the maximum flow value is exactly \(V(\mu)\).
For an exact bit-complexity bound, write each input mass as \(\mu_t=a_t/b_t\), with positive integer denominator, and let \(D=\prod_tb_t\). The binary length of \(D\) is at most the sum of the denominator lengths, hence is bounded by \(L\). Multiplying every network capacity by \(D\) produces integer capacities with binary length bounded by \(O(L)\).
The Edmonds–Karp theorem states that maximum flow on a finite directed network with nonnegative capacities can be computed using \(O(NA^2)\) arithmetic operations, where \(N\) and \(A\) are the numbers of vertices and arcs. Here \(N=\tau+2\) and \(A=m+\tau\). On the scaled network, all capacities, residual capacities, and flow values remain integers of \(O(L)\) bits, since the total source capacity is at most \(3D\). Thus this computation has polynomial bit complexity. Dividing its value by \(D\) gives \(V(\mu)\) exactly.
The rational number \(\sum_t\mu_tq_t\) can likewise be computed and compared with \(V(\mu)\) in polynomial bit complexity.
5. Membership and separation algorithm
Perform the following steps:
Sections 2 and 3 prove correctness. Each returned certificate uses an input mass or the minimum of two input masses, multiplied only by \(3\), so its binary encoding length is polynomial in the input length. The scans and their exact rational comparisons also take polynomial time.
The discrete hardness result concerns a different feasible set: its matching selects a subset of edges, so each edge is used at most once. This is explicit in the cited paper’s model, and its Theorem 13 establishes the stated discrete hardness. [Biró et al., *The Stable Fixtures Problem with Payments*](https://arxiv.org/pdf/1508.06420). In the present model, a single edge can carry \(3a\) units for a coalition containing mass \(a\) at each endpoint. That permitted construction forces the local edge inequality and makes the characterization above possible.
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned problem correctly. The characterization, exact polynomial-time algorithm, and rational separation certificates are valid. No major or minor issues were found.
The singleton certificate is valid. If \(q_t<0\), positivity of the support mass gives \(\mu_tq_t<0\). Choosing \(z_t=\mu_t\), all other coordinates zero, and \(x=0\) satisfies every constraint and gives a strict blocking inequality. This also covers isolated vertices.
The edge certificate is valid. For an edge \((t,u)\), the endpoints are distinct, and \(a=\min\{\mu_t,\mu_u\}>0\). The proposed coalition lies in the box, and the matching uses exactly \(3a\) at each endpoint. There is no edge-capacity constraint in the assigned problem. Consequently, \(q_t+q_u<3\) gives precisely the claimed strict inequality.
Both constructions use rational data.
Every step of the summation argument is justified:
Thus the argument bounds the value of every feasible \(x\) by the coalition’s allocation.
The maximum exists: the feasible set is nonempty and closed, and each coordinate has the stated finite upper bound. With no edges, the feasible set consists of the unique empty matching vector, so this case also causes no difficulty.
Nothing in this argument requires rational coalition coordinates. The universal quantifier over real \(z\) is fully addressed.
Together with the separately required efficiency equality, these arguments establish exactly the claimed characterization.
The network correctly represents \(V(\mu)\). The middle capacity \(3\) excludes no feasible matching because \(\mu_t\le1\), and hence \(x_{tu}\le3\mu_t\le3\).
Both directions of the matching–flow correspondence satisfy the relevant capacities and conservation equations. The flow value equals the sum of middle-arc flows. Isolated vertices, an empty edge set, and an empty bipartition side are all covered.
The denominator scaling is valid. The product \(D\) has binary length bounded by the sum of the input denominator lengths, and every scaled capacity is an integer with \(O(L)\) bits.
The stated Edmonds–Karp bound applies to this finite network with nonnegative integer capacities. Here \(N=\tau+2\) and \(A=m+\tau\). Capacities, flows, and residual capacities remain of polynomial binary length; the total source capacity is at most \(3D\). Thus the arithmetic-operation bound yields polynomial bit complexity.
Computing the rational allocation total and comparing it exactly with the flow value also takes polynomial time. No numerical tolerance or real-number oracle is assumed.
The rejection order satisfies the task: an efficiency failure may be reported directly. If efficiency holds, either local violation supplies the required rational \(z\) and feasible rational \(x\).
If both scans pass, sufficiency proves every coalition inequality. Conversely, if any coalition inequality fails, the local conditions cannot both hold, so one of the supplied certificates exists.
The claim about support of at most two types means that a violation has such a witness; it does not assert that every violating coalition itself has small support. Under that reading, the claim is proved.
The coordinate values and the full certificate encoding have polynomial length.
The cited model defines a matching as a subset of edges, so an edge can be selected only once. Its Theorem 13 states co-NP-completeness for bipartite multiple-partners assignment games with vertex capacity \(3\) and unit edge weights. The prover’s comparison accurately reflects the source. [Biró et al., *The Stable Fixtures Problem with Payments*](https://arxiv.org/pdf/1508.06420).
This citation supplies context; the continuous conclusion follows independently from the preceding argument.
No additional clarification or repair 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.