| paper | d4-conf-aaai-2020-1790 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite directed community template \(H\) with buyer roles \(V\), inviteable roles \(R_s\), and role values, consider \(N\) copies of \(H\) attached to a common seller. The seller assigns each copy an invitation pattern \(S\subseteq R_s\), with fraction \(\lambda_S\) of copies receiving that pattern, where \(\lambda_S\ge 0\) and \(\sum_S\lambda_S=1\). Let the supply be \(k_N\) units with \(k_N/N\to\kappa\), fix a deterministic role-based tie order, and run DNA-MU on the finite population. Does there exist a rational mass vector \(\lambda\) for which the limiting seller revenue per copy is at least \(Q\)?
A mass distribution \(\lambda\) over invitation patterns for repeated copies of a finite referral-network template, with role-level values and connectivity, per-copy supply rate \(\kappa\), and objective of maximizing limiting DNA-MU revenue per copy. In the fixed-size-copy limit, each individual’s descendants carry zero population mass in the price calculation.
In fixed-size repeated components, each buyer’s descendants have zero limiting mass, so DNA-MU’s descendant-based price adjustment disappears; the proponent flags this effect but does not establish whether authors would accept the resulting fluid rule as their mechanism.
fatal: False
The mirror covers Theorem 5’s seller revenue optimization. It leaves the strategy-proofness, efficiency, and mechanism-comparison results without a continuous question.
The strongest mirror is the paper’s OPTIMAL DIFFUSION problem, anchored in Theorem 5, proved by the authors. Given the number of units \(k\), a reported profile \(\theta'\), the seller’s direct buyers \(r_s\), and a threshold \(K\), the problem asks whether some subset \(r'_s\subseteq r_s\) makes the seller’s total revenue under DNA-MU at least \(K\). The paper proves this decision problem NP-complete by reduction from PARTITION; it gives a proof sketch here and defers the full proof to the full version. This is my lead anchor because the continuous question would ask directly whether that hardness survives when invitations can be chosen by mass.
A plausible high-multiplicity regime is an online marketplace serving many repeated referral communities: for example, large professional cohorts with similar buyer values and the same local referral pattern. Model one community by a finite directed network template \(H=(V\cup\{s\},E)\). Imagine a unit mass of isomorphic copies of \(H\), with one buyer per role \(u\in V\) in each copy. A type is a template role together with its valuation and referral behavior; across copies, buyers of the same role are indistinguishable for the auction’s connectivity and priority calculations. The number of buyers grows with the number of copies, while the number of distinct types is the number of roles and value classes. The seller knows the network, as assumed in the paper’s complexity problem.
Here is the continuous problem I would hand to a prover. Let \(R_s\subseteq V\) be the roles the seller can invite directly. The seller chooses a mass distribution \(\lambda_S\geq 0\), for \(S\subseteq R_s\), with \(\sum_{S\subseteq R_s}\lambda_S=1\). Here \(\lambda_S\) is the fraction of communities in which precisely the roles in \(S\) receive the invitation. If \(\operatorname{Reach}_H(S)\) is the set of roles connected to the seller after inviting \(S\), the connected mass of role \(u\) is
\[
y_u(\lambda)=\frac{1}{|V|}\sum_{S:\,u\in\operatorname{Reach}_H(S)}\lambda_S.
\]
Take a per-community supply rate \(\kappa\), corresponding to \(k_n/n\to\kappa\) units across \(n\) copies. Run the fluid limit of DNA-MU on the connected role masses, using weighted order statistics for its prices and the template’s distance priority. The decision question, Continuous Optimal Diffusion, is: given \(H\), the role values, \(R_s\), \(\kappa\), and a revenue threshold \(Q\), does there exist \(\lambda\) whose resulting DNA-MU revenue per community is at least \(Q\)? A solution is the invitation-mass vector \(\lambda\), together with its induced connected masses, allocations, prices, and revenue. Individuals remain unit-demand and receive either zero or one unit; only the aggregate mass of winners can be fractional. Scaling supply with population is the co-modification needed to keep the auction meaningful.
I would provisionally expect hardness to transfer for versions with unrestricted finite network templates. The reduction’s combinatorics appear to lie in which branches of the referral network become connected, not in the sheer number of people. Fractional invitation masses may still leave a hard optimization over reachable seed patterns. But Theorem 5 does not establish hardness for this continuous problem: one must show that mixing invitation patterns cannot erase the hard choice, or build a new reduction. The corresponding tractability question is whether the revenue calculation can be optimized over reachable-mass vectors with a polynomial pricing oracle. A useful bridge result would show how a continuous solution can be rounded to a discrete population with small additive revenue loss.
This mirror covers Theorem 5 and the underlying seller revenue-optimization problem. I would not extend it to the paper’s strategy-proofness or efficiency theorems; that would need separate models and arguments.
My weakest point is the fit between high multiplicity and network identity. Buyers in separate copies have different named followers, though their roles and neighborhoods are identical up to relabeling. More seriously, for fixed-size repeated communities, excluding a buyer’s descendants changes only a vanishing amount of population mass in the fluid limit. The local critical-descendant feature of DNA-MU therefore fades, even though seller-controlled reachability and aggregate competition remain. Authors could reasonably ask for a continuum network model that retains macroscopic descendant effects; for that, a finite support of network-role types may not suffice. This makes the case a qualified yes for repeated-cohort regimes, not a claim that arbitrary social-network auctions have a natural high-multiplicity limit.
The best objection is that OPTIMAL DIFFUSION is a problem about controlling one particular network, not simply choosing how much mass of each buyer type to reach. A buyer’s exact follower set affects connectivity and the diffusion critical tree; distance and priority affect allocation and prices. The proponent’s repeated-community model can compress isomorphic roles, but it also changes the setting: it turns one network into many components and lets the seller choose an invitation pattern for a fraction of those components.
That compression loses part of DNA-MU’s structure. In fixed-size communities, each buyer’s descendants have vanishing population mass, so excluding them from that buyer’s price calculation has no effect in the fluid limit. The rule’s network-dependent price adjustment disappears. If instead the network grows so that descendant sets retain positive mass, individual roles generally need more and more detailed network descriptions; a fixed finite set of types no longer captures them. The proposed model may still yield a useful revenue-optimization problem, but its connection to the paper’s unrestricted network problem becomes less direct.
The arbitrary tie-breaking among buyers at the same distance adds another complication. Repeating a template creates many buyers at equal distances. Preserving their exact priority requires tracking their order; replacing it with a fluid tie rule can change who wins at the supply cutoff. A natural mass-level rule may be reasonable, but it needs its own justification as a mirror of the authors’ mechanism.
Those objections do not defeat the strongest version of the mirror. A better candidate starts from the reduction itself: replicate its branch patterns, scale supply with population, and allow the seller to invite a fraction of the copies of each root role. The resulting mass choice could turn the reduction’s integer multiplicity choices into fractional ones. That is a coherent high-multiplicity question about whether the revenue hardness survives, and a tractable answer would be valuable to this programme.
So the negative case is weak where it must be strongest. The repeated-community proposal does not preserve every feature of the original mechanism, but the paper has a named computational result, and a reduction-shaped population model remains plausible. I cannot honestly argue that no worthwhile continuous mirror exists in any scenario. My case is limited to saying that the proponent’s particular construction needs a clearer account of priority and what network structure it preserves; it does not rule out the better mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.