Considerate Equilibrium

1 Introduction

Multi-agent scenarios, in which self-motivated, rational actors share resources, allocate tasks or compete for production or communication lines, are central to AI. Natural tools for the analysis of such interactions include the well-studied solution concepts developed for strategic games. Rationality is usually captured in a way that agents are acting autonomously in order to maximize their own utility function. This leads to much interest in the study of stable outcomes, making it the central topic in game theory. In strategic games, the standard concept of stability is the Nash equilibrium (NE)- a state resilient to unilateral changes of players' strategies. While every finite game possesses a mixed Nash equilibrium, a pure strategy Nash equilibrium is not guaranteed in general, though has been proven to exist in several interesting classes such as congestion (or, potential) games [12, 15]. A drawback of Nash equilibrium is that it neglects coalitional deviations by groups of players; these are captured most prominently by the notion of strong equilibrium (SE) [3], where no coalition can strictly improve the utility of all participants. A slightly stronger variant, termed super-strong equilibrium (SSE) [5,16], guarantees that no coalition can strictly improve any participant without deteriorating at least one other member. SSE postulates the natural and widely considered condition of (strong) Pareto efficiency [13] for every coalition. However, while stability against deviations by coalitions of players is a most natural desideratum, it is well-known that there are only very few strategic games with SE, and SSE are even harder to guarantee.

∗This work was supported by the German Israeli Foundation (GIF) under contract 877/05, by DFG grant Ho 3831/3-1 and by the National Research Foundation (Singapore) under grant 2009-08.

However, in contrast to the assumptions underlying SE and SSE, many real-life scenarios allow only certain subsets of players to cooperate and apply joint deviations. Indeed, to deviate collectively, a group of players has to find a deviation, agree on it, and coordinate individual actions. This is impossible for a subset of players that are completely unrelated to each other. To this end, a promising recent approach for limited coalitional deviations was proposed in [5], where there is a given partition of the set of players such that only sets of the partition can implement joint actions. A partition equilibrium is a SSE subject to feasible coalitions being restricted to player sets in the partition only. In contrast to standard SSE, partition equilibrium was shown to always exist in resource selection games (RSGs) [1]; moreover, corresponding strategy profiles are also NE-that is, coalitional and unilateral stability are obtained simultaneously.

In this paper, we significantly strengthen the partition equilibrium concept by considering coalitional deviations and stable outcomes based on a rich combinatorial structure derived from a social network among the players rather than just partitions. We assume that players in a strategic game correspond to the set of nodes in a graph, where edges represent social relations (or, communication links) among the players. In addition, there are coordination constraints that prescribe what coalitions can potentially emerge and jointly deviate in the game. In particular, we focus on the natural case where potential coalitions of players are fully connected-that is, the set of feasible coalitions corresponds to the set of all possible cliques in the graph.

Crucially, besides the ability of cooperation, the presence of social links may also affect the strategic interests of players in the game. In this spirit, social context games [2] were proposed to model scenarios where a player's utility can depend on the payoffs of other players. For example, a player may be interested in ranking his payoff as high as possible comparing to the others' payoffs [4], or a player may care about the total payoff of a subset of his "friends", as in coalitional congestion games [8, 11]. A social context game is then defined by some underlying game, the social context given by some topological or graph-theoretic structure of neighborhood, and aggregation functions capturing the effects of utility changes in the underlying game on player incentives. In [2], RSGs are considered as the underlying games, and four natural social contexts are studied. However, unlike for partition equilibrium, this work deals only with unilateral deviations.

This paper studies the interplay between social structure and the outcome of multi-agent interaction in yet another way. Instead of relating a player's utility to the payoffs of other participants, we consider the effects their actions may have on it. In presence of social connections, these effects introduce additional incentives for the players and may have crucial influence on the decisions they make in the game. For example, in social networks such as FaceBook or LinkedIn, links among the agents represent friendships, professional partnerships, or even family relations. In other contexts of interest, agents may be tied by business contracts, technological dependencies or communication lines. In such scenarios, it is natural to expect that an agent will behave in a "considerate" manner and avoid taking actions that may harm his neighbors in the network. This motivates the study of consideration in strategic games, which is in the main focus of our work. As far as we are aware, this paper is the first to address this issue.

