Two necessary conditions for strategy-proofness: On what domains are they also sufficient?

A social choice function may or may not satisfy a desirable property depending on its domain of definition. For the same reason, different conditions may be equivalent for functions defined on some domains, while not in other cases. Understanding the role of domains is therefore a crucial issue in mechanism design. We illustrate this point by analyzing the role of two conditions, monotonicity and reshuffling invariance, that are always necessary, but not always sufficient for strategy-proofness. We identify domains, that we call intertwined, ensuring the equivalence between these two conditions and that of strategy-proofness for whatever functions are defined on them. We prove that some important domains are intertwined: those of single-peaked preferences, both with public and private goods, and also those arising in simple models of house allocation. We also discuss the relationship between our conditions on functions and domains with others considered in the literature.