acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Local Search in Near-Potential Binary Games

Abstract

We study decentralized binary programming games in which agents make constrained binary decisions under coupled costs, limited computation, and unreliable communication. We propose Decentralized Local Search (DLS), which replaces exact best-response optimization with randomized local search and uses locally maintained empirical-frequency estimates over a random time-varying network. Communication may become increasingly sparse, provided successful information propagation persists over time. For near-potential games, we establish finite-time belief-tracking guarantees and almost-sure convergence to an approximate Nash equilibrium set. Under a best-response margin condition, DLS reaches the pure Nash equilibrium set in finite time almost surely; if equilibria are strict, the joint decisions eventually stabilize at a pure Nash equilibrium. Numerical experiments show that DLS preserves equilibrium-seeking performance while substantially reducing the cost of repeated exact optimization.

Primary area:
optimization
Keywords:
distributed optimization, game-theoretical learning, networked systems

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_rECMOpenReview ↗
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 ϵexp\epsilon_{exp}. Agents act with inertia and track others’ fading-memory empirical frequencies via consensus over random networks whose block-success probabilities may vanish, provided ∑mpj,m=∞\sum_m p_{j,m}=\infty. 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 ∑mpj,m=∞\sum_m p_{j,m}=\infty 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 ϵexp\epsilon_{exp}. 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(KiK_i, ≥ϵexp\ge\epsilon_{exp}) number of children, so the list evolves as a branching process with mean offspring at least KiϵexpK_i\epsilon_{exp}. With the paper’s own parameters this is ≥8⋅0.15=1.2>1\ge 8\cdot0.15=1.2>1 even for the smallest instances (and about 7575 for K=500K=500). The process is supercritical, the while SL ≠ ∅ loop runs forever with positive probability, and xi(t)x_i(t) 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 Mε,δ(j,m0)M_{\varepsilon,\delta}(j,m_0) that depends on m0m_0. When pj,m→0p_{j,m}\to0, 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 HH and ρ>0\rho>0” uniformly, and the resulting bound (1−ρ)m(1-\rho)^m, then fail; a conditional Borel–Cantelli argument with ∑mρm=∞\sum_m\rho_m=\infty would be required and is not provided. In addition, Assumption 4 combined with strictness essentially posits a δ\delta-margin improvement at every non-equilibrium profile, so the near-potential difficulty is largely assumed away. The intermediate set XδhX_{\delta h} with h=∣X∣h=|X| (exponential in ∑iKi\sum_i K_i) is vacuous.

Questions for authors

(a) Does Algorithm 1 terminate almost surely for Kiϵexp>1K_i\epsilon_{exp}>1? If not, please state and analyze the capped version actually used, including how Lemma 3 survives the cap. (b) How is uniformity in m0m_0 obtained when pj,m→0p_{j,m}\to0? (c) Can you compute δ\delta 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 f^−i\hat f_{-i}. 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

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.

  1. 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.

  2. 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.

  1. 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.

  2. 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.

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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  1. You are correct that the previous numerical results were obtained using an earlier implementation with FIFO expansion and an acceptance tolerance of 10−1210^{-12}. We reran the DLS experiments using Algorithm 1 as now specified, including uniform random expansion, visited-set tracking, Cmax⁡=60C_{\max}=60, and ζ=10−9\zeta=10^{-9}. 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.

  2. Remark 2 shows that the expansion cap can be selected from the constraints: for the packing and cardinality structures considered here, Lmax⁡≤2sL_{\max}\le 2s, where ss is the maximum number of selected items. All benchmarks satisfy Lmax⁡≤50<Cmax⁡=60L_{\max}\le50<C_{\max}=60. Remark 1 explains that a sufficient bound on Δmin⁡\Delta_{\min} can be obtained when the cost coefficients have a known common resolution uu, allowing any 0<ζ<u0<\zeta<u. Without such a certificate, ζ\zeta 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.

  3. 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 N=32N=32 proves that FIP fails there. For the remaining tested cases without a known potential, we report empirical findings without claiming FIP.

  4. 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.

Reviewer_KMPZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Paper considers distributed multi agent binary games in which each agent has to take a binary decision at each step. Authors propose Decentralized Local Search (DLS), a method which tackles two main challenges: 1) The high local computation cost that each agent has for the best response strategy and 2) high cost of communication between agents. The paper replaces this exact best response calculation with a local search which is more efficient and addresses the first issue. For the communication overhead, DLS allows agents to use an estimate of other agent's parameters with infrequent updates which leads to a sparse communication graph between agents and addresses the second challenge. Finally, authors provide the convergence guarantee to the Nash equilibrium for this method.

