# Presentation: 511237

## Common Knowledge and Handshakes in Computer-Mediated Cooperation 

- Albert Esterline
- Dept. of Computer Science
- North Carolina A&T State University

## Introduction

- Goal:
- Model human and artificial agents formally and uniformly in systems where they collaborate
- Gain insight into the conditions for coordination that such modeling offers.

## Start with a simple distributed game that displays a common interface.
Players collaborate to move proxy agents around a grid.
Requires making agreements—entails common knowledge.
Formal characterization and interpretation of common knowledge.
New common knowledge and simultaneous actions.

- Players collaborate to move proxy agents around a grid.
- Requires making agreements—entails common knowledge.
- Formal characterization and interpretation of common knowledge.
- New common knowledge and simultaneous actions.

## Handshakes and process algebras
Process-algebraic agent abstraction
Must add account of common knowledge and deontic notions.
Co-presence heuristics for establishing common knowledge
Grounding (human-computer dialog)
Back to the simple distributed game
Virtual agents

- Process-algebraic agent abstraction
- Must add account of common knowledge and deontic notions.
- Co-presence heuristics for establishing common knowledge
- Grounding (human-computer dialog)
- Back to the simple distributed game
- Virtual agents

## Simple Distributed Cooperative System

- Users move proxy agents on a grid.
- Each player participates at his own workstation.
- But system ensures that grid state is displayed in exactly the same way to all players.
- Each agent visits several goal cells specific to it in an unspecified order.
- Single-cell moves are made in round-robin fashion.
- Object: cooperate so as to minimize the total number of single-cell moves taken by all proxy agents to visit all their goal cells.

## Free space on the grid tends to occur in long corridors.
Need agreements to avoid lengthy backtracking when two agents travel in opposite directions on a corridor. 
Interface has features that allow the players to suggest and agree on itineraries.
All interaction is by clicking—easy interpretation of communication

- Need agreements to avoid lengthy backtracking when two agents travel in opposite directions on a corridor.
- Interface has features that allow the players to suggest and agree on itineraries.
- All interaction is by clicking—easy interpretation of communication

## A player can make a suggestion when its his/her turn.
All players can negotiate.
Agreement must be unanimous.
An agreement is obligates the player of the proxy agent in question.
It must be common knowledge.

- All players can negotiate.
- Agreement must be unanimous.
- An agreement is obligates the player of the proxy agent in question.
- It must be *common knowledge*.

## Slide 8

## Three Approaches to Common KnowledgeIterate Approach

- Assume *n* agents named 1, 2, ..., *n*., G={1,...,*n*}
- Introduce *n* modal operators K*i*, 1  *i*  *n*.
- K*i*  is read “agent *i* knows that ”.
- EG , read as “everyone in group G knows that ”.
-        is the EG operator iterated *k* times.
- CG :   is common knowledge in group G.

## Fixed-point Approach

- View  CG   as a fixed-point of the function
*	**	**f*(*x*) = EG(  *x*).
- Specifically (derivable in augmented S5),
- 		CG   EG (  CG )

## Shared Situation Approach

- Assume that A and B are rational.
- We may infer common knowledge among A and B that  if
- A and B know that some situation  holds.
-  indicates to both A and B that both A and B know that  holds.
-  indicates to both A and B that .

## Barwise on the Three Approaches

- Barwise contrasts the 3 approaches within his situation theory.
- An *infon* is an (*n*+1)-tuple of a relation and *n* (*minor*) *constituents*.
- Its polarity is 1 if the minor constituents are related as per the relation.
- A set of infons is a *situation* (small world).
- An infon with polarity 1 is a “fact” (of some situation, not others).

## Minor constituents may be situations, even one where the infon itself occurs.
Example
	H, pi, 3 		player i has the 3 of clubs
	S, pi, s 		player i sees situation s
	s = {H, p1, 3, S, p1, s, S, p2, s}
	situation where player 1 has the 3 of hearts and this is publicly perceived by both player 1 and player 2 

