Differentially Private Multi-Agent Constraint Optimization
Sankarshan Damle,1 Aleksei Triastcyn,2 Boi Faltings,2 Sujit Gujar1
1Machine Learning Lab, International Institute of Information Technology, Hyderabad2
Artificial Intelligence Laboratory, Ecole Polytechnique Fédérale de Lausannesankarshan.damle@research.iiit.ac.in, {aleksei.triastcyn, boi.faltings}@epfl.ch, sujit.gujar@iiit.ac.in

Abstract
Several optimization scenarios involve multiple agents thatdesire to protect the privacy of their preferences. There exist distributed algorithms for constraint optimization that provide improved privacy protection through secure multiparty
computation. However, it comes at the expense of high computational complexity and does not constitute a rigorous privacy guarantee, as the result of the computation itself may
compromise agents’ preferences. In this work, we show how
to achieve differential privacy through randomization of thesolving process. In particular, we present P-Gibbs, which
adapts the SD-Gibbs algorithm to obtain differential privacy
guarantees with much higher computational efficiency. Experiments on graph coloring and meeting scheduling show
the algorithm’s privacy-performance trade-off compared tovariants with uniform sampling and the SD-Gibbs algorithm.

1

Introduction

The idea of distributed computation has been a trending
topic among computer scientists for decades. Distributing
the computation has several well-known advantages overcentralized computing. Some of these include no single
point failure, incremental growth, reliability, open system,
parallel computing, and easier management of resources.
One of the successful applications of distributed computing
is distributed constraint optimization problem (DCOP), first
introduced in (Yokoo et al. 1998).
Introducing DCOPs. DCOP is a problem where agents collectively compute their value assignments in order to maximize the sum of resulting constraint rewards. In DCOP,
constraints quantify the preference that each agent places oneach of its possible assignments. DCOPs help model various
multi-agent coordination and resource allocation problems.
DCOPs find use in problems such as distributed schedulingof meetings, the distributed allocation of targets to sensors in
a network, the distributed allocation of resources and coordination of mobile agents in disaster evacuation scenarios, andthe distributed management of power distribution networks.
DCOP Algorithms. Many a times, solving a DCOP instance is NP-Hard. Nevertheless, the field has grown steadily
over the years, with several algorithms being introduced
Copyright c 2021, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

to solve DCOP instances, each providing some improvement over the previous (Fioretto, Pontelli, and Yeoh 2018).
These algorithms are either: (1) search-based algorithms like
SynchBB (Hirayama and Yokoo 1997), ADOPT (Modi et al.
2005) and its variants, AFB (Gershman, Meisels, and Zivan 2009), and MGM (Maheswaran, Pearce, and Tambe2006), where the agents enumerate through sequences ofassignments in a decentralized manner; and (2) inferencebased algorithms like DPOP (Petcu and Faltings 2005),
max-sum (Farinelli et al. 2008), and Action GDL (Vinyals,
Rodriguez-Aguilar, and Cerquides 2009), where the agentsuse dynamic programming to propagate aggregated information to other agents.
Ottens, Dimitrakakis, and Faltings (2012) propose Distributed Upper Confidence Tree (DUCT), an extension of
UCB (Fischer and Muller 1991) and UCT (Gelly and Silver2007). While DUCT outperforms the algorithms above, its
per-agent memory requirement is exponential in the numberof agents. It prohibits it from scaling up to larger problems.
Nguyen et al. (2019) improve upon DUCT through theirsampling-based DCOP algorithms called Sequential Distributed Gibbs (SD-Gibbs) and Parallel Distributed Gibbs(PD-Gibbs). These are distributed extensions of the Gibbs
algorithm (Liao 1998). Both SD-Gibbs and PD-Gibbs have alinear-space memory requirement, i.e., the memory requirement per agent is linear in the number of agents. The authors
showed empirically that SD-Gibbs and PD-Gibbs could findbetter solutions than DUCT, run faster, and solve some large
problems that DUCT fails to solve due to memory limitations. Therefore, in this work, we focus on SD-Gibbs.1
Privacy in DCOPs. The need for preserving the privacyof an agent’s private information is vital and is an active
research area (Damle, Faltings, and Gujar 2019; Sharma,
Xing, and Liu 2019; Li et al. 2020; Lu, Tang, and Wang2018). This need holds for DCOPs too, as, in the processof ‘solving’ a DCOP instance, the transfer of information
across agents may leak sensitive information, such as agent’s
preferences, to the other participating agents. Thus, privacypreserving solutions to DCOPs are necessary and form thebasis of this work.
Privacy in DCOPs has focused on the use of cryptographic
primitives, such as partial homomorphic encryption. Sev1

Our results also follow for PD-Gibbs.

