People frequently use internet-based messaging systems to coordinate. In order to achieve that, it is sufficient for them to exchange natural language messages. The message history they generate can be seen as a shared database that can be tapped into by personal assistive systems; moreover, messaging is increasingly used for human-computer communication. However, if natural language understanding is required for such systems to function properly, the cost of developing them is high and only few market players will be able to compete. If, on the other hand, it is possible to mix machine-interpretable data with natural language conversations, assistive or conversational programs may be developed more easily. As a first important challenge, we tackle the problem of negotiating agreements and unambiguously represent what has been agreed upon in a machine-readable form. In this paper, we propose an extension of the Web of Needs, a decentralized, Linked Data based matching and messaging system, to allow conversation partners to produce a mutually agreed-upon RDF dataset.