Mechanism Design Powered by Social Interactions: A Call to Arms

Theorem 1 and Theorem 2 are impossibility statements about mechanism properties, while Theorem 3 is a characterization theorem; none is a numbered computational result. Thus bit (a) fails, even though the proposed typed referral-tree model could motivate a separate high-multiplicity research problem. The opponent also identifies a genuine modeling gap: aggregate mass constraints do not preserve individual invitation deviations or network reachability.

The objection that survived

The proposed aggregate monotonicity condition replaces unilateral invitation incentives, while a type-mass vector omits overlapping reachability and permission paths.

What the mirror covers

The candidate covers only the coalitional/query-network discussion around Theorem 3; Theorems 1 and 2 and the remaining auction, matching, influence-selection, and cost-sharing material remain uncovered.

Open questions for a prover

The case FOR (proponent)

The strongest honest answer is a qualified one: the paper admits a credible population mirror, but it has no qualifying ChoCo computational anchor.

The paper’s Theorem 1 is an impossibility theorem cited from Rastegari et al. (2007); Theorem 2 is an impossibility theorem cited from Yang et al. (2022); and Theorem 3 is a characterization theorem cited from Zhang and Zhao (2022), not proved here. None asserts NP-hardness, membership in \(P\), approximation complexity, or parameterized complexity. Thus, strictly speaking, this paper cannot support a Class A/B/C verdict under the programme’s anchor rule.

