PaperlayerView exact revision on arXiv

Source-linked AI summary

ABRA: An algorithm which cannot converge to low-quality Nash equilibria

Vartika Singh, Philip N. Brown

arXiv:2609.11889v1cs.GT

TL;DR

The paper addresses how to avoid low-quality Nash equilibria in game-theoretic solutions to multi-agent coordination with submodular objectives. It proposes ABRA, combining noise-driven approximate best responses with rationality-controlled exploitation. For two-player games, ABRA improves equilibrium guarantees beyond half of optimal, while simulations find expected objectives typically well above half.

  • Problem

    Submodular coordination games can have Nash equilibria near half of optimal, and such bad equilibria are unstable, motivating methods to escape them.

  • Method

    ABRA combines a noise parameter β, which samples approximate best responses to support escape, with a rationality parameter p, which controls best-response selection.

  • Results

    For two-player games, ABRA's equilibrium objective is strictly above 1/2 of optimal by a β-controlled term; recurrent-class guarantees and simulations likewise place expected objectives above half.

  • Takeaways & Limitations

    Noise can help avoid undesirable equilibria, while rationality can limit objective degradation and time spent in bad states within the stated two-player scope.

Abstract

from arXiv · show

We consider a game theoretic approach to solve multi-agent coordination problems with submodular objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal. A recent work further shows that the equilibria which achieve this worst-case bound are not stable. Leveraging this, we design an Approximate Best Response Algorithm (ABRA) governed by a noise parameter and a rationality parameter. The noise allows ABRA to escape the bad equilibria and the rationality parameter balances any degradation in the objective function caused by the noise. We show for any two-player game that if ABRA converges to a Nash equilibrium, its system objective value is strictly more than 50% of optimal plus a term controlled by the noise parameter. Otherwise, ABRA converges to some recurrent class: if a recurrent class contains any action profile yielding system objective less than 50% of the optimal, the class must also contain either the optimal action profile or an action profile yielding system objective strictly more than 50\% of the optimal by the same amount in addition to a factor controlled by noise parameter. The time that ABRA spends in such action profiles can be controlled using the rationality parameter. Using numerical simulations, we show that the minimum expected objective function is typically well above half of the optimal.

I. INTRODUCTION

ABRA uses controlled noise and rationality to escape unstable low-quality equilibria in submodular coordination games. For two-player games, its guarantees improve on the half-optimal worst-case bound while exposing a trade-off between the quality of optimal and sub-optimal recurrent classes.

  • I. INTRODUCTION: ABRA lets agents choose approximate best responses using noise parameter β and rationality parameter p.Noise supports exploration and escape from undesirable equilibria, while rationality governs selection of best responses.
  • I. INTRODUCTION: A sub-optimal recurrent class contains either the optimal action profile or a Nash equilibrium exceeding 1/2 of optimal by a β-controlled term.Thus, even recurrent behavior that excludes the optimal profile contains a sufficiently high-quality equilibrium.
  • I. INTRODUCTION: Increasing β improves lower bounds for Nash equilibria in sub-optimal classes but degrades the quality of action profiles in optimal classes.The algorithm therefore trades improved escape from bad equilibria against weaker guarantees within optimal recurrent classes.
  • I. INTRODUCTION: An appropriate rationality parameter p can limit ABRA's time in bad action profiles, while simulations show expected objectives well within 1/2 of optimal plus a β-dependent term.Figure 1 depicts achievable objective values for recurrent classes containing an optimal action and for sub-optimal recurrent classes.

II. MODEL

The model uses marginal-contribution utilities in a two-agent potential game for submodular system objectives, then applies ABRA to perturb best-response dynamics and avoid inferior equilibria.

  • II. MODEL: The system objective is a normalized, non-decreasing, submodular function over the agents’ joint actions.
  • II. MODEL: Agents observe the other agent’s action but not that agent’s action set, so they cannot directly compute the globally optimal profile.
  • II. MODEL: Marginal-contribution utilities induce a potential game whose potential is the system objective, but multiple Nash equilibria can include inferior outcomes.
  • II. MODEL: ABRA lets agents choose exact best responses with probability p or actions from a β-neighborhood of best responses otherwise.
  • II. MODEL: Noise β must remain below 0.5, while rationality p is below 1 so approximate best responses receive positive probability.
  • II. MODEL: The resulting action sequence is a Markov chain that may have absorbing states and multiple optimal or sub-optimal recurrent classes.

IV. MAIN RESULTS

The main-results setup defines the optimal profile and the worst objective value reachable through unilateral deviation, which parameterize the later class-quality bounds.

  • IV. MAIN RESULTS: The section characterizes the optimal profile through the action pair attaining the maximum system objective.
  • IV. MAIN RESULTS: It defines x̄ as the minimum system objective attainable when either agent unilaterally deviates from the optimal profile.

A. Absorbing states

