Interacting agents processing information

 
 


We are interested in the (pairwise) links between computational complexity, game theory, learning theory and logics of information dynamics, e.g. learning theory in its interrelation with dynamic epistemic logic and game theory. Our perspective is to a large extent a mixture of computational complexity theory and cognitive science: we assume that agents are bounded in their computational powers and ask how difficult epistemic processes are from an agent's internal perspective. In other words, we search for a procedural angle which will help to better understand cognitive aspects of these theories. There are several possible outputs of such an endeavor, e.g., we can merge logical frameworks, evaluate and revise existing theories according to their tractability, or plan empirical experiments confronting theories with cognitive reality. We invite all interested MoL students to join us in this project.



 

cognition and interaction: mathematical models

fields covered

computational complexity theory

game theory

learning theory

dynamic logics of information

teaching

Cédric Dégremont

fistname.uva at gmail.com

Nina Gierasimczuk

firstname.lastname at gmail.com

Lena Kurzen

firstname.lastname at gmail.com

Jakub Szymanik

firstname.lastname at gmail.com



 


LOGIC ORIENTED PAPERS


    * Complexity and DEL


   1. Johan van Benthem and Eric Pacuit - The Tree of Knowledge in Action: Towards a Common Perspective, Advances in Modal Logic 2006: 87-10

   2. Carsten Lutz - Complexity and Succinctness of Public Announcement Logic, LTCS-Report 05-09, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, Germany, 2005.


    * DEL and Games


   1. Alexandru Baltag, Sonja Smets and Jonathan Zvesper - When all is done but not (yet) said: Dynamic rationality in extensive games, (submitted)

   2. Oliver Board - Dynamic interactive epistemology, Games and Economic Behavior 49 (2004), 49-80 (excluding the appendix)




(BEHAVORIAL) ECONOMICS ORIENTED PAPERS


    * Learning and Games


   1. Yin-Wong Cheung and Daniel Friedman - Individual Learning in Normal Form Games: Some Laboratory Results, Games and Economic Behavior, 19 (1997), 46-76 (section 1 and 2 only)



    * Higher-order reasoning and games


   1. Roberto A. Weber - Behavior and learning in the "Dirty Faces" game, Experimental Economics 4-3 (2001), 229-242

   2. Ariel Rubinstein - The Electronic Mail Game: Strategic Behavior under "Almost Common Knowledge, American Economic Review 79-3 (1989), 385-91



    * Cognitive science and Economics


   1. Herbert A. Simon - A Behavioral Model of Rational Choice, The Quarterly Journal of Economics 69-1 (1955), 99-118.




GAMES AND COMPLEXITY PAPERS


    * (Complexity of) Combinatorial Games


   1.     Eric Demaine and Robert Hearn - Playing Games with Algorithms: Algorithmic Combinatorial Game Theory, in Games of No Chance III, to appear.



    * (Complexity of) Imperfect Information Games


   1.     Daphne Koller and Avi Pfeffer - Generating and solving imperfect information games, in Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995, 1185-1192





COGNITIVE SCIENCE ORIENTED PAPERS


    * What is tractable for bounded agents


   1. Marcello Frixione - Tractable competence, Minds and Machines 11 (2001), 379-397

   2. Iris van Rooij - The Tractable Cognition thesis, Cognitive Science, 32 (2008), 939-984.



    * Tractability and resoning


   1. Hector Levesque - Logic and the complexity of reasoning, JPL 17:4 (1988), 355-389



    * Learning as intractable problem


   1. Peter Kugel - Thinking may be more than computing, Cognition 22 (1986), 137-198



    * Applications


   1. John Tsotsos - Analyzing vision at the complexity level, Behavioral and brain sciences 13 (1990), 423-469.




indicative list of papers

Background handbooks:


* van Ditmarsch, H., van der Hoek, W., Kooi, B.: Dynamic Epistemic Logic. Springer (2007)

* Jain, S., Osherson, D., Royer, J.S., Sharma, A.: Systems that Learn. MIT Press, Chicago (1999)

  1. *Osborne, M. J., Rubinstein, A.: A Course in Game Theory. MIT Press (1994)

  2. *Papadimitriou, C. H.: Computation Complexity. Addison-Welsey (1994)
 

week 1

  1. •Tutorials in relevant topics

week 2

  1. •Students present papers from the literature

week 3

  1. • Students present a research project

February 1st

  1. •Students hand in a short paper based on their research project


 

Paper selected by Ido

Daphne Koller and Avi Pfeffer - Generating and solving imperfect information games, in Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995, 1185-1192