#### References for 

**"Common Knowledge and Handshakes in Computer-Mediated Cooperation"**

Oak Ridge National Laboratory

### Friday, June 11, 2004

### **Albert Esterline**

> Dept. of Computer Science, North Carolina A&T State University
>
> esterlin@ncat.edu

I arranged the references by topics. Each reference is commented.

# Work by Barwise

Barwise, Jon. *The Situation in Logic*. Stanford, CA: CSLI (Center for
the Study of Language and Information) , 1989. Distributed by The
Chicago University Press.

> Chapter 8, "Situations, Sets and the Axiom of Foundation" (originally
> appeared in *Studies in Logic: Logic Colloquium '84*, Elsevier Sci.
> Pub., 1984), presents Aczel's antifoundation axiom and uses it as part
> of an axiomatic foundation for situation theory.
>
> Chapter 9, "On the Model Theory of Common Knowledge" (containing
> results originally announced in "Three Views of Common Knowledge," in
> *Theoretical Aspects of Reasoning About Knowledge II*. Menlo Park, CA:
> Morgan Kaufmann, 1988) presents the three approaches to common
> knowledge.

## Common Knowledge in Computer Science

Fagin, R., Halpern, J.Y., Vardi, M.Y., and Moses, Y. *Reasoning about
Knowledge*. Cambridge, MA: The MIT Press, 1995.

This is the classical presentation of epistemic logic, including
especially common knowledge, from the computer-science point of view.
This includes the results on the difficulty in attaining new common
knowledge and the logical dependence of agreement and coordination on
common knowledge.

## Process Algebras

Milner, R. *Concurrency and Communication***.** Prentice-Hall
International Computer Science Series, 1989.

> This is the classical presentation of the process algebra CCS.

Roscoe, Bill. *The Theory and Practice of Concurrency*. Prentice Hall,
1998.

This is the most current (as far as I know) extensive treatment of CSP.

Milner, R. *Communicating and Mobile Systems: the Pi-Calculus*.
Cambridge University Press, 1999.

This is probably the easiest introduction to the -calculus, which
generalizes CCS by allowing links (channel names) to be passed as values
in handshakes. This allows one to model changing communication structure
("mobility"). It is shown that the -calculus has the expressive power of
higher-order calculi, where processes themselves can be communicated.
Indeed, it's shown how the lazy -calculus can be simulated with the
-calculus, which thus provides a universal model for computation.

## Work by H.H. Clark and Friends

Clark, H.H. *Using Language*. Cambridge University Press, 1996.

This has a thorough presentation of Clark's notion of common ground,
which includes common knowledge in face-to-face conversation. The point
of departure is speech-act theory influenced by conversation analysis
(allied with ethnomethodology), which is concerned with the addressees,
not just the speaker. Agent communication languages generally start with
speech-act theory but don't consider issues that are critical to Clark's
work.

Clark, H.H., and Carlson T.B., "Speech Acts and Hearers' Beliefs", in
Smith, N. V. (ed.), *Mutual Knowledge*. N.Y.: Academic Press, 1982, pp.
1-37.

This presents three "co-presence heuristics" for establishing common
knowledge (which the authors call mutual belief): physical, linguistic,
and cultural co-presence. These all take Barwise's shared-situation
approach to common knowledge (having taken the notion from Lewis, whose
approach is discussed by Barwise). This is good on how humans actually
attain new common knowledge.

Clark, H.H. "How do Real People Communicate with Virtual Partners?" In
S.E. Brennan, A. Giboin, and D. Traum (Cochairs), *Psychological Models
of Communication in Collaborative Systems* (Papers from the 1999 AAAI
Fall Symposium). Menlo Park, CA: AAAI Press, 1999.

This presents the notion of a virtual agent.

Cahn, J.E. and Brennan, S.E. "A Psychological Model of Grounding and
Repair in Dialog." In S.E. Brennan, A. Giboin, and D. Traum (Cochairs),
*Psychological Models of Communication in Collaborative Systems* (Papers
from the 1999 AAAI Fall Symposium). Menlo Park, CA: AAAI Press, 1999.

