Answer: No.
Proposition 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateis closely related to the greedy approach for ob- taining a 1/2-approximation for the maximum matching problem [Karp et al., 1990]. Its proof is similar and is therefore omitted.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite public types \(q\), topics \(j\), rational public masses \(\mu_q\), application sets \(C_q\), rankings, values \(v_{qj}\), topic capacities \(b_j\), and total capacity \(\kappa\), each complete type is \((q,r)\), where \(r\) determines an acceptable set \(A_{q,r}\). The actual masses \(\nu_{q,r}\) are hidden, subject to \(\sum_r \nu_{q,r}=\mu_q\). A policy may sequentially offer a fixed topic to a chosen mass of a public type, observe exact aggregate acceptances and rejections, and make later offers to remaining mass. For every admissible hidden distribution and response history, can a polynomial-time policy guarantee a final accepted assignment of value at least \(\frac12\operatorname{OPT}(\nu)\), where \(\operatorname{OPT}(\nu)\) is the maximum-value feasible matching using the realized acceptable sets and capacities?
There are \(m\geq 1\) topics and a finite set \(Q\) of public types. Each \(q\in Q\) has positive binary-rational mass \(\mu_q\), an application set \(C_q\), a truthful total preorder on \(C_q\), and nonnegative binary-rational values \(v_{qj}\). Topic capacities \(b_j\) and total capacity \(\kappa\) are positive binary rationals; masses need not sum to one.
For each public type, number its preference equivalence classes from best to worst. A complete type \((q,r)\) accepts exactly the first \(r\) classes, denoted \(A_{q,r}\), where \(r\) ranges from zero to the number of classes; thus empty and full acceptable sets are allowed.
A society is given by its support: the list of the \(\tau\) complete types with positive mass, each mass \(\nu_{q,r}\) a binary rational. Here \(\tau\) is the actual support size, not the number of possible types. This list and its masses are hidden from the policy; only the public data and marginals \(\sum_r\nu_{q,r}=\mu_q\) are revealed.
A sequential fixed offer selects a positive rational mass from an unmatched cohort of one public type, distinguished by its observed offer history, and offers one topic \(j\in C_q\). The offered mass cannot exceed either residual topic capacity or residual total capacity. Each recipient accepts exactly when \(j\in A_{q,r}\); accepted mass is irrevocably assigned to \(j\) and receives no further offers, while rejected mass remains available.
Only exact aggregate accepted and rejected masses are observed. Selecting part of a cohort reveals no hidden types: its composition may be any rational split consistent with one fixed hidden society and all previous cohort partitions. Guarantees quantify over every such response history.
Define \(\operatorname{OPT}(\nu)\) as the maximum of \(\sum_{q,r,j}v_{qj}x_{q,r,j}\) over nonnegative assignment masses satisfying \(x_{q,r,j}=0\) when \(j\notin A_{q,r}\), \(\sum_jx_{q,r,j}\leq\nu_{q,r}\), \(\sum_{q,r}x_{q,r,j}\leq b_j\), and \(\sum_{q,r,j}x_{q,r,j}\leq\kappa\).
Let \(L\) be the encoding length of the public data and hidden support representation, and \(H\) the total response encoding length. Polynomial time means polynomially many offers in \(m,\tau,L\) and total bit complexity polynomial in \(m,\tau,L,H\).
Does there exist a deterministic polynomial-time sequential fixed-offer policy guaranteeing final value at least \(\frac12\operatorname{OPT}(\nu)\) for every admissible hidden society and response history?
For discrete students, unit topic capacities and an integer total capacity, a polynomial-time sequential fixed-offer protocol achieves ratio \(\frac12\), and no deterministic sequential fixed-offer protocol guarantees a larger ratio. [Source](https://www.ijcai.org/proceedings/2019/0019.pdf)
No result settling this exact continuous model was located.
No. The obstruction is the number of offers required to find acceptable mass in a cohort whose mass is exponentially larger than capacity. It persists with unit capacities, strictly positive values, and no empty acceptable sets.
Fix an integer \(N\geq 1\). There are two topics, \(d\) and \(h\), and one public type \(q\), with:
The fixed hidden society has exactly two supported complete types:
\[
\nu_{q,1}=2^N-1,\qquad A_{q,1}=\{d\},
\]
\[
\nu_{q,2}=1,\qquad A_{q,2}=\{d,h\}.
\]
Thus \(\tau=2\), both supported types have nonempty acceptable sets, and their masses have the required public marginal.
All these data have encoding length \(L_N=O(N)\): the only growing numbers are the binary integers \(2^N\) and \(2^N-1\).
The optimum is exactly \(\operatorname{OPT}(\nu)=1\). Indeed, assigning the entire unit mass of type \((q,2)\) to \(h\) attains value \(1\). Conversely, every assignment has total mass at most \(\kappa=1\), and every value per unit mass is at most \(1\).
Lemma. Against any sequential fixed-offer policy, the above fixed society admits the following responses throughout its first \(2^N-1\) offers, or until the policy stops:
Proof. Call the cohort with empty offer history the untouched cohort. We maintain the following invariant after \(t\) offers:
Initially these statements hold with \(U_0=0\).
Consider offer \(t+1\), where \(t+1\leq 2^N-1\), and write its mass as \(s>0\). Every legal offer satisfies \(s\leq 1\), because residual total capacity never exceeds its initial value \(1\).
If the selected cohort has nonempty history, it consists entirely of type \((q,1)\), so any selected portion also has that type.
If the selected cohort is untouched, its available type-\((q,1)\) mass is at least
\[
2^N-1-U_t\ \geq\ 2^N-1-t\ \geq\ 1.
\]
Consequently, the adversary can select the whole offered mass \(s\) from type \((q,1)\), leaving all type-\((q,2)\) mass untouched. Then \(U_{t+1}=U_t+s\leq t+1\).
Type \((q,1)\) accepts \(d\) and rejects \(h\), giving exactly the claimed responses. Accepted recipients leave the unmatched population; rejected recipients form a cohort containing only type \((q,1)\). The invariant therefore persists.
Every split is rational, preserves the two fixed type masses, and refines the existing cohort partitions. Hence this is an admissible history for one fixed hidden society, rather than a sequence of changing societies. \(\square\)
Suppose a policy had the required polynomial offer bound. Because \(m=\tau=2\) and \(L_N=O(N)\), there would be constants \(C>0\) and an integer \(a\geq 0\) such that the number of offers on these instances is at most
\[
B_N=\left\lceil C(N+1)^a\right\rceil.
\]
Choose \(N\) sufficiently large that \(B_N\leq 2^N-1\). Apply the lemma’s adversarial splits throughout the policy’s execution. The policy must terminate within \(B_N\) offers; otherwise an admissible continuation would violate its offer bound.
Along this history, every accepted assignment is to \(d\). Since total accepted mass is at most \(1\), its final value is at most \(\frac14\). But \(\operatorname{OPT}(\nu)=1\). Thus its final value is strictly less than \(\frac12\operatorname{OPT}(\nu)\), contradicting the proposed guarantee.
This proves impossibility solely from the offer bound, irrespective of computational power or response encoding length \(H\).
More quantitatively, on this family any policy guaranteeing one half must have an admissible execution requiring at least \(2^N\) offers: stopping anywhere along the lemma’s first \(2^N-1\) responses fails.
Multiplying all masses and capacities in the construction by \(2^{-N}\) gives public mass \(1\), supported masses \(1-2^{-N}\) and \(2^{-N}\), and capacities \(b_d=b_h=\kappa=2^{-N}\). The same proof applies, with optimum \(2^{-N}\) and final value at most \(\frac14\,2^{-N}\).
In fact, no fixed positive approximation factor is achievable with polynomially many offers. For any proposed factor \(\alpha>0\), replace \(v_{qd}=\frac14\) by a fixed positive rational \(\eta<\min\{\alpha,1\}\). The optimum remains \(1\), while the same history gives final value at most \(\eta<\alpha\).
The [cited discrete theorem](https://www.ijcai.org/proceedings/2019/0019.pdf) treats students as individually listed agents. Here, exponentially large mass is represented by just two support entries, while each offer can inspect at most one unit of mass. That difference prevents its polynomial offer guarantee from extending to this model.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly: no deterministic policy with the required polynomial offer bound can guarantee one half of the optimum. The proof establishes an exponential lower bound on offers, independently of computational power. No major or minor mathematical gaps were found.
For every integer \(N\geq 1\), the construction satisfies the task’s requirements:
The encoding claim \(L_N=O(N)\) is correct: the growing integers have binary representations of length proportional to \(N\), while the remaining data have constant size.
Assigning the unit mass with acceptable set \(\{d,h\}\) to \(h\) satisfies every assignment constraint and attains value \(1\).
Conversely, total assigned mass is at most \(\kappa=1\), and each assigned unit has value at most \(1\). Thus \(\operatorname{OPT}(\nu)=1\). Both bounds are justified.
The induction preserves the stated invariant.
Every legal offer has mass \(s\leq 1\), because offered mass cannot exceed residual total capacity. This remains true even after arbitrarily many rejected offers.
For an offer from a cohort with nonempty history, the induction hypothesis guarantees that the entire cohort has complete type \((q,1)\).
For an offer from the untouched cohort, the range \(t+1\leq 2^N-1\) gives
\[
2^N-1-U_t\geq 2^N-1-t\geq 1.
\]
Consequently, that cohort contains enough type-\((q,1)\) mass to supply the entire offered mass \(s\). The update \(U_{t+1}=U_t+s\leq t+1\) is correct. If the offer comes from a previously touched cohort, \(U_t\) remains unchanged and still satisfies the invariant.
The response rules follow directly from \(A_{q,1}=\{d\}\): offers of \(d\) are fully accepted, and offers of \(h\) are fully rejected. Accepted mass leaves the unmatched population; rejected mass has nonempty history and consists only of type \((q,1)\).
The adversary does not change the hidden society. Each step partitions existing rational masses within existing cohorts, leaving all type-\((q,2)\) mass untouched. This is precisely the adversarial selection permitted by the task.
The endpoint is also correct: before offer \(2^N-1\), at least one unit of low type remains untouched. No further offer is covered by the lemma.
A polynomial offer bound in \(m,\tau,L\), restricted to \(m=\tau=2\) and \(L_N=O(N)\), yields an upper bound of the stated form \(B_N=\lceil C(N+1)^a\rceil\).
For sufficiently large \(N\), \(B_N\leq 2^N-1\). The lemma therefore supplies an admissible response history throughout the policy’s permitted execution.
On this history, all accepted mass is assigned to \(d\). Total accepted mass is at most \(1\), so final value is at most \(1/4\), strictly below \(\operatorname{OPT}(\nu)/2=1/2\).
The quantifiers are correct: for any purported policy, the prover chooses a sufficiently large instance and an admissible history on one fixed hidden society that defeats its guarantee. The argument does not require the policy to know the hidden support.
Response encoding length \(H\) cannot evade the contradiction because the task’s offer bound is polynomial in \(m,\tau,L\), independently of \(H\).
The exponential offer statement follows from the lemma: any terminating policy guaranteeing one half cannot stop anywhere along the first \(2^N-1\) adversarial responses.
The normalization claim is valid. Scaling masses and capacities by \(2^{-N}\) preserves the relevant inequalities and scales all assignment values by the same factor. The scaled data still have encoding length \(O(N)\).
For any fixed \(\alpha>0\), choosing a fixed positive rational \(\eta<\min\{\alpha,1\}\) preserves the optimum \(1\) and makes the adversarial final value at most \(\eta<\alpha\). Thus the stronger impossibility claim is also established.
The comparison with the discrete model is accurate: the cited paper represents students individually and makes fixed offers to individual students. This comparison is explanatory; the continuous lower bound does not invoke the discrete theorem as a proof premise. [Cechlárová, Gourvès, and Lesca, *On the Problem of Assigning PhD Grants*](https://www.ijcai.org/proceedings/2019/0019.pdf).
None. No repair or additional lemma is needed.
The established result is an unconditional offer lower bound for this interaction model. It is not a computational hardness classification for a named complexity class.
⟨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.