- Minority Game is receiving an increasing interest because it models emergent properties of complex systems including rational entities, such as for instance the evolution of financial markets. As such, Minority Game provides for a simple yet stimulating scenario for system simulation. In this paper, we aim at presenting a logic approach to the Minority Game whose goal is to overcome the well-known limits of the equation model in the verification of the system behaviour. We realise the social system simulation using a novel MAS metamodel based on agents and artifacts, where the agent rationality is obtained using a BDI architecture. To this end, we adopt the TuCSoN infrastructure for agent coordination, and its logic-based tuple centre abstractions as artifact representatives. By implementing Minority Game over TuCSoN, we show some of the benefits of the artifact model in terms of flexibility and controllability of the simulation. A number of parameters can affect the behaviour of Minority Game simulation: such parameters are explicitly represented in the coordination artifact, so that they can be tuned up during the simulation. In particular, experiments are shown where memory size and number of wrong moves are adopted as the tuning parameters.
I. INTRODUCTION
Minority Game (MG) is a mathematical model that takes
inspiration from the “El Farol Bar” problem introduced by
Brian Arthur (
As showed by (
The Minority Game is a social simulation that aims at
reproducing a simplified human social scenario. A (human)
society is composed by different kinds of people with different
behaviours, and its composition affects the progress of the
game. In principle, a logic-based approach based on BDI agent
makes it easier to explicitly model a variety of diverse social
behaviours. Also, in this scenario, argumentation theory (
In this paper we proceed along this direction, and adopt a
novel MAS meta-model based on the notion of artifact (
In order to implement MG simulations we adopt the
TuCSoN infrastructure for agent coordination (
By implementing MG over TuCSoN, we can experiment with flexibility and controllability of the artifact model, and see if and how they apply to the simulation – in particular, artifacts allow for a greater level of controllability with respect to agents. To this end, in this paper we show how the model allows some coordination parameters to be changed during the run of a simulation with no need to stop the agents: this can be useful e.g. to change the point of equilibrium, controlling the collective behaviour resulting by interactions propagated from the entities at the micro level.
The remainder of this paper is organised as follows. First, we introduce the general simulation framework based on agents and artifacts. Then, we provide the reader with some relevant details of the Minority Game. Some quantitative results of MG simulation focussing on system dynamics and run-time changes are presented, just before final remarks. Player
Monitor
Tuning
Figure 1): all the agents share the same coordination artifact. The agent types differ because of their role and behaviour: player agents play MG, the monitor agent is an observer of interactions which visualises the progress of the system, the tuning agent can change some rules or parameters of coordination, and drives the simulation to new states. Note that the main advantage of allowing a dynamic tuning of parameters instead of running different simulations lays in the possibility of tackling emergent aspects which would not necessarily appear in new runs.
The main control loop of a player agent is a sequence of actions: observing the world (perception), updating its KB (effects), scheduling next intention (precondition), elaborating and executing a plan (action). This structure is depicted in Figure 2. Moreover, in order to connect agent mental states with interactions, we use the concept of action preconditions and perception effects as usual.
Fig. 1. TuCSoN Simulation Framework for MG
The architecture proposed for MAS simulation is based on
TuCSoN (
In our simulation framework we adopt logic-based agents, N namely, agents built using a logic programming style, keeping A(t) = X ai(t) a knowledge base (KB) of facts and acting according to i some rule—rules and facts thus forming a logic theory. The In order to take decisions agents adopt strategies. A strategy implementation is based on tuProlog technology1 for Java- is a choosing device that takes as input the last m winning Prolog integration, and relies on its inference capabilitieAsgfoernt mreesnutlatsl,satandteprovides the action (1 or −1) to perform in the agent rationality. Agents roughly follow the BDI architecture next time step. The parameter m is the size of the memory (as showed in Figure 2), as the KB models agent beliefs while of the past results (in bits), and 2m is therEeffofreecthse potential rules model agent intentions. past history that defines the number of possible entries for a
To coordinate agents we take inspiration from natural sys- strategy. tems like ant-colonies, where coordination is achieved through The typical strategy implementation is as follows. Each the mediation of the environment: our objective is to have a agent carries a sequence of 2m actions, called a strategy, e.g. possibly large and dynamic set of agents which coordinate each other through the environment while bringing about their goals.
Externally, we can observe overall system parameters by Effects inspecting the environment, namely, the tuple centres agents Beliefs interact with. In this way we can try different sPysretecmonbdeit-ions haviours changing only the coordination behaviour of the environment. Furthermore we can change, during the simulation, InDteenstirioenss some coordination parameters (expressed as tuples in a tuple Preconditions centre), programming and then observing the transition of the whole system either to a new point of equilibrium or to a Action Perception divergence.
Three kinds of agents are used in our simulation: player agents, monitor agents and tuning agents (as depicted in
Fig. 2. Agent Architecture m = 3 23actions = [+1, +1, −1, −1, +1, −1, +1, +1]. The information on past m wins is stored considering the success of − group if A(t) > 0 or + group if A(t) < 0. Such a past history is mapped on the natural number that results by considering − as 0 and + as 1. Such a number is used as position in the sequence of the next action to take: for instance, if [−, +, −] is the past winning group, we read it as 010 (that is, 2), and accordingly pick the decision in position 2 inside [+1, +1, −1, −1, +1, −1, +1, +1], that is −1.
Each agent actually carries a number s ≥ 2 of strategies.
During the game the agent evaluates all its strategies according to their success, and hence at each step it decides based on the most successfull strategy so far. Figure 3 shows a typical evolution of the game.
One of the most important applications of MG is in the
market models: (
Another point of view, presented e.g. by (
In this work a generalisation of MG is presented that relaxes the constraints on the number of resources, studying how the system behaves within a given range.
MG can be considered a social simulation that aims to reproduce a simplified human scenario. Each (human) agent, in this scenario, must do a choice under the minority global rule. In order to study the system composed by different kinds of players with different behaviours, we here adopt a logic-based approach to build the players. In this way, it is possible to observe particular social behaviours which would otherwise remain hidden in the approximation of the mathematical model.
A more recent paper (
The next step is to consider players as in an
argumentation scenario (
In order to track the performance of an MG system, the most interesting quantity is variance, defined as σ2 = [A(t) − A(t)]2: it shows the variability of the bets around the average value A(t). In particular, the normalised version of variance ρ = σ2/N is considered.
Generally speaking, variance is the inverse of global efficiency: as variance decreases agent coordination improves, making more agents winning. Variance is interestingly affected by the parameters of the model, such as number of agents (N ), memory (m) and number of strategies (s): in particular, the fluctuation of variance is shown to depend only on the ratio α = 2m/N between agent memory and the number N of agents.
For large values of α—the number of agents is small with respect to the number of possible histories—the outcomes are seemingly random: the reason for this is that the information that agents observe about the past history is too complex for their limited processing analysis.
When new agents are added, fluctuation decreases and agents perform better by choosing randomly, in this case ρ = 1 and α ≈ 1/2, as visible in the results of our simulation in Figure 4—the game enters into a regime where the loosing group is close to N/2, hence we might say coordination is performing well.
If the number of agents increase further, fluctuations rapidly increase beyond the level of random agents and the game enters into the crowded regime. With a low value of α the value of σ2/N is very large: it scales like σ2/N ≈ α−1.
The results of other observations suggest that the behaviour of MG can be classified in two phases: an information-rich asymmetric phase, and an unpredictable or symmetric phase.
A phase transition is located where σ2/N attains its minimum (αc = 1/2), and it separates the symmetric phase with α < αc from an asymmetric phase with α > αc.
All these cases have been observed with the TuCSoN simulation framework described in next section.
IV. THE SIMULATION FRAMEWORK operation set_spec(). The following ReSpecT reaction The construction of MG simulations with MASs is based is fired when an agent inserts tuple play(X), and triggers on the TuCSoN framework and on tuProlog as an inferential the whole behaviour: engine to program logic agents. The main innovative aspect of this MG simulation is the possibility of studying the evolution of the system with particular and different kinds of agent behaviour at the micro level, imposed as coordination parameters which are changed on-the-fly. reaction(out(play(X)),( %read the last value of count in_r(count(Y)), Z is Y+1, %calculate the partial result in_r(sum(M)), V is M+X, out_r(sum(V)), %store the new value of count out_r(count(Z)) %this action will be catch )).
Each agent has an internal plan, structured as an algebraic
composition of allowed actions (with their preconditions) and
perceptions (with their effects), that enables the agent to use
the coordination artifact to play the MG. This plan can be
seen as Operating Instructions (
Operating instructions are expressed by the following theory: % pre=Preconditions % eff=Effects % act=Action % per=Perception firststate(agent(first,[])). definitions([ def(first,[],...), %definition of the main control loop def(main,[S], [act(out(play(X)),pre(choice(S,X))), per(in(result(Y)),eff(res(Y))), agent(main,[S])] ), ... ]).
The first part of operating instructions is expressed by term first, where the agent reads the game parameters that are stored in the KB, and randomly creates its own set of strategies.
In the successive part main, the agent executes its main cycle. It first puts tuple play(X) in the tuple space, where X = ±1 is agent vote. The precondition of this action choice(S,X) is used to bind in the KB X with the value currently chosen by the agent according to strategy S. Then, the agent gets the whole result of the game in tuple result(Y) and applies it to its KB. After this perception, the cycle is iterated again.
The interaction protocol between agents and the coordination artifact is then simply structured as follows. First each agent puts the tuple for its vote. When the tuples for all agents have been received, the tuple centre checks them, computes the result of the game—either 1 or −1 is winning—and prepares a result tuple to be read by agents.
The ReSpecT program for this behaviour is loaded in the tuple centre by a configuration agent at bootstrap, through
This reaction considers the bet (X), counts the bets (Z), and computes the partial result of the game (V). When all the agents have played, the artifact produces the tuple winner(Result,Turn,NumberOfLoss,MemorySize,last/more) which is the main tuple of MG coordination. reaction(out_r(count(X)),( %check if all agents have already played rd_r(numag(Num)), X=:=Num, in_r(totcount(T)), Turn is T+1, rd_r(game(G)), %read the result of the game in_r(sum(Result)), %reset the sum value out_r(sum(0)), rd_r(countsession(CS)), in_r(count(Y)), %reset the count value out_r(count(0)), %calculate variance in_r(qsum(SQ)), NSQ is Result*Result+SQ, out_r(qsum(NSQ)), %calculate mean in_r(totsum(R)), NewS is R+Result, out_r(totsum(NewS)), rd_r(numloss(NumberOfLoss)), rd_r(mem(MemorySize)), % put out the tuple with the result out_r(winner(Result,Turn,NumberOfLoss, MemorySize,G)), out_r(totcount(Turn)) )).
Fig. 5. Interface of the Monitor Agent
The winner tuple contains the result of the game (Result), the number of steps (Turn), two tuning parameters (NumberOfLoss and MemorySize) and one constant to communicate agents whether they have to stop or to play further (last/more). Figure 5 reports the graphical interface of the monitor agent that during its lifet-ime reads the tuple winner and draws variance.
In classical MG simulation there are a number of parameters that can affect the system behaviour, which are explicitly represented in the tuple centre in form of tuples: the number of agents numag(X), memory size mem(X), and the number of strategies numstr(X). In our framework, we have introduced as a further parameter the number of wrong moves after which the single agent should be recalculate own strategy, represented as a tuple numloss(X). Such a threshold is seemingly useful to break the symmetry in the strategy space when the system is in a pathological state, i.e., when all agents have the same behaviour and the game oscillates from minimum to maximum value.
In our framework, it is possible to explore the possibility to dynamically tune up the coordination rules by changing numloss and mem coordination parameters, which are stored as tuples in the coordination artifact. The simulation architecture built in this way, in fact, allows for on-the-fly change of some game configuration parameters—such as the dimension of agent memory—with no need to stop the simulation and re-program the agents.
By changing the parameters, the tuning agent can drive the system from an equilibrium state to another, by controlling agent strategies, the dimension of memory, or the number of losses that an agent can accept before discarding a strategy. This agent observes system variance, and decides whether and how to change tuning parameters: reference variance is calculated by first making agents playing the game randomly— see Figure 4. The new value of parameters is stored in tuple centre through tuples numloss(NumberOfLoss) and mem(MemorySize), the rules of coordination react and update the information that will be read by the agents.
The result of the tuned simulation in Figures 6 and 7 shows how the system changes its equilibrium state and achieves a better value of variance.2 In this simulation the tuning agent is played by a human that observes the evolution of the system and acts through the tuning interface to change the coordination parameters, such as threshold of losses and memory, hopefully finding new and better configurations. The introduction of the threshold of losses in the agent behaviour is useful when the game is played by few agents: these parameters enable system evolution and a better agent cooperative behaviour.
In this paper, we aim at introducing new perspectives on agent-based simulation by adopting a novel MAS meta-model based on agents and artifacts, and by applying it to Minority Game simulation. We implement and study MG over the TuCSoN coordination infrastructure, and show some benefits of the artifact model in terms of flexibility and controllability of the simulation. In particular, in this work we focus on the possibility to build a feedback loop on the rules of coordination driving a system to a new and better equilibrium state. Many related agent simulation tools actually exist: as this paper is a starting point, we plan to perform a systematic comparison of their expressiveness and features. In the future, we are interested in constructing an intelligent and adaptive tuning agent with a BDI architecture, substituting the human agent in driving the evolution over time of the system behaviour.
The first author of this paper, Enrico Oliva, would like to warmly thank Dr. Peter McBurney and the Department of Computer Science at University of Liverpool for their scientific support and their hospitality during his stay in Liverpool, when this paper was mostly written.
2In Figure 6, the first phase of equilibrium is followed by a second one obtained by changing the threshold parameter S = 5. Finally, a third phase is obtained changing the dimension of the memory to m = 5.