Critical strengths

Paper addresses an important problem in multi-agent system which matters for real-world applications.

Critical weaknesses
  1. The paper assumes so much familiarity with the topic and elaborates to less on assumptions and main results. This makes the paper hard to read for people who are not very familiar with the topic. Moreover, use of many notations and different subscripts and superscripts makes it hard to remember different parameter and I think the overall writing and notation should be significantly simplified.
  2. The experimental part of the paper needs significant improvement. For instance, Table 1 is a large table full of numerical results and it is very hard to understand what is the main message from this table. It would have been much better to summarise these results in a plot with nice visualisations. The same applied to some subsections, for instance 6.4 is a large amount of text which is not really understandable.
Questions for authors
  1. could authors provide more intuition about consensus update (eq. 4) and Assumption 3?
3 comments

We thank the reviewer for the thoughtful feedback and for recognizing the practical motivation behind our work. The comments on presentation and experimental results are particularly helpful. We recognize that some parts of the manuscript are difficult to follow, especially for readers who are less familiar with decentralized learning and game theory. We plan to improve the presentation as follows.

  1. We appreciate the concerns regarding the clarity of the assumptions, theoretical results, and notation. Our intention was to present a general framework for decentralized learning in constrained binary games, but we recognize that the technical details can obscure the main ideas. We will revise these sections by introducing the assumptions more intuitively, explaining their roles in the convergence analysis, and providing a clearer interpretation of the main results. We will also simplify the notation where possible and improve the transitions between the problem formulation, algorithm, and theoretical analysis.

  2. The reviewer makes a useful suggestion regarding the presentation of the numerical results. Table 1 contains detailed comparisons across several problems and network sizes, making it difficult to identify the main findings. We will reorganize the experimental section and introduce additional visualizations that better illustrate the differences between DLS, feasible-only local search (FLS), and exact best responses (EBR). In particular, we will emphasize the cases where exploring infeasible intermediate solutions helps DLS outperform FLS, as well as the computational advantages of avoiding exact best-response calculations. We will also shorten Section 6.4 and focus the discussion on the main observations rather than describing individual numerical results.

  3. We appreciate the request for more intuition behind the consensus update in Eq. (4) and Assumption 3. The main idea of Eq. (4) is that each agent maintains local estimates of the other agents' empirical decisions without requiring direct communication with everyone. At each iteration, an agent updates these estimates by averaging the information received from its available neighbors. The agent whose decision is being estimated also incorporates its latest empirical-frequency change, allowing this new information to gradually propagate through the network.

Assumption 3 describes the communication conditions needed for this information to propagate reliably over time. It does not require the network to be connected at every iteration or communication probabilities to remain uniformly positive. Instead, it requires the candidate communication networks to provide connectivity over finite windows and the probabilities of successful propagation over repeated blocks to satisfy a persistence condition. Intuitively, communication can become increasingly infrequent, provided sufficiently many opportunities for information propagation remain. We will add these explanations before the formal statements and clarify how the communication assumptions support the convergence analysis.

We appreciate the reviewer's suggestions, which will help us make the paper more accessible and communicate its contributions more effectively. We believe that improving the exposition and highlighting the main experimental findings will substantially strengthen the presentation of the work.

Thank you for the reply. I still think the paper needs substantial work to be ready. I will maintain my score.

Thank you for your assessment. We understand your continuing concerns about the presentation and readiness of the paper.

We have uploaded a second revision, with new changes highlighted in green. In particular, we clarified the interpretation of Table 1 and the principal experimental comparisons, reran the DLS experiments using the revised algorithm, added Appendix G to document the differences from the previous implementation, and made the applicability and limitations of the FIP-based convergence result explicit.

We also clarified the algorithmic parameter requirements and the communication regimes covered by the theorem. We hope these changes make the results and their scope easier to evaluate.

We appreciate your time and consideration.

Reviewer_voMJOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies decentralized learning in a near-potential integer programming game, where each player chooses a constrained binary vector. The proposed algorithm, DLS, replaces exact best responses with randomized local search. At each update, a player either retains its current action or searches over single-bit neighbors. Players use consensus to track fading-weighted averages of other players’ actions.

