Approximate representation of the Pareto frontier in multiparty negotiations: Decentralized methods and privacy preservation

• A decentralized method for Pareto frontier in multiparty negotiations is proposed.
• The proposed method can generate an approximate representation of Pareto frontier.
• The approximate error can be controlled by the number of iterations and stepsize.
• The proposed method is privacy preserving.

Multiparty negotiations have drawn much research attention in recent years and an important problem is how to find a Pareto optimal solution or the entire Pareto frontier in a decentralized way. Privacy preservation is also important in negotiation analysis. The main aim of this paper is to find an approximate representation of the Pareto frontier in a decentralized manner and meanwhile, all parties’ privacy can be effectively protected. In this paper, we propose a decentralized discrete-time algorithm based on a weight sum method and the well-known subgradient optimization algorithm, where a mediator works as a coordinator to help negotiators. The proposed algorithm is easily executable, and it only requires the mediator to compute a weighted average of the noisy estimates received from negotiators and negotiators to follow a subgradient optimization iteration at this weighted average. The proposed algorithm can generate an approximate Pareto optimal solution for one particular weight vector and an approximate representation of the Pareto frontier by varying appropriately weight vectors. The approximation error between the obtained approximate representation and the Pareto frontier can be controlled by the number of iterations and the step-size. Moreover, it also reveals that the proposed algorithm is privacy preserving as a result of the random disturbance technique and the weighted average scheme used in this algorithm.