d4-conf-aaai-2000-0231 (d4-conf-aaai-2000-0231)

Given \(m\) goods and \(\tau\) bidder types, each with an integer bundle \(q_t\in\mathbb{Z}_{\ge 0}^m\), a rational price \(p_t\ge 0\), and population mass \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), together with rational per-capita supplies \(s_g\ge 0\), choose accepted mass \(x_t\in[0,\mu_t]\) to maximize \(\sum_t p_t x_t\), subject to \(\sum_t q_{tg}x_t\le s_g\) for every good \(g\). Each accepted bidder receives their whole integer bundle; only the accepted mass of a type is fractional.

There are \(m\ge 1\) goods. A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts listed types, not possible types.
Type \(t\) submits one offer consisting of a nonempty integer bundle \(q_t\in\mathbb Z_{\ge 0}^m\setminus\{0\}\) and a price \(p_t\in\mathbb Q_{\ge 0}\). Supplies \(s_g\in\mathbb Q_{\ge 0}\) are per capita. Offers are additive; there are no constraints beyond the stated capacities.
Choose accepted masses \(x_t\in[0,\mu_t]\) to maximize \(\sum_{t=1}^{\tau}p_tx_t\), subject to \(\sum_{t=1}^{\tau}q_{tg}x_t\le s_g\) for every good \(g\). Every accepted bidder receives the entire bundle; only the accepted population mass is divisible. Goods may remain unallocated.
For the decision version, an additional threshold \(R\in\mathbb Q_{\ge 0}\) is given, and the question is whether feasible revenue is at least \(R\). All numerical inputs are binary encoded; \(L\) is their total bit length.

