Asynchronous Repetition of Interactive Proof Systems

Abstract

We analyze whether strategic provers can gain an advantage by coordinating their actions across multiple simultaneous games, specifically within the context of parallel repetition and error reduction for interactive proof systems. Suppose the verifier uses a Boolean decision rule, f , that aggregates the results of the individual game executions and determines whether to accept or reject. We prove that if f is a monotone rule (where winning more individual games always increases the chance of acceptance), the prover cannot benefit from cross-game coordination. Instead, the naive behavior – playing each game independently – maximizes the prover's overall acceptance probability. This confirms a recent conjecture by Goldreich regarding the optimality of independent strategies under the majority rule.