| paper | d4-conf-aaai-2021-0901 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1.1
statement extracted from the paper’s text layer
Given advertisers \(K\), types \(T\) with rational masses \(\mu_t>0\) summing to \(1\), pre-spend beliefs \(s_t\in\Delta_K\), per-capita budgets \(\beta_k\), nonnegative saliences \(a_u\) with \(\sum_u\mu_u a_u=1\), and a rational exact finite Friedkin–Johnsen quotient \(H\ge0\) with \(\sum_t H_{t,u}=1\), compute a pure Nash equilibrium in per-type spends \(b_{t,k}\ge0\) satisfying \(\sum_t\mu_t b_{t,k}\le\beta_k\). Define \(r_{t,k}(b)=(s_{t,k}+b_{t,k})/(1+\sum_{\ell\in K}b_{t,\ell})\), \(z_{u,k}(b)=\sum_t H_{t,u}r_{t,k}(b)\), and \(U_k(b)=\sum_u\mu_u a_u z_{u,k}(b)\); the output must satisfy \(U_k(b)\ge U_k(b'_{\cdot,k},b_{-k})\) for every advertiser \(k\) and every feasible unilateral deviation \(b'_{\cdot,k}\). Seek running time polynomial in \(K\), \(\tau=|T|\), and rational input bit length \(L\).
Keep the advertisers as finite strategic players; group receiver users into \(\tau\) structurally equivalent types carrying masses \(\mu_t\). Advertisers choose per-capita spends \(b_{t,k}\) under mass-weighted budgets, and a finite quotient influence map \(H\) determines weighted linear influence payoffs \(U_k\).
Covers Theorem 1.1’s equilibrium computation for linear payoffs and invites analogous existence, uniqueness, and no-regret results. It leaves out individualized node targeting in generic networks, the random-graph experiments, and instances without a small exact quotient.
The strongest mirror is the paper’s equilibrium computation in a large network where users fall into a small number of meaningful audience segments. The continuous object is the receiver population: a type \(t\) is a mass \(\mu_t\) of users with the same initial belief vector, the same role in the network’s influence dynamics, and the same payoff weight. Thus \(\sum_t\mu_t=1\), with \(\tau\) types potentially far fewer than the number \(N\) of users. This fits settings such as a large platform selling advertising by audience segment, where each segment has a stable mix of influence exposure and campaign spending is set per person in the segment.
My lead is Type-Compressed Continuous Influence Equilibrium. An instance has finitely many advertisers \(K\); rational type masses \(\mu_t\); initial beliefs \(s_t\in\Delta_K\); and a type-level Friedkin–Johnsen influence operator \(H\), supplied as a valid finite quotient of the network dynamics. Write \(H_{t,u}\) for the contribution of type \(t\)’s internal belief to type \(u\)’s limiting external belief, with \(\sum_t H_{t,u}=1\). Advertiser \(k\) has a per-capita budget \(\beta_k\). Its decision is a nonnegative per-person spend \(b_{t,k}\) for each type, subject to \(\sum_t\mu_t b_{t,k}\le\beta_k\). After spending, type \(t\)’s internal belief in advertiser \(k\) is
\[ r_{t,k}(b)=\frac{s_{t,k}+b_{t,k}}{1+\sum_{\ell\in K}b_{t,\ell}}, \]
and the limiting external belief is \(z_{u,k}(b)=\sum_t H_{t,u}r_{t,k}(b)\).
For nonnegative type saliences \(a_u\) with \(\sum_u\mu_u a_u=1\), let advertiser \(k\)’s payoff be \(U_k(b)=\sum_u\mu_u a_u z_{u,k}(b)\). These are linear, nondecreasing payoffs, and their sum is one because each type’s external beliefs lie in \(\Delta_K\). The question is: compute a pure Nash equilibrium, meaning a feasible spend profile \(b\) such that no advertiser can increase \(U_k\) by changing only its own per-type spending. The solution is the spend profile itself. With rational type-level inputs, the relevant size parameters are \(K,\tau\), and the input bit lengths, rather than \(N\).
This is a high-multiplicity regime when a finite counterpart has \(n_t\) users of each type, \(\mu_t=n_t/N\), and \(N\) is large relative to \(\tau\). Mass means share of the audience; spending is per person; and the objective remains each advertiser’s share of the network’s eventual influence. The network operator is a co-modification needed to describe interactions among continuum-sized segments. In this scenario, the core question—how advertisers allocate budgets against one another through Friedkin–Johnsen dynamics, and what equilibrium results—should be recognizable to the authors.
The anchor is Theorem 1.1, proved in this paper. It says that if the advertisers’ payoff functions are nondecreasing and convex and the game is constant-sum, a pure Nash equilibrium exists; if, additionally, all payoffs are continuous and strictly increasing and every node’s pre-allocation internal belief in every advertiser is nonzero, that equilibrium is unique. It also says that under the nondecreasing, convex, constant-sum conditions, repeated play with no-regret learning converges in average trajectory to a pure Nash equilibrium. Finally, when the payoffs are linear, a pure Nash equilibrium can be computed in polynomial time using convex programming. The theorem is a tractability anchor, not a hardness result; the paper gives no comparable named hardness result.
I expect this mirror to be Class A: tractable. For the stated segment-level game, the same convexity structure supports a finite-dimensional convex-programming approach. The expected running time is polynomial in the explicit type-level input, including the size of \(H\), \(\tau\), \(K\), and the rational bit lengths. This is a proposed extension of the paper’s theorem: the theorem itself proves the result for finite networks, not for this continuous type model.
The scope is the equilibrium claims in Theorem 1.1, especially polynomial-time computation with linear payoffs. It does not cover arbitrary network instances, or the experiments on random graphs. Further questions include whether the theorem’s uniqueness and no-regret claims extend under the same assumptions; how the type-level result relates to equilibria when finite populations allow individual targeting; and whether computation remains tractable with arbitrary convex payoffs or approximate type-level network models.
The soft spot is the segment-level action. The paper allows advertisers to spend different amounts on different nodes; this mirror lets them choose one per-capita amount per type. That is plausible for campaigns bought through audience segments, but it excludes individualized targeting within a segment. Likewise, the finite type model requires network dynamics to close over the type-level operator. The mirror is strongest in the regime where both features are part of the application; it should not be presented as a result about every large or irregular network.
I can make only a weak case against this mirror. The proponent’s anchor is real: Theorem 1.1 is a named computational result, and its equilibrium question survives the move to a population of audience segments. The paper’s political-campaign setting makes that scenario especially easy to motivate. The theorem’s existence, uniqueness, no-regret, and polynomial-computation claims all have recognizable type-level counterparts.
The strongest objection is that network position is part of a node’s complete type. In a generic network, nodes have different influence profiles and payoff weights, so preserving the Friedkin–Johnsen dynamics may require nearly one type per node. Then the proposed masses do not compress the instance. Requiring an exact finite quotient \(H\) avoids that problem only by restricting attention to networks whose nodes fall into a small number of structurally equivalent groups. A continuum version with arbitrary interactions instead needs a kernel and spending functions over a continuum; without a finite representation and an approximation criterion, that is not yet a computational problem with a stated input size.
That objection weakens against the best version of the mirror. A finite block network with many interchangeable users per block is a plausible regime, and \(H\) is a reasonable co-modification for representing their interactions. Per-capita budgets and type-level payoffs preserve the central question: how advertisers spend against each other as influence propagates. The fact that the resulting equilibrium problem may reduce to a finite quotient, or inherit the paper’s convex-programming method, does not make the mirror invalid. It would be a result about a restricted regime, not a collision with a continuous treatment already in the paper.
So the negative case is that the mirror’s reach may be narrow: generic network instances lack useful multiplicity, while broader continuum models need additional computational foundations. That does not defeat the exact-quotient scenario. I cannot honestly conclude that no worthwhile mirror exists in any scenario; this anchor survives the strongest objection I can support.
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.