A dialogue game is presented that enables us to generate coherent elementary conversational sequences at the speech act level. Central to this approach is the fact that the cognitive states of players change as a result of the interpretation of speech acts and that these changes provoke the production of a subsequent speech act. The rules of the game are roughly based on the Gricean maxims of co-operation — i.e., agents are forbidden to put forward information they do not believe and are forbidden to ask anything they already believe; the Gricean maxim of relevance is determined by a so-called imbalance in the players’ belief and desire states. As in realistic conversational situations, it is assumed that the information needed to answer a question can be present in a distributed manner. Consequently, the structure of the dialogues may become rather complex, and may result in the generation of counter-questions and sub-dialogues. It will be shown that the structure and the coherence of conversational units do not necessarily have to be the product of a complex planning process or a speech act grammar, but can be based on elementary generation rules that take only into account the local context. As a result, the conversational game does not suffer from the same computational complexity as existing planning models for speech act generation. Although simple in its basic form, the framework enables us to produce abstract conversations with some properties that agree strikingly with dia- logue properties found in Conversation Analysis.