d4-conf-sagt-2025-0022 (d4-conf-sagt-2025-0022)

Given courses \(C\) with integral credits \(O(c)\), types \(T\) with rational masses \(\mu_t\) summing to \(1\), rational per-capita capacities \(q_c\), and an explicit allocation \(x_{t,A}\) of each type's mass to feasible integral bundles \(A\), decide whether the allocation is pair-size-stable. A block exists if some positive mass assigned to \(A\) can switch to \((A\setminus D)\cup\{c\}\), where \(c\notin A\), the type prefers \(c\) to every course in \(D\subseteq A\), \(O(c)\ge O(D)\), and \(O(A)-O(D)+O(c)\le T_t\); course \(c\) must have spare capacity or be able to replace lower-priority mass.

Let \(C\) be a set of \(m\) courses with positive integer credits \(O(c)\), and write \(O(A)=\sum_{c\in A}O(c)\).
A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type \(t\) has a positive integer credit limit \(T_t\) and a strict ranking \(\succ_t\) of its acceptable courses \(P_t\). Each course has a positive rational capacity \(q_c\) and a strict priority order \(\succ_c\) over its acceptable types; acceptability is mutual. Members of the same type have equal priority.
A feasible integral bundle for \(t\) is any \(A\subseteq P_t\) with \(O(A)\le T_t\), including the empty bundle; there are no additional bundle constraints or lower quotas.
The input allocation explicitly lists its \(K\) positive binary-rational entries \(x_{t,A}\), with unlisted entries zero, feasible bundles only, \(\sum_A x_{t,A}=\mu_t\), and course loads \(\ell_c=\sum_{t,A:c\in A}x_{t,A}\le q_c\). All integers are binary encoded; \(L\) is the total input bit length. State running times in \(m,\tau,K,L\).
A block consists of \(t,A,c,D\) with \(x_{t,A}>0\), \(c\in P_t\setminus A\), and \(D\subseteq A\), possibly empty, such that \(c\succ_t d\) for every \(d\in D\), \(O(D)\le O(c)\), and \(O(A)-O(D)+O(c)\le T_t\).
It additionally requires a positive rational \(\varepsilon\le x_{t,A}\) satisfying \(\varepsilon\le q_c-\ell_c+\sum_{u:t\succ_c u}\sum_{B:c\in B}x_{u,B}\): this mass switches to \((A\setminus D)\cup\{c\}\), using vacancies and, if needed, displacing mass of strictly lower-priority types from \(c\). Bundles remain integral even though mass can be split. The allocation is pair-size-stable exactly when no block exists.

Is testing pair-size stability polynomial-time solvable, or is its complementary problem of detecting a block \(\mathrm{NP}\)-hard?