The solution concepts naturally corresponding to considerate behavior extend the notions of NE, SE and SSE to consider decisions (either group or individual) that do not deteriorate any neighboring players. Focusing on the natural case where coalitions of players that execute a strategy change must be fully connected, we define the considerate equilibrium to be a state in which (1) no coaliton formed by a clique in the social network can deviate so that the utility of at least one member of the coalition strictly improves and (2) none of the players neighboring the clique gets worse.

We observe that partition equilibrium evolves as a special case of considerate equilibrium when the social network is composed of a set of disjoint cliques. Indeed, one may find that the restriction of coalitional deviations in partition equilibrium essentially postulates two structural properties: (1) coalitions of players that execute a strategy change have to be "close" to each other, and (2) their decision must strictly benefit at least one of them but not strictly deteriorate any other player close to them. The notion of closeness is defined in both cases simply as being in the same partition set. However, while [2, 5] are initial steps in relating the social structure to the outcome of a game, they are quite restrictive in that only particular social contexts and fixed coalitional structures (partitions) are considered. In addition, they generally ignore the phenomenon of considerate behavior which is present in our work. Similar arguments apply w.r.t. [7], where fixed coalition structures in load balancing and congestion games are studied. Here coalitions act as single "splittable" players that strive to minimize the makespan or the sum of costs of the agents in the coalition.

We explore the concept of considerate behavior in the prominent class of resource selection games. In an RSG, each player chooses one of a finite set of resources, and its cost is given by a delay function depending on the number of players choosing the same resource. RSGs are a fundamental setting in computer science, operations research and economics, due to their practical applicability (e.g., in electronic commerce and communication networks) and plausible analytical properties. In particular, for strictly increasing delay functions, SE always exist [9, 10], but SSE is not guaranteed [5]. The latter fact has been prominently utilized to demonstrate the power of limited coalitional deviations [1, 5].

1.1 Our Results

We show that regardless of the social network topology, all RSGs with strictly increasing delay functions possess a considerate equilibrium. Our proof in Section 3 is constructive and yields an efficient algorithm for computing such an equilibrium. Importantly, the computed considerate equilibrium is also a standard NE for a given RSG, thus showing that there exists a state that is stable against selfish and considerate behavior simultaneously. Observe that the number of cliques might be exponential in the number of players, which makes non-trivial even the computation of a single improving move. We solve this problem by showing that, in an NE, every profitable deviation of a clique is witnessed by a move of a single player that decreases a suitably defined potential function. In addition, our proof is fundamentally different and significantly simpler than the existence proof for the special case of partition equilibrium in [1].

In Section 4, we study convergence properties of considerate dynamics. Let us remark that the potential function argument used in our existence proof does not imply that the sequential dynamics defined by deviations of cliques is acyclic, since the single player moves considered in the existence proof do not necessarily correspond to allowed improving moves. Indeed, we show that even for identical, strictly increasing delays there are infinite sequences of improving moves of cliques. This is in contrast to the dynamics corresponding to partition equilibrium, for which we show the finite improvement property in this setting.

2 Preliminaries and Initial Results

A strategic game is a tuple (N, (Si)i∈N , (ui)i∈N), where N is the set of n players, ans Si is a strategy space of player i. A state s of the game is a vector of strategies (s1, . . . , sn), where si ∈ Si. For convenience, we use s-i to denote (s1, . . . , si-1, si+1, . . . , sn), i.e., s reduced by the single entry of player i. Similarly, for a state s we use sC to denote the strategy choices of a coalition C ⊆ N and s-C for the complement, and we write s = (sC, s-C). The utility of player i in state s is ui(s) ∈ R. For a state s a coalition C ⊆ N is said to have an improving move if there is s′C such that ui(s′C , s-C) > ui(s) for every player i ∈ C. In particular, the improving move is unilateral if |C| = 1. A state has a weak improving move if there is C ⊆ N and s′C such that ui(s′C , s-C) ≥ ui(s) for every i ∈ C and ui(s′C , s-C ) > ui(s) for at least one i ∈ C. A (pure strategy) Nash equilibrium (NE) [14] is a state that has no unilateral improving moves, a strong equilibrium (SE) [3] is a state that has no improving moves, and a super-strong equilibrium (SSE) [5] is a state that has no weak improving moves.

To model considerate behavior, we adjust the definition of improving moves. In particular, there is an undirected, unweighted graph G = (N,E) over the set of players. For a subset C ⊆ N, consider the neighborhood of C as N(C ) = {j ∈ N | ∃i ∈ C, {i, j} ∈ E}.

