- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper proposes Decentralized Local Search (DLS) for constrained binary programming games. Agents replace exact best responses with a randomized trace-based single-bit-flip local search (after Bertsimas et al., 2013). The search explores lightly infeasible points and admits otherwise excluded candidates with probability . Agents act with inertia and track others’ fading-memory empirical frequencies via consensus over random networks whose block-success probabilities may vanish, provided . Under admissible-path reachability, a best-response margin condition (Assn. 4) and strict equilibria, Theorem 1 claims almost-sure finite-time stabilization at a pure Nash equilibrium. Experiments cover nine game classes with up to 100 agents, compared against a feasible-only local search (FLS) and exact solver-based best responses (EBR).
Critical strengths
(1) The setting is practically motivated, combining a combinatorial best response with unreliable, possibly vanishing communication. The network condition is weaker than the usual uniform joint connectivity. (2) The experimental suite is broad. The FLS ablation shows where exploring infeasible points matters (P2, P4, P5), and the connectivity ablation is informative.
Critical weaknesses
(1) Algorithm 1 as stated does not terminate, so the main theorem does not apply to the method analyzed. In line 10, any one-bit neighbor that fails (A1)–(A3) is still appended to SL with probability . There is no visited set, and the exploration branch bypasses the trace-box pruning. Once no further strict improvement is available, each expanded node therefore spawns a Binomial(, ) number of children, so the list evolves as a branching process with mean offspring at least . With the paper’s own parameters this is even for the smallest instances (and about for ). The process is supercritical, the while SL ≠ ∅ loop runs forever with positive probability, and is then undefined. Lemma 3, Corollary 1 and Theorems 1–3 all assume that each call returns. The experiments silently add a 60-expansion cap that does not appear in Algorithm 1 or the analysis. Under a FIFO cap, the positive-probability path argument of Lemma 3 does not go through, because the admissible path need not be reached within the cap. Hence the convergence guarantee covers neither the stated algorithm (which may not terminate) nor the implemented one (which is not analyzed). (2) The almost-sure convergence argument is not uniform in time. Lemma 1 gives a holding horizon that depends on . When , which is exactly the advertised regime, this horizon can grow without bound, so the per-attempt success probability in Theorems 2–3 can decay to zero. The claim that “there exist finite and ” uniformly, and the resulting bound , then fail; a conditional Borel–Cantelli argument with would be required and is not provided. In addition, Assumption 4 combined with strictness essentially posits a -margin improvement at every non-equilibrium profile, so the near-potential difficulty is largely assumed away. The intermediate set with (exponential in ) is vacuous.
Questions for authors
(a) Does Algorithm 1 terminate almost surely for ? If not, please state and analyze the capped version actually used, including how Lemma 3 survives the cap. (b) How is uniformity in obtained when ? (c) Can you compute for P4, P5 and P7-ESU and verify Assumption 4 and strictness on any instance? (d) Lemma 2 argues via a “multilinear mixed extension” over finite action sets, while the algorithm evaluates costs on marginal bit frequencies . Could you state explicitly under which conditions on the costs these coincide (e.g., multilinearity across different agents’ bits), and confirm that they hold for P7–P9?
3 comments
Thank you for the significant rework of the theoretical part. However, I have several critical points regarding the new version and the way my questions were addressed.
-
Inconsistency between the new results and the old text and experiments. As far as I can see, all numbers in the experiments are the same as in the original submission. Were the experiments carried out for the new algorithm, with the visited set and the acceptance margin? Or does the new algorithm behave exactly as the old one? The value of the acceptance margin used in the experiments is also not specified. Besides, the text contains several artifacts of the old analysis. In particular, Section 6 refers to "the near-potential regime addressed by Theorem 1", which corresponds to the old statement, and the conclusion still claims convergence to the approximate Nash equilibrium set of a near-potential game, whereas the revised Theorem 1 concerns games with the finite improvement property.
-
The algorithm with guarantees seems hard to implement, since its parameters depend on unknown problem quantities: the acceptance margin must be smaller than Δ_min, the minimum positive unilateral cost difference, and the expansion cap C_max must be at least the maximum admissible improvement-path length L_max.
-
As the authors acknowledge, the experimental setting is currently outside the theory, in particular for P4, P5 and P7-ESU, where neither the finite improvement property nor the required parameters have been verified.
-
I have doubts about the novelty of the results. The finite improvement property is noticeably stronger than weak acyclicity, and combining better-response dynamics under this property with finite-time belief tracking follows a fairly standard scheme (e.g., Monderer & Shapley, 1996; Aydın & Eksin, 2022).
For the current revision, I do not see a reason to increase my rating.
Thank you for your careful assessment. We have uploaded a second revision, with the new changes highlighted in green. We address your four concerns below.
-
You are correct that the previous numerical results were obtained using an earlier implementation with FIFO expansion and an acceptance tolerance of . We reran the DLS experiments using Algorithm 1 as now specified, including uniform random expansion, visited-set tracking, , and . The updated results appear in Section 6 and Appendices D–G. Appendix G directly compares both implementations on the same seeds. Exact equilibrium attainment changes on five of the 36 instances with an exact equilibrium test; the remaining counts are unchanged. Extended simulations show that all unfinished runs on P3 and P7 reach equilibrium within four times the original horizon. We also corrected the outdated near-potential statements in Section 6 and the conclusion.
-
Remark 2 shows that the expansion cap can be selected from the constraints: for the packing and cardinality structures considered here, , where is the maximum number of selected items. All benchmarks satisfy . Remark 1 explains that a sufficient bound on can be obtained when the cost coefficients have a known common resolution , allowing any . Without such a certificate, is a numerical tolerance rather than a verified theoretical threshold. Under sufficiently accurate beliefs, a positive margin prevents false improvement acceptance but may exclude smaller improvements.
-
We establish FIP for 29 of the 38 benchmark instances: P1–P3, P5, P6, P7–WLU, P8, and P9 with common beliefs. In particular, Appendix B establishes that P5 is a weighted potential game. For P4, P7–ESU, and P9 with private beliefs, Appendix C reports tests using exact best-response dynamics. A strict-improvement cycle on P4 with proves that FIP fails there. For the remaining tested cases without a known potential, we report empirical findings without claiming FIP.
-
We agree that FIP is stronger than weak acyclicity and that inertia combined with belief tracking builds on established work. Our contribution is replacing exact best-response optimization with finite-budget randomized local search over constrained binary decisions, including infeasible intermediate points, while preserving a positive-probability improvement guarantee under the stated assumptions. Lemmas 2–3 establish the correctness and reachability properties required for this replacement.
We appreciate your feedback and hope the revised manuscript clarifies both the contribution and its limitations.
We thank the reviewer for the detailed assessment and constructive feedback. The comments have helped us identify several important issues in the original analysis, particularly regarding the termination of Algorithm 1 and the convergence guarantees. We have reconsidered these points and developed the following revisions.
The reviewer raises an important concern about the termination of Algorithm 1. As originally presented, the algorithm did not explicitly prevent previously explored points from being revisited, and its termination was not guaranteed. We have corrected this by introducing a visited set and explicitly incorporating the finite expansion cap used in the experiments. We have also revised Assumption 1 to require that the cap is at least as large as the maximum admissible improvement-path length. The updated Lemma 3 accounts for both randomized exploration and the selection of expansion points, establishing a strictly positive probability of finding an improvement within the finite budget. We recognize that the experimental cap of 60 is theoretically covered only when the corresponding reachability condition holds.
The concern about the lack of a uniform convergence probability is well taken. Our revised argument uses a fixed communication horizon and explicitly accounts for decreasing communication reliability. Instead of requiring a uniform success probability across time, we establish a lower bound for favorable sequences of unilateral improvements over fixed blocks. The persistence condition in Assumption 3 ensures that the sum of these bounds diverges, implying that the probability of never reaching an equilibrium approaches zero.
We have also reconsidered the game-theoretic assumptions. Following suggestions from the reviews, we propose replacing the original Assumption 4 with the finite improvement property (FIP). Although stronger than weak acyclicity, FIP is directly compatible with our randomized local-search guarantee, which ensures a positive probability of finding some strict improvement rather than a particular one. Under this condition, the revised analysis establishes almost-sure convergence to a pure Nash equilibrium without requiring strict equilibria or the previous margin assumption. We will also clarify the relationship with existing results on inertial best-response dynamics.
The original Assumption 4 was restrictive, and its applicability to the numerical examples was not established. We therefore propose removing it in favor of FIP. The requested near-potential parameters and minimum nonzero unilateral cost differences have not yet been verified for P4, P5, and P7-ESU. We will clarify this limitation and avoid claiming that these experiments satisfy the revised theoretical assumptions without verification. The numerical results remain useful for evaluating the empirical performance of DLS, but should be distinguished from theoretically guaranteed cases.
We appreciate the request to clarify the relationship between marginal-frequency evaluations and expected costs. Our intention was to extend the cost functions from binary decisions to the continuous belief space through multilinear extensions. Every cost function on a finite binary space admits such an extension, although directly substituting marginal frequencies into a nonlinear expression does not always produce it. We will clarify this distinction and verify the evaluations used for P7–P9. Importantly, our revised Lemma 2 only requires that the cost extension be continuous and agree with the original cost at pure action profiles. Thus, the strict-improvement argument does not rely on multilinearity itself.
We appreciate the reviewer's detailed suggestions, which have been valuable in improving the theoretical analysis. We believe these revisions provide a more rigorous foundation for the implemented algorithm while clarifying the assumptions, limitations, and scope of the convergence guarantees.