Under reachability and communication assumptions, the paper claims that the algorithm visits the approximate Nash equilibrium set infinitely often almost surely. With additional assumptions, including a best-response margin and strict equilibria, it claims eventual stabilization at a pure Nash equilibrium. The numerical studies report equilibrium attainment comparable to that of a best-response baseline.

Critical strengths
  • The proposed algorithm offers computational and communication efficiency with comparable performance. It could be a practical substitute when exact best responses are expensive.
  • The network model allows communication to become increasingly sparse over time, subject to conditions on the probability of successful information propagation within a block. This gives the model flexibility in how often players can communicate.
Critical weaknesses

The cost used to evaluate candidates during local search needs a clearer definition. Section 3 defines expected costs using distributions over whole feasible actions, whereas Section 4 evaluates costs using one average per bit. When a cost depends on whether several bits of the same opponent’s action are active together, the per-bit averages do not determine the expected cost. Please specify how the algorithm scores fractional inputs, explain how that scoring rule relates to the mixed-strategy cost, and state what regularity or cost structure the convergence analysis requires.

Questions for authors
  • Could a utility design or an equilibrium selection rule improve collective welfare while preserving decentralized implementation?
  • The experiments cap local search at 60 expansions, while Algorithm 1 has no explicit expansion cap. Does the capped version retain the positive probability of finding an improvement required by the analysis?
  • Could the authors clarify how Lemma 2 handles ties in the true costs? Since Eq. (19) defines the minimum gap over nonzero cost differences, I was unsure how the argument treats a candidate that appears strictly better under the estimated beliefs but ties the incumbent under the true actions. Could the authors explain whether this case can occur and, if so, whether it affects the subsequent analysis?
1 comment

We thank the reviewer for the thoughtful assessment and constructive suggestions. We appreciate the recognition of the computational advantages of DLS and the flexibility of our communication model. The comments also highlight several points that deserve clarification, particularly regarding cost evaluations, finite search budgets, and the convergence analysis.

  1. We appreciate the request to clarify the cost evaluations used in DLS. Our algorithm performs randomized local search over an agent's own binary decisions, potentially exploring infeasible intermediate solutions to identify an improving feasible action. Each candidate is evaluated using the estimated empirical frequencies of the other agents. These evaluations are based on continuous extensions of the original cost functions to the belief space and need not represent exact expected costs under arbitrary mixed strategies. We will clarify this distinction and explicitly describe the scoring functions used in the numerical experiments. Importantly, our revised Lemma 2 only requires these functions to be continuous and to agree with the original costs at pure action profiles. This ensures that sufficiently accurate beliefs preserve the relevant cost comparisons, which is the property needed for our convergence analysis.

  2. The suggestion concerning welfare improvement is interesting and closely related to the broader motivation of our work. Our primary objective is to develop a computationally efficient decentralized learning algorithm that avoids solving exact best-response problems. Nevertheless, the choice of utility functions can significantly influence the welfare of the resulting equilibria, as illustrated by the wonderful-life and equally shared utilities in P7. Designing utilities that better align individual incentives with collective performance is a promising direction. Similarly, welfare-aware equilibrium selection could improve outcomes when multiple equilibria exist, although such a mechanism would need to preserve decentralized implementation and account for the information available to each agent. We will include a brief discussion of these possibilities and their relationship to our framework.

  3. The reviewer identifies an inconsistency between the finite expansion cap used in the experiments and Algorithm 1 as originally stated. We have revised the algorithm to explicitly incorporate the cap and updated Assumption 1 to require that the maximum admissible improvement-path length does not exceed the expansion budget. We have also revised Lemma 3 to account for both randomized exploration and the selection of expansion points. Under these conditions, the capped algorithm retains a strictly positive probability of finding a strict unilateral improvement. We recognize that the experimental cap of 60 is covered by the theoretical result only when the corresponding path-length condition is satisfied.

  4. The concern about ties in Lemma 2 is well founded. In the original argument, a candidate with the same true cost as the incumbent could appear strictly better because of errors in the estimated beliefs. We address this by introducing a positive acceptance threshold smaller than the minimum positive unilateral cost improvement. When the beliefs are sufficiently accurate, this threshold prevents the algorithm from accepting changes that are not genuine strict improvements, including ties. We have revised Lemma 2 and the subsequent analysis accordingly. We have also reconsidered the original game-theoretic assumptions and propose replacing Assumption 4 with the finite improvement property (FIP). Together, these changes support an almost-sure convergence argument without requiring strict equilibria or the previous best-response margin assumption.

