When rational but myopic agents negotiate over the exchange of indivisible resources, any restriction to the negotiation protocol may prevent the system from converging to a socially optimal allocation in the general case. On the other hand, restrictions to the expressive power of the utility functions used by individual agents to represent their preferences can sometimes reduce the complexity of resource allocation problems and allow for very restricted negotiation protocols to work effectively. This paper reviews a number of recent theoretical results addressing these issues. Specifically, it analyses how the confinement to structurally simple deals and to certain restricted classes of cardinal utility functions can enable agents to move to an optimal allocation, while reducing the overall complexity of the process. The case of complex deals is also studied, and both restrictions on utility functions and specially designed protocols are proposed which drastically reduce the complexity of the resource allocation process.