This is a joint work with Professor Jan van Eijck(CWI, Netherlands), and Tomasz Sadzik(Stanford, USA). It was presented in Games, action and social software Workshop , 30 Oct – 3 Nov 2006 @ Lorentz Center, Leiden, the Netherlands.
A pre-publication version is open for download: Action Emulation.
Abstract:
The effects of public announcements, private communications, deceptive messages to groups, and so on, can all be captured by a general mechanism of updating multi-agent models with so-called update action models [3], now in widespread use (see [9] for a textbook treatment). There is a natural extension of the definition of a bisimulation to action models. Surely enough, updating with bisimilar action models gives the same result (modulo bisimulation). But the converse turns out to be false: there are examples of pairs of non-bisimilar update models with the same update effect. This paper is a quest for a notion of structural equivalence that is more appropriate for action models than bisimulation. We propose action emulation as a notion of structural equivalence more appropriate for action models, and generalizing standard bisimulation. It is proved that action emulation provides a full characterisation of update effect. The important case of updating with purely propositional information is treated first, as an easy stepping stone for the more general treatment.
Acknowledgement: Thanks to Johan van Benthem, Hans van Ditmarsch and Albert Visser for inspiring discussions, and thanks to two anonymous reviewers for helpful comments. We are grateful to our editor Wiebe van der Hoek for encouragement and patience. The first author(van Eijck) is grateful to the Netherlands Institute for Advanced Studies in Wassenaar (NIAS) for providing the opportunity to complete this paper as Fellow-in-Residence.
Further comments are welcomed!
No related posts.
Related posts brought to you by Yet Another Related Posts Plugin.
