Social Dilemmas in Computational Ecosystems

1. Introduction

Effective use of distributed computation is challenging since the individual processes or agents must obtain resources in a dynamically changing environment and collaborate despite a variety of asynchronous and unpredictable changes. Be­ cause centralized control is often unable to respond rapidly to local changes in these systems, the agents are often de­ signed to act autonomously using locally available infor­ mation. Such decentralized systems are often more robust and simpler to design and incrementally modify than those using a central controller. On the other hand, these agents face the difficult task of performing well in spite of in­ complete, imperfect and changing information. Because these characleristics are shared with biological ecosystems and human societies, we refer to these systems as com­ putational ecosystems [Hogg, 1994; Huberman and Hogg, 1988; Gasser and Huhns, 1989; Miller and Drexler, 1988; Waldspurger et al., 1992; Wellman, 1993; White, 1994].

This analogy between computational and human societies offers suggestions for the appropriate design of agents as well as new potential problems not seen with centralized control or with a small number of agents. In this paper we show that one such problem, namely the social dilemma involved in maintaining cooperation among a large group the system (e.g., in distributed problem solving) one might hope to avoid social dilemmas entirely by explicitly pro­ gramming desired cooperative behaviors into the agents. Recently, however, it has been recognized that such dilem­ mas can occur in contexts such as coevolutionary genetic algorithms with a single overall goal [Glance and Hogg, 1995]. This is an example of the general mathematical fact that locally optimal actions can result in suboptimal global performance. At the same time, determining the globally superior choice by central fiat may be computationally in­ tractable. In some cases, the optimal state may actually be provably impossible to find within a distributed setting since individual choices will take the system away from the optimum instead of towards it This is the computational analogue of a social dilemma. In this case the dilemma is due to information limits rather than incentive prob­ lems, but has the same detrimental effect Social dilemmas stand in contrast to other causes of difficulty in computa­ tional problems. For instance, hilly landscapes cause meth­ ods such as neural nets [Rumelhart et al., 1986], simulated annealing [Kirkpatrick et al., 1983] and greedy heuristics for NP-hard search problems [Garey and Johnson, 1979] to become trapped in local minima, making the overall mini­ mum hard, but not impossible, to find. Despite these obser­ vations, one might hope computational social dilemmas are exceptional and so rarely seen in practice. The major new finding of this paper, given in Section 4, is that these dilem­ mas are indeed readily found in computational ecosystems.

3. Dynamics of Computational Ecosystems

Computational ecosystems consist of agents, with compu­ tational tasks to perform, and various resources with which to accomplish their tasks. These resources can include both hardware and software (e.g., information from sen­ sors, databases and the use of specialized algorithms). A simple model of these societies supposes each agent uses one resource at a time, evaluates its choice at a rate a and selects that resource it perceives to be best based on locally available information. The suitability of a resource can de­ pend on how many other agents are using it, leading to a range of dynamical behaviors including simple equilibria. continual oscillations and chaos [Kephart et al., 1989].

Specifically, the state of a system with r resources at a given time can be characterized by the fraction of agents /; using resource i with

Let c; be an agent's cost of using the resource, which can depend on the state of the system. The overall average cost per agent is then given by Cglobal = L: /;c;. This provides one simple measure of global performance for the system and is appropriate for situations in which the agents are each contributing to the result More complex global measures can arise in other situations such as cooperative problem solving in which a single solution is required and so the global performance is determined by the time for the first agent to finish [Clearwater et al., 1991].

The dynamical behavior, on average, is given by [Huberman and Hogg, 1988]

where p; is the probability that resource i will be perceived to be the best one, i.e., have lowest cost, when an agent makes a choice. Note that L: p; = 1 and that the Pi depend on the /i because the resource costs do. The two terms on the right side of Eq. 2 are readily understood as I) a decrease in use of resource i due to agents ali'eady using it making choices at a rate a, and 2) an increase in the use of resource i due to agents perceiving it to be the best one when they make their choices.

