  In recent years, several studies proposed privacy-preserving algorithms for
solving Distributed Constraint Optimization Problems (DCOPs). All of those
studies assumed that agents do not collude. In this study we propose the first
privacy-preserving DCOP algorithm that is immune to coalitions, under the
assumption of honest majority. Our algorithm -- PC-SyncBB -- is based on the
classical Branch and Bound DCOP algorithm. It offers constraint, topology and
decision privacy. We evaluate its performance on different benchmarks, problem
sizes, and constraint densities. We show that achieving security against
coalitions is feasible. As all existing privacy-preserving DCOP algorithms base
their security on assuming solitary conduct of the agents, we view this study
as an essential first step towards lifting this potentially harmful assumption
in all those algorithms.
