Privatizing Constraint Optimization

Abstract

My thesis will contribute to the fields of constraint processing and multiagent systems by proposing novel schemes for achieving privacy in constraint optimization as well as new ways of analyzing and understanding the privacy properties of constraint optimization algorithms. Motivation: It is my belief that there are many domains within constraint processing that motivate the need for more private algorithms and that this work will be broadly applicable. However, I would like to present two particular salient examples in the following paragraphs. One domain that naturally motivates privacy preserving constraint optimization algorithms is scheduling. In this domain, a number of agents, including, say, Sally in Human Resources, wish to schedule events subject to their individual constraints. They wish to keep these constraints private. Sally’s calendar, for one, contains the intersection of multiple professional endeavors as well as items relevant to her personal life. In this case, the agents involved—including Sally—want a solution that will optimize the global social welfare, but that doesn’t mean they want everyone to know how Sally’s preference for attending cancer support group meetings led to that result. As another motivating example, consider the problem of resource allocation. Imagine several government, corporate and nonprofit groups that come together to help with some disaster relief effort. They all wish to contribute the resources that will lead to the optimal end, however, they are mutually distrustful in most of their other endeavors and don’t want the other entities to know the details of their individual constraints. Background: Initially, all constraint processing algorithms were centralized. All constraints were communicated to a central server that then could learn everything about everyone. Concerns about privacy led to the development of distributed constraint satisfaction and optimization algorithms [12, 6]. In these algorithms, each agent owns its own constraints and passes messages as necessary to other agents to collaboratively compute the solution. Since the information was distributed among many agents, these algorithms were thought to be more private. However, since this time most work in this area has focused on improving the effi-