The simplest case is when the agents have full informa­ tion on their individual costs and there are no delays in the information. In that case they will always select that re­ source with the lowest actual cost giving Pi = 1 when Ci is the lowest cost, and zero otherwise. Uncertainty and de­ lays in the information give well-studied mechanisms that degrade performance [Kephart et al., 1989]. Here we fo­ cus instead on the perfect information case to highlight the suboptimal behavior due explicitly to the social dilemmas.

4. How Dilemmas Arise

Having introduced the possibility of social dilemmas and the dynamical model for computational ecosystems, we now turn to the question of how often these dilemmas can be expected to occur. Although ideally approached empirically once many such systems become available for study, we can gain considerable insight from examining the kinds of resource costs that will give rise to a social dilemma. Specifically, this will happen when the local dynamics does not lead to the globally optimal state even when the agents have perfect local information. In such cases, the performance of the group as a whole would benefit if some agents "cooperated" by maldng different resource choices even though they would incur higher costs.

4.1 Theory for Linear Costs

Consider the situation with r resources and with costs de­ pending linearly on their utilization:

with the vectors c and r having components c; and /; giving the cost and utilization of the resources. The matrix M specifies how the costs depend on the utilization, and the vector v is a usage-independent contribution to the costs. Note that because ofEq. 1, the choices forM and v are not unique, e.g., this relation can be used to eliminate f,. from the costs so the last column of M will be zero. Furtherm<Xe, because agents make choices based on the minimum cost option (when they have perfect information), the results presented here will not be affected by rescaling the unit of cost, i.e., multiplying each component of M and v by a constant, or by shifting the origin of the costs, i.e., adding a constant to each component of v.

The global average cost is given by

From this we see that the linear cost example considered here is particularly useful for investigating social dilemmas: except in degenerate special cases, Cglobal has only one minimum and so avoids the complication of local minima. The resource usage that minimizes this cost is found by minimizing Cglobal - .X(L: /; - 1 ), where the Lagrange multiplier .X is used to enforce Eq. 1. Setting all partial derivatives to zero gives the extremum as the solution to

with

where 1 represents the vector all of whose components equal I. There are two degenerate cases in which this extremum will not in fact be the global minimum cost. First, while this is the only point where the partial derivatives vanish, it could be a maximum or saddle point instead of a minimum. Second, the extremum may not have each/; ~ 0. In either case, the true minimum cost will be found at the boundary of the allowed set of values, i.e., at least one resource is not used at all. In effect, such systems can be viewed as having fewer resources.

By contrast, the equilibrium found by local choices will be where all resources have the same cost so agents will remain where they are, on average. That is c = J-'1 where 1-' is a constant, which gives C 9 1obal = 1-'· This can be combined with Eq. 1 to obtain

whose solution gives the equilibrium state found by local choices, again provided /; ~ 0 (otherwise, some resources, with relatively high costs, will not be used in equilibrium).

4.2 The Existence of Social Dilemmas

Th see that social dilemmas can be expected quite frequently in computational ecosystems, consider a typical situation in which the cost to use a resource increases with its use, with some fixed overhead, but is not directly dependent on the

with use of other resources. That is c; = /;I a; + v; with a; > 0 so that M is a diagonal matrix with m;; = 1 I a;. The global minimum, from Eq. 5, is at f;/a; = s + ~(v- v;), with costs c; = s + ~(v + v;). In these expressions we defined s = 11 I: a~: and v = s I: a~:v~: as a weighted average of the components of v. This gives

By contrast, the local equilibrium from Eq. 7 is f;/a; = s + v - v;, with cost c; = s + v, which is also the value of Cglobal at this equilibrium In both cases, a negative resulting value for /; indicates resource i isn't used and the calculation should be repeated without it to find the correct resource use.

We thus see that the local equilibrium is globally optimal only if all v; are the same, as was the case in a limited previous study of the 3-resource case [Kephart et al., 1989]. Otherwise, the local equilibrium point will have wider range of resource use than is optimal. Thus we see that generally, even with resources whose costs depend only on their own load, the public goods social dilemma arises.

A simple example, with two resources, is shown in Fig. 1 with the dynamics given by Eq. 2, M = G ~) and

local equilibrium is at the suboptimal value It = ! . Even though, in this case, the system passes through the optimal state during its evolution, more agents continue selecting to use resource 2. This results in the final state having a higher cost, as shown in the figure.

