The complexities of actions and recipes used in collaborative planning are defined using set theory and an accompanying formalization. The formalizations presented can be used as a basis for making decisions in relation choosing recipes, and other activities concerning collaborative task execution in a multi-agent environment. Introducing the notion of the complexity of a recipe and an action provides a measure of the difficulty of a task, based upon which decisions regarding the use of particular recipes and contractors can be made.