- Example
- 	*H*, *p**i*, 3 		player *i* has the 3 of clubs
- 	*S*, *p**i*, *s* 		player *i* sees situation s
- 	*s* = {*H*, *p**1*, 3, *S*, *p**1*, *s*, *S*, *p**2*, *s*}
- 	situation where player 1 has the 3 of hearts and this is publicly perceived by both player 1 and player 2

## Define classes INFON (of infons) and SIT of (situations) by mutual induction.
Consider the fixed-points of a monotone increasing operator  corresponding to this inductive definition.
If a standard set theory (e.g., ZFC) is used as the metatheory, there’s a unique fixed-point.
But Barwise considers a variant of ZFC giving multiple fixed-points

- Consider the fixed-points of a monotone increasing operator  corresponding to this inductive definition.
- If a standard set theory (e.g., ZFC) is used as the metatheory, there’s a unique fixed-point.
- But Barwise considers a variant of ZFC giving multiple fixed-points

## Two intuitions about sets:
I1.  Sets are collections got by collecting together things already at hand to get something new (a set).
I2.  Sets arise from independently given structured situations by dropping the structure—“forgetful situations.”
I1 generates the cumulative hierarchy characteristic of, e.g., ZFC.
I2 gives a richer universe of sets.

**I1**.  Sets are collections got by collecting together things already at hand to get something new (a set).
**I2**.  Sets arise from independently given structured situations by dropping the structure—“forgetful situations.”
**I1** generates the cumulative hierarchy characteristic of, e.g., ZFC.
**I2** gives a richer universe of sets.

## b  s:  b is a constituent of situation s (a minor constituent of some infon in it).
Reality is wellfounded iff every situation is wellfounded.
A situation is wellfounded iff it’s neither circular nor ungroundable.
Situation s is circular if  s  ...  s. 
s is ungroundable if there’s an infinite sequence
		...  s  s  s 

- Reality is wellfounded iff every situation is wellfounded.
- A situation is *wellfounded* iff it’s neither circular nor ungroundable.
- Situation *s* is *circular* if  *s*  ...  *s*.
*s* is *ungroundable* if there’s an infinite sequence
- 		...  *s*  *s*  *s*

## These notions also apply to sets.
The Axiom of Foundation of ZFC:
A set contains no infinitely decreasing membership sequence.
Rules out circular and ungroundable sets.
Barwise proves:
  The universe of sets is wellfounded iff the universe of situations is.
So we must replace the Axiom of Foundation of ZFC with something that
admits non-wellfounded sets and
supports unique construction of sets.

- The Axiom of Foundation of ZFC:
- A set contains no infinitely decreasing membership sequence.
- Rules out circular and ungroundable sets.
- Barwise proves:
-   The universe of sets is wellfounded iff the universe of situations is.
- So we must replace the Axiom of Foundation of ZFC with something that
- admits non-wellfounded sets and
- supports unique construction of sets.

## Take Aczel’s Anti-Foundation Axiom, AFA.
When this replaces the Axiom of Foundation in ZFC, get ZFC/AFA set theory.
A tagged graph is a directed graph where each node without children is tagged with an atom or .
A decoration for a tagged graph is a recursive function  mapping a node x to a set.
If x is childless, then (x) is its tag.
Otherwise (x) = {(y) : y is a child of x}. 
A tagged graph G is wellfounded if the child-of relation on G is wellfounded (no circular or infinite directed paths).

- When this replaces the Axiom of Foundation in ZFC, get ZFC/AFA set theory.
- A *tagged graph* is a directed graph where each node without children is tagged with an atom or .
- A *decoration* for a tagged graph is a recursive function  mapping a node *x* to a set.
- If *x* is childless, then (*x*) is its tag.
- Otherwise (*x*) = {(*y*) : *y* is a child of *x*}.
- A tagged graph G is *wellfounded* if the *child-of* relation on G is wellfounded (no circular or infinite directed paths).

## Without AFA, can prove that every wellfounded tagged graph has a unique decoration in the universe of sets.
AFA asserts that every tagged graph has a unique decoration.

