Improving Privacy in Distributed Constraint Optimization

Multi-agent systems that work with people to accomplish tasks require access to infor-mation that their users consider private. Mechanisms that protect this private informa-tion from the other participants and accurate characterizations of the extent to which these mechanisms do so are essential for the adoption of such systems. This thesis examines these issues in the context of algorithms for distributed constraint optimization (DCOP), a prominent technique for multi-agent coordination. Prior research on DCOP algorithms has focused on the tradeoffs between efficiency and optimality and largely ignored privacy questions. To characterize the level of privacy protection in DCOP algorithms, this thesis defines four privacy properties: the Global Loss Property, the Maximum Adversary Property, the Maximum Victim Property and the Cost-For-Loss Property. These properties provide a global view of the amount of private information lost during optimization as well as a more local view of the way that the leakage of private information affects individual participants. The thesis analyzes the extent to which existing metrics assess privacy loss as defined b