Preserving Privacy in Region Optimal DCOP Algorithms

1 Introduction

The Distributed Constraint Optimization Problem (DCOP) is a general model for solving distributed combinatorial problems that has a wide range of applications in multi-agent systems. Complete algorithms for DCOP-solving [Gershman et al., 2009; Modi et al., 2005; Petcu and Faltings, 2005] are guaranteed to find the optimal solution, but because DCOPs are NP-hard, these algorithms' worst case runtime is exponential. Thus, there is growing interest in incomplete algorithms, which may find sub-optimal solutions but run quickly enough to be applied to large problems or real-time applications [Maheswaran et al., 2004; Teacy et al., 2008; Zhang et al., 2005; Zivan et al., 2014].

Tal Grinshpoun

Ariel University Ariel, Israel talgr@ariel.ac.il

Local search algorithms, e.g., DSA [Zhang et al., 2005] and DBA [Hirayama and Yokoo, 2005], are, in general, simple incomplete algorithms that were found empirically to produce high-quality solutions. The main disadvantage of these algorithms is that they do not offer guarantees on the quality of the solutions that they produce. Thus, in the last decade, researchers have developed solution concepts that offer a balance in the trade-off between run-time efficiency (the time required to find a solution) and the guaranteed solution quality [Katagishi and Pearce, 2007; Kiekintveld et al., 2010; Maheswaran et al., 2006; Pearce and Tambe, 2007; Vinyals et al., 2011]. The guarantees are achieved by selecting a criterion according to which agents are grouped, and then producing solutions that are locally optimal in the following sense: there exists no better-quality solution that differs from the obtained solution only in the assignments of agents that are all contained in a single group. The criteria for selecting groups are defined by two parameters: k, an upper bound on the group's size, and t, an upper bound on the distance (i.e., the length of the shortest connecting path in the constraint graph) of agents in the group from the group's central agent, called the mediator. These two parameters define for each agent, serving as a mediator, a region, which is the collection of all maximal-sized connected groups of at most k agents that include the mediator and in which all agents are of distance at most t from the mediator [Vinyals et al., 2011]. Such solutions, termed region-optimal, provide under certain conditions a guaranteed bound on the ratio between their quality and the quality of an optimal solution [Pearce and Tambe, 2007; Vinyals et al., 2011].

Privacy is one of the main motivations for solving constraint problems in a distributed manner. The term privacy is quite broad, a fact that gave rise to several categorizations of the different types of privacy [Faltings et al., 2008; Greenstadt et al., 2007; Grinshpoun, 2012]. In this paper we relate to the categorization of Faltings et al. [2008] that distinguishes between agent privacy, topology privacy, constraint privacy, and decision privacy. (For full definitions of those notions the reader is referred to [Faltings et al., 2008] or [L´eaut´e and Faltings, 2013]; we briefly recall those definitions in Section 4.)

The first attempt to produce a more secure region-optimal algorithm (actually k-optimal) was conducted by Greenstadt [2009]. While the ideas presented in that extended abstract were preliminary, we share the motivation and take herein a further step in that direction.

We describe here an algorithmic framework called RODA (Region-Optimal DCOP Algorithm) that generalizes, for didactic purposes, existing local search algorithms that issue solutions with quality guarantees, e.g. the KOPT algorithm [Katagishi and Pearce, 2007], or the DALO algorithm [Kiekintveld et al., 2010]. RODA is a new formalization rather than a new algorithm; it is an umbrella setup that generalizes the main existing region-optimal algorithms, and allows us to include in our study of privacy the region selection methods of all existing algorithms of the region-optimality family [Katagishi and Pearce, 2007; Kiekintveld et al., 2010; Vinyals et al., 2011].

We then proceed to present P-RODA, a privacy-preserving implementation of RODA. Hence, P-RODA includes a privacy-preserving implementation of a general regionoptimal algorithm, which can implement the region traversing methods of KOPT, DALO, and any other algorithm from the region-optimality family, and follow either a synchronous or an asynchronous operation mode. P-RODA is a perfect simulation of RODA, in the sense that given the same random choices (some of the algorithms that fall under the RODA framework use randomness), both RODA and P-RODA will go through the same sequence of intermediate assignments and will issue the same output after a given number of iterations. However, centralized computations in RODA that may leak private information are replaced in P-RODA with distributed computations that prevent such information leakage. Thus, our framework securely achieves k-size-optimality, t-distance-optimality, or any combination of the two, and finds solutions with the same guarantees on the distance from the optimum as proved in [Kiekintveld et al., 2010; Pearce and Tambe, 2007; Vinyals et al., 2011].

