- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The authors introduce certified temporal equilibrium synthesis (CTES) for finite, deterministic concurrent games. Each player in the game has a boolean LTL specification that provides a reward of 1 if satisfied and there is a system requirement that is to be satisfied. The set of feasible candidate solutions for the search is restrained by a parameter space . A candidate is considered to be feasible when the resulting run by the joint policy satisfies and also is in pure Nash equilibrium against history dependent deviation. The feasible candidates are ordered based on quality functions defined. The authors use greedy constructors to get an initial candidate policy, the resulting lasso is examined, for each of the opponent that loses, a search for satisfying deviation is done. Each deviation that are profitable is stored in the deviation bank that are used as replays for the next search. Empirical evidence shows improvement in the certified initial profile in 22 out of 120 contention runs.
Critical strengths
- The problem is clear, and reusing counterexamples across candidates is a reasonable idea. The paper correctly sees that replay must close the loop on opponent memory, not just physical state, and that payoff improvement must be rechecked on the current candidate.
- The experimental protocol is detailed: matched streams, paired seeds, coverage reporting, and honest reporting of negative and null results.
Critical weaknesses
- The experiments do not compare their method against any verification tools (EVE was mentioned in the paper) or a simple cache ing mechanism.
- I am not sure if ICLR is the right venue for this paper as there is no real learning component here.
- How to design the candidate space is not explored and is assumed.
- Tables 6 and 7 from the appendix seem to show minimal gain from the method.
Questions for authors
- Tables 6 and 7 show no significant effect of guidance or the bank on final quality. What evidence supports their value beyond throughput?
- Why does replay require exact matches of recorded opponent memories, rather than simulating the current opponents along the recorded deviator actions and checking that the states match until a configuration repeats?
- How should be designed for a new game and how sensitive are the results to the choice of ?
General Response
We thank Reviewers aaez, sw36, and GM5y for their constructive feedback and continued discussion. Their comments helped us explain the contribution more clearly and identify where further evidence was needed.
The central insight of CTES is that one profitable infinite deviation can rule out a family of candidate policies. Reuse requires checking whether the behavior remains executable against the current opponents. This check follows their memory updates through loop closure. A separate check establishes whether the deviation still improves the player’s current payoff. We prove that accepted replay yields a legal history-dependent deviation. The resulting evidence supports rejection across policy updates. It can also exclude unstable controller families during symbolic search.
In response to Reviewer aaez, we clarified how these transfer conditions distinguish CTES from existing witness-reuse methods. We added an independent EVE comparison on identical candidate profiles. Both methods agree on all certification verdicts in this comparison. The new coupled contention experiments examine reuse under richer interactions. Shuffled streams test its sensitivity to candidate order. We also added an analytical cross-check for the resource games. The revised response distinguishes the complete certification cost measured in the EVE comparison from the bank’s computational contribution. The latter is measured separately and includes unsuccessful replay costs.
In response to Reviewer sw36, we revised the robot example around finding a safe equilibrium with a high return rate. The example now explains why safety alone does not imply equilibrium. It then shows why operational quality remains relevant when choosing between equilibria. Concise explanations of LTL connect the formal goals to the robots’ recurring tasks. We also clarified the role of certification in the synthesis procedure. In particular, the verifier must consider opponent responses outside nominal play. The revised formulation explicitly separates the finite-memory candidate family from the unrestricted legal history-dependent deviations considered during certification.
In response to Reviewer GM5y, we strengthened the evidence for the individual contributions of guidance and the deviation bank. We added matched ablations that switch the two components independently. All configurations use the same candidate family and certified initialization. They also share the verification backend and computational budget. Guidance improves final certified quality beyond the common initialization. Its mean service-quality gain over matched unguided search is 2.00% in five-player games. The corresponding gain is 5.75%–5.91% in eight-player games, depending on the bank setting. The bank increases online certification throughput by 5.64%–13.47% over matched bank-off configurations. The revised response attributes these gains to the corresponding components. Additional LRU controls examine the value of reuse when candidate profiles are not repeated.
The follow-up discussion with Reviewer GM5y also prompted a clearer explanation of replay. We now state that exact memory matching is a sufficient condition for sound reuse. Offline simulation tests examine how valid memory trajectories can be reconstructed against current opponents. The timed experiments retain strict replay.
To address candidate-space coverage, we added full-game EVE queries and exact domain references. Independently constructed periodic controllers attain full welfare on every input in the coverage study, including those where EVE times out. We expanded the explanation of how to construct this family for a new game. The manuscript also explains how additional memory or response rules can enlarge it. Failure to find a certified policy within a budget is now explicitly distinguished from a proof of equilibrium nonexistence. The supplementary material documents the new evidence.