Computing equilibria for constraint-based negotiation games with interdependent issues

Negotiation with interdependent issues and nonlinear, non-monotonic utility functions is difficult because it is hard to efficiently explore the contract space. This paper presents a new result in automated negotiations with interdependent issues, complete information and time constraints. We consider that agents express their preferences using constraints defined as one interval per issue and that we represent their constraint sets as intersection graphs. We model negotiations as a bargaining game and we show that the equilibrium solution is one of the maximal cliques of the constraint graph. Consequently, we find that the problem of computing the equilibrium solution has polynomial-time complexity when the number of issues is fixed.