We appreciate the reviewer's helpful observations, which have contributed to improving the clarity and rigor of our work. We believe these revisions strengthen the theoretical analysis and provide a clearer understanding of the assumptions, limitations, and practical contributions of DLS.

Reviewer_y47jOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper proposes Decentralized Local Search, DLS. It does three things in particular. Firstly, It replaces the exact best response solutions with a randomized one bit flip local search, that can pass through midly infeasible points. Secondly, It tracks the other agents' diminishing average decisions by consensus over a random network that may become increasingly sparse. Lastly, it keeps it's previous decision with high probability. This paper proves that the process visits a δ·|X|-approximate equilibrium set infinitly often. Under a margin condition and strict equilibria, it settles at a pure Nash Equilibrium almost guaranteed. Experiments showed on nine game classes, DLS matches exact best response dynamics in equilibrium attainment on most instances.

Critical strengths
  1. The problem is well motivated. Combining difficult individual optimization problems with incomplete information is practically relevant.
  2. The communication model is weaker than the bounded-intercommunication or uniform-connectivity assumptions common in consensus analyses, since block-success probabilities may decay as long as their sum diverges.
  3. The experimental protocol is careful: 50 seeds per configuration, Nash gaps computed from exact best responses against the true final decisions, and open reporting of incomplete cases (P3 at N = 100, P4 with η = 0.5, FLS stalling under knapsack budgets, the P8 shortfall).
  4. The comparison is fair in an important respect: EBR runs inside the same inertial, consensus-based framework and differs only in the response rule, which isolates the effect of replacing exact solves with local search.
Critical weaknesses
  1. The proofs assert a fixed H < ∞ and ρ > 0 from every state, but Lemma 1's horizon depends on the starting block and Corollary 1's bound contains ε_in^(N(T+1)−1) with T = MB. When p_{j,m} decays, the required holding time grows and this probability shrinks, so uniformity does not follow. Either a uniform bound or a valid non-uniform recurrence argument is needed.
  2. The proof excludes a positive true cost difference but not a zero one. For example, if c_i(b, q) − c_i(a, q) = −q, the actions tie at q = 0, yet b looks strictly better for any belief q̂ > 0. Lemma 3, Corollary 1, and the theorems rely on this strict-improvement step, an acceptance margin or a tie-tolerant argument may repair it.
  3. The abstract and introduction claim convergence, but Theorem 2 establishes only infinitely-often visitation, which is weaker than the guarantees of perfect-information scenarios Candogan et al. (2013a) that line 309 claims to preserve. The tolerance δ·|X| grows at least exponentially in N, and δ is not reported for any near-potential benchmark, so its informativeness cannot be assessed.
  4. If x_i in Assumption 4 is the current decision, the assumption implies every δ-approximate equilibrium is exact, making the game weakly acyclic under best responses. The paper cites Young (2004), Swenson et al. (2018), and Aydın & Eksin (2022) only for the consensus construction and does not relate Theorem 1 to existing convergence results for inertial best response in weakly acyclic games. Framing the contribution as showing that inexact local search meets those conditions would be clearer.
  5. Appendix D varies per-link activation probability and equates divergence of Σ_t p(t) with Assumption 3. Assumption 3 instead requires information to reach all agents within a block, whose probability is at most on the order of p(t)^(N−1). At N = 32 this is summable for γ = 0.5 and 1, so those runs do not satisfy the assumption. Please derive the actual p_{j,m} for the experimental network.
  6. The experiments cap Algorithm 1 at 60 expansions, but the analysis assumes no cap, so it is unclear whether Lemma 3's reachability still holds.