Definition 1 (Considerate Improving Moves) A state s has a considerate improving move for a coalition C if there is s′C such that ui(s′C , s-C) > ui(s) for all i ∈ C and uj(s′C , s-C) ≥ uj(s) for all j ∈ N(C ). For a unilateral considerate improving move we have |C| = 1. A state s has a weak considerate improving move for a coalition C if there is s′C such that ui(s′C , s-C) ≥ ui(s) for all i ∈ C ∪N(C ) and ui(s′C , s-C) > ui(s) for at least one i ∈ C.

Note that every (weak/unilateral) considerate improving move is also a (weak/unilateral) improving move but not vice versa. To define coalitional equilibria, let us, for the time being, also assume that there is a set system of feasible coalitions C ⊆ 2N . A considerate Nash equilibrium (CNE) is a state s that has no unilateral considerate improving moves. A (super) strong considerate equilibrium ((S)SCE) is a state s that has no (weak) considerate improving move for a coalition C ∈ C. Note that for CNE we implicitly assume C is the set of all singleton sets {i} for all i ∈ N. Every NE is a CNE, and every (S)SE is a (S)SCE. The converse only holds for CNE and NE if E = ∅. In general, (S)SCE are (S)SE only if E = ∅ and C = 2N . In this way, the presence of social ties and a non-trivial set of feasible coalitions weaken the structural requirements for the existence of equilibrium.

In the rest of the paper, we make the natural assumption that the set of feasible coalitions corresponds to the set of cliques in G. In our analysis, we focus on weak improving moves and study super strong considerate equilibria as we believe that this solution concept is most interesting not only from a technical point of view but also a natural and convincing model for the interaction of coalitional structures in the presence of a social network.

Definition 2 (Considerate Equilibria) A considerate equilibrium (CE) is a state s that has no weak considerate improving move for a coalition corresponding to a clique in G.

The notion of CE nicely generalizes partition equilibrium. In particular, a partition equilibrium is a CE if the social network G is partitioned into isolated cliques. Note that we do not explicitely assume that the set of feasible coalitions is restricted to maximal cliques. If the graph is partitioned into isolated cliques, however, this rather technical assumption made in the definition of partition equilibrium is a natural consequence of the assumption that the coalitions behave considerately towards their neighbors. In this way, since weak improving moves do not decrease the utility of neighboring players, one can assume w.l.o.g. that all members of a partition set participate in a coalition.

We apply the concept of consideration to resource selection games (RSG) 1 -a basic class of potential games [12, 15]. In an RSG, there is a set of resources R, and Si = R for every player i ∈ N. For a state s we denote by ℓr(s) the number of players that pick r ∈ R in s. For each resource r ∈ R, there is a delay function dr(x) ∈ R. Throughout the paper we assume that all delay functions are non-negative and strictly increasing. In a state with si = r, player i has cost ci(s) = -ui(s) = dr (ℓr (s)).

In this paper, we focus on RSGs with strictly increasing delays. In this case, it is known that NE exist [15], can be computed in polynomial time [6], and are equivalent to SE [9]. Moreover, the games possess a (strong) potential function [9, 12], i.e., every sequence of unilateral improving moves has finite length and ends in a NE/SE. Trivially, by restriction of improving moves, the same holds also for CNE and SCE. Interestingly, however, SSE are not guaranteed to exist even in simplest games. 2 In contrast, we prove below that all RSGs with strictly increasing delays possess considerate equilibria. However, even for identical resources, we show that there are infinite sequences of weak considerate improving moves of coalitions being cliques in G. This is in contrast to a special case where G is a disjoint set of cliques and CE reduces to partition equilibrium; in this case, there exists a potential function for weak (considerate) improving moves in games with identical resources.

3 Existence and Computation

This section contains our main theorem showing the existence of CE in RSGs with strictly increasing delay functions. The existence proof is constructive and yields a polynomial time algorithm computing a state that is both a CE and a standard NE, thus showing that the two equilibrium concepts intersect.

Theorem 1 For any RSG with strictly increasing delay functions and any associated social network G, there exists at least one state that is an NE and a CE. Moreover, there is a polynomial time algorithm computing such a state.

Proof : We describe a process that starts in a Nash equilibrium and converges to a CE. This process consists of movements of single players. Every strategy profile in this sequence is a standard Nash equilibrium.

