Answer: \(\mathrm{NP}\text{-hard}\), already for \(k=2\), and for every fixed \(k\ge 2\).
Theorem 22 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor all k ≥2, top-k POSSIBLESET is NP-complete, NECESSARYITEM is coNP-complete, and NECES- SARYSUBSET is coNP-complete for balanced alternation policies.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite preference types \(T\) with rational masses \(\mu_t\), course types \(O\) with rational capacities \(\sigma_o\) satisfying \(\sum_{o\in O}\sigma_o=k\), strict rankings \(\succ_t\), and a distinguished type \(t^\star\), does there exist a finite-block priority word \(w:[0,1]\to T\) with rational breakpoints and type masses \(\mu_t\), whose alternating left-to-right and right-to-left scans allocate each infinitesimal agent an integral bundle of \(k\) distinct courses, such that every member of type \(t^\star\) receives exactly its top-\(k\) courses?
A society is given by its support: the list of \(\tau\) preference types \(T\) with positive binary rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible rankings.
The input also contains \(m=|O|\) courses with positive binary rational capacities \(\sigma_o\) satisfying \(\sum_o\sigma_o=k\), an integer \(2\le k\le m\), a strict ranking \(\succ_t\) of all courses for each type, and a distinguished type \(t^\star\in T\). Let \(L\) be the total input bit length.
Agents are positions \(x\in[0,1]\) with Lebesgue measure \(\lambda\). A priority word \(w:[0,1]\to T\) is constant on finitely many intervals with rational endpoints and satisfies \(\lambda(w^{-1}(t))=\mu_t\); types may occupy multiple intervals, with no prescribed bound on their number.
Starting with empty bundles, perform \(k\) complete scans of the same positions, increasing in odd rounds and decreasing in even rounds. At each position, assign its highest-ranked course having positive residual capacity and absent from its previous bundle.
Precisely, traverse intervals on which type and previous bundle are constant, assigning the chosen course to successive positions until that interval ends or its residual capacity reaches zero, then recompute the choice; assigning a course to mass \(d\) consumes capacity \(d\). Retain each position's bundle between rounds. A word is admissible only if almost every position receives one course in every round; null sets, including boundary points, are ignored.
Is deciding whether an admissible priority word exists that gives almost every agent of type \(t^\star\) exactly its top-\(k\) courses in \(\mathrm{P}\), with running time polynomial in \(m,\tau,k,L\), or is it NP-hard?
For finite agents and distinct indivisible items, giving a designated agent its top-\(k\) items under balanced alternation is NP-complete for every fixed \(k\ge2\). [Aziz–Walsh–Xia](https://cgi.cse.unsw.edu.au/~tw/awxijcai2015.pdf)
A continuum course draft with alternating priority scans and exclusion of previously received courses is already studied by [Budish–Cantillon](https://kylewoodward.com/blog-data/pdfs/references/budish%2Bcantillon-american-economic-review-2012A.pdf). No result settling this finite-block priority-existence decision problem was located.
The decision problem is NP-hard already for \(k=2\), even when all course capacities are equal. It is consequently NP-hard for every fixed \(k\ge 2\).
The reduction below adapts the exact-cover construction in [Aziz–Walsh–Xia, extended version, proof of Theorem 22](https://arxiv.org/pdf/1412.2226). The essential additional argument proves the reverse implication despite arbitrary splitting of preference types.
We reduce from Exact Cover by 3-Sets. Its input consists of a universe \(X\), with \(|X|=3h\), and triples \(S_1,\ldots,S_\ell\subseteq X\). The question is whether some \(h\) triples partition \(X\).
We may assume \(h\ge 1\), \(\ell\ge h\), and every element belongs to at least one triple. Instances violating these conditions are immediately decidable, so this restriction preserves NP-hardness.
Set \(n=1+4\ell+4h\) and \(\delta=1/n\).
Introduce the following supported types:
| Type | Number of such types | Mass of each |
|---|---:|---:|
| Distinguished type \(t^\star\) | \(1\) | \(\delta\) |
| Leader \(L_j\), for each triple | \(\ell\) | \(\delta\) |
| Follower \(H_{j,e}\), for each \(e\in S_j\) | \(3\ell\) | \(\delta\) |
| Element type \(X_e\), for each \(e\in X\) | \(3h\) | \(\delta\) |
| Guard type \(G\) | \(1\) | \(h\delta\) |
Their masses sum to \((1+4\ell+3h+h)\delta=1\). In particular, the guards form one supported preference type, which may be split arbitrarily in a candidate word.
Introduce courses \(a,b\), together with mutually disjoint sets:
Every course has capacity \(\delta\). Since \(\ell\ge h\), all these cardinalities are nonnegative. The number of courses is
\(\displaystyle m=2+\ell+3\ell+8h+h+(4\ell-h)=2n.\)
Thus their total capacity is \(2n\delta=2\), as required for \(k=2\).
For each element, define \(K_e=\{u_{j,e}:e\in S_j\}\). Fix arbitrary strict orders within all displayed sets. The rankings are:
| Type | Ranking |
|---|---|
| \(t^\star\) | \(a\succ b\succ\text{rest}\) |
| \(L_j\) | \(p_j\succ a\succ D\succ b\succ\text{rest}\) |
| \(H_{j,e}\) | \(p_j\succ u_{j,e}\succ a\succ D\succ b\succ\text{rest}\) |
| \(X_e\) | \(K_e\succ b\succ\text{rest}\) |
| \(G\) | \(a\succ P\succ E\succ b\succ\text{rest}\) |
Here “rest” lists every unlisted course in an arbitrary fixed strict order. These rankings are distinct: different groups have different first courses; followers have different second courses; element types have disjoint nonempty sets of first-ranked private courses; and the two types ranking \(a\) first have different second courses.
Write \(\mathcal K=P\cup U\cup D\). Its total capacity is \((4\ell+8h)\delta\).
The construction has polynomial size, and all masses and capacities have polynomial binary encoding length.
Suppose \(J\subseteq\{1,\ldots,\ell\}\) indexes an exact cover, with \(|J|=h\).
For each group \(j\), place its leader before its three followers. Construct the priority word in the following order:
Each ordinary type occupies an interval of length \(\delta\), and the guard interval has length \(h\delta\). Hence all endpoints are rational.
In the increasing first round:
These choices follow the displayed rankings: before the selected groups act, every course in \(P\cup U\), together with \(a\), has exhausted.
In the decreasing second round:
At this point, precisely the courses in \(F\) remain. The remaining positions belong to the \(3h\) element types and the \(4(\ell-h)\) members of unselected groups, totaling \((4\ell-h)\delta\). Their first-round courses have exhausted, so none of the remaining courses is excluded by their previous bundles.
Consequently, these positions consume the courses in \(F\), one interval of mass \(\delta\) per course. Everyone receives a course in both rounds. The word is admissible, and almost every distinguished agent receives \(\{a,b\}\).
Now suppose an arbitrary admissible priority word gives almost every distinguished agent \(\{a,b\}\). No restriction is imposed on the number or placement of intervals occupied by any type.
Every successful distinguished agent receives \(a\) first and \(b\) second. Indeed, if such an agent received \(b\) first, then \(a\), which it receives later, would still have positive residual capacity at its first choice. Since \(a\succ b\), that choice would be impossible.
The distinguished mass and both target capacities equal \(\delta\). Therefore:
Let \(\alpha\) and \(\beta\) be the essential infimum and essential supremum of the distinguished positions. Because their mass is positive, \(\alpha<\beta\).
In round one, \(a\) has positive residual capacity at every position \(x<\beta\): a positive mass of distinguished positions remains to its right. Since guards rank \(a\) first, almost all guard positions must therefore lie at or to the right of \(\beta\).
Course \(b\) remains available throughout round one. In round two, it remains available at every position \(x>\alpha\), because a positive mass of distinguished positions below \(x\) still awaits its second choice.
The rankings and the reservation of \(a,b\) imply:
For example, a group member’s courses ranked above \(b\), apart from the forbidden course \(a\), belong to \(\mathcal K\). Whenever \(b\) is available, choosing outside \(\mathcal K\) would therefore require choosing \(a\) or \(b\). The other assertions follow by the same direct comparison with the displayed rankings.
Define \(f_j\delta\) to be the total capacity of \(p_j\) allocated to guards, and put \(f=\sum_j f_j\). Then \(0\le f_j\le 1\).
The guards receive total course mass \(2h\delta\), whereas the entire capacity of \(E\) is \(h\delta\). Thus \(f\ge h\).
Let \(M\) be the total mass of group members positioned above \(\alpha\). Counting allocations from \(\mathcal K\), we obtain
\(\displaystyle (4\ell+8h)\delta\ \ge\ 4\ell\delta+M+3h\delta+f\delta.\)
The four terms on the right count group first choices, the specified group second choices, element first choices, and guard choices from \(P\), respectively. These are distinct allocation events. Therefore
\(\displaystyle M\le (5h-f)\delta\le 4h\delta.\)
Call \(j\) active if \(f_j>0\), and let \(s\) be the number of active indices.
Fix an active \(j\). Every guard allocation of \(p_j\) occurs after all first-round choices at positions below \(\alpha\): guards lie beyond \(\beta>\alpha\) in round one, and their second choices occur later still.
Consequently, \(p_j\) has positive residual capacity whenever a member of group \(j\) positioned below \(\alpha\) makes its first choice. All four group types rank \(p_j\) first, so all such positions receive \(p_j\).
If their total mass is \(B_j\), the capacity of \(p_j\) gives
\(\displaystyle B_j+f_j\delta\le\delta.\)
Group \(j\) has total mass \(4\delta\). Its mass \(M_j\) above \(\alpha\) consequently satisfies
\(\displaystyle M_j=4\delta-B_j\ge(3+f_j)\delta.\)
Summing over active groups yields \(M\ge(3s+f)\delta\). Moreover, \(f\le s\), since each \(f_j\le1\); together with \(f\ge h\), this gives \(s\ge h\). Hence
\(\displaystyle 4h\ge M/\delta\ge3s+f\ge4h.\)
All inequalities are equalities. In particular:
This is the step that rules out fractional selection of additional groups.
Fix an inactive group \(j\). Its leader lies below \(\alpha\), where course \(a\) remains available in round one. Since its ranking begins \(p_j\succ a\), and it cannot receive \(a\), its entire mass \(\delta\) receives \(p_j\). This exhausts that course.
No follower can therefore receive \(p_j\). Each follower also lies below \(\alpha\), and its ranking begins \(p_j\succ u_{j,e}\succ a\). Avoiding \(a\) forces its entire mass \(\delta\) to receive \(u_{j,e}\), exhausting that private course.
Thus no element type can receive a private course belonging to an inactive group. But every element type \(X_e\) receives a course in \(K_e\) in round one. It follows that \(e\) belongs to at least one active triple.
The active triples therefore cover all \(3h\) elements. There are exactly \(h\) such triples, each of size \(3\), so they form an exact cover.
This establishes the reverse implication for every admissible successful priority word, including arbitrarily split words.
For a prescribed \(k>2\), add \(k-2\) courses of capacity \(1\), ranked above every original course by every type, in the same strict order.
The first \(k-2\) rounds necessarily give every position these courses, one per round. Their capacities exhaust exactly at the ends of their respective rounds. The remaining two rounds operate on the original instance.
If those two rounds begin with a decreasing scan, reflect the word by \(x\mapsto1-x\). Reflection preserves masses, rational endpoints, admissibility, and bundles, and converts the two scans to increasing followed by decreasing.
Thus the padded instance is successful exactly when the original instance is successful. Its capacities sum to \(k\), and the distinguished target is exactly its top-\(k\) set. This proves NP-hardness for every fixed \(k\ge2\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes NP-hardness for \(k=2\), with equal capacities, and for every fixed \(k\ge2\). I found no major or minor issues requiring repair.
The construction satisfies the task’s restrictions.
The restrictions on the X3C instances exclude only immediately decidable cases and do not undermine the hardness reduction.
The cited [Aziz–Walsh–Xia extended version](https://arxiv.org/pdf/1412.2226) does contain the X3C construction in the proof of Theorem 22. The continuum reverse implication is established separately in the submitted argument; it does not depend on transferring finite-agent hardness without justification.
The proposed word is valid: its intervals have the required masses and rational endpoints.
The first-round allocation follows the rankings:
In round two, the remaining \(4h\) courses in \(D\) suffice for the selected groups. Their first-round courses in \(D\) are already exhausted, so bundle exclusion does not interfere. Guards then consume \(E\), and the distinguished type receives \(b\).
At that point, only \(F\) remains. Its capacity is exactly
\[
(4\ell-h)\delta,
\]
matching the remaining element and unselected-group mass. Their previous courses are exhausted and lie outside \(F\). Consequently, every remaining position can receive a second course.
The forward implication proves admissibility as well as distinguished-type success.
Section 3.1 is correct.
A successful distinguished agent cannot receive \(b\) before \(a\): receiving \(a\) later implies that \(a\) was available at its first choice, when its strict ranking would require choosing \(a\).
The distinguished mass equals each target capacity. Therefore its successful allocation exhausts all of \(a\) in round one and all of \(b\) in round two, leaving no positive-measure allocation of either course to another type.
The essential endpoint statements are also valid:
Thus guards must lie at or above \(\beta\), up to null sets. No connectedness assumption about distinguished positions is used.
All four allocation restrictions in Section 3.2 follow from the rankings and target reservation.
In particular, \(b\) is available throughout round one and during round-two choices above \(\alpha\). A group member choosing outside \(\mathcal K\) in those circumstances would have to pass over the available, unexcluded course \(b\). Element types similarly must choose from \(K_e\) in round one.
Guards lie above \(\alpha\), never receive \(a\) or \(b\), and therefore receive both courses from \(P\cup E\). Their total allocation is \(2h\delta\), while \(E\) has capacity \(h\delta\), establishing \(f\ge h\).
The inequality
\[
(4\ell+8h)\delta
\ge 4\ell\delta+M+3h\delta+f\delta
\]
counts distinct allocation events from \(\mathcal K\). In particular, first- and second-round allocations to the same position are distinct capacity consumption events. The resulting bound \(M\le4h\delta\) is correct.
Section 3.3 supplies the essential continuum argument.
For an active group, positive guard consumption of \(p_j\) occurs after every first-round choice below \(\alpha\). Capacity cannot increase, so \(p_j\) must still be available at all such earlier group choices. Every group member there consequently receives \(p_j\).
Hence
\[
B_j+f_j\delta\le\delta,
\qquad
M_j\ge(3+f_j)\delta.
\]
Summing over active groups gives \(M/\delta\ge3s+f\). Since \(f_j\le1\), one has \(s\ge f\ge h\). The displayed chain
\[
4h\ge M/\delta\ge3s+f\ge4h
\]
therefore forces equality throughout.
The stated consequences follow: \(s=h\), \(f=h\), every active \(f_j=1\), every active group lies above \(\alpha\), and every inactive group lies below it, all up to null sets. This argument permits arbitrary splitting of every supported type, including guards.
Section 3.4 is valid even if leaders and followers are interleaved.
An inactive leader lies below \(\alpha\), where \(a\) is available. Avoiding \(a\) forces its full mass to receive \(p_j\), exhausting that course’s capacity. Thus no follower or other type can receive positive mass of \(p_j\).
Each inactive follower must then receive its own \(u_{j,e}\), since otherwise it would choose the available \(a\). Its full mass exhausts that private course.
Consequently, element allocations cannot use private courses from inactive groups. Every element receives a course in \(K_e\), so every element belongs to an active triple. Exactly \(h\) active triples cover \(3h\) elements; their total cardinality is \(3h\), forcing an exact cover.
The padding argument is correct. Each universally preferred capacity-one course supplies an entire round. Previous-bundle exclusion then makes the next added course the common highest available choice.
After those rounds, the original courses and capacities are untouched, and previous bundles contain only added courses. The remaining two rounds therefore reproduce the original problem, with reflection handling the reversed starting direction.
Reflection preserves rational finite-block words, type masses, and admissibility. The padded distinguished target is precisely its top-\(k\) set.
The proof establishes NP-hardness, as requested. It makes no unsupported claim of NP membership.
Required repair: none.
⟨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.