Agent-based Systems
Paolo Turrini
www.dcs.warwick.ac.uk/~pturrini R p.turrini@warwick.ac.uk
Knowledge
Paolo Turrini Knowledge Agent-based Systems
The plan for today
Knowledge and possible worlds: the knowledge relation
one agent versus many
various forms of group knowledge
Knowing how to play
combining knowledge and strategy intuitions from extensive games
Paolo Turrini Knowledge Agent-based Systems
Why knowledge?
Ann
LR
Bob Bob
LRLR (w,l) (d,d) (d,d) (w,l)
Bob has a strategy to win…
Paolo Turrini Knowledge
Agent-based Systems
Why knowledge?
Ann
LR
Bob Bob
LRLR (w,l) (d,d) (d,d) (w,l)
Bob has a strategy to win… but does he know which one?
Paolo Turrini Knowledge Agent-based Systems
Knowledge vs Ignorance
The main underlying assumption behind the theory of knowledge in multi-agent systems (and in game theory) is that we live in one world and this world collects all the relevant facts (for instance, those that are true now, were true in the past and will be true in the future).
However, we are typically not able to fully determine it: “is my mom thinking of me now?”
“was there a penalty on Cristiano Ronaldo?”
“will Berlusconi be president again?”
Paolo Turrini Knowledge Agent-based Systems
Knowledge vs Ignorance
w1 w2
Example (Cristiano Ronaldo)
I’m watching a Juventus game and my stream pauses.
I’ve missed a penalty on Cristiano Ronaldo.
If Ronaldo is all that matters to me, there are two possible worlds:
A world in which Ronaldo dives
A world in which Ronaldo does not dive
I cannot say which one of these two worlds I’m living at.
Paolo Turrini Knowledge Agent-based Systems
Knowledge vs Ignorance
w1 w2 w3 w4
Red is dive, blue is mum, purple is both, black is none.
Typically there are other matters that I deem relevant.
I might be able to distinguish some of their combination
Paolo Turrini Knowledge Agent-based Systems
Knowledge vs Ignorance
w1 w2 w3 w4
Red is dive, blue is mum, purple is both, black is none.
Definition (Facts)
Call any E ⊆ W a fact, i.e., a fact is a subset of the possible worlds. Name two facts in the example. What can you say about what I know?
Paolo Turrini Knowledge Agent-based Systems
Knowledge, formally
We model knowledge as a relation over the set of worlds. Let us start with one agent, i, and their knowledge relation:
∼i ⊆ W × W
Intuitively (w1, w2) ∈∼i means that agent i cannot distinguish between
worlds w1 and w2.
So if i lives at w1 they consider it possible that real world is actually w2.
We call this relation the indistinguishability relation.
Paolo Turrini Knowledge Agent-based Systems
Properties
Again: (w1, w2) ∈∼i means i cannot distinguish between w1 and w2. What are the intuitive properties of the indistinguishability relation?
Is it reflexive?
Reflexivity: for all w ∈ W, (w,w) ∈∼i Does this make sense to you?
Paolo Turrini Knowledge Agent-based Systems
Properties
Again: (w1, w2) ∈∼i means i cannot distinguish between w1 and w2. What are the intuitive properties of the indistinguishability relation?
Is it symmetric?
Symmetry: for all w1, w2 ∈ W , IF (w1, w2) ∈∼i THEN (w2, w1) ∈∼i Does this make sense to you?
Paolo Turrini Knowledge Agent-based Systems
Properties
Again: (w1, w2) ∈∼i means i cannot distinguish between w1 and w2. What are the intuitive properties of the indistinguishability relation?
Is it transitive?
Transitivity: for all w1, w2, w3 ∈ W , IF (w1, w2) ∈∼i and (w2, w3) ∈∼i THEN (w1, w3) ∈∼i
Does this make sense to you?
Paolo Turrini Knowledge Agent-based Systems
Properties
Again: (w1, w2) ∈∼i means i cannot distinguish between w1 and w2. What are the intuitive properties of the indistinguishability relation?
Is it serial?
Seriality: for all w1 ∈ W , there exists w2 ∈ W such that (w1, w2) ∈∼i . Does this make sense to you?
Can you possibly accept seriality without accepting the previous properties?
Paolo Turrini Knowledge Agent-based Systems
Knowledge
There is no ultimate model of knowledge, it depends on what kind of knowledge we want to capture.
For the time being, we are going to assume that it is an equivalence relation over the set of all states: reflexive, transitive, symmetric.
It is therefore a partition of the set of all states (if you don’t know why, prove it!)
Paolo Turrini Knowledge Agent-based Systems
Knowledge and Ignorance
w1 w2 w3 w4
Red is dive, blue is mum, purple is both, black is none.
I’m going to compactly represent the relation with undirected arcs between indistinguishable worlds, omitting reflexive and transitive links.
Notice how this visually partitions the set of all worlds.
Paolo Turrini Knowledge Agent-based Systems
Knowledge and Ignorance
w1 w2 w3 w4
Red is dive, blue is mum, purple is both, black is none.
Now knowledge…
I know that something is true if and only if that something is true at all the worlds that I cannot distinguish from the one I’m at.
Paolo Turrini Knowledge Agent-based Systems
Knowledge and Ignorance
w1 w2 w3 w4
Red is dive, blue is mum, purple is both, black is none.
Let ∼i [w] = {w′ | (w,w′) ∈∼i} be what i cannot distinguish from w. Wesaythati knowsfactE atw whenever∼i [w]⊆E
We denote KiE = {w |∼i [w] ⊆ E} the worlds at which i knows E.
Paolo Turrini Knowledge Agent-based Systems
Knowledge and Ignorance
w1 w2
What does the agent know?
Paolo Turrini Knowledge Agent-based Systems
Knowledge and Ignorance
w1 w2 w3
What does the agent know?
Paolo Turrini Knowledge Agent-based Systems
Knowledge and Ignorance
w1 w2 w3
What does the agent know?
Paolo Turrini Knowledge Agent-based Systems
Knowledge and Ignorance
Bob
Ann
w1 w2 w3
Now let us populate the world with other agents, each with their indistinguishability relation.
Notice the relations don’t need to be related in any way. What do these agents know?
Paolo Turrini Knowledge Agent-based Systems
Multi-agent knowledge
At w1:
Ann
Bob
w1 w2 w3
Does Ann know red?
Does Bob know Ann knows red?
Does Bob know Ann does not know Bob knows red?
Does Bob know Bob knows Ann does not know Bob knows red?
Paolo Turrini Knowledge Agent-based Systems
Group knowledge
Bob
Ann
w1 w2 w3
We can talk about the knowledge of many agents. But we can also talk about what they know together.
What does this mean? Any intuitions?
Paolo Turrini Knowledge Agent-based Systems
Group knowledge
Ann
Bob
w1 w2 w3
What everyone knows already? Or with communication?
Or joint observation?
As always, we need to make choices and restrict our study to some interesting forms of group knowledge.
Paolo Turrini Knowledge Agent-based Systems
General Knowledge
Let N be the set of agents and W the set of worlds. Let E be a fact.
Definition (General Knowledge)
It is general knowledge that E at w if everyone knows E at w. General knowledge is what everyone knows.
For example, Ann knows E and Bob knows E.
Paolo Turrini Knowledge Agent-based Systems
General Knowledge
Bob
Ann
w1 w2 w3
Tell me two facts that are general knowledge at w3.
Paolo Turrini Knowledge Agent-based Systems
General Knowledge
Bob
Ann
w1 w2 w3
Tell me two facts that are general knowledge at w3. At w2?
Paolo Turrini Knowledge Agent-based Systems
General Knowledge
Let N be the set of agents and W the set of worlds. Let E be a fact.
KE = KiE = {w |∼i [w]⊆E} i∈N i∈N
is the set of worlds where everyone knows E.
Notice: w ∈ KE means that everyone knows E at w.
Paolo Turrini Knowledge Agent-based Systems
General Knowledge
Bob
Ann
w1 w2 w3
Tell me one fact that is general knowledge everywhere.
Paolo Turrini Knowledge Agent-based Systems
General Knowledge
Bob
Ann
w1 w2 w3
Tell me one fact that is general knowledge everywhere.
Can it be that (= can you come up with a model such that) nothing is general knowledge?
Paolo Turrini Knowledge Agent-based Systems
Distributed Knowledge
Let N be the set of agents and W the set of worlds. Let E be a fact.
Definition (Distributed Knowledge)
We say that it is distributed knowledge that E at w if every agent knew E by intersecting their indistinguishability relation.
Distributed knowledge is the implicit knowledge the agents have, what they would know if they could communicate.
In other words, what they would know as a group.
For example: if Ann cannot distinguish w1 from w2 and Bob cannot distinguish w2 from w3 then, talking, they would know they are at w2.
Paolo Turrini Knowledge Agent-based Systems
Distributed Knowledge
Bob
Ann
w1 w2 w3
Tell me one fact that is distributed knowledge at w2. Tell me one fact that is not.
Paolo Turrini Knowledge Agent-based Systems
Distributed Knowledge
Let N be the set of agents and W the set of worlds. Let E be a fact.
DKE ={w |( ∼i [w])⊆E} i∈N
is the set of worlds where it is distributed knowledge that E.
Paolo Turrini Knowledge Agent-based Systems
Distributed Knowledge
Bob
Ann
w1 w2 w3
Tell me one fact that is distributed knowledge everywhere. Tell me one fact that is not.
Paolo Turrini Knowledge Agent-based Systems
Common Knowledge
Let N be the set of agents and W the set of worlds. Let E be a fact.
Definition
It is common knowledge that E at w if everyone knows E at w and knows that everyone knows, and knows that everyone knows that everyone knows, and kn… (too long to write)
Common knowledge is what is experienced by everyone, e.g., a result of a joint public observation.
It is an idealised setting, but – with some lenience – it can reasonably be assumed in certain circumstances.
For instance: look at the clock now. Its time is common knowledge.
Paolo Turrini Knowledge Agent-based Systems
Common Knowledge
Bob
Ann
w1 w2 w3
What is common knowledge at w3? What is not?
Paolo Turrini Knowledge Agent-based Systems
Common Knowledge
Let N be the set of agents and W the set of worlds. Let E be a fact.
∞
CE = K k E = KE ∩ KKE ∩ KKKE . . . k=1
is the set of worlds where it is common knowledge that E.
Paolo Turrini Knowledge Agent-based Systems
Common Knowledge
Bob
Ann
w1 w2 w3
What is common knowledge everywhere? What is not?
Paolo Turrini Knowledge Agent-based Systems
Learning
w1 w2 w3 w4
Red is dive, blue is mum, purple is both, black is none.
Suppose I’m told Ronaldo did dive.
How does the model change if I learn a new fact?
Paolo Turrini Knowledge Agent-based Systems
Learning
w1 w2 w3 w4
Red is dive, blue is mum, purple is both, black is none.
Suppose I’m told Ronaldo did dive.
How does the model change if I learn a new fact?
Paolo Turrini Knowledge Agent-based Systems
Chess vs Poker
Ann
LR
Bob Bob
LRLR (w,l) (d,d) (d,d) (w,l)
Here Bob knows what Ann has chosen.
Paolo Turrini
Knowledge
Agent-based Systems
Chess vs Poker
Ann
LR
Bob Bob
LRLR (w,l) (d,d) (d,d) (w,l)
Here he doesn’t.
In other words, there are two worlds that Bob cannot distinguish:
the one in which Ann has chosen to go left
and the other in which Ann has chosen to go right.
Paolo Turrini Knowledge Agent-based Systems
Chess vs Poker
Ann
LR
Bob Bob
LRLR (w,l) (d,d) (d,d) (w,l)
There is a difference between: knowing that I have a winning strategy
and knowing which one it is.
Bob knows he has a winning strategy, but does not know which one.
Paolo Turrini Knowledge Agent-based Systems
Knowing that versus knowing how
It makes sense to assume that players will choose the same actions in situations that they cannot distinguish.
After all, how can I say “if Ann has chosen left, then I go right”, if I cannot observe any sign of this?
Paolo Turrini Knowledge Agent-based Systems
Knowing that versus knowing how
Definition (Uniform Strategies)
Let H be the set of histories of a game and let ∼i be a relation over these histories. a
A strategy σi is said to be uniform if σi (h) = σi (h′) whenever h ∼i h′.
In words, If I can’t distinguish two situations, I’m going to have to play the
same action in both.
aThis is not a rigorous definition at this stage, but it’s easy to see that it can fall under our case if we interpret a history as a possible world. We will make it precise later on in the course.
If I have a uniform strategy to win, then I know how to win. Otherwise, I don’t.
Bob, in the previous example, knows he can win, but does not know how.
Paolo Turrini Knowledge Agent-based Systems
Chess vs Poker
Ann
LR
Bob Bob
LRLR (w,l) (d,d) (d,d) (w,l)
Which strategies are uniform? Which ones aren’t?
Paolo Turrini
Knowledge
Agent-based Systems
What we have seen
A mathematical model of knowledge and ignorance Multi-agent knowledge
Group knowledge: general, distributed, common Knowing that versus knowing know
Paolo Turrini Knowledge Agent-based Systems
What next?
We are going to look at logical decisions in computational environments: actions, knowledge, objectives.
We start with one agent, others will follow.
Paolo Turrini Knowledge Agent-based Systems