| paper | d4-conf-ijcai-2025-0453 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. A deterministic polynomial-time mechanism achieves welfare exactly \(\mathrm{OPT}\) for every truthful-value profile and every invitation profile, with individual rationality and dominant-strategy truthfulness in joint individual value-and-invitation deviations. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.1
statement extracted from the paper’s text layer
Given \(k\) items, rational per-capita supplies \(q_j\), and a finite directed block network whose blocks have rational masses \(\mu_t\), values \(v_t\), desired bundles \(S_t\), and referral roles, does a polynomial-time mass extension of Net-\(\sqrt{k}\)-APM achieve welfare at least \(1/\sqrt{k}\) of the feasible mass-allocation optimum while remaining individually rational and dominant-strategy truthful in each bidder’s value and invitation choices? Each individual can invite an adjacent block, activating its positive mass; each served individual receives a whole desired bundle, and the mechanism may serve a fraction of each block. No budget-balance guarantee is required.
A dense block referral network with finitely many bidder types and rational mass, bundle, and per-capita supply data. Allocation variables are served fractions \(x_t\), constrained by \(\sum_t \mu_t x_t \mathbf{1}[j\in S_t]\le q_j\); individuals still receive whole bundles, and invitation decisions remain individual choices that can activate mass.
The paper’s strategyproofness argument concerns atomic bidders with named edges, while in a mass model a unilateral bid has zero aggregate effect and an invitation may activate positive mass. The threshold and payment arguments therefore need to be rebuilt, but that is the proposed research question rather than a reason to discard the dense block regime.
fatal: False
The mirror covers Theorem 5.1’s \(\sqrt{k}\)-approximate welfare, individual rationality, and strategyproofness claims; it does not cover the NSA guarantee in Theorem 5.2 or the paper’s general implementability characterizations.
The strongest positive case is narrow: a continuous version of the paper’s Net-\(\sqrt{k}\)-APM result for combinatorial network auctions with single-minded bidders.
My lead anchor is Theorem 5.1, proved in this paper. It states that Net-\(\sqrt{k}\)-APM achieves a \(\sqrt{k}\)-approximation to efficient welfare and is individually rational and strategyproof, but is not weakly budget balanced. The paper gives the mechanism: order bidders by bid divided by the square root of their desired bundle size, greedily allocate nonconflicting bundles, and use the ID-MON payment rule. The paper cites the NP-hardness of optimal single-minded allocation from earlier work; it does not give a numbered hardness result of its own. So this is an algorithmic anchor, not a hardness anchor.
A concrete mirror is Mass Net-\(\sqrt{k}\)-APM. An instance has \(k\) items, per-capita supplies \(q_j\), and a society distribution \(\mu\) over \(\tau\) bidder types. A type records a bidder’s value, desired bundle \(S_t\), and referral role: the network information relevant to whom they can invite. Use a finite typed referral network, with invitation reports and activation represented at the role level. The intended regime is large \(N\) and relatively small \(\tau\): for example, a high-volume crowdsourcing market with many bidders sharing package interests, values, and referral roles. Supplies scale with population, so the normalized feasibility condition is \(\sum_t \mu_t x_t \mathbf{1}[j\in S_t]\le q_j\).
The allocation variable \(x_t\in[0,1]\) is the fraction of type-\(t\) mass served. This is a type-level average: every individual still receives either the whole desired bundle or nothing. A solution must give a mechanism for reported bids and invitations, with feasible allocations and payments, such that truthful bidding and inviting all neighbors is a dominant strategy for each individual, truthful utility is nonnegative, and welfare at the truthful profile is at least \(1/\sqrt{k}\) of the continuous welfare optimum. The optimum is over feasible type-mass allocations. As in Theorem 5.1, the problem imposes no budget-balance guarantee.
The natural candidate is the mass version of the paper’s greedy allocation: process types by \(v_t/\sqrt{|S_t|}\), allocating as much of each cohort as remaining per-capita supplies permit. The mirror should also prove that this allocation is ID-MON under individual bid and invitation deviations, then apply the paper’s ID-MON payment construction. In Theorem 4.2, for an ID-MON allocation the revenue-maximizing IR and SP payment charges a winner \(v_i^*(\varnothing)\) and gives a loser the transfer \(v_i^*(\varnothing)-v_i^*(r_i)\); it maximizes revenue among IR and SP payments for that same allocation. The continuous problem asks whether the corresponding thresholds and transfers can be computed from the finite type-mass representation.
I expect this mirror to be Class A, with running time polynomial in \(k,\tau\), the input bit length \(L\), and the size of the typed network description. The type-mass allocation has finitely many variables, and the proposed greedy rule processes finitely many types. The hard part is showing that the mass-greedy rule retains the welfare guarantee and that referral deviations still satisfy the required monotonicity; this is a research question, not something Theorem 5.1 already proves.
This mirror covers Theorem 5.1’s approximate-welfare, IR, and SP result. It does not claim to continuize the paper’s separate NSA result, its full characterization of implementable allocations, or all network-auction mechanisms. Further questions include whether the \(\sqrt{k}\) guarantee is tight in the mass model, whether better welfare is possible under the same incentive constraints, and how to relate the continuous mechanism to finite markets with \(N\gg\tau\).
The weakest point is the network model. In the paper, invitation sets are sets of named neighbors in a finite graph. The proposed typed referral model groups structurally equivalent roles and represents invitations at the mass level. That is plausible for repeated network settings, but it is a real modeling extension: identity-specific edges or sparse referrals may not preserve the paper’s monotonicity arguments. I would accept the mirror only for the stated repeated-role regime.
Theorem 5.1 is a real algorithmic anchor: Net-\(\sqrt{k}\)-APM gives a \(\sqrt{k}\)-welfare guarantee with IR and SP, and Proposition 4.4 addresses payment computation. So the negative case cannot rest on there being nothing computational to mirror.
It rests on what makes that result a *network* auction. A bidder’s type includes \(r_i=N(i)\), and SP quantifies over that individual’s choices of which named neighbors to invite. Grouping bidders by value and desired bundle does not preserve those choices. Grouping them by “referral role” works only if the role representation also preserves who can reach whom, which invitations overlap, and how information propagates. In a sparse network, those details typically make agents’ roles distinct, so the number of relevant types can remain close to the number of bidders. The proposed compression then removes little of the instance the algorithm operates on.
The suggested mass-greedy mechanism also does not inherit the paper’s proof just by replacing bidders with cohorts. Its fractional \(x_t\) describes a share of a type being served; it does not specify which individuals win or what any one individual’s critical bid is. More fundamentally, a role-level invitation by a cohort is a collective action. It is not the paper’s unilateral deviation by one bidder. Under a sparse repeated-network model, one person’s invitations affect only a bounded number of other people; as the market grows, that change typically has vanishing effect on aggregate competition. The invitation incentive central to the paper’s SP result then becomes vacuous or disappears in the limit.
The best repair is a block or graphon model in which an individual can invite a positive mass of bidders, while cohorts retain whole-bundle outcomes and item supplies scale with population. That is mathematically coherent, and its mass allocation may be an LP. But it gives individuals macroscopic referral power, unlike the paper’s arbitrary finite graph of named neighbors. Keeping sparse referrals instead loses nontrivial invitation effects; keeping exact arbitrary edges retains an essentially individual network and its input size. The mirror thus faces a choice between a network limit that forgets the strategic feature and a new dense-network model that adds it back by assumption.
That defeats the proposed Mass Net-\(\sqrt{k}\)-APM as a faithful mirror, including its claim that the paper’s ID-MON payment construction carries over. It does not prove that every plausible dense-referral scenario would be uninteresting. A platform where users can broadcast invitations to whole cohorts might support a worthwhile continuous question. That remaining possibility is the weakness in the negative case: I can make a strong case against the natural sparse-network continuization, but not honestly rule out every meaningful network limit.
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.