In this paper we present a model of cooperative problem solving (CPS). Linear Logic (LL) is used for encoding agents’ states, goals and capabilities. LL theorem proving is applied by each agent to determine whether the particular agent is capable of solving the problem alone. If no individual solution can be constructed, then the agent may start negotiation with other agents in order to find a cooperative solution. Partial deduction in LL is used to derive a possible deal. Finally proofs are generated and plans are extracted from the proofs. The extracted plans determine agents’ responsibilities in cooperative solutions.