d4-conf-aaai-2008-0177

The strongest positive case is a high multiplicity advertiser population. The many agents are advertiser accounts; a type is their complete bid tree, including its impression subsets, bids, and volume caps. Mass \(\mu_t\) is the fraction of accounts using type \(t\). A plausible regime is a network with many local franchise or merchant accounts choosing from a small menu of standardized campaign templates: \(N\) accounts, with \(N\gg\tau\). Accounts that differ in any modeled bid or cap are different types.

The network’s supply must scale with the population: let \(q_j\) be the forecasted supply of impression \(j\) per unit of advertiser population. A finite population of size \(N\) then has supply approximately \(Nq_j\). The paper already treats impression assignments as forecasted amounts or rates; that is useful here, but the continuized object is the distribution of advertisers.

My lead anchor is Proposition 1, proved in the paper. It says that when agents submit bid-tree valuations, the paper’s allocation LP has an integer optimal solution. In full, that LP maximizes total bid value subject to each agent’s volume cap at every bid-tree node, the supply limit for every impression, and nonnegative allocations. The proposition concerns the underlying efficient allocation problem, not just the LP encoding.

The corresponding continuous question is BidTree Mass-Welfare Allocation. An instance gives the impression set \(M\), a finite supported distribution of advertiser types \(\mu\), each type’s bid tree with bids \(b_{tS}\) and integral per-advertiser caps \(c_{tS}\), and per-capita supply \(q_j\). Here \(S\) is a node’s subset of impressions. The question is to find a welfare-maximizing assignment of bundles to the advertiser mass. Each account still receives an integral bundle \(B\in\mathbb Z_+^M\); the assignment may distribute a type’s mass among different bundles, so its type-level average can be fractional.

Equivalently, let \(y_{tj}\) be the total amount of impression \(j\) allocated to type \(t\), measured per unit of the whole population, and write \(y_t(S)=\sum_{j\in S}y_{tj}\). The compact allocation problem maximizes \(\sum_t\sum_S b_{tS}y_t(S)\), subject to \(y_t(S)\leq\mu_t c_{tS}\), \(\sum_t y_{tj}\leq q_j\), and \(y_{tj}\geq0\). With the bid-tree constraints, the per-account feasible bundle polytope is integral, so a feasible type-level average can be implemented by distributing mass over integral bundles.

I expect this mirror to be Class A: the type-level problem is a rational LP of size polynomial in \(m\), \(\tau\), the bid-tree descriptions, and the input bit length. The continuous question is not whether the mass allocation remains integral; it is whether the same efficient-allocation objective can be solved from a compact distribution of types, with complexity governed by \(\tau\) rather than the number of advertiser accounts. Proposition 1 supplies the exact bid-tree allocation structure to continue, though its integral-optimum conclusion itself does not carry over as the target.

A second, related anchor is Proposition 2, also stated and derived in the paper by LP duality. It says that if \(x\) is an optimal solution to the allocation LP and \(p\) is an optimal dual solution, then \(\langle x,p\rangle\) is a competitive equilibrium: each bidder receives a utility-maximizing bundle at prices \(p\), and any impression with unallocated supply has price zero.

Its mirror is BidTree Mass Competitive Equilibrium. On the same input, find nonnegative prices \(p_j\) and, for every type, a distribution of its mass over integral bundles such that every bundle receiving positive mass maximizes that type’s bid-tree value minus \(p\cdot B\); total assigned mass respects each supply \(q_j\); and any impression with slack supply has price zero. I expect this to be Class A as well: solve the mass-welfare LP and take dual prices. In the continuum, agents of one type may divide among tied utility-maximizing bundles, giving the fractional type average while each assigned bundle remains integral.

The mirror covers the paper’s efficient allocation and its supporting competitive prices. It does not claim to mirror the scheduler, bidder-feedback result, or incentive analysis. Further questions include whether the continuous equilibrium price set retains the lattice property of Proposition 3; whether minimum CE prices retain the paper’s stability interpretation; and how well the mass solution approximates finite populations when type proportions or supplies must be rounded. If the impression space is represented more succinctly than its explicit \(m\) entries, the complexity of that representation is another natural question.

There is no named NP-hardness result in this paper to anchor a hardness mirror. Its statement that combinatorial allocation can be NP-hard is background, not a result about this bid-tree problem. So this is a tractability and scaling case, not a claim that continuization dissolves hardness.

The weakest point is that exact repetition of bid trees may be uncommon in a heterogeneous ad market. If nearly every account has unique bids or caps, then \(\tau\) approaches \(N\) and the compression buys little. Also, the integer-allocation statement in Proposition 1 is not needed to solve the fractional type-level LP. The case still holds in a standardized-template regime: advertisers share the paper’s full modeled preferences and constraints, while population mass replaces an unwieldy list of repeated accounts. That makes this a sensible high-multiplicity mirror, though a modest one.