Using utility graphs to search for Pareto-optimal outcomes in complex, interdependent issue negotiations

Negotiation is a powerful tool for modelling complex interactions between self - interested agents, which can be people, companies or increasingly, AI - enabled autonomous agents, that aim to reach the best agreement for their human owners. While negotiation is often thought as a competitive process, in which one part y wins and the other one l oses, in practice most real negotiations involve more complex, win - win scenarios ( Raif fa [20]), in which agreements can be found that maximize the utilities of both agents . S uch outcomes (agreements) are called Pareto - efficient, i.e. it is not possible to find another outcome that would increase one agent's utility, without making another agent worse off. Yet, finding agreements that are Pareto - efficient is a challenging computational problem, especially in complex negotiation domains, where issues negotiated upon are interdependent (i.e. the utility of the value chosen for one negotiation issue depends strongly on the choice for other one s). Consider, for example, the negotiations between parties in a logistic supply chain: producers want to have certain combinations of resources/quantities, delivered at certain times to be able to produce their goods, whil e suppliers may face similar constraints in their cost function for supplying different combinations of items . Or the peer - to - peer negotiations between prosumers in a decentralised power grid, that require certain amounts of energy at different times and locations, which involve non - linear constraints, especially if the capacity of the distribution network is limited .