d4-conf-atal-2010-0008 (d4-conf-atal-2010-0008)

Given \(M\) courses, fixed prices \(p\), and a finite set \(T\) of student types with rational masses \(\mu_t\) summing to \(1\), where each type has budget \(b_t\), additive values \(v_{tj}\), and a succinct permissible-schedule set \(\Psi_t\subseteq\{0,1\}^M\), compute for each type a utility-maximizing affordable schedule \(x_t\in\arg\max\{\sum_j v_{tj}x_j:x\in\Psi_t,\ p\cdot x\le b_t\}\), then output aggregate demand \(d_j=\sum_{t\in T}\mu_t x_{tj}\) for each course. Each unit of mass receives an integral schedule.

A society is given by its support: the list of the \(\tau\) student types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts represented types, not possible types.
There are \(m\geq1\) courses, fixed nonnegative rational prices \(p_j\), positive rational budgets \(b_t\), and nonnegative rational additive values \(v_{tj}\). All rationals use binary encoding.
An input bound \(1\leq k\leq m\) limits schedule size. Each permissible-schedule set is encoded by an explicit list \(\mathcal C_t\) of pairs \((S,c)\), where \(S\subseteq\{1,\ldots,m\}\) and \(c\in\{0,\ldots,|S|\}\): \(\Psi_t=\{x\in\{0,1\}^m:\sum_jx_j\leq k,\ \sum_{j\in S}x_j\leq c\text{ for every }(S,c)\in\mathcal C_t\}\). Thus the empty schedule is permissible.
Assume strict preferences: distinct schedules in \(\Psi_t\) have distinct additive utilities. Every member of type \(t\) receives the same integral schedule \(x_t\).
Compute \(x_t\in\arg\max\{\sum_jv_{tj}x_j:x\in\Psi_t,\ \sum_jp_jx_j\leq b_t\}\) for every type, and output these schedules and \(d_j=\sum_t\mu_tx_{tj}\). Let \(L\) be the total input bit length and \(C=\sum_t|\mathcal C_t|\).

Is this exact demand-computation problem solvable in polynomial time in \(m,\tau,k,C,L\), or is it NP-hard?