For finite societies, testing pair-size stability is weakly \(\mathrm{coNP}\)-complete, even with one student and no additional bundle constraints ([source](https://arxiv.org/html/2505.21229v2#S3)).
No complexity classification for this exact mass-input problem was located in the literature search.

Classification. Detecting a block is weakly \(\mathrm{NP}\)-complete, and testing pair-size stability is weakly \(\mathrm{coNP}\)-complete. Hardness holds even when \(\tau=K=1\), every capacity is \(1\), and the sole type’s entire mass receives one bundle. Thus polynomial-time stability testing would imply \(\mathrm{P}=\mathrm{NP}\).

The proof below applies directly to the stated mass-input model.

1. Exact characterization of a block.

For each acceptable type-course pair, define its available mass by
\[ r_{t,c}=q_c-\ell_c+\sum_{u:t\succ_c u}\sum_{B:c\in B}x_{u,B}. \]
Here and below, displayed formulas are understood with the same mathematical delimiters as inline formulas.

Fix a listed entry \(x_{t,A}>0\) and a course \(c\in P_t\setminus A\). Define
\(E_{t,A,c}=\{d\in A:c\succ_t d\}\) and
\(a_{t,A,c}=\max\{0,O(A)+O(c)-T_t\}\).

Lemma. This entry and course admit a block exactly when \(r_{t,c}>0\) and there exists \(D\subseteq E_{t,A,c}\) satisfying
\(a_{t,A,c}\le O(D)\le O(c)\).

Proof. The preference requirement is precisely \(D\subseteq E_{t,A,c}\). The credit-limit inequality rearranges to
\(O(D)\ge O(A)+O(c)-T_t\).
Since \(O(D)\ge0\), combining it with the required inequality \(O(D)\le O(c)\) gives the stated interval.

The mass condition is equivalent to \(r_{t,c}>0\): necessity follows from \(0<\varepsilon\le r_{t,c}\). Conversely, when \(r_{t,c}>0\), the positive rational
\(\varepsilon=\min\{x_{t,A},r_{t,c}\}\)
satisfies both mass bounds. This proves both directions. \(\square\)

2. Membership in \(\mathrm{NP}\).

A certificate for block detection consists of a listed-entry index, a course index, and an \(m\)-bit indicator vector for \(D\). The lemma gives a polynomial-time verifier; no numerical certificate for \(\varepsilon\) is needed.

For completeness, exact rational arithmetic also has polynomial bit complexity. Put all input masses and capacities over the common denominator obtained by multiplying their input denominators. Its bit length is at most the total denominator bit length, hence at most \(L\). All relevant sums and comparisons consequently involve integers with \(O(L)\) bits. Credit sums likewise have \(O(L)\) bits.

More explicitly, compute
\(M_{u,c}=\sum_{B:c\in B}x_{u,B}\).
Scanning the allocation requires at most \(Km\) rational additions. For each course, suffix sums along its priority order compute every \(r_{t,c}\), using at most \(m\tau\) further additions. Preference ranks can be stored in the same polynomial preprocessing.

A conservative bound for preprocessing and checking one certificate is
\(O((Km+m\tau+m)L^3)\)
bit operations. Thus block detection belongs to \(\mathrm{NP}\), and stability testing belongs to \(\mathrm{coNP}\).

3. Hardness with one supported type and one allocation entry.

We reduce from Subset Sum with positive binary-encoded integers: given \(a_1,\ldots,a_n\) and a positive target \(b\), decide whether some index set \(I\) satisfies
\(\sum_{i\in I}a_i=b\).
This problem is \(\mathrm{NP}\)-complete; it is also the source problem used in [Theorem 1 of Rodríguez and Manlove](https://arxiv.org/html/2505.21229v2#S3). We may assume \(n\ge1\), since the empty-list cases are trivial.

Create courses \(d_1,\ldots,d_n,c^\ast\), with credits
\(O(d_i)=a_i\) and \(O(c^\ast)=b\).
There is one type \(t\), with
\(\mu_t=1\) and \(T_t=S:=\sum_{i=1}^n a_i\).
It accepts every course and ranks \(c^\ast\) first, followed by the other courses in any strict order. Every course has capacity \(1\) and accepts only \(t\).

The sole allocation entry is
\(x_{t,A}=1\), where \(A=\{d_1,\ldots,d_n\}\).
This input is feasible: \(O(A)=S=T_t\), each \(d_i\) has load \(1\), and \(c^\ast\) has load \(0\). All required masses and capacities are positive binary-rational numbers.

The only course absent from the sole allocated bundle is \(c^\ast\). It has available mass \(r_{t,c^\ast}=1\) and is preferred to every course in \(A\). Therefore a block exists exactly when some \(D\subseteq A\) satisfies
\(O(D)\le b\) and \(S-O(D)+b\le S\).
The second inequality gives \(O(D)\ge b\), so these conditions are equivalent to \(O(D)=b\).

Consequently, a Subset Sum solution gives a block, with \(\varepsilon=1\); conversely, every block gives a Subset Sum solution.

The construction has \(m=n+1\) and \(\tau=K=1\). Computing \(S\) and writing the instance takes polynomial time in the source input length. This proves \(\mathrm{NP}\)-hardness of block detection and, by complementation, \(\mathrm{coNP}\)-hardness of stability testing.

4. A pseudo-polynomial algorithm.

Let \(W=\max_{c\in C}O(c)\); if there are no courses, the allocation is immediately stable.

After the preprocessing above, inspect each of the at most \(Km\) candidate entry-course pairs. Discard candidates with \(r_{t,c}=0\). For every remaining candidate, use subset-sum dynamic programming on the credits of \(E_{t,A,c}\), retaining sums only through \(O(c)\).

Explicitly, enumerate these credits as \(w_1,\ldots,w_h\), where \(h\le m\). Set \(R_0=\{0\}\), and recursively define
\(R_i=R_{i-1}\cup\{s+w_i:s\in R_{i-1},\ s+w_i\le O(c)\}\).

By induction, \(R_i\) contains exactly the subset sums of the first \(i\) credits that are at most \(O(c)\). Positivity of the credits justifies truncation: a partial sum exceeding \(O(c)\) cannot later decrease.

The candidate admits a block precisely when \(R_h\) contains an integer in
\([a_{t,A,c},O(c)]\), by the lemma. A Boolean-array implementation uses \(O(m(W+1))\) updates per candidate. A conservative total running time is
\(O((Km+m\tau+Km^2(W+1))L^3)\)
bit operations.

This is pseudo-polynomial and becomes polynomial when course credits are unary encoded or bounded by a polynomial in \(L\). Combined with the hardness and membership proofs, it establishes the claimed weak completeness classification for the exact mass-input problem.

⟨structured verdict parsed — rendered above⟩

The output resolves the stated mass-input problem. Its block characterization, polynomial certificate verifier, Subset Sum reduction, and pseudo-polynomial algorithm are correct. No major or minor mathematical issues were found.

1. Exact characterization

The lemma matches every condition in the task.

• The definition of \(E_{t,A,c}\) captures exactly which allocated courses may be dropped.
• Rearranging the credit-limit condition gives \(O(D)\ge O(A)+O(c)-T_t\). Since credits are nonnegative, the lower endpoint \(a_{t,A,c}\) is correct.
• Combining this with the pair-size condition gives precisely \(a_{t,A,c}\le O(D)\le O(c)\).
• Because the listed allocation entry is positive, \(r_{t,c}>0\) is equivalent to the existence of the required positive rational switching mass. The proposed \(\varepsilon=\min\{x_{t,A},r_{t,c}\}\) satisfies both bounds.

The empty-drop case is included: \(D=\varnothing\) qualifies exactly when the candidate course fits without dropping credits and has positive available mass.

2. Membership and arithmetic bounds

The certificate identifies a positive listed entry, an acceptable absent course, and a subset of the allocated bundle. Its size is polynomial in the explicit input size, and the lemma supplies all necessary checks. An additional certificate for \(\varepsilon\) is unnecessary.

The rational-arithmetic argument is sound. The product of input denominators has bit length at most \(L\), and scaling to that denominator leaves relevant numerators and sums with \(O(L)\) bits. Credit sums also have \(O(L)\) bits.

The preprocessing correctly aggregates course loads by type. Suffix sums must exclude the current type, as specified by the strict-priority formula; equal-priority members of that type contribute no displacement mass.

The stated verifier bound,
\(O((Km+m\tau+m)L^3)\),
is conservative and sufficient. Consequently, block detection belongs to \(\mathrm{NP}\), and stability testing belongs to \(\mathrm{coNP}\).

3. Hardness reduction

The source problem is stated with positive integer weights and a positive target. This is the standard NP-complete Subset Sum restriction. The attribution to [Theorem 1 of Rodríguez and Manlove](https://arxiv.org/html/2505.21229v2#S3) is accurate: that theorem uses the same source problem and corresponding finite-society construction.

Every constructed input satisfies the task’s requirements:

• \(S>0\), so the sole type has a positive integer credit limit.
• All course credits and capacities are positive.
• Acceptability is mutual, and the singleton course priority orders are strict.
• The sole mass and allocation entry equal \(1\).
• The allocated bundle has credit total \(S=T_t\), and all loads satisfy capacities.

Only \(c^\ast\) can participate as the added course. Its available mass equals \(1\), and it outranks every allocated course. The two blocking inequalities force \(O(D)=b\), establishing both directions of the reduction. The proposed switching mass \(\varepsilon=1\) is valid.

There are no unintended blocks. Repeated source weights remain distinct courses, and instances with \(b>S\) correctly produce no block. Computing \(S\) and writing the instance require polynomial time.

Thus the reduction establishes block-detection hardness directly in the mass-input model, even with \(\tau=K=1\). Complementation establishes stability-testing hardness.

4. Pseudo-polynomial algorithm

The dynamic-programming recurrence correctly records attainable subset sums through \(O(c)\). Positivity of credits justifies discarding larger sums. Each item is used at most once because the recurrence uses the preceding state.

The interval test follows directly from the lemma. It handles empty eligible sets, zero lower endpoints, and unattainable intervals correctly. Feasibility ensures \(r_{t,c}\ge0\), so discarding candidates with \(r_{t,c}=0\) is sufficient. The no-course case is explicitly handled.

There are at most \(Km\) candidates, each requiring \(O(m(W+1))\) updates. The stated total bound,
\(O((Km+m\tau+Km^2(W+1))L^3)\),
is a valid conservative bit-operation bound.

This establishes the claimed pseudo-polynomial algorithm and polynomial running time when course credits are unary encoded or polynomially bounded. Together with membership and hardness, it supports the weak completeness classification.

Feedback

No additional mathematical clarification or repair is required. The output establishes weak \(\mathrm{NP}\)-completeness of block detection and weak \(\mathrm{coNP}\)-completeness of stability testing for the exact representation specified in the task.

⟨structured verdict parsed — rendered above⟩