Is this revenue-threshold problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For discrete additive offers, CAMUS is guaranteed to find a revenue-maximizing feasible subset; its completeness guarantee is not a polynomial-time guarantee. [Source](https://cdn.aaai.org/AAAI/2000/AAAI00-009.pdf)
Nearby work studies fractional relaxations as bounds for discrete multi-unit winner determination, without explicitly formulating the supported population-mass problem above. [Source](https://arxiv.org/pdf/cs/0202016)

Conclusion

The revenue-threshold problem is in \(\mathrm P\), with running time polynomial in \(m,\tau,L\). Divisibility of the accepted population mass makes the stated problem an exact rational linear-feasibility problem.

1. Exact linear formulation

For each listed type \(t\), introduce one real variable \(x_t\), representing its accepted mass. Consider the following system:

• Population bounds: \(0\le x_t\le\mu_t\) for every \(t\in\{1,\ldots,\tau\}\).
• Supply constraints: \(\sum_{t=1}^{\tau}q_{tg}x_t\le s_g\) for every \(g\in\{1,\ldots,m\}\).
• Revenue threshold: \(-\sum_{t=1}^{\tau}p_tx_t\le-R\).

This system has exactly \(\tau\) variables and \(m+2\tau+1\) linear inequalities.

Equivalence. If the auction instance admits feasible accepted masses with revenue at least \(R\), those masses satisfy all the displayed inequalities. Conversely, any solution of the system gives allowed accepted masses, respects every supply constraint, and has revenue at least \(R\). Thus the answer to the decision problem is yes exactly when this system is feasible.

No additional integrality condition is needed. By the premises, every accepted member of type \(t\) receives the entire bundle \(q_t\), while the mass of accepted members may be any \(x_t\in[0,\mu_t]\). Its aggregate consumption is therefore exactly \(q_{tg}x_t\) for good \(g\).

2. Polynomial encoding size and exact decision

We use the standard polynomial-time linear-feasibility theorem: for a binary-encoded rational matrix \(A\) and rational vector \(b\), feasibility of \(Ax\le b\) over real variables can be decided deterministically in time polynomial in the dimensions and total encoding length. This is an exact feasibility theorem, applicable also to systems whose feasible sets have empty interior. See [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/eng/zvmmf5239).

We verify the encoding hypothesis explicitly. Let \(D\) be the product of the positive denominators of all rational numerical inputs. Because their binary encodings contribute to \(L\), the binary length of \(D\) is \(O(L+1)\). Multiplying every inequality by the positive integer \(D\) preserves feasibility and gives integer coefficients.

Every resulting coefficient has bit length \(O(L+1)\): each is \(D\) times an input rational, an input integer, or one of \(0,1,-1\). The augmented matrix consequently has encoding length at most

\(O\bigl((m+2\tau+1)(\tau+1)(L+1)\bigr).\)

Computing \(D\) and the scaled coefficients uses polynomially many operations on integers of polynomial bit length, so the construction itself takes polynomial time in \(m,\tau,L\).

Applying the linear-feasibility theorem therefore decides the original threshold problem in polynomial time. In particular, equality at the threshold is handled exactly; the argument does not depend on a numerical tolerance.

For completeness, the revenue maximum also exists. The original feasible set contains the zero vector, is closed, and lies inside the bounded box \(\prod_{t=1}^{\tau}[0,\mu_t]\). It is therefore compact, and the continuous linear revenue function attains its maximum.

3. Why the discrete-auction results do not imply hardness here

CAMUS concerns selecting a feasible subset of discrete bids, and its completeness theorem guarantees an optimal allocation in that setting. [CAMUS paper, problem definition and Theorem 2](https://cdn.aaai.org/AAAI/2000/AAAI00-009.pdf). The nearby work uses linear programming as a fractional relaxation to bound the discrete optimum. [Gonen and Lehmann, Section 2.2](https://arxiv.org/pdf/cs/0202016).

For the present model, the continuous variables are themselves the permitted decisions, so the linear formulation is exact.

A small instance makes the distinction explicit. Take \(m=\tau=1\), \(\mu_1=1\), \(q_{11}=2\), \(s_1=1\), and \(p_1=1\). Feasibility requires \(0\le x_1\le\tfrac12\), so the optimal revenue is \(\tfrac12\). Every accepted bidder still receives two units; only half the population is accepted. Replacing the permitted interval by the discrete requirement \(x_1\in\{0,1\}\) would instead give optimal revenue zero.

Thus the polynomial-time result applies to the full stated problem, with arbitrary binary-encoded quantities and prices and one variable per listed type.

⟨structured verdict parsed — rendered above⟩

Verdict

The prover resolves the stated problem correctly: the revenue-threshold problem belongs to \(\mathrm P\), with running time polynomial in \(m,\tau,L\). No major or minor mathematical issues were found.

Step-by-step verification

1. Exact formulation

The choice of one real variable \(x_t\) per listed type matches the task exactly. The permitted decisions are accepted population masses in \([0,\mu_t]\); no integer restriction on these masses is present.

All constraints are translated correctly:

• The population bounds impose precisely the permitted intervals.
• The supply inequalities account for aggregate consumption \(q_{tg}x_t\).
• The inequality \(-\sum_t p_tx_t\le -R\) is equivalent to revenue at least \(R\).

The count of \(\tau\) variables and \(m+2\tau+1\) inequalities is correct. Both directions of the feasibility equivalence follow directly from the stated definitions.

The explanation concerning whole bundles is also correct. Integer bundle quantities do not impose integrality on accepted population masses. No additional allocation restriction is assumed or required by the task.

Finding: Correct and complete.

2. Encoding size

The denominator-clearing argument is valid under the stated binary rational encoding.

The product \(D\) is positive, and its binary length is bounded by the sum of the input denominator lengths, hence by \(O(L+1)\). Multiplication by \(D\) therefore preserves each inequality’s direction and feasibility.

Every denominator divides \(D\), so the scaled coefficients are integers. Their bit lengths are \(O(L+1)\): multiplication adds operand bit lengths, and both the input numerators or integer quantities and \(D\) have bit length \(O(L+1)\).

The augmented matrix has \((m+2\tau+1)(\tau+1)\) entries. The stated encoding bound
\[ O\bigl((m+2\tau+1)(\tau+1)(L+1)\bigr) \]
is consequently correct. Computing the product and scaled entries requires polynomially many arithmetic operations on integers of polynomial bit length.

Finding: Correct; there is no hidden dependence polynomial in numerical values rather than their bit lengths.

3. Polynomial-time feasibility theorem

The prover states the needed theorem precisely: real feasibility of a binary-encoded rational system \(Ax\le b\) is decidable deterministically in polynomial time in its dimensions and encoding length.

This is the standard exact polynomial-time linear-feasibility theorem associated with [Khachiyan’s work](https://www.mathnet.ru/eng/zvmmf5239). Its hypotheses are satisfied by the constructed system:

• All coefficients and right-hand sides are rational, and become integer after scaling.
• There are finitely many variables and inequalities.
• The encoding length is polynomially bounded.
• The variables are real, as required.

The theorem does not require a nonempty interior. The prover correctly distinguishes exact feasibility from approximate numerical testing. Thus equality at the threshold causes no gap.

Finding: The theorem is correctly stated and applied.

4. Maximum existence and edge cases

The original feasible set contains the zero vector because supplies are nonnegative. It is closed, being defined by finitely many non-strict linear inequalities, and bounded by the population box. Compactness and attainment of the continuous revenue objective therefore follow correctly.

This paragraph concerns the original allocation constraints, not the threshold-augmented system, which may be infeasible.

The argument also covers zero prices, zero supplies, \(R=0\), thresholds exceeding attainable revenue, and feasible sets of lower dimension. Positive masses summing to \(1\) ensure a nonempty support; no unsupported case involving an empty society is used.

Finding: Correct; no missing edge case affects the conclusion.

5. Discrete-auction comparison

The contextual source claims are accurate. The [CAMUS paper](https://cdn.aaai.org/AAAI/2000/AAAI00-009.pdf) defines allocations through subsets of bids and states its completeness guarantee in Theorem 2. [Gonen and Lehmann, Section 2.2](https://arxiv.org/pdf/cs/0202016), use fractional linear programming to bound the discrete optimum.

The numerical example is valid. Its supply constraint is \(2x_1\le1\), so the continuous optimum is \(x_1=\tfrac12\), with revenue \(\tfrac12\). Under the separately imposed restriction \(x_1\in\{0,1\}\), only zero is feasible, giving revenue zero.

These observations support the distinction the prover draws; the polynomial-time conclusion itself rests on the exact formulation and feasibility theorem.

Finding: Correct.

Repair feedback

No additional clarification, missing lemma, or mathematical repair is needed. The proof establishes membership in \(\mathrm P\) for the full stated input model.

⟨structured verdict parsed — rendered above⟩