Generic negotiation mechanisms with side payments - Design, analysis and application for decentralized resource-constrained multi-project scheduling problems

Negotiation mechanisms have been proven useful for decentralized resource-constrained multi-project scheduling with self-interested parties (agents) that work together in completing a project. The current paper is concerned with such kinds of multi-agent problems, where each involved party pursues the individual goal of maximizing the discounted cash flow that is connected to its own project activities. Since the parties assess schedules and proposed changes to solutions in terms of money, it is appropriate to utilize money transfers (side payments). We design and analyze different automated negotiation procedures with side payments for resolving conflicts of interest between two agents and experimentally compare results with negotiation mechanisms without the use of money transfers. In principle, we consider two generic negotiation approaches: firstly, an agent may offer tentative payments in order to incentivize the other agent to accept changes to the project schedule within iterative improvement-based negotiation processes; secondly, agents offer or claim money for selecting the final solution from an approximate set of Pareto-optimal solutions that have been generated by a preceding search process. Taking account of self-interested agents and private preference information we discuss suitable elements of the mechanism with regard to strategic agent behavior. We provide insights regarding the effectiveness of different behavioral choices and analyze reasonable strategies of the agents from a prescriptive perspective. Overall, the proposed solution mechanism improves existing results from the literature for the considered kind of problem. Since the approach is built on general concepts, it may be also useful for other applications.