- AFA asserts that _every_ tagged graph has a unique decoration.

## With ZFC/AFA as our metatheory, there are many fixed-points of .
Least fixed-point gives collection of wellfounded infons and situations.
Interested in greatest fixed-point.
Includes all the non-wellfounded infons and situations as well.

- Least fixed-point gives collection of wellfounded infons and situations.
- Interested in greatest fixed-point.
- Includes all the non-wellfounded infons and situations as well.

## Want to compare iterate and fixed-point approaches.
Show how infon  gives rise to an transfinite sequence of wellfounded infons ,  a finite or infinite ordinal.
Requires a sequence s for any situation as well.
These are sequences of approximations.
Members of a sequence approximating a non-wellfounded situation have increasingly deep nestings.
Corresponds to increasingly deep nestings of “everyone knows that” operator.

- Show how infon  gives rise to an transfinite sequence of wellfounded infons ,  a finite or infinite ordinal.
- Requires a sequence *s* for any situation as well.
- These are sequences of approximations.
- Members of a sequence approximating a non-wellfounded situation have increasingly deep nestings.
- Corresponds to increasingly deep nestings of “everyone knows that” operator.

## For circular infon , approximations get ever stronger but never as strong as .
Yet the totality of all approximations captures .
If each  holds in a situation, so does .
The finite approximations of a circular infon are equivalent to it w.r.t. finite situations.
But this doesn’t hold for infinite situations.
In this sense, iterate approach is weaker than fixed-point approach.

- Yet the totality of all approximations captures .
- If each  holds in a situation, so does .
- The finite approximations of a circular infon are equivalent to it w.r.t. finite situations.
- But this doesn’t hold for infinite situations.
- In this sense, iterate approach is weaker than fixed-point approach.

## In shared-situation approach, characterize common knowledge in terms of existence of a real situation meeting a certain condition.
Introduce a second-order language to express the existential conditions.
Variables range over situations, may be bound by existential quantifiers.
Semantics stated in terms of assignment of situations to free situation variables in a condition.
A model for a condition is an assignment making it true.

- Introduce a second-order language to express the existential conditions.
- Variables range over situations, may be bound by existential quantifiers.
- Semantics stated in terms of assignment of situations to free situation variables in a condition.
- A *model* for a condition is an assignment making it true.

## Two conditions with the same free variables are strongly equivalent if they have the same models.
A condition entails a sequence of infons
     if that sequence is a list of facts, each holding in the situation assigned to a given variable in any assignment satisfying the condition.
Two conditions with the same free variables are informationally equivalent if they entail the same sequences of infons.
A model M of a condition  is a minimal model of 
    if each situation in M has no more information than the corresponding situation in any other model of .
A condition generally has several minimal models.

- A condition *entails* a sequence of infons
-      if that sequence is a list of facts, each holding in the situation assigned to a given variable in any assignment satisfying the condition.
- Two conditions with the same free variables are *informationally equivalent* if they entail the same sequences of infons.
- A model *M* of a condition  is a *minimal model* of 
-     if each situation in *M* has no more information than the corresponding situation in any other model of .
- A condition generally has several minimal models.

## Can be shown that 2 conditions are informationally equivalent iff they have a minimal model in common.
So, suppose we start with shared-situation approach, formulating a condition.
Situations in a minimal model of this condition give a handle for fixed-point approach.
But 2 conditions can be informationally equivalent and not strongly equivalent.
Conditions are more discriminating than the situations that are their minimal models.
2 conditions may be different but equally correct ways a group comes to have shared information.

- So, suppose we start with shared-situation approach, formulating a condition.
- Situations in a minimal model of this condition give a handle for fixed-point approach.
- But 2 conditions can be informationally equivalent and not strongly equivalent.
- Conditions are more discriminating than the situations that are their minimal models.
- 2 conditions may be different but equally correct ways a group comes to have shared information.

## Barwise’s Conclusions