eral privacy-preserving algorithms are present in literature,
which use cryptographic primitives atop existing DCOP
algorithms to provide strong privacy guarantees. These
include P-DPOP, P3/2 -DPOP, P2 -DPOP (Léauté 2011),
which build on the DPOP algorithm; P-SyncBB (Grinshpoun and Tassa 2016) over SynchBB; and most recently
P-MaxSum (Tassa, Grinshpoun, and Zivan 2017) which
presents the privacy variant of the max-sum algorithm. However, the use of cryptographic primitives and the computationally expensive nature of DCOPs results in thesealgorithms not being scalable, even for moderate problems. Moreover, these techniques cannot be generalized
to sampling-based algorithms such as DUCT, SD-Gibbs,
which are computationally efficient.
Brito et al. (Brito et al. 2009) use information entropy toquantify the privacy loss incurred by an algorithm in the process of solving a DCOP. Grinshpoun et al. (Grinshpoun et al.
2013) present private local-search algorithms, based on the
aforementioned algorithms. The authors use the quantification to show that their algorithms provide high quality of solutions while simultaneously preserving privacy. While theprivacy loss metric defined in (Brito et al. 2009) is interesting, we believe it is not rigorous. Moreover, the improved
performance of SD-Gibbs, both in terms of solution quality
and memory, motivates us to design new private algorithms
with rigorous privacy guarantees.
Differential Privacy (DP). We use DP (Dwork 2006;
Dwork et al. 2006) to preserve privacy of agent preferences,i.e., ensuring constraint privacy in DCOPs. For cases when
the set of variables and agents involved is common knowledge, there are more efficient techniques for distributed optimization using a central coordinator and stochastic gradient descent. Researchers have developed DP techniques forthis context as well (Huang, Mitra, and Vaidya 2015). While
such algorithms are well-suited for contexts such as federated learning, where the model parameters are common
knowledge, in meeting scheduling, they would leak the information of who is meeting with whom, which is usually
the most sensitive information. Therefore, we focus on algorithms where each participant only knows about agentsthat it shares constraints with and nothing about the rest of
the problem. In particular, we focus on achieving privacy in
SD-Gibbs using DP techniques. Furthermore, we consider
a stronger local model of privacy (Dwork and Roth 2014),
which ensures the indistinguishability of any two agents.
Contributions. Achieving a scalable, privacy-preserving
DCOP, without a centralized authority is a challenge. We
show that SD-Gibbs may leak information about agent constraints during its execution. Further, the iterative nature ofefficient algorithms like SD-Gibbs may lead to a high privacy loss over the iterations.
Addressing this problem, we develop new differentiallyprivate variants of the SD-Gibbs algorithm. Specifically,
we present (i) P-Gibbs: which uses softmax with temperature to smooth sampling distributions in SD-Gibbs; and(ii) P-Uniform: which samples values uniformly. Additionally, during computation, we add Gaussian noise to the relative utility in both algorithms. We then provide a refined

analysis of privacy within the framework of (, δ)-DP (Sections 4.1, 4.2 and 4.3). Our experiments demonstrate our algorithms’ practicality and strong performance for a reasonable privacy budget, i.e, , with SD-Gibbs as the baseline.
Throughout the paper, we omit proofs of some of the results presented. These proofs are provided in the appendix.

2
2.1

Preliminaries

DCOP

Distributed Constraint Optimization Problem (DCOP) is aclass of problems comprising a set of variables, a set of
agents owning them; and a set of constraints defined overthe set of variables. These constraints reflect each agent’s
preferences. Formally,
Definition 1 (DCOP). A Distributed Constraint Optimization Problem (DCOP) is a tuple hX , A, D, F, αi wherein,• X = {x1 , . . . , xp } is a set of variables;• A = {1, . . . , m} is a set of agents;• D = {D1 , . . . , Dp } is a set of finite domains such that Di
is the domain of xi ;• F is a set of utility functions Fij : Di ×Dj → R. Fij gives
the utility of each combination of values of variables in its
scope. Let var(Fij ) denote the variables in the scope ofFij .
• α : X → A maps each variable to one agent.
In this work, w.l.o.g (Yokoo 2012), we assume that p =m, i.e., the number of agents and the number of variables areequal. Also, let D = Di = Dj , ∀i, j, i.e., all variables havethe same domain. The total utility in DCOP, for a complete
assignment X = {xi = di | ∀i}, where di is the assignmentof variable xi , is:


m
X
X

F (X) ,Fij (X||D ) ,
(1)
i=1

j

where X||D is the projection of X to the subspace on which
Fij is defined. The objective of a DCOP is to find an assignment X∗ that maximizes the total utility, i.e., F (X∗ ) =maxX∈D F (X).
Constraint Graph In DCOP, each combination of variables/agents is referred to as a constraint. The utility functions over these constraints quantify how much each agent
prefers a particular constraint. This constraint structure iscaptured through a constraint graph.
Definition 2 (Constraint Graph (CG)). Given a DCOP
hX , A, D, F, αi, its constraint graph G = hX , Ei is suchthat (xi , xj ) ∈ E, ∀j ∈ var(Fij ).
A pseudo-tree arrangement has the same nodes and edges
as the constraint graph. The tree satisfies (i) there is a subset
of edges, called tree edges, that form a rooted tree; and (ii)
two variables in a utility function appear in the same branchof that tree. Such an arrangement can be constructed using a
distributed-DFS (Hamadi, Bessiere, and Quinqueton 1998).
For the algorithms presented in this paper, let Ni refer tothe set of neighbours of xi in CG. Also, let Ci denote the setof children xi in the pseudo-tree, Pi as the parent of variable
xi , and P Pi as the set of pseudo-parents of xi .

Variables

Definition

di and dˆid∗id¯i
Xi and X̄iti , t∗i , t̄∗i
∆i
¯i
∆
Ω
Ω̄
Ω∗

Values in current and previous iteration
Value in the best complete solution so far
Best response value
Context and best-response context
Time index, best-response and non-best response index
Difference in current and previous local solution of agent i
Difference in current best-response solution with previous
Shifted utility of the current complete solution
Shifted utility of the best-response solution
Shifted utility of the best complete solution

