Local-Effect Games

1 Introduction

Games have long been studied in AI as a model of compet­ itive multiagent interactions. In particular, many researchers in AI have been interested in finding Nash equilibria (c.f. [5; 2]; for an introduction to games and equilibrium concepts, see e.g. [3]). Recently, there has been a lot of work on compact representations of games with large numbers of players, and games for which the computation of equilibria is tractable [8; 15; 6; 7; 14; 9]. Much work in this vein has been based on the exploitation of one of two kinds of locality. First, some approaches exploit unconditional independencies be­ tween players' abilities to affect each other's payoffs [8; 15; 6; 1]. Second, some approaches exploit symmetry in util­ ity functions along with context-specific independencies be­ tween players' effects on each other; more precisely, games in which players' abilities to affect each other depend on the ac­ tions they choose. Here we study games in this second class, because we believe that this sort of context-specific indepen­ dence is more common in real-world games.

Although compact representation has not been a primary motivation for economists, some work from economics does fall into the framework defined above. Most influentially, Rosenthal defined congestion games [13]. In these games each agent i selects a subset Si from an available set of re­ sources R; where nr is the number of agents who choose resource r E R, and Fr are arbitrary functions for each r, agent i pays:

Observe that agent payoffs exhibit no unconditional inde­ pendencies: all agents are given the same action choices, and so all agents can affect each other's payoffs. On the other hand, context-specific independence does exist when two agents choose non-intersecting resource subsets. Rosen­ thal's main result in [13] was that congestion games always have pure-strategy Nash equilibria (PSNE) . This is importa~t because, although all games have mixed-strategy Nash eqUI­ libria [11], there are few known classes of interesting games with pure strategy equilibria. At the same time, pure strategy equilibria are attractive: they can be more likely to a~i~e ~n play as they are more intuitive than mixed-strategy eqmhbna for many players; they can be easier for agents to coordinate to; as there are a finite number of pure strategy profiles in a given game, they can be easier to compute than mixed strat­ egy equilibria.

Rosenthal's work was extended by Monderer and Shapley [10], who showed that the class of congestion games is equiv­ alent to the class of games with potential functions. Potential functions map agents' joint actions to a real number, with the property that if X and Y are strategy profiles differing only in the action choice of one agent i, P(X) - P(Y) is equal to the difference in i's payoff from selecting the two actions. This result is useful because it means that the construction of a potential function is sufficient for showing the existence of a pure-strategy equilibrium. Potential functions can also be used to compute equilibria: the set of pure-strategy Nash equilibria is equivalent to the set of strategy profiles that max­ imize P.

Recent work in computer science and AI has explored classes of games inspired by and extending congestion games. For example, Kearns et al. examined games with bounded effects [7], and Roughgarden studied a nonatomic variant [14]. In this paper we propose a new class, which we call local-effect games.

2 Local-Effect Games

In congestion games, whenever two agents affect each other's payoff, they each do so by the same amount. Local-effect games (LEGs) model situations where agents' effects on each other are potentially asymmetric. Generally, action A locally affects action B if the utility of agents taking action B de­ pends on some function F A ,B of the number of agents taking action A, but the utility of agents taking action A depends on a different function FB,A of the number of agents taking action B.

There are many natural settings which are modeled by such locally-effecting actions. One problem domain that has been studied in Economics for a three quarters of a century is the location problem [4]. These problems model situations where agents must choose a location to operate their busi­ ness in the presence of other competing agents, and each agent's profit depends on how far she is from her competi­ tors. The canonical example concerns ice cream vendors who must choose a spot on the beach to set up a kiosk, with agents' utility depending on how many other ice cream sell­ ers have located themselves in the same or adjacent areas. Work from Economics on this problem has usually dealt with one-dimensional continuous spaces and has not modeled lo­ cal effects explicitly; also, game theoretic analyses have typ­ ically considered only a small (e.g. 2 or 3) number of agents (c.f. [12]). It is easy to think of many variants on the loca­ tion problem: ice cream sellers arranging themselves around a lake (ring structure); vendors opening coffee houses in a city (grid structure); pairs at a cocktail party trying to pick a quiet room, with noise proportional to the number of peo­ ple in the room, and noise also emanating from nearby rooms (arbitrary structure).

Another natural domain modeled by LEGs is a role forma­ tion game, where agents can take on one of a set of partially­ substitutable roles. Agents are rewarded according to the amount of work they do, so their payoff is reduced as other agents adopt the same or similar roles.