The basic cause of the problem is agents choose based only on their own costs, not on how their actions affect others. For example, if there are 1000 agents at the global minimum (i.e., 375 agents using resource 1), then the costs are c1 = 1 i, c2 = ~ and agents using resource 1 are tempted to switch. Suppose one agent moves from resource 1 to 2, reducing its own cost by about 0.25. This move also affects the remaining agents: the cost of resource 1 drops slightly, thereby benefiting the 37 4 agents that remain there, but the cost of resource 2 increases slightly, harming the 625 already there. The net result in this case is that the increased cost to the agents already using resource 2 outweighs the benefit both to the agent that moved and those remaining on resource 1: the global cost increases slightly.

4.3 Generalizations

In the general case with nondiagonal matrix M, we can see that dilemmas will also often arise as follows. In order that Eqs. 5 and 7 give the same value for f, we must have

which is a linear equation for v. In general, most vectors v will not satisfy this equation, and hence the global minimum and the local equilibrium will be at different points. Thus on very general grounds we can expect the results seen explicitly above for simple diagonal matrices to apply to a wide range of linear cost functions.

An example is where resource 1 uses a communication channel controlled by resource 2, so agents using resource 1 incur higher cost when resource 2 is busy with its own tasks and unable to service the requests. Such an instance is

which has global minimum at f = (1/2, 1/2) with cost 3/4, but local equilibrium at f = (0, 1) with cost 1. To avoid the dilemma, Eq. 10 requires that v1 = v2 - 1.

Finally, for the more realistic case of nonlinear cost func­ tions, the analysis cannot give a complete characterization of the dynamics (e.g., there may be local minima}, but can provide some insight. The dilemma will exist (in addi­ tion to any problems due to local minima) when the local dynamics drives the system away from the global mini­ mum, even if it is initially quite close. Whether this is the case can be determined by expanding Eq. 2 around the global minimum, giving a linearized system to which the above analysis applies. Because we saw that dilemmas exist quite commonly with linearized costs, this argument shows they will correspondingly exist for many nonlinear prob­ lems. How important the dilemmas will be in such cases will depend on how easily the system is stuck in local min­ ima That is, if there are many local minima, they can be expected to prevent the system from getting near the global minimum at all and hence the existence of a dilemma that prevents convergence to the global minimum will rarely af­ fect the dynamics. On the other hand, systems with fewer local minima, or that have techniques to avoid or overcome them, would be limited instead by a social dilemma This suggests that an interesting question for future work is to determine the interplay between these effects, and whether strategies that alleviate one problem increase the other.

5. Braess' Paradox

A particularly subtle version of the dilemma is given by Braess' Paradox [Cohen and Horowitz, 1991; Irvine, 1993] in which adding resources to a system can actually lower performance. While usually presented in the context of traffic or electric current flow, it has a natural interpre­ tation as selection among resources. A specific example, which corresponds to that considered for traffic and genetic algorithms [Glance and Hogg, 1995] is given by the three resource case with the costs

When only the first two resources are available, P1 = 1 when c1 < c2 , corresponding to 11 < h. and similarly P2 = 1 when 11 > h. Thus, starting from an initial condition of all agents using resource 1, i.e., It (0) = 1, Eq. 2 gives 11(t) =e-at and h(t) = 1-11(t) until these values reach 1/2, at which point they remain at that value.

When the third resource is added, each agent finds the new resource has a lower cost and selects it, i.e., P3 = 1. Thus 11 and h decay exponentially toward zero increasing the overall cost, as illustrated in Fig. 2.

In our previous notation, this case corresponds to

Eq. 5 gives the global minimum at 11 = h = 1/2, fa = 0 with a cost of Cglobal = 5/2, while Eq. 7 gives the local equilibrium at 11 = h = 0, fa = 1 with cost Cglobal = 3.