- Fixed-point approach is correct analysis of common knowledge.
- Common knowledge generally arises via shared situations.
- Iterate approach characterizes how common knowledge is used?
- Progress through sequence of approximations corresponds to inferring ever deeper nestings of “everyone knows that”?
- But doubt about a given inference blocks next step.

## Knowing that  is stronger than carrying the info that .
Involves carrying the info in a way relating to ability to act.
Possible-worlds semantics of standard epistemic logic requires we know all logical consequences of what we know.

- Involves carrying the info in a way relating to ability to act.
- Possible-worlds semantics of standard epistemic logic requires we know all logical consequences of what we know.

## Common knowledge (per fixed-point approach) is a necessary but not sufficient condition for action.
Useful only when arising in a straightforward shared situation.
A situation works not just by giving rise to common knowledge.
It also “provides a stage for maintaining common knowledge through the maintenance of a shared situation.”
The shared interface of our system is a common artifact in Devlin’s sense.

- Useful only when arising in a straightforward shared situation.
- A situation works not just by giving rise to common knowledge.
- It also “provides a stage for maintaining common knowledge through the maintenance of a shared situation.”
- The shared interface of our system is a *common artifact* in Devlin’s sense.

## Common Knowledge and Simultaneous Action

- Agents *A* and *B* communicate over a channel.
- It’s common knowledge that
- delivery of a message is guaranteed and
- a message *A* sends to *B* arrives either immediately or after  time units.
- At time *m**S*, *A* sends *B* a message  that doesn’t specify the sending time.
- Let
*m**D* denote the message arrival time and
*sent*() the proposition that  has been sent.

## KB sent() is true at mD.  
But A can’t be sure that KB sent() before mS+. 
So KA KB sent() isn’t true until mS+. 
And B knows this.  
But  may have been delivered immediately.
So B doesn't know that mS+ time has elapsed until mD+.  
So KB KA KB sent() doesn’t hold until mD+.
And A knows this. 
But it may take  time for  to be delivered.
So mD could (for all A knows) be mS+.  
So KA KB KA KB sent() does not hold until mS+2. 

- But *A* can’t be sure that K*B* *sent*() before *m**S*+.
- So K*A* K*B* *sent*() isn’t true until *m**S*+.
- And *B* knows this.
- But  may have been delivered immediately.
- So *B* doesn't know that *m**S*+ time has elapsed until *m**D*+.
- So K*B* K*A* K*B* *sent*() doesn’t hold until *m**D*+.
- And *A* knows this.
- But it may take  time for  to be delivered.
- So *m**D* could (for all *A* knows) be *m**S*+.
- So K*A* K*B* K*A* K*B* *sent*() does not hold until *m**S*+2.

## mS

- mS

- mS+ 

- mS+ 2

- mS+ 3

- mD

- mD+ 

- mD+ 2

- mS

- mS+ 

- mS+ 2

- mS+ 3

- mD

- mD+ 

- mD+ 2

- mD+ 3

- 

- 

## A straightforward induction shows that, for any natural number k, 
before mS+k, (KA KB)k sent() doesn’t hold, while 
at mS+k it does.  
Common knowledge requires infinitely deep nesting of KA KB. 
So common knowledge of sent() is never attained no matter how small . 

- before *m**S*+k, (K*A* K*B*)*k* *sent*() doesn’t hold, while
- at *m**S*+*k* it does.
- Common knowledge requires infinitely deep nesting of K*A* K*B*.
- So common knowledge of *sent*() is never attained no matter how small .

## But suppose that 
A attaches the sending time mS to , giving message , and 
A and B use the same global clock . 
When B receives , he knows it was sent at mS. 
Because of the global clock, it is common knowledge at time mS+ that it is mS+. 
Since it is also common knowledge that a message received at mS+ was sent at mS, 
		CG sent(), G = {A, B}, 
	holds at mS+.  

*A* attaches the sending time *m**S* to , giving message , and
*A* and *B* use the same global clock .
- When *B* receives , he knows it was sent at *m**S*.
- Because of the global clock, it is common knowledge at time *m**S*+ that it is *m**S*+.
- Since it is also common knowledge that a message received at *m**S*+ was sent at *m**S*,
- 		CG sent(), *G* = {*A*, *B*},
- 	holds at *mS*+.

