Negotiating over small bundles of resources

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. This paper addresses this issue by analysing how the confinement to certain classes of utility functions can enable agents to move to an optimal allocation by negotiating over small bundles of items at a time. In particular, we consider so-called k-separable domains, where the full set of resources can be divided into several preferentially independent bundles of limited cardinality.