| paper | Altruism, Collectivism and Egalitarianism: On a Variety of Prosocial Behaviors in Binary Networked Public Goods Games |
| authors | — |
| venue | AAMAS 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given finite behavioural types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), rational \(a\in(0,1)\), costs \(c_t\), and rational piecewise-linear nondecreasing benefit functions \(g_t:[0,1]\to\mathbb{Q}_{\ge 0}\), let \(T_+=\{t:\mu_t>0\}\), \(F_t(q)=g_t(q)+a\min_{s\in T_+}g_s(q)\), and \(q=\sum_t\mu_tz_t\). Decide whether there exists \(z\in[0,1]^T\), realizable by a measurable pure assignment, such that \(z_t=0\Rightarrow D^+F_t(q)\le c_t\), \(z_t=1\Rightarrow D^-F_t(q)\ge c_t\), and \(0<z_t<1\Rightarrow D^-F_t(q)\ge c_t\ge D^+F_t(q)\), where \(D^-\) and \(D^+\) are one-sided derivatives; output \(z\) if it exists.
An atomless complete-clique BNPG with finitely many behavioural types \(T\), masses \(\mu\), aggregate investment \(q\), and type payoff \(F_t(q)=g_t(q)+a\min_sg_s(q)\); the decision variables are \(z_t\) and \(q\), and the task is equilibrium feasibility.
The proponent's fixed \(\eta>0\) retains a finite pivotal agent, while sending \(\eta\to0\) makes unscaled positive costs dominate; a nontrivial benefit-cost normalization must therefore be specified.
fatal: False
Covers the repaired clique egalitarian equilibrium problem corresponding to Theorem 3; it leaves the general-network equilibrium results, all PNM results, and the other prosociality classifications untreated.
The strongest positive case is for the paper’s network-modification results, especially Theorem 6.
The natural regime is a large community deciding whether to adopt a shared public good: vaccination, mask-wearing, or participation in a city-wide emergency system. The relation graph is a clique because every participant benefits from the aggregate investment of the whole community. There may nevertheless be only a modest number of complete behavioural types: risk and cost sensitivity, baseline benefit function, and prosocial orientation. A population of \(10^6\) people divided among, say, a few dozen such types is a genuine high-multiplicity regime.
My lead problem is Continuous Type-Block Egalitarian PNM. An instance contains a finite type set \(T\), masses \(\mu_t\) with \(\sum_t\mu_t=1\), an effective individual contribution size \(\eta>0\), nondecreasing benefit functions \(g_t:[0,1]\to\mathbb{Q}_{\ge0}\), investment costs \(c_t\), an egalitarian coefficient \(a\), an initial symmetric prosocial type-network \(K_0\), allowable type-pair modifications with costs \(\kappa_{ts}\), and a budget \(B\). Every individual relation is present, while a prosocial edge \(\{t,s\}\) means that every member of type \(t\) regards the type-\(s\) cohort as part of their prosocial neighbourhood. The type-level restriction is important: a campaign connects cohorts or institutions, not individually named people.
The target is that all mass invests. If \(K'\) is the modified prosocial network, define
\[ F_{t,K'}(q) = g_t(q) + a\min_{s:\{t,s\}\in K'}g_s(q). \]
At the all-invest profile, a single individual’s investment changes the aggregate investment level from \(1-\eta\) to \(1\). Thus the target is a PSNE exactly when, for every type \(t\),
\[ F_{t,K'}(1)-F_{t,K'}(1-\eta)\ge c_t. \]
The decision problem asks whether there exists \(K'\) satisfying
\[ \sum_{\{t,s\}\in K'\triangle K_0}\kappa_{ts}\mu_t\mu_s\le B \]
and all the equilibrium inequalities. The solution is the modified type-network \(K'\), or a certificate that none exists.
This is a direct high-multiplicity version of the paper’s PNM problem. The anchor is Theorem 6, proved in this paper: for target \(x^\star=(1,\ldots,1)\), symmetric egalitarian PNM is NP-complete even when the relation graph is a clique. The theorem’s reduction can be blown up: replace every gadget vertex by a large cohort of identical agents, and every allowed edge by a cohort-level prosocial connection. The threshold inequalities are unchanged after normalizing masses and costs. The population can therefore be much larger than the number of types, while the SAT combinatorics remain in the type-level agenda. I would expect hardness to transfer, making this a Class B mirror rather than a case where continuity removes the difficulty.
The mirror is plausible because PNM is already presented by the authors as a policy problem involving campaigns, introductions, and community meetings. In the continuous version, those interventions naturally operate on cohorts rather than individuals. The continuous object is the population distribution \(\mu\), not a fractional outcome or a noise model.
A second worthwhile anchor is Theorem 3, proved here: when the relation graph is a clique, deciding whether a PSNE exists for egalitarian BNPG is solvable in \(O(|V|^2)\) time. Its continuous counterpart is Continuous Clique Egalitarian Equilibrium.
The instance again gives \(T,\mu,\eta\), benefit functions \(g_t\), costs \(c_t\), and a complete prosocial clique. A pure population strategy is a vector \(z\in[0,1]^T\), where \(z_t\) is the fraction of type-\(t\) mass investing. This is not a mixed strategy: one can realise \(z_t\) by assigning a measurable subset of type-\(t\) individuals to invest. Let
\[ q=\sum_{t\in T}\mu_tz_t \]
be the aggregate investing mass, and let
\[ F_t(q)=g_t(q)+a\min_{s\in T}g_s(q). \]
A type-\(t\) noninvestor must not gain by switching, so
\[ F_t(q+\eta)-F_t(q)\le c_t. \]
A type-\(t\) investor must not gain by withdrawing, so
\[ F_t(q)-F_t(q-\eta)\ge c_t. \]
If \(0<z_t<1\), both inequalities must hold, because both pure actions occur within that type. The problem asks whether such a vector \(z\) exists and, if so, outputs \(z\) together with the induced pure population assignment.
I would expect this to be Class A for the standard encoded version in which each \(g_t\) is piecewise-linear with polynomially many breakpoints, especially under the usual concave public-good utilities. The discrete clique proof scans possible aggregate investment counts; the continuous version scans intervals and breakpoints of \(q\), with fractional type mass eliminating subset-sum artefacts. This does not claim that every arbitrary succinct nonconcave extension is easy, but it is a credible continuous analogue of the paper’s tractable clique result.
A third, weaker but conceptually attractive mirror comes from Theorem 5, proved here: finding a PSNE in a collectivistic BNPG game is in PLS. The supporting results are Lemma 1, which identifies social welfare as an exact potential, and Theorem 4, which proves that a welfare-maximising PSNE always exists.
The continuous problem is Typed Collectivist Potential Equilibrium. Let \(T,\mu\) be the types and masses, let \(K_{st}=K_{ts}\) be a symmetric type-level interaction kernel, and let \(z_t\in[0,1]\) be investing mass. With
\[ r_t(z)=\sum_s K_{ts}\mu_sz_s, \]
define normalized social welfare by
\[ \Phi(z) = \sum_t\mu_t g_t(r_t(z)) - \sum_t\mu_tc_tz_t. \]
A type’s collectivist marginal utility is the directional change in \(\Phi\) caused by moving a small mass of that type from noninvestment to investment. A mass-action PSNE requires that this marginal be nonpositive for types assigned action \(0\), nonnegative for types assigned action \(1\), and zero for a split type. The problem asks for such a \(z\), preferably one maximizing \(\Phi\).
For concave piecewise-linear \(g_t\), \(\Phi\) is a concave function over a box, so the continuous problem is naturally solvable by convex optimization. Thus the discrete PLS/potential-game result points toward a Class A continuous formulation, while the unrestricted nonconcave version generates a useful boundary question: can the continuous collectivist problem become continuum-specifically hard?
These mirrors deliberately cover only the clique-based equilibrium and intervention results, not the paper as a whole. They do not claim that arbitrary network positions can be compressed into a small type set. Their strongest weakness is the treatment of prosocial links. If the continuum limit permits arbitrary infinitesimal individual links, egalitarian minimum terms can become degenerate: any positive link density may expose an agent to the same type-level minimum. The lead mirror therefore relies on a defensible institutional interpretation in which a type-pair link is a cohort-level intervention. If a referee rejects that interpretation, the PNM mirror weakens substantially. The clique equilibrium mirror survives more comfortably, because its high-multiplicity interpretation only requires common aggregate exposure and finitely many behavioural types.
The most useful follow-up questions are whether fractional prosocial-link densities yield an LP or a genuinely continuum-specific hard problem, whether the discrete-to-continuous rounding loss can be bounded as \(\eta\to0\), and whether the tree algorithms in Theorems 2 and 7 extend to typed tree-like interaction kernels.
The lead anchor, Theorem 6, does not survive the rational-clone test as stated. In the paper, PNM modifies edges between named individual vertices. The reduction encodes a satisfying assignment by selecting particular edges, and the budget counts those individual modifications. Cloning each vertex does not turn this into a type-level problem: the faithful blow-up still has choices among individual clone-to-clone edges. A type-level edge \(\{t,s\}\), by contrast, connects every member of cohort \(t\) to every member of cohort \(s\), with cost \(\kappa_{ts}\mu_t\mu_s\). That is a new intervention primitive, not a high-multiplicity encoding of the paper’s primitive.
This distinction matters especially for egalitarianism. One suitable prosocial neighbour can determine a player’s minimum, so a sparse set of individual links may suffice, whereas a complete cohort link adds many redundant links. Different partial link patterns have the same type-level description but can have different costs and different equilibrium effects. Allowing link densities does not repair this: for a minimum utility, any positive density can provide the full benefit, so with linear modification costs the infimum is often approached by densities tending to zero. Restricting interventions to all-or-nothing cohort links avoids that degeneracy only by changing the PNM problem into institutional type-network design. The fact that \(G\) is a clique does not help, because the reduction’s information is carried by the sparse prosocial graph \(H\).
There is also a more basic problem with the proposed \(\eta\)-formulation. At the all-invest profile, one individual changes the normalized aggregate from \(1\) to \(1-\eta\). For fixed continuous \(g_t\),
\[ g_t(1)-g_t(1-\eta)\longrightarrow 0 \]
as \(\eta\to0\), and the same is true of the egalitarian term under ordinary regularity. Thus positive investment costs eventually overwhelm the incentive to invest. Keeping \(\eta>0\) means retaining atoms and therefore a finite-population model; scaling benefits or costs with \(1/\eta\), or replacing individual deviations by positive-mass deviations, produces a different game. The proponent’s PNM question is therefore either a finite weighted restatement or a new cohort-deviation model, not a continuous mirror of Theorem 6.
Theorem 3 has a cleaner setting, but the same dilemma remains. Grant the strongest possible version: \(G=H\) is a complete clique, agents are partitioned into finitely many behavioural types, and \(z_t\) is a measurable pure assignment of actions within each type. In the genuine atomless limit, one player’s action does not change \(q\) at all. The paper’s PSNE condition is based on the finite differences at \(p-1\) and \(p\), precisely because one player is pivotal. The proponent’s inequalities retain this pivotality through \(\eta\). If \(\eta\) is removed, they become derivative or nonatomic best-response conditions; if \(\eta\) is retained, the model is just a finite clone model. A derivative-based mass-action equilibrium may be a sensible new mean-field problem, but it is not the computational problem in Theorem 3.
Theorem 5 is weaker as an anchor than the proponent suggests. Lemma 1’s exact-potential identity is a statement about finite individual deviations on a finite undirected graph. The proposed functional
\[ \Phi(z)=\sum_t\mu_t g_t(r_t(z))-\sum_t\mu_t c_tz_t \]
requires additional choices that are absent from the paper: a dense block-graph scaling, normalization of neighbour sums, treatment of the individual’s own contribution, and a symmetric type kernel. With binary \(z_t\), this is merely a finite type-compressed potential game. With fractional \(z_t\), it is a welfare relaxation or nonatomic variational model, not the paper’s PLS search problem over bit strings and one-player neighbours. The added concavity assumption makes \(\Phi\) amenable to convex optimization, but concavity is not assumed in the theorem; it supplies tractability by changing the model.
The common obstruction is that these results are not driven by population counts alone. They use individual network incidence, selected prosocial edges, and pivotal one-player deviations. A distribution over behavioural types forgets those objects unless they are reintroduced as a graph kernel, a distribution over neighbourhoods, or cohort-level intervention rules. Once they are reintroduced, the result is no longer a population continuization of the paper but a typed mean-field network game.
The negative case is therefore strong against the proponent’s claim that Theorem 6 gives a direct high-multiplicity mirror, and it also defeats the stated formulations of Theorems 3 and 5. It is not honestly airtight against every conceivable extension. A large complete community with finitely many behavioural types, normalized aggregate benefits, and an explicitly defined nonatomic equilibrium could be a worthwhile new computational public-goods model. But that would be a new ChoCo problem inspired by this paper, not a faithful continuous mirror of any of its named results.
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.