MAS Project: Gossip

Tiemen Rozeboom 1339125
Jordy Oldenkamp 1339087

 


 

Contents

Contents. 2

Introduction. 3

Gossip. 3

Analyzing the journal 4

The Method. 5

 

 

 


 

Introduction

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'.

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.

http://www.t-men.nl/mas/index_html_1d43d752.jpg
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

Analyzing the journal

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.

The Method

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)

 

-> ~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)

 

-> ~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)

 

-> ~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)

 

-> ~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)

 

“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)

 

-> ~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,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)

 

-> ~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,C)

-> In(C,B)

-> P(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)

 

-> ~In(xD,F)

-> P(F,xD) ^ P(xD,C)

S(B,E,A)

-> In(A,E)

-> P(E,A)

 

-> ~In(A,E)

-> P(E,A) ^ P(A,B)

S(A,F,D)

->  In(D,F)

-> P(F,D)

 

-> ~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,C)

-> In(C,B)

-> P(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.

Conclusion

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.