| paper | d4-conf-ijcai-2019-0652 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Result 2 is a named computational hardness result, but its proposed mirror replaces individual choices responding to actual neighbors with mass splitting in response to aggregate type distributions. That changes pure Nash equilibrium into a nonatomic equilibrium, so the proposed problem does not preserve the anchored question and the paper’s hardness result does not carry over. The block model is a plausible extension of the paper, but that alone does not make it a surviving mirror of Result 2.
fails bit b-changes — the continuum limit changes the question
The proposed construction attempts to cover Result 2’s weighted equilibrium-computation hardness; it does not propose mirrors for Results 1, 3, or 4, and no result has a surviving population mirror.
My lead is a Block-Mean-Field Discrete Preference Game Equilibrium problem, anchored in the paper’s printed Result 2 in §1.1. The supplied text does not print a numeral on the corresponding formal theorem in §3, so I’m using its explicit numbered label. Result 2 says that computing an equilibrium in weighted discrete preference games is PLS-hard even when every player has constant degree, the strategy set has constant size, and the distances between distinct strategies are all either \(1\) or \(2\). This result is proved here, by reduction from local max-cut; the paper cites the degree-five local max-cut hardness used in that reduction.
Here is the continuous problem I would give a prover. An instance has a finite set of types \(T\), rational masses \(\mu_t\) summing to \(1\), and a finite metric space \((L,d)\). For the anchored version, \(L\) has constant size and distinct strategies are at distance \(1\) or \(2\). Each type \(t\) has a preferred strategy \(s_t\), a nonnegative preference weight \(w_t\), and rational symmetric influence intensities \(\lambda_{tu}=\lambda_{ut}\) toward other types. The type-interaction graph can be required to have constant degree. All these data are part of the type: agents of type \(t\) have the same preference and the same influence profile.
Let \(q_{t,a}\) be the fraction of the whole society consisting of type-\(t\) agents choosing \(a\), with \(q_{t,a}\ge 0\) and \(\sum_{a\in L}q_{t,a}=\mu_t\). Define a type-\(t\) agent’s cost of choosing \(a\) at population state \(q\) by
\[
c_t(a;q)=w_t d(s_t,a)+\sum_{u\in T}\sum_{b\in L}\lambda_{tu}q_{u,b}d(a,b).
\]
The problem, Block-Mean-Field DPG Equilibrium, is: given those rational data, find a rational array \(q\) satisfying the mass constraints such that \(q_{t,a}>0\) only when \(a\) minimizes \(c_t(a;q)\) over \(L\). A type may divide its mass across strategies, but only among tied best responses. The solution is the equilibrium allocation \(q\); there is no planner’s objective to minimize. With symmetric intensities the game has the potential
\[
\Phi(q)=\sum_{t,a}w_t d(s_t,a)q_{t,a}
+\frac12\sum_{t,u,a,b}\lambda_{tu}q_{t,a}q_{u,b}d(a,b),
\]
which helps characterize equilibria but is not a substitute for the equilibrium condition.
The regime is a large population in stable cohorts: for example, users choosing among a small set of platforms or policy bundles, where members of a cohort share a preferred option and the same aggregate exposure profile toward a few other cohorts. Each cohort might contain thousands of people. The total population can grow while the number \(\tau=|T|\) of distinct types stays fixed, so \(N\) can be much larger than \(\tau\); in complexity instances, \(\tau\) remains a parameter and may grow. The interaction intensities describe normalized exposure to type masses, as in a weighted block network. This retains the paper’s metric costs and equilibrium question while replacing individual neighbor lists with cohort-level influence.
I think the authors would recognize this as a continuous analogue of their weighted game: the same agents’ preferences, metric distances, and influence costs determine best responses, and the paper already allows weighted social ties. The necessary co-modification is that exposure is specified by type and scaled against population mass. In a finite block network, that corresponds to many agents per cohort with per-edge weights normalized so the total influence from a cohort stays bounded. This is not a claim that Result 2 already proves hardness for the continuum problem.
The main open question is the fate of that hardness. My provisional expectation for variable \(\tau\) is Class C, though with low confidence: the local-max-cut combinatorics can live in the interaction graph on types even when every type has large mass. But a fractional equilibrium can split a type across tied best responses, so the paper’s discrete reduction does not by itself transfer. A prover should determine whether such splits make the problem tractable, or whether a construction can force or recover discrete behavior and transfer hardness. Useful follow-ups are whether fixed \(\tau\) permits an efficient algorithm, whether every instance has an equilibrium using just one strategy per type, and whether a computed continuum equilibrium can be rounded to an approximate equilibrium in a large finite block population.
The mirror covers the weighted equilibrium-computation hardness in Result 2; it does not claim to mirror the directed nonexistence example or the tree- and product-metric algorithms. Its weakest point is that the original hardness reduction has a growing collection of distinct network roles. The continuous question retains those roles as types, so the number of people grows independently of the number of types, but the reduction’s combinatorics may still grow with \(\tau\). And unless fractional equilibria can be handled, the discrete hardness anchor does not settle the continuous problem.
The strongest anchor is genuinely computational: Result 2 proves PLS hardness for finding an equilibrium in weighted discrete preference games, even with constant degree, a constant strategy set, and distances only \(1\) or \(2\). The difficulty lives in an equilibrium of a player-by-player configuration on a social graph. A player’s best response depends on the actual strategies of her neighbors, and the reduction uses those graph positions as distinct roles.
The proponent’s block model is the best version of a mirror I can see. Large cohorts choosing among a few platforms, with stable aggregate exposure between cohorts, give a plausible population story. Its equilibrium condition is precise, and symmetric interaction intensities yield a potential. But the model gets a type-level state \(q\) by changing how the network works: each agent responds to aggregate mass, as in a normalized dense block network, rather than to a bounded set of actual neighbors. In a sparse graph, two agents with the same preferences and the same type-level neighbor counts can still face different neighbor strategies. Aggregate type masses do not determine either agent’s best response. Making types detailed enough to preserve those local neighborhoods tends to make them graph roles, rather than large interchangeable cohorts.
That difference also changes the computational object. In the paper, every player chooses one strategy and equilibrium means no individual can profitably deviate. In the block model, an equilibrium is a distribution over strategies in which each type puts mass only on best responses to the aggregate. Fractional splitting is part of the solution, and the local-max-cut reduction does not itself say what happens to those splits. This is more than a restatement of Result 2 over a continuum: it is a worthwhile-looking computational question about a related nonatomic game, but its connection to the paper’s hardness result is limited.
That is the negative case, and its limit is real. The paper studies weighted networks broadly, not only sparse ones, and its authors could reasonably recognize normalized, dense cohort interactions as an extension of their model. The programme also permits co-modifications when they make continuization natural. I would therefore not claim that no scenario yields a worthwhile mirror. The narrower objection is that the strongest proposed mirror obtains a clean continuous problem by replacing the paper’s local network interaction and player-level equilibrium with aggregate interaction and type-level equilibrium. Whether the authors would count that as their problem is the point on which the case against is weakest.
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.