ABRA excludes the worst Nash equilibria when it reaches an absorbing state and gives sub-optimal recurrent classes stronger equilibrium guarantees, with performance controlled by noise and rationality.

  • A. Absorbing states: An absorbing state under ABRA is a Nash equilibrium whose system objective exceeds half of optimal by an additive term controlled by β.
  • A. Absorbing states: This absorbing-state guarantee holds for every rationality choice p < 1, including zero noise, so the worst half-optimal equilibrium is never reached.
  • B. Sub-optimal classes: A sub-optimal class is a recurrent class that excludes the optimal action profile.
  • A. Absorbing states: Standard best-response dynamics is recovered when β = 0.
  • B. Sub-optimal classes: Every sub-optimal class contains a Nash equilibrium with objective strictly above half of optimal by a β-controlled amount.
  • B. Sub-optimal classes: If a sub-optimal class contains an outcome below half-optimal, its equilibrium quality improves by the same amount, while the class’s worst outcome is bounded by a β-dependent degradation.

C. Optimal classes

Optimal recurrent classes contain the optimal profile but can include degraded outcomes under noise; the resulting bounds expose a trade-off between optimal- and sub-optimal-class quality.

  • C. Optimal classes: An optimal recurrent class contains the optimal action profile and has a game-dependent lower bound determined by the worst unilateral deviation value x̄.
  • C. Optimal classes: The paper also derives a game-independent lower bound for every optimal class, with equality possible only under a specific x̄ condition.
  • C. Optimal classes: Although optimal classes may contain especially poor action profiles, an appropriate rationality parameter limits ABRA’s time spent in them.

D. Trade-off between optimal and sub-optimal classes

ABRA exposes a trade-off governed by noise: increasing β improves guarantees for sub-optimal recurrent classes but degrades the lower bound in optimal classes. Simulations show rationality p can improve expected objective and time spent in optimal profiles.

  • D. Trade-off between optimal and sub-optimal classes: Every sub-optimal class contains an action profile with objective strictly greater than 1/2 + 3β/2 when the optimal-class lower bound is achievable.
  • D. Trade-off between optimal and sub-optimal classes: Higher β improves the guaranteed quality of sub-optimal classes but degrades the quality of optimal classes.The paper states this trade-off explicitly and depicts it in Figure 1.
  • A. Expected system objective and Rationality parameter: As p increases, the stationary probability of choosing the optimal action increases when the process is concentrated on the optimal class.For β = 0.2, Figure 2 indicates that ABRA spends more time in the optimal action profile at higher rationality.
  • A. Expected system objective and Rationality parameter: In a two-player example with β = 0.2, the optimal class can include profiles with objective values from 1 down to 0.4, while an absorbing sub-optimal profile yields 0.71.
  • A. Expected system objective and Rationality parameter: The minimum expected system objective improves with p and becomes above 1/2 plus a β-controlled term once p is sufficiently high.

B. Avoiding the bad NE using ABRA

ABRA can avoid a bad Nash equilibrium by adding noise, but excessive noise degrades the quality of the recurrent class. In the example, moderate noise makes the optimal profile the only absorbing state.

  • B. Avoiding the bad NE using ABRA: The example has a good NE with objective value 1 and a bad NE with objective value 0.51.
  • B. Avoiding the bad NE using ABRA: Very small noise may fail to escape the bad NE, leaving the minimum expected objective at 0.51.
  • B. Avoiding the bad NE using ABRA: At β = 0.1, the bad NE becomes transient and the optimal action profile becomes the only absorbing state, guaranteeing payoff 1.
  • B. Avoiding the bad NE using ABRA: Further increasing noise adds sub-optimal profiles to the recurrent class and lowers the expected system objective.Even large noise can outperform zero noise for an appropriate rationality parameter.

VI. CONCLUSIONS

The paper introduces ABRA for submodular maximization, using noise for exploration and rationality for exploitation. Its two-player guarantees and simulations show system objectives above half of optimal under suitable parameter choices.

  • VI. CONCLUSIONS: ABRA uses noise to explore and escape local maxima, while rationality favors best-response actions and limits degradation from noise.
  • VI. CONCLUSIONS: For two-player games, convergence to an equilibrium yields an objective strictly above 1/2 of optimal by a noise-controlled term.The paper states that this improves known price-of-anarchy bounds.
  • VI. CONCLUSIONS: When ABRA converges to a recurrent class, the paper provides lower bounds on the system objective for such classes.
  • VI. CONCLUSIONS: Numerical simulations show the minimum expected objective under ABRA is more than half of optimal by a term controlled by noise and rationality.
  • VI. CONCLUSIONS: The paper leaves extension to general n-player games as future work.

APPENDIX

The appendix establishes structural bounds for ABRA using submodularity and reachability properties. These bounds quantify the worst-case objective in recurrent classes and support the paper’s equilibrium guarantees.

  • APPENDIX: Submodularity yields W(a) ≤ W(a1, ˜a2) + W(˜a1, a2) for any action profile and alternative actions.
  • APPENDIX: If a profile is absorbing under ABRA, it is an NE, and the proof uses reachability to show recurrent classes must contain stronger profiles or the optimal action.
  • APPENDIX: For any action choice of player 2, the β-neighborhood of player 1’s best responses guarantees payoff greater than max{1 − x̄, x̄} − β.
  • APPENDIX: Applying both players’ β-neighborhood guarantees yields a lower bound greater than max{max{1 − x̄, x̄} − 2β, x̄ − β} over the relevant recurrent set.
  • APPENDIX: The minimum objective over the optimal recurrent set is at least x̄ − β when x̄ ≥ 1/2, and at least 1/2 − 3β/2 when x̄ < 1/2.
Loading 2609.11889v1…