Table 1: Variables maintained by each agent xi in SD-Gibbs
Procedure 1: Sampling in SD-Gibbs (Nguyen et al.
2019)
1 ti ← ti + 1; dˆi ← di
2 di ← Sample based on (2)P
F (d0 , d¯ )3 d¯i ← argmaxd0 ∈D¯iih hxj ,dj i∈X̄i ij i j iPˆ
4 ∆i ←
hxj ,dj i∈Xi Fij (di , dj ) − Fij (di , dj )hiP
¯i , d¯j ) − Fij (dˆi , d¯j )
¯i ←
5 ∆
F
(
d
¯
ij
hxj ,dj i∈Xi
∗ ∗6 Send VALUE(xi , di , d¯i , t , t̄ ) to each xj ∈ Ni
i

2.2

i

Sequential Distributed Gibbs (SD-Gibbs)

We now describe Sequential Distributed Gibbs (SD-Gibbs)
as first introduced in (Nguyen et al. 2019). SD-Gibbs uses
the well known Gibbs sampling algorithm (Nguyen et al.
2019, Algortihm 1) to solve a DCOP instance as: (i) A
DCOP, whose solution is one with the maximum utility, canbe mapped to a problem whose solution is one with the maximum likelihood; and (ii) A solution with the maximum utility is also a solution with the maximum likelihood.
The authors then map DCOP to a maximum a posteriori (MAP) estimation problem. For this, consider MAP ona Markov Random Field (MRF). MRF consists of a set of
random variables represented by nodes, and a set of potential functions. Each potential function, represented by
θij (xi ; xj ), is associated with an edge. Let the graph constituting MRF, with nodes and edges, be denoted by hV, Ei.
Let P r(xi = di ; xj = dj ) be defined as exp(θij (xi =di ; xj = dj )). Then, the most probable assignment is given
by:


Y
X
1
1
Pr(X) =eθij (xi ,xj ) = exp θij (xi , xj ) .
Z
Z
i,j∈E

i,j∈E

Here, Z is the normalisation factor. This corresponds to the
maximum solution of DCOP if,
X
F (X) =
θij (xi , xj ).
i,j∈E

Sampling We now describe sampling in SD-Gibbs. Let Xidenote agent i’s context, defined as the set consisting of its
neighbors and the value assigned to them. In each iteration,
each agent i samples a value di with the following equation,

Pr(xi |xj ∈ X \ {xi }) = Pr(xi |xj ∈ Ni )X
1= exp ZFij (di , dj )

hxj ,dj i∈Xi

(2)Let, Pi (xi ) = {Pr(xi |xj ∈ X \ {xi })|xi = di ∀di ∈Di }, i.e., Pi represents the SD-Gibbs probability distributionof each agent i. The relevant notations required for the SDGibbs algorithm are presented in Table 1.
Algorithm The following steps summarize SD-Gibbs. We
present the formal algorithm in the supplement.
S0 The algorithm starts with a construction of the pseudotree and each agent initializing each of their variables,from Table 1, to their default values. The root then starts
the sampling, as descried in Procedure 1 and sends the
VALUE message (line 6) to each of its neighbors.
S1 Upon receiving a VALUE message, the agent i updates
its current contexts, Xi and X̄i with the sender’s values.
If the message is from agent i’s parents, then the agent
itself samples, i.e., executes Procedure 1. This samplingstage continues until all the leaf agents have sampled.
S2 Each leaf agent j then sends a BACKTRACK message to¯ j . When the parent
its parent comprising xj , ∆j , and ∆receives the message, it too sends a BACKTRACK message to its parent. The process continues until the root
receives the message – concluding one iteration.
S3 To reach a solution, each agent i uses its current (∆i )¯ i ) local utility differences.
and current best-response (∆We refer to these differences as relative utilities. Upon receiving a BACKTRACK message, agent i adds the deltavariables of its children to its own. Consequently, thesevariables for the root agent quantify the global relative
utility. Based on this, at the end of an iteration, the root
decides to keep or throw away the current solution.

2.3

Privacy in DCOPs

Privacy in DCOP algorithms comprises the fact that any
given agent’s knowledge about the problem will not be revealed to other agents by the messages exchanged during thealgorithm execution. Privacy definitions relevant to DCOPs
include (Faltings, Léauté, and Petcu 2008): (i) Agent Privacy
which states that no agent should be able to discover the
existence of its non-neighbors; (ii) Topology Privacy which
implies that agents must not learn topological information of
the CG; (iii) Decision Privacy which prevents the discoveryof an agent’s assignments from other agents; and (iv) Constraint Privacy which states that no agent must be able todiscover the nature of constraint that does not involve a variable it owns. In this work, we focus on constraint privacy toensure privacy of agent preferences. Since absolute privacy
is not an achievable goal (Dwork 2006), we formalise constraint privacy in terms of (, δ)-DP (Dwork and Roth 2014).

2.4

Differential Privacy

Differential Privacy (DP) is normally defined for adjacentdatabases, i.e., databases differing in a single entry. However, in this instance, not only we want to protect privacy
against external adversaries, but also against curious fellow agents. To do so, we consider the local model of privacy (Dwork and Roth 2014). It is defined on individual entries rather than databases, or in our setting, on individual
agents. Formally, we want our algorithm for any two utility
functions (vectors in Rp ) to satisfy the following definition,from (Dwork and Roth 2014),
Definition 3 (Local Differential Privacy). A randomized
mechanism M : F → R with domain F and range R satisfies (, δ)-DP if for any two inputs F, F 0 ∈ F and for any
subset of outputs O ⊆ R we have,Pr[M(F ) ∈ O] ≤ e Pr[M(F 0 ) ∈ O] + δ(3)Privacy loss, useful for our analysis of DP, is defined as
Pr[M(F ) = o]oLM(F )||M(F 0 ) = ln
(4)
Pr[M(F 0 ) = o]Privacy Leakage in SD-Gibbs In SD-Gibbs, constraint
privacy is compromised in the following two ways:
1. By sampling. Each variable value in SD-Gibbs is sampled according to agent i’s utility Fij . As values withmore utility are more likely to be drawn, SD-Gibbs leaks
sensitive information about these utility functions. Fortunately, this stage can be secured by simply making distributions more similar across agents (Section 3).
2. By relative utility ∆. Every leaf agent j in the pseudo¯ j to its parent i. The parent agent
tree sends its ∆j and ∆¯ i , respectively, and passes
adds the values to its ∆i and ∆them on up the tree. The process continues until the values reach the root. Thus, any intermediate agents, or anadversary observing ∆, can learn something about j’s
utility even if sampling is private.

within the domain.2 In other words, D1 = D2 = . . . = Dp
and Fij (·, ·) > 0, ∀i. Further, in order to bound privacy lossof the algorithm by a reasonably small , we introduce thefollowing assumption about utility functions.

3.1

Recall the notion of max-divergence, a worst-case analogue
of KL divergence, for two probability distributions P and Q:


P (x)
D∞ (P ||Q) = max ln
.
(6)
x
Q(x)
Absolute continuity is trivially satisfied by the initial assumptions introduced above. With this in mind, we now
present the main privacy assumption.
Assumption 1 (Bounded Sampling Divergence). For any
two agents i and j, with value domains D = Di =Dj and i 6= j, max-divergence between SD-Gibbs sampling distributions is bounded by a constant Γ∞ . Formally,∀i, j, s.t. i 6= j and ∀Xi , Xj , we have,
D∞ (Pi ||Pj ) ≤ Γ∞ .

3.2

3

(5)

Differential Privacy in SD-Gibbs

First, typically for DP, we need to ensure full support of theoutcome distribution. Indeed, if Pr[M(D0 ) = o] = 0 forsome o, the privacy loss incurred is infinite and one cannot
bound . It implies that all agents must have the same domain for their variables and non-zero utility for each value

Bounding Sensitivity with Assumption 1

Claim 1. In SD-Gibbs, ∀i, j s.t i 6= j and D = Di = Dj ,from Assumption 1, we have,


X
X
Fik −
Fjl  ≤ Γ∞
max 
d∈D

Xi

Xj

Proof. Observe that,

max 
d∈D

Sensitivity In order to achieve DP, particularly for ∆’s, weneed to bound its sensitivity. Sensitivity is defined as the
maximum possible change in the output of a function weseek to make privacy-preserving. Formally,
Definition 4 (Sensitivity). Sensitivity, denoted by τ , is the
maximum absolute difference between any two relative utility values ∆ and ∆0 , i.e.,
∆,∆

(7)

We now prove that Assumption 1 leads to bounded sensitivity for relative utility ∆. Specifically, Claim 1 presents Γ∞as the maximum difference of sums of utility, for any pair ofagents in SD-Gibbs. Then, Theorem 1 uses this difference tobound the sensitivity.

These follow by observing what critical information gets
transferred by each agent i in S0-S3. We ignore t∗ and t̄∗because these are simply functions of utility, i.e., will be private by post-processing property once utility are private.

τ = max0 ∆ − ∆0Privacy Assumption


X

Fik −

Xi

X

Fjl 

Xj



hP
i
1/Z
·
exp
F
(d,
d
)
ik
k
Xi

hP
i
= max ln d∈D
1/Z · exp
Xj Fjl (d, dl )!
Pi (xi = d)= max ln≤ Γ∞ .
(8)d∈D
Pj (xj = d)This proves the claim.
Theorem 1. For any two agents i and j, i 6= j, under
Assumption 1, the relative utility sensitivity in SD-Gibbs isbounded by τ = 2 · Γ∞ .
2

If any agent has a zero utility for some value, then all agents
must have zero utility, and w.l.o.g., we can simply exclude suchvalues from all domains.

Proof. We know,
X
∆i ←

h
i
Fik (di , dk ) − Fik (dˆi , dk ) .

hxk ,dk i∈Xi

For brevity, let Fi (d) represent Fik (d, dk ), ∀hxk , dk i ∈ Xi .
Similarly, Fj (d) represent Fjl (d, dl ), ∀hxl , dl i ∈ Xj . Now
from (5), let κ = ∆i − ∆j , i.e.,


X
X
X
X
ˆ −
ˆ
Fi (d) −Fi (d)κ=
Fj (d) −Fj (d)

=

Xi

Xi

X

X

Fi (d) −

Xi

Xj

Xj

Xj



X
X
ˆ −
ˆ
Fj (d) − Fi (d)
Fj (d)Xi

Xj

From Claim 1 and (5), we get, 0 ≤ κ ≤ 2 · Γ∞ , and thus,τ = 2 · Γ∞ .

3.3

Enforcing Assumption 1 with Softmax

In order to enforce Assumption 1, we apply a softmax function to sampling distributions. Let the softmax distribution
with temperature γ over Pi be given by pi :()
exp(Pi (xi = dk )/γ)pi (xi , γ) = P; ∀dk ∈ D
dl ∈D exp(Pi (xi = dl )/γ)
(9)
The following claim follows from Assumption 1.
Claim 2. For two probability distributions using softmax, pi
and pj , we have, ∀i, j, ∀d ∈ D and ∀D, s.t. |D| > 1, γ ≥ 1#"
2pi (xi = d, γ)ln≤ = Γ∞
pj (xj = d, γ)γEffect of Softmax. We illustrate the effect of softmax withthe following example. Let Dj = {d1 , d2 , d3 }, ∀j suchthat Pi = [0.8, 0.15, 0.05]. Observe that the distribution
is such that the probability of sampling d1 is significantly
more than others. Now, the corresponding softmax distributions, from (9), will be: p(·, γ = 1) = [0.50, 0.26, 0.24],p(·, γ = 2) = [0.41, 0.30, 0.29], and p(·, γ = 10) =[0.35, 0.33, 0.32]. That is, the softmax distribution is more
uniform than Gibbs’. This implies that an adversary will be
more indifferent towards the domain values the domain values while sampling. For e.g., d1 and d2 in p(·, γ = 1). Thus
softmax allows us to improve on the privacy leak during
sampling in SD-Gibbs.

4

Preserving Constraint Privacy in DCOP

We now build upon SD-Gibbs to present two novel, scalable
algorithms for DCOPs that preserve constraint privacy.

4.1

P-Gibbs

The difference in P-Gibbs and SD-Gibbs is as follows:
1. P-Gibbs uses softmax function over SD-Gibbs distributions for sampling di ’s, ∀i.
2. P-Gibbs randomly chooses subsets of agents to sample
new values in each iteration. More specifically, in every
iteration, each agent i samples a new value di with probability q, or uses previous values with probability 1 − q.

Providing (, δ)-DP for P-Gibbs We first calculate theprivacy parameters of the sampling stage, denoted by s andδ, in P-Gibbs. For this, we use an extension of the moments
accountant method (Abadi et al. 2016) for non-Gaussianmechanisms. Following derivations by Triastcyn and Faltings (2020),
0

Pr[L ≥ s ] ≤ max0 eλDλ+1 [M(F )||M(F )]−λs .
F,F

(10)

Here, L is the privacy loss between any two agents andDλ (·||·) is Renyi divergence of order λ ∈ N with a slightabuse of notation (using M(·) instead of a distribution imposed by it). Unlike Triastcyn and Faltings (2020), we consider the classical DP. Using their notion of Bayesian DP
could improve the bounds, but we leave it for future work.
Also from (Triastcyn and Faltings 2020), we borrow thenotion of privacy cost ct (λ). By trivial manipulation, foreach iteration t,ct (λ) = max λDλ+1 pi (d)||pj (d) ≤ λΓ∞ ,
(11)
i,j

where (11) is due to monotonicity Dλ (P ||Q) ≤Dλ+1 (P ||Q) ≤ D∞ (P ||Q), ∀λ ≥ 0. Importantly, this cost
can be further reduced by subsampling agents with probability q < 1, as we outline next.
Reproducing the steps of the sampled Gaussian mechanism analysis by Triastcyn and Faltings (2020) for our mechanism and classical DP, we formulate the following result.
Theorem 2. Privacy cost ct (λ) at iteration t of a samplingstage of P-Gibbs, with agent subsampling probability q, ishi(s)ct (λ) = ln Ek∼B(λ+1,q) ekΓ∞ ,where B(λ, q) is the binomial distribution with λ experiments and probability of success as q, λ ∈ N.
Finally, merging the results, we can compute s , δ acrossmultiple iterations asPT (s)
ln δ ≤ t=1 ct (λ) − λs
P

(12)
(s)
T

s ≤ λ1
t=1 ct (λ) − ln δFigure 1 shows the variation of s for different values of λand Γ∞ , with the sampling probability q = 0.1. We observethat λ has a clear effect on the final s value, and one should
ideally minimize the bound over λ.

4.2

P-Uniform

We presented P-Gibbs, which uses a softmax function to satisfy Assumption 1 and bound the privacy loss incurred bysampling. Coupled with Theorem 2 and Eq. 12, it allows us
to quantify privacy parameters s and δ.
A more “extreme” way to prevent this leakage is to always
sample uniformly, i.e., di ∈ Uniform(Di ), for each agent i.
This will provide the least information leakage in the sampling stage of SD-Gibbs. We refer to this private version of
SD-Gibbs as P-Uniform.
Theorem 3. Privacy loss in P-Uniform for sampling d ∈ D
is 0, for any two agents i and j, D = Di = Dj and i 6= j.

Algorithm(s , δ)P-Gibbs(Γ∞ , 0)P-Uniform(0, 0)(n , δ)q
( στ 2 ln 1.25
δ , δ)q( στ 2 ln 1.25
δ , δ)( = s + n , δ) for T iterations


T (s)
T (n)
1
λ ct (λ) + λ ct (λ) − λ ln δ, δ


T (n)
1
c
(λ)
−
ln
δ,
δ
t
λ
λ



Table 2: Per-iteration and final (, δ) bounds for P-Gibbs and P-Uniform.

5

Experimental Evaluation

We now empirically evaluate the performance of our novel
algorithms, P-Gibbs and P-Uniform, w.r.t. to SD-Gibbs.

Figure 1: Variation of s with λProof. Observe that the probability of sampling any d ∈ Dwill the be the same for any two distinct agents i and j. As aresult, from Eq. 4, the privacy loss incurred is 0.
This implies that s = 0 in P-Uniform. Further, observethat the temperature parameter in P-Gibbs may be tuned todecrease the overall privacy budget (Figure 1). As γ → ∞,we have pi = pj =⇒ s → 0. Thus, increasing γ, or
equivalently, decreasing Γ∞ , leads to P-Gibbs performing
more similarly to P-Uniform, as more information of SDGibbs sampling distribution is lost.

4.3

Privacy of ∆ in P-Gibbs and P-Uniform

Sections 4.1 and 4.2 deal with the privacy loss occurring due
to sampling in P-Gibbs and P-Uniform, respectively. How¯ also leak inforever, as aforementioned, the values ∆ and ∆mation about agents’ constraints. As a result, we must sanitize these values so as to fully preserve privacy. We achieve
this by employing the Gaussian noise mechanism (Dwork
and Roth 2014) defined asMG (∆) , ∆ + Yi ,where Yi ∼ N (0, τ 2 σ 2 ), τ is the sensitivity and σ is thenoise parameter.
Privacy parameters for the relative utility ∆, denoted by
n and δ, can be computed either using the basic composition along with (Dwork and Roth 2014, Theorem A.1) or the
moments accountant (Abadi et al. 2016). The latter can be
unified with the accounting for the sampling stage by using:
h
i
2 2
2 2
(n)
ct (λ) = ln Ek∼B(λ+1,q) ekDλ+1 [N (0,τ σ )||N (τ,τ σ )] .
Table 2 summarises expressions for per-iteration and total
 values for P-Gibbs and P-Uniform.

Setup pyDCOP (Rust, Picard, and Ramparany 2019) isa Python module that provides implementations of many
DCOP algorithms (DSA, MGM, MaxSum, DPOP, etc.). It
also allows the implementation of one’s own DCOP algorithm easily, by providing all the required infrastructure:agents, messaging system, metrics collection, etc. We use
pyDCOP’s implementation of the SD-Gibbs algorithm torun our experiments. In addition, we also implement our privacy variants – P-Gibbs and P-Uniform.
Generating Test-cases pyDCOP allows for generating
random test-cases for various problems through its command line interface using the generate option. We generategraph-coloring and meeting scheduling problem instances.
These are benchmark problems in DCOP literature. We test
the performance of our algorithms across 25 such randomly
generated problems.
Method We consider the utility given by SD-Gibbs’ solution as one of the two baselines. The second baseline is the“one-shot” random assignment, i.e., an algorithm that randomly assigns values to each agent and outputs the utility
based on it. As there is no exchange of information in suchan one-shot assignment, trivially with respect to constraint
privacy, (i) one-shot:  = 0; and (ii) SD-Gibbs:  = ∞.
Further, note that all these methods, including our PGibbs and P-Uniform, are random algorithms. Hence, for afair comparison, we run each benchmark problem 20 times
and use the subsequent average utility for our calculations.
Throughout our experiments we fix: γ = 4, λ =100 (for sampling), λ = 7 (for noise), q = 0.1, δ =10−2 , and T = 50. The choice of δ is such that δ < 1/m.
We let γ = 4 which implies Γ∞ = 0.5. Finally, we consider ∈ {1, 5, 7.5, 10}, calculated using the results in Table 2.
Solution Quality (SQ) We use the following metric:
Definition 5 (Solution Quality (SQ)). Solution quality SQAof an algorithm A is defined as
SQA =UA − UR,US − URfor utilities of A, SD-Gibbs, and one-shot: UA , US , UR .
SQ allows us to place the utility of P-Gibbs and PUniform in the context of SD-Gibbs and one-shot random
solutions. SQA ≈ 1 indicates that utility does not deteriorate compared to SD-Gibbs. On the other hand, SQA ≈ 0means that there is little gain compared to a purely randomFigure 2: Graph Coloring Benchmark
Algorithm



SQ (mean ± std)

P-Gibbs

57.5
100.281 ± 0.143
0.348 ± 0.159
0.324 ± 0.192

P-Uniform

1
5
7.5
10

0.190 ± 0.119
0.322 ± 0.180
0.321 ± 0.153
0.341 ± 0.195

Table 3: Graph coloring, average SQ across problems.
assignment. It is possible that SQA > 1 due to randomness
or privacy noise acting as a simulated annealing.

5.1

Graph-Coloring (GC)We generate 25 sample graph-coloring problems. The problems are such that the number of agents/variables lie between [30, 50) and agents’ domain size between [10, 20).
Each constraint is a random integer taken from (0, 10).
Figure 2 gives SQ per problem instance, per . Table 3
provides SQ scores averaged across all problems. For bothalgorithms, the average SQ improves between the minimum
and the maximum privacy budgets, although not evenly
across the range. Overall, private SQ is evidently lower inthis benchmark. However, since it is the first method of its
kind, to the best of our knowledge, we believe it is still astrong result, and future work will improve the performance.

5.2

Meeting Schedule (MS)We generate 25 sample meeting scheduling problems. The
problems are such that the number of agents/variables lie
between [1, 50) with number of slots, i.e., domain for eachagent randomly chosen from [50, 100). Each constraint is arandom integer taken from (0, 100), while each meeting may
occupy [1, 5] slots randomly. Figure 3 gives the comparison.
Analogously to the graph-coloring example, Figure 3 provides SQ scores per problem, with different plots for each ,
and Table 4 average SQ over all problems. Notably, bothmethods perform nearly as well as SD-Gibbs.
In this problem, performance is very strong and there
is virtually no loss of utility. The average SQ increases
only marginally with the privacy budget, which could be attributed to the fact that the SQ is high to begin with.

Figure 3: Meeting Scheduling Benchmark
Algorithm



SQ (mean ± std)

P-Gibbs

57.5
100.973 ± 0.0513
0.973 ± 0.051
0.975 ± 0.0498

P-Uniform

1
5
7.5
10

0.979 ± 0.0475
0.985 ± 0.0372
0.987 ± 0.0373
0.990 ± 0.0328

Table 4: Meeting scheduling, average SQ across problems.

In both problems, P-Gibbs and P-Uniform perform very
similarly, which is not intuitive at a first glance. However,
we can attribute this behavior to the following fact. For equalvalues of , P-Uniform adds less noise in ∆, thereby alleviating the lack of information in the sampling stage.
Discussion. We believe that the improved performance ofour privacy variants in MS over SD-Gibbs is because the
Gibbs sampling in SD-Gibbs assumes statistical independence of the variables. This is given in random GC instances
but not in MS. Thus, the performance of SD-Gibbs is not
significantly better than our privacy variants in MS. Ourvariants also outperform SD-Gibbs in some cases (Figure3) which can be attributed to the noise added which acts as
simulated annealing.

6

Conclusion

In this paper, we address the problem of privacy-preserving
distributed constraint optimization. We employ a rigorous
standard of differential privacy to guarantee constraint andutility privacy for agents. As we use the local model of DP,
our approach protects not only against external adversaries
but also against other agents within the same system.
We propose two novel, private DCOP algorithms based on
SD-Gibbs. For these methods, we perform theoretical privacy analysis and experimental evaluation on such benchmark problems as graph coloring and meeting scheduling.
Our experiments demonstrate that the developed techniques
can achieve strong privacy guarantees while maintaining
high utility, especially in meeting scheduling problems.

References
Abadi, M.; Chu, A.; Goodfellow, I.; McMahan, H. B.;
Mironov, I.; Talwar, K.; and Zhang, L. 2016. Deep learningwith differential privacy. In Proceedings of the 2016 ACM
SIGSAC Conference on Computer and Communications Security, 308–318.

Grinshpoun, T.; and Tassa, T. 2016. P-SyncBB: A privacy
preserving branch and bound DCOP algorithm. Journal of
Artificial Intelligence Research 57: 621–660.
Hamadi, Y.; Bessiere, C.; and Quinqueton, J. 1998. Distributed Intelligent Backtracking. In ECAI, 219–223.

Brito, I.; Meisels, A.; Meseguer, P.; and Zivan, R. 2009.
Distributed constraint satisfaction with partially known constraints. Constraints 14(2): 199–234.

Hirayama, K.; and Yokoo, M. 1997. Distributed partial constraint satisfaction problem. In International Conference on
Principles and Practice of Constraint Programming, 222–
236. Springer.

Damle, S.; Faltings, B.; and Gujar, S. 2019. A Truthful,
Privacy-Preserving, Approximately Efficient Combinatorial
Auction For Single-minded Bidders. In Proceedings of the
18th International Conference on Autonomous Agents andMultiAgent Systems, 1916–1918.

Huang, Z.; Mitra, S.; and Vaidya, N. 2015. Differentially private distributed optimization. In Proceedings of the 2015 International Conference on Distributed Computing and Networking, 1–10.

Dwork, C. 2006. Differential Privacy. In 33rd International Colloquium on Automata, Languages and Programming, part II (ICALP 2006), volume 4052 of Lecture Notes
in Computer Science, 1–12. Springer Verlag. ISBN 3-54035907-9. URL https://www.microsoft.com/en-us/research/
publication/differential-privacy/.
Dwork, C.; McSherry, F.; Nissim, K.; and Smith, A. 2006.
Calibrating noise to sensitivity in private data analysis. In
Theory of cryptography conference, 265–284. Springer.
Dwork, C.; and Roth, A. 2014. The Algorithmic Foundations of Differential Privacy. Theoretical Computer Science9(3-4): 211–407.
Faltings, B.; Léauté, T.; and Petcu, A. 2008. Privacy guarantees through distributed constraint satisfaction. In 2008
IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, volume 2, 350–358.
IEEE.
Farinelli, A.; Rogers, A.; Petcu, A.; and Jennings, N. R.
2008. Decentralised coordination of low-power embedded
devices using the max-sum algorithm. In Proceedings of the
7th International Joint Conference on Autonomous Agentsand Multiagent Systems - Volume 2, 639–646. International
Foundation for Autonomous Agents and Multiagent Systems.
Fioretto, F.; Pontelli, E.; and Yeoh, W. 2018. Distributed
constraint optimization problems and applications: A survey. Journal of Artificial Intelligence Research 61: 623–698.
Fischer, W.; and Muller, B. W. 1991. Method and apparatus
for the manufacture of a product having a substance embedded in a carrier. US Patent 5,043,280.
Gelly, S.; and Silver, D. 2007. Combining online and offline
knowledge in UCT. In Proceedings of the 24th international
conference on Machine learning, 273–280.
Gershman, A.; Meisels, A.; and Zivan, R. 2009. Asynchronous forward bounding for distributed COPs. Journalof Artificial Intelligence Research 34: 61–88.
Grinshpoun, T.; Grubshtein, A.; Zivan, R.; Netzer, A.; andMeisels, A. 2013. Asymmetric distributed constraint optimization problems. Journal of Artificial Intelligence Research 47: 613–647.

Léauté, T. 2011. Distributed Constraint Optimization: Privacy Guarantees and Stochastic Uncertainty. PhD thesis,
Ecole Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland. URL http://thomas.leaute.name/main/
DCOP privacy uncertainty thesis.html.
Li, Q.; Wu, Z.; Wen, Z.; and He, B. 2020. Privacy-Preserving
Gradient Boosting Decision Trees. Proceedings of the AAAI
Conference on Artificial Intelligence 34(01): 784–791. doi:
10.1609/aaai.v34i01.5422. URL https://ojs.aaai.org/index.
php/AAAI/article/view/5422.
Liao, J. 1998. Variance reduction in Gibbs sampler using quasi random numbers. Journal of Computational andGraphical Statistics 7(3): 253–266.
Lu, Y.; Tang, Q.; and Wang, G. 2018. ZebraLancer: Private and Anonymous Crowdsourcing System atop Open
Blockchain. In 2018 IEEE 38th International Conference
on Distributed Computing Systems (ICDCS), 853–865. doi:
10.1109/ICDCS.2018.00087.
Maheswaran, R. T.; Pearce, J. P.; and Tambe, M. 2006. A
family of graphical-game-based algorithms for distributed
constraint optimization problems. In Coordination of largescale multiagent systems, 127–146. Springer.
Modi, P. J.; Shen, W.-M.; Tambe, M.; and Yokoo, M. 2005.
ADOPT: Asynchronous distributed constraint optimization
with quality guarantees. Artificial Intelligence 161(1-2):
149–180.
Nguyen, D. T.; Yeoh, W.; Lau, H. C.; and Zivan, R. 2019.
Distributed gibbs: A linear-space sampling-based dcop algorithm. Journal of Artificial Intelligence Research 64: 705–
748.
Ottens, B.; Dimitrakakis, C.; and Faltings, B. 2012. DUCT:An upper confidence bound approach to distributed constraint optimization problems. In Twenty-Sixth AAAI Conference on Artificial Intelligence.
Petcu, A.; and Faltings, B. 2005. DPOP: A scalable method
for multiagent constraint optimization. In IJCAI 05, CONF,
266–271.
Rust, P.; Picard, G.; and Ramparany, F. 2019. pyDCOP: a
DCOP library for Dynamic IoT Systems. In International
Workshop on Optimisation in Multi-Agent Systems.

Sharma, S.; Xing, C.; and Liu, Y. 2019. Privacy-preserving
deep learning with SPDZ. In The AAAI Workshop on
Privacy-Preserving Artificial Intelligence.
Tassa, T.; Grinshpoun, T.; and Zivan, R. 2017. Privacy preserving implementation of the Max-Sum algorithm and its
variants. Journal of Artificial Intelligence Research 59: 311–
349.
Triastcyn, A.; and Faltings, B. 2020. Bayesian Differential
Privacy for Machine Learning. In Proceedings of the 37th
International Conference on Machine Learning.
Vinyals, M.; Rodriguez-Aguilar, J. A.; and Cerquides, J.
2009. Generalizing DPOP: Action-GDL, a new complete
algorithm for DCOPs. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent
Systems-Volume 2, 1239–1240. International Foundation forAutonomous Agents and Multiagent Systems.
Yokoo, M. 2012. Distributed constraint satisfaction: foundations of cooperation in multi-agent systems. Springer Science & Business Media.
Yokoo, M.; Durfee, E. H.; Ishida, T.; and Kuwabara, K.
1998. The distributed constraint satisfaction problem: Formalization and algorithms. IEEE Transactions on knowledge and data engineering 10(5): 673–685.

Algorithm 1: Sequential Distributed Gibbs (Nguyen
et al. 2019)
1 Create pseudo-tree
2 Each agent xi calls INITIALIZE()

Procedure 1: INITIALIZE() (Nguyen et al. 2019)∗
1 di ← dˆi ← d ← d¯i ← ValInit(xi )iXi ← X̄i ← {(xj , ValInit(xj ))|xj ∈ Ni }∗∗3 ti ← ti ← t̄i ← 0¯
4 ∆i ← ∆i ← 0
5 if xi is root then6ti ← t∗i ← t̄∗i ← 0
7
SAMPLE()
8 end
2Procedure 2: SAMPLE() (Nguyen et al. 2019)
1 ti ← ti + 1; dˆi ← di
2 di ← Sample based on (2)P
F (d0 , d¯ )3 d¯i ← argmaxd0 ∈D¯iih hxj ,dj i∈X̄i ij i j iPˆ
4 ∆i ←
hxj ,dj i∈Xi Fij (di , dj ) − Fij (di , dj )ihP
¯i , d¯j ) − Fij (dˆi , d¯j )
¯i ←
5 ∆
F
(
d
¯
ij
hxj ,dj i∈Xi
∗ ∗6 Send VALUE(xi , di , d¯i , t , t̄ ) to each xj ∈ Ni
i

Ai

SD-Gibbs

Algorithm 1 presents the complete SD-Gibbs algorithm.

B

ProofsWe now restate the results presented in the main paper andprovide their formal proofs.

B.1

Proof of Claim 2

Claim. For two probability distributions using softmax, pi
and pj , we have, ∀i, j, ∀d ∈ D and ∀D, s.t. |D| > 1, γ ≥ 1"#
pi (xi = d, γ)2ln≤ = Γ∞
pj (xj = d, γ)γProof. Because pi and pj are soft-max distributions, wehave,(pi (xi , γ) =(pj (xj , γ) =exp(Pi (xi = dk )/γ)P
; ∀dk ∈ D
dl ∈D exp(Pi (xi = dl )/γ))exp(Pj (xj = dk )/γ)P
; ∀dk ∈ D
dl ∈D exp(Pj (xj = dl )/γ),).

Note that, Pi and Pj are the probability distributions
through SD-Gibbs sampling. With this, observe,

Procedure 3: VALUE(xs , ds , d¯s , t∗s , t̄∗s ) (Nguyen
et al. 2019)0
1 Update hxs , ds ∈ Xi i with (xs , ds )2 if xs ∈ P Pi ∪ {Pi } then3
Update hxs , d0s ∈ X̄i i with (xs , d¯s )4 else5Update hxs , d0s ∈ Xi i with (xs , d¯s )6 end
7 if xs = Pi then8
if t̄∗s ≥ t∗s andt̄∗s > max{t∗i , t̄∗i } then9d∗i ← d¯i ; t̄∗i ← t̄∗s
10else if t∗s ≥ t̄∗s andt̄∗s > max{t∗i , t̄∗i } then11d∗i ← d¯i ; t∗i ← t∗s
12
end
13
SAMPLE()14
if xi is a leaf then¯ i ) to Pi
15
Send BACKTRACK(xi , ∆i , ∆16
end
17 end#P

1. Both the numerator and denominator in r.h.s of (A2) are
positive.
2. As ln(x) is an increasing function x, this implies that r.h.sof (A2) is maximum when the numerator is maximum anddenominator is minimum.
3. The difference, Pi (xi = d) − Pj (xj = d), can be atmost 1. Therefore, numerator in r.h.s of (A2) is at-mostexp(1/γ) = e1/γ .
4. The denominator in r.h.s of (A2) is minimum when N1 is
minimum and N2 is maximum. Note that, N1 is minimum
when Pi (xi = d) = 0, ∀d, i.e., minimum N1 = |D|.
But, N2 is maximum when Pj (xj = d) = 1, ∀d, i.e.,
maximum N2 = |D| · e1/γ .
5. Using these values in (A2) completes the claim.

B.2¯ s ) (Nguyen
Procedure 4: BACKTRACK(xs , ∆s , ∆et al. 2019)¯i ← ∆¯i + ∆¯s
1 ∆i ← ∆i + ∆ s ; ∆2 if Received BACKTRACK from all children in thisiteration then¯ i ) to Pi
3
Send BACKTRACK(xi , ∆i , ∆4
if xi is root then¯ i ; Ω ← Ω + ∆i
5Ω̄ ← Ω + ∆6
if Ω ≥ Ω̄ and Ω > Ω∗ then7Ω∗ ← Ω; d∗i ← di ; t∗i ← ti
8else if Ω̄ ≥ Ω and Ω̄ > Ω∗ then9Ω∗ ← Ω̄; d∗i ← d¯i ; t̄∗i ← ti
10
end
11
SAMPLE()
12end
13 endexp(Pi (xi =d)/γ)
exp
(P
(x
=d
)/γ)
i
i
l
pi (xi = d, ·) dl ∈Dln≤ ln pj (xj = d, ·)P exp(Pj (xj =d)/γ)
dl ∈D exp(Pj (xj =dl )/γ)
exp(1/γ(Pi − Pj )))
≤ ln
(A2)
N1 /N2P
Here, N1 =dl ∈D exp(Pi (xi = dl )/γ) and N2 =
P
exp(P
(x
=
dl )/γ). Now, in (A2) observe,
j
j
dl ∈D
"