## Can model the global clock is with another agent.
An action by any other agent is always simultaneous with one of this agent’s actions (a “tick”). 
More parsimoniously: 
Require that an agent have a different state at each point in a run. 
It always knows what time it is. 

- An action by any other agent is always simultaneous with one of this agent’s actions (a “tick”).
- More parsimoniously:
- Require that an agent have a different state at each point in a run.
- It always knows what time it is.

## A thesis of standard epistemic logic 
		CG   EG CG .
So the transition 
from  not being common knowledge 
to it being common knowledge 
    must involve simultaneous changes in the knowledge of all agents in the group.  
I.e., information becomes shared in the required sense at the same time for all agents sharing it.
No surprise—all the agents are involved in the circularity. 

- 		C*G*   E*G* C*G* .
- So the transition
- from  not being common knowledge
- to it being common knowledge
-     must involve simultaneous changes in the knowledge of all agents in the group.
- I.e., information becomes shared in the required sense at the same time for all agents sharing it.
- No surprise—all the agents are involved in the circularity.

## Common Knowledge Inherent in Agreement and Coordination 

- Suppose that *A* and *B* agree to something .
- For there to be an agreement, every party in group *G* = {*A*, *B*} must know there’s agreement:
*	**	**agree**G*() E*G* *agree*()		(**)
- By idempotence of , this is equivalent to
*	**	**agree**G*() E*G* (*agree**G*()  *agree**G*())
- But standard epistemic logic includes the inference rule
- 		From 1  E*G* (2  1) infer C*G* 2
- Substituting *agree**G*() for both 1 and 2 in the rule and using (**) for the premise, we infer
*	**	**agree**G*() C*G* *agree*()

## To show formally that coordination implies common knowledge requires extensive development.
But the result is just as direct. 

- But the result is just as direct.

## Process Algebras and Handshakes

- The standard epistemic-logic framework explicates the notion of simultaneous actions.
- But the notion it provides of a joint action preformed by *n* agents is simply:
- an (*n*+1)-tuple whose components are the simultaneous actions of the environment and the n agents.
- One thing critical to a joint action is:
- the agents must time their contributions so that each contributes only when all are prepared.

## A handshake in process algebras is a joint communication action that happens only when both parties are prepared for it.  
A process algebra (e.g., -calculus, CCS, CSP) is a term algebra.
Terms denote processes. 
Combinators apply to processes to form more complex processes. 
Combinators typically include
alternative and parallel composition and 
a prefix combinator that forms a process from a given process and a name. 

- A process algebra (e.g., -calculus, CCS, CSP) is a term algebra.
- Terms denote processes.
- Combinators apply to processes to form more complex processes.
- Combinators typically include
- alternative and parallel composition and
- a prefix combinator that forms a process from a given process and a name.

## Names come in complementary pairs.
A prefix offers a handshake.
A handshake results in an action identified by the prefix of the selected alternative.
Resulting process consists of only the selected alternative with its prefix removed. 
Parallel processes may handshake if they have alternatives with complementary prefixes. 
Only way a process can evolve is as result of handshakes.  

- A prefix offers a handshake.
- A handshake results in an action identified by the prefix of the selected alternative.
- Resulting process consists of only the selected alternative with its prefix removed.
- Parallel processes may handshake if they have alternatives with complementary prefixes.
- Only way a process can evolve is as result of handshakes.

## Handshakes between parallel components can happen only when they have evolved to have alternatives beginning with complementary prefixes.
In this sense, they can handshake only when both are prepared. 
Handshakes synchronize the behavior of components
They thereby coordinate behavior. 
Handshakes are like speech acts.
Contemporary analysis of face-to-face conversation emphasizes the active role of addressees (e.g., nods).

- In this sense, they can handshake only when both are prepared.
- Handshakes synchronize the behavior of components
- They thereby coordinate behavior.
- Handshakes are like speech acts.
- Contemporary analysis of face-to-face conversation emphasizes the active role of addressees (e.g., nods).

