MAS
Project: Gossip
Tiemen
Rozeboom 1339125
Jordy Oldenkamp 1339087
This website is part of the final assignment for the course Multi-Agent
Systems (MAS). We will investigate, model (using Kripke models) and try to
solve a problem we call 'Gossip'. Let us start by explaining the problem,
'Gossip'.
The problem we deal with is called Gossip, the background information on
the subject goes as follows: there is a group of women in a culture where each
woman has a personal temple, this temple is not to be entered by anyone else
but the Owner. The problem is that the women sneak around in other temples as
well.
Now, when the Owner of a temple suspects another woman, the Intruder, from
entering her temple, she has to punish the Intruder by beating her across the
head with a ritual stick (Illustration 1: the ritual sticks). These suspicions
arise from accusation of one or more third parties, the Accusers.
Illustration 1: the ritual sticks
Now when
accusations are made the procedure goes as follows:
Now the goal of this assignment is to analyze the following series of
events:
- C speaks to F
- B speaks to E
- A speaks to F
- F speaks to A
- E speaks to B
- A speaks to B
- E strikes A
- A strikes C
- A strikes B
- B strikes A
- F strikes D
- A strikes E
- B strikes C
- C strikes A
Before jumping straight to Kripke models we first try to logically
interpret the journal and see if this leads to a solution. The journal reveals
the following:
When we fill all this in, we
get the following ‘interpreted’ version of the journal together with the
resulting punishments/retalliations:
- C speaks to F -> C accuses D of entering F's temple (1)
-> (11)
- B speaks to E -> B accuses A of entering E's temple (2) ->
(7) -> (9)
- A speaks to F -> A accuses D of entering F's temple (3) ->
(11)
- F speaks to A -> F accuses C of entering A's temple (4) ->
(8)
- E speaks to B -> E accuses A of entering B's temple (5) ->
(10) -> (12)
- A speaks to B -> A accuses C of entering B's temple (6) ->
(13) -> (14)
- E strikes A -> E gives A an unjust punishment (7) ->
(9)
- A strikes C -> A gives C a just punishment (8)
- A strikes B -> A revenges B's accusation to E (9)
- B strikes A -> B gives A an unjust punishment (10) ->
(12)
- F strikes D -> F gives D a just punishment (11)
- A strikes E -> A revenges E's accusation to B (12)
- B strikes C -> B gives C an unjust punishment (13) ->
(14)
- C strikes A -> C revenges A's accusation to B (14)
From this we have learned that there have been 2 intruders, C and D. The
other strikings have all been consequences of false accusations. As it turns
out there has been no need for an elaborate Kripke model analysis to solve the
puzzle but for educational purposes we will create a method that will
systematically solve the puzzle.
For every instance of speaks,
we will put the possible consequences of this in a table and will eventually
solve the puzzle by means of elimination. Underlining a sentence in this table
means that with the information available at that point, it still is an option.
Striking-through means that with the current information, this sentence can
never hold.
We write down events /
proposition as follows:
S(x,y,z) = x speaks to y and rats z, note that x y and z must be different
persons as people don’t rat on
themselves nor are they accused of
entering their own temple
In(x,y) = x is an intruder of y’s temple, again x and y must be different persons
P(x,y) = x strikes y, also in this case x cannot be y as people are assumed not
to strike themselves
First, we create the initial
table where each speaks-to event is followed by its two possible consequences,
of which one must hold, initially we have no information on strikes so no lines
are underlined:
S(C,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,C) |
S(B,E,x) |
-> In(x,E) |
->
P(E,x) |
|
-> ~In(x,E) |
-> P(E,x) ^ P(x,B) |
S(A,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,A) |
S(F,A,x) |
-> In(x,A) |
->
P(A,x) |
|
-> ~In(x,A) |
-> P(A,x) ^ P(x,F) |
S(E,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,E) |
S(A,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,A) |
We now
consider information “E strikes A”, this can’t be retaliation as no this is the
first action, this information fits two possible lines which we now underline
and fill in the unknown x:
S(C,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,C) |
S(B,E,A) |
-> In(A,E) |
->
P(E,A) |
|
-> ~In(A,E) |
-> P(E,A) ^ P(A,B) |
S(A,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,A) |
S(F,A,x) |
-> In(x,A) |
->
P(A,x) |
|
-> ~In(x,A) |
-> P(A,x) ^ P(x,F) |
S(E,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,E) |
S(A,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,A) |
“A
strikes C”: can’t be retaliation of S(A,F,x) as this line is not yet a possibility,
so it must be a consequence of S(F,A,x)
S(C,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,C) |
S(B,E,A) |
-> In(A,E) |
->
P(E,A) |
|
-> ~In(A,E) |
-> P(E,A) ^ P(A,B) |
S(A,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,A) |
S(F,A,C) |
-> In(C,A) |
->
P(A,C) |
|
-> ~In(C,A) |
-> P(A,C) ^ P(C,F) |
S(E,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,E) |
S(A,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,A) |
“A strikes
B”, only fits one place eliminating In(A,E):
S(C,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,C) |
S(B,E,A) |
|
|
|
-> ~In(A,E) |
-> P(E,A) ^ P(A,B) |
S(A,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,A) |
S(F,A,C) |
-> In(C,A) |
->
P(A,C) |
|
-> ~In(C,A) |
-> P(A,C) ^ P(C,F) |
S(E,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,E) |
S(A,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,A) |
“B
strikes A”: can’t fit last row as A wouldn’t rat on herself, so must be a
consequence S(E,B,A)
S(C,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,C) |
S(B,E,A) |
|
|
|
-> ~In(A,E) |
-> P(E,A) ^ P(A,B) |
S(A,F,x) |
-> In(x,F) |
->
P(F,x) |
|
-> ~In(x,F) |
-> P(F,x) ^ P(x,A) |
S(F,A,C) |
-> In(C,A) |
->
P(A,C) |
|
-> ~In(C,A) |
-> P(A,C) ^ P(C,F) |
S(E,B,A) |
-> In(A,B) |
->
P(B,A) |
|
-> ~In(A,B) |
-> P(B,A) ^ P(A,E) |
S(A,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,A) |
“F
strikes D”: fits first or third row, at least one must accuse D, noted by xD,
meaning that if the sentence holds, the x must be replaced by a D.
S(C,F,xD) |
-> In(xD,F) |
->
P(F,xD) |
|
-> ~In(xD,F) |
-> P(F,xD) ^ P(xD,C) |
S(B,E,A) |
|
|
|
-> ~In(A,E) |
-> P(E,A) ^ P(A,B) |
S(A,F,xD) |
-> In(xD,F) |
->
P(F,xD) |
|
-> ~In(xD,F) |
-> P(F,xD) ^ P(xD,A) |
S(F,A,C) |
-> In(C,A) |
->
P(A,C) |
|
-> ~In(C,A) |
-> P(A,C) ^ P(C,F) |
S(E,B,A) |
-> In(A,B) |
->
P(B,A) |
|
-> ~In(A,B) |
-> P(B,A) ^ P(A,E) |
S(A,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,A) |
“A
strikes E”: only fits one row, so the alternative row is false
S(C,F,xD) |
-> In(xD,F) |
->
P(F,xD) |
|
-> ~In(xD,F) |
-> P(F,xD) ^ P(xD,C) |
S(B,E,A) |
|
|
|
-> ~In(A,E) |
-> P(E,A) ^ P(A,B) |
S(A,F,xD) |
-> In(xD,F) |
->
P(F,xD) |
|
-> ~In(xD,F) |
-> P(F,xD) ^ P(xD,A) |
S(F,A,C) |
-> In(C,A) |
->
P(A,C) |
|
-> ~In(C,A) |
-> P(A,C) ^ P(C,F) |
S(E,B,A) |
|
|
|
-> ~In(A,B) |
-> P(B,A) ^ P(A,E) |
S(A,B,x) |
-> In(x,B) |
->
P(B,x) |
|
-> ~In(x,B) |
-> P(B,x) ^ P(x,A) |
“B
strikes C”: must be a consequence of S(A,B,C)
S(C,F,xD) |
-> In(xD,F) |
->
P(F,xD) |
|
-> ~In(xD,F) |
-> P(F,xD) ^ P(xD,C) |
S(B,E,A) |
|
|
|
-> ~In(A,E) |
-> P(E,A) ^ P(A,B) |
S(A,F,xD) |
-> In(xD,F) |
->
P(F,xD) |
|
-> ~In(xD,F) |
-> P(F,xD) ^ P(xD,A) |
S(F,A,C) |
-> In(C,A) |
->
P(A,C) |
|
-> ~In(C,A) |
-> P(A,C) ^ P(C,F) |
S(E,B,A) |
|
|
|
-> ~In(A,B) |
-> P(B,A) ^ P(A,E) |
S(A,B,C) |
-> In(C,B) |
->
P(B,C) |
|
-> ~In(C,B) |
-> P(B,C) ^ P(C,A) |
“C
strikes A”: must be retaliation of S(A,B,C)
S(C,F,xD) |
->
In(xD,F) |
->
P(F,xD) |
|
->
~In(xD,F) |
->
P(F,xD) ^ P(xD,C) |
S(B,E,A) |
|
|
|
->
~In(A,E) |
->
P(E,A) ^ P(A,B) |
S(A,F,xD) |
-> In(xD,F) |
->
P(F,xD) |
|
-> ~In(xD,F) |
-> P(F,xD) ^ P(xD,A) |
S(F,A,C) |
-> In(C,A) |
->
P(A,C) |
|
-> ~In(C,A) |
-> P(A,C) ^ P(C,F) |
S(E,B,A) |
|
|
|
-> ~In(A,B) |
-> P(B,A) ^ P(A,E) |
S(A,B,C) |
|
|
|
-> ~In(C,B) |
-> P(B,C) ^ P(C,A) |
No more
strikes so everywhere line where ^P(x,y) must hold is eliminated, also we can
fill in xD by D as this is the only possibility.
S(C,F,D) |
->
In(D,F) |
->
P(F,D) |
|
|
|
S(B,E,A) |
|
|
|
->
~In(A,E) |
->
P(E,A) ^ P(A,B) |
S(A,F,D) |
-> In(D,F) |
->
P(F,D) |
|
|
|
S(F,A,C) |
-> In(C,A) |
->
P(A,C) |
|
|
|
S(E,B,A) |
|
|
|
-> ~In(A,B) |
-> P(B,A) ^ P(A,E) |
S(A,B,C) |
|
|
|
-> ~In(C,B) |
-> P(B,C) ^ P(C,A) |
So it
can be seen that P(A,C) and P(F,D) were the only two just accusational strikes
and the others were just retributions and unjust accusational strikes.
The Gossip
puzzle is a puzzle that can be solved analytically (by means of elimination) and
it is not hard to devise a method that will solve any (solvable) version of
this puzzle. Although if the journal gets more complex the lines containing the
‘x notation’, which essentially contains several possibilities (A,B,C,D,E and F),
will each have to be written out so that each line would be a possibility resulting
in a much larger table.
This may be
not very feasible by hand but this method can easily be translated into an
algorithm that can solve any (solvable) instance of the gossip puzzle; however
such an implementation is trivial and has therefore been omitted from this
project. Another option is of course to simply put the implication-rules into a
program like the Logic Workbench (LWB) and ask it about the In(x,y) propositions.