Expressive negotiation in settings with externalities

In recent years, certain formalizations of combinatorial ne-gotiation settings, most notably combinatorial auctions, have become an important research topic in the AI community. A pervasive assumption has been that of no externalities: the agents deciding on a variable (such as whether a trade takes place between them) are the only ones affected by how this variable is set. To date, there has been no widely studied for-malization of combinatorial negotiation settings with exter-nalities. In this paper, we introduce such a formalization. We show that in a number of key special cases, it is NP-complete to find a feasible nontrivial solution (and therefore the max-imum social welfare is completely inapproximable). How-ever, for one important special case, we give an algorithm which converges to the solution with the maximal conces-sion by each agent (in a linear number of rounds for utility functions that decompose into piecewise constant functions). Maximizing social welfare, however, remains NP-complete even in this setting. We also demonstrate a special case which can be solved in polynomial time by linear programming