Consider a state s. Let dmax denote the maximal delay of a player in s. Note that in a Nash equilibrium, each used resource r has either delay dr(ℓr) = dmax or dr(ℓr) < dmax and dr(ℓr + 1) ≥ dmax. In the former case, we call resource r a high resource, in the latter case, we call it a low resource if additionally dr(ℓr + 1) = dmax. Let Ni,r(s) denote the set of neighbors of player i in G that are on resource r in s.

1 Also being referred to as simple congestion games , singleton congestion games or parallel link games

2 Consider a game with N = {1, 2, 3}, R = {r1, r2}, and dr1 (x) = dr2 (x) = x.

We are now ready to describe the process:

1. Compute a Nash equilibrium s.
2. If there is a player i placed on a high resource r and there is a low resource r′ with |Ni,r(s)| > |Ni,r′ (s)| then set s = (s-i, r′ ), and repeat this step.
3. If there is a player i placed on a high resource r and there is a low resource r′ with |Ni,r(s)| = |Ni,r′ (s)| and dr(ℓr(s) - 1) < dr′ (ℓr′ (s)) then set s = (s-i, r′ ), and continue with step 2.
4. Output s.

Note that each state produced by this process is a Nash equilibrium. During this process, the following potential function

decreases strictly from step to step, where we use Ni(s) = Ni,si (s) as a shorthand for the neighbors of i on the same resource and assume M > ∑r∈R dr(n). One can easily modify the delay functions such that M = n|R|2 without changing the players' preferences which implies that the process terminates after polynomially many steps.

To prove that this process results in a CE, we show that if a state s is a NE and there exists weak considerate improving move s′C , then there is also a move of a single player i ∈ C as described above.

Let H and L denote the set of high and low resources in s, respectively. Let Rh be the set of resources that are high in s but no longer high in (s′C , s-C), and let Rl be the set of resources that are low in s and become high in (s′C , s-C). By definition, Rh ⊆ H and Rl ⊆ L. Let Nh be the set of players of C on resources of Rh in s, and let Nl be the set of players of C on resources of Rl in s.

Lemma 2 During the move s′C , all players in Nl are moving from resources in Rl to resources outside of Rl. In turn, |Nl| + |Rl| players are moving from resources in H to the resources in Rl. Finally, at least |Nl|+|Rl| players are leaving Rh towards resources outside of Rh.

Proof : Since s′C is a weak considerate improving move, all players in Nl must move from resources in Rl to resources outside of Rl as their delay would increase, otherwise. These players can only be replaced by players from H as other players would have an increased delay after the move, otherwise. In turn, altogether |Nl| + |Rl| players need to move from H to Rl so that the resources of Rl become high resources after the move. Furthermore, we observe that the number of players on resources in H \ Rh does not change during the considered move, and there are no players entering H \ Rh from outside of H as such players would have an increased delay, otherwise. As a consequence, there must be at least |Nl| + |Rl| players that are leaving Rh towards H \ Rh or Rl in order to have |Nl| + |Rl| players that move from H to Rl. This proves Lemma 2. ✷ The lemma implies

Let maxh = maxi∈Nh Ni(s) denote the maximum number of neighbors that a player of Nh has on his resource. The definition maxh implies

Note that no player of C has a neighbor that has chosen a resource from Rl and is not in C. Otherwise, this neighbor's delay would increase during the move so that s′C would not be a considerate move. Therefore, we can set minl = mini∈Nh,r∈Rl Ni,r(s), where the choice of i is irrelevant. The definition of minl immediately implies

Let us derive some more helpful equations regarding the different kinds of resources. For each resource that decreases its load during the improving move, there is at least one resource that increases its load by one because the number of players on each low resource can only increase by one. This gives

Combining the Equations (2), (1), and (3) gives

Now, we distinguish between the following two cases.

Case 1: maxh > minl. In this case, we can set i = argmaxj∈Nh Nj(s) and r′ = argminr∈Rl Ni,r(s), which satisfies the conditions of step 2 of the process.

Case 2: maxh ≤ minl. In this case, Equation 5 yields |Rh| ≥ |Rl|, which, coupled with Equation 4, implies |Rh| = |Rl|. Substituting this equality back into the Equation 5 gives maxh ≥ minl which implies maxh = minl. Define q = |Rh| = |Rl| and k = maxh = minl. Now Equations 2 and 3 yield |Nh| ≤ |Nl|+q, which in combination with Equation 1 gives |Nh| = |Nl| + q.

