Answer: Every instance admits a stable allocation. Existence and construction are in \(\mathrm{P}\), and construction is \(\mathrm{FPT}\) parameterized by \(k=m+\tau\).
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSIMPLE-CAS∗can be solved in time 2O(q(p+1))· n4 log n if the association graph is edgeless.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), activities \(A\), and rational approval intervals \(I_{t,a}\subseteq[0,1]\), find a stable allocation \(x_{t,a}\ge 0\), including a void option \(a_0\), with \(\sum_{a\in A\cup\{a_0\}}x_{t,a}=\mu_t\). Let \(z_a=\sum_t x_{t,a}\); require \(x_{t,a}>0\Rightarrow z_a\in I_{t,a}\), and, whenever type \(t\) has positive mass left in the void, require that \(z_a\) is not a right-accumulation point of \(I_{t,a}\) for every activity \(a\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types. Let \(A\) contain \(m\) activities; there are no friend or enemy relations.
For each \((t,a)\in T\times A\), the approval set \(I_{t,a}\) is either empty or a closed interval \([\ell_{t,a},u_{t,a}]\subseteq[0,1]\) with binary-rational endpoints; singleton intervals are allowed. Types are distinguished by their approval profiles. Approved outcomes are mutually indifferent and strictly preferred to the void option \(a_0\); disapproved outcomes are strictly worse than void.
An allocation consists of real masses \(x_{t,a}\geq0\) for \(a\in A\cup\{a_0\}\), with \(\sum_{a\in A\cup\{a_0\}}x_{t,a}=\mu_t\); write \(z_a=\sum_{t\in T}x_{t,a}\) for \(a\in A\).
It is stable precisely when \(x_{t,a}>0\Rightarrow z_a\in I_{t,a}\) for every real activity, and \(x_{t,a_0}>0\Rightarrow I_{t,a}\cap(z_a,z_a+\varepsilon) =\varnothing\) for some \(\varepsilon>0\), for every \(a\in A\). This latter condition excludes right-accumulation points, including at empty activities; joining does not require existing participants' consent.
The problem is to decide whether a stable allocation exists and find one when it does. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\), with parameter \(k=m+\tau\).
Is deciding whether a stable allocation exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, is the continuous problem \(\mathrm{FPT}\) parameterized by \(k=m+\tau\)?
For finite agents without friend or enemy relations and with interval approvals, stable allocation is solvable in \(2^{O(\tau(m+1))}n^4\log n\) time; with arbitrary approval sets, the discrete problem is \(\mathrm{W}[1]\)-hard parameterized by \(m\). [Eiben, Ganian and Ordyniak](https://www.ijcai.org/proceedings/2018/0028.pdf)
Discrete stable-existence is \(\mathrm{NP}\)-complete even with interval approvals, as follows from the interval-preserving stable-existence reduction applied to the increasing-approval perfect-assignment hardness result. [Darmann et al.](https://link.springer.com/article/10.1007/s00182-017-0596-4)
No result settling this exact continuous model was located in the literature search.
Every instance in the stated continuous model admits a stable allocation. Moreover, one can construct a rational stable allocation in
\(O\!\left(L^3+m\tau\log(\tau+1)L\right)\) bit operations.
Thus stable existence is in \(\mathrm{P}\), and construction is also \(\mathrm{FPT}\) parameterized by \(k=m+\tau\).
The key is divisibility: at the largest feasible load of an activity, all remaining mass that would want to join that activity fits into its current load.
For a nonempty approval interval \(I=[\ell,u]\) and a load \(z\in[0,1]\), the following equivalence holds:
\[ I\cap(z,z+\varepsilon)\ne\varnothing\text{ for every }\varepsilon>0 \quad\Longleftrightarrow\quad \ell\le z<u. \]
Indeed:
In particular, singleton intervals never create right accumulation.
For an activity \(a\), define its willing and right-accumulating types at load \(z\) by
\[ W_a(z)=\{t:I_{t,a}\ne\varnothing,\ \ell_{t,a}\le z\le u_{t,a}\}, \]
and
\[ M_a(z)=\{t:I_{t,a}\ne\varnothing,\ \ell_{t,a}\le z<u_{t,a}\}. \]
Consequently, \(M_a(z)\subseteq W_a(z)\). Stability requires that every type in \(M_a(z_a)\) have zero mass in void.
Consider one activity and remaining type masses \(r_t\ge0\), with \(\sum_t r_t\le1\). These are masses still available for assignment.
Write \(W(z)\) and \(M(z)\) for the sets defined above, and let
\[ F(z)=\sum_{t\in W(z)}r_t. \]
A load \(z\) can be formed using only approving remaining mass if and only if \(z\le F(z)\).
Necessity follows by summing the available masses of approving types. Sufficiency follows from divisibility: take mass from those types, up to their respective capacities \(r_t\), until the total reaches \(z\).
Lemma. There exists a largest feasible load \(z^\star\). At that load,
\[ \sum_{t\in M(z^\star)}r_t\le z^\star. \]
Furthermore, one can fill the activity to \(z^\star\) while assigning the entire remaining mass of every type in \(M(z^\star)\).
Proof. Let
\[ \mathcal F=\{z\in[0,1]:z\le F(z)\}. \]
This set contains \(0\). It is also closed. To prove this, suppose \(z_j\in\mathcal F\) and \(z_j\to z\). If a type does not approve \(z\), closedness of its approval interval implies that it does not approve \(z_j\) for all sufficiently large \(j\). There are finitely many types, so eventually \(W(z_j)\subseteq W(z)\). Hence
\[ z_j\le F(z_j)\le F(z), \]
and passing to the limit gives \(z\le F(z)\). Thus \(\mathcal F\) is a nonempty compact set and has a maximum \(z^\star\).
Suppose, for a contradiction, that
\[ B:=\sum_{t\in M(z^\star)}r_t>z^\star. \]
Every type in \(M(z^\star)\) has \(\ell_t\le z^\star<u_t\). Because there are finitely many such types, we can choose \(\delta>0\) satisfying
\[ \delta<B-z^\star \quad\text{and}\quad \delta<u_t-z^\star\ \text{for every }t\in M(z^\star). \]
All these types approve \(z^\star+\delta\), so
\[ F(z^\star+\delta)\ge B>z^\star+\delta. \]
Also, \(z^\star+\delta<B\le1\). Therefore \(z^\star+\delta\) is feasible, contradicting maximality.
It remains to construct the claimed filling. First assign all remaining mass of types in \(M(z^\star)\). Its total \(B\) is at most \(z^\star\). The other willing types have available mass
\[ F(z^\star)-B\ge z^\star-B. \]
Use those types to supply the remaining \(z^\star-B\) mass. Every participant approves \(z^\star\), and no mass of a type in \(M(z^\star)\) remains unassigned. This proves the lemma. \(\square\)
Process the activities in any order \(a_1,\ldots,a_m\). Initially set \(r_t=\mu_t\) for every type.
For each activity \(a_i\):
The lemma guarantees that every step is possible. Assign all masses left after the final step to void.
Proof of stability. Assignments to a processed activity are never changed. Consequently, its final load is exactly the load used when selecting its participants. Every participant was selected from its willing set, establishing individual rationality.
Now suppose type \(t\) has positive mass in void at the end. Its remaining mass was therefore positive immediately before processing every activity. If \(t\) had belonged to \(M_{a_i}(z_i^\star)\), step 2 would have assigned its entire remaining mass, leaving no mass of that type for void. Thus
\[ t\notin M_{a_i}(z_i^\star)\qquad\text{for every }i. \]
By Section 1, each activity therefore has some right neighborhood containing no approved point for this void type. This is precisely the required void-stability condition.
If the definition requires a common positive \(\varepsilon\) across activities for each void type, take the minimum of the finitely many positive choices. Mass conservation follows directly from the updates to \(r_t\). Hence the resulting allocation is stable. \(\square\)
Fix an activity and its current remaining masses. Form the sorted list of distinct breakpoints consisting of \(0\), \(1\), and all endpoints of its nonempty approval intervals:
\[ 0=b_0<b_1<\cdots<b_s=1. \]
There are at most \(2\tau+2\) breakpoints. On each open gap \((b_i,b_{i+1})\), the willing set is constant. Let \(S_i\) be its total remaining mass.
Consider the following candidate loads:
The largest candidate is exactly the largest feasible load.
To verify completeness, consider a feasible load \(z\) in an open gap. Then \(z\le S_i\).
The breakpoint \(0\) is always a candidate, so the candidate list is nonempty.
All breakpoint and gap totals can be computed by a sweep after sorting endpoints. At each breakpoint, add masses of intervals beginning there, evaluate the closed-point total, and then remove masses of intervals ending there. This ordering also handles singleton intervals correctly.
Thus one activity requires \(O(\tau\log(\tau+1))\) arithmetic operations, including the subsequent allocation. All activities require \(O(m\tau\log(\tau+1))\) arithmetic operations.
Let \(D\) be the product of all denominators appearing in the input masses and interval endpoints. Since their total encoding length is at most \(L\), the integer \(D\) has \(O(L)\) bits.
Express all input numbers over this common denominator. Every number subsequently constructed remains an integer multiple of \(1/D\):
All these values lie in \([0,1]\), so their scaled numerators have \(O(L)\) bits. Additions, subtractions, and comparisons therefore take \(O(L)\) bit operations.
Using elementary integer arithmetic, common-denominator preprocessing takes \(O(L^3)\) bit operations. The complete construction consequently takes
\[ O\!\left(L^3+m\tau\log(\tau+1)L\right) \]
bit operations and produces an allocation of total encoding length \(O(\tau(m+1)L)\).
Because \(m,\tau\le k\), this is also bounded by
\[ O\!\left(L^3+k^2\log(k+1)L\right), \]
which is an \(\mathrm{FPT}\) bound for \(k=m+\tau\). On valid inputs, the decision answer is always yes.
In the discrete model, stability tests whether an unassigned agent approves the group size *after* joining. That agent need not approve the current group size; this distinction already underlies the one-activity nonexistence example in [Darmann et al., Proposition 1](https://link.springer.com/article/10.1007/s00182-017-0596-4).
In the stated continuous model, a type with right accumulation at \(z\) already approves \(z\), because its interval is closed. Moreover, finitely many such intervals admit a common sufficiently small positive increase in load. These are exactly the properties used in the saturation lemma. Divisibility then lets us prioritize all right-accumulating mass when filling each activity.
⟨structured verdict parsed — rendered above⟩
The output resolves the task. The saturation lemma, sequential construction, and claimed bit-complexity bound are correct for the stated continuous stability definition. I found no mathematical gaps requiring clarification.
For a closed nonempty interval \([\ell,u]\), the condition that every right neighborhood of \(z\) intersects the interval is exactly \(\ell\le z<u\). The proof correctly excludes the cases \(z<\ell\) and \(z\ge u\), including equality at the upper endpoint.
Singleton intervals therefore never create right accumulation. Empty approval sets also create none. The definitions of \(W_a(z)\) and \(M_a(z)\), their inclusion relationship, and the reformulation of void stability are all consistent with the task.
For \(z\in[0,1]\), the condition \(z\le F(z)\) is necessary because only willing types can supply participants. It is sufficient because the masses are divisible and each type supplies at most its remaining capacity.
This includes \(z=0\): assigning no participants is feasible regardless of which types approve zero.
The feasible set contains zero. The closedness argument is valid: if a type does not approve the limiting load, closedness of its approval set means that sufficiently nearby loads are also disapproved. Finiteness of the support permits a common sufficiently large sequence index, giving
\(W(z_j)\subseteq W(z)\).
Thus feasibility passes to the limit. The feasible set is a nonempty closed subset of the compact interval \([0,1]\), so it has a maximum. The compactness theorem is applied with its hypotheses satisfied.
Under the contradiction assumption \(B>z^\star\), the set of right-accumulating types is nonempty, and each has strictly positive upper-endpoint slack. Finiteness permits the stated positive choice of \(\delta\).
Every such type approves \(z^\star+\delta\). The inequalities
\(F(z^\star+\delta)\ge B>z^\star+\delta\) establish feasibility, while
\(z^\star+\delta<B\le1\) ensures the candidate remains in the permitted domain. This contradicts maximality.
The subsequent filling argument respects all type capacities. The right-accumulating mass totals at most \(z^\star\), and the other willing types have enough available mass to supply the difference. No assumption about integral participants is used.
Each application of the lemma uses nonnegative remaining masses whose total is at most one. Updating these masses preserves that invariant and mass conservation.
Earlier activities receive no later assignments, so their final loads equal the loads at which their participants were checked for approval.
If a type has positive final void mass, it cannot have belonged to the right-accumulating set of any processed activity: that step would have exhausted its remaining mass. The interval characterization therefore supplies the required right neighborhood for every activity.
The argument also handles a common positive neighborhood size, should that quantifier interpretation be required, because there are finitely many activities.
All willing-set changes occur at the listed endpoints, so the willing set is constant on each open gap.
For a feasible gap load \(z\), the inequality \(z\le S_i\) ensures that, when \(S_i<b_{i+1}\), the proposed candidate \(S_i\) lies strictly inside that gap and dominates \(z\). When \(S_i\ge b_{i+1}\), closedness ensures that every interval contributing to the gap total also contributes at its right endpoint. That endpoint is therefore a feasible candidate.
Breakpoint candidates cover loads at endpoints, and zero guarantees a nonempty candidate list. Consequently, taking the largest candidate computes exactly the maximum established by the lemma.
The sweep order—add starting intervals, evaluate the point, remove ending intervals—correctly handles closed endpoints and singleton intervals. Sorting and sweeping support the claimed \(O(\tau\log(\tau+1))\) operation count per activity, including filling.
The product of input denominators has \(O(L)\) bits. Expressing the input over this denominator is exact.
All subsequently constructed loads and masses remain multiples of \(1/D\), because the algorithm uses sums, differences, comparisons, and minima. Their values remain in \([0,1]\), so their scaled numerators also have \(O(L)\) bits.
Elementary integer arithmetic supports the stated \(O(L^3)\) preprocessing bound. Subsequent additions, subtractions, and comparisons cost \(O(L)\) each. Hence the overall bound
\(O(L^3+m\tau\log(\tau+1)L)\) and the stated output-length bound are justified.
Substituting \(m,\tau\le k\) yields the claimed FPT bound. Polynomial-time construction also settles the requested decision problem.
Empty approvals, singleton approvals, zero remaining masses, loads zero and one, and coincident endpoints are covered by the argument. If there are no activities, placing every type in void satisfies the stated conditions vacuously.
The discrete comparison accurately describes deviations evaluated at the group size after joining. The cited one-activity nonexistence statement and example appear in [Darmann et al., Proposition 1](https://link.springer.com/article/10.1007/s00182-017-0596-4). This citation is explanatory; the continuous result is established independently.
No repair or additional clarification is needed.
⟨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.