| paper | d4-conf-ijcai-2021-0037 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\); a pure Nash equilibrium can be computed whenever one exists in time polynomial in \(m,\tau,h,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 55
statement extracted from the paper’s text layer
Given a monotonically growing temporal cycle \(C=(V,(E_t)_{t=1}^{h})\) and a binary-rational distribution \(\mu\) over its vertices, let two players choose seeds \(p_1,p_2\in V\) and give player \(i\) payoff \(\sum_{v:\,\operatorname{td}(p_i,v)<\operatorname{td}(p_j,v)}\mu_v\), with tied types unassigned. Determine whether a pure Nash equilibrium exists and, if so, output one.
The temporal cycle is fixed contact infrastructure, and its vertices are population types with rational masses summing to one. Each player chooses a seed location; each type’s mass is awarded according to which seed has smaller temporal distance, with ties receiving no payoff.
The mirror covers equilibrium existence and computation for mass-weighted temporal Voronoi games on monotonically growing cycles; it leaves the paper’s diffusion-game, tree, shrinking-graph, and unweighted results aside.
The strongest mirror I believe is a mass-weighted version of the paper’s temporal Voronoi game. The natural regime is a large population living in a small number \(q\) of communities arranged on a cycle. Residents of one community share its location and temporal contact role, while the communities’ links appear over the campaign and never disappear. If the population size is \(N\gg q\), each community has a rational population share \(\mu_v\), with \(\sum_v\mu_v=1\). Residents at the same type have the same temporal distance to every campaign seed, so their outcomes agree; counting captured people becomes measuring captured mass. This is a familiar location-based influence scenario, and it puts the population—not the outcome space—on a continuum.
My anchor is Corollary 55, proved in this paper using Theorems 53 and 54. It states that every temporal Voronoi game on a monotonically growing temporal cycle has a Nash equilibrium, and one can be found in \(\mathcal{O}(n^2)\) time. The paper’s other main results are also algorithmic or about equilibrium existence; I find no named hardness result to anchor here. Corollary 55 is the closest fit because a Voronoi game directly partitions a population according to which seed reaches each location first.
I would call the mirror Mass-Weighted Temporal Voronoi Equilibrium on Growing Cycles. An instance is a monotonically growing temporal cycle \(C=(V,(E_t)_{t=1}^{h})\), with \(q=|V|\), and a binary-rational distribution \(\mu\in\mathbb{Q}_{>0}^{V}\) summing to one. A type is a community’s location together with its temporal contact role; its mass is the fraction of residents there. Two campaigners choose seed locations \(p_1,p_2\in V\). Each type’s mass goes to the campaign whose seed has smaller temporal distance to it; tied types go to neither. Thus
\[
U_i(p_1,p_2)=\sum_{v\in V:\,\td(p_i,v)<\td(p_j,v)}\mu_v
\quad (j\ne i).
\]
The task is to output a pure Nash equilibrium, or certify that none exists: a profile \((p_1,p_2)\) is an equilibrium exactly when neither player can increase this mass payoff by changing seed locations.
For this per-instance search problem, I expect tractability. The cycle has \(q\) seed choices per player. After computing temporal distances, enumerate the \(q^2\) profiles and compare each player’s payoff with its \(q\) deviations. The payoff sums are exact rational computations, giving a polynomial-time algorithm in \(q\), \(h\), and the input bit length. This establishes a modest Class A mirror, not a weighted extension of Corollary 55’s sharper guarantee: the corollary says every unweighted instance has an equilibrium and gives an \(\mathcal{O}(n^2)\) construction, while my weighted question also permits a “none” answer. The sharper structural question is whether every rationally weighted instance still has an equilibrium, and, if so, whether the paper’s paramount-response argument yields a comparably efficient construction.
I would limit the mirror to Corollary 55’s temporal Voronoi games on monotonically growing cycles. The paper’s shrinking-graph results and temporal diffusion results are outside this case. Continuous-space Voronoi games are already known and are useful neighboring work; the proposed mirror concerns a population distribution over types on a temporal contact network, so that prior work is context rather than a collision.
The weak point is the move from individual vertices to communities. In the paper, a seed is one vertex; in this scenario it is a community location whose residents share a distance profile. That makes mass-weighted Voronoi allocation plausible, since co-located residents receive the same integral outcome, but the paper’s equilibrium proof relies on unweighted counts and parity. Nothing in Corollary 55 guarantees those arguments survive arbitrary rational masses. That limits the strength of the algorithmic payoff, but leaves a clear, paper-recognizable question: whether its temporal Voronoi equilibrium structure persists when the agents occupying each type carry population mass.
The negative case is weak on its central burden. Corollary 55 is a named algorithmic result, and the paper’s treatment of continuous-space Voronoi games does not already answer the temporal-graph question.
The best objection is about what gets aggregated. In the paper, each vertex is simultaneously a payoff unit, a possible seed location, and part of the network that determines temporal reachability. Vertices on a cycle have different structural roles. Giving a vertex a mass of residents while keeping its single network position preserves their shared distances, but it changes the interpretation: the vertices become community locations and the residents become beneficiaries. That is a modeling choice the paper itself does not establish as a high-multiplicity regime. Duplicating vertices as individual network agents would also change the graph and could destroy the path or cycle structure.
The community interpretation repairs much of this objection. A temporal network of \(q\) locations can serve as infrastructure for a large population whose members at each location share a contact role. A campaigner chooses a location, and temporal distance assigns each resident mass to a winner or a tie. That is a coherent continuous-population Voronoi game. It also fits the programme’s campaigning angle, though its connection to social choice is looser than a model with voter preferences and election outcomes. The paper’s cited continuous-space Voronoi games do not settle the temporal-network version.
There is a narrower flaw in the proposed computational task. Returning an equilibrium or certifying that none exists can be done by enumerating seed profiles and deviations for any finite two-player game with an explicit payoff table. That does not mirror Corollary 55’s structural guarantee that an equilibrium always exists. The stronger mirror would ask whether every rational weighting still admits an equilibrium, and whether the paper’s temporal structure yields an efficient construction. That remains a recognizable and well-posed continuous-population question.
So the objection limits the mirror’s scope and the force of the proponent’s proposed algorithmic result; it does not defeat the stronger mirror. Under the programme’s stated scope, I cannot honestly make the case that no worthwhile continuous mirror exists.
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.