For discrete students, Othman–Budish–Sandholm (2010) assert that additive utility maximization cannot be represented by polynomially many constraints unless \(\mathrm P=\mathrm{NP}\), and establish NP-hardness of individual demand computation ([source](https://ericbudish.org/files/finding_approximate_competitive_equilibria.pdf)).
No separate complexity result for the precise finite-support mass formulation above was identified in the search.

Result. Exact demand computation is \(\mathrm{NP}\)-hard, even when \(\tau=1\), \(\mu_1=1\), \(k=m\), and \(C=0\). Thus it is not polynomial-time solvable in the stated parameters unless \(\mathrm P=\mathrm{NP}\). The reduction below explicitly preserves strict preferences.

Reduction. Use the standard \(\mathrm{NP}\)-complete decision version of binary-encoded \(0\)–\(1\) knapsack. Its input consists of positive integer weights \(w_1,\ldots,w_n\), nonnegative integer profits \(a_1,\ldots,a_n\), a positive integer capacity \(B\), and a positive integer threshold \(H\). The question is whether some \(x\in\{0,1\}^n\) satisfies
\(\sum_{j=1}^n w_jx_j\leq B\) and \(\sum_{j=1}^n a_jx_j\geq H\).

Construct a society with one represented type and set
\[ m=n,\qquad \tau=1,\qquad \mu_1=1,\qquad k=m,\qquad \mathcal C_1=\varnothing. \]
Set \(p_j=w_j\), \(b_1=B\), and, writing \(M=2^m\), set
\[ v_{1j}=Ma_j+2^{j-1}. \]

All these numbers are nonnegative integers, hence admissible binary-encoded rationals, and the budget is positive. Because \(k=m\) and the constraint list is empty, \(\Psi_1=\{0,1\}^m\). Consequently, the affordable schedules are exactly the feasible knapsack selections.

Strict preferences and preservation of the objective. For any schedule \(x\), define
\[ A(x)=\sum_{j=1}^m a_jx_j,\qquad T(x)=\sum_{j=1}^m2^{j-1}x_j. \]
Its utility is \(U(x)=MA(x)+T(x)\), with \(0\leq T(x)\leq M-1\).

First, if \(A(x)>A(y)\), integrality gives \(A(x)-A(y)\geq1\). Therefore,
\[ U(x)-U(y) =M\bigl(A(x)-A(y)\bigr)+T(x)-T(y) \geq M-(M-1)=1. \]
Thus higher original profit always means strictly higher utility.

Second, suppose \(U(x)=U(y)\). Then
\[ M\bigl(A(x)-A(y)\bigr)=T(y)-T(x). \]
The right-hand side has absolute value at most \(M-1\), while the left-hand side is an integer multiple of \(M\). Both sides must therefore be zero. Hence \(T(x)=T(y)\). Uniqueness of binary expansion implies \(x=y\).

Distinct schedules consequently have distinct utilities throughout \(\Psi_1\), as required—not merely among affordable schedules.

Let \(x^\star\) be the schedule returned by an exact demand algorithm. It maximizes original knapsack profit among affordable schedules: otherwise, an affordable \(y\) with \(A(y)>A(x^\star)\) would have \(U(y)>U(x^\star)\), contradicting optimality. Hence the original knapsack instance is a yes-instance exactly when \(A(x^\star)\geq H\).

Polynomial encoding and hardness conclusion. Although \(M\) has exponential numerical magnitude, its binary representation has only \(m+1\) bits. Each constructed value \(v_{1j}\) has \(O(m+\log(a_j+1))\) bits. The entire construction therefore has polynomial encoding length and is computable in polynomial time.

One call to an exact demand algorithm, followed by computing \(A(x^\star)\) and comparing it with \(H\), decides knapsack. A running time polynomial in \(m,\tau,k,C,L\) would therefore give a polynomial-time algorithm for an \(\mathrm{NP}\)-complete problem.

The mass formulation introduces no obstacle to this reduction: a support containing a single type of mass \(1\) is permitted, and its aggregate demand satisfies \(d_j=x^\star_j\). Thus even computing aggregate demand alone is hard on these instances.

The cited [Othman–Budish–Sandholm paper, Section 3](https://ericbudish.org/files/finding_approximate_competitive_equilibria.pdf) also identifies the connection to knapsack. The construction above supplies the strict-preference and encoding checks for the precise formulation in the question; it does not require their separate assertion about constraint representations.

Tractable boundary. For every fixed constant \(k\), exhaustive enumeration gives a polynomial-time algorithm. For each type, enumerate the \(\sum_{r=0}^k\binom mr\) schedules of size at most \(k\), check every listed constraint and affordability, and retain the schedule of greatest utility. Each check and comparison uses polynomial-time exact rational arithmetic. For fixed \(k\), the number of candidates is polynomial in \(m\).

Once the schedules are known, aggregation also takes polynomial time. Indeed, writing \(\mu_t=h_t/q_t\), the common denominator \(Q=\prod_tq_t\) has bit length at most the total input bit length. Each \(d_j\) can be expressed with denominator \(Q\) and numerator between \(0\) and \(Q\). The hardness concerns the general problem in which \(k\) is part of the input.

⟨structured verdict parsed — rendered above⟩

Verdict

The proof is correct and resolves the task. It establishes \(\mathrm{NP}\)-hardness of exact demand computation under every stated promise, including strict preferences. No major or minor mathematical gaps were found.

Step-by-step verification

• Source problem. The prover precisely states the standard binary-encoded decision version of \(0\)–\(1\) knapsack: positive integer weights and capacity, nonnegative integer profits, and a positive integer profit threshold. Its \(\mathrm{NP}\)-completeness is a valid standard theorem. The reduction uses this decision problem appropriately: an exact demand output supplies a selection whose original profit can be compared with the threshold.

• Admissibility of the constructed society. All target hypotheses are satisfied:

• One represented type with mass \(\mu_1=1\) gives positive mass and total mass \(1\).
• Setting \(m=n\) and \(k=m\) satisfies the schedule-size restriction for nonempty knapsack instances.
• The empty constraint list gives \(C=0\) and \(\Psi_1=\{0,1\}^m\).
• Prices \(p_j=w_j\) are positive rational numbers, and budget \(b_1=B\) is positive.
• Values \(v_{1j}=Ma_j+2^{j-1}\) are positive integers, hence admissible nonnegative binary-encoded rationals.

Consequently, affordability is exactly the original knapsack weight constraint. No additional permissible-schedule restriction changes the feasible selections.

• Perturbation range. The stated bound \(0\leq T(x)\leq M-1\) is correct: selecting all binary place values gives \(2^m-1=M-1\). It holds for every permissible schedule, including the empty schedule.

• Preservation of profit ordering. Because original profits are integers, \(A(x)>A(y)\) implies \(A(x)-A(y)\geq1\). The calculation

\[ U(x)-U(y)\geq M-(M-1)=1 \]

is correct. Thus the perturbation cannot reverse an original strict profit comparison. Zero profits and ties in original profit cause no failure.

• Strict preferences. If \(U(x)=U(y)\), the displayed identity equates an integer multiple of \(M\) with a number of absolute value at most \(M-1\). The only possible multiple is zero. It follows that \(T(x)=T(y)\), and uniqueness of the binary representation of these place-value sums implies \(x=y\).

This verifies the required promise on all of \(\Psi_1\), rather than only on affordable schedules. In particular, the reduction does not rely on an algorithm accepting inputs that violate strict preferences.

• Recovery of the knapsack answer. The argument that a utility maximizer also maximizes original profit is valid: any affordable selection with larger original profit would have larger constructed utility. Therefore, the equivalence between a yes-instance and \(A(x^\star)\geq H\) holds in both directions.

A maximizer exists because the feasible set is finite and contains the empty schedule. Strict preferences make it unique, although the profit-recovery argument itself only requires optimality.

• Encoding size and reduction time. The exponential numerical magnitude of \(M=2^m\) creates no encoding problem: its binary representation has \(m+1\) bits. The bound \(O(m+\log(a_j+1))\) for each constructed value is correct, including when \(a_j=0\). Writing all values and performing the required integer arithmetic take polynomial time in the source input length.

All target parameters, including the constructed total bit length \(L\), are polynomially bounded in that length. Computing \(A(x^\star)\) and comparing it with \(H\) also use polynomial-time integer arithmetic. Thus the stated single-call reduction establishes the claimed hardness of the computational output problem.

• Finite-support masses and aggregate demand. With one type of mass \(1\), the formula gives \(d_j=x^\star_j\) exactly. Hence the same reduction establishes hardness even when only aggregate demand is requested. The mass formulation does not weaken the conclusion.

• Fixed-\(k\) boundary. The enumeration argument is correct. For each fixed constant \(k\), the stated number of candidate schedules is polynomial in \(m\). Explicitly listed constraints can be checked in polynomial time in their input length, and exact rational affordability and utility comparisons have polynomial bit complexity. The empty candidate ensures that the procedure always has a feasible schedule to retain.

The claim is correctly restricted to fixed \(k\); it does not claim a uniform polynomial running time when \(k\) varies with the input.

• Aggregation bit complexity. The denominator-product argument is sound. The binary length of \(Q=\prod_t q_t\) is bounded by the total encoded denominator length, hence by \(L\). Positive masses summing to \(1\) ensure that every aggregate coordinate lies between \(0\) and \(1\), giving the stated numerator range. Exact aggregation therefore has polynomial running time and output length.

• External citation. Section 3 of the cited paper does identify additive demand maximization with knapsack optimization. The prover accurately describes that connection and does not depend on the paper’s separate constraint-representation assertion. [Othman–Budish–Sandholm, Section 3](https://ericbudish.org/files/finding_approximate_competitive_equilibria.pdf).

Feedback to the prover

No repair or additional mathematical clarification is required. The general hardness conclusion and the fixed-\(k\) tractability statement are both justified.

⟨structured verdict parsed — rendered above⟩