Sieuwert van Otterloo

Publications

2005

• A Strategic Analysis of Multi-agent Protocols (PhD dissertation)
  Sieuwert van Otterloo - Amsterdam, 2005
  My PhD dissertation, successfully defended on November 25 2005
  The research goal behind this dissertation is to develop ways to compare and analyse multi-agent protocols. In order to do so one has to distinguish different types of protocols, and one has to distinguish different classes of properties. Protocols that can be modelled as imperfect information game forms are therefore discussed in the first part of this dissertation, whereas protocols that can be modeled as imperfect information are the subject of the second part. In both parts we define concepts that help us to analyse and understand protocols, demonstrate these concepts on example protocols, and investigate the computational properties of these concepts. [download PS(2 Mb)] [download PDF(1 Mb)]
• Reasoning about Extensive Games
  Sieuwert van Otterloo - Amsterdam, 2005
  accepted for ESSLLI 2005 student session (poster presentation)
  Extensive games of perfect information can be used as a model for multi agent decision making. For instance auctions and voting can be modeled as extensive games. An extension of modal logic called GLP- is defined that allows us to express whether each agent has the appropriate amount of influence in the decision making process. In this paper a complete axiom system for this logic is presented. [download PS(265 kb)] [download PDF(106 kb)]
• Verification of Voting Protocols
  Sieuwert van Otterloo, Olivier Roy- Amsterdam, 2005
  submitted
  Verification of strategic properties is complicated, even for very small protocols. In this work we look at voting protocols that allow three agents to vote over three alternatives, and investigate what properties of those protocols can be expressed in different logics. We first verify some basic requirements using a logic of coalition powers. Then we investigate a few advanced properties in complete and incomplete information context, using two more expressive logics. Along the way, we propose a new compact way to represent game trees. [download PS(179 kb)] [download PDF(86 kb)]
• The Value of Privacy: Optimal Strategies for Privacy Minded Agents
  Sieuwert van Otterloo - Amsterdam, 2005
  accepted for AAMAS 2005
  Agents often want to protect private information, while at the same acting upon the information. These two desires are in conflict, and this conflict can be modeled in strategic games where the utility not only depends on the expected value of the possible outcomes, but also on the information properties of the strategy an agent uses. In this paper we define two such games using the information theory concepts of entropy and relative entropy. For both games we compute optimal response strategies and establish the existence of Nash equilibria. [download PS(201 kb)] [download PDF(97 kb)] Visit the website of this paper

2004

• On the Complexity of Knowledge Condition Games
  Sieuwert van Otterloo, Michael Wooldridge, Barcelona, 2004
  presented at EUMAS 2004, Barcelona
  Understanding the flow of knowledge in multi agent protocols is essential when proving the correctness or security of such protocols. Current logical approaches, often based on model checking, are well suited for modeling knowledge in systems where agents do not act strategically. Things become more complicated in strategic situations. In this paper we show that such situations can best be understood as a special type of game, a \emph{knowledge condition game}. This paper summarizes some results on these games. Two proofs are sketched for the computational complexity of deciding whether a coalition can win a knowledge condition game with and without opponents (Sigma_2 P-complete and NP-complete respectively). We also consider a variant of knowledge condition games in which agents do not know which strategies are played, and prove that under this assumption, the presence of opponents does not affect the complexity. The decision problem without opponents is still NP-complete, but for a different reason. [download PS(227 kb)][download PDF(103 kb)]
• Knowledge Condition Games
  Sieuwert van Otterloo, Wiebe van der Hoek, Michael Wooldridge, Liverpool - Utrecht, 2004
  accepted for Game Theory and Decision Theory 2004, New York
  in modified format also presented at Knowledge and Games 2004, Liverpool
  Agents often interact strategically to meet conditions involving their own or other agents' knowledge. This interaction can be modeled using a new type of game, knowledge condition games. In this paper knowledge condition games are defined and applied to two example problems involving voting and a quiz master problem. It is also shown that a restricted class of knowledge condition games is NP-complete. [download PS(227 kb)][download PDF(103 kb)]