Terminology and notations. A Distributed Constraint Optimization Problem (DCOP) [Hirayama and Yokoo, 1997] is a tuple hA↪X↪D↪Ri where A is a set of agents A1↪A2↪ ▷ ▷ ▷ ↪An, X is a set of variables X1↪X2↪ ▷ ▷ ▷ ↪Xn 1 , D is a set of finite domains D1↪D2↪ ▷ ▷ ▷ ↪Dn, and R is a set of binary relations (constraints). Each variable Xi takes values in the domain Di, and it is held by a single agent. A constraint Ci↪j 2 R defines a non-negative cost for every possible value combination of Xi and Xj, for some 1  i < j  n. A value assignment is a pair including a variable and a value from that variable's domain. A complete assignment consists of value assignments to all variables in X . The objective is to find a complete assignment of minimal cost. The constraint graph is a graph whose nodes are the n agents (or variables) where two nodes are connected by an edge if the two corresponding variables are constrained. We shall refer to such pairs of agents or variables as neighbors. For every agent Ai, 1  i  n, we let Nt(Ai) denote the set of all agents whose distance to Ai in the constraint graph is at most t. The special case of the distance-1 neighborhood will be denoted N(Ai) := N1(Ai).

1 We make a standard assumption that each agent holds exactly one variable.

2 Region Optimal DCOP Algorithms

Region-optimality is a concept that is based on assigning agents to groups, such that each group of agents has one agent that performs as its mediator. For a given agent Ah, its region Rh is the collection of all groups of which Ah can serve as the mediator. A region is commonly defined by two parameters, k and t:

Definition 1 The region Rh = R(k↪t) h of agent Ah is the collection of all subsets of agents B ⇢ A such that: (a) Ah 2 B, (b) ♣B♣  k, (c) B ✓ Nt(Ah), (d) the restriction of the constraint graph to B is connected, and (e) there exists no proper superset of B that complies with all previous conditions.

Definition 2 Given a DCOP with n agents and the entire set of corresponding regions R = ¶R1↪R2↪ ▷ ▷ ▷ ↪Rn♦, a regionoptimal solution to this DCOP is a complete assignment whose cost cannot be reduced by changing the value assignments only to agents that are all included in a single group that belongs to some region in R.

Protocol 1 describes RODA, an algorithmic framework that generalizes existing region-optimal algorithms [Katagishi and Pearce, 2007; Kiekintveld et al., 2010; Vinyals et al., 2011]. We proceed to explain it in detail. Hereinafter, when we speak of a general agent we denote it by Ai; however, when we speak of that agent as a mediator we denote it by Ah, 1  i↪ h  n.

RODA starts with an initialization phase (Step 1), in which each agent Ah gathers information from agents in its tdistance neighborhood Nt(Ah); the collected information is needed for Ah to determine its region Rh (Definition 1), and later on to function as the mediator. That information includes: (a) the domains of variables controlled by agents in that neighborhood; and (b) the constraints that agents in that neighborhood have with all their neighbors (these constraints can involve agents of distance at most t + 1 from Ah).

After the initialization phase ends, the local search phase starts. First, each agent selects an initial assignment to its variable (Step 2). Then, the algorithm performs a fixed number L of improvement iterations. In the `th iteration (Steps 310), some of the agents will update their current assignment from a`-1 i to a`i towards reducing the overall cost. After all agents initiate the next assignment to be like the current one (Step 4), every agent Ah selects a group A`h from its region Rh (Step 5); the selection can be random or one that follows some systematic rule. In the next steps Ah will act as the mediator of the selected group.

