d4-conf-ecai-2016-0168 (d4-conf-ecai-2016-0168)

Given a finite set of student types \(T\), rational masses \(\mu_t\) summing to \(1\), seat types \(G\), a strict ranking and nonnegative rational additive utilities \(v_{tg}\) for each \(t\), rational per-student supplies \(s_g\) with \(\sum_{g\in G}s_g=R\) for an integer \(R\), and a rational threshold \(w\), does there exist a policy of \(R\) measurable measure-preserving orderings of an atomless unit population such that, in every round, each student takes their highest-ranked seat type still available and almost every student receives total utility at least \(w\)? Supplies are consumed by the induced mass-flow, while each individual receives an integral bundle.

Let \(G\) be a nonempty set of \(m\) seat types. A society is given by its support: the list of the \(\tau\) student types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has nonnegative rational additive utilities \(v_{tg}\) and a strict ranking of \(G\) in nonincreasing utility order, with utility ties resolved by the supplied ranking. Supplies \(s_g\geq0\) are binary rationals satisfying \(\sum_gs_g=R\), where \(R\geq1\) is a binary-encoded integer; the threshold \(w\) is rational.
Represent students by the Lebesgue probability space \(X=[0,1]\), partitioned into measurable type sets of masses \(\mu_t\). A policy consists of \(R\) independently chosen measure-preserving measurable bijections \(\sigma_r:X\to[0,1]\), understood modulo null sets; \(\sigma_r(x)\) is student \(x\)'s position in round \(r\).
Each student receives one whole seat per round; repeated seat types are allowed. For measurable picks \(a_r:X\to G\), the remaining supply at position \(u\) is \(q_{rg}(u)=s_g-\sum_{j<r}\lambda\{x:a_j(x)=g\}-\lambda\{x:\sigma_r(x)<u,\ a_r(x)=g\}\), where \(\lambda\) is Lebesgue measure.
A valid outcome has \(q_{rg}(u)\geq0\) for every \(r,g,u\), and almost every student picks their highest-ranked type with \(q_{rg}(\sigma_r(x))>0\). Supply persists between rounds; preferences do not change with earlier picks.
The decision problem asks whether such a policy and valid outcome exist with \(\sum_{r=1}^R v_{t(x),a_r(x)}\geq w\) for almost every \(x\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L,R\), accounting for the binary encoding of \(R\).

Is this continuous possible egalitarian welfare problem in \(\mathrm{P}\), with running time polynomial in the input length, or is it \(\mathrm{NP}\)-hard?

