d4-conf-ijcai-2021-0037 (d4-conf-ijcai-2021-0037)

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.

Let \(m\geq 3\) and \(h\geq 1\). The input explicitly lists an undirected temporal graph \(C=(V,(E_t)_{t=1}^{h})\), where \(|V|=m\), \(E_t\subseteq E_{t+1}\), and \((V,E_h)\) is a simple cycle. Set \(E_t=E_h\) for every \(t>h\).
A temporal walk traverses edges present at strictly increasing positive integer times; waiting is allowed. Define \(\operatorname{td}(u,v)\) as the minimum arrival time of such a walk, with \(\operatorname{td}(v,v)=0\) and distance \(\infty\) if no walk exists.
A society is given by its support: a list of \(\tau\) vertex types with positive binary-rational masses \(\mu_v\), summing to \(1\); unlisted vertices have mass \(0\). Thus \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length.
Two players simultaneously choose seeds \(p_1,p_2\in V\), including vertices of zero mass; coincident seeds are permitted. Player \(i\), against player \(j\neq i\), receives \(u_i(p_1,p_2)=\sum_{v\in V:\operatorname{td}(p_i,v)<\operatorname{td}(p_j,v)}\mu_v\). Tied types are unassigned. Use the standard pure Nash equilibrium concept with all unilateral seed changes permitted.

Is deciding whether this game admits a pure Nash equilibrium in \(\mathrm{P}\), with an equilibrium computable whenever one exists in time polynomial in \(m,\tau,h,L\), or is the existence decision problem \(\mathrm{NP}\)-hard?

For uniform vertex masses, a pure Nash equilibrium always exists and can be found in \(\mathcal{O}(m^2)\) time, assuming constant-time access to edge appearance times. This result does not cover arbitrary rational vertex masses.

Result

The problem is in \(\mathrm{P}\), and an equilibrium can be computed whenever one exists.

The decisive observation is that each player has only \(m\) explicitly represented strategies. Thus there are \(m^2\) seed profiles to check. Arbitrary rational masses do not prevent polynomial-time checking, provided payoffs are computed exactly.

1. Computing all temporal distances

For each final-cycle edge \(e\), define its appearance time
\[ a_e=\min\{t:e\in E_t\}. \]
Monotonicity and the extension after time \(h\) imply that \(e\) is available at exactly the positive integer times \(t\geq a_e\). Reading the input determines all appearance times in \(\mathcal{O}(mh)\) elementary operations, since each \(E_t\) contains at most \(m\) edges.

Fix a path with edges \(e_1,\ldots,e_k\). Its earliest possible traversal times satisfy
\[ T_0=0,\qquad T_i=\max\{a_{e_i},T_{i-1}+1\}. \]
Indeed, this recurrence gives a feasible traversal. Conversely, any feasible traversal with times \(S_1,\ldots,S_k\) satisfies \(S_i\geq a_{e_i}\) and \(S_i\geq S_{i-1}+1\). Induction therefore gives \(S_i\geq T_i\), proving optimality.

We next justify restricting attention to simple paths. If a temporal walk repeats a vertex, delete the portion between two occurrences of that vertex. The retained edge times remain strictly increasing, and waiting at the repeated vertex connects the retained portions. If the deleted portion is terminal, arrival becomes earlier. Repeated deletion consequently produces a simple path with arrival no later than the original walk.

Between two distinct vertices of a simple cycle, there are exactly two simple paths: the two cycle arcs. Hence \(\operatorname{td}(u,v)\) is the minimum of the greedy arrival times along those arcs.

For each source \(u\), traverse the cycle in each direction for \(m-1\) edges, using the recurrence above. This computes arrivals along both arcs to every other vertex in \(\mathcal{O}(m)\) operations. Taking their minima and setting \(\operatorname{td}(u,u)=0\) computes the entire distance table in \(\mathcal{O}(m^2)\) operations.

All computed times are at most \(h+m-2\): a path has at most \(m-1\) edges, and its edges can be traversed at consecutive times beginning at \(h\). Thus their bit lengths are polynomially bounded.

2. Computing payoffs exactly

Write the listed masses as
\[ \mu_v=\frac{c_v}{d_v}, \]
where \(c_v,d_v\) are positive binary-encoded integers. Define
\[ Q=\prod_{v\in\operatorname{supp}(\mu)}d_v, \qquad w_v=c_v\frac{Q}{d_v}. \]
Then every \(w_v\) is an integer, and the normalization of the masses gives
\[ \sum_{v\in\operatorname{supp}(\mu)}w_v=Q. \]

The bit length of \(Q\) is at most the sum of the denominator bit lengths, up to an additive constant, and hence is \(\mathcal{O}(L)\). Each \(w_v\) also has \(\mathcal{O}(L)\) bits because \(0<w_v\leq Q\). These integers can be computed in polynomial time.

For every ordered seed pair \((p,q)\), compute
\[ W(p,q)= \sum_{\substack{v\in\operatorname{supp}(\mu)\\ \operatorname{td}(p,v)<\operatorname{td}(q,v)}}w_v. \]
This takes \(\mathcal{O}(\tau)\) distance comparisons and integer additions per pair. Moreover,
\[ u_1(p,q)=\frac{W(p,q)}{Q}, \qquad u_2(p,q)=\frac{W(q,p)}{Q}. \]
The strict comparison implements precisely the rule that tied types are unassigned. Every score lies between \(0\) and \(Q\), so exact arithmetic remains polynomial in \(L\).

3. Checking all best responses