## Process-Algebraic Agent Abstraction

- Some of the combinators (and their syntactic patterns) persist through transitions—
- e.g., parallel composition and restriction (or hiding) combinators.
- Other combinators (e.g., alternative composition and prefix) don't thus persist.
-  Processes corresponding to agents persist through transitions.
- So a a multiagent system from is
- a parallel composition.
- Each component models an agent and involves a recursively defined process identifier.

## This view of agents is simpler than that of standard epistemic logic. 
Handshakes are primitives, so no need for assumptions about agents’ states or a global clock to support joint actions. 
State of an agent given simply by the current form of the term denoting it.
A process algebra is more concrete than epistemic logic.
 A logic lets us assert abstract properties of an agent or system of agents.
Using a process algebra, we specify the behavior of agents. 

- Handshakes are primitives, so no need for assumptions about agents’ states or a global clock to support joint actions.
- State of an agent given simply by the current form of the term denoting it.
- A process algebra is more concrete than epistemic logic.
-  A logic lets us assert abstract properties of an agent or system of agents.
- Using a process algebra, we specify the behavior of agents.

## What’s Missing in the Process-Algebraic Agent Abstraction

- Tempting to view process-algebraic terms as possible plans an agent or a person may undertake.
- But the notion that humans execute predefined plans in interacting with technology or with each other has been heavily criticized by ethnomethodologists.
- Emphasize how situated behavior is determined in an ongoing way.

## Certain speech acts occur only to establish common knowledge.
Nearly all contributions in a conversation advance our common knowledge.
So what future actions might be appropriate is determined as a joint project unfolds. 
And patterns of joint communication actions have nothing to say about behavior that deviates from them. 

- Nearly all contributions in a conversation advance our common knowledge.
- So what future actions might be appropriate is determined as a joint project unfolds.
- And patterns of joint communication actions have nothing to say about behavior that deviates from them.

## What was missing in our agent abstraction was the persisting effects of speech acts. 
Within a conversation speech acts can establish common knowledge. 
Also, certain speech acts have deontic effects, such as obligations, prohibitions, and permissions. 

- Within a conversation speech acts can establish common knowledge.
- Also, certain speech acts have *deontic* effects, such as obligations, prohibitions, and permissions.

## Deontic Logic

- Modal operators of standard deontic logic:
- O ,  “ is obligatory”,
- P ,  “ is permitted”, and
- F ,  “ is forbidden (or prohibited)”.
- P    O     F 
- Development driven by certain paradoxes that arise when there’s a conflict between
- the logical status (valid, satisfiable, etc.) of a deontic-logic formula and
- the intuitive understanding of the natural-language reading of the formula.

## Dyadic deontic logic—e.g.,
O   “Given , it is obligatory that .”
Special obligations, permissions, and prohibitions—e.g.,
OA   “It is obligatory for A that .” 
Directed obligations, etc.—e.g.,
OA,B    “A is obligated to B that .” 
Deontic operators derived from operators that make action explicit—e.g.,
A sees to it that  
operators of dynamic logic.

- O   “Given , it is obligatory that .”
*Special* obligations, permissions, and prohibitions—e.g.,
- OA   “It is obligatory for A that .”
- Directed obligations, etc.—e.g.,
- OA,B    “A is obligated to B that .”
- Deontic operators derived from operators that make action explicit—e.g.,
- A sees to it that 
- operators of dynamic logic.

## Deontic notions are appropriate whenever we distinguish between
what is ideal (obligatory) and 
what is actual. 
Reject  O     as a thesis.
Obligation may be violated.

- what is ideal (obligatory) and
- what is actual.
- Reject  O     as a thesis.
- Obligation may be violated.

## Some application areas of computer science:
formal specification 
Modern software is so complex, we must cover non-ideal cases too in specifications. 
fault tolerance
Non-ideal behavior introduces obligations to correct the situation.
database integrity constraints—distinguish between
deontic constraints: may be violated
necessity constraints: largely analytically true. 

