Improving Privacy in Distributed Constraint Optimization
February 21, 2008
Thursday, February 21, 11:00AM
Stevens Institute of Technology
Computers increasingly act as autonomous agents entrusted with critical tasks, sensitive data, and interactions with with other humans and machines in large, multi-agent systems. These systems often require the agents to negotiate solutions to constraint optimization problems, such as resource allocation, supply-chain negotiation, and meeting scheduling. For these problems, the constraints are often extremely sensitive, representing personal or proprietary information of the agents. However, the primary algorithms for distributed constraint optimization were not developed with privacy in mind, leading to problems in meeting the needs of users.
This talk provides an analysis of the ways in which privacy has been protected and lost in distributed constraint optimization algorithms. Based on this analysis, I present a new algorithm which augments a prominent algorithm with secret sharing techniques. My approach significantly reduces privacy loss, while introducing only minimal computational overhead. My results show that my new algorithm reduces privacy loss by 29-88% on average over previous approaches.