On average, the resources in Rl hold |Nl|/q players from C in state s and the resources Rh hold |Nh|/q players from C. We claim that this implies that each resource in Rl holds exactly |Nl|/q players from C; and each resource in Rh holds exactly |Nh|/q players from C and no additonal neighbor of one of them. To see this, let rh denote a resource from Rh holding a maximum number of players from C and let rl denote a resource from Rl holding a minimum number of players from C. Let i ∈ Nh be a player assigned to rh. As s′C is a considerate move, i does not have neighbors outside of C on rl. Thus, if the claim above would not hold, i would have either at least |Nh|/q neighbors on rh or strictly less than |Nh|/q - 1 = |Nl|/q neighbors on rl, which would imply maxh > minl and thus contradict our assumption. As a consequence, |Ni,r(s)| = k = Ni,r′ (s)|, for every i ∈ Nh, r ∈ Rh, and r′ ∈ Rl.

Now, Lemma 2 implies that each of the q resources in Rl is left by its k players from C and each of the q resources in Rh is left by its k + 1 players from C.

We make a few further observations: The definition of Rh implies that the number of players on a resource fromH \Rh does not decrease during the considered move. Besides, this number cannot increase due to a weak improving move. Next consider a resource r ̸∈ H ∪Rl. The definition of Rl implies that the number of players on r cannot increase during a weak improving move. Now suppose the number of players on r would decrease. Then there is a leaving player i, who moves to either Rh or another resource in L \ Rl, as its delay would increase, otherwise. In the latter case, a different player must make room for i. By following this player, we can iteratively construct a chain of moving players until finally there is a player that moves to a resource in Rh. Thus, together with the players leaving the resources in Rl there are at least qk + 1 that need to migrate to a resource with a delay of less than dmax (after the move). However, the resources in Rh have only a capacity for taking qk many of such players. Hence, the number of players on any resource outside of Rl or Rh does not change during this move.

Now, take one of the players from Nl. During the considered move, this player migrates to another resource having a delay strictly less than dmax (after the move). If this resource does not belong to Rh then another player needs to leave this resource in order to compensate for the arriving player. Following that player, we iteratively construct a chain of moving players, leading from a resource in Rl to a resource in Rh. In this manner, we can decompose the set of moving players into a collection of qk many chains each of which leads from Rl to Rh. As we are considering a weak improving move, the delays in each of these chains does not increase and there is at least one such chain leading from a resource r′ ∈ Rl to a resource r ∈ Rh with dr(ℓr(s) - 1) < dr′ (ℓr′ (s)). We choose an arbitrary player i ∈ Nh assigned to resource r in s. We have shown above that for this player |Ni,r(s)| = Ni,r′ (s)| holds. Thus, player i satisfies the condition in step 3 of our process, which completes our analysis for Case 2.

This shows that, when the process terminates, there are no weak considerate improving moves. Therefore, the resulting state is a CE. ✷

4 Convergence

Next we show that the dynamics of weak considerate improving moves by general cliques does not have the finite improvement property, i.e., the dynamics corresponding to CE might cycle (Theorem 3). Our construction works even for resources with identical delays. This separates considerate equilibrium from partition equilibrium as, in the same setting, the dynamics corresponding to partition equilibrium admits the finite improvement property (Proposition 4).

Theorem 3 There are symmetric RSGs with strictly increasing and identical delays, for which there are infinite sequences of weak considerate improving moves by coalitions that are cliques in G.

Proof : For the proof we construct a game with a modular structure. Our game consists of a number of smaller games, referred to as blocks. Each block consists of 14 players and 5 resources, and by itself it is acyclic. However, by creating social ties across blocks, we create larger cliques that are able to perform "resets" in one block while making improvements in other blocks. By a careful scheduling of such reset moves we construct an infinite sequence of moves.

More formally, we have 19 blocks, and in each block i, we have 14 players. There are 8 players Bi ,C i ,Di ,Ei , F i ,Gi , P i ,Qi involved in our sequence, while 6 additional "dummy" players never move. The dummy players are singleton nodes in the social network and are only required to, in essence, simulate non-identical resources by increasing some of the delays to larger values. The social graph consists of internal links within each block and inter-block connections as follows. For each block, there are edges {Bi , F i }, {C i , Ei } and {Di , Gi }. In addition, for each i = 1, ..., 19 there are two inter-block cliques,

• {Di , P i , P i+1 ,Bi+1 ,Di+2 , P i+2 ,C i+6 ,Ei+6 } and
• {Di ,Qi ,Qi+1 ,C i+1 ,Di+2 ,Qi+2 ,Bi+9 , F i+9 },

