| paper | Opinion Dynamics with Median Aggregation |
| authors | — |
| venue | AAMAS 2025 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 6.1
statement extracted from the paper’s text layer
Given \(\tau\) types with rational masses \(\mu_a\ge0\), \(\sum_a\mu_a=1\), intrinsic opinions \(s_a\), initial public opinions \(z_a^0\), rational weights, and block influences \(K_{ab}\), define \(M_\mu(z)=\min\{x:\sum_{a:z_a\le x}\mu_a\ge\tfrac12\}\). Each positive-mass type \(a\) asynchronously replaces its common public opinion by a best response minimizing \(\alpha_a|s_a-y|+\sum_bK_{ab}|z_b-y|+\gamma_a|M_\mu(y,z_{-a})-y|\). Find the minimum integer \(\delta^\star\ge0\) such that, after replacing every \(\gamma_a\) by \(\gamma_a+\delta^\star\), all equilibria reachable from \(z^0\) have the same global median \(M_\mu\).
A weighted block-network opinion game with type masses \(\mu\), state \(z\in\mathbb{R}^{\tau}\), lower weighted median \(M_\mu\), and block influence matrix \(K\); type \(a\)'s cost is \(\alpha_a|s_a-y|+\sum_bK_{ab}|z_b-y|+\gamma_a|M_\mu(y,z_{-a})-y|\), and an asynchronous move changes the whole positive-mass block.
The proposed cohort update is a coordinated bloc move: an individual clone would split its type and generally destroy the paper's two-phase state representation, so the claimed polynomial transfer is not established for the literal high-multiplicity asynchronous process.
fatal: False
The mirror covers the typed extremal-reachable-equilibrium subroutine of Theorem 4.3 and uniform median stabilization in Theorem 6.1; it also proposes a segment-budget analogue of Theorem 7.1 and Corollary 7.2. It does not separately mirror the exponential-equilibrium construction of Corollary 5.2 or the remaining structural statements.
The strongest positive case is a typed, block-network version of the paper’s median game. It continuizes the population, not the opinion space: opinions remain scalar and public, while the population is represented by rational masses.
Let \(A=\{1,\ldots,\tau\}\) be agent types, with rational masses \(\mu_a\ge 0\) summing to \(1\). A type contains its intrinsic opinion \(s_a\), initial public opinion \(z_a^0\), weights \(\alpha_a,\gamma_a\), and its complete local-interaction role. Write \(K_{ab}\) for the total influence that type \(a\) receives from type \(b\). A state is \(z\in\mathbb{R}^{\tau}\), and the global opinion is the lower weighted median
\[ M_\mu(z)=\min\left\{x:\sum_{a:z_a\le x}\mu_a\ge \frac12\right\}. \]
The cost of type \(a\) choosing \(y\) is
\[ \operatorname{cost}_a(y,z_{-a}) = \alpha_a|s_a-y| +\sum_b K_{ab}|z_b-y| +\gamma_a|M_\mu(y,z_{-a})-y|. \]
A type update replaces \(z_a\) by a best response, with the median recomputed after the update. Thus the population is a collection of anonymous cohorts, each representing many agents with identical intrinsic opinions, public opinions, weights, and local interaction roles.
This is plausible in a large online society or public-opinion system: millions of users fall into a moderate number of stable segments, and members of a segment receive the same local information channels and the same global poll. The regime is \(N\gg \tau\): for rational \(\mu_a=p_a/N\), clearing denominators gives \(p_a\) identical clones of type \(a\). The local graph is a block network or graphon-like interaction pattern. This is not a claim about arbitrary sparse networks, where every vertex may be a distinct type; it is a high-multiplicity regime in which repeated demographic and network roles are the meaningful objects.
My lead anchor is Theorem 6.1, proved in this paper. It states that the minimum uniform additive increase in all median weights \(\gamma_i\) that stabilizes the global median can be found in polynomial time.
The corresponding problem is Minimum Uniform Median Stabilization\(_\infty\).
An instance consists of the typed society above, with rational masses, rational opinions and weights, and an initial state \(z^0\). For an integer \(\delta\ge 0\), replace every \(\gamma_a\) by \(\gamma_a+\delta\). Consider all equilibria reachable from \(z^0\) by asynchronous type-level best-response updates. The task is to output
\[ \delta^\star = \min\left\{\delta\in\mathbb{Z}_{\ge 0}: M_\mu(z)=M_\mu(z') \text{ for every pair of reachable equilibria }z,z'\right\}. \]
A valid solution is \(\delta^\star\), together with the stabilized median if desired.
I expect this problem to be in Class A. The paper’s Theorem 4.3, also proved here, supplies the key subroutine: the ascending and descending 2-Phase algorithms compute the maximum and minimum reachable equilibria. Their proofs use monotonicity and weighted-median structure rather than the identities of individual agents. In the typed model, each cohort should move at most once in each phase, giving a polynomial dependence on \(\tau\), the number of interaction entries, and the encoding length. The median can take values only from the finite support
\[ \{s_a:a\in A\}\cup\{z_a^0:a\in A\}. \]
The dependence on \(\delta\) should therefore remain a monotone step function with polynomially many breakpoints, allowing the binary-search argument from Theorem 6.1 to survive. This is precisely the kind of continuous optimization gain the ChoCo programme is looking for: a large population becomes a small weighted optimization object, while the paper’s median-feedback dynamics remains recognizable.
A second, harder anchor is Theorem 7.1, proved here, together with its strengthening Corollary 7.2, also proved here: StableMedian is NP-complete, even when \(\beta=1\).
The natural mass analogue is Segment-StableMedian\(_\infty\). Its input is a typed society and a rational mass budget \(q\). A solution chooses a set of types \(S\subseteq A\) with
\[ \sum_{a\in S}\mu_a\le q \]
and a common \(\delta\ge 0\). Every member of each selected type receives the increased median weight \(\gamma_a+\delta\); all other types retain their original weights. The question is whether every reachable equilibrium has the same global median as the initial state:
\[ M_\mu(z)=M_\mu(z^0) \]
for every equilibrium \(z\) reachable after the intervention.
This is a segment-targeted rather than individually targeted intervention: a platform, broadcaster, or campaign can increase poll exposure for an entire demographic/network segment. Clearing denominators gives a finite high-multiplicity version in which selecting a type selects all identical clones of that role. The vertex, edge, and pivot gadgets in Theorem 7.1 survive this replication: the hardness is carried by the incidence pattern between vertex and edge roles, not by the number of named people. I therefore expect this integral-cohort version to remain NP-hard, a Class B mirror. Corollary 7.2 suggests that the hardness should persist even with unit local weights.
The fully divisible relaxation is a valuable further question: choose \(x_a\in[0,\mu_a]\) with \(\sum_a x_a\le q\), split each type into treated and untreated mass, and ask for stabilization. The vertex-cover reduction no longer transfers automatically once a type can be fractionally treated. That version might become a tractable fractional-cover problem, or it might expose a genuinely continuum-specific threshold hardness. It is exactly the sort of boundary question the programme should investigate.
This case covers the paper’s main stabilization results—Theorems 4.3 and 6.1 directly in the typed dynamics, and Theorem 7.1/Corollary 7.2 in the segment-intervention extension. It does not claim to continuize every statement in the paper, such as the exponential number of reachable equilibria.
The weakest point is the update semantics. A literal atomless population with unilateral individual deviations is not faithful: one individual has zero effect on the global median, so the median term becomes effectively exogenous and the paper’s reachability notion degenerates. The mirror therefore uses positive-mass cohort updates and block-structured local interactions. That is an explicit extension, not a disguised direct equivalence. The case for it is that cohort-level opinion updates and segment-level poll interventions are natural in the paper’s own applications, preserve its cost function, median feedback, equilibrium notion, and stabilization objective, and admit an exact rational-clone interpretation for synchronized high-multiplicity societies.
The strongest negative point is that the proposed mirror changes the strategic unit. This paper is not merely a weighted population model: its essential feedback is that one updating agent can change the median. That operation disappears under population continuization.
In an atomless population, a unilateral deviation has measure zero. Thus, for almost every state,
\[ M_\mu(y,z_{-i})=M_\mu(z) \]
for every action \(y\). The median becomes an exogenous target in the deviator’s cost, rather than the endogenous aggregate appearing in Proposition 3.2. Consequently the paper’s best-response correspondence, reachability relation, and equilibrium set are not preserved.
Clearing denominators does not repair this. If type \(a\) is expanded into \(p_a\) identical clones, one clone’s update produces \(p_a-1\) agents at the old opinion and one at the new opinion. The state immediately leaves the proposed diagonal representation \(z\in\mathbb{R}^{\tau}\). The correct state must record masses \(q_{a,x}\) of each type at each opinion, and a type may split and move repeatedly. The paper’s two-phase argument that each agent moves at most once therefore does not become an argument that each type moves once.
The only way to retain the proponent’s model is to require all members of a type to update synchronously. That is a coalition or bloc game: a positive-mass group controls its entire mass. Theorem 4.3 may well have a weighted analogue for that new game, but it is not a continuum limit of the paper’s asynchronous individual dynamics. Its apparent efficiency comes from replacing \(N\) strategic agents by \(\tau\) strategic blocs, not from continuizing the population while preserving the original strategic object.
The same defect defeats the proposed mirror of Theorem 6.1. Under atomless individual updates, uniform median stabilization concerns a fixed aggregate median and a different reachability process. Under individual clone updates, types split and the extremal reachable states are no longer represented by the proposed ascending and descending two-phase procedures. Under synchronized updates, Theorem 6.1 becomes a new bloc-stabilization theorem. The finite support of possible opinions does not solve this semantic problem.
Theorem 7.1 has an additional mismatch. The paper selects \(k\) named agents. In a normalized high-multiplicity population, \(k\) agents have mass \(k/N\), which vanishes as \(N\) grows. Selecting an entire type instead treats a positive-mass segment and changes the intervention problem. Selecting only part of a type is more faithful, but then treated and untreated members become distinct types, and the vertex-cover reduction no longer transfers automatically.
Nor does replication alone preserve the reduction. The gadgets depend on the particular incidence of vertex agents and edge agents. A complete type must include that local-interaction role. Preserving arbitrary incidences therefore requires essentially one type per relevant incidence pattern; collapsing them to \(K_{ab}\) erases which vertices cover which edges. Corollary 7.2’s unit-weight restriction does nothing to address this loss of identity.
A fractional segment intervention would be a legitimate new research problem, but it is precisely a new problem: it has divisible treatment, split cohorts, and a different control budget. One would need a new hardness or tractability result rather than inheriting Theorem 7.1.
Thus none of the proponent’s three anchors currently yields a population-only mirror of the paper. The proposed block model could be worthwhile as a new theory of coordinated cohort dynamics and segment control, but calling it a continuization of these results overstates the connection. The honest negative conclusion is therefore strong against the proposed mirrors, though the universal claim that no related bloc or mean-field model could ever be worthwhile is too strong to prove from this paper alone.
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.