A theory of communication between autonomous agents should make testable predictions about which communicative behaviors are collaborative, and provide a framework for determining the features of a communicative situation that affect whether a behavior is collaborative. The results presented here are derived from a two-phase empirical method. First, we analyze a corpus of naturally occurring problem-solving dialogues in order to identify potentially collaborative communicative strategies. Second, we experimentally test hypotheses that arise from the corpus analysis in Design-World, an experimental environment for simulating dialogues. The results indicate that collaborative behaviors must be defined relative to the cognitive limitations of the agents and the cognitive demands of the task. The method of computational simulation provides an additional empirical basis for theories of human-computer collaboration.