Questions for authors
  1. Can you provide either a uniform positive hitting probability under the stated assumptions or a valid non-uniform argument that the favorable holding-and-propagation events recur almost surely, for example when p_{j,m} ≈ c/m?
  2. How would you repair Lemma 2 in the presence of true ties, and will the the main theorem survive this change?
  3. Under the intended interpretation, Is Assumption 4 equivalent to every δ-approximate equilibrium being exact? What are δ and the minimum nonzero unilateral cost difference for P4, P5, P7 ESU, and P9, and does Assumption 4 hold on these instances?
  4. Why is Theorem 2 stated with tolerance δ·|X| rather than δ, given the descent step? I want to know if the result can be strengthened from infinitely-often visitation to eventual containment?
  5. What block-propagation probabilities p_{j,m} does the experimental network process actually induce, and do the γ = 0.5 and γ = 1 runs satisfy Assumption 3?
  6. Does Algorithm 1 terminate without the expansion cap, and does the capped version used in the experiments retain the reachability property of Lemma 3?

I would be glad to raise my score if the rebuttal provides a valid recurrence argument or restricts the claims to settings where one holds, repairs Lemma 2, and aligns the stated claims with the theorems.

4 comments

We thank the reviewer for the careful review and constructive feedback. The comments have helped us identify several important issues in the original analysis, particularly concerning convergence and the treatment of ties. We have reconsidered the theoretical assumptions and developed the following revisions.

  1. The original proof did not adequately justify a uniform hitting probability when communication reliability decreases over time. To address this, we have developed a block-based argument that explicitly accounts for the communication probabilities. Instead of assuming a uniform probability of success, we establish a lower bound on the probability of a favorable sequence of unilateral improvements over a fixed horizon. Under the persistence condition in Assumption 3, the sum of these lower bounds diverges, implying that the probability of never reaching an equilibrium approaches zero. This reasoning also accommodates block-success probabilities of order c/mc/m, provided the persistence condition holds.

  2. The reviewer raises a valid concern regarding ties in Lemma 2. We address this by introducing a positive acceptance threshold smaller than the minimum positive unilateral cost improvement. When the beliefs are sufficiently accurate, this prevents the algorithm from accepting an apparent improvement between actions with equal true costs. We have revised Lemma 3 accordingly to ensure that accepted changes are genuine strict improvements, and the updated convergence argument relies on this corrected result.

  3. Upon reconsideration, we recognize that Assumption 4 imposes a restrictive condition that, under the interpretation highlighted by the reviewer, effectively requires the relevant approximate equilibria to be exact equilibria. We therefore propose replacing it with the finite improvement property (FIP). Although FIP is stronger than weak acyclicity and near-potential structure, it is more appropriate for our algorithm, which guarantees a positive probability of finding some strict improvement rather than a particular one. We have not yet verified whether the near-potential benchmarks satisfy FIP or determined the requested values of δ\delta and the minimum nonzero unilateral cost differences. We will clarify these limitations and avoid claiming theoretical coverage without the necessary verification.

  4. The tolerance δ.∣X∣\delta . |\mathcal{X}| in the original theorem comes from accumulating the near-potential approximation error along a finite sequence of unilateral improvements, rather than from a single step. This bound can be conservative, particularly for larger games. The reviewer also makes an important distinction between infinitely-often visitation and eventual convergence. Under the revised FIP assumption, our analysis aims to establish almost-sure stabilization at a pure Nash equilibrium without requiring strict equilibria or the previous margin assumption. We will revise the abstract and introduction to reflect this result under the more restrictive game assumption and clarify its relationship to existing inertial best-response results.

  5. Our previous interpretation of Assumption 3 in Appendix D was incorrect. The divergence of individual link-activation probabilities does not necessarily guarantee persistent information propagation across the network. In particular, the experiments with decay exponents γ=0.5\gamma=0.5 and γ=1\gamma=1 cannot be justified by Assumption 3 under the stated independent-link model. We will correct this discussion and present these findings as empirical observations rather than theoretically guaranteed cases. This correction does not affect the reported simulation results.

  6. The reviewer also identifies an important inconsistency between the finite expansion cap used in the experiments and the original analysis. Without the cap, Algorithm 1 terminates because the binary search space is finite and previously expanded points are excluded from further expansion. For the capped version, we have revised Assumption 1 to require that the expansion cap be at least as large as the maximum admissible improvement-path length. We have also updated Lemma 3 to account for both randomized exploration and the selection of expansion points. The revised result establishes a strictly positive probability of finding an improvement within the finite search budget under this condition. The experimental cap of 60 is covered only when the corresponding path-length requirement is satisfied.

We appreciate the reviewer's detailed suggestions, which have been valuable in improving the analysis. We believe these revisions address the main theoretical concerns while providing a clearer account of the assumptions, limitations, and contributions of DLS.