• Model Checking Knowledge and Time via Local Propositions: Cooperative and Adversarial Systems
  Wiebe van der Hoek, Michael Wooldridge, Sieuwert van Otterloo, Liverpool, 2004
  submitted
  [download PS(488 kb)] [download PDF(249 kb)]
• On Epistemic Temporal Strategic Logic
  Sieuwert van Otterloo, Geert Jonker, Liverpool - Utrecht, 2004
  accepted for student sessions of the ESSLLI summer school 2004, Nancy
  accepted for LCMAS workshop 2004, Nancy
  We present a new interpretation of ATEL, a modal logic for reasoning about knowledge, time and strategies. Our approach uses a more subtle meaning of the ability to reach a goal. We use examples to illustrate this and give a semantics using extensive games of imperfect information. Furthermore we show that perfect recall and perfect memory now can be characterized using ATEL*. [download PS(302 kb)] [download PDF(133 kb)] This paper has been published as an electronic note in computer science. [ENTCS version PS(300 kb)] [ENTCS version PDF(178 kb)]
• Axioms for Game Logic with Preferences
  Sieuwert van Otterloo, Wiebe van der Hoek, Michael Wooldridge, Liverpool, 2004
  Presented at LOFT 2004, Leipzig
  Game Logic with Preferences (GLP) is a logic that makes it possible to reason about how information or assumptions about the preferences of other players can be used by agents in order to realize their own preferences. We extend the work done on this logic by looking at the satisfiability problem for this logic. We introduce an axiom system and show the soundness of this system. [download PDF(73 kb)]
• Preferences in Game Logics
  Sieuwert van Otterloo, Wiebe van der Hoek, Michael Wooldridge, Liverpool, 2004
  Presented at AAMAS 2004
  [download PS(410 kb)] [download PDF(97 kb)] Visit the GLP website

2003

• Model checking a knowledge exchange scenario
  Sieuwert van Otterloo, Wiebe van der Hoek, Michael Wooldridge, Liverpool, 2003
  MoChArt workshop, IJCAI 2003 in Acapulco
  This paper discusses model checking knowledge using an extension of Linear Temporal Logic (LTL). It uses the Russian Cards problem, an example of a secure communication protocol, to demonstrate a method and shows that the method is less efficient for ignorance claims than for knowledge claims. [download PS(161 kb)] [download SPIN source code]
• Knowledge as Strategic Ability Sieuwert van Otterloo, Wiebe van der Hoek, Michael Wooldridge, Liverpool, 2003
  presented at LCMAS workshop, Eindhoven 2003, published in ENTCS 85, no. 2 2003
  This paper was presented under the title Transforming knowledge properties into winning strategies. It describes a reduction method which allows one to model check ATEL on turn-based systems using an ATL model checker such as Mocha. A correctness proof for the method is given [download pdf, 234kb] [download ps.zip, 213kb] [download source code] [download specification file]

2002

• Evolutionary Algorithms and Scheduling Problems
  Sieuwert van Otterloo, Master's thesis, Universiteit Utrecht 2002
  This thesis discusses evolutionary algorithms, which includes genetic algorithms and their application to scheduling problems. [dowload pdf(453kb)]

2001

• A security analysis of Pretty good Privacy
  Sieuwert van Otterloo, Master's thesis, Universiteit Utrecht 2001
  In the first half of 2001 I have done research at a certain institute interested in security of computer programs. With Mario de Boer and Gerard Tel I have studied the source code of Pretty Good Privacy, an encryption program. Despite all the effort put into it the program contains errors like any big program. Some of these affect the security. [download ps(1288kb)] [download pdf(980kb)]

2000

• Amazing Wavelet Image Compression
  Sieuwert van Otterloo, Student project, Universiteit Utrecht 2000
  A student project on Wavelet Image compression techniques [download doc(238kb)]