The Evolution of Artificial Social Systems

1 Introduction

The basic idea of the artificial social systems approach of Shoham and Tennenholtz [1995; 1997] is to add a mechanism, called a social law, that will minimize the need for both centralized control and on-line resolution of conflicts. A social law is defined as a set of restrictions on the agents' activities which allow them enough freedom on the one hand, but at the same time constrain them so that they will not interfere with each other. Several variants have been introduced to reason about the design and emergence of social laws. However, existing models of artificial social systems cannot be used for the evolution of such systems, because these models do not contain an explicit representation of the social laws in force. In this paper we use enforceable social laws [Boella and van der Torre, 2005] to address the question how artificial social systems can be extended to reason about the evolution of artificial social systems.

2 Artificial social systems and social laws

Shoham and Tennenholtz [1995] introduce social laws in a setting without utilities. They define also rational social laws [Shoham and Tennenholtz, 1997] as social laws that improve a social game variable. A game or multi-agent encounter is a set of agents with for each agent a set of strategies and a utility function defined on each possible combination of strategies. We extend artificial social systems with a control system, called a normative system, to model enforceable social laws. Following Boella and Lesmo [2002], the normative system is represented by a socially constructed agent called the normative agent or agent 0. In [Boella and van der Torre, 2005], the normative system is represented by the set of control strategies of agent 0, but not by a utility function.

Definition 1 A normative game (or a normative multi-agent encounter) is a tuple a0 ✁ ✄ ✆ ✄ ✟ ✄ ☛ ✄ ✍ ✎ ✄ ✍ ✒ ✔ , where ✁ ✖ ✗ ✘ ✄ ✛ ✄ ✢ ✤ is a set of agents, ✆ , ✟ and ☛ are the sets of strategies available to agents 0, 1 and 2 respectively, and ✍ ✎ ✧ ✆ ✪ ✟ ✪ ☛ ✯ ✱ ✆ and ✍ ✒ ✧ ✆ ✪ ✟ ✪ ☛ ✯ ✱ ✆ are real-valued utility functions for agents 1 and 2, respectively.

We use here as game variable the maximin value, following Tennenholtz [2000]. This represents safety level decisions, see Tennenholtz' paper for a motivation.

Definition 2 Let ✆ , ✟ and ☛ be the sets of strategies available to agent 0, 1 and 2, respectively, and let ✍ ✷

Leendert van der Torre

CWI Amsterdam and Delft University of Technology The Netherlands torre@cwi.nl

be the utility function of agent ✸ . Define ✍ ✎ ✹ ✆ ✄ ✻ ✄ ☛ ✼ ✖ ✾ ✿ ❁ ❃ ❅ ❆ ❈ ❉ ❅ ❋ ✍ ✎ ✹ ● ✄ ✻ ✄ ■ ✼ for ✻ ❏ ✟ , and ✍ ✒ ✹ ✆ ✄ ✟ ✄ ■ ✼ ✖ ✾ ✿ ❁ ❃ ❅ ▼ ❈ ❖ ❅ ▼ ✍ ✒ ✹ ● ✄ ✻ ✄ ■ ✼ for ■ ❏ ☛ . The maximin value for agent 1 (respectively 2) is defined by ✾ ◗ ❙ ❖ ❅ ▼ ✍ ✎ ✹ ✆ ✄ ✻ ✄ ☛ ✼ (respectively ✾ ◗ ❙ ❉ ❅ ❋ ✍ ✒ ✹ ✆ ✄ ✟ ✄ ■ ✼ ). A strategy of agent ✸ leading to the corresponding maximin value is called a maximin strategy for agent ✸ .

A social law is useful with respect to an efficiency parameter ❨ if each agent can choose a strategy that guarantees it a payoff of at least ❨ .

Definition 3 Given a normative game ❩ ✖ a0 ✁ ✄ ✆ ✄ ✟ ✄ ☛ ✄ ✍ ✎ ✄ ✍ ✒ ✔ and an efficiency parameter ❨ , we define a social law to be a restriction of ✟ to ✟ ❫ ✟ , and of ☛ ❫ ☛ . The social law is useful if the following holds: there exists ✻ ❏ ✟ such that ✍ ✎ ✹ ✆ ✄ ✻ ✄ ☛ ✼ ❜ ❨ , and there exists ■ ❏ ☛ such that ✍ ✒ ✹ ✆ ✄ ✟ ✄ ■ ✼ ❜ ❨ .

A social law is quasi-stable if an agent does not profit from violating the law, as long as the other agent conforms to the social law (i.e., selects strategies allowed by the law).

Definition 4 Given a normative game ❩ ✖ a0 ✁ ✄ ✆ ✄ ✟ ✄ ☛ ✄ ✍ ✎ ✄ ✍ ✒ ✔ , and an efficiency parameter ❨ , a quasi-stable social law is a useful social law (with respect to ❨ ) which restricts ✟ to ✟ and ☛ to ☛ , and satisfies the following: there is no ✻ ❞ ❏ ✟ ❢ ✟ which satisfies ✍ ✎ ✹ ✆ ✄ ✻ ❞ ✄ ☛ ✼ ❤ ✾ ◗ ❙ ❖ ❅ ▼ ✍ ✎ ✹ ✆ ✄ ✻ ✄ ☛ ✼ , and there is no ■ ❞ ❏ ☛ ❢ ☛ which satisfies ✍ ✒ ✹ ✆ ✄ ✟ ✄ ■ ❞ ✼ ❤ ✾ ◗ ❙ ❉ ❅ ❋ ✍ ✒ ✹ ✆ ✄ ✟ ✄ ■ ✼ .