Thank you for the detailed response. I appreciate the acknowledgment of the issues with ties, Appendix D, and visitation versus convergence. The acceptance threshold fix for Lemma 2 looks sound, though please state how agents obtain a lower bound on the minimum positive cost difference. The PDF on OpenReview does not yet reflect the described revisions. My remaining concerns:

1. Please give the explicit per-horizon lower bound and show that its sum diverges for block-success probabilities pj,m=O(c/m)p_{j,m} = O(c/m). Within a fixed horizon, every source needs successful propagation, possibly several times. The probability of that can scale like (c/m)k(c/m)^k with k≥2k \ge 2, and ∑m(c/m)k<∞\sum_m (c/m)^k < \infty.

2. This is a substantial change: the exact result no longer relies on near-potential structure. Which of P1–P9 satisfy FIP, in particular P9 and P7-ESU?

3. The visited-point exclusion is not in the submitted algorithm. With in-order processing and deterministic appends under (A1)–(A3), reaching depth LL may take far more than LL expansions. Why does a cap of at least Lmax⁡L_{\max} suffice, and does Lmax⁡≤60L_{\max} \le 60 hold on the benchmarks?

Based on the current manuscript and the response, I do not yet see sufficient reason to increase my rating, but I would be glad to revisit it if an updated manuscript addresses the points above.

Thank you for identifying the remaining gaps. The updated PDF, with new changes highlighted in green, includes the following corrections.

  1. You are correct that our previous response did not account adequately for repeated successful propagation. We withdraw the claim that success probabilities of order c/mc/m are sufficient. Equations (33)–(34) now give the conditional probability of absorption during block mm as \begin{equation} \mathbb P(B_m\mid\mathcal F_{mK}) \ge a\prod_{s=mK}^{(m+1)K-1}p_s, \end{equation} where K=∣X∣(T+Hc)K=|\mathcal X|(T+H_c), Hc=(N−1)BH_c=(N-1)B, and a>0a>0 is explicitly specified in Equation (34), independently of mm. The bound accounts for all required communication events within the block.

Assumption 3 now requires the sum of these block products to diverge. For ps≍c/sp_s\asymp c/s, the product decays as m−Km^{-K} and is summable when K>1K>1; therefore, such rates are not covered. In contrast, constant reliability and logarithmic decay such as ps=(log⁡(s+e))−γp_s=(\log(s+e))^{-\gamma} satisfy the revised condition. Remark 3 establishes these distinctions, and Appendix D explicitly identifies polynomial-decay experiments as finite-horizon stress tests outside the theorem.

  1. We establish FIP for P1–P3, P5, P6, P7–WLU, P8, and P9 with common beliefs, comprising 29 of 38 instances. Appendix B proves that P5 is a weighted potential game. For P4, P7–ESU, and P9 with private beliefs, FIP remains unverified in general. Appendix C reports tests using exact best-response dynamics: a strict-improvement cycle proves that FIP fails for P4 with N=32N=32, while no violation was found in the tested P7–ESU and P9 private-belief instances. We explicitly distinguish empirical observations from theoretical guarantees.

  2. Algorithm 1 now includes visited-set tracking and selects the next expansion vertex uniformly from the search list. Lemma 3 bounds the list size by 1+Cmax⁡(Ki−1)1+C_{\max}(K_i-1), yielding a strictly positive probability of following an admissible path within L≤Lmax⁡≤Cmax⁡L\le L_{\max}\le C_{\max} expansions. This is a positive-probability guarantee, not a deterministic guarantee for every search realization. Remark 2 verifies Lmax⁡≤50L_{\max}\le50 for all benchmark constraint structures, below the implemented cap of 60.

We also reran the experiments using the revised algorithm and reported the differences in Appendix G.

Remark 1 provides a sufficient lower bound on Δmin⁡\Delta_{\min} when cost coefficients have a known common resolution. Otherwise, the implemented ζ=10−9\zeta=10^{-9} is interpreted as a numerical tolerance; its satisfaction of ζ<Δmin⁡\zeta<\Delta_{\min} is not independently certified for every sampled instance.

Thank you again for helping us clarify the precise scope of the convergence result.

Thank you for the thorough revision. The updated manuscript addresses my main concerns and the claims now match the theorems. I also appreciate the explicit FIP analysis of the benchmarks and the transparency of Appendix G. Based on the revision, I have raised my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.