An overview of privacy improvements to k-optimal DCOP algorithms

ABSTRACT

For agents to be trusted with sensitive data, they must have mechanisms to protect their users' privacy. This paper explores the privacy properties of k-optimal algorithms: those algorithms that produce locally optimal solutions that cannot be improved by changing the assignments of k or fewer agents. While these algorithms are subject to large amounts of privacy loss, they can be modified to reduce this privacy loss by an order of magnitude. The greatest improvements are achieved by replacing the centralized local search with a distributed algorithm, such as DPOP.

REFERENCES

• 1: S. Fitzpatrick and L. Meertens. Distributed coordination through anarchic optimization. In Distributed Sensor Networks: A Multiagent Perspective. Kluwer Academic Publishers, 2003.
• 2: R. Greenstadt, B. Grosz, and M. Smith. Ssdpop: Improving the privacy of dcop with secret sharing. In DCR, 2007.
• 3: Rachel Greenstadt , Jonathan P. Pearce , Milind Tambe, Analysis of privacy loss in distributed constraint optimization, Proceedings of the 21st national conference on Artificial intelligence, p.647-653, July 16-20, 2006, Boston, Massachusetts
• 4: H. Katagishi and J. Pearce. Kopt: Distributed dcop algorithm for arbitrary k-optima with monotonically increasing utility. In DCR, 2007.
• 5: Rajiv T. Maheswaran , Jonathan P. Pearce , Emma Bowring , Pradeep Varakantham , Milind Tambe, Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications, Autonomous Agents and Multi-Agent Systems, v.13 n.1, p.27-60, July 2006 [doi>10.1007/s10458-006-5951-y]
• 6: R. Maheswaran, J. Pearce, and M. Tambe. Distributed algorithms for dcop: A graphical-game-based approach. In PDCS, 2004.
• 7: A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In IJCAI, 2005.
• 8: Marius C. Silaghi , Debasis Mitra, Distributed Constraint Satisfaction and Optimization with Privacy Enforcement, Proceedings of the Intelligent Agent Technology, IEEE/WIC/ACM International Conference, p.531-535, September 20-24, 2004 [doi>10.1109/IAT.2004.51]
• 9: M. Yokoo , K. Hirayama, Distributed Constraint Satisfaction Algorithm for Complex Local Problems, Proceedings of the 3rd International Conference on Multi Agent Systems, p.372, July 03-07, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.m Miscellaneous

General Terms:
Algorithms, Security

Keywords:
distributed constraint optimization, security and privacy