When the set of strategies ✆ of agent 0 is a singleton, then our definitions reduce to those of Tennenholtz [2000]. With the extension of agent 0 representing the control system we define enforceable social laws as quasi-stable social laws in normative games where the strategies of agent 0 may have been restricted [Boella and van der Torre, 2005].

Definition 5 Given a normative game ❩ ✖ a0 ✁ ✄ ✆ ✄ ✟ ✄ ☛ ✄ ✍ ✎ ✄ ✍ ✒ ✔ , and an efficiency parameter ❨ , a social law (i.e., a restriction of ✟ to ✟ ❫ ✟ , and of ☛ ❫ ☛ ) is enforceable if there is a restriction of ✆ to ✆ ❫ ✆ such that ✟ ✄ ☛ is quasi-stable in the normative game ❩ ✖ a0 ✁ ✄ ✆ ✄ ✟ ✄ ☛ ✄ ✍ ✎ ✄ ✍ ✒ ✔ .

Computational problems can be defined to find enforceable social laws (with respect to an efficiency parameter).

3 Representing social laws

We extend normative games with a utility function of agent 0, to represent the norms which are enforced. Since agent 0 is a socially constructed agent, in the sense of Searle [1995], its utility function can be updated. In particular, the enforcement of a social law by ✆ ❫ ✆ is represented by giving ✆ strategies a high utility, and ✆ ❢ ✆ strategies a low utility. Moreover, we go beyond the framework of enforceable social laws by varying the utility of agent 0 depending on the strategies played by the other agents, and by considering incremental updates of the utility function to represent the evolution of artificial social systems. Formally, we extend a normative game with a utility function ✍ ✁ ✧ ✆ ✪ ✟ ✪ ☛ ✂ ✱ ✆ , we define ✍ ✁ ✹ ● ✄ ✟ ✄ ☛ ✼ ✖ ✾ ✿ ❁ ❖ ❅ ▼ ❈ ❉ ❅ ❋ ✍ ✁ ✹ ● ✄ ✻ ✄ ■ ✼ for ● ❏ ✆ , and we define useful and quasi-stable social laws in the obvious way. Enforced social laws are defined as follows.

Definition 6 Given a normative game ❩ ✖ a0 ✁ ✄ ✆ ✄ ✟ ✄ ☛ ✄ ✍ ✎ ✄ ✍ ✒ ✔ , and an efficiency parameter ❨ , a social law (i.e., a restriction of ✟ to ✟ ❫ ✟ , and of ☛ ❫ ☛ ) is enforced if there is a unique restriction of ✆ to ✆ ❫ ✆ such that ✆ ✄ ✟ ✄ ☛ is quasi-stable.

3.1 Identification of enforced social laws

The game in Table 1 illustrates that the computational problem to find quasi-stable laws corresponds in extended normative games to the identification of enforced social laws. The table should be read as follows. Strategies are represented by literals, i.e., atomic propositions or their negations. Each table represents the sub-game given a strategy of agent ✘ , represented by ☎ ✆ and ✆ , respectively. Agent 1 is playing columns and agent 2 is playing rows. The values in the tables represent the utilities of agent 0 (in italics), 1 and 2.

Table 1: What is the enforced social law?

Agent 0 (the normative system) can play strategy ☎ ✆ or ✆ , agent 1 can play strategy ✟ or ☎ ✟ , agent 2 can play strategy ❨ or ☎ ❨ . When the normative systemplays ☎ ✆ , the sub-game of agent 1 and 2 is a classical prisoner's dilemma. Intuitively, the strategy ☎ ✆ corresponds to the state before the social law is introduced, and ✆ corresponds to the introduction of a control system that sanctions an agent for deviating from ✟ ✄ ❨ . For example, the utility of agent 1 in ☎ ✟ ✄ ❨ ✄ ✆ (2) is lower than its utility in ☎ ✟ ✄ ❨ ✄ ☎ ✆ (4) due to this sanction.

When the normative system plays ✆ , the agents are always worse off compared to the normative agent playing ☎ ✆ , all else being equal. Nevertheless, due to the dynamics of the game, the overall outcome is better for both agents. For example, in the sub-game defined by strategy ☎ ✆ , the only Nash equilibrium is ✢ ✄ ✢ . Now suppose we set the efficiency parameter to ✡ , which means that all agents will be better off. If the normative system plays ✆ , then the sub-game has a Nash equilibrium which is the (Pareto optimal) ✡ ✄ ✡ . This explains why the agents accept the possibility to be sanctioned.

3.2 Iterated design of enforced social laws

The social law design problem is, given a normative game, to define a new utility function for the normative system. The principle that we like to maintain as much as possible from the existing social laws can be represented by the use of the principle of minimal change. Table 2 represents the evolution of an artificial social system by an incremental increase of the utility of agent 0 to the efficiency parameter of the new social law.

The first table represents that the normative system does not impose a control system, the second table represents that there is a sanction for playing ☎ ✟ ✎ ✄ ☎ ✟ ✒ or ☎ ❨ ✎ ✄ ☎ ❨ ✒ , and the third table represents that there is an additional sanction for playing something else than ✟ ✎ and ❨ ✎ . The first social law is ✟ ✖ ✗ ✟ ✎ ✄ ✟ ✒ ✤ ✄ ☛ ✖ ✗ ❨ ✎ ✄ ❨ ✒ ✤ based on control system ✆ ✖ ✗ ✆ ✎ ✄ ✆ ✒ ✤ , and the second social law is ✟ ✖ ✗ ✟ ✎ ✤ ✄ ☛ ✖ ✗ ❨ ✎ ✤ based on control system ✆ ✖ ✗ ✆ ✒ ✤ .