where the exponent is meant to cycle through the numbers 1 to 19, i.e., above P j means P ((j-1) mod 19)+1 .

The 95 resources are denoted by rij with i = 1, . . . , 19, j = 1, . . . , 5. The delay functions are identical dr(x) = x for all r ∈ R. Note that in general, our example does not require linear delays, it suffices to ensure dr(3) > dr(2).

Let us consider a single block i and a sequence of six states within this block depicted in Fig. 1. Note that α → β rep-

resents a weak considerate improving move for {Di ,Gi }, where Di performs the move, and Gi strictly improves. Similarly, β → γ is a weak considerate improving move for {Ci ,Ei }, δ → ϵ for {Di ,Gi }, and ϵ → ζ for {Bi , F i }. The steps γ → δ and ζ → α are resets, in which a cyclic switch is performed and no player within the block strictly improves. It suffices to show that these steps can be implemented with improving moves by inter-block cliques.

Consider the first reset γ → δ, in which Di and Bi swap places, and for simplicity assume w.l.o.g. that i = 5. This swap is executed in three moves, where we first swap in P 5 for D5 , then swap P 5 and B5 and finally swap out P 5 to bring D5 back in. This cyclic switch is the result of the following sequence of weak considerate improving moves: (1) coalition {D3 , P 3 , P 4 ,B4 ,D5 , P 5 ,C 9 ,E9 } applies a deviation where D5 and P 5 exchange their places, and C 9 moves away from E9 in block 9 as β → γ prescribes; (2) coalition {D4 , P 4 , P 5 ,B5 ,D6 , P 6 ,C 10 ,E10 } improves by swapping P 5 and B5 , and moving C 10 away from E10 in block 10; (3) finally, D5 and P 5 swap with coalition {D5 , P 5 , P 6 , B6 , D7 , P 7 , C 11 , E11 } where C 11 moves away from E11 in block 11. In the final dynamics, we will use these moves also to simultaneously perform swaps in the other blocks 3, 4, 6, and 7.

The second reset swap ζ → α by D5 and C 5 can be done in similar fashion by a circular swap involving Q5 and using the Bi and F i players of blocks i = 12, 13, 14. Note that our edges are carefully designed not to generate any undesired connections. In particular, D5 , P 5 , B5 rely on the movement of C 9 , C 10 and C 11 to execute their swaps. During these swaps, B9 , B10 and B11 are deteriorated. None of the deteriorated players are attached to players in the respective improving coalitions, i.e., none of D3 , P 3 , P 4 , B4 , D5 or P 5 are neighbors with B9 , none of D4 , P 4 , P 5 , B5 , D6 or P 6 are neighbors with B10 , and none of D5 , P 5 , P 6 , B6 , D7 or P 7 are neighbors with B11 . In addition, for making the switch between D5 , Q5 and C 5 we use the movement of B12 , B13 and B14 . Note that none of the players required to execute the switches are neighbors with C 12 , C 13 or C 14 , respectively.

An infinite sequence of weak considerate improving moves can now, for example, be obtained from a starting state as follows. We indicate for each block in which state α to ζ it is initialized. Here γ1, γ2, ζ1, and ζ2 indicate the intermediate states of the corresponding circular resetting swaps.

In the first step, we can simultaneously advance blocks 1-3 from (ζ2, ζ1, ζ ) to (α, ζ2, ζ1) using movement of B10 , which advances block 10 to ζ. In the next step we advance blocks 12-14 from (γ2, γ1, γ ) to (δ, γ2, γ1) using movement of C 18 , which advances block 18 to γ. Next, we make two internal switches in blocks 11 from δ to ϵ and 19 from α to β. In this way, we have shifted the state sequence by one block, which implies that we can repeat this sequence endlessly. ✷ In contrast, observe that if the graph is a set of disjoint cliques, then for games with identical and strictly increasing delay functions we can easily construct a potential function that implies acyclicity with respect to weak (considerate) improving moves.

Proposition 4 In every symmetric RSG with strictly increasing, identical delays functions, every sequence of weak improving moves of allowed partition sets is finite and ends in a partition equilibrium.

Note that in this case we can assume w.l.o.g. that dr(x) = x for all r ∈ R. Also, each weak improving move decreases the sum of costs of all players in the partition set. Thereby, the results of [7] for linear delays directly imply the finite improvement property.