More generally, when a social dilemma exists, the lo­ cal equilibrium has a higher cost than the global minimum. Hence some additional constraints on the resource use, e.g., eliminating any use of the third resource in the example of Eq. 13, can in fact change the local equilibrium to be closer to, or even reach, the global minimum. Thus social dilem­ mas will always be associated with a seemingly paradoxical situation in which additional restrictions can result in lower costs. This contrasts with the usual intuition that eliminat­ ing some available choices in a minimization problem gives a cost at least as large as that for the unrestricted problem. Braess' paradox is particularly surprising in the form given here where an additional constraint of simply eliminating one of the resources is sufficient to lower the cost.

6. Addressing Social Dilemmas

Having seen that social dilemmas can arise for a variety of resource costs, a natural question is how their effect can be alleviated while still retaining the autonomous local decision-making of the computational ecosystem.

A dynamical approach relies on using uncertainty in the agents' evaluation of the costs, which tends to move the system toward equal use of the available resources [Kephart et al., 1989]. When the dilemma gives an equilibrium with more variation in resource use than is optimal the addition of some uncertainty (either deliberately added to the agents or from external causes) can help to improve the performance. This benefit of uncertainty is in addition to its previously recognized use to improve the stability of computational ecosystems. Specifically, uncertainty is modeled by adding a normally distributed random variable with zero mean and standard deviation u to the costs as evaluated by each agent. For the case of two resources, this changes the probability that an agent will choose resource 1, used in Eq. 2, to be p1 = ! ( 1 + erf( ca2"ac' ) ) where erf( x) denotes the error function. When u is small agents usually choose the resource with the lower cost, but for large u each is chosen with nearly equal probability. An example of the improvement this can give is shown in Fig. 3.

A second approach to public goods dilemmas, commonly used in human societies, is to introduce mechanisms that enforce contribution, such as taxation. This can be used to artificially change the relative costs perceived by the agents when making choices. An example, shown in Fig. 3, is to add an extra cost x to the overused resource.

While they can be effective, these methods require find­ ing the correct value for the adjustment which can be hard to determine, especially in a complex, changing situation. Hence one would like to rely on the agents themselves to make the necessary adjustments. One such method is suggested by a different approach to the dilemma in hu­ man societies: create new markets that, at least partially, restrict benefits to those that contribute. This amounts to privatizing the public good using computational pric­ ing and accounting mechanisms [Miller and Drexlez, 1988] within computational economies [Waldspurgez et al., 1992]. The resulting prices also provide information on competing uses for resources in a manner similar to that in market economies [Hayek, 1978]. For example, in Fig. 1 agents could be required to pay for the use of resource 2 thus encouraging more of them to use resource 1 instead.

Finally, coopezation can be maintained if the bene­ fits are concentrated in small groups with long-range plans [Glance and Hubennan, 1994] or if interactions are repeated [Axelrod and Hamilton, 1981; Bendor and Mookherjee, 1987]. There are also a variety of mecha­ nisms to evolve cooperation in such cases [Simon, 1990]. These observations can suggest additional mechanisms for computational ecosystems as well.

7. Conclusion

We have seen that social dilemmas readily arise in compu­ tational ecosystems even when all the agents are designed with a single overall goal. This is a new mechanism that lowers performance, in addition to the previously recog­ nized oscillations and chaotic behavior caused by dynami­ cal instabilities [Kephart et al., 1989]. Since the existence of a dilemma will not always be readily apparent from the cost functions, especially in cases that include nonlineari­ ties, it may be easy to confuse the lowered performance due to a social dilemma with that due to uncertainty or delays in the available information. Such confusion could lead to inappropriate attempts to address the problem.

In dynamic environments with changing resource avail­ ability (e.g., a new machine added to a network) or cost functions (e.g., due to a better implementation of a data­ base search) the system could have public goods problems at some times but not others. This is another reason to in­ vestigate analogies with human social institutions such as markets that allow local decisions by many agents to re­ spond to these problems in a timely way.

Finally, social dilemmas can also occur in coevolutionary genetic algorithms and cooperative problem solving where the usefulness of particular methods depends on choices of other agents [Glance and Hogg, 1995]. The results presented here, showing that many cost functions can give rise to dilemmas, suggest they may be common in these situations as well despite their very different dynamical behaviors. Thus methods for recognizing and alleviating social dilemmas are likely to prove useful in a variety of multiagent computational contexts.

Acknowledgments

I have benefited from discussions with N. Glance.