Answer: Polynomial-time solvable; a qualifying rational allocation always exists.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a compatibility graph and some choice of upper and lower bounds in Table 1, Algorithm 2 finds a matching that satisfies optimality, individual rationality and fairness whenever it exists in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational mass distribution μ over a finite set of complete compatibility types, a compatibility graph on those types, and a partition into fairness groups, find a maximum-matched-mass allocation that satisfies individual rationality and attains the greatest minimum Max-M-Min selection ratio over all capacity-feasible allocations, or report that none exists. Define each group’s lower bound as the greatest mass it can match using only within-group exchanges, and its upper bound as the greatest mass it receives among maximum-mass allocations; use the paper’s convention when the bounds coincide.
A society is given by its support: a list \(T\) of \(\tau\geq1\) complete types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Each type specifies compatibility and fairness-group membership; its patient is incompatible with its own donor.
The input includes a simple undirected compatibility graph \(H=(T,E)\), where an edge permits reciprocal pairwise exchange between its endpoint types, and a partition \(G_1,\ldots,G_k\) into nonempty fairness groups. Same-type exchanges are excluded. Set \(m=|E|\), and let \(L\) be the total input bit length.
A capacity-feasible allocation assigns divisible exchange masses \(x_e\in\mathbb R_{\geq0}\) satisfying \(\sum_{e\ni t}x_e\leq\mu_t\). Write \(y_i(x)=\sum_{t\in G_i}\sum_{e\ni t}x_e\) and \(S(x)=\sum_i y_i(x)\); thus each exchange contributes twice its mass to matched mass. Let \(\mathcal F\) contain all capacity-feasible allocations and \(\mathcal F^*=\arg\max_{x\in\mathcal F}S(x)\).
Define \(\ell_i\) as the greatest matched mass obtainable using only edges with both endpoints in \(G_i\), and \(u_i=\max_{x\in\mathcal F^*}y_i(x)\), with \(u_i\geq\ell_i\). Individual rationality means \(y_i(x)\geq\ell_i\) for every group.
The Max-M-Min selection ratio is \(a_i(x)=(y_i(x)-\ell_i)/(u_i-\ell_i)\) when \(u_i>\ell_i\); when \(u_i=\ell_i\), it is \(-\infty\) if \(y_i(x)<\ell_i\), and \(+\infty\) otherwise. Let \(a^*=\max_{x\in\mathcal F}\min_i a_i(x)\), with maximization over all capacity-feasible allocations.
The computational problem is to return a rational allocation \(x\in\mathcal F^*\) satisfying individual rationality and \(\min_i a_i(x)=a^*\), or report that none exists; any qualifying allocation is acceptable.
Is this continuous allocation problem solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,k,L\).
For finite agents, a polynomial-time algorithm finds a maximum, individually rational, fair matching whenever one exists; for Max-M-Min, such a matching always exists. [Source](https://www.ijcai.org/proceedings/2021/0059.pdf)
No result settling exactly the continuous problem defined above was located in the literature search.
The problem is solvable in polynomial time. In fact, under the stated assumptions, a qualifying rational allocation always exists.
An algorithm uses at most \(2k+2\) rational linear programs, each with at most \(m+1\) variables and \(O(m+\tau+k)\) constraints. Its bit running time is
\(O\!\left((k+1)\operatorname{poly}(m+\tau+k,L)\right).\)
The proof below works directly with divisible exchange masses. It does not require converting the society into a finite-agent instance of the [cited matching result](https://www.ijcai.org/proceedings/2021/0059.pdf).
Write \(d_t(x)=\sum_{e\ni t}x_e\) for the matched mass of type \(t\), and let \(S^*=\max_{x\in\mathcal F}S(x)\).
Lemma. For every \(x\in\mathcal F\), there exists \(\widehat x\in\mathcal F^*\) such that \(d_t(\widehat x)\geq d_t(x)\) for every \(t\).
Proof. Construct a directed network with a source \(s\), a sink \(z\), and two copies \(t_L,t_R\) of each type \(t\). Include:
An allocation \(x\) induces a feasible flow by assigning mass \(x_{\{u,v\}}\) to both corresponding middle arcs. The source and sink arcs associated with \(t\) each carry \(d_t(x)\). Its flow value is \(S(x)\).
Conversely, any feasible flow \(f\) induces the allocation
\(\displaystyle x^f_{\{u,v\}}=\frac{f(u_L,v_R)+f(v_L,u_R)}2.\)
By flow conservation,
\(\displaystyle d_t(x^f)=\frac{f(s,t_L)+f(t_R,z)}2\leq\mu_t.\)
Thus \(x^f\in\mathcal F\). Moreover,
\(\displaystyle S(x^f)=\sum_{\{u,v\}\in E}\bigl(f(u_L,v_R)+f(v_L,u_R)\bigr)=|f|.\)
Consequently, the unrestricted maximum flow value equals \(S^*\).
Now maximize flow value subject also to the lower bounds
\(f(s,t_L)\geq d_t(x),\qquad f(t_R,z)\geq d_t(x)\quad(t\in T).\)
This constrained flow set is nonempty, because it contains the flow induced by \(x\), and is compact, because all arc capacities are finite. Hence it has a maximizer \(\widehat f\).
Suppose its residual network contained an \(s\)-to-\(z\) path. Choose a simple such path and augment by a positive amount. A simple path visits \(s\) only at its start and \(z\) only at its end. Therefore the augmentation increases its first source arc and last sink arc and leaves all other source and sink arcs unchanged. In particular, it preserves every added lower bound, contradicting the maximality of \(\widehat f\).
Thus no residual \(s\)-to-\(z\) path exists. To verify that this implies unrestricted optimality, let \(R\) be the vertices reachable from \(s\) in the residual network. Then \(z\notin R\), every original arc leaving \(R\) is saturated, and every original arc entering \(R\) carries zero flow. Conservation shows that \(|\widehat f|\) equals the capacity of this cut. Every feasible flow has value at most that capacity, so \(\widehat f\) is an unrestricted maximum flow.
The allocation \(\widehat x=x^{\widehat f}\) therefore belongs to \(\mathcal F^*\), and
\(\displaystyle d_t(\widehat x)=\frac{\widehat f(s,t_L)+\widehat f(t_R,z)}2\geq d_t(x).\)
This proves the lemma. \(\square\)
Since each group’s matched mass is a sum of type matched masses, the lemma also gives \(y_i(\widehat x)\geq y_i(x)\) for every group.
For each group, choose an allocation attaining its internal optimum \(\ell_i\). Their union, denoted \(x^0\), is capacity-feasible: the groups have disjoint vertex sets, and each chosen allocation uses only its group’s internal edges. Thus
\(y_i(x^0)=\ell_i\quad\text{for every }i.\)
Applying the lemma produces an allocation in \(\mathcal F^*\) satisfying all individual-rationality inequalities. This also proves \(u_i\geq\ell_i\).
Define
\(J=\{i:u_i>\ell_i\},\qquad Z=\{i:u_i=\ell_i\}.\)
First suppose \(J\neq\varnothing\). Consider the compact, nonempty set
\(\mathcal C=\{x\in\mathcal F:y_i(x)\geq\ell_i\text{ for every }i\in Z\}.\)
On this set, the minimum selection ratio equals the continuous function
\(\displaystyle g(x)=\min_{i\in J}\frac{y_i(x)-\ell_i}{u_i-\ell_i}.\)
Outside \(\mathcal C\), the minimum selection ratio is \(-\infty\). Since \(g(x^0)=0\), the global optimum \(a^*\) is a finite, attained value satisfying \(a^*\geq0\).
Choose a global optimizer \(x^a\). For \(i\in J\), its ratio is at least \(a^*\geq0\), so \(y_i(x^a)\geq\ell_i\). For \(i\in Z\), this inequality follows from membership in \(\mathcal C\). Hence \(x^a\) is individually rational.
Extend \(x^a\) using the lemma. Every selection ratio is nondecreasing as its group’s matched mass increases, including the stipulated extended-real ratios for \(Z\). Therefore the extension has minimum ratio at least \(a^*\). It cannot have a greater value, by the definition of \(a^*\). The extension is consequently maximum, individually rational, and fair.
If \(J=\varnothing\), the allocation \(x^0\) has every ratio equal to \(+\infty\), so \(a^*=+\infty\). Its extension to \(\mathcal F^*\) remains individually rational and has the same minimum ratio.
Thus a qualifying allocation exists in every case.
First compute \(S^*\) with one linear program:
\(\displaystyle \text{maximize }2\sum_{e\in E}x_e,\quad\text{subject to }x\geq0,\ \sum_{e\ni t}x_e\leq\mu_t\ (t\in T).\)
For each group \(i\), compute \(\ell_i\) by maximizing \(2\sum_{e\subseteq G_i}x_e\) over allocations using only internal edges. This requires at most \(k\) linear programs.
For each group \(i\), compute \(u_i\) by maximizing \(y_i(x)\) subject to capacity feasibility and \(S(x)=S^*\). This requires \(k\) further linear programs.
Form \(J\) and \(Z\) using exact rational comparisons.
If \(J\neq\varnothing\), solve the following final linear program in \(x\) and \(\alpha\):
\(\text{maximize }\alpha,\)
subject to
\(x_e\geq0\quad(e\in E),\)
\(\displaystyle \sum_{e\ni t}x_e\leq\mu_t\quad(t\in T),\)
\(S(x)=S^*,\qquad \alpha\geq0,\)
\(y_i(x)\geq\ell_i+\alpha(u_i-\ell_i)\quad(i\in J),\)
\(y_i(x)\geq\ell_i\quad(i\in Z).\)
Return its allocation component \(x\).
Every feasible solution is maximum and individually rational, and its minimum ratio is at least \(\alpha\). Consequently, its objective value cannot exceed \(a^*\). Conversely, Section 2 supplies a qualifying allocation, making \(\alpha=a^*\) feasible. Therefore the linear-programming optimum is exactly \(a^*\), and any optimal allocation returned qualifies.
If \(J=\varnothing\), solve the feasibility linear program consisting of capacity feasibility, \(S(x)=S^*\), and \(y_i(x)\geq\ell_i\) for every group. Section 2 proves feasibility, and every solution has minimum ratio \(+\infty=a^*\).
The total number of linear programs is at most \(2k+2\).
The polynomial-time claim concerns exact bit computation, including the derived quotas.
Let \(D\) be the product of the denominators of the input masses. Then \(\log_2 D\leq L\). The constraint matrix of the original allocation polytope consists of the incidence matrix and nonnegativity rows, whose entries lie in \(\{-1,0,1\}\).
For \(m\geq1\), any vertex is determined by an invertible \(m\)-by-\(m\) submatrix \(A\). After scaling the right-hand side by \(D\), Cramer’s rule gives a common coordinate denominator dividing \(D|\det A|\). Hadamard’s inequality yields
\(\displaystyle |\det A|\leq m^{m/2}.\)
Also, \(0\leq x_e\leq1\) and \(0\leq S(x),y_i(x)\leq1\). Hence the relevant vertex coordinates and objective values have bit length
\(b=O\!\left(L+m\log(m+1)+1\right).\)
The same argument applies to internal optima. Each \(u_i\) can be attained at a vertex of \(\mathcal F^*\), and every vertex of this optimal face is a vertex of \(\mathcal F\). Thus \(S^*,\ell_i,u_i\), and their differences all have bit length \(O(b)\). When \(m=0\), these quantities are zero, so the bound still holds.
Set \(N=m+\tau+k+3\). With dense encoding, every linear program used above has total encoding length at most
\(B=O\!\left(N^2+(k+1)b\right).\)
Including nonnegativity constraints, each has at most \(m+1\) variables and \(m+\tau+k+3\) inequality constraints, with an equality represented by two inequalities.
If \(T_{\mathrm{LP}}(n,r,B)\) denotes the polynomial bit running time of an exact rational linear-programming algorithm, the overall bound is
\(O\!\left(L+(2k+2)\,T_{\mathrm{LP}}(m+1,m+\tau+k+3,B)\right).\)
In particular, this is \(O((k+1)\operatorname{poly}(m+\tau+k,L))\).
For \(J\neq\varnothing\), the final feasible set is bounded: the capacities bound \(x\), and \(y_i(x)\leq u_i\) on \(\mathcal F^*\) implies \(0\leq\alpha\leq1\). It is also nonempty and rational. An optimal rational vertex therefore exists and has polynomial encoding length. The feasibility case likewise has a rational vertex of polynomial encoding length.
Thus the algorithm returns the required rational allocation in polynomial time.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated continuous problem. The argument establishes polynomial-time solvability and the stronger conclusion that a qualifying rational allocation always exists. I found no major or minor mathematical issues.
The network construction and both conversions are correct.
For an allocation \(x\), assigning \(x_{\{u,v\}}\) to each of the two corresponding middle arcs satisfies conservation. Each source and sink arc associated with \(t\) carries \(d_t(x)\leq\mu_t\). The middle-arc capacity \(1\) is sufficient because \(x_{\{u,v\}}\leq\mu_u\leq1\). The flow value is indeed \(S(x)\), including the factor of two.
Conversely, averaging the two directed flows gives a nonnegative allocation with
\[
d_t(x^f)=\frac{f(s,t_L)+f(t_R,z)}2\leq\mu_t.
\]
Summing middle-arc flows gives both \(S(x^f)\) and the flow value. Thus the unrestricted maximum-flow value equals \(S^*\).
The constrained maximizer exists: its feasible set contains the flow induced by \(x\), is closed, and is bounded by finite capacities.
The augmentation argument is valid using the ordinary residual network of the original capacitated network. A simple path from \(s\) to \(z\) cannot traverse a reverse source arc, which would revisit \(s\), or a reverse sink arc, which would require visiting \(z\) before its endpoint. Consequently, augmentation increases the first source arc and last sink arc and leaves all other source and sink arcs unchanged. Every added lower bound is preserved.
The cut argument correctly establishes unrestricted optimality. With no residual path to \(z\), all original arcs leaving the reachable set are saturated and all original arcs entering it carry zero flow. Conservation then equates flow value with cut capacity, an upper bound on every feasible flow.
Finally, averaging the constrained source and sink flows preserves each lower bound \(d_t(x)\). The lemma therefore establishes exactly the claimed coordinatewise domination. Summing within groups gives the stated groupwise domination.
Each internal optimum is attained because its feasible allocation polytope is nonempty and compact. Combining internal optimizers is feasible because the groups partition the types. The resulting allocation satisfies \(y_i(x^0)=\ell_i\) for every group.
Applying the extension lemma establishes maximum individual-rational feasibility and also justifies \(u_i\geq\ell_i\).
When \(J\neq\varnothing\), the set \(\mathcal C\) is compact and contains \(x^0\). On \(\mathcal C\), every zero-denominator group contributes \(+\infty\), so the minimum ratio is exactly the displayed finite continuous function \(g\). Outside \(\mathcal C\), some zero-denominator group contributes \(-\infty\), making the overall minimum \(-\infty\).
Thus the global optimum is finite and attained. Since \(g(x^0)=0\), it is nonnegative. This establishes individual rationality for every positive-denominator group at a global optimizer; membership in \(\mathcal C\) establishes it for the remaining groups.
The extension lemma increases every group’s matched mass. All stipulated ratios are nondecreasing in that mass, including the extended-real cases. The extended allocation therefore retains the global optimal ratio while belonging to \(\mathcal F^*\).
When \(J=\varnothing\), all ratios at \(x^0\) equal \(+\infty\). Its extension remains individually rational and retains that value. This correctly handles the degenerate denominator case.
The preliminary programs correctly compute \(S^*\), each \(\ell_i\), and each \(u_i\). Their feasible sets are nonempty and compact, and their objectives match the definitions.
For \(J\neq\varnothing\), the final program correctly encodes:
The restriction \(\alpha\geq0\) is justified by the established inequality \(a^*\geq0\). It also makes individual rationality automatic for positive-denominator groups.
Every feasible objective value is at most \(a^*\), while the qualifying allocation established in Section 2 makes \(\alpha=a^*\) feasible. Hence the optimal objective equals \(a^*\). Any allocation component of an optimal solution has minimum ratio exactly \(a^*\).
For \(J=\varnothing\), the feasibility program is sufficient, and its feasibility has already been proved.
The count of at most \(2k+2\) linear programs is correct.
The denominator bound is valid: the logarithm of the product of input denominators is bounded by their total encoding length.
At a vertex of the original allocation polytope, an invertible active-constraint matrix has integer entries in \(\{-1,0,1\}\). Scaling the right-hand side by \(D\), Cramer’s rule supplies the claimed common denominator bound. Hadamard’s inequality applies because each row has Euclidean norm at most \(\sqrt m\).
The bounds \(x_e\leq1\) and \(S(x),y_i(x)\leq1\) are correct; the latter follows from total capacity \(1\). These magnitude bounds and the common denominator bound give the stated polynomial bit lengths for coordinates and objective values.
The internal programs have the same matrix structure. Also, \(\mathcal F^*\) is an optimal face of \(\mathcal F\), and its vertices are vertices of \(\mathcal F\). Consequently, the bound applies to every \(u_i\). Taking rational differences preserves the stated asymptotic bit bound.
The dense encoding estimate
\[
B=O\!\left(N^2+(k+1)b\right)
\]
correctly accounts for the matrix entries and the derived rational quotas. The final program has at most \(m+1\) variables and \(m+\tau+k+3\) inequalities when its equality is represented by two inequalities.
The invoked polynomial-time exact rational linear-programming guarantee applies to these rational programs with polynomial encoding length. The final optimization program is nonempty and bounded: capacity constraints bound \(x\), and any group in \(J\) gives \(\alpha\leq1\) on \(\mathcal F^*\). The feasibility program is likewise nonempty and bounded. Both therefore admit rational vertices of polynomial encoding length.
The case \(m=0\) is handled correctly: all matched masses and quotas are zero, \(J=\varnothing\), and the empty allocation qualifies.
The stated running time
\[
O\!\left((k+1)\operatorname{poly}(m+\tau+k,L)\right)
\]
therefore follows. No 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.