d4-conf-aaai-2005-0185 (d4-conf-aaai-2005-0185)

Given a finite support \(T\) of complete valuation types with positive rational masses \(\mu_t\), and explicit values \(v_t(B)\) for bundles \(B\subseteq M\), compute the limiting item baseline prices and bundle prices when the society is replicated to high multiplicity with fixed scarce supply. For each item \(\ell\), the price is \(p_\ell=\max_{t\in T}\max_{\substack{B\in\mathcal B_t\ \ell\in B}} v_t(B)/|B|\), taking the inner maximum as \(0\) if no such bundle exists; then \(p(B)=|B|\max_{\ell\in B}p_\ell\).

Let \(M\) be a set of \(m\geq 1\) items, with one unit of each item available. A society is given by its support: a list \(T\) of \(\tau\geq 1\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type supplies an explicit table of nonnegative binary rational values \(v_t(B)\) for every \(B\subseteq M\), with \(v_t(\varnothing)=0\) and free disposal. Values are private, utilities are quasi-linear, and there are no allocative externalities. Let \(L\) be the total input bit length, including these tables and masses.
Define \(\mathcal B_t=\{B\subseteq M:B\neq\varnothing\text{ and }v_t(C)<v_t(B)\text{ for every }C\subsetneq B\}\).
Replication means taking \(k\mu_t\) identical bidders of each type, along integers \(k\) making these counts integral, while retaining the fixed item supply.
The limiting prices to compute exactly are \(p_\ell=\max_{t\in T}\max_{B\in\mathcal B_t:\,\ell\in B}v_t(B)/|B|\), with an empty inner maximum equal to \(0\), and \(p(B)=|B|\max_{\ell\in B}p_\ell\) for nonempty bundles, with \(p(\varnothing)=0\). Compute every item price and every bundle price.

Is exact computation of these limiting prices possible in time polynomial in \(m\), \(\tau\), and \(L\), or is it NP-hard?

For finite bidders, the AM-MB ascending auction under straightforward bidding is known to converge, as the price increment tends to zero, to item baselines given by the second-largest bidder-specific maximum minimal-bundle average value. This is a convergence result, without a polynomial bit-complexity bound. [Source](https://cdn.aaai.org/AAAI/2005/AAAI05-042.pdf)
No result settling this exact support-and-mass pricing problem was located in the literature search.

Exact computation is polynomial-time solvable

With the stated explicit valuation-table representation, every item price and every bundle price can be computed exactly in time polynomial in \(m\), \(\tau\), and \(L\). The essential point is that the input already contains \(\tau 2^m\) valuation entries, so enumerating all bundles is polynomial in the input length.

1. Recognizing minimal bundles

Free disposal means that \(v_t(C)\leq v_t(D)\) whenever \(C\subseteq D\).

Lemma. For every type \(t\) and every nonempty bundle \(B\),
\[ B\in\mathcal B_t \quad\Longleftrightarrow\quad v_t(B\setminus\{\ell\})<v_t(B) \text{ for every }\ell\in B. \]

Proof. If \(B\in\mathcal B_t\), each \(B\setminus\{\ell\}\) is a proper subset of \(B\), so every indicated inequality follows from the definition.

Conversely, suppose all the indicated inequalities hold. Let \(C\subsetneq B\). Choose \(\ell\in B\setminus C\). Then \(C\subseteq B\setminus\{\ell\}\), and free disposal gives
\[ v_t(C)\leq v_t(B\setminus\{\ell\})<v_t(B). \]
This holds for every proper subset \(C\), proving \(B\in\mathcal B_t\). \(\square\)

Thus testing whether a bundle is minimal requires at most \(m\) comparisons of explicit table entries.

2. Exact algorithm and correctness

Index the valuation tables by the \(m\)-bit incidence vectors of bundles.

• Initialize \(p_\ell=0\) for every item \(\ell\in M\).
• For each type \(t\) and each nonempty bundle \(B\), use the lemma to test whether \(B\in\mathcal B_t\).
• Whenever the test succeeds, compute \(a_{t,B}=v_t(B)/|B|\). For each \(\ell\in B\), replace \(p_\ell\) by \(\max\{p_\ell,a_{t,B}\}\).
• Output the resulting item prices. Output \(p(\varnothing)=0\); for each nonempty \(B\), compute and output \(p(B)=|B|\max_{\ell\in B}p_\ell\).

By the lemma, step 3 processes exactly the pairs \((t,B)\) with \(B\in\mathcal B_t\). For an item \(\ell\), it processes exactly those pairs additionally satisfying \(\ell\in B\). Consequently, its final value is precisely
\[ p_\ell=\max_{t\in T}\max_{\substack{B\in\mathcal B_t\\\ell\in B}} \frac{v_t(B)}{|B|}. \]
If there are no qualifying pairs, the initialized value remains zero. Otherwise, initialization at zero does not affect the maximum because all values are nonnegative. Step 4 then evaluates the stipulated bundle-price formula exactly.

3. Polynomial bit complexity

Every explicit rational entry requires at least one bit. Hence \(L\geq\tau 2^m\), and in particular \(2^m\leq L\).

Testing all bundles uses at most \(\tau m2^m\) rational comparisons. Updating all item maxima uses at most another \(\tau m2^m\) comparisons. Computing all bundle prices uses at most \(m2^m\) comparisons and \(2^m\) multiplications.

These operations have polynomial bit complexity. To see this explicitly, write a valuation as \(v_t(B)=a/b\), with \(a\geq0\) and \(b>0\). Both integers have at most \(L\) bits. For \(s=|B|\), represent its average as \(a/(bs)\). Its numerator and denominator therefore have \(O(L+\log m)\) bits.

Compare two rational candidates by cross multiplication: \(a_1/d_1<a_2/d_2\) exactly when \(a_1d_2<a_2d_1\). All integers involved have \(O(L+\log m)\) bits, so ordinary integer arithmetic suffices in polynomial time.

Each maximum retains one existing candidate; taking maxima does not accumulate denominators. Finally, multiplying an item price by a bundle size adds at most \(O(\log m)\) numerator bits. Thus every output price has a representation of \(O(L+\log m)\) bits. Fractions can also be reduced in polynomial time if required.

Including bundle indices, the complete output has \(O(2^m(m+L+\log m))\) bits, which is polynomial in \(m\) and \(L\). Table indexing and all remaining bookkeeping likewise require polynomial time. Therefore the entire algorithm has polynomial bit complexity in the requested parameters.

4. Scope of the conclusion

The masses do not enter the prescribed price formulas. Their positivity specifies which types belong to the support; the algorithm need not construct replicated bidders.

The [cited auction convergence result](https://cdn.aaai.org/AAAI/2005/AAAI05-042.pdf) supplies context, but the complexity conclusion follows directly from evaluating the given formulas. The algorithm enumerates exponentially many bundles in \(m\), yet this is polynomial in the length of the explicit input tables.

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: proved. The output resolves the assigned problem under its explicit valuation-table representation. The algorithm computes the prescribed prices exactly, and its running time and output length are polynomial in \(m\), \(\tau\), and \(L\). No major or minor mathematical issues were found.

1. Minimal-bundle characterization

The lemma is correct in both directions.

• If \(B\in\mathcal B_t\), then each \(B\setminus\{\ell\}\), for \(\ell\in B\), is a proper subset of \(B\). The required strict inequality therefore follows directly from the definition.
• Conversely, for every proper subset \(C\subsetneq B\), the set \(B\setminus C\) is nonempty, so the indicated choice of \(\ell\) exists. Free disposal applies to \(C\subseteq B\setminus\{\ell\}\), giving

\(v_t(C)\leq v_t(B\setminus\{\ell\})<v_t(B)\).
This establishes the defining inequality for every proper subset.

The argument correctly includes the empty proper subset. For a singleton bundle, the test compares its value with \(v_t(\varnothing)=0\). Thus singleton bundles and zero-valued bundles require no omitted exception.

The bound of at most \(m\) table-entry comparisons per bundle is valid.

2. Algorithm correctness

The algorithm enumerates every type and every nonempty bundle and applies the proved characterization. Consequently, it processes precisely the pairs \((t,B)\) with \(B\in\mathcal B_t\).

For each item \(\ell\), updates occur precisely for those processed bundles containing \(\ell\). Each update takes the maximum of the current value and the prescribed candidate \(v_t(B)/|B|\). Since \(B\) is nonempty, division by \(|B|\) is well-defined.

Initialization at zero correctly handles both possibilities:

• If no qualifying pair exists for an item, its price remains zero.
• If qualifying pairs exist, all candidates are nonnegative, so initialization does not change their maximum.

Thus the computed item prices equal the task’s formulas. The final pass evaluates the stipulated bundle-price formula for every nonempty bundle and separately outputs the prescribed empty-bundle price.

There is no missing correctness argument involving masses or replication: the task explicitly supplies the limiting-price formulas, and those formulas depend only on the supported types and their valuations.

3. Enumeration and operation counts

The explicit input contains \(\tau 2^m\) rational valuation entries. Each entry requires at least one bit, so the stated inequality \(L\geq\tau 2^m\) is justified by the input representation.

The operation bounds are valid:

• Minimality testing uses at most \(\tau m2^m\) comparisons.
• Updating item maxima uses at most \(\tau m2^m\) comparisons.
• Evaluating all bundle maxima uses at most \(m2^m\) comparisons.
• Evaluating all bundle prices uses at most \(2^m\) multiplications.

Computing the averages also requires at most \(\tau 2^m\) denominator multiplications. Although not separately listed in the operation count, these operations are explicitly covered by the subsequent representation analysis and do not affect the polynomial bound.

Because \(\tau 2^m\leq L\), these counts are polynomial in the requested parameters.

4. Exact arithmetic and output length

For an input rational \(a/b\), the denominator is positive and both integers have at most \(L\) bits. Representing an average as \(a/(b|B|)\) adds at most \(O(\log m)\) denominator bits.

Cross multiplication correctly compares these rationals because their denominators are positive. The products have at most twice the operand bit length, which remains \(O(L+\log m)\). Standard integer arithmetic therefore implements each comparison in polynomial time.

The assertion that maxima retain existing candidates is correct. No repeated addition or denominator combination occurs, so the representation sizes do not grow with the number of comparisons. Multiplying a selected item price by a bundle size adds at most \(O(\log m)\) numerator bits. Optional fraction reduction is also polynomial-time.

The complete output-size bound
\(O(2^m(m+L+\log m))\)
is valid, including bundle identifiers. Since \(2^m\leq L\), it is polynomial in \(m\) and \(L\).

Table indexing is not an unsupported complexity assumption: indexing or arranging an already explicit table by incidence vectors requires only polynomial bookkeeping.

5. Scope and required feedback

The proof establishes exact polynomial-time computation for the representation specified in the task. It makes no unsupported claim about succinct valuation representations or the bit complexity of the ascending auction.

The cited convergence result is not used as a premise of the algorithm or its complexity proof, so no application of that result requires verification here.

Required repair or clarification: none.

⟨structured verdict parsed — rendered above⟩