- formal specification
- Modern software is so complex, we must cover non-ideal cases too in specifications.
- fault tolerance
- Non-ideal behavior introduces obligations to correct the situation.
- database integrity constraints—distinguish between
- deontic constraints: may be violated
- necessity constraints: largely analytically true.

## Co-presence Heuristics

- Clack and Carlson: people ordinarily rely on special kinds of evidence to which the shared-situation induction scheme is applied.
- Co-presence heuristics:
- Physical co-presence (*cf*. Chwe)
- Object is located between agents A and B.
- Both A and B see the object and each other simultaneously.
- Gives evidence of the “triple co-presence” of A, B, and the object of common knowledge.

## Slide 52

## Linguistic co-presence
Triple co-presence of A, B, and the linguistic positing of the object of common knowledge
Community membership
If A finds that B is in the same community as A, 
    then A can conclude that B must have common knowledge shared by that community.
The other 2 heuristics presuppose this one. 

- Triple co-presence of A, B, and the linguistic positing of the object of common knowledge
- Community membership
- If A finds that B is in the same community as A,
-     then A can conclude that B must have common knowledge shared by that community.
- The other 2 heuristics presuppose this one.

## Physical Co-presence

- Apply the physical co-presence heuristic so that groups of agents may attain common knowledge perceptually.
- Agents must model each others’ perception—requires
- shared perceptual abilities and
- common knowledge of these abilities.
- A standard design would have
- rules for classifying perceived objects (including other agents) and
- rules for constructing perceptual models of other agents.

## Implemented a prototype, coupled with a back propagation neural network.
Agent behavior adapted to trainer’s feedback.
Captured “hidden knowledge” not captured by knowledge engineer.

- Agent behavior adapted to trainer’s feedback.
- Captured “hidden knowledge” not captured by knowledge engineer.

## Grounding

- Clark emphasizes the “common ground” in face-to-face conversation.
- “Grounding” has become a major topic in human-computer dialog.
- Two-phase communication: presentation, acceptance.
- Grounding criterion: threshold at which evidence for common knowledge is deemed sufficient.
- Diagram (e.g., human-computer) conversations.
- Brennan: emphasize private models to avoid inconsistencies in a diagram.
- But omits what’s critical: shared situation

## Back to the Simple Distributed Game

- An agreement is sealed with a handshake in which all players take part.
- This joint action establishes the required common knowledge.
- The itineraries record obligations.

## For implementing a handshake mechanism: 
each player must be able independently to initiate his contribution (this is being prepared), and 
there must be feedback indicating to all that all have initiated he contributions and persisted with them. 
In our implementation, a player 
moves the mouse cursor over a designated area and 
holds down the left mouse button.  
If all players participate, the suggestion is displayed in the updated display of the itinerary. 

- each player must be able independently to initiate his contribution (this is being prepared), and
- there must be feedback indicating to all that all have initiated he contributions and persisted with them.
- In our implementation, a player
- moves the mouse cursor over a designated area and
- holds down the left mouse button.
- If all players participate, the suggestion is displayed in the updated display of the itinerary.

## Ways a player may disagree:
By simply not participating in the handshake. 
Then the opportunity times out.
By offering a counter-suggestion.  
Done in the same way as the original suggestion.
But done by a player during the turn of the player who made the original suggestion. 

- By simply not participating in the handshake.
- Then the opportunity times out.
- By offering a counter-suggestion.
- Done in the same way as the original suggestion.
- But done by a player during the turn of the player who made the original suggestion.

## Virtual Agents (Clark)

- Clark is concerned with how we communicate with virtual partners—e.g.,
- the person speaking to me in the letter
- the person giving me directions via a cook book
*Disembodied language*: not produced by an actual speaker at the moment it’s interpreted.
- Two main forms:
- written language
- mechanized speech (e.g., films, telephone messages)

## Disembodied language is a representation of embodied language.
We’re intended to imagine the embodied language it represents.
Salient features:
Virtual speaker
Producer: the person/institution ultimately responsible for the disembodied language
Virtual time
Pacing