For each opponent seed \(q\), compute
\[ M(q)=\max_{r\in V}W(r,q). \]
A profile \((p,q)\) is a pure Nash equilibrium if and only if
\[ W(p,q)=M(q) \quad\text{and}\quad W(q,p)=M(p). \]

To verify this equivalence, player \(1\)'s payoff after deviating to \(r\) is \(W(r,q)/Q\). Because \(Q>0\), no such deviation improves the payoff exactly when \(W(p,q)=M(q)\). The identical argument for player \(2\), holding \(p\) fixed, gives the second equality.

Compute the maxima and inspect every ordered pair. Return any pair satisfying both equalities; if no pair does, report that no pure Nash equilibrium exists. This includes coincident seeds and every zero-mass vertex as possible strategies.

4. Complexity and conclusion

Apart from polynomial-time preprocessing of the rational masses, the algorithm uses
\[ \mathcal{O}\bigl(mh+m^2+m^2\tau\bigr) \]
elementary comparisons and arithmetic operations. Every integer involved has bit length polynomial in \(L+\log(m+h)\). Consequently, the total bit complexity is polynomial in \(m,\tau,h,L\).

This settles the stated existence and construction problems. The uniform-mass result provides a stronger guarantee of existence and a faster running time; neither guarantee is needed for this polynomial-time decision algorithm.

⟨structured verdict parsed — rendered above⟩

Verification verdict

The prover correctly resolves the task: pure Nash equilibrium existence is decidable in polynomial time, and the algorithm returns an equilibrium whenever one exists. The argument is rigorous, and no major or minor mathematical issues were found.

Step-by-step audit

1. Appearance times and earliest traversal

Every edge of \(E_h\) has an appearance time \(a_e\in\{1,\ldots,h\}\). Monotonicity, together with the extension beyond \(h\), ensures that this edge is available precisely at all integer times \(t\geq a_e\).

For a fixed path, the recurrence
\[ T_0=0,\qquad T_i=\max\{a_{e_i},T_{i-1}+1\} \]
correctly enforces both edge availability and strictly increasing positive traversal times. Its optimality follows from the stated induction: every feasible traversal has its \(i\)-th traversal time at least \(T_i\).

The appearance-time preprocessing bound of \(\mathcal{O}(mh)\) elementary operations is valid because each listed edge set contains at most \(m\) edges. Encoding and arithmetic costs are accounted for in the subsequent bit-complexity discussion.

2. Reduction from walks to simple paths

The deletion argument is valid. Removing a segment between two occurrences of the same vertex preserves the connectivity of the retained walk and the strictly increasing order of its retained traversal times. Waiting is permitted, so the resulting gap causes no feasibility problem.

When the removed segment is terminal, the shortened walk reaches the same destination earlier. Repeating this operation terminates and gives a simple path with arrival no later than the original walk.

For distinct vertices of a simple cycle, the two cycle arcs are exactly its two simple paths. Thus taking the minimum of their greedy arrival times correctly computes the temporal distance. The diagonal values are assigned separately according to the task’s convention.

3. Distance-table construction and time bounds

Traversing \(m-1\) edges in each direction from a fixed source visits every other vertex and computes the arrival time along each of its two arcs. Consequently, the claimed \(\mathcal{O}(m^2)\) operation bound for the complete distance table is correct.

The bound \(h+m-2\) is also correct: a nonempty simple path has at most \(m-1\) edges, all of which are available from time \(h\), so consecutive traversal times beginning at \(h\) yield arrival by \(h+m-2\). Greedy arrivals cannot exceed this feasible schedule. This also covers \(h=1\); diagonal distances are \(0\).

4. Exact rational payoff computation

The common denominator
\[ Q=\prod_{v\in\operatorname{supp}(\mu)}d_v \]
is positive and divisible by every listed denominator. Therefore all quantities
\[ w_v=c_vQ/d_v \]
are positive integers. The normalization assumption gives \(\sum_v w_v=Q\), so each weight and every accumulated payoff score lies between \(0\) and \(Q\).

The bit length of the product \(Q\) is bounded by the aggregate denominator encoding length, hence by \(\mathcal{O}(L)\). Computing the product, exact quotients, weights, and sums requires polynomial bit complexity. No assumption of reduced fractions is needed.

The score \(W(p,q)\) sums exactly the masses won by the player choosing \(p\) against \(q\), after multiplication by \(Q\). Its strict distance comparison correctly excludes tied types. Iterating only over the support is valid because omitted vertices contribute zero mass.

5. Equilibrium criterion and exhaustive search

For a fixed opponent seed \(q\), maximizing \(W(r,q)\) over every \(r\in V\) is exactly the best-response problem, since the positive common denominator does not affect comparisons.

Accordingly, the two equalities
\[ W(p,q)=M(q),\qquad W(q,p)=M(p) \]
are necessary and sufficient for neither player to have a strictly profitable unilateral deviation.

The search includes all ordered profiles and all unilateral seed choices, including zero-mass vertices and coincident seeds. Hence returning a qualifying pair is sound, and reporting nonexistence after exhausting the profiles is complete.

6. Overall complexity and scope

Computing all scores costs \(\mathcal{O}(m^2\tau)\) elementary operations. Computing the best-response maxima and checking profiles costs an additional \(\mathcal{O}(m^2)\). Together with the stated preprocessing and polynomial-size integer arithmetic, this establishes polynomial time in \(m,\tau,h,L\).

The conclusion concerns existence decision and conditional construction; it does not assert universal equilibrium existence for arbitrary masses. This matches the task precisely.

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