Answer: Polynomial-time solvable in \(m,\tau,k,L\), with an exact optimal value and an explicit optimal allocation supported on polynomially many schedules.
Theorem 4.11 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate\maxsamrm{} is \cnp-hard even when the number of rounds ($k$) is 3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types \(T\) with rational masses \(\mu_t\) summing to \(1\), resource types \(U\) with per-capita supplies \(\sigma_u\), a compatibility relation, and each type’s permitted rounds \(K_t\) and request \(\rho_t\), choose nonnegative masses \(\lambda_{t,p}\) on full schedules \(p\). Each schedule assigns a compatible resource type in \(\rho_t\) distinct rounds of \(K_t\); require \(\sum_p \lambda_{t,p} \leq \mu_t\) for each \(t\) and \(\sum_{t,p:\,p(r)=u}\lambda_{t,p} \leq \sigma_u\) for each \(u,r\). Maximize \(\sum_{t,p}\lambda_{t,p}\), the mass receiving all requested rounds.
A society is given by its support: a list \(T\) of \(\tau\) agent types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) resource types \(U\), with nonnegative binary-rational per-capita supplies \(\sigma_u\), available separately in each of \(k\geq1\) explicitly represented rounds. Supplies need not sum to \(1\).
The input specifies a round-independent compatibility relation \(C\subseteq T\times U\), and, for each \(t\), an explicit set \(K_t\subseteq\{1,\ldots,k\}\) and an integer request \(1\leq\rho_t\leq|K_t|\).
Let \(P_t\) consist of all schedules \(p:D_p\to U\) with \(D_p\subseteq K_t\), \(|D_p|=\rho_t\), and \((t,p(r))\in C\) for every \(r\in D_p\). Resource types may repeat across rounds; schedules are implicit, not listed in the input.
An allocation assigns real masses \(\lambda_{t,p}\geq0\), subject to \(\sum_{p\in P_t}\lambda_{t,p}\leq\mu_t\) and \(\sum_{t\in T}\sum_{p\in P_t:\,r\in D_p,\,p(r)=u}\lambda_{t,p}\leq\sigma_u\) for every \(u,r\).
The objective is to maximize the fully satisfied mass \(\sum_{t\in T}\sum_{p\in P_t}\lambda_{t,p}\); unallocated mass receives no service. Let \(L\) be the total binary input length.
Is this continuous optimization problem solvable in time polynomial in \(m,\tau,k,L\), or is it \(\mathrm{NP}\)-hard?
For discrete agents and individual resources, maximizing the number of fully satisfied agents is \(\mathrm{NP}\)-hard even for \(k=3\); deciding whether everyone can be satisfied is polynomial-time solvable. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/26380/26152)
No result settling the exact continuous model above was located in the literature search.
The exact continuous problem is solvable in time polynomial in \(m,\tau,k,L\). It admits a polynomial-size linear program. The key is that its marginal variables can always be decomposed into fully satisfying schedules; this is proved constructively below.
For each type \(t\), let \(A_t=\{u\in U:(t,u)\in C\}\).
Introduce a variable \(x_t\) for the satisfied mass of type \(t\), and variables \(y_{t,r,u}\) for \(r\in K_t\), \(u\in A_t\), representing the mass of that type using resource \(u\) in round \(r\).
Consider the following linear program:
\(\displaystyle \begin{aligned} \text{maximize}\quad &\sum_{t\in T}x_t\\ \text{subject to}\quad &0\leq x_t\leq\mu_t &&(t\in T),\\ &y_{t,r,u}\geq0 &&(t\in T,\ r\in K_t,\ u\in A_t),\\ &\sum_{u\in A_t}y_{t,r,u}\leq x_t &&(t\in T,\ r\in K_t),\\ &\sum_{r\in K_t}\sum_{u\in A_t}y_{t,r,u}=\rho_t x_t &&(t\in T),\\ &\sum_{\substack{t\in T:\\r\in K_t,\ u\in A_t}}y_{t,r,u}\leq\sigma_u &&(u\in U,\ r\in\{1,\ldots,k\}). \end{aligned} \)
Empty sums are zero. In particular, if \(A_t=\varnothing\), the equality and \(\rho_t\geq1\) force \(x_t=0\).
The per-round constraint is essential: a satisfied mass \(x_t\) can receive at most \(x_t\) units of service in any one round.
Given a feasible allocation \(\lambda\), define
\(\displaystyle x_t=\sum_{p\in P_t}\lambda_{t,p}, \qquad y_{t,r,u}= \sum_{\substack{p\in P_t:\\r\in D_p,\ p(r)=u}}\lambda_{t,p}. \)
The mass and resource constraints follow directly from the allocation constraints.
For any fixed type and round, each schedule uses at most one resource. Consequently,
\(\displaystyle \sum_{u\in A_t}y_{t,r,u} =\sum_{\substack{p\in P_t:\\r\in D_p}}\lambda_{t,p} \leq x_t. \)
Every schedule uses exactly \(\rho_t\) rounds, so
\(\displaystyle \sum_{r\in K_t}\sum_{u\in A_t}y_{t,r,u} =\sum_{p\in P_t}|D_p|\lambda_{t,p} =\rho_t x_t. \)
Thus the resulting LP solution is feasible and has the same objective value.
Lemma. Fix a type \(t\). Suppose nonnegative numbers \(x\) and \(y_{r,u}\), indexed by \(r\in K_t\), \(u\in A_t\), satisfy
\(\displaystyle v_r:=\sum_{u\in A_t}y_{r,u}\leq x, \qquad \sum_{r\in K_t}v_r=\rho_t x. \)
Then there are nonnegative schedule masses \(\lambda_p\) satisfying
\(\displaystyle \sum_{p\in P_t}\lambda_p=x, \qquad \sum_{\substack{p\in P_t:\\r\in D_p,\ p(r)=u}}\lambda_p=y_{r,u}. \)
Moreover, a decomposition can be found in polynomial time when the given numbers are rational.
Proof. If \(x=0\), nonnegativity and the total-service equality imply that all \(y_{r,u}=0\). The empty allocation suffices.
Suppose \(x>0\). We repeatedly extract a schedule from the current residual values.
Call a round tight if \(v_r=x\), and positive if \(v_r>0\). There are at most \(\rho_t\) tight rounds: if their number is \(h\), then
\(\displaystyle h x\leq\sum_r v_r=\rho_t x.\)
There are at least \(\rho_t\) positive rounds: if their number is \(s\), then
\(\displaystyle \rho_t x=\sum_r v_r\leq s x.\)
Therefore we can choose a set \(D\subseteq K_t\) of exactly \(\rho_t\) positive rounds containing every tight round. For each \(r\in D\), choose \(u_r\in A_t\) with \(y_{r,u_r}>0\). These choices define a valid schedule \(p\), with domain \(D\) and \(p(r)=u_r\).
Set
\(\displaystyle \delta= \min\left( \{x\} \cup\{y_{r,u_r}:r\in D\} \cup\{x-v_r:r\in K_t\setminus D\} \right). \)
Every quantity in this minimum is positive: selected entries are positive, and every unselected round is not tight. Thus \(\delta>0\).
Assign mass \(\delta\) to \(p\), and update the residual by
\(\displaystyle x'=x-\delta,\qquad y'_{r,u}= \begin{cases} y_{r,u}-\delta,&r\in D,\ u=u_r,\\ y_{r,u},&\text{otherwise}. \end{cases} \)
These residual values satisfy the same hypotheses:
\(\displaystyle \sum_r v'_r=\rho_t x-\rho_t\delta=\rho_t x'. \)
It remains to prove finite termination. If \(x'>0\), the minimum defining \(\delta\) guarantees that either a previously positive entry becomes zero, or a previously non-tight, unselected round becomes tight.
Zero entries never become positive. A tight round stays tight at every subsequent nonterminal step: it must be selected, so its round total and \(x\) decrease by the same amount. Hence these events can occur only finitely many times.
More precisely, writing \(d=|K_t||A_t|\) and \(n=|K_t|\), there are at most \(d+n\) nonterminal steps and one terminal step. The algorithm must therefore reach \(x=0\), at which point all residual entries are zero.
Summing the extracted schedule masses and their coordinate contributions proves the required identities. Repeated occurrences of the same schedule may be combined.
For rational inputs, choose a common denominator \(Q\) equal to the product of their denominators. Every residual value and every extracted \(\delta\) remains an integer multiple of \(1/Q\), because the algorithm uses only sums, differences, comparisons, and minima. The bit length of \(Q\) is bounded by the total initial denominator bit length. All residual values remain bounded by their initial values, so their numerators also have polynomial bit length. Together with the polynomial step bound, this proves polynomial-time constructibility. \(\square\)
Take any feasible solution of the compact LP. Apply the lemma independently to each type, using \(x=x_t\) and \(y_{r,u}=y_{t,r,u}\).
The resulting schedules belong to \(P_t\): they select exactly \(\rho_t\) distinct rounds from \(K_t\), and use only compatible resources. Repeating a resource across different rounds is allowed by the stated model.
For each type, the decomposition allocates exactly \(x_t\leq\mu_t\). It also preserves every marginal \(y_{t,r,u}\). Therefore the aggregate use of each resource in each round is unchanged and remains at most \(\sigma_u\).
The resulting schedule allocation is feasible and has objective value \(\sum_t x_t\). Combined with Section 2, this proves equality of the two optimal values, with an effective conversion in both directions.
In particular, the compact LP does not merely provide an upper bound: its optimum is attainable in the original continuous model.
The LP has
\(\displaystyle N=\tau+\sum_{t\in T}|K_t||A_t| \leq\tau+\tau km \)
variables. Including nonnegativity constraints, its number of constraints is \(O(N+\tau k+mk+\tau)\).
Its coefficients are rational. Apart from the supplied masses and supplies, their magnitudes are at most \(k\), since \(1\leq\rho_t\leq k\). Thus its entire binary encoding length is polynomial in \(m,\tau,k,L\).
The feasible region is nonempty because the zero solution is feasible. It is bounded: \(x_t\leq\mu_t\), and every \(y_{t,r,u}\leq x_t\). Consequently, the optimum is finite and attained.
The standard rational linear-programming theorem gives an exact optimal rational solution in time polynomial in the LP’s binary encoding length, with polynomial output bit length; see [Trevisan’s account of polynomial-time linear programming](https://lucatrevisan.wordpress.com/2011/01/24/cs261-lecture-5-linear-programming/). All its hypotheses hold here.
Finally, the decomposition lemma converts that solution into an explicit allocation with only polynomially many positive schedule masses, also in polynomial time.
This settles the requested continuous model. The discrete hardness result is consistent with this conclusion: indivisible agents cannot be split into the fractional schedule masses used by the decomposition.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes polynomial-time solvability of the exact continuous model in USER_TASK, including an exact optimal value and an explicit optimal allocation supported on polynomially many schedules. No major or minor mathematical issues were found.
The variables match the intended quantities: \(x_t\) is fully satisfied mass, and \(y_{t,r,u}\) is its resource usage in a particular round.
The constraints correctly enforce:
The formulation uses only rounds in \(K_t\) and resources compatible with \(t\). It imposes no unintended restriction on repeating a resource across different rounds.
The empty-compatibility case is handled correctly: if \(A_t=\varnothing\), the total-service equality becomes \(0=\rho_t x_t\), forcing \(x_t=0\) because \(\rho_t\geq1\).
Assessment: Correct. Sufficiency of these marginal constraints requires the decomposition lemma, which the output supplies.
All schedule sets are finite, so the sums defining \(x_t\) and \(y_{t,r,u}\) are well-defined even though schedules are implicit in the input.
The mass and resource constraints transfer directly. The round inequality follows because a schedule is a function on its selected rounds and therefore assigns exactly one resource in each selected round.
The total-service identity correctly counts each schedule’s contribution exactly \(\lvert D_p\rvert=\rho_t\) times. The objective is preserved.
Assessment: Correct, with no omitted hypothesis or counting error.
When \(x=0\), nonnegative entries and zero total service force every entry to be zero. Assigning zero mass to every schedule satisfies both required identities.
For \(x>0\), the two counting bounds are correct:
Tight rounds are positive. Consequently, exactly \(\rho_t\) positive rounds can be selected while including every tight round.
Each selected round has a positive resource entry, so the resource choice exists. The resulting schedule satisfies all domain, cardinality, and compatibility requirements.
Every term in the minimum defining \(\delta\) is strictly positive:
The minimum is defined even when every round is selected, because it still contains \(x\) and the selected entries.
All four residual checks are valid.
For selected rounds, both the round total and residual mass decrease by \(\delta\), preserving their inequality. For unselected rounds, the slack term in the minimum ensures their unchanged total remains at most \(x-\delta\).
Exactly \(\rho_t\) distinct entries are reduced, one in each selected round. Thus the total-service equality is preserved with the stated coefficient \(\rho_t\).
If the step is nonterminal, then \(\delta<x\). Therefore some other term attains the minimum: either a positive selected entry becomes zero, or an unselected round becomes tight.
The claimed monotonicity properties hold:
Hence each nonterminal step creates an event that cannot recur for the same entry or round. The bound of at most \(d+n\) nonterminal steps is valid, including steps where several events occur simultaneously.
The algorithm cannot stop with positive residual mass: its schedule-selection and positive-extraction arguments remain applicable whenever that mass is positive. The finite event bound therefore establishes termination at zero residual mass.
At termination, the maintained total-service equality and nonnegativity force all residual entries to vanish. Summing the extracted masses and coordinate contributions yields the required identities.
The common-denominator argument is correct. Sums, differences, minima, and comparisons preserve the stated denominator grid.
The product denominator has bit length bounded by the sum of the initial denominator bit lengths. Residual coordinates and extracted masses are bounded by initial quantities, giving polynomial numerator bit lengths as claimed. Together with the polynomial number of steps and explicitly indexed coordinates, this establishes polynomial-time constructibility.
Assessment: The lemma is fully established for real inputs, with the additional algorithmic claim correctly restricted to rational inputs.
Applying the lemma independently to each type is legitimate. The only constraints coupling types are resource-round capacities, and the decomposition preserves every resource-round marginal.
Each resulting schedule fully satisfies its allocated mass. The type mass limits and all aggregate resource capacities are preserved, as is the objective.
Together with the forward direction, this establishes exact equality of feasible objective values and optimal values. No relaxation gap remains.
Assessment: Correct.
The variable count and constraint count are correct. Their bounds depend on the actual support size \(\tau\), without enumerating possible types or implicit schedules.
The integer coefficients have magnitude at most \(k\); supplied rational masses and supplies retain polynomial encoding size when repeated in the explicit LP. Thus the complete LP encoding is polynomial in \(m,\tau,k,L\).
The zero solution is feasible. Every resource variable satisfies \(y_{t,r,u}\leq x_t\leq\mu_t\), so the feasible region is bounded. It is also closed, being defined by finitely many linear equalities and inequalities. The claimed attainment is therefore justified.
The invoked rational-LP theorem is stated sufficiently precisely: exact optimization of an explicitly encoded rational LP takes polynomial time and admits a polynomial-bit optimal rational solution. The cited account discusses polynomial-time optimization, rational encoding, and bounded-size rational optimal solutions. The application satisfies the required hypotheses; equality constraints cause no difficulty. [Trevisan’s account](https://lucatrevisan.wordpress.com/2011/01/24/cs261-lecture-5-linear-programming/)
Finally, the decomposition’s support bound and arithmetic bound apply to the rational optimal LP solution. Each extracted schedule has at most \(k\) assignments, so the explicit allocation also has polynomial output size.
Assessment: Correct.
The argument covers empty compatibility sets, zero supplies, zero satisfied mass, a single round, and requests equal to all eligible rounds. It does not assume supplies sum to one or impose restrictions beyond the stated continuous model.
The observation about discrete hardness is consistent with the result and is not used as a premise of the proof.
No additional mathematical clarification or repair is needed. The central decomposition, equivalence, termination, and bit-complexity claims are all justified as written.
⟨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.