For finitely many agents and indivisible items, deciding whether sincere picking under recursively balanced policies achieves a given egalitarian welfare threshold is \(\mathrm{NP}\)-complete ([source](https://arxiv.org/pdf/1511.08280)). No result settling this exact atomless, integral-bundle formulation was located in the literature search.

The problem is \(\mathrm{NP}\)-hard, even with one student type, strictly ordered integer utilities, supply \(\tfrac12\) for every seat type, and \(R=m/2\). Consequently, it has no algorithm polynomial in the input length unless \(\mathrm{P}=\mathrm{NP}\).

The following reduction works directly in the atomless model.

1. Source problem and construction.

We reduce from PARTITION: given positive binary-encoded integers \(d_1,\ldots,d_n\), decide whether there is a subset \(I\subseteq\{1,\ldots,n\}\) satisfying

\(\displaystyle \sum_{i\in I}d_i=\frac12\sum_{i=1}^n d_i.\)

This is the classical \(\mathrm{NP}\)-complete problem established in [Karp’s *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Define

\(\displaystyle S=\sum_{i=1}^n d_i,\qquad C=S+1,\qquad b_i=(n-i)C,\qquad D=\sum_{i=1}^n b_i.\)

Construct a society with one student type of mass \(1\), and set \(R=n\). Introduce \(m=2n\) seat types

\(\displaystyle G=\{h_i,\ell_i:1\leq i\leq n\},\)

each with supply \(s_{h_i}=s_{\ell_i}=\tfrac12\). Their total supply is \(n=R\).

The single student type has utilities

\(\displaystyle v_{h_i}=b_i+d_i,\qquad v_{\ell_i}=b_i,\)

and ranking

\(\displaystyle h_1\succ\ell_1\succ h_2\succ\ell_2\succ\cdots\succ h_n\succ\ell_n.\)

This ranking strictly follows utility. Indeed, \(v_{h_i}>v_{\ell_i}\) because \(d_i>0\), and, for \(i<n\),

\(\displaystyle v_{\ell_i}-v_{h_{i+1}}=C-d_{i+1}>0.\)

All utilities are nonnegative integers. Set the threshold to

\(\displaystyle w=D+\frac S2.\)

No parity assumption on \(S\) is necessary: the threshold may be a half-integer.

2. Proven round-forcing lemma.

For every policy and valid outcome in the constructed instance, round \(i\) assigns \(h_i\) to almost every student whose position is below \(\tfrac12\), and assigns \(\ell_i\) to almost every student whose position is above \(\tfrac12\). Consequently, each of these seat types is assigned to mass \(\tfrac12\), and no other seat type is assigned in that round except possibly on a null set.

We prove this by induction on \(i\). At the beginning of round \(i\), the induction hypothesis gives zero remaining supply for every earlier pair and remaining supply \(\tfrac12\) for each seat type in the current and later pairs. These conditions hold initially for \(i=1\).

Because \(\sigma_i\) preserves measure,

\(\displaystyle \lambda\{x:\sigma_i(x)<u\}=u\qquad(0\leq u\leq1).\)

For \(u<\tfrac12\), the mass that has selected \(h_i\) before position \(u\) is at most \(u\). Hence

\(\displaystyle q_{i,h_i}(u)\geq\frac12-u>0.\)

Every earlier seat type has zero supply. Thus \(h_i\) is the highest-ranked available type, and sincerity forces almost every student with position below \(\tfrac12\) to choose \(h_i\).

It follows that, by position \(\tfrac12\), exactly mass \(\tfrac12\) has chosen \(h_i\). For every \(u\geq\tfrac12\), cumulative consumption of \(h_i\) is therefore at least \(\tfrac12\). Validity requires it to be at most its supply \(\tfrac12\), so

\(\displaystyle q_{i,h_i}(u)=0\qquad\left(\frac12\leq u\leq1\right).\)

For \(\tfrac12<u<1\), no positive mass selected \(\ell_i\) before position \(\tfrac12\). Its consumption before position \(u\) is thus at most \(u-\tfrac12\), giving

\(\displaystyle q_{i,\ell_i}(u)\geq\frac12-\left(u-\frac12\right)=1-u>0.\)

With earlier types and \(h_i\) exhausted, \(\ell_i\) is the highest-ranked available type. Sincerity therefore forces almost every student with position above \(\tfrac12\) to choose \(\ell_i\).

The exceptional positions have measure zero because \(\sigma_i\) preserves measure. Round \(i\) consequently exhausts exactly its own pair and leaves later pairs untouched. This establishes the induction.

3. Necessity: a feasible outcome gives a partition.

Suppose a policy and valid outcome give welfare at least \(w\) almost everywhere.

By the lemma, outside a null set every student receives exactly one of \(h_i,\ell_i\) in each round \(i\). Define \(z_i(x)=1\) when student \(x\) receives \(h_i\), and \(z_i(x)=0\) otherwise. Then

\(\displaystyle U(x)=D+\sum_{i=1}^n d_i z_i(x)\)

almost everywhere, and

\(\displaystyle \int_X z_i(x)\,d\lambda(x)=\frac12.\)

Therefore average welfare is exactly the threshold:

\(\displaystyle \int_X U(x)\,d\lambda(x)=D+\frac12\sum_{i=1}^n d_i=w.\)

The integrable function \(U-w\) is nonnegative almost everywhere and has integral zero. It must therefore vanish almost everywhere: otherwise some set on which \(U-w\geq1/k\) would have positive measure and give a positive integral.

Choose any student outside the null sets where the preceding conclusions fail. The subset

\(\displaystyle I=\{i:z_i(x)=1\}\)

satisfies

\(\displaystyle \sum_{i\in I}d_i=U(x)-D=\frac S2.\)

Thus the source PARTITION instance is a yes-instance. The whole-seat requirement is essential here: every \(z_i(x)\) is either \(0\) or \(1\).

4. Sufficiency: a partition gives an explicit valid policy.

Conversely, suppose \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}d_i=S/2\). Partition the population into

\(\displaystyle A=[0,\tfrac12),\qquad B=[\tfrac12,1),\)

ignoring the endpoint of measure zero.

For round \(i\in I\), use the identity order \(\sigma_i(x)=x\). For round \(i\notin I\), swap the two halves:

\(\displaystyle \sigma_i(x)= \begin{cases} x+\tfrac12,&0\leq x<\tfrac12,\\ x-\tfrac12,&\tfrac12\leq x<1. \end{cases} \)

Fix the endpoint \(1\). Each map is a measurable, measure-preserving bijection.

Assign \(h_i\) to students positioned below \(\tfrac12\), and \(\ell_i\) to the remaining students. To verify validity directly, the remaining supplies in round \(i\) are

\(\displaystyle q_{i,h_i}(u)=\max\{\tfrac12-u,0\},\qquad q_{i,\ell_i}(u)=\min\{\tfrac12,1-u\}.\)

Earlier pairs have remaining supply zero, while later pairs retain supply \(\tfrac12\) per seat type. Thus every remaining supply is nonnegative for every \(u\).

Before position \(\tfrac12\), \(h_i\) is the highest-ranked type with positive supply. From position \(\tfrac12\) to position \(1\), \(\ell_i\) is the highest-ranked type with positive supply. The assigned picks are therefore sincere almost everywhere.

Every student in \(A\) receives \(h_i\) exactly for \(i\in I\), so their welfare is

\(\displaystyle D+\sum_{i\in I}d_i=D+\frac S2=w.\)

Every student in \(B\) receives the complementary choices, giving welfare

\(\displaystyle D+\sum_{i\notin I}d_i=D+\frac S2=w.\)

This is the required policy and valid outcome.

5. Encoding size and running-time implications.

Let \(N\) be the source input bit length, and put

\(\displaystyle B=\left\lceil\log_2\!\left(n^2(S+1)+1\right)\right\rceil.\)

All constructed numerical values have \(O(B)\) bits. Successive additions compute the offsets and threshold, and the construction takes \(O(nB)\) bit operations with output length \(L=O(nB)\). Since \(n=O(N)\) and \(\log(S+1)=O(N)\), both bounds are polynomial in \(N\).

The target parameters satisfy

\(\displaystyle \tau=1,\qquad m=2n,\qquad R=n=m/2.\)

The binary representation of \(R\) uses only \(O(\log n)\) bits. In particular, the reduction never expands a binary-encoded, exponentially large number of rounds.

The two directions prove a polynomial-time many-one reduction from PARTITION. Hence the continuous possible egalitarian welfare problem is \(\mathrm{NP}\)-hard. Even a general running-time bound polynomial in \(m,\tau,L,R\) would imply \(\mathrm{P}=\mathrm{NP}\), because all four parameters are polynomially bounded on these constructed instances.

⟨structured verdict parsed — rendered above⟩

The reduction is sound and establishes \(\mathrm{NP}\)-hardness for the exact atomless, integral-bundle problem. The only issue is a minor endpoint misstatement in the sincerity verification; it does not affect the almost-everywhere requirement.

• Source problem and admissibility of the construction.

The source problem is stated precisely: PARTITION on positive binary-encoded integers. Its cited NP-completeness is the standard result, and the stated input satisfies its hypotheses. See [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Taking the source list to be nonempty, the construction has \(\tau=1\), \(m=2n\), and \(R=n\geq1\). The student mass is \(1\), and total supply is \(2n\cdot\tfrac12=n=R\). Thus the constructed instance satisfies the task’s mass, supply, and round-count requirements.

All utilities are nonnegative integers. Within each pair, \(d_i>0\) gives \(v_{h_i}>v_{\ell_i}\). Between consecutive pairs, the displayed difference \(C-d_{i+1}>0\) is correct because \(C=S+1\) and \(d_{i+1}\leq S\). The supplied ranking therefore strictly agrees with utility.

The threshold \(D+S/2\) is an admissible rational even when \(S\) is odd.

• Round-forcing lemma.

The induction is valid. Its initial condition follows from the specified supplies, and its induction hypothesis records exactly the consumption established in previous rounds.

Measure preservation gives the asserted prefix mass for every \(u\in[0,1]\). Before position \(\tfrac12\), consumption of \(h_i\) cannot exceed the entire prefix mass, so the lower bound on its remaining supply is correct. Earlier types have zero remaining supply, making \(h_i\) the highest-ranked available type. Sincerity consequently forces the asserted choices almost everywhere in that prefix.

The prefix below \(\tfrac12\) has mass exactly \(\tfrac12\), so its forced consumption exhausts \(h_i\). For every later position, monotonicity of cumulative consumption and the validity constraint give the claimed zero remaining supply.

Before position \(\tfrac12\), consumption of \(\ell_i\) has measure zero. Its subsequent consumption is bounded by the mass between positions \(\tfrac12\) and \(u\), yielding the correct bound \(1-u>0\) for \(u<1\). Sincerity then forces \(\ell_i\) throughout the remaining interval, almost everywhere.

The exceptional positions have null preimages under each measure-preserving map. Thus each round exhausts its own pair and leaves later pairs untouched. There is no circular use of the lemma.

• Necessity.

Since there are finitely many rounds, the exceptional sets can be combined into one null set. Outside it, the binary indicators \(z_i(x)\) describe exactly the assigned whole-seat choices.

The welfare identity and the marginal identities \(\int_X z_i\,d\lambda=\tfrac12\) follow from the lemma. The resulting average welfare is exactly \(w\).

The argument that a nonnegative integrable function with zero integral vanishes almost everywhere is correctly justified. Hence welfare equals \(w\) almost everywhere. The complement of the combined null set has measure \(1\), so choosing a student there is legitimate. That student’s binary choices give the required partition.

This direction correctly uses individual integral bundles; equality of average welfare alone would not supply the claimed subset without those binary choices.

• Sufficiency and validity.

The identity and half-swap maps are measurable, measure-preserving bijections with the stated endpoint convention. The picks defined from positions are measurable.

Both displayed remaining-supply formulas are correct for every \(u\in[0,1]\), including the boundary positions. Earlier pairs have zero remaining supply and later pairs retain their original supply. Consequently, validity holds at every position.

Minor issue: the sentence “From position \(\tfrac12\) to position \(1\), \(\ell_i\) is the highest-ranked type with positive supply” is imprecise if it includes position \(1\). The displayed formula gives \(q_{i,\ell_i}(1)=0\). The positivity assertion holds on \([\tfrac12,1)\). The endpoint has a null preimage, so the claimed almost-everywhere sincerity remains correct.

Minimum clarification: explicitly exclude position \(1\) from that positivity statement.

The identity rounds give \(A\) the high choice precisely for indices in \(I\); the swapped rounds give \(B\) the complementary choices. The two welfare calculations are correct, with the ignored endpoint covered by the almost-everywhere requirement.

• Encoding and complexity conclusion.

The stated \(O(B)\) bit bound covers the utilities, offsets, threshold, round count, and seat identifiers. Repeated additions suffice for the claimed \(O(nB)\) construction bound, including computing the offsets and their sum. The output-length bound is also consistent with the explicit ranking and numerical data.

Both \(n\) and \(\log(S+1)\) are polynomially bounded in the source input length. Therefore the construction is a polynomial-time many-one reduction.

The binary encoding of \(R\) is handled correctly: on these instances \(R=n=m/2\), so the reduction does not require expanding an exponentially large number of rounds. A running time polynomial in \(m,\tau,L,R\) would already solve these instances in polynomial time.

The proof establishes the requested NP-hardness conclusion. It makes no unsupported claim of membership in \(\mathrm{NP}\) or of strong NP-hardness.

⟨structured verdict parsed — rendered above⟩