Paper deep dive
Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees
Vartika Singh, Philip N. Brown
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 9/11/2026, 3:32:26 AM
Summary
This paper introduces Truncated Noisy Best-Response (TNBR) algorithms for multi-agent coordination in submodular maximization games. It proves that these algorithms provide both 'Performance' bounds (ensuring high-value recurrent states exist) and 'Safety' bounds (ensuring no arbitrarily bad recurrent states exist). The work establishes a trade-off where poor safety guarantees imply better performance guarantees, leveraging the instability of worst-case Nash equilibria.
Entities (8)
Relation Signals (7)
Nash Equilibria → hasqualitybound → 50% of optimal
confidence 95% · It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal
TNBR Algorithms → solves → Submodular Maximization
confidence 95% · We consider a game theoretic approach to solve multi-agent coordination problems with submodular maximization objectives... we propose a family of algorithms which we call Truncated Noisy Best-Response (TNBR) Algorithms.
TNBR Algorithms → provides → Performance Bounds
confidence 93% · first, "Performance" bounds ensure that TNBR algorithms always have a high-value recurrent state
TNBR Algorithms → provides → Safety Bounds
confidence 93% · second, "Safety" bounds ensure that TNBR algorithms never have arbitrarily-bad recurrent states.
TNBR Algorithms → modeledby → Markov Chains
confidence 90% · We compute bounds on the recurrent classes of TNBR algorithms' associated Markov chains.
Performance Bounds → tradesoffwith → Safety Bounds
confidence 90% · these two types of bounds are linked by a waterbed-like effect: every game with a poor Safety guarantee necessarily has a favorable Performance guarantee.
Logit Selection Rule → istypeof → TNBR Algorithms
confidence 85% · The logit selection rule... This rule is derived from the common log-linear learning algorithm... A TNBR algorithm is specified by... an action selection rule F
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We consider a game theoretic approach to solve multi-agent coordination problems with submodular maximization objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal, but that the equilibria which achieve this worst-case bound are not stable. To exploit this instability, we propose a family of algorithms which we call Truncated Noisy Best-Response (TNBR) Algorithms. These algorithms are flexibly characterized by agents asynchronously and stochastically selecting actions from a neighbourhood of their best response payoffs. We compute bounds on the recurrent classes of TNBR algorithms' associated Markov chains. Our bounds fall into two categories: first, "Performance" bounds ensure that TNBR algorithms always have a high-value recurrent state; second, "Safety" bounds ensure that TNBR algorithms never have arbitrarily-bad recurrent states. Furthermore, these two types of bounds are linked by a waterbed-like effect: every game with a poor Safety guarantee necessarily has a favorable Performance guarantee.
Tags
Links
- Source: https://arxiv.org/abs/2609.11863v1
- Canonical: https://arxiv.org/abs/2609.11863v1
Trouble viewing inline? Open PDF directly →
Full Text
54,037 characters extracted from source content.
Expand or collapse full text
Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guaranteesfootnoteinfo Vartika Singh Email: singh.vsvartika@gmail.com Philip N. Brown Email: pbrown2@uccs.edu Abstract We consider a game theoretic approach to solve multi-agent coordination problems with submodular maximization objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal, but that the equilibria which achieve this worst-case bound are not stable. To exploit this instability, we propose a family of algorithms which we call Truncated Noisy Best-Response (TNBR) Algorithms. These algorithms are flexibly characterized by agents asynchronously and stochastically selecting actions from a neighbourhood of their best response payoffs. We compute bounds on the recurrent classes of TNBR algorithms’ associated Markov chains. Our bounds fall into two categories: first, “Performance” bounds ensure that TNBR algorithms always have a high-value recurrent state; second, “Safety” bounds ensure that TNBR algorithms never have arbitrarily-bad recurrent states. Furthermore, these two types of bounds are linked by a waterbed-like effect: every game with a poor Safety guarantee necessarily has a favorable Performance guarantee. †thanks: [†address: Blue Yonder, India†address: University of Colorado Colorado Springs, CO 80918, USA footnoteinfo]This paper was not presented at any IFAC meeting; it extends work originally presented in [20]. Research was sponsored by the Air Force Office of Scientific Research under award number FA9550-23-1-0171 and by the Army Research Office under grant number W911NF-25-1-0239. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the AFOSR, Army Research Office, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. Corresponding author P. N. Brown. Tel. +1-719-255-3332. , , 1 INTRODUCTION Multi-agent coordination problems have a wide range of applications such as task assignment, resource sharing, channel access control in wireless networks, coverage optimization, network routing, and others (see [2, 3, 7, 10, 18]). The goal is to maximize a system objective controlled by the actions of all the agents. A natural approach to solve such problems uses game theory (see [11, 12]) — a system planner endows the agents with individual utility functions and decision rules that depend only on their local information. The system planner can design the local utility functions in order to drive the equilibria of the game toward a desired system optimal state (e.g., [21]). It is well-understood that if agent utility functions are selected carefully (i.e., using the marginal contribution utility design [11]), the resulting game is a potential game with the system objective as the potential function (see e.g. [8]), and it is known that these equilibria can be learned efficiently by distributed algorithms [4]. In this case, the system-optimal outcome is also a Nash equilibrium (NE) of the game; however, suboptimal Nash equilibria can exist as well. An extensive literature has emerged to derive and optimize lower bounds on the quality of these suboptimal equilibria [16, 17]. When the system objective is submodular maximization and agent payoffs have been designed appropriately, it has been proved that every Nash equilibrium obtains a system objective value within 50% of optimal [22]. Furthermore, it is known for these games that a) any NE close to this 50% bound is not stable, and b) any stable NE obtains significantly more than 50% of optimal [19]. In other words, a stable NE cannot be very bad, and a bad NE cannot be stable. This suggests that by adding some noise to agent behaviour, it may be possible to selectively avoid the poor-performing NE without substantially destabilizing the good-performing NE. In this paper, we extend our previous work in [20] and prove positive results in this direction which apply to a large family of distributed algorithms parameterized by a neighbourhood size β∈[0,1]β∈[0,1]; we term these Truncated Noisy Best-Response (TNBR) Algorithms. In this family of algorithms, agents compute a best-response “neighbourhood” of all actions which obtain a payoff within β of their best-response payoff. The agents asynchronously make randomized selections from these best-response neighbourhoods. Here, β=0β=0 resolves to a simple asynchronous best-response Markov chain, for which (possibly suboptimal) NE are absorbing states. As β increases from 00, one hopes that suboptimal NE become transient while high-performing NE remain recurrent. In this paper, we study two-player submodular maximization games with appropriate payoffs and system objectives normalized to the interval [0,1][0,1]. Our results come in two broad categories: • (Performance) In any such game, every TNBR algorithm has a recurrent action profile with system objective value strictly greater than 12+β 12+β (Theorems 2, 3). • (Safety) In any such game and any TNBR algorithm, every recurrent action profile has system objective value at least 12−g(β) 12-g(β) where g(⋅)g(·) is a nondecreasing function satisfying g(0)=0g(0)=0 (Theorems 3, 4). The expressions 12+β 12+β and 12−g(β) 12-g(β) can be viewed as an extension of classical bounds on worst-case Nash equilibria: when β=0β=0, both expressions coincide at 12 12, which is the known lower bound on the system objective of Nash equilibria in this class of games [22]. Our work provides a theoretical justification for algorithmic optimism: when agents randomize (locally suboptimally), something better than a worst-case equilibrium is visited infinitely often, and arbitrarily-poor states are transient. Note that these types of guarantees on a distributed dynamic update process are rare in the game theory literature. There are many results on practical equilibrium-seeking dynamics [13], but these typically guarantee convergence to some Nash equilibrium without being able to guarantee convergence to a good equilibrium. If worst-case bounds are known on equilibrium quality (e.g., the Price of Anarchy in submodular maximization games [22]), this represents a safety guarantee without a corresponding performance guarantee. On the other hand, there are dynamics in games which are known to select only the optimal Nash equilibria (e.g., the logit-response dynamics in potential games [1]), but these almost universally do so by making every action profile recurrent. That is, they represent a performance guarantee without corresponding safety properties. To our knowledge, our work is the first which provides both. Furthermore, we prove several intriguing subtleties and tradeoffs surrounding the relationship between the Safety and Performance properties, and in many cases an unfavorable Safety bound forces an improvement of the corresponding Performance bound. For example, Theorem 3 shows that in a recurrent class which contains no system-optimal outcome, if g(⋅)g(·) is very steep (indicating an unfavorable Safety property), then the corresponding Performance bound necessarily improves by the same amount. We also include a suite of numerical experiments to empirically study the expected value of a specific TNBR algorithm called the Approximate Best Response Algorithm (ABRA). Here, our experiments indicate that by carefully choosing the specific TNBR algorithm, it is possible to improve upon our baseline bounds substantially. Figure 1: Conceptual plot of the system objective values of the recurrent states of a TNBR algorithm. (i) If an optimal action profile is recurrent (performance), then every action profile below the green region is transient (safety). (i) Otherwise, some action profile above the blue region is recurrent (performance) and every action profile below the blue region is transient (safety). 2 Model We consider a game theoretic approach for sub-modular maximization problems. A system designer provides two agents with local utility functions and decision rules that depend only on the information available to the agents. Given finite sets of elements E1E_1 and E2E_2, agent i has action set i⊆2EiA_i 2^E_i so that the joint action space is defined by :=1×2.A:=A_1×A_2. We assume that for each agent i, non-participation is feasible; i.e., ∅∈i _i. The optimization problem is specified by a function W:→[0,1]W:A→[0,1]. We assume the function W to be sub-modular, non-decreasing and normalised; that is, for any sets a,a′a,a such that a⊂a′a⊂ a and any element x∈x , we have W(a∪x)−W(a) W(a∪\x\)-W(a) ≥ ≥ W(a′∪x)−W(a′), W(a ∪\x\)-W(a ), W(a′)≥W(a) W(a )≥ W(a) and W(∅)=0. W( )=0. (1) Frequently, we slightly abuse notation and write W(a,b)W(a,b) to denote W((,,,))W((a,b)) where a∈1a _1 and b∈2b _2. Any agent i can observe the action of the other agent but is unaware of their action set −iA_-i, thus cannot directly compute the optimal action profile. The system designer aims to design the utility functions and decision rules such that the agent behaviour is driven towards a desirable outcome. In this paper, we select the marginal contribution local utility functions (see [8]): Ui(ai,a−i):=W(ai,a−i)−W(∅,a−i),U_i(a_i,a_-i):=W(a_i,a_-i)-W( ,a_-i), (2) where aia_i represents the action of agent i and a−ia_-i represents the action of the other agent. It is clear from (2) that the local utility of any agent equals the gain in the system utility when that agent chooses to participate. One may anticipate that when agents act as per their self-interest, and try to improve their local utilities, they may also improve the system objective. The marginal contribution utility structure (2) induces a potential game among the agents with the system objective function W as the potential function [8]. Accordingly, the maximizer of W is always a pure Nash equilibrium (NE) of this game. However, the game may have suboptimal NE as well. It is shown in [22] that any NE is guaranteed to be within 12 12 of the optimal for such games. Further, [19] shows that the ‘bad’ NE (the ones with inferior system objective) are not stable: at an unstable NE, none of the agents lose much by switching to the optimal action, i.e., the optimal action is an approximate best response for any agent. Inspired by this, our paper proposes a family of algorithms that leverages the fragility of the ‘bad’ NE in order to escape them by adding a noise parameter β. We describe the algorithm in the next section. Before presenting the algorithmic framework, Lemma 1 states a key structural property of games in our model: at a high-payoff action profile, if one agent can deviate to any low-payoff action profile, the other agent necessarily has only high-payoff deviations. We will use this property repeatedly to prove the paper’s main results. Lemma 1 If W is sub-modular, non-decreasing and normalised, i.e. satisfies (1), then for any a=(a1,a2)a=(a_1,a_2), W(a)≤W(a1,a~2)+W(a~1,a2) for all a~1∈1,a~2∈2.W(a)≤ W(a_1, a_2)+W( a_1,a_2) for all a_1 _1,\ a_2 _2. Proof: From (1), we have W(a1,a2)−W(a2) W(a_1,a_2)-W(a_2) ≤ ≤ W(∅,a1)−W(∅)=W(a1), W( ,a_1)-W( )=W(a_1), W(a)≤W(a1)+W(a2) W(a)≤ W(a_1)+W(a_2) ≤ ≤ W(a1,a~2)+W(a~1,a2). W(a_1, a_2)+W( a_1,a_2). In the above, the first inequality follows since W is sub-modular. The second inequality follows since W(∅)=0W( )=0, and the last inequality follows from the non-decreasing nature of W, completing the proof. ■ 3 Truncated Noisy Best Response Algorithms From [19], since suboptimal NE have low stability, agents may be able to escape them by adding some noise while still considering the best responses of the agents. We introduce a noise parameter β∈[0,0.5)β∈[0,0.5) and allow the agents to choose actions probabilistically from the β-neighbourhood of their best response.11 1 A noise parameter β≥0.5β≥ 0.5 does not add any value to the system and makes all NE recurrent. Basically, the agent makes a randomized action selection only from the set of actions which provide utility within β of the current best-response payoff. A high noise parameter β may degrade the performance of the system by allowing inferior actions in the β-neighbourhood, while a low noise parameter may not be sufficient to escape the bad NE. Our approach allows us to explicitly characterize this trade-off. Let ℬi(a−i)B_i(a_-i) represent the best response set of agent i when the action of the other agent is a−ia_-i; i.e., ℬi(a−i):=argmaxUi(ai,a−i):ai∈iB_i(a_-i):= \U_i(a_i,a_-i):a_i _i\. Further, define iβ(a−i)N^β_i(a_-i) to be the set of actions in the β-neighbourhood of the best response set for agent i (with a∗∈ℬi(a−i)a^* _i(a_-i)): iβ(a−i):=ai:|Ui(a∗,a−i)−U(ai,a−i)|≤β.N^β_i(a_-i):=\a_i:|U_i(a^*,a_-i)-U(a_i,a_-i)|≤β\. A TNBR algorithm proceeds by allowing agents to update their actions asynchronously according to a pre-specified probability distribution on iβ(a−i)N^β_i(a_-i). To specify this probability distribution, we define an action selection rule F(⋅)F(·) as an algorithm which inputs a set of actions and outputs a probability distribution over that set. When F(iβ(a−i))F(N^β_i(a_-i)) assigns positive probability to every action in iβ(a−i)N^β_i(a_-i), we say that F is a fully-supported action selection rule. Most of our results are agnostic to the specific choice of action selection rule, but for concreteness we present two feasible examples of fully-supported action selection rules here. Example 1 The logit selection rule FγlogF log_γ with rationality parameter γ>0γ>0 assigns a probability distribution to the actions in iβ(a−i)N^β_i(a_-i) according to the softmax function. That is, the probability that agent i selects action ai′∈iβ(a−i)a_i ^β_i(a_-i) is Pr[ai=ai′]=exp(γUi(ai′,a−i))∑ai∗∈iβ(a−i)exp(γUi(ai∗,a−i)). [a_i=a_i ]= (γ U_i(a_i ,a_-i) ) _a_i^* ^β_i(a_-i) (γ U_i(a_i^*,a_-i) ). (3) This rule is derived from the common log-linear learning algorithm [1].22 2 In the β→1β→ 1 limit, a TNBR algorithm with the logit selection rule resolves exactly to log-linear learning. Example 2 The mistakes rule FpmisF mis_p with rationality parameter p∈[0,1)p∈[0,1) assigns a probability distribution to the actions in iβ(a−i)N^β_i(a_-i) by usually selecting uniformly from the best response set, but occasionally selecting a best-response-neighbourhood action uniformly at random. That is, agent i selects action aia_i according to ai=a∈ℬi(a−i) with probability p,a∈iβ(a−i) with probability 1−p.a_i= \ array[]la _i(a_-i)& with probability p,\\ a ^β_i(a_-i)& with probability 1-p.\\ array . In the above, a is chosen from ℬi(a−i)B_i(a_-i), or iβ(a−i)N^β_i(a_-i) uniformly at random. This rule is inspired by classical mistakes-based learning dynamics (e.g., [5, 6, 23]). Using this action selection rule, one obtains an algorithm substantially identical to the Approximate Best Response Algorithm (ABRA) of the conference version of this paper [20]. With the above definitions in place, we can now precisely state the family of algorithms which we study in this paper. Definition 1 A truncated noisy best-response algorithm is specified by the tuple (β,F(⋅))(β,F(·)), where β≥0β≥ 0 and F(⋅)F(·) is a fully-supported action selection rule. The agents are initialized at some joint action profile a(0)=(a1(0),a2(0))a(0)=(a_1(0),a_2(0)). At any t≥1t≥ 1, some agent i is selected uniformly at random; this agent observes the joint action profile a(t−1)a(t-1) and then selects its next action by sampling ai(t)∼F(iβ(a−i(t−1)))a_i(t) F(N^β_i(a_-i(t-1))). It can be seen that the sequence of joint action profiles a(t)t\a(t)\_t induced by any TNBR algorithm (β,F)(β,F) evolves as a Markov chain (see e.g., [9, 15]) governed by the noise parameter β and action selection rule F. This Markov chain need not be irreducible, and may have multiple recurrent classes depending upon the system objective function W. We can now state the first general result of this paper, that the recurrent classes of these algorithms are governed only by β, and are independent of the choice of action selection rules: Theorem 1 Consider any fully-supported action selection rules F1F_1 and F2F_2 and any 2-player submodular maximization game W. For any β≥0β≥ 0, let ℜ1=ℛii=1k1 R_1=\R_i\_i=1^k_1 and ℜ2=ℛii=1k2 R_2=\R_i\_i=1^k_2 be the sets of recurrent classes of TNBR algorithms (β,F1)(β,F_1) and (β,F2)(β,F_2), respectively when applied to game W. Then ℜ1=ℜ2 R_1= R_2. Proof: First note that for any action profile a and either player i, because F1F_1 and F2F_2 are fully-supported, it holds that supp(F1(iβ(a−i)))=supp(F2(iβ(a−i)))=iβ(a−i). supp(F_1(N^β_i(a_-i)))= supp(F_2(N^β_i(a_-i)))=N^β_i(a_-i). (4) Now, consider action profiles a=(a1,a2)a=(a_1,a_2) and a′=(a1′,a2′)a =(a_1 ,a_2 ). First, suppose that a′a is reachable from a under TNBR algorithm (β,F1)(β,F_1); that is, there is a sequence of positive-probability transitions leading from a to a′a given the action selection probabilities in (β,F1)(β,F_1). Due to (4), this means that a′a is reachable from a under TNBR algorithm (β,F2)(β,F_2) as well. Conversely, the same argument gives that if a′a is not reachable from a under (β,F1)(β,F_1), that it is not reachable from a under (β,F2)(β,F_2) either. Now, let ℛR be a recurrent class of (β,F1)(β,F_1); that is, for any a,a′∈ℛa,a , a′a is reachable from a and for any a′∉ℛa , a′a is not reachable from a. By the above arguments, these reachability relationships hold under (β,F2)(β,F_2) as well, meaning that ℛR is a recurrent class of (β,F2)(β,F_2). By swapping F1F_1 and F2F_2 in this argument, the proof is completed. ■ We refer to any recurrent class that contains an optimizer of W as an optimal class (denoted by ℛβ∗R_β^*) and any recurrent class that does not contain the optimizer as a sub-optimal class (denoted by ℛβR_β). The Markov chain may converge to an absorbing state, a sub-optimal class or an optimal class depending upon initial distribution. We now provide the qualitative analysis of the system objective over these classes generated under any TNBR algorithm (β,F)(β,F). 4 The Recurrent Classes of TNBR Algorithms Here, we present a series of qualitative characterizations of the recurrent classes of TNBR Algorithms, parameterized by β. Due to Theorem 1, all of the results of this section hold for any action selection rule F. Without loss of generality, assume that (a11,a21)(a^1_1,a_2^1) is the optimal profile with W(a11,a21)=1W(a^1_1,a_2^1)=1. 4.1 Absorbing states improve upon worst-case If the sequence of action profiles a(t)\a(t)\ generated using a TNBR algorithm (β,F)(β,F) converges to an absorbing state, then we have the following result with proof in Appendix: Theorem 2 If (a1∗,a2∗)(a_1^*,a_2^*) is an absorbing state for Markov chain (a1(t),a2(t))t\(a_1(t),a_2(t))\_t generated using TNBR with noise parameter β, then, i) (a1∗,a2∗)(a_1^*,a_2^*) is an NE, and i) the system objective satisfies W(a1∗,a2∗)>12+βW(a_1^*,a_2^*)> 12+β. The above result implies that the sequence of action profiles (a1(t),a2(t))t\(a_1(t),a_2(t))\_t generated using (β,F)(β,F) converges only to the NE that have system objective value greater than 12+β 12+β. This provides a significant improvement over the known bound [22] that every NE has system objective at least 12 12. Also, note the strict inequality in the theorem statement; this indicates that no TNBR algorithm can ever converge to a worst-case Nash equilibrium, even when the noise parameter β=0β=0. This reaffirms the findings of [19] regarding the fragility of worst-case NEs. 4.2 Sub-optimal classes contain high-quality NE Now, we consider the sub-optimal classes: those recurrent classes which contain no optimal action profile. We have the following Performance guarantee with proof in Appendix. Theorem 3 If ℛβR_β is a sub-optimal class under TNBR algorithm (β,F)(β,F) then mina∈ℛβW(a)>12−β2. _a _βW(a)> 12- β2. (5) Further, it holds that maxa∈ℛβW(a)>12+δ+β _a _βW(a)> 12+δ+β (6) where δ∈[0,β/2)δ∈[0,β/2) satisfies mina∈ℛβW(a)=12−δ _a _βW(a)= 12-δ. From the above theorem, it is guaranteed that even a sub-optimal class always contains a Nash equilibrium with system objective value more than 12+β 12+β. Moreover, when the sub-optimal class contains an action profile with system objective less than 12 12, then a) the quality of the best Nash equilibrium in the class is further improved by the same amount, and b) the system objective of any action profile in any sub-optimal class cannot be worse than 12 12 by more than β2 β2. While one would typically hope not to converge to a sub-optimal class, Theorem 3 provides a strong mitigating promise: sub-optimal classes always contain a reasonably “good” NE, and cannot contain any arbitrarily bad action profiles. 4.3 Optimal Classes Have a Safety Guarantee We now consider any optimal class ℛβ∗R^*_β — the recurrent class of action profiles that contains the optimal action profile (a11,a21)(a^1_1,a^1_2). We derive a Safety guarantee: a lower bound on the system objective value over the optimal class. Towards proving this result (and later Theorem 5), we present the following Lemma which specializes Lemma 1 to the optimal recurrent class. The proof of Lemma 2 appears in the Appendix. Lemma 2 Define x¯ x as the following: x¯:=minW(a1′,a21),W(a11,a2′):a1′∈1,a2′∈2, x:= \W(a_1 ,a_2^1),W(a^1_1,a_2 ):a_1 _1,a_2 _2\, (7) If ℛβ∗R_β^* is an optimal class of action profiles under TNBR algorithm with (β,F)(β,F), then the system objective function satisfies the following: W(a1,a2)≥maxmax1−x¯,x¯−2β,x¯−βW(a_1,a_2)≥ \ \1- x, x\-2β, x-β\ (8) for all (a1,a2)∈ℛβ∗(a_1,a_2) ^*_β, with x¯ x as in (7). The above result provides the worst possible value that the system objective function can take once the sequence a(t)t\a(t)\_t enters the optimal class. The lemma shows that this lower bound depends upon the particular game in consideration through x¯ x. We can now state the main ‘safety’ result: Theorem 4 If ℛβ∗R_β^* is an optimal class under TNBR algorithm (β,F)(β,F), then the system objective function satisfies the following: mina∈ℛβ∗W(a)≥12−3β2. _a _β^*W(a)≥ 12- 3β2. (9) Proof: From Lemma 2, the minimum value that W can take over ℛβ∗R_β^* is maxmax1−x¯,x¯−2β,x¯−β \ \1- x, x\-2β, x-β\. Hence, for x¯≥12 x≥ 12, W≥x¯−β≥12−βW≥ x-β≥ 12-β. For x¯<12 x< 12, W≥max1−x¯−2β,x¯−βW≥ \1- x-2β, x-β\. The right hand side is minimized when x¯=12−β2 x= 12- β2, and provides a minimum value of 12−32β 12- 32β, obtaining (9). ■ The above theorem shows that the minimum value that the system objective can take if a(t)t\a(t)\_t converges to ℛβ∗R_β^* can be as bad as in (9). This may seem like a negative result but we discuss in Section 5.1 that an appropriate action selection rule can limit the time that a TNBR algorithm spends in the action profiles with the worst system objective value. Before that, we describe the trade-off between improving the sub-optimal classes and degrading the optimal class in the following. 4.4 Trade-off between Safety and Performance guarantees To this point, we have shown independent Performance (Theorems 2, 3) and Safety (Theorems 3, 4) guarantees; here we also show that the two are closely linked by a waterbed-like tradeoff effect. Specifically, if a particular game’s optimal classes have a very poor Theorem 4 safety guarantee (9), then its sub-optimal classes necessarily have a very favorable Theorem 3 performance guarantee (5). The precise mechanism causing this is somewhat opaque; fundamentally, the effect occurs because manipulating the payoff matrix to force the optimal-class safety guarantee down causes certain payoffs elsewhere in the payoff matrix to rise (enforced indirectly by Lemma 1), which pushes the suboptimal-class performance guarantee up. Theorem 5 If ℛβ∗R_β^* is an optimal class under TNBR algorithm (β,F)(β,F) that satisfies mina∈ℛβ∗W(a)=12−β−δ _a _β^*W(a)= 12-β-δ (10) for some δ∈[0,β2]δ∈[0, β2], then every sub-optimal class ℛβR_β satisfies maxa∈ℛβW(a)>12+β+δ. _a _βW(a)> 12+β+δ. (11) Proof: From Lemma 2 and equation (10), x¯−β x-β ≤12−β−δ⟹x¯≤12−δ. ≤ 12-β-δ x≤ 12-δ. Using equation (16), the above implies W(a11,a2′)≥12+δW(a_1^1,a_2 )≥ 12+δ for all a2′∈2a_2 _2. Using similar arguments as (18) leads to (11). ■ Remark 1 In this paper, we provide the TNBR framework and a characterization of several important tradeoffs, and allow “end-users” of TNBR to decide how to select β and F(⋅)F(·) given their own specific metrics of interest. Due to the generality of the TNBR framework, a value of β which is optimal (with respect to some metric) for one choice of action selection rule may not be optimal for any other choice of action selection rule. 5 Numerical Experiments As already mentioned, the sequence of action profiles a(t)\a(t)\ generated using a TNBR algorithm need not converge to a single absorbing state, and may have multiple recurrent classes depending upon the algorithm’s parameters. Thus, it is natural to analyse the expected value of the system objective W under achievable stationary distributions. For concreteness, in this section we conduct all our experiments with the mistakes model action selection rule as defined in Example 2; we call this the Approximate Best Response Algorithm (ABRA). Let Π be the set of stationary distributions of the Markov chain a(t)t\a(t)\_t concentrated on various recurrent classes and Eπ[⋅]E_π[·] represent the expectation under distribution π. Define the following performance metric: β,p(W):=minπ∈ΠEπ[W]maxaW(a)=minπ∈ΠEπ[W],P_β,p(W):= _π∈ E_π[W] _aW(a)= _π∈ E_π[W], (12) since maxaW(a)=1 _aW(a)=1 in our framework. This metric measures the worst case expected system objective as compared to the optimal value. 5.1 Experiments on a Small Game In this section, we numerically show the variation in probability of choosing an optimal action under stationary distribution concentrated over optimal class, qp∗q^*_p, as the rationality parameter varies. We also plot the expected system objective as a function of rationality parameter. Consider the following system objective function, W=[10.80.60.50.50.60.40.390.50.390.390.390.50.390.390.71],W= bmatrix1&0.8&0.6&0.5\\ 0.5&0.6&0.4&0.39\\ 0.5&0.39&0.39&0.39\\ 0.5&0.39&0.39&0.71 bmatrix, (13) which is controlled by actions of two players with action sets, i=ai1,ai2,ai3,ai4A_i=\a_i^1,a_i^2,a_i^3,a_i^4\ for i=1,2i=1,2. The (j,k)(j,k)-th entry of matrix in (13) corresponds to the system objective value achieved under action profile (a1j,a2k)(a_1^j,a_2^k); for example, W(a11,a21)=1W(a^1_1,a^1_2)=1 is the system optimal. Recall that the system objective function is the potential function for the corresponding potential game induced by marginal utilities. It is well known that any NE of the potential game is the local maximizer of the potential function (see [14]). Thus, the game induced by W in (14) has two NEs, (a11,a21)(a^1_1,a^1_2) with objective value 11 and (a14,a24)(a_1^4,a_2^4) with objective value 0.710.71; the noise parameter is fixed to β=0.2β=0.2. In game (13), as the sequence of action profiles a(t)t\a(t)\_t generated using ABRA for (β,p)(β,p) progresses, it may converge to the absorbing state (a14,a24)(a_1^4,a_2^4) yielding a system objective value 0.710.71 which is strictly more than 12+β 12+β as shown in Theorem 2. Otherwise, a(t)t\a(t)\_t may converge to the optimal class, which for β=0.2β=0.2 contains the action profiles with the values 1,0.8,0.6,0.5,0.4\1,0.8,0.6,0.5,0.4\. The minimum value that the system objective can take is 0.4, which is less than 12 12, and is worse than the well known PoA bound in [22]. Figure 2: The probability of choosing an optimal action in an optimal class for W in (13) of section 5.1, when noise parameter β=0.2β=0.2. Figure 3: Minimum expected value of system objective W in (13) of section 5.1, when noise parameter β=0.2β=0.2. When rationality parameter p is sufficiently high, this value rises above 12+β 12+β. However, in Figure 2, we observe that the probability of choosing the optimal action (when a(t)t\a(t)\_t converges to the optimal class) increases as the rationality parameter p increases. This implies that ABRA spends most of the time in an optimal action profile if it converges to an optimal class. In Figure 3, we plot β,p(W)P_β,p(W) as a function of rationality parameter p<1p<1 and observe that the minimum expected value of the system objective β,p(W)P_β,p(W) in (12) improves with the rationality parameter p and is above 12+β 12+β once p≥0.3p≥ 0.3. 5.2 Avoiding the bad NE using ABRA Now, we present an example where ABRA avoids a bad NE. We consider the following system objective function, W=[10.80.50.50.60.50.50.50.51],W= bmatrix1&0.8&0.5\\ 0.5&0.6&0.5\\ 0.5&0.5&0.51 bmatrix, (14) which is controlled by actions of two players with action sets, i=ai1,ai2,ai3A_i=\a_i^1,a_i^2,a_i^3\ for i=1,2i=1,2. Here W(a11,a21)=1W(a^1_1,a^1_2)=1 is the system optimal. The game induced by W in (14) has two NEs, the good NE (a11,a21)(a^1_1,a^1_2) with objective value 11 and the bad NE (a13,a23)(a_1^3,a_2^3) with objective value 0.510.51. In Figure 4, we plot the minimum expected value of system objective W, i.e., W(β,p)P_W(β,p) of (12) as a function of β and fix the rationality parameter at p=0.5p=0.5. When the noise parameter β is very small, it is not sufficient to escape the bad NE, and the agents may converge to the (a13,a23)(a_1^3,a_2^3), which yields minimum possible expected system objective 0.510.51. When noise parameter is slightly increased, e.g., β=0.1β=0.1, then the NE (a13,a23)(a^3_1,a^3_2) becomes transient, and the optimal action profile becomes the only absorbing state guaranteeing the optimal payoff of 1. However, when the noise is further increased, the quality of the optimal class degrades, and all the action profiles constitute one optimal class: the addition of sub-optimal action profiles in the recurrent class reduces W(β,p)P_W(β,p). Figure 4: Minimum expected value of system objective W in (14) of section 5.2 as a function of noise parameter β. Adding a small amount of noise escapes the worst NE; however, large amounts of noise reduce system performance. 5.3 Experiments on Large Games The experiments in the preceding sections illustrate some of the algorithm’s fine-grained behavior in a digestible way. To complement this, here we present the results of a few experiments on much larger games. The games in this section are max-weight set cover games (this is a classic submodular problem; see e.g. [16]). A max-weight set cover game has a set of resources ℛR of positive values vrr∈ℛ\v_r\_r . Agent i has action set i⊂2ℛA_i⊂ 2^R. The problem’s system objective is to maximize the total value of resources which are included in any agent’s action set: W(a1,a2):=∑r∈a1∪a2vr.W(a_1,a_2):= _r∈ a_1∪ a_2v_r. (15) For these experiments, we generated two instances of max-weight set cover games with |ℛ|=9|R|=9 and |i|=50|A_i|=50 for i∈1,2i∈\1,2\. Resource values were uniformly sampled (with replacement) from 1,…,10\1,…,10\, and action sets were uniformly sampled (without replacement) from the subsets 2ℛ2^R containing no more than 4 elements. To conform to the paper’s assumptions, we normalized the system objective to have a maximum of 11.33 3 For full implementation details, see https://github.com/descon-uccs/tnbr-2026/. Our experiments compare two action selection rules: the logit rule FγlogF_γ log with γ=10γ=10, and the mistakes rule FpmisF_p mis with p=0p=0. That is, our implemented mistakes rule simply performs uniform selection from the best-response neighbourhood iβ(a−i)N^β_i(a_-i). These two rules are convenient, because they each naturally converge to well-known game-theoretic learning algorithms when β is at an extreme point. In particular, FγlogF_γ log converges to the classic log-linear learning when β→1β→ 1, and both FγlogF_γ log and FpmisF_p mis converge to asynchronous best response dynamics when β→0β→ 0. For each generated game and each action selection rule, we sweep β from 0 to 1; for each value of β and each game instance, we perform 5000 random action initializations, then run each TNBR variant for 20000 agent updates from each initialization. Then, over the last 5000 agent updates of each run, we calculate • The system objective averaged over the last 5000 agent updates, and • The minimum system objective observed over the last 5000 agent updates. Each of these quantities are recorded as the “result” of the particular run. We then aggregate these last-5000 quantities over all runs, in the following way: • We average all (averaged) system objectives, and • We compute the minimum system objective. This stands as a proxy for the minimum objective value of any recurrent action profile. Figure 5: Large-game experiment results as described in Section 5.3 for Game 1, which has worst-case NE of welfare 0.7650.765 and stability margin 0.6410.641. The TNBR traces are averages over all runs of the average welfare of last 5000 timesteps of each run for the logit and uniform action selection rules, respectively. The green trace is the minimum welfare of any recurrent state (estimated empirically). Note that the upper plot shows β∈[0,1]β∈[0,1]; the lower plot is the same experiment with β∈[0,0.3]β∈[0,0.3]. Figure 6: Large-game experiment results as described in Section 5.3 for Game 2, which has worst-case NE of welfare 0.7830.783 and stability margin 0.0370.037. The TNBR traces are averages over all runs of the average welfare of last 5000 timesteps of each run for the logit and uniform action selection rules, respectively. The green trace is the minimum welfare of any recurrent state (estimated empirically). Note that the upper plot shows β∈[0,1]β∈[0,1]; the lower plot is the same experiment with β∈[0,0.3]β∈[0,0.3]. The experimental results are depicted in Figures 5 and 6 and display a number of interesting features. Note that we repeat the experiment on two separate games which we identify as “Game 1” and “Game 2.” These games have similarly low-efficiency worst-case Nash equilibria of welfare 0.7650.765 and 0.7830.783, respectively. They are distinguished by their stability margin values, computed according to the definition in [19]; these values are 0.6410.641 and 0.0370.037, respectively. In particular, the very low stability margin of 0.0370.037 in Game 2 indicates that when agents are selecting the worst-case Nash equilibrium, either agent can deviate to a system-optimal action without experiencing a large loss in payoff. This indicates that the worst-case Nash equilibrium lacks stability. Interestingly, in both example games, the suboptimal and optimal recurrent classes collapse together into a unique recurrent class even for relatively low values of β. The main distinction between the two games is the following: • In Game 1 (high stability margin), when suboptimal and optimal recurrent classes collapse together, the resulting unique recurrent class contains enough low-welfare action profiles that the average payoff (over algorithm initializations) immediately begins to decrease with β. • In Game 2 (low stability margin), the suboptimal and optimal recurrent classes collapse into a unique recurrent class which contains only an optimal action profile, at least until β>0.1β>0.1. While our experiments cannot tell if this is a statistically significant distinction, it may hint at further structure to be studied and will be the subject of future work. The experimental results also validate the “safety guarantee” of Theorem 4; the green trace in each plot of Figures 5 and 6 (the empirically-estimated minimum welfare of any recurrent state) remains substantially above the black dashed line (the lower bound given in Theorem 4). 6 Discussion and Conclusions We propose the class of TNBR algorithms as applied to 2-agent submodular maximization problems, and we analytically prove worst-case guarantees on the recurrent classes of the resulting Markov chain. To our knowledge, these guarantees are the first of their kind beyond the simple decades-old bounds provided by Price of Anarchy analysis. We hope this inspires new questions in the study of performance in multiagent optimization algorithms: future work should investigate more nuanced questions than those of traditional worst-case equilibrium analysis. We hope to extend our result to general n-player submodular games. To date, we have found no straightforward extensions beyond 22 players. It is possible to prove a multi-player version of Lemma 1, but we have been unable to find a way to use it to prove serviceable bounds such as those presented in Theorem 4. Many of the 2-player results (e.g., (7)) are facilitated by the fact that any action profile can be reached by any other in at most 2 unilateral deviations; as the number of agents grows, this “deviation distance” grows accordingly and may require different mathematical techniques to analyse. Last, we note that TNBR algorithms share a common scalability limitation with classical best-response-based algorithms (e.g., [13]) and other stochastic algorithms with payoff-dependent probability distributions (e.g., logit-response dynamics [1]): agents must evaluate their utility functions for every available action at every timestep. For games with large action sets, this becomes computationally prohibitive. Accordingly, future research could investigate payoff-based or sampling-based approaches to promote better scaling behavior. APPENDIX: Proofs Proof of Lemma 2: First, note that x¯ x is the minimum value of the system objective function that can be achieved when any agent unilaterally deviates from the optimal. As in the proof of Lemma 2, we assume without loss of generality that x¯ x is achieved by unilateral deviation by agent 1, i.e., x¯=W(a1′,a21) x=W(a_1 ,a_2^1) for some a1′∈1a_1 _1. The analysis follows in the exact similar manner if x¯ x were achieved by the deviation of agent 2. Fix β and consider the problems with non-empty ℛβ∗R_β^*. Consider any action profile (a1,a2)(a_1,a_2) in ℛβ∗R^*_β. If a1=a11a_1=a^1_1, then by (16), W(a1,a2) W(a_1,a_2) ≥ ≥ maxx¯,1−x¯, \ x,1- x\, ≥ ≥ maxmax1−x¯,x¯−2β,x¯−β. \ \1- x, x\-2β, x-β\. Now, say a1≠a11a_1≠ a^1_1. Observe that for all a~2∈2 a_2 _2, the set of action choices for player 1, ℬ1(a~2)∪1β(a~2)B_1( a_2) ^β_1( a_2) always guarantees a payoff more than max1−x¯,x¯−β \1- x, x\-β using (16). This implies that (a1,a2)∈ℛβ∗(a_1,a_2) _β^* under TNBR only if W(a1,a2′)≥max1−x¯,x¯−β for some a2′∈2.W(a_1,a_2 )≥ \1- x, x\-β for some a_2 _2. Then, the β-neighbourhood of best responses for player 2, ℬ2(a1)∪2β(a1)B_2(a_1) ^β_2(a_1) guarantees a payoff more than maxmax1−x¯,x¯−2β,x¯−β \ \1- x, x\-2β, x-β\. Since the agents can never move to an action profile worse than the ones in β-neighbourhood under TNBR algorithms, and since the above is true for any (a1,a2)(a_1,a_2), the proof is complete. ■ Proof of Theorem 2: Let x¯ x be defined as in (7); that is, the minimum value of system objective function that can be achieved when any agent unilaterally deviates from the optimal. As in the proof of Lemma 2, we assume without loss of generality that x¯ x is achieved by unilateral deviation by agent 1, i.e., x¯=W(a1′,a21) x=W(a_1 ,a_2^1) for some a1′∈1a_1 _1. The analysis follows in the exact similar manner if x¯ x was achieved by the deviation of agent 2. For any a2′∈2a_2 _2, first observe by the definition of x¯ x in (7) and Lemma 1 that W(a11,a2′) W(a_1^1,a_2 ) +x¯≥W(a11,a21)=1, thus +\ x\ ≥\ W(a_1^1,a_2^1)=1, thus W(a11,a2′) W(a_1^1,a_2 ) ≥ ≥ 1−x¯, and again by (7), 1- x, and again by eqn_x_bar, W(a11,a2′) W(a_1^1,a_2 ) ≥ ≥ maxx¯,1−x¯≥12∀a2′∈2, \ x,1- x\\ ≥\ 12\ ∀\ a_2 _2, (16) because maxx¯,1−x¯≥12 \ x,1- x\≥ 12 for all x¯∈[0,1] x∈[0,1]. If (a1∗,a2∗)(a_1^*,a_2^*) is an absorbing state for the Markov chain generated using TNBR algorithms with noise parameter β, then it is trivially an NE, and W(a1∗,a2∗)−β>W(a11,a2∗)≥12W(a_1^*,a_2^*)-β>W(a^1_1,a_2^*)≥ 12 by (16). ■ Proof of Theorem 3: Let (a1,a2)∈ℛβ(a_1,a_2) _β. Then44 4 If any of (17) or (18) do not hold, then (a1,a2)(a_1,a_2) can lead to the optimal action profile (a11,a21)(a_1^1,a_2^1), violating the definition of the sub-optimal class. If (19) and (20) both do not hold then (a1,a2)(a_1,a_2) cannot be in ℛβR_β. W(a11,a2) W(a_1^1,a_2) < < maxa∈1W(a,a2)−β, _a _1W(a,a_2)-β, (17) andW(a1,a21) and\ \ W(a_1,a_2^1) < < maxb∈2W(a1,b)−β, _b _2W(a_1,b)-β, (18) and at least one of the following must hold: W(a1,a2) W(a_1,a_2) ≥ ≥ maxa∈1W(a,a2)−β, _a _1W(a,a_2)-β, (19) and/orW(a1,a2) and/or\ \ W(a_1,a_2) ≥ ≥ maxb∈2W(a1,b)−β. _b _2W(a_1,b)-β. (20) Say (19) holds. Then by (16) and (17), 12≤W(a11,a2)<maxa∈1W(a,a2)−β≤W(a1,a2). 12\ ≤\ W(a_1^1,a_2)< _a _1W(a,a_2)-β\ ≤\ W(a_1,a_2). (21) Thus, we only need to consider the case when (20) holds and (19) does not – we must have some b~∈2 b _2 with (a1,b~)∈ℛβ(a_1, b) _β such that55 5 When (19) does not hold, (a1,a2)(a_1,a_2) is not reachable by action of player 1, thus it much be reachable by action of player 2 – thus, there must be some action profile (a1,b~)∈ℛβ(a_1, b) _β reachable by action of player 1 such that player 2 can reach (a1,a2)(a_1,a_2) from (a1,b~)(a_1, b)., W(a1,b~) W(a_1, b) ≥ ≥ maxa∈1W(a,b~)−β>W(a11,b~). _a _1W(a, b)-β\ >\ W(a^1_1, b). (22) We now prove (5) using contradiction. Say W(a1,a2)=12−β2−ϵW(a_1,a_2)= 12- β2-ε for some ϵ≥0ε≥ 0. Using equations (18) and (20), W(a1,a21) W(a_1,a^1_2) < < maxb∈2W(a1,b)−β≤12−β2−ϵ. _b _2W(a_1,b)-β\ ≤\ 12- β2-ε. 8.53581pt (23) By Lemma 1, W(a11,b~)≥1−W(a1,a21)>12+β2+ϵW(a_1^1, b)≥ 1-W(a_1,a_2^1)> 12+ β2+ε. Further by (22) and (23), we have the contradiction, 12+β2+ϵ 12+ β2+ε < < W(a11,b~)<W(a1,b~)≤12+β2−ϵ. W(a_1^1, b)\ <\ W(a_1, b)\ ≤\ 12+ β2-ε. Towards proving (6), say W(a1,a2)=12−δW(a_1,a_2)= 12-δ for 0≤δ<β20≤δ< β2. By (21), equation (19) must not hold, thus (20) should be true. By (18) and (20), 12−δ=W(a1,a2)≥maxb∈2W(a1,b)−β 12-δ=W(a_1,a_2)\ ≥\ _b _2W(a_1,b)-β > > W(a1,a21). W(a_1,a^1_2). Thus, by Lemma 1, W(a11,a2)>12+δW(a^1_1,a_2)> 12+δ. Using (17), 12+δ<W(a11,a2) 12+δ\ <\ W(a_1^1,a_2) < < maxa∈1W(a,a2)−β _a _1W(a,a_2)-β maxa∈1W(a,a2) _a _1W(a,a_2) > > 12+δ+β, 12+δ+β, and since argmaxa∈1W(a,a2)∈ℛβ _a _1W(a,a_2) _β whenever (a1,a2)∈ℛβ(a_1,a_2) _β, (6) is true. ■ References [1] C. Alós-Ferrer and N. Netzer (2010) The logit-response dynamics. Games and Economic Behavior 68 (2), p. 413–427. External Links: Document, ISBN 0899-8256, ISSN 08998256, Link Cited by: §1, §6, Example 1. [2] P. N. Brown, J. H. Seaton, and J. R. Marden (2023) Robust networked multiagent optimization: designing agents to repair their own utility functions. Dynamic Games and Applications 13 (1), p. 187–207. Cited by: §1. [3] B. L. Ferguson, P. N. Brown, and J. R. Marden (2022) The Effectiveness of Subsidies and Tolls in Congestion Games. IEEE Transactions on Automatic Control 67 (6), p. 2729–2742. External Links: Document, 2102.09655, ISSN 0018-9286, Link Cited by: §1. [4] Y. Giannakopoulos, A. Grosz, and T. Melissourgos (2024) On the Smoothed Complexity of Combinatorial Local Search. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), External Links: Document, 2211.07547, Link Cited by: §1. [5] M. Kandori, G. J. Mailath, and R. Rob (1993) Learning, Mutation, and Long Run Equilibria in Games. Econometrica 61 (1), p. 29–56. External Links: Document, ISBN 00129682, ISSN 0012-9682 Cited by: Example 2. [6] M. Kandori and R. Rob (1995) Evolution of equilibria in the long run: a general theory and applications. Journal of Economic Theory 65 (2), p. 383–414. Cited by: Example 2. [7] I. Kordonis, M. M. Dessouky, and P. A. Ioannou (2019) Mechanisms for cooperative freight routing: incentivizing individual participation. IEEE Transactions on Intelligent Transportation Systems 21 (5), p. 2155–2166. Cited by: §1. [8] D. S. Leslie and J. R. Marden (2011) Equilibrium selection in potential games with noisy rewards. In International Conference on NETwork Games, Control and Optimization (NetGCooP 2011), p. 1–4. Cited by: §1, §2, §2. [9] D. A. Levin and Y. Peres (2017) Markov chains and mixing times. Vol. 107, American Mathematical Society. Cited by: §3. [10] C. Liu, K. Lu, X. Chen, and A. Szolnoki (2023) Game-theoretical approach for task allocation problems with constraints. Applied Mathematics and Computation 458, p. 128251. Cited by: §1. [11] J. R. Marden and J. S. Shamma (2015) Game theory and distributed control. In Handbook of Game Theory with Economic Applications, Vol. 4, p. 861–899. Cited by: §1, §1. [12] J. G. Martin, F. J. Muros, J. M. Maestre, and E. F. Camacho (2023) Multi-robot task allocation clustering based on game theory. Robotics and Autonomous Systems 161, p. 104314. Cited by: §1. [13] D. Monderer and L. S. Shapley (1996) Potential Games. Games and Economic Behavior 14 (1), p. 124–143. External Links: Document, ISBN 0899-8256, ISSN 08998256, Link Cited by: §1, §6. [14] D. Monderer and L. S. Shapley (1996) Potential games. Games and Economic Behavior 14 (1), p. 124–143. Cited by: §5.1. [15] J. R. Norris (1998) Markov chains. Cambridge University Press. Cited by: §3. [16] D. Paccagnan, R. Chandan, and J. R. Marden (2020) Utility Design for Distributed Resource Allocation—Part I: Characterizing and Optimizing the Exact Price of Anarchy. IEEE Transactions on Automatic Control 65 (11), p. 4616–4631. External Links: Document, ISSN 0018-9286, Link Cited by: §1, §5.3. [17] C. Papadimitriou (2001) Algorithms, games, and the internet. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, p. 749–753. Cited by: §1. [18] G. Qu, D. Brown, and N. Li (2019) Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions. Automatica 105, p. 206–215. Cited by: §1. [19] J. H. Seaton and P. N. Brown (2023) On the Intrinsic Fragility of the Price of Anarchy. IEEE Control Systems Letters 7, p. 3573–3578. External Links: Document, ISSN 2475-1456, Link Cited by: §1, §2, §3, §4.1, §5.3. [20] V. Singh and P. N. Brown (2024) ABRA: An algorithm which cannot converge to low-quality Nash equilibria. In 2024 IEEE 63rd Conference on Decision and Control (CDC), p. 1745–1750. External Links: Document, ISBN 979-8-3503-1633-9, Link Cited by: §1, Example 2, Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guaranteesfootnoteinfo. [21] V. Singh, W. Wesley, and P. N. Brown (2025) Optimal utility design with arbitrary information networks. In 2025 American Control Conference (ACC), Vol. , p. 2895–2900. External Links: Document Cited by: §1. [22] A. Vetta (2002) Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., p. 416–425. External Links: Document, ISBN 0-7695-1822-2, ISSN 0272-5428, Link Cited by: §1, §1, §1, §2, §4.1, §5.1. [23] H. P. Young (1993) The Evolution of Conventions. Econometrica 61 (1), p. 57–84. External Links: Document, ISBN 0792335198 Cited by: Example 2.