The strongest provisional anchor is Theorem 3: “The weighted permission Shapley value mechanisms characterize all incentive compatible mechanisms in query networks under some mild conditions.” The underlying work models invitations through an acyclic network and uses weighted permission-Shapley rewards to make inviting neighbours incentive compatible. [Zhang and Zhao (2022)](https://arxiv.org/abs/2011.09049)

A precise provisional mirror would be Typed Query-Diffusion\(_\infty\). An instance contains a finite set \(T\) of complete network-role types; rational masses \(\mu_t\), with \(\sum_{t\in T}\mu_t=1\); a typed rooted invitation tree specified by the number \(b_{tu}\) of children of type \(u\) belonging to a type-\(t\) agent; rational contribution values \(a_t\); and rational reward weights \(\omega_t\). A type includes the agent’s depth, complete local permission pattern, contribution, and reward weight. Thus identical agents are genuinely interchangeable.

The intended regime is a large platform running standardized crowdsourcing or referral campaigns. Millions of participants occupy repeated roles in balanced invitation trees: the number of agents \(N\) is large, while the number of role types \(\tau=|T|\) is small. For example, all depth-three recruiters with the same number of child positions and the same contribution rule form one type. The mass \(\mu_t\) is their population fraction. Clearing denominators recovers a finite high-multiplicity tree.

The action variable is the mass of invitation edges activated from each type to each child type. A solution is a type-symmetric reward mechanism \(M\) assigning reward densities \(r_t(x)\) to active type masses \(x\), such that

\[ \sum_{t\in T} x_t r_t(x)=\sum_{t\in T}a_t x_t \]

for every feasible invited population \(x\), and such that inviting an available child never decreases the inviter’s reward:

\[ r_t(x+\varepsilon e_u)\ge r_t(x) \]

for every permitted type edge \(t\to u\) and feasible \(\varepsilon>0\). The problem asks whether such a mechanism exists and, if so, outputs its type-level reward rule. The intended solution family is precisely the weighted permission-Shapley family characterized by Theorem 3.

I would expect the fixed-template, additive version to be Class A: after aggregation, efficiency and diffusion-incentive constraints become finitely many type-level inequalities, and computation should depend on \(\tau\), the role-incidence description, and encoding length rather than on \(N\). The unrestricted DAG version, with variable overlapping permission paths and succinct coalition values, is a plausible Class C research problem; this paper gives no complexity result settling it.

The mirror is author-recognizable because it preserves their actual ingredients: invitation-dependent participation, network permissions, monotone coalition value, reward allocation, and dominant incentives to invite. It does not fractionalize the coalition itself; mass represents repeated agents occupying the same network role.

The weakest point is substantial: a pure atomless population makes unilateral invitations strategically vacuous, since one individual has zero mass. To avoid that, the proposed model is really a continuum of repeated finite network positions, or else it must replace individual deviations by positive-mass cohort deviations. That is an extension, not a literal direct mirror. Moreover, the mass vector \(\mu\) alone does not encode network topology; the typed incidence structure \(b_{tu}\) must be supplied separately.

So my positive case covers only the coalitional/query-network direction surrounding Theorem 3. It is a credible high-multiplicity research problem, probably tractable in restricted typed-tree regimes, but it cannot honestly be presented as a continuous computational mirror of a named complexity result from this paper.

The case AGAINST (opponent, writing after the proponent)

This paper should receive a negative verdict under ChoCo’s criteria. The decisive point is that it contains no qualifying computational result. Theorem 1 is a cited impossibility theorem about traditional combinatorial auctions, not about diffusion mechanisms. Theorem 2 is a cited impossibility theorem about incentive-compatible matching. Theorem 3 is a cited characterization of reward mechanisms. None states NP-hardness, polynomial-time solvability, approximation complexity, or parameterized complexity. The paper is a call for mechanism-design theory, not a complexity paper whose results invite continuization.

The proposed Theorem 3 mirror also fails as a faithful high-multiplicity model. In the paper, a player’s type includes \(r_i\subseteq N\), the player’s actual neighbor set. That is not merely a preference or valuation type: it is a relation to named vertices. A distribution \(\mu\) over role types does not determine which agents are connected, which paths overlap, which players can reach a given invitee, or which coalitions are connected. Those are exactly the facts on which diffusion incentives and permission Shapley rewards depend.

Adding the incidence numbers \(b_{tu}\) does not solve this. Two networks can have the same numbers of parents and children of every type while having different reachability, shared descendants, initial participants, and permission paths. To preserve those distinctions one must supply the whole typed graph, or a graph kernel describing how type instances connect. Then the continuous object is no longer a society distribution \(\mu\); it is a population plus a separate network structure. If vertex identities are retained, the number of relevant types generally grows with \(n\), defeating the fixed-type high-multiplicity regime.

The atomless formulation creates a deeper problem. In the source paper, an invitation is a unilateral action by a particular player that changes the participation and payment of particular other players. In the proposed model, changing \(x_u\) by an infinitesimal \(\varepsilon\) is a cohort deviation. It is not the deviation used in Theorem 3. The condition

\[ r_t(x+\varepsilon e_u)\ge r_t(x) \]

is therefore not a type-level form of dominant-strategy incentive compatibility; it is a new monotonicity requirement on aggregate rewards. The equation

\[ \sum_t x_t r_t(x)=\sum_t a_t x_t \]

likewise imposes aggregate budget balance but does not encode who invited whom or which permission paths generated the reward.

The best repair is to take a continuum of independent copies of a finite network motif, with each individual still able to invite a concrete child. That preserves unilateral incentives, but it makes the continuum only a bookkeeping device. If value and rewards are additive across copies, the mechanism problem decomposes into the finite motif problem and population mass merely scales totals. If copies interact, then their cross-copy graph and coalition structure must be represented, so \(\mu\) alone again becomes insufficient. Alternatively, one can permit positive-mass cohort deviations, but then the strategic concept is no longer the individual IC notion characterized by weighted permission Shapley values.

The same obstruction appears in the other named results. Theorem 1 concerns critical payments, revenue monotonicity, and false-name manipulation by particular bidders. In an atomless population, a single bidder or false identity has zero mass; making false names mass-bearing changes the problem. A repeated finite auction motif preserves the theorem only as a finite witness, without producing a continuous computational question. Theorem 2 is even more identity-dependent: matching assigns particular houses to particular agents, while stability quantifies over particular coalitions and, in the network version, connected subsets of a particular graph. A mass matching would either fractionalize the allocation—bringing in outcome-space continuity, which ChoCo excludes—or replace individual coalitional deviations by a new positive-mass notion.

The proponent’s claim that the fixed-template version should be Class A is also unsupported by Theorem 3. The theorem supplies a characterization under special query-network assumptions; it does not provide a finite inequality system for arbitrary typed networks, nor a pricing problem, nor an algorithmic complexity statement. In the special repeated-tree case, the weighted permission-Shapley rule is essentially already the prescribed mechanism. In the general case, the missing computation is precisely the network-dependent mechanism-design problem that the proposed type vector has abstracted away.

There is a real residual weakness in this negative case: one can invent a respectable research problem involving many repeated referral trees, typed local environments, and aggregate reward accounting. But that is either a decomposable replication of finite games or a new measure-valued network-mechanism theory. It is not a continuous mirror of a computational result in this paper. On the evidence available, ChoCo should not spend its effort on this paper as a continuization target.

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.