Privacy Preserving DCOP Solving by Mediation

In this study we propose a new paradigm for solving DCOPs, whereby the agents delegate the computational task to a set of external mediators who perform the computations for them in an oblivious manner, without getting access neither to the problem inputs nor to its outputs. Specifically, we propose MD-MAX-SUM, a mediated implementation of the Max-Sum algorithm. MD-MAX-SUM offers topology, constraint, and decision privacy, as well as partial agent privacy. Moreover, MD-MAX-SUM is collusion-secure, as long as the set of mediators has an honest majority. We evaluate the performance of MD-MAX-SUM on different benchmarks. In particular, we compare its performance to PC-SyncBB, the only privacy-preserving DCOP algorithm to date that is collusion-secure, and show the significant advantages of MD-MAX-SUM in terms of runtime.