We introduce mCP nets, an extension of the CP net formalism to model and handle the qualitative and conditional preferences of multiple agents. We give a number of different semantics for reasoning with mCP nets. The semantics are all based on the idea of individual agents voting. We describe how to test optimality and preference ordering within a mCP net, and we give complexity results for such tasks. We also discuss whether the voting schemes fairly combine together the preferences of the individual agents.