=Paper=
{{Paper
|id=Vol-204/paper-28
|storemode=property
|title=Minority Game: A Logic-Based Approach in TuCSoN
|pdfUrl=https://ceur-ws.org/Vol-204/P02.pdf
|volume=Vol-204
|dblpUrl=https://dblp.org/rec/conf/woa/OlivaVO06a
}}
==Minority Game: A Logic-Based Approach in TuCSoN==
https://ceur-ws.org/Vol-204/P02.pdf
Minority Game:
A Logic-Based Approach in TuCSoN
Enrico Oliva Mirko Viroli Andrea Omicini
A LMA M ATER S TUDIORUM—Università di Bologna
via Venezia 52, 47023 Cesena, Italy
E-mail:{enrico.oliva,mirko.viroli,andrea.omicini}@unibo.it
Abstract— Minority Game is receiving an increasing interest society is composed by different kinds of people with different
because it models emergent properties of complex systems in- behaviours, and its composition affects the progress of the
cluding rational entities, such as for instance the evolution of game. In principle, a logic-based approach based on BDI agent
financial markets. As such, Minority Game provides for a simple
yet stimulating scenario for system simulation. makes it easier to explicitly model a variety of diverse social
In this paper, we aim at presenting a logic approach to the behaviours. Also, in this scenario, argumentation theory (3) is
Minority Game whose goal is to overcome the well-known limits useful to model the information exchange and sharing between
of the equation model in the verification of the system behaviour. humans/agents so as to improve the agent reasoning abilities,
We realise the social system simulation using a novel MAS meta- as well as to provide a more realistic simulation of a society.
model based on agents and artifacts, where the agent rationality
is obtained using a BDI architecture. In this paper we proceed along this direction, and adopt a
To this end, we adopt the TuCSoN infrastructure for agent novel MAS meta-model based on the notion of artifact (4).
coordination, and its logic-based tuple centre abstractions as The notion of artifact is inspired by Activity Theory (5): it
artifact representatives. By implementing Minority Game over
TuCSoN, we show some of the benefits of the artifact model in represents those abstractions living in the MAS environment
terms of flexibility and controllability of the simulation. that provide a function, which agents can exploit to achieve in-
A number of parameters can affect the behaviour of Minority dividual and social goals. The engineering principles promoted
Game simulation: such parameters are explicitly represented in by this meta-model makes it possible to flexibly balance the
the coordination artifact, so that they can be tuned up during the computational burden of the whole system between autonomy
simulation. In particular, experiments are shown where memory
size and number of wrong moves are adopted as the tuning of the agents and the designed behaviour of artifacts.
parameters. In order to implement MG simulations we adopt the
I. I NTRODUCTION TuCSoN infrastructure for agent coordination (6), which in-
troduces tuple centres as artifact representatives. A tuple centre
Minority Game (MG) is a mathematical model that takes
is a programmable coordination medium living in the MAS
inspiration from the “El Farol Bar” problem introduced by
environment, used by agents interacting by exchanging tuples
Brian Arthur (1). It is based on a simple scenario where at each
(logic tuples in the case of TuCSoN logic tuple centres). As
step a set of agents perform a boolean vote which conceptually
we are not concerned much with the mere issues of agent
splits them in two classes: the agents in the smaller class win.
intelligence, we rely here on a weak form of rationality,
In this game, a rational agent keeps track of previous votes
through logic-based agents adopting pre-compiled plans called
and victories, and has the goal of winning throughout the steps
operating instructions (7).
of the game—for which a rational strategy has to be figured
out. Several researches showed that, although very simple, this By implementing MG over TuCSoN, we can experiment
model takes into account crucial aspects of some interesting with flexibility and controllability of the artifact model, and
complex systems coupling rationality with emergence: e.g. see if and how they apply to the simulation – in particular,
bounded rationality, heterogeneity, competition for limited re- artifacts allow for a greater level of controllability with respect
sources, and so on. For instance, MG is a good model to study to agents. To this end, in this paper we show how the model
market fluctuation, as an emergent property resulting from allows some coordination parameters to be changed during the
interactions propagating from micro scale (agent interaction) run of a simulation with no need to stop the agents: this can
to macro scale (collective behaviour). be useful e.g. to change the point of equilibrium, controlling
As showed by (2), a multiagent system (MAS) can be used the collective behaviour resulting by interactions propagated
to realise a MG simulation—there, BDI agents provide for from the entities at the micro level.
rationality and planning. An agent-based simulation is partic- The remainder of this paper is organised as follows. First,
ularly useful when the simulated systems include autonomous we introduce the general simulation framework based on
entities that are diverse, thus making it difficult to exploit the agents and artifacts. Then, we provide the reader with some
traditional framework of mathematical equations. relevant details of the Minority Game. Some quantitative
The Minority Game is a social simulation that aims at results of MG simulation focussing on system dynamics and
reproducing a simplified human social scenario. A (human) run-time changes are presented, just before final remarks.
181
Agent
Figure 1): all the agents share the same coordination artifact.
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
Tuning
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
Player necessarily appear in new runs.
Monitor
The main control loop of a player agent is a sequence of
actions: observing the world (perception), updating its KB
Fig. 1. TuCSoN Simulation Framework for MG
(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
II. T HE TuCSoN F RAMEWORK FOR S IMULATION with interactions, we use the concept of action preconditions
The architecture proposed for MAS simulation is based on and perception effects as usual.
TuCSoN (6), which is an infrastructure for the coordination of III. M INORITY G AME
MASs. TuCSoN provides agents with an environment made MG was introduced and first studied by (10), as a means
of logic tuple centres, which are logic-based programmable to evaluate a simple model where agents compete through
tuple spaces. The language used to program the coordination adaptation for finite resources. MG is a mathematical rep-
behaviour of tuple centres is ReSpecT, which specifies how resentation from ‘El Farol Bar’ problem introduced by (1),
a tuple centre has to react to an observable event (e.g. when providing an example of inductive reasoning in scenarios of
a new tuple is inserted) and has to accordingly change the bounded rationality. The game consists in an odd number N of
tuple-set state (8). Tuple centres are a possible incarnation of agents: at each discrete time step t of the game an agent i takes
the coordination artifact notion (9), representing a device that an action a (t), either 1 or −1. Agents taking the minority
i
persists independently of agent life-cycle and provides services action win, whereas the majority looses. After a round, the
to let agents participate to social activities. total action result is calculated as:
In our simulation framework we adopt logic-based agents, N
namely, agents built using a logic programming style, keeping
X
A(t) = 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 capabilitiesAgent
for mental state
results, and provides 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 therefore
Effects
the 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
Beliefs
inspecting the environment, namely, the tuple centres agents
Preconditions
interact with. In this way we can try different system be-
haviours changing only the coordination behaviour of the en-
Desires
vironment. Furthermore we can change, during the simulation, Intentions
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
1 http://tuprolog.alice.unibo.it Fig. 2. Agent Architecture
182
Fig. 3. Typical Time evolution of the Original MG with N = 51, m = 5 Fig. 4. Variance of the Game with 11 Random Agents
and s = 2
to test the MG from a logic-based point of view, and to
m = 3 23 actions = [+1, +1, −1, −1, +1, −1, +1, +1]. The
experiment with some dynamic tuning strategy.
information on past m wins is stored considering the success
The next step is to consider players as in an argumenta-
of − group if A(t) > 0 or + group if A(t) < 0. Such a
tion scenario (3), where agents have the ability to exchange
past history is mapped on the natural number that results by
arguments with the purpose to make their own choice or to
considering − as 0 and + as 1. Such a number is used as
persuade others to change theirs.
position in the sequence of the next action to take: for instance,
if [−, +, −] is the past winning group, we read it as 010 (that B. MG Performance
is, 2), and accordingly pick the decision in position 2 inside
[+1, +1, −1, −1, +1, −1, +1, +1], that is −1. In order to track the performance of an MG system,
Each agent actually carries a number s ≥ 2 of strategies. the most interesting quantity is variance, defined as σ 2 =
During the game the agent evaluates all its strategies according [A(t) − A(t)]2 : it shows the variability of the bets around the
to their success, and hence at each step it decides based on average value A(t). In particular, the normalised version of
the most successfull strategy so far. Figure 3 shows a typical variance ρ = σ 2 /N is considered.
evolution of the game. Generally speaking, variance is the inverse of global ef-
One of the most important applications of MG is in the ficiency: as variance decreases agent coordination improves,
market models: (11) use MG as a coarse-grained model for making more agents winning. Variance is interestingly affected
financial markets to study their fluctuation phenomena and by the parameters of the model, such as number of agents (N ),
statistical properties. Even though the model is coarse-grained memory (m) and number of strategies (s): in particular, the
and provides an over-simplified micro-scale description, it any- fluctuation of variance is shown to depend only on the ratio
way captures the most relevant features of system interaction, α = 2m /N between agent memory and the number N of
and generates collective properties that are quite similar to agents.
those of the real system. For large values of α—the number of agents is small with
Another point of view, presented e.g. by (12), considers the respect to the number of possible histories—the outcomes are
MG as a point in space of a Resource Allocation Game (RAG). seemingly random: the reason for this is that the information
In this work a generalisation of MG is presented that relaxes that agents observe about the past history is too complex for
the constraints on the number of resources, studying how the their limited processing analysis.
system behaves within a given range. 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
A. MG Logic-Based Approach
Figure 4—the game enters into a regime where the loosing
MG can be considered a social simulation that aims to group is close to N/2, hence we might say coordination is
reproduce a simplified human scenario. Each (human) agent, performing well.
in this scenario, must do a choice under the minority global If the number of agents increase further, fluctuations rapidly
rule. In order to study the system composed by different increase beyond the level of random agents and the game
kinds of players with different behaviours, we here adopt enters into the crowded regime. With a low value of α the
a logic-based approach to build the players. In this way, value of σ 2 /N is very large: it scales like σ 2 /N ≈ α−1 .
it is possible to observe particular social behaviours which The results of other observations suggest that the behaviour
would otherwise remain hidden in the approximation of the of MG can be classified in two phases: an information-rich
mathematical model. asymmetric phase, and an unpredictable or symmetric phase.
A more recent paper (2) observes that MG players could be A phase transition is located where σ 2 /N attains its minimum
naturally modelled as agents with a full BDI model, and adopts (αc = 1/2), and it separates the symmetric phase with α < αc
a new adaptive stochastic MG with dynamically evolving from an asymmetric phase with α > αc .
strategies in the simulation. We can then apply our simulation All these cases have been observed with the TuCSoN
framework, with Logic Agents and Coordination Artifacts, simulation framework described in next section.
183
IV. T HE S IMULATION F RAMEWORK 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 reaction(out(play(X)),(
of this MG simulation is the possibility of studying the %read the last value of count
in_r(count(Y)),
evolution of the system with particular and different kinds of Z is Y+1,
agent behaviour at the micro level, imposed as coordination %calculate the partial result
parameters which are changed on-the-fly. in_r(sum(M)),
V is M+X,
A. Operating Instructions out_r(sum(V)),
%store the new value of count
Each agent has an internal plan, structured as an algebraic out_r(count(Z))
composition of allowed actions (with their preconditions) and %this action will be catch
)).
perceptions (with their effects), that enables the agent to use
the coordination artifact to play the MG. This plan can be This reaction considers the bet (X), counts the bets (Z),
seen as Operating Instructions (7), a formal description based and computes the partial result of the game (V). When
on Labelled Transition Systems (LTS) that the agent reads to all the agents have played, the artifact produces the tuple
understand what its step-by-step behaviour should be. Through winner(Result,Turn,NumberOfLoss,MemorySize,last/more)
an inference process, the agent accordingly chooses the next which is the main tuple of MG coordination.
action to execute, thus performing the cycle described in reaction(out_r(count(X)),(
Section II. %check if all agents have already played
Operating instructions are expressed by the following the- rd_r(numag(Num)),
X=:=Num,
ory: in_r(totcount(T)),
% pre=Preconditions Turn is T+1,
% eff=Effects rd_r(game(G)),
% act=Action %read the result of the game
% per=Perception in_r(sum(Result)),
firststate(agent(first,[])). %reset the sum value
definitions([ out_r(sum(0)),
def(first,[],...), rd_r(countsession(CS)),
%definition of the main control loop in_r(count(Y)),
def(main,[S], %reset the count value
[act(out(play(X)),pre(choice(S,X))), out_r(count(0)),
per(in(result(Y)),eff(res(Y))), %calculate variance
agent(main,[S])] in_r(qsum(SQ)),
), NSQ is Result*Result+SQ,
... out_r(qsum(NSQ)),
]). %calculate mean
in_r(totsum(R)),
The first part of operating instructions is expressed by NewS is R+Result,
out_r(totsum(NewS)),
term first, where the agent reads the game parameters that rd_r(numloss(NumberOfLoss)),
are stored in the KB, and randomly creates its own set of rd_r(mem(MemorySize)),
strategies. % put out the tuple with the result
out_r(winner(Result,Turn,NumberOfLoss,
In the successive part main, the agent executes its main MemorySize,G)),
cycle. It first puts tuple play(X) in the tuple space, where out_r(totcount(Turn))
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.
B. Tuple Centre Behaviour
The interaction protocol between agents and the coordina-
tion 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 Fig. 5. Interface of the Monitor Agent
184
Fig. 6. Variance of the System with Initial Parameters N = 5 and m = 3 Fig. 7. System Evolution of the Variance in Figure 6
The winner tuple contains the result of the game D. Simulation Results
(Result), the number of steps (Turn), two tuning parame- The result of the tuned simulation in Figures 6 and 7 shows
ters (NumberOfLoss and MemorySize) and one constant how the system changes its equilibrium state and achieves
to communicate agents whether they have to stop or to play a better value of variance.2 In this simulation the tuning
further (last/more). Figure 5 reports the graphical interface agent is played by a human that observes the evolution of
of the monitor agent that during its life-time reads the tuple the system and acts through the tuning interface to change
winner and draws variance. 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
C. Tuning the Simulation is useful when the game is played by few agents: these param-
eters enable system evolution and a better agent cooperative
In classical MG simulation there are a number of parameters
behaviour.
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 V. C ONCLUSION
strategies numstr(X). In our framework, we have introduced
In this paper, we aim at introducing new perspectives on
as a further parameter the number of wrong moves after
agent-based simulation by adopting a novel MAS meta-model
which the single agent should be recalculate own strategy,
based on agents and artifacts, and by applying it to Minority
represented as a tuple numloss(X). Such a threshold is
Game simulation. We implement and study MG over the
seemingly useful to break the symmetry in the strategy space
TuCSoN coordination infrastructure, and show some benefits
when the system is in a pathological state, i.e., when all
of the artifact model in terms of flexibility and controllability
agents have the same behaviour and the game oscillates from
of the simulation. In particular, in this work we focus on the
minimum to maximum value.
possibility to build a feedback loop on the rules of coordination
In our framework, it is possible to explore the possibility driving a system to a new and better equilibrium state. Many
to dynamically tune up the coordination rules by changing related agent simulation tools actually exist: as this paper is a
numloss and mem coordination parameters, which are stored starting point, we plan to perform a systematic comparison
as tuples in the coordination artifact. The simulation architec- of their expressiveness and features. In the future, we are
ture built in this way, in fact, allows for on-the-fly change of interested in constructing an intelligent and adaptive tuning
some game configuration parameters—such as the dimension agent with a BDI architecture, substituting the human agent
of agent memory—with no need to stop the simulation and in driving the evolution over time of the system behaviour.
re-program the agents.
By changing the parameters, the tuning agent can drive the
VI. ACKNOWLEDGEMENTS
system from an equilibrium state to another, by controlling
agent strategies, the dimension of memory, or the number of The first author of this paper, Enrico Oliva, would like
losses that an agent can accept before discarding a strategy. to warmly thank Dr. Peter McBurney and the Department
This agent observes system variance, and decides whether and of Computer Science at University of Liverpool for their
how to change tuning parameters: reference variance is calcu- scientific support and their hospitality during his stay in
lated by first making agents playing the game randomly— Liverpool, when this paper was mostly written.
see Figure 4. The new value of parameters is stored in
tuple centre through tuples numloss(NumberOfLoss) and 2 In Figure 6, the first phase of equilibrium is followed by a second one
mem(MemorySize), the rules of coordination react and obtained by changing the threshold parameter S = 5. Finally, a third phase
update the information that will be read by the agents. is obtained changing the dimension of the memory to m = 5.
185
R EFERENCES id=1018409.1018752
[10] D. Challet and Y.-C. Zhang, “Emergence of cooperation
[1] W. B. Arthur, “Inductive reasoning and bounded rational- and organization in an evolutionary game,” Physica
ity (the El Farol problem),” American Economic Review, A: Statistical and Theoretical Physics, vol. 246, no.
vol. 84, no. 2, pp. 406–411, May 1994. 3–4, pp. 407–418, Dec. 1997. [Online]. Available:
[2] W. Renz and J. Sudeikat, “Modeling Minority Games http://dx.doi.org/10.1016/S0378-4371(97)00419-6
with BDI agents – a case study,” in Multiagent [11] D. Challet, M. Marsili, and Y.-C. Zhang, “Modeling
System Technologies, ser. LNCS, T. Eymann, F. Klügl, market mechanism with minority game,” Physica A:
W. Lamersdorf, M. Klusch, and M. N. Huhns, Eds. Statistical and Theoretical Physics, vol. 276, no.
Springer, 2005, vol. 3550, pp. 71–81, 3rd German 1–2, pp. 284–315, Feb. 2000. [Online]. Available:
Conference (MATES 2005), Koblenz, Germany, 11- http://dx.doi.org/10.1016/S0378-4371(99)00446-X
13 Sept. 2005. Proceedings. [Online]. Available: http: [12] H. V. D. Parunak, S. Brueckner, J. Sauter, and R. Savit,
//www.springerlink.com/link.asp?id=y62q174g56788gh8 “Effort profiles in multi-agent resource allocation,” in 1st
[3] S. Parsons and P. McBurney, “Argumentation-based com- International Joint Conference on Autonomous Agents
munication between agents.” in Communication in Mul- and Multiagent Systems (AAMAS 2002), C. Castelfranchi
tiagent Systems, ser. Lecture Notes in Computer Science, and W. L. Johnson, Eds. Bologna, Italy: ACM, 15–
M.-P. Huget, Ed., vol. 2650. Springer, 2003, pp. 164– 19 July 2002, pp. 248–255.
178. [13] N. R. Jennings, C. Sierra, L. Sonenberg, and M. Tambe,
[4] A. Ricci, M. Viroli, and A. Omicini, “Programming Eds., 3rd International Joint Conference on Autonomous
MAS with artifacts,” in Programming Multi-Agent Agents and Multiagent Systems (AAMAS 2004). New
Systems, ser. LNAI, R. P. Bordini, M. Dastani, York, USA: ACM, 19–23 July 2004.
J. Dix, and A. El Fallah Seghrouchni, Eds.
Springer, Mar. 2006, vol. 3862, pp. 206–221, 3rd
International Workshop (PROMAS 2005), AAMAS
2005, Utrecht, The Netherlands, 26 July 2005.
Revised and Invited Papers. [Online]. Avail-
able: http://www.springerlink.com/openurl.asp?genre=
article&issn=0302-9743&volume=3862&spage=206
[5] A. Ricci, A. Omicini, and E. Denti, “Activity Theory
as a framework for MAS coordination,” in Engineering
Societies in the Agents World III, ser. LNCS, P. Petta,
R. Tolksdorf, and F. Zambonelli, Eds. Springer-Verlag,
Apr. 2003, vol. 2577, pp. 96–110.
[6] A. Omicini and F. Zambonelli, “Coordination for Inter-
net application development,” Autonomous Agents and
Multi-Agent Systems, vol. 2, no. 3, pp. 251–269, Sept.
1999.
[7] M. Viroli and A. Ricci, “Instructions-based semantics
of agent mediated interaction,” in 3rd International
Joint Conference on Autonomous Agents and Multiagent
Systems (AAMAS 2004), N. R. Jennings, C. Sierra,
L. Sonenberg, and M. Tambe, Eds., vol. 1. New
York, USA: ACM, 19–23 July 2004, pp. 102–109.
[Online]. Available: http://portal.acm.org/citation.cfm?
id=1018409.1018737
[8] A. Omicini and E. Denti, “Formal ReSpecT,” Electronic
Notes in Theoretical Computer Science, vol. 48, pp. 179–
196, June 2001.
[9] A. Omicini, A. Ricci, M. Viroli, C. Castelfranchi, and
L. Tummolini, “Coordination artifacts: Environment-
based coordination for intelligent agents,” in 3rd
International Joint Conference on Autonomous Agents
and Multiagent Systems (AAMAS 2004), N. R. Jennings,
C. Sierra, L. Sonenberg, and M. Tambe, Eds., vol. 1.
New York, USA: ACM, 19–23 July 2004, pp. 286–293.
[Online]. Available: http://portal.acm.org/citation.cfm?
186