Transcript A Memetic Framework for D

A Memetic Framework for
Describing and Simulating Spatial
Prisoner’s Dilemma with Coalition
Formation
Sneak Review by Udara Weerakoon
Duality form of the problem
• Agents get a percentage of compromise when
cooperating with other agents
• Leaders impose taxes to the other agents
belonging to its coalition
Prisoner's Dilemma
• Two men are collectively charged with a crime
and held in separate cells. They have no way
of communicating with each other or making
any kind of agreement. The two men are told
that:
– if one of them confesses to the crime and the
other does not, the confessor will be freed, and
the other will be jailed for three years; and
– if both confess to the crime, then each will be
jailed for two years.
PD cont…
• Both prisoners know that if neither confesses,
then they will each be jailed for one year
PD Strategies
• ALL-D. This is the 'hawk' strategy, which encodes what a
game-theoretic analysis tells us is the 'rational' strategy in
the finitely iterated prisoner's dilemma: always defect, no
matter what your opponent has done.
• RANDOM. This strategy is a control: it ignores what its
opponent has done on previous rounds, and selects either
C or D at random, with equal probability of either outcome.
• TIT-FOR-TAT. This strategy is as follows:
– (1) on the first round, cooperate;
– (2) on round t > 1, do what your opponent did on round t - 1.
PD Strategies cont…
• TESTER. This strategy was intended to exploit computer
programs that did not punish defection: as its name
suggests, on the first round it tested its opponent by
defecting. If the opponent ever retaliated with
defection, then it subsequently played TIT-FOR-TAT. If
the opponent did not defect, then it played a repeated
sequence of cooperating for two rounds, then
defecting.
• JOSS. Like TESTER, the JOSS strategy was intended to
exploit 'weak' opponents. It is essentially TIT-FOR-TAT,
but 10% of the time, instead of cooperating, it will
defect.
Evolutionary Game Theory
• Evolutionary game theory (EGT) is the application of game theory to
interaction dependent strategy evolution in populations. EGT differs
from classical game theory by focusing on the dynamics of strategy
change more than the properties of strategy equilibria. Despite its
name, evolutionary game theory has become of increasing interest
to economists, sociologists, anthropologists, and philosophers
(source: common in Wikipedia and the paper).
• Replicator Dynamics
• Replicator dynamics refers to picking the percent of each agent type
to match the percent of total utility earned by agents of that type.
So if 50% of the agents use strategy A and earn 60% of the utility, in
the next round, 60% of the agents should be strategy A. It doesn’t
matter which agent has which type, but only the percentages of
each.
• Imitator Dynamics
Evolutionarily Stable Strategy
Nash Equilibrium is defect
Unfailing Bayesian Rationality
• Baysian: To evaluate the probability of a
hypothesis, the Bayesian probabilist specifies
some prior probability, which is then updated
in the light of new relevant data.
conditional probability
posterior probability
prior probability
marginal probability
Memetics
• “Memes” are a non-organic replicator form
e.g. tunes, catch-phrases, taboos
• “In the memetics model, less successful
individuals and groups within a population
imitate the behavior of the more successful
peers in order to improve their competence
for resources. Accordingly, the more above
average an individual is, the more others copy
his behavior”
Spatial Distribution
• Two dimensional square lattice of N nodes
• Each cell is rules by an agent
• It can follow two strategies
1. Defections
2. Cooperation
• Cell could be
1. Independent cell
2. Coalition cell
3. Leading cell
Probabilistic Tit-for-Tat
• Tit-for-Tat with a probability – only indep cells
Learning Automata
• Selection of next strategy based on previous
experience and payoffs
Holonic MAS
• I have to read it