This is Part I of a paper concerning an iterative decentralized process design to allocate resources optimally in decomposable environments that are possibly characterized by indivisibilities and other nonconvexities. Important steps of the process involve randomization. In Part I we present the basic models and results, together with examples showing that certain assumptions can be satisfied in both classical and nonconvex cases. Part II will go further with such examples in showing that our process yields optimal allocations in environments in which the competitive mechanism fails, as well as show how abstract conditions used in Part I can be verified in terms of properties of preferences and production functions that are familiar to economists.