13 November 2009, Computational Social Choice Seminar, Eric Pacuit

Abstract

A state of knowledge (or belief) of some fact P in a multiagent situation is a description of the agents' first-order and higher-order information about P. At one extreme all agents may be completely unaware of P (and whether the other agents have any information about P). The other extreme is when there is common knowledge of P. It is natural to represent such a state as a set of finite strings over the finite alphabet consisting of a knowledge (belief) operator for each agent. A natural question is how many different (consistent) levels of knowledge are there? Parikh and Krasucki show that there are only countably many different states of knowledge. However, Hart, Heifetz and Samet prove that there are uncountably many different states of knowledge. In this talk, we will explain these apparently contradictory results (of course, there is no contradiction as the results use different definitions of a "state of knowledge" ) and their significance for modeling knowledge in a game-theoretic situation. Time permitting, we will discuss similar types of results by Ron Fagin on "quantitative aspects" of modal logic.

References:
1. R. Fagin, A Quantitative Analysis of Modal Logic, Journal of Symbolic Logic 59:209-252 (1994).
2. S. Hart, A. Heifetz and D. Samet, "Knowing Whether," "Knowing That," and the Cardinality of State Spaces, Journal of Economic Theory 70:249-256 (1996).
3. R. Parikh, Levels of Knowldge, Games and Group Action, Research in Economics 57:267-281 (2003).
4. R. Parikh and P. Krasucki, Levels of Knowledge in Distributed Systems, Sadhana 17:16 -191 (1992).

For more information, see http://www.illc.uva.nl/~ulle/seminar/, or contact Ulle Endriss (ulle at illc.uva.nl).