- We’re intended to imagine the embodied language it represents.
- Salient features:
- Virtual speaker
- Producer: the person/institution ultimately responsible for the disembodied language
- Virtual time
- Pacing

## Many joint activities divide into layers of joint actions.
what is actually happening—a pretense
the pretense itself
Two things needed for successful layering
Credible characters
Props

- what is actually happening—a pretense
- the pretense itself
- Two things needed for successful layering
- Credible characters
- Props

## When we interpret any form of communication with a computer, we communicate with virtual agents.
Reeves and Nass, The Media Equation
People equate media and real life.
This “is very common, it is easy to foster, it does not depend on fancy equipment, and thinking will not make it go away.”

- Reeves and Nass, *The Media Equation*
- People equate media and real life.
- This “is very common, it is easy to foster, it does not depend on fancy equipment, and thinking will not make it go away.”

## Our proxy agents are virtual agents?
But the language (clicking fields) is produced by the player at the moment it’s interpreted.
The 2 layers intermingle.
Equally natural to say
the proxy agent moves
the player moves the proxy agent
Likewise for obligations.

- But the language (clicking fields) _is_ produced by the player at the moment it’s interpreted.
- The 2 layers intermingle.
- Equally natural to say
- the proxy agent moves
- the player moves the proxy agent
- Likewise for obligations.

## But common knowledge?
The activities in our game can be automated (some easily)
No way to tell whether we’re communicating with a person or agent behind the proxy agent.
And no way to tell whether there’s one person controlling two proxy agents.

- The activities in our game can be automated (some easily)
- No way to tell whether we’re communicating with a person or agent behind the proxy agent.
- And no way to tell whether there’s one person controlling two proxy agents.

## Conclusion

- Insights from formal modeling into coordination.
- Started with a simple distributed cooperative game.
- Agreements, presupposing common knowledge.
- Formal characterization of common knowledge.
- Iterate, fix-point, and shared-situation approaches.
- New common knowledge and simultaneous actions.
- Handshakes—joint actions
- Process-algebraic agent abstraction
- Also need epistemic and deontic effects.

## Co-presence heuristics for common knowledge
Grounding
Back to coordination game
Virtual agents and disembodied language

- Grounding
- Back to coordination game
- Virtual agents and disembodied language

## Need conventions to escape dependence on simultaneous actions.
Cf. disembodied language
In CS, we have languages and protocols.
Agent communication in the first instance (conceptually) is synchronous.
Need appropriate support for asynchronous communication.
Need the appropriate “language game.”

*Cf*. disembodied language
- In CS, we have languages and protocols.
- Agent communication in the first instance (conceptually) is synchronous.
- Need appropriate support for asynchronous communication.
- Need the appropriate “language game.”

## Agent software development
Specification
Modal logics, concepts of common knowledge and obligations, etc.
Design
Process algebras (or something at comparable level of abstraction)
Implementation
Appropriate communication primitives, including transactional features

- Specification
- Modal logics, concepts of common knowledge and obligations, etc.
- Design
- Process algebras (or something at comparable level of abstraction)
- Implementation
- Appropriate communication primitives, including transactional features

## Future WorkCoordination Game

- Agents with path-planning and negotiation abilities
- Automated aids for players (e.g., measure distances)
- Implementing counters allows operational definitions of
- Fairness
- When several players want to make a counter-suggestion at the same time, who gets the floor?
- Linear combination of inverses of counters gives priorities.
- Trustworthiness
- Don’t enforce obligations, but can count violations

## Formal

- General obligations and some special obligations (roles) should be common knowledge.
- Multi-modal logic
- Relation between process algebras and modal logics
*Cf*. Hennessey-Milner logics

## Conceptual

- A lot packed into the notions of _situation_, _situated_.
- Also _environment_, _information_ in the _environment_
- _Not_ *amount* of information
- Important for ubiquitous and embedded computing.
- _Joint action_, _joint activity_
- Relate to distributed, extended transactions