Researchers and industry are actively developing Software Agents (SAs), autonomous software that will assist users in achieving various tasks, collaborate with them, or even act on their behalf. To explore new interaction modes for SAs which need to be more sophisticated than simple exchanges of messages, we have analysed human conversations and elaborated an interaction approach for SAs based on a conversation model. Using this approach, we have developed a multi-agent system that simulates conversations involving SAs. We assume that SAs perform communicative acts to negotiate about mental states, such as beliefs and goals, turn-taking and special conversational sequences. We also assume that SAs respect communication protocols when they negotiate. In this paper, we describe the conceptual structure of communicative acts, the knowledge structures used to model a conversation, and the communication protocols. We show how an inference engine using ‘conversation-managing rules’ can be integrated in a conversational agent responsible for interpreting communicative acts, and we discuss the different kinds of rules that we propose. The prototype PSICO was implemented to simulate conversations on a computer platform.