d4-conf-aaai-2022-1496

The strongest computational anchor is Lemma 2, proved in this paper. It says that, for a fixed set of participants \(N'\), both the I-critical and II-critical prices can be computed in polynomial time. An I-critical price \(p^*\) is one where total demand drops from above supply to at most supply: \(D(N',p^*)>m\ge D(N',p^*+\epsilon)\) for every \(\epsilon>0\). An agent is important when removing their demand would leave demand below supply while demand including them meets it: \(D-D_i<m\le D\). A II-critical price has no important agent at \(p^*\), but has one at \(p^*+\epsilon\) for every \(\epsilon>0\). The proof generates at most \(mn\) demand change points, sorts them, and scans them; its stated running time is \(O(mn^2)\). The paper proves this result here. It does not give a named NP-hardness result, so this algorithmic result is the right anchor.

My lead mirror is Mass-SNCA I-Critical Price. Consider a large sponsored-ad auction run by a platform with public daily spending caps and a referral network. Many advertisers may share a value per impression, a cap, and a referral role—for example, accounts in the same campaign and budget tier occupying the same position in repeated local referral networks. A type \(t\) is that complete record, including its network role; \(\mu_t\) is its fraction of the advertiser population. The support has size \(\tau\), with population size \(N\gg\tau\). Inventory scales with the market: there are \(Nq\) units for rational supply density \(q>0\). This uses the public-budget ad-auction setting the authors themselves identify, while making the repeated-cohort assumption explicit.

Given the active type masses, reserve price \(v_s>0\), and supply density \(q\), define per-capita demand at price \(p\) as
\[ D_\mu(p)=\sum_t \mu_t\,\mathbf{1}[p\le v_t]\left\lfloor\frac{b_t}{p}\right\rfloor. \]
This is the large-\(N\) demand: for sufficiently large replicated markets, each buyer’s budget-limited demand is below total inventory, so the finite-market cap of \(Nq\) units per buyer does not bind. The problem is to return the exact rational price \(p^*\) at which \(D_\mu(p^*)>q\) but \(D_\mu(p^*+\epsilon)\le q\) for every \(\epsilon>0\). The price is the decision variable; the solution is the threshold, not an allocation or a mechanism.

This mirrors the I-critical-price computation in Lemma 2, not the whole SNCA. With \(K=\sum_t\lfloor b_t/v_s\rfloor\), demand changes only at values \(v_t\) and \(b_t/k\) for relevant positive integers \(k\). Sorting and scanning these events gives an exact algorithm polynomial in \(\tau\), \(K\), and the input bit length \(L\). I expect this problem to be tractable in that parameterization, the Class A direction suggested by the paper’s price computation. If budgets are binary encoded and \(K\) is large, this is only polynomial in a numeric parameter; obtaining a bound polynomial in \(\tau\) and \(L\) alone is a further question.

I would not claim that Lemma 2’s II-critical-price result transfers unchanged. In the continuum, one buyer has vanishing mass, so individual pivotality—the feature that defines an important agent—disappears. Treating an entire type cohort as one “important agent” would restore pivotality by changing what counts as an agent, and I do not think the paper’s authors should be expected to accept that as the same problem. The continuous mirror covers the I-critical half of Lemma 2; it does not claim a mirror of SNCA’s incentive-compatibility proof, network activation process, or welfare results.

The weakest point is that the price subproblem takes the active type masses as given and therefore leaves the network’s strategic activation rule aside. The repeated referral-motif regime is plausible for platform markets, but it is a constructed instance regime, not a claim that every social-network auction has few types. The natural next questions are whether the price computation can be polynomial in bit length without \(K\), and what replaces individual importance in a genuinely atomless, incentive-compatible clinching mechanism.