Proof of Theorem 2

Theorem. Privacy cost ct (λ) at iteration t of a samplingstage of P-Gibbs, with agent subsampling probability q, ishi(s)ct (λ) = ln Ek∼B(λ+1,q) ekΓ∞ ,where B(λ, q) is the binomial distribution with λ experiments and probability of success as q, λ ∈ N.
Proof. The result follows by substituting Γ∞ in place of theratio of normality distributions in (Triastcyn and Faltings
2020, Theorem 3).
Discussion.
1. The theorem follows from Assumption 1.
2. Unlike the analysis in (Triastcyn and Faltings 2020, TheoR
rem 3), we do not have cLt (λ) and ct (λ), as well as expectation over the data. This is because we compute the conventional differential privacy bounds, instead of BayesianDP, and thus, directly use the worst-case ratio, i.e., Γ∞ .

B.3

Proof of Theorem 3

Theorem. Privacy loss in P-Uniform for sampling d ∈ D
is 0, for any two agents i and j, D = Di = Dj and i 6= j.

Proof. For any two agents i and j, D = Di = Dj and i 6= j,from (4),!
Pr(xi ∈ D)
L = lnPr(xj ∈ D)!
Pr(xi = d)≤ max lnd∈DPr(xj = d)


1/|D|
≤ ln
= ln(1) = 0.
1/|D|This proves the theorem.