Untangling Complex Systems, page 94
However, the evaporation of the pheromone assures that suboptimal paths discovered earlier do
not impede to find better solutions, exploiting the power of each individual ant to make stochas-
tic choices. The swarm intelligence of social insects has inspired two families of algorithms:
(I) Ant Colony Optimization (ACO), and (II) Particle Swarm Optimization (PSO). ACO has been
used to solve heuristically the Traveling Salesman Problem (Dorigo et al. 1996). An artificial ant
releases pheromone on its path. The amount of pheromone laid down is inversely proportional to
the overall length of the path. Longer routes will have much less pheromone than shorter routes.
Longer routes become less attractive, and the longest routes can become wholly neglected after a
while because pheromone evaporates over time. By repeating the travel many times, the artificial
ants are able to find the shortest paths. ACO algorithm has also been proposed to solve other
combinatorial optimization problems, such as the job-shop scheduling problem. A PSO algorithm
starts with a swarm of particles, each representing a potential solution to a problem (Kennedy and
Eberhart 1995). A particle has both a position and a velocity. Its position is the candidate solu-
tion it currently represents. Its velocity is a displacement vector in the search space, which will
contribute toward a fruitful change in its location at the next iteration. Particles move through a
multidimensional search space. The calculation of a new position for each particle is influenced
by three contributions. First, the previous velocity. Second, the personal best: the particle remem-
bers the best place it has encountered. Third, the global best: every particle in the swarm is aware
of the best position that any particle has discovered. After a random initialization of positions
and velocities, the evaluation of the fitness of the particles’ current positions, and consequent
initialization of the personal bests and global best, PSO proceeds in a remarkably straightforward
manner. PSO algorithms have been used to solve various optimization problems. They have been
applied to unsupervised learning, game learning, scheduling and planning applications, and as an
alternative to backpropagation for training an artificial neural network.
TRY EXERCISE 13.4
What surprises biologists, economists, and social scientists is the observation that although liv-
ing beings are selfish, there are notable examples of cooperation. Every living being is instinc-
tively selfish because its primary purposes are those of fighting to survive and reproduce. Despite
this fierce competition, there are many examples of the social organization driven by cooperation.
480
Untangling Complex Systems
How can such cooperation arise among fundamentally selfish individuals? There are different mech-
anisms (Nowak 2006). Often, the donor and the recipient of an altruistic act are genetic relatives
(according to the so-called “kin selection” mechanism). But, we observe cooperation also between
unrelated individuals or even between members of different species. Cooperation may arise from
two individuals, A and B, who repeatedly encounter, based on the direct reciprocity mechanism:
at every meeting, every individual can choose to cooperate or defect. For example, if A cooperates
now, B may cooperate next time. The idea might be to help someone who may later help you or
metaphorically speaking “you scratch my back and I’ll scratch yours.” Hence, it might pay off to
cooperate. What is a good strategy? Around 1950, during the Cold War, two mathematical game
theorists, Merrill Flood and Melvin Drescher of the RAND Corporation,3 invented the Prisoner’s
Dilemma as a model to investigate the cooperation dilemma. Two individuals, A and B, are arrested
for committing a crime together and are questioned into separate rooms. Each prisoner is given the
opportunity of either betraying the other by testifying against him or cooperating with the other by
remaining silent. The offer is:
• If both A and B betray reciprocally, each of them serves three years in prison.
• If A betrays B, whereas B remains silent, A will be set free, whereas B will serve five years
in prison. The opposite is also true.
• If both A and B remain silent, both of them will serve only one year in prison.
The options are synthetically presented in the payoff matrix of Table 13.1.
A and B must choose before knowing the other’s decision. Both of them might reason as fol-
lows. “If my companion remains silent, it would be better for me to betray them, because I will be
set free. On the other hand, if my companion betrays me, it is convenient that I betray him, too.
Otherwise, he will be set free, and I will spend five years in prison.” If the decision must be taken
just once, there is no escape from this sad logic. Thus, they both betray, although they are aware
that if both remained silent, they would serve just one year in prison. The pursuit of self-interest
leads both of them to a poor outcome. The Prisoner’s Dilemma can be easily transformed in a
“donation game” in which cooperation corresponds to offering the other player a benefit b at a per-
sonal cost c with b > c. Defection means offering nothing. The payoff matrix is thus as Table 13.2.
In the 1980s, Robert Axelrod organized a series of Iterated Prisoner’s Dilemma tournaments
for computer programs to discover the best strategy. The winning strategy was the simplest of all,
tit-for-tat, echoing the fundamental principle of lex talionis: take an eye for an eye (Axelrod 1984).
This strategy always starts with cooperation; then it does whatever the other player has done in the
TABLE 13.1
Payoff Matrix for the Prisoner’s
Dilemma
A
A stays
B
silent
A betrays
B stays silent
1
0
1
5
B betrays
5
3
0
3
3 RAND Corporation is a nonprofit institution that helps improve policy and decision making on energy, education, health, justice, environment, and international and military affairs through research and analysis. The address of its website is
https://www.rand.org/.
How to Untangle Complex Systems?
481
TABLE 13.2
Payoff Matrix for a Generalized Prisoner’s
Dilemma
A
B
A cooperates
A defects
B cooperates
b- c
b
b- c
- c
B defects
- c
0
b
0
previous round: a cooperation for a cooperation, a defection for a defection. From the success of the
tit-for-tat strategy, Axelrod extracted some lessons:
• Be nice: never be the first to defect.
• Be retaliatory: retaliate immediately when betrayed.
• Be forgiving: relent after a single cycle of punishment.
• Be clear: be transparent about your strategy, e.g., make it easy to infer.
Tit-for-tat is not a perfect strategy when there are accidental defections due to “trembling hands” or
“blurred minds.” In fact, it reacts to an accidental defection always with an immediate retaliation.
An alternative strategy is generous-tit-for-tat that cooperates whenever the counterpart cooperates
but sometimes cooperates although the other player has defected, admitting forgiveness (Nowak
and Sigmund 1992). The tit-for-tat strategy is an efficient catalyst of cooperation in a society where
nearly everybody is a defector, but once cooperation is established, the win-stay lose-shift strategy
is better able to maintain it. Win-stay, lose-shift embodies the idea of repeating your previous move
whenever you are doing well but changing otherwise (Nowak and Sigmund, 1993).
Sometimes humans cooperate even when they are not in direct contact. One person is in a posi-
tion to help another, but there is no possibility for a direct reciprocation. For example, we help
strangers who are in need by donating to charities that do not give us anything in return. What may
fuel this kind of cooperation is reputation. Helping someone establishes a good reputation, which
will be rewarded by others (Nowak and Sigmund 1998). People who are more helpful are more
likely to receive help. This behavior is indirect reciprocity: “You scratch my back, and I’ll scratch
someone else’s” or “I scratch your back, and someone else will scratch mine.” Indirect reciprocity
has cognitive demands. It is necessary that we remember our own interactions, and we must also
monitor the ever-changing social network of the group. Language facilitates the acquisition of infor-
mation and gossip. Indirect reciprocity is likely to be connected with the origin of moral and social
norms (Nowak and Sigmund 2005).
A further improvement of the Prisoner’s Dilemma model is the introduction of spatial structure.
In the original model, there was no notion of space. In fact, it was equally likely for any player to
encounter any other player. The mathematical biologist Martin Nowak envisioned that placing play-
ers on spatial structures or social networks imply that some individuals interact more often than
others and have substantial effect on the evolution of cooperation. A cooperator pays a cost for each
neighbor to receive a benefit. Defectors have no costs, and their neighbors receive no benefits. In this
setting, cooperators form network clusters, where they help each other (Lieberman et al. 2005) and
a group of cooperators is expected to be more successful than a group of defectors.
Computer simulations of idea models, such as the Prisoner’s Dilemma, are sometimes the
only available means of investigating Complex Systems. They are used to advance science and
policy in many contexts. However, they describe a reality that is highly simplified. For example,
the economy is a vast and complex set of arrangements and actions wherein economic agents
482
Untangling Complex Systems
Economic agents
Economy
FIGURE 13.20 Scheme of the mutual relationships between the economic agents and the environment
they originate. The bottom-up and top-down excitatory and inhibitory causations embody the Adam Smith’s
“Invisible Hand.”
(producers, consumers, investors) constantly change their actions and strategies in response to the
outcome they mutually create. The economy emerges from a continually developing set of techno-
logical innovations, institutions, and arrangements that induce further innovations, institutions, and
arrangements (Arthur 2015). There are mutual “excitatory” and “inhibitory” effects between the
economic agents and the economy they contribute to creating (see Figure 13.20). These bottom-up
and top-down causation phenomena embody the Adam Smith’s “Invisible Hand.” The interact-
ing agents self-organize, and the patterns they give rise, in turn, cause the interacting elements to
change or adapt.
In complex situations, deductive rationality can break down. In fact, agents cannot rely upon
the other agents to behave under perfect rationality, and so they are forced to guess their behavior.
Agents are induced to formulate subjective beliefs about subjective beliefs. Objective, universal
and well-defined assumptions then cease to apply, and rational deductive reasoning loses meaning.
In the presence of complex, variable, and ill-defined situations humans look for patterns to construct
internal models or hypotheses. We make localized deductions based on our current hypotheses.
We test our temporary deductions by collecting feedback from the environment. We strengthen or
weaken our trust in our hypothesis and models, discarding some of them when they fail to predict,
and replacing them with new ones. Such mental behavior is inductive and can be modeled in a vari-
ety of ways. Usually, it leads to a rich psychological world in which agents’ hypothesis or mental
models compete for survival against other agents’ hypothesis and mental models: a psychological
world that is both complex and evolutionary (Arthur 2015).
TRY EXERCISE 13.5
13.3.2 comPuTing by exPloiTing The Physicochemical laws
All the phenomena that are investigated by science are causal. Any cause and effect relation can
be described as a computation wherein the cause is the input, the effect is the output, and the law
governing the transformation is the algorithm for the computation. The law can be either linear or
non-linear. Therefore, different types of computation can be carried out depending on which physi-
cochemical law we exploit (see Figure 13.21).
13.3.2.1 Thermodynamics
Any physicochemical system, pushed away from equilibrium by some temporary forces or main-
tained out-of-equilibrium constantly by some permanent forces, can be imagined being used as a
computing machine. The laws that govern its response to the external forces rule its computational
performances. The conditions required to process information are (I) the distinguishability of states
within the system and (II) the capability for a controlled change of its states. If the system is merely
a particle in two potential energy wells, like that shown in Figure 13.22, the location of the particle
How to Untangle Complex Systems?
483
FIGURE 13.21 Types of computations that can be implemented by exploiting the natural physicochemical laws.
U
a
Eb
0
x
FIGURE 13.22 A particle (black circle) in two potential energy wells. The height of the energetic barrier is
Eb whereas the barrier width is a.
in one of the two wells is said to be distinguishable if there is a very low probability of spontaneous
transition from one well to the other. In other words, the probability of staying in the two wells must
be different. If it is the same, i.e., 0.5, the two states are indistinguishable. The particle can sponta-
neously change well, and hence state, either going “classically” over the barrier or through quantum
mechanical tunneling transitions.
The probability of a classical transition over barrier at temperature T is
Eb
−
P
kT
classical = e
[13.7]
Imposing Pclassical = 0 5
. , it derives that distinguishability is lost when the energetic barrier is
Eb ≤ kTln
2. The barrier must have Eb > kTln 2 to distinguish the two possible states.
From quantum mechanics, we know that when the barrier width a is small, the particle can tun-
nel through the energetic barrier Eb. A simple analytical form of tunneling probability for a particle
of effective mass m through a rectangular barrier of width a is given by the Wentzel-Kramers-
Brillouin approximation (Zhirnov et al. 2003):
484
Untangling Complex Systems
2 2 m
−
a Eb
P
quantum = e
[13.8]
Imposing Pquantum = 0 5
. , it derives that distinguishability is lost by quantum mechanical tunneling
events when a ≤ ( ln
2) (2 2 mE )
b , i.e., when the barrier width is less than the limit fixed by the
Heisenberg’s uncertainty principle, which, for an electron, is:
∆ x ≥ =
=
=1 5
. nm(at300 K) [13.9]
∆ p
2 mEb
2 mkTln 2
The total probability of transition by either “classical” or tunneling mechanism is:
P
)(
)
tot = Pclassical + Pquantum − ( Pclassical
Pquantum [13.10]
The states in the two wells become indistinguishable when (Zhirnov et al. 2003)
2
ln
( 2 2
)
Eb ≈ kTln 2 +
[13.11]
8 ma 2
The second term on the right part of the equation [13.11] becomes significant when a < 5nm. If a < 5 nm, the barrier height must be E
2
2
2)2) (8 2
)
b > kTln + (
( ln
ma to have two distinguishable states.
When we can distinguish states, we can make operations by switching from one state to the
other in a controllable way. The logical operations of a computation can be reversible or irreversible.
When we use elementary logic operations, such as AND, OR, etc., with two inputs and one output,
or we erase a bit in the memory, we do irreversible logical operations. A logical operation is irrevers-
ible whenever the inputs cannot be reconstructed from the outputs.