Formally, let G = (A, F, n) be a local-effect game for n agents. A is the set of actions available to each player in the game. Let D denote the distribution of players across actions, and D( a) denote the number of players who chose action a E A. For every pair of actions a, a' E A, Fa,a' : z+ _, JR+ is the cost function expressing the cost due to the local effect from action a to action a', and depending on the number of agents having chosen action a. From this we can build the cost function of an agent a who chose action i E A:

We assume that in all local-effect games F is strictly monotonic: that 'Va, a' I a E A Fa,a' (x) either increases strictly monotonically with x or is always 0. Furthermore we assume 'Va, a' I a E A Fa,a' (0) = 0.

It is useful to think of a directed graph representing the ac­ tions and their local effects. We create a node for every action, and draw an edge from node i to node j if 'Vx F; ,j ( x) = 0 is false. We will sometimes denote functions of the form F; ,;(x) as node functions, and functions of the form Fi ,j(x), i I j as edge functions. Let neigh( i) denote the set of nodes to which there are directed edges originating at node i .

We make one assumption about this graph's connectivity:

That is, each pair of nodes in the graph are either both or neither neighbors of each other, though they might influence each other according to different local-effect functions.

Definition 1 A local-effect game is a bidirectional local­ effect game (B-LEG) when 'Va E A, 'Va' I a E AFa,a'(x) = Fa',a(x).

ForB-LEGs local-effect functions between pairs of actions are always the same in both directions; note however that for a given distribution of agents the magnitude of the local ef­ fects between a pair of actions may be different. The graph­ ical representation of actions and local effects in B-LEGs is undirected.

Definition 2 A local-effect game is a uniform local-effect game (U-LEG) when 'VA, B, C E A (BE neigh(A) 1\ C E neigh( A)) -> 'Vx FA,B(x) = FA,c(x).

That is, if action A has any effect on nodes B and C then the same function governs its effect on both. We define nota­ tion for the uniform effect from node A: F.4 (x) =FA,· (x).

3 Theoretical Results

3.1 Nonexistence of Pure Strategy Equilibria

Rosenthal was able to show that congestion games always have a PSNE. For local-effect games, we can find counter­ examples where exhaustive enumeration of strategies shows the absence of any PSNE, demonstrating that such a sweep­ ing general result is impossible. One example (found ex­ perimentally, and confirmed by exhaustive search) is the B­ LEG G = ({A, B, C}, F, 11), with FA,A(x) = 2.79x, FB,B(x) = 4.72x, Fc,c(x) = 1.5x, FA,B(x) = 0.64logx, FA,c(x) = 0.32logx, FB,c(x) = 2.77logx.

3.2 Pure Strategy Equilibria: Potential Functions

In this section we show that two interesting classes of local­ effect games have potential functions, meaning that they al­ ways have pure-strategy Nash equilibria. Although these re­ sults show regions of overlap between the class of conges­ tion games and the class of local-effect games, the potential functions themselves are interesting as their construction is nontrivial. Also, these results are useful because they make it possible for the games to be described in the more intuitive local-effect game framework.

Theorem 1 Bidirectional local-effect games have pure strat­ egy Nash equilibria if'Vi, 'Vj I i Fi ,j(x) = mi ,jX·

Sketch of Proof. Here we prove the result by giving a potential function:

The first term is the standard congestion game potential function. A game with only functions of the form Fi,i(x) is a congestion game, and so must have the congestion game po­ tential function. The relationship between each Fi ,j ( x) func­ tion and the agent's cost function is additive, and potential functions are only used for taking differences. Thus if we can find a potential function P' for a game with only local effects and all Fi,i(x) = 0, the potential function for a gen­ eral B-LEG will be the sum of the congestion game potential function and P'.

Thus it remains to argue that our second term is this P': that it captures changes in utility arising from local effects.

Consider the sum of the contribution of local effects to each agent's utility: s = 2:::~= 1 I:jEneigh(i) D(i)mj ,iD(j). When a single agent a deviates, s increases by twice the amount of the change to a's utility, because all Fi,j (x) are linear and bidirectional. That is, there is a change both in the amount of local effect acting on agent a, and new local effect caused by agent a, and bidirectionality and linearity imply that these two amounts are the same. Thus the desired result is obtained by adding ~s to the congestion game potential function. 0

Observe that Theorem 1 holds forB-LEGs with non-linear functions Fi,i(x)-what is required is linearity of the local­ effect functions.

Theorem 2 Uniform local-effect games have pure strategy Nash equilibria if the local-effect graph is a clique.