This is concerned with "grounding," how dialog partners establish a
common ground (in Clark's sense---Brennan was a student of Clark).
Conversations are analyzed with contribution graphs, showing the
presentation and acceptance contributions (possibly with embedded
clarifications and repairs) of the partners. This is first presented for
face-to-face human conversation then applied to HCI. Brennan is probably
the leading researcher on grounding. My point is that her approach,
focusing on converging mental states, ignores what's critical for common
knowledge, viz., a shared self-referential (cf. fixed point) situation.
Common knowledge can't be analyzed in terms of all participants having
mental states that are the same in relevant respects.

## Common Knowledge and Social Phenomena

Michael S.-Y. Chwe, *Rational Ritual: Culture, Coordination, and Common
Knowledge*. Princeton, NJ: Princeton University Press, 2001.

A short, clear, well-argued book with plenty of examples showing the
importance of common knowledge for social activity and the role of
ritual (broadly understood) in establishing common knowledge. Easy to
read. Chwe is a political scientist who has applied game theory to many
social phenomena. (Common knowledge is critical for game theory---but
this is a big topic on its own.)

## The Media Equation

Reeves, B. and Nass, C., *The Media Equation: How People Treat
Computers, Television, and New Media Like Real People and Places*, CSLI
Publications (Stanford Univ.), 1996.

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

## Criticisms of AI/CS Notion of Plan by Ethnomethodologists

Suchman, L.A., *Plans and Situated Actions: The Problem of Human-Machine
Communication*, New York: Cambridge University Press, 1987.

The classical work on technology-mediated situated action, blasting the
AI view of plans. This is in the tradition of
ethnomethodology/conversation analysis, although she doesn't make a big
point out of the tradition. Any attempt to see things represented in
some formalism as effective of action must come to terms with this
criticism. The main point is that steps are worked out "ongoingly" as
action proceeds, that plans are resources (e.g., for after-the-fact
justification or preliminary orientation) and are not effective of
action. Our response is to point out the role of epistemic (e.g., common
knowledge) and deontic (e.g., obligations) effects of speech acts, which
are modeled as handshakes in a process algebra.

Heath, C and Luff, P. *Technology in Action*. Cambridge, UK: Cambridge
Univ. Pr., 2000.

Some thorough and thoroughly discussed "workplace studies" in the
tradition of ethnomethodology/conversation analysis. Nice, clear
presentation of this tradition. A good complement to Suchman (although
not necessarily influenced by her, at least from the same tradition).

## Relevant Papers by Me and Friends

Esterline, A.C and Rorie, T. \"Using the -Calculus to Model Multiagent
Systems,\" in C. Rouff *et al*. (eds.), *Formal Approaches to
Agent-Based Systems*, Springer-Verlag, 2001

This presents our process-algebraic agent abstraction, with an example
thoroughly worked out in the -calculus.

Esterline, A.C., "Using Statecharts and Modal Logics to Model Multiagent
Plans and Transactions," in M. G. Hinchey *et al*. (eds.) *Formal
Approaches to Agent-Based Systems*, Berlin: Springer-Verlag, 2003, pp.
146-161.

This relates common knowledge and obligations (and other deontic
notions) to plans in multiagent systems and to extended transactions.

Esterline, A.C., Rorie, T., and Homaifar, A. "A Process-Algebraic Agent
Abstraction," chapter in a book on multiagent systems, edited by C.
Rouff, Springer-Verlag, in press.

This works out some of the implications of our process-algebraic agent
abstraction, including the relation to epistemic and deontic notions,
how plans (captured by process-algebraic terms) can be effective of
action, and the intentional stance.

Wiriyacoonkasem, S. and Esterline, A. "Heuristics for Inferring Common
Knowledge via Agents' Perceptions in Multiagent Systems," *The 5^th^
World Multi-Conference on Systemics, Cybernetics and Informatics*.
Orlando, FL, 2001.

> This considers Clark and Carlson's physical co-presence heuristic from
> the point of view of multiagent systems. This presents a technique for
> a finite unfolding of a physical co-presence situation to determine
> whether the situation supports common knowledge; it is restricted to
> the two-agent case. The MS thesis work this is based on also
> implemented a system to flag common-knowledge situations, with rules
> for classifying perceived objects (including other agents) and rules
> for constructing perceptual models of other agents; a neural net was
> used to capture hidden knowledge, not covered by the explicit rules.