@article {1509416,
	title = {Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications },
	journal = {Journal of Autonomous Agents and Multiagent Systems (JAAMAS)},
	volume = {13},
	year = {2006},
	pages = {27 - 60},
	abstract = {It is critical that agents deployed in real-world settings, such as businesses, offices, universities and research laboratories, protect their individual users{\textquoteright} privacy when interacting
with other entities. Indeed, privacy is recognized as a key motivating factor in the design
of several multiagent algorithms, such as in distributed constraint reasoning (including both
algorithms for distributed constraint optimization (DCOP) and distributed constraint satisfaction (DisCSPs)), and researchers have begun to propose metrics for analysis of privacy loss
in such multiagent algorithms. Unfortunately, a general quantitative framework to compare
these existing metrics for privacy loss or to identify dimensions along which to construct new
metrics is currently lacking.
This paper presents three key contributions to address this shortcoming. First, the paper
presents VPS (Valuations of Possible States), a general quantitative framework to express,
analyze and compare existing metrics of privacy loss. Based on a state-space model, VPS
is shown to capture various existing measures of privacy created for specific domains of
DisCSPs. The utility of VPS is further illustrated through analysis of privacy loss in DCOP
algorithms, when such algorithms are used by personal assistant agents to schedule meetings
among users. In addition, VPS helps identify dimensions along which to classify and construct
new privacy metrics and it also supports their quantitative comparison. Second, the article
presents key inference rules that may be used in analysis of privacy loss in DCOP algorithms
under different assumptions. Third, detailed experiments based on the VPS-driven analysis
lead to the following key results: (i) decentralization by itself does not provide superior protection of privacy in DisCSP/DCOP algorithms when compared with centralization; instead,
privacy protection also requires the presence of uncertainty about agents{\textquoteright} knowledge of the
constraint graph. (ii) one needs to carefully examine the metrics chosen to measure privacy
loss; the qualitative properties of privacy loss and hence the conclusions that can be drawn
about an algorithm can vary widely based on the metric chosen. This paper should thus serve
as a call to arms for further privacy research, particularly within the DisCSP/DCOP arena.},
	author = {Rajiv T. Maheswaran and Jonathan P. Pearce and Bowring, Emma and Varakantham, Pradeep and Tambe, Milind}
}