Then (Step 6), each mediator Ah gathers the current assignments of all agents in A`h as well as of their direct neighbors (some of whom could be outside A`h ). With that information, Ah finds the locally best assignments β for the agents in its group A`h (Step 7). Then, Ah computes the improvement ∆`h in the overall cost, in case the current assignments in its group are replaced with the found locally best ones (Step 8). It broadcasts its findings (β and ∆`h ) to its group (Step 9). Later on we explain in detail how Ah computes β for its group and the corresponding ∆`h .

Next, a contest takes place between neighboring groups (groups that include agents that are neighbors). Every group which is a local winner (namely, the improvement which it offers is greater than the improvement offered by any of its neighboring groups, where ties are broken by the groups' indices) updates its current assignments to the found local optimal ones β (Step 10). After conducting the pre-set number of iterations L, the agents set their variables to the last assignment found (Step 11).

Note that our description of RODA (and P-RODA) adopts the synchronous operation of KOPT [Katagishi and Pearce, 2007]. The adaptation to an asynchronous operation as in DALO [Kiekintveld et al., 2010] is simple and omitted due to space limitation.

We now revisit Steps 7 and 8 and provide the necessary technical details. Let

• ÷ β`-1 h 2 D`h be the current partial assignment to the variables controlled by A`h , and ↵`-1 h 2 N `h be the partial assignment that was received by the agents in A`h from their neighbors outside A`h . (β`-1 h and ↵`-1 h consist of the assignments that Ah retrieves in Step 6.)
• ÷ D`h := QAi2A`h Di be the Cartesian product of the domains of all variables of A`h , and N `h := QAj2(SAi2A`h N(Ai))∩A`h Dj be the Cartesian product of the domains of all variables that correspond to agents outside A`h that have neighbors in A`h .

Then, Ah finds a β 2 D`h that minimizes the local cost

Here, the notation β♣Di denotes the Di-entry of the tuple β. The first term on the right-hand side of Eq. (1) is the sum of constraints that involve two agents inside the group A`h . The second term is the sum of constraints that involve one agent in A`h and one external agent. Finally, given the found optimal tuple β, Ah computes

which is the improvement in the local cost for A`h if they replace the current local partial assignment β`-1 h with β.

3 Private RODA

In this section we explain how to execute the RODA algorithm in a privacy-preserving manner. To that end, we follow the algorithmic flow of Protocol 1 and explain, for each step in that protocol, how to execute it in a privacypreserving manner. We make the standard assumption (e.g. [Grinshpoun and Tassa, 2014; L´eaut´e and Faltings, 2013; Tassa et al., 2015]) that the agents are semi-honest, which means that they respect the protocol and do not form coalitions.

The main effort in transforming RODA into a private algorithm (to which we refer hereinafter by P-RODA) lies in converting the centralized computations that are carried out

Protocol 1 RODA

• 1: The agents exchange local information (see details in the text). 2: Ai randomly selects a0i 2 Di, 1  i  n.
• 3: for ` = 1↪ ▷ ▷ ▷ ↪L do
• 4: Ai sets a`i = a`-1 i , 1  i  n.
• 6: Ah receives a`-1 j fromAj for all Aj 2 SAi2A`h N(Ai).
• 5: Ah selects A`h 2 Rh, 1  h  n.
• 7: Ah finds a locally optimal tuple of assignments, β 2 D`h := QAi2A`h Di, for the variables controlled by its group A`h.
• 8: Ah computes ∆`h, the cost improvement if all agents in A`h update their assignment to the one given by β.
• 9: Ah informs all agents in A`h about the found β and ∆`h.
• 10: For every 1  h  n: If A`h wins the contest against A`h0 for all groups A`h0 that are neighboring to A`h, then 8Ai 2 A`h, Ai sets a`i according to β. (Winning occurs if ∆`h > ∆`h0 or if ∆`h =∆`h0 and h < h0 .)
• 11: Ai sets Xi := aLi , 1  i  n.

by the mediator (especially in Steps 7 and 8) to distributed computations that are performed by all agents in the group using secure multi-party protocols. In RODA, in order to allow the mediator to perform the centralized computations for its group, it had to receive in the initialization phase (Step 1) and then in each iteration (Step 6) private information from agents that are at distance at most t + 1 from it. As such exchange of data contradicts privacy, we replace it in P-RODA with a much reduced exchange of data and then we modify the subsequent steps so that they are performed by all agents in the group using secure multi-party protocols. In what follows, we provide explanations only on those steps in Protocol 1 that have to be modified in P-RODA; steps that we do not mention below remain the same.

• ÷ Step 1 (Initialization). This phase is performed in PRODA in a reduced manner. Every agent Ah, 1  h  n, learns only topological information in the form of the restriction of the constraint graph to Nt(Ah). This is sufficient for Ah to determine its region Rh. All the other information that Ah collected at this phase in RODA from its neighbors - the domains of variables for all agents in Nt(Ah), and the constraint information relating to each pair of agents of which one agent is fromNt(Ah) - is not needed in P-RODA, since in P-RODA we replace the centralized computations that Ah did as a mediator in RODA with secure multi-party protocols.
• ÷ Step 6 (Assignment propagation). While in RODA every mediator learns the current assignment data for all agents in its group and their neighbors (which means that it may learn assignment data of agents which are at distance as far as t+1 from it), P-RODA performs a much reduced propagation of current assignment data: every agent Ai sends its current assignment a`-1 i only to its direct neighbors (N(Ai) ∩¶Ai♦).
• ÷ Step 7 (Locally optimal assignments). This step includes the computations that are hardest to perform securely, whence we postpone the discussion of their private execution to Section 3.1. The sub-protocol described in Section 3.1 ends with all agents in the group learning the currently optimal β; hence, that protocol accomplishes Step 7 and part of Step 9 in RODA. In P-RODA, as opposed to RODA, it is essential to have all agents in the group know β before proceeding to

computing ∆`h in Step 8, because that computation is done in P-RODA by a distributed protocol involving all agents.

• ÷ Steps 8-9 (Local improvements). While in RODA it was the mediator who computed ∆`h , and then informed all agents in its group about the result, in P-RODA all agents in the group compute it jointly and privately using a secure summation protocol. Consider the local cost ˆ C(β↪ ↵`-1 h ), as defined in Eq. (1); it can be broken into the following sum,

where

It is easy to see that ∆`h = PAi2A`h ∆`h (i), where ∆`h (i) := γi(β`-1 h ↪ ↵`-1 h ) - γi(β↪ ↵`-1 h ) is a value known to Ai 2 A`h (because Ai knows β from Step 7 and it also knows the relevant components of β`-1 h and ↵`-1 h from the reduced Step 6 in P-RODA). Therefore, ∆`h can be computed by all agents in A`h using a secure summation protocol.

However, secure summation protocols usually reveal the final sum to at least one of the agents, what might hinder constraint privacy. Therefore, we perform the secure summation protocol with a small "twist" so that instead of issuing the final sum∆`h , it issues two shares, denoted sh and s0h , that distribute uniformly at random on ZS for some large integer S, and ∆`h = sh + s0h mod S. The mediator will get sh while all other members of its group will get s0h . Using such secret sharing implies that, under the semi-honestness assumption, none of the agents learns any information on ∆`h .

• ÷ Step 10 (Contest). While in RODA, the difference ∆`h was known to the mediator, whence it was easy for mediators of neighboring groups to compare those values in order to determine which of the groups are winners in this iteration (and, consequently, get to update their local assignments), in P-RODA the value of ∆`h is shared by the mediator and any other single member of its group. Therefore, we proceed to describe the manner in which the contest of Step 10 can be carried out in P-RODA.

First, the agents in each group A`h engage in a secure union protocol [Tassa and Gudes, 2012] for finding the set of all neighboring groups; we omit the details of that procedure. Then, each pair of neighboring groups, say A`h and A`m, where h < m, performs the following verification:

• ÷ Ah and Am select "deputies" in their respective groups, A0h 2 A`h ∩ ¶Ah♦ and A0m 2 A`m ∩ ¶Am♦.
• ÷ Ah sends its share in ∆`h , sh, to Am.
• ÷ A0h sends (sh - sm + s0h ) mod S to A0m.
• ÷ Am sends (sh - sm) mod S to A0h .
• ÷ A0m computes (sh-sm+s0h -s0m) mod S. This value equals (∆`h -∆`m) mod S.
• ÷ A0m infers from the last difference whether ∆`h ≥ ∆`m or not. If so, it informs Ah who informs all agents in A`h that their group won. Otherwise, it informs all agents in A`m that their group won. (Notice that, as in RODA, in case of a tie, the group with the lower index wins.)

For the sake of achieving constraint privacy (see Theorem 2 later on), it is important that the agent who gets the difference (∆`h -∆`m) mod S will not be a member of both A`h and A`m. Indeed, as shown by Kiekintveld et al. [2010], it is possible to select the deputies A0h and A0m so that at least one of them is not a member of both A`h and A`m.

3.1 Private Computation of the Best Partial Assignment for a Group of Agents

Overview

Here we discuss the privacy-preserving execution of Step 7 in RODA. In that step, the agents within each group need to solve a local DCOP. Hence, one possibility would be to invoke an existing privacy-preserving complete algorithm for that purpose. Two recent studies proposed such algorithms: Grinshpoun and Tassa [2014] proposed P-SyncBB, a privacypreserving version of the SyncBB algorithm; and L´eaut´e and Faltings [2013] proposed three privacy-preserving versions of DPOP: P-DPOP(+) , P3◁2 -DPOP(+) , and P2 -DPOP(+) .

One may implement any of those four algorithms in the framework of P-RODA for a privacy-preserving execution of Step 7 (after a simple modification in order to take into account also constraints vis-a-vis agents outside the group). However, all these algorithms have their shortcomings: PSyncBB incurs a large number of communication rounds and messages, and disrespects decision privacy; P-DPOP(+) and P3◁2 -DPOP(+) ensure only partial constraint privacy; and P2 - DPOP(+) is very inefficient (in terms of run-time). Hence, we proceed to describe here a novel protocol for the secure solution of the local DCOP within a group. The protocol can be executed efficiently only when the Cartesian products of the domains of the group's variables, D`h , are not too large. Thus, we suggest to use it whenever feasible, and when it is not to use one of the above mentioned algorithms.

A Statement of the Computational Problem

Given ↵`-1 h 2 N `h , the partial assignment that was received by the agents in A`h from their neighbors outside A`h (Step 6 in P-RODA), the agents in A`h wish to compute a tuple β 2 D`h = QAi2A`h Di that minimizes the local cost ˆ C(β↪ ↵`-1 h ), Eq. (1), in a privacy-preserving manner. (Note that ↵`-1 h is not known in its entirety to any single agent in A`h ; each agent in the group knows only those components in ↵`-1 h that correspond to its direct neighbors outside the group.)

Arranging the Partial Costs in a Tensor

For simplicity, let us assume that A`h = ¶A1↪A2↪ ▷ ▷ ▷ ↪Ak♦. Assume further that all domains Dj, 1  j  n, are publicly ordered: Dj = ¶vj0 ↪ vj1 ↪ ▷ ▷ ▷ ↪ vj ♣Dj♣-1 ♦. Then each Ai 2 A`h can construct a private k-dimensional tensor Gi such that for any multi-index [i1↪ ▷ ▷ ▷ ↪ ik], where 0  ij 

♣Dj♣ - 1, 1  j  k, the corresponding entry in the tensor is Gi[i1↪ i2↪ ▷ ▷ ▷ ↪ ik] = γi(β↪ ↵`-1 h ), where β = (v1 i1 ↪ ▷ ▷ ▷ ↪ vk ik ), and γi is as defined in Eq. (4). According to Eq. (3), the sum of these tensors is a tensor G in which G[i1↪ i2↪ ▷ ▷ ▷ ↪ ik] = ˆ C(β↪ ↵`-1 h ), for β = (v1 i1 ↪ ▷ ▷ ▷ ↪ vk ik ). To summarize: each of the agents Ai 2 A`h holds a private tensor Gi. They jointly wish to compute the multi-index of the entry in G = Pki=1 Gi which is minimal. That multi-index reveals the required β. The protocol below performs that.

The Protocol

Let E : GP ! GC be a public-key encryption function from some additive group of plaintexts GP to a multiplicative group of ciphertexts GC. Assume that: (a) its decryption key is known only to the mediator Ah; (b) it is probabilistic (i.e., encryption depends also on a random string); and (c) it is homomorphic (i.e., 8m↪m0 2 GP , E(m+m0 ) = E(m) · E(m0 )). Paillier cryptosystem [Paillier, 1999] is an example of such an encryption function. Then, the protocol goes as follows:

1. The mediator Ah selects a deputy A0h .
2. Agent Ai, for all 1  i  k, sends to A0h the componentwise encryption of its private tensor E(Gi).
3. A0h computes the component-wise product Qki=1 E(Gi). Owing to the homomorphic property, A0h gets as a result the encrypted tensor E(Pki=1 Gi) = E(G).
4. A0h selects a random c 2 GC and computes c · E(G). Since c = E(r) for some random r 2 GP , it holds that c · E(G) = E(r) · E(G) = E(G+r) (the multiplication with the scalar c and the addition with the scalar r are done component-wise).
5. A0h selects a secret and random permutation ⇡ on D`h = Qki=1 Di and then sends to the mediator Ah the permuted tensor ⇡(E(G + r)) = E(⇡(G + r)).
6. Ah decrypts and recovers the tensor ⇡(G+ r).
7. Ah informs A0h of the position in ⇡(G+ r) of the minimal entry.
8. A0h uses ⇡-1 to recover the original multi-index of the minimal entry. If it is [i1↪ i2↪ ▷ ▷ ▷ ↪ ik] then β = (v1 i1 ↪ ▷ ▷ ▷ ↪ vk ik ). A0h informs all group members about β.

A note about finding the minimal entry: We view the entries of G (and ⇡(G)) as integers, as they describe local costs of tuples in D`h . We wish to find a minimal entry in ⇡(G). However, the entries in ⇡(G+ r) = ⇡(G) + r are the result of addition modulo q (and not an addition of integers). So such an addition may create a wrap around which, usually, will prevent Ah from finding a minimal entry in ⇡(G). However, as q is typically a very large integer, and in particular larger than twice the maximal entry in ⇡(G), Ah can infer from ⇡(G) + r the location of a minimal entry in ⇡(G).

3.2 P-RODA Simulates RODA

An important observation about the relation between RODA and P-RODA is the following.

Theorem 1 P-RODA perfectly simulates RODA in the following sense: When the two algorithms are executed on the same DCOP setting, then assuming that both start with the same random initial assignment (a01 ↪ ▷ ▷ ▷ ↪ a0n ) and that in each iteration every mediator selects the same group from its region in P-RODA as it does in RODA, then the sequence of intermediate assignments (a`1 ↪ ▷ ▷ ▷ ↪ a`n ), ` ≥ 1, that the two algorithms produce will be the same.

A consequence of Theorem 1 is that all convergence guarantees for RODA, as implied by the proofs in [Kiekintveld et al., 2010; Pearce and Tambe, 2007; Vinyals et al., 2011], equally apply to P-RODA.

4 Privacy Discussion

In this section we discuss the privacy of P-RODA with respect to the common notions of privacy in this field [Faltings et al., 2008; L´eaut´e and Faltings, 2013]. Due to space limitations, we omit proofs.

Theorem 2 P-RODA maintains constraint privacy in the sense that no agent may use its view during P-RODA's execution in order to infer binary constraints of other agents.

Theorem 3 P-RODA respects partial decision privacy: it leaks to any Ai only the final decisions of agents in N(Ai) that were in the same group with Ai in the last iteration; the final decisions of all other agents remain unknown to Ai.

We conclude with a note about agent and topology privacy. Agent privacy is respected when no agent can discover the identity or even the existence of non-neighboring agents [L´eaut´e and Faltings, 2013, Definition 4]. Topology privacy is respected when no agent is able to discover the existence of topological constructs in the constraint graph, such as nodes (i.e. variables) or edges (i.e. constraints), unless it owns a variable involved in the construct [L´eaut´e and Faltings, 2013, Definition 5]. It seems that RODA is inconsistent with either of those two privacy notions in the sense that an algorithm that achieves one of those privacy goals will essentially differ in its operation from RODA. Indeed, for any t > 1, each mediator has to gather around it a group of agents in a distance up to t from it. Clearly, such a group reveals to the mediator the existence of agents that are not direct neighbors. Moreover, the group must be connected, so that even if the group is selected by a trusted third party, the mediator learns topological properties of the graph which topology privacy forbids.

5 Efficiency Analysis

We analyze here the computational overhead of P-RODA with respect to the baseline RODA. We count only encryption and decryption operations, since the other performed operations (e.g. random numbers' generation, additions, or multiplications) have computational costs that are orders of magnitude smaller than those of the cryptographic operations.

Let us fix an agent Ai, 1  i  n. We denote by p`i the number of groups to which it belongs in the `th iteration, and by H` i := ¶h`i↪j : 1  j  p`i ♦ the indices of those groups. Then the excessive computational cost for Ai is to perform Pp`i j=1 ♣D`h`i↪j ♣ encryptions. In addition, as Ai is the mediator of its own group, A`i , it needs to perform also ♣D` i ♣ decryptions. (Those costs are incurred by the protocol in Section 3.1.) Since an agent may be selected for groups only of mediators within distance t from it, and since every group has at most k agents, we infer the following.

Proposition 4 The computational overhead in each iteration of P-RODA is bounded by dk ntCE + dkCD where d := max1in ♣Di♣ is the maximal domain size, nt := max1in ♣Nt(Ai)♣ is the maximal size of a t-neighborhood, and CE and CD are the costs of encryption and decryption, respectively. In particular, the computational overhead does not depend on the number of agents n.

To realize the actual time it will take P-RODA to run we followed the simulated time approach [Sultanik et al., 2008] by measuring the time of atomic operations performed in the algorithm and then counting the non-concurrent times these operations are performed. We measured the run-times of encryption and decryption by averaging multiple runs of the common Java implementation of the Paillier cryptosystem 2 on a hardware comprised of an Intel i7-4600U processor and 16GB memory. Our tests show that encryption takes at most CE = 2 msec, while decryption takes at most CD = 3 msec.

According to Proposition 4 the factors that impact the computational overhead are k, d, and the topology of the tdistance neighborhoods. As the dependence on d is polynomial while the dependence on k is exponential we focus here on the latter dependence. In order to understand the effect of the neighborhood's topology, we consider three classic types of networks - random networks (Erd˝os-R´enyi model [1959]), scale-free networks (Barab´asi-Albert model [1999]), and small-world networks (Watts-Strogatz model [1998]).

Figure 1 depicts the computational overhead as a function of k in the three network types, when running the algorithm for L = 50 iterations. In this setup we fix the number of agents to n = 100, the constraint density to p = 0▷1, the domain sizes to d = 5, and the upper bound of the distance to t = 1, and vary k = 3↪ ▷ ▷ ▷ ↪ 8. Figure 1 confirms the exponential dependency on k, whence for high values of k one may need to switch in Step 7 to another complete DCOP private algorithm such as P-SyncBB. Another interesting phenomenon is the higher computational overhead in scale-free networks. This is not surprising, since scale-free networks consist of several highly-connected hubs, and that directly affects nt. Nevertheless, when using higher distance values (t ≥ 3), scale-free networks exhibit similar performance to that of the other network types. Varying the distance t has almost no effect on the performance of random and small-world networks, and therefore these results are omitted.

Although not directly affecting the computational overhead, an increase in the number of agents n might potentially affect the topology of neighborhoods, and lead to an indirect effect on the computational overhead. We therefore use the same setting of the previous experiment, but now we fix k = 3 and vary n = 100↪ ▷ ▷ ▷ ↪ 1000. Figure 2 confirms that the problem's size has almost no effect on the computational overhead, except for the case of scale-free networks in which nt does increase when n increases and, consequently, we witness a moderate increase in the computational overhead.

2 http://www.csee.umbc.edu/ kunliu1/research/Paillier.html

6 Conclusion

Region optimality is an important concept that offers a balance between run-time efficiency and guarantees on the solution quality. Privacy loss is a major drawback of regionoptimal algorithms, yet, to the best of our knowledge, no secure protocol for finding region-optimal solutions has been proposed to date. In this paper we proposed P-RODA, an algorithmic framework that converges to region-optimal solutions while preserving constraint privacy and partial decision privacy. The underlying algorithm RODA generalizes the algorithms in the region-optimality family, such as KOPT [Katagishi and Pearce, 2007] and DALO [Kiekintveld et al., 2010]. Privacy is achieved chiefly by using secret sharing and homomorphic encryption. P-RODA is scalable with respect to the number of agents n, but it is more suitable for regions with a small group size k.

As future work we aim at improving the privacy guarantees of P-RODA. One such improvement could be the obtaining of full decision privacy. Currently, P-RODA reveals to every agent the final decision of all direct neighboring agents that happened to be with that agent in the same group in the last iteration. It is possible to achieve full (rather than partial) decision privacy by enhancing the secure implementation of Step 7 in P-RODA so that each agent learns only its component in the optimal local assignment β and not all of the tuple β, as is the case now. Similarly, it might be possible to achieve assignment privacy by replacing the transfer of current assignment data in Step 6 of P-RODA with secure multi-party protocols. Clearly, such enhancements of privacy come with a price tag, as they entail greater computational and communication costs.

Acknowledgment: We thank Vadim Levit for helping us in the experimental evaluation.