Sketch of Proof. Again we provide a potential function:

As argued in Theorem 1, to construct a potential function it is sufficient to add the standard congestion game potential function with a function that accounts for changes in utility due to local effects. This explains the first term.

Let distributions X and Y be identical except that Dx(A) = a and Dx(B) = {3, while Dy(A) = a- 1 and Dy(B) = {3 + 1. Assuming FA,A(·) = FB,B(·) = 0, P(X)- P(Y) = F'f3({3)- F,4(a- 1). This is precisely the change in utility for an agent deviating from A in X to B in Y: the agent will be spared the local effect F'f3({3) since he moves to B and is no longer subject to its local effect; how­ ever, since he moves away from A and the graph is a clique, he is now subject to the local effect F,4 (a - 1). Because the graph is a clique, and because the game is aU-LEG, the ar­ gument holds no matter which pair of nodes is chosen as A and B. 0

3.3 LEGs and Potential Functions

Finding potential functions is an effective way of proving the existence of pure-strategy equilibria; however, there are many LEGs for which potential functions can be shown not to exist. In this section we give a complete characterization of the class of LEGs which have potential functions.

Lemma 1 A local-effect game has a potential function if \Ia, a' E AFa,a'(·) = 0.

Sketch of Proof. Trivially, a LEG without any local effects is a congestion game. 0

Lemma 2 The class of potential games does not contain the class of local-effect games for which :JA, B, C E A where B E neigh(C) and not A E neigh(B) and not A E neigh( C) and (FB,C =f. Fc,B or FB,c is nonlinear).

Sketch of Proof. Assume for contradiction that every LEG in the class has a potential function P. We will consider three distributions of agents in order to derive properties of P. Without loss of generality, we take A, B and C to be the first three actions in the game, and we take the total number of actions to be n. For more compact notation in what follows, let a= D(A), {3 = D(B) and 1 = D(C). Define the follow­ ing three distributions: X = (a, {3, /, D( 4), .. . , D(n) ), Y = (a - 1, {3 + 1, 1, D ( 4), ... , D ( n)) and Z = (a, {3 + 1, 1 - 1, D(4) , . . . , D(n)). Without making any assumptions about the local effects between actions A, B and C and any of the other n- 3 actions, and for x E {A, B, C}, let:

That is, Ux(D(x), D( 4) , ... , D(n)) denotes the (negative) utility contributed to each agent taking action x E {A, B , C} by those agents also taking action x, and by those agents tak­ ing the 4 1 h through nth actions. For compactness we will ab­ breviate Ux(D(x), D(4), ... , D(n)) as ux(D(x)) below.

If distribution X were the case and an agent playing action A switched to action B, then distribution Y would be the result. Thus:

If X were the case and an agent playing action C switched to action B, then Z would be the result. Thus:

If Y were the case and an agent playing action C switched to action A, then Z would be the result. Thus:

From equations (7) and (8), we can infer:

Intersect equation (10) with equation (9) and rearrange. Observe that uA(a), uB(f3 + 1) and uc(T) all cancel out, demonstrating that this proof does not depend on what edges exist between A, B, C and the rest of the graph, or on node effects. Define Ia,a' ( x) = Fa,a' ( x) - Fa,a' ( x - 1): the in­ cremental cost on the local effect between a and a' of adding the x 1 h agent to a. We then get:

Clearly, equation (11) will not be satisfied for all {3, 1 un­ less FB,c = Fc,B and FB,C is linear. This contradicts our assumption that a potential function exists for every LEG in the class. 0

Lemma 3 The class of potential games does not contain the class of local-effect games for which 3A, B, C E A where B E neigh( C) and A E neigh(B) and not A E neigh( C) and (Fa,c =1- Fe, a or Fa,c is nonlinear or FA,B =1- Fa ,A or FA,B is nonlinear).

Sketch of Proof. This proof follows the proof of Lemma 2 and uses the same setting and definitions, except that (as stated in the theorem) A E neigh(B). Using the same ar­ guments about distributions X , Y and Z we can derive:

Clearly, equation (12) will not be satisfied for all a, /3,1 unless FA,B = Fs ,A, Fa,c = Fe, a, and both FA,B and :F B,C are linear. This contradicts our assumption that a po­ tential function exists for every LEG in the class. D

Lemma 4 The class of potential games does not contain the class of local-effect games for which 3A, B, C E A where BE neigh( C) and A E neigh(B) and A E neigh( C) and (:Fa ,c =1- Fc,B or Fa,c is nonlinear or FA,B =1- Fa,A or :FA,B is nonlinear or FA,C =1- Fc,A or FA,C is nonlinear) and (FA,B =1- FA,C or Fa,A =1- Fa,c or Fc,A =1- Fc,a).

Sketch of Proof. This proof follows the proof of Lemmas 2 and 3 and uses the same setting and definitions, except that (as stated in the theorem) A E neigh( B) and A E neigh( C) . Using the same arguments about distributions X, Y and Z we can derive:

Equation (13) may be rewritten as:

From equation (13) we can see that the contradiction does notobtainforalla,/3,1when:FA,B = FA,c,Fa,A = Fa ,c, and Fc,A = Fc,B· From equation (14) we can see that the contradiction does not obtain for all a, beta, 1 when FA,B = Fa ,A,Fa,c = Fc,a,FA,c = Fc,A and FA,a,FA,c and F B,C are all linear. If neither condition holds, our assump­ tion a potential function exists for every LEG in the class is contradicted. D

We can now completely characterize those classes of LEGs that have potential functions.

Theorem 3 The class of potential games contains the class of local-effect games for which any of the following hold:

1. the local-effect graph contains fewer than three nodes
2. the local-effect graph contains no edges
3. the game is a bidirectional local-effect game and all local-effect functions are linear
4. the game is a uniform local-effect game and the localeffect graph is a clique

No other local-effect games have potential functions.

Sketch of Proof. First, it is clear that a game with only a single action has a potential function. A LEG with only two actions is trivially aU-LEG and has a local-effect graph which is a clique, so by Theorem 2 it has a potential function . This proves statement 1 in the theorem, and leaves us to con­ sider LEGs which have 3 or more actions. We will do a case analysis considering all possible local-effect graph structures for these LEGs. Clearly, all graphs with 3 or more nodes are included if we consider all graphs with no edges, all cliques, and all graphs containing subgraphs having three nodes and either exactly one or exactly two edges.

Lemma 1 proves that if the local-effect graph has no edges then the LEG is a congestion game, proving statement 2.

If the local-effect graph contains a subgraph with three nodes and exactly one edge, and is not a B-LEG with linear functions, Lemma 2 shows that it does not have a potential function. If it is a B-LEG with linear functions, Theorem 1 shows that it has a potential function, proving statement 3.

If the local-effect graph contains a subgraph with three nodes and exactly two edges, and is not a B-LEG with linear functions (again, statement 3), Lemma 3 shows that it does not have a potential function.

If the local-effect graph is a clique, it contains a a clique of size three as a subgraph. If the graph is not a U-LEG, Lemma 4 shows that it does not have a potential function. If it is aU-LEG, Theorem 2 shows that it does have a potential function, proving statement 4. D

3.4 Other Pure-Strategy Equilibria

We are also able to prove the existence of pure-strategy Nash equilibria for classes of graphs, and node and edge functions that Theorem 3 shows cannot have potential functions. The following constructive proof has classes of B-LEGs and U­ LEGs as special cases:

Theorem 4 If a local-effect game satisfies

then there exists a pure-strategy Nash equilibrium in which agents choose nodes that constitute an independent set.

Sketch of Proof. This proof proceeds by induction, build­ ing up a Nash equilibrium one agent at a time, and with each agent making a myopic best response to the previous distribu­ tion. In the case of a single agent, it is clearly an equilibrium for him to select the best node. Define Di as the distribution of agents at induction step i. Assume that n - 1 agents have each selected the best node in turn, resulting in a distribution Dn-l which is a Nash equilibrium and also an independent set. We must show that when an additional agent n chooses the best node the resulting distribution Dn is still an indepen­ dent set, and still a Nash equilibrium.

First, we show that the new distribution is an independent set. Assume for the purposes of contradiction that it was best for n to choose a node that does not belong to the independent set. Then it must be the case that the selected node has at least one neighbor which has been chosen by one or more other agents. Let the node selected by n be A, and let B be some neighboring node. From condition 2 in the theorem (linearity/sublinearity), we can infer that:

From condition 1 in the theorem (functional dominance), we know that:

Thus we can use equation (16) to weaken the bound in equation (15) to get:

Define the utility at inductive step i for an agent taking action X, and disregarding any local effect from action Y:

At some step i in the induction, Di(B) = 0 and Di(A) = 0, but Di+1 (B) = 1. From the fact that the distribution of agents resulted from myopic choices (stated in the induction hypothesis), we know that:

We can use U A , ~B(1) in equation (18) because Di(B) = 0 anyway. From the monotonicity of local-effect functions, and the fact that i :S n we can write:

We can use equation (19) to weaken the bound given in equation (18):

Finally, we can use equation (20) to further weaken the bound given in equation (17). This gives us:

Equation (21) contradicts our assumption that agent n would myopically choose A over B; therefore Dn must be an independent set.

Now we show that D' is a Nash equilibrium. Let C be the node that the new agent i selected in making his myopic response to the distribution D. From symmetry of cost func­ tions we know that no agent can profitably deviate from node C: if so, i would have chosen a different node in the first place. Consider an agent j who chose a node V -=/=- C. Agent j's payoff does not change from distribution D to distribution D', because D' is an independent set, and so Fc,v( ·) = 0 (there are no local effects between nodes C and V. Since dis­ tribution D was a Nash equilibrium (inductive hypothesis) j will not deviate from a new distribution D' that differs only in that node C is more costly. D

4 Empirical Findings

Section 3 shows that there are many cases in which local­ effect games have pure-strategy Nash equilibria. Myopic best response has been shown to be an effective technique for computing pure strategy equilibria in a variety of settings [10]. In this section we show that this simple algorithm can compute pure strategy equilibria for very large local-effect games that are not covered by any of the positive results in section 3 and that do not have potential functions. We present five different graph structures with similar local-effect functions, and show sample equilibria. We should note that we have been able to find equilibria experimentally for most B-LEGs 1 with different graph structure and different local­ effect functions that we have tried, and that convergence oc­ curs within a second in most cases. As with our theoretical results, we do not claim that these equilibria are unique; in­ deed, because agents' cost functions are symmetric, a new equilibrium can always be constructed from a given equilib­ rium by swapping action choices between pairs of agents. Furthermore, we have observed many cases where multiple structurally different equilibria exist in the same local-effect game.

All games shown here are B-LEGs with \iA, \iB FA,B(x) = kA,B log(x + 1). We use one kn for all node functions and another ke for all edge functions (i.e., \iA, \iB -=/=- A kA,A kB,B and \fA, \iB -=/=- A, \iC rt {A, B} kA,B = kA,c). We hold ke = 1 throughout, and vary kn to highlight some of the more interesting equilibria. These equilibria are represen­ tative of average runs, and were found with a minimum of parameter manipulation. Each node is labelled with the number of agents choosing the node in equilibrium. Fig. 1 shows a T structure representative of a simple location problem. Fig. 2, which we call 'arbitrary' in what follows, I B 1s is interesting because there are 2 nodes with 2 neighbors, 2 with 3 neighbors and 2 with 4 neighbors. This setting could represent a role formation game. Fig. 3 shows a binary tree structure; observe that most agents select leaf nodes because they have only one neighbor, and thus the parents of leaves are chosen by few agents. Fig. 4 shows a two-dimensional grid, representative of our coffee house location problem. Observe that the corners are most desirable, as they have only two neighbors; nodes neighboring corners are thus under-populated, leading to another concentration of agents in the middle of each edge. It is also interesting that agents concentrate in the central node, even though it has four neigh­ bors, because its neighbors are relatively under-populated. Fig. 5 shows what happens to the game from Fig. 4 when we remove a single node (consider the same location problem when one node becomes unavailable). Observe that agents generally cluster around the missing node, except for one neighboring node that is entirely unpopulated, as a result of the large local effects acting upon it.

1 So far, we have only experimented with B-LEGs because undi­ rected local-effect graphs are easier to specify and generate, and be­ cause we consider them to be among the most natural LEGs. We expect to experiment with other classes of LEGs in our future work.

Figure 6: Steps to conver- Figure 7: Steps to conver­ gence for the five graphs gence for the arbitrary graph

The amount of time it took to reach convergence in each graph is shown in Fig. 4, starting in each case with a uni­ form distribution of agents across the actions. Finally, since the 'arbitrary' graph in Fig. 2 took the longest to converge (34% of the agents moved before convergence occurred) we examine this graph in more detail in Fig. 4. Observe that as we vary the number of agents, the number of steps required for convergence increases roughly linearly.

5 Conclusion

Local-effect games exploit context-specific independence be­ tween players' payoff functions. Finding a potential function is a good technique for finding equilibria; we identify all the local-effect games for which potential functions ex­ ist, and provide the potential function in each case. We also give a positive theoretical result for a broad class of games that do not have potential functions. Furthermore, we can show that myopic best response dynamics converge quickly in other cases which do not have potential functions, and are also not covered by our positive theoretical results.