Keywords

1 Introduction

A wide range of real-world systems can be modelled as dynamic sets of interconnected nodes [14, 20]. The adequate management of complex networked systems is becoming critical for industrialized countries, since they keep growing in size and complexity. An important sub-class involves autonomous, self-interested entities (e.g. drivers in a transportation network). The self-interested nature of the entities in the network causes the network to deviate from socially-optimal behaviour. This leads to problems related to unavailability and inefficient use of resources.

Different fields of research are working on these challenges, but, so far, with only mixed success. Optimization techniques are especially suited to address large-scale systems with an underlying network structure, usually with a “divide and conquer” approach [22, 24]. However, their performance severely decreases as the complexity of the system increases [21], and with the presence of autonomous entities which deviate from the globally optimal solution, thus harming the social goal. Negotiation techniques are known to be useful to handle self-interested behaviour [1], but scale poorly with problem size and the intricacies of interdependencies [15].

Belief propagation (BP) is a message-passing technique which has been successfully used to solve optimization problems by modelling problem constraints using a graph structure [9]. In our previous work, we used it to improve the scalability of an agent self-preference exploration during an auction-based negotiation process over preference spaces built of hypercube-shaped constraints [18]. In a more recent work [11], the concept was extended to utility hypergraphs, enabling negotiations with more complex shaped constraints. These works contributed to greatly enhance scalability in complex negotiations by modelling utilities as graphs, but did not explore problems which were graph-structured by themselves. In addition, these works used belief propagation to explore the preferences of each agent separately, thus keeping the BP process as a local optimization process, using it to assist in the local search for solutions during the negotiation process. This is coherent with the usual use of BP in cooperative optimization settings.

Our goal is to provide a novel perspective of the multi-agent negotiation process as a competitive belief propagation, which can help to efficiently handle conflicts in network-structured settings. In this paper, we contribute to this goal in the following way:

  • We define the negotiation problem as a factor graph \(F_P\) and the negotiation process as a competitive belief propagation over the factor graph, and we show how the model suits well-known negotiation settings in the literature (Sect. 2).

  • We apply this model to a challenging, network structured complex negotiation setting: Wi-Fi channel negotiation (Sects. 3.1 and 3.2).

  • We propose a distributed, scalable approach to use competitive belief propagation to solve the problem (Sect. 3.3).

To test our hypothesis and evaluate the validity of our contribution, we have conducted a set of experiments in a realistic scenario setting (Sect. 4). Our experiments show that the belief propagation approach outperforms a classical nonlinear negotiation approach in terms of solution efficiency and performance. The last section summarizes our contributions and sheds light on future challenges and lines of research.

2 Negotiation as Competitive Belief Propagation

As we said above, our goal is to provide an alternative perspective on automated negotiation as a competitive belief propagation process, so that this process can be mapped naturally to network structured problems. To understand the rationale of this novel perspective, let’s see a simple example of the correspondence between the two problems. Consider the classic negotiation game between a buyer agent B and a seller agent S over the price p of an item, and let us assume that they are going to use an alternating offer protocol for the negotiation [7]. Let \(b^0_B\) and \(b^0_S\) the initial agent offers (or bids). For a typical bargaining scenario, we will have \(b^0_B<b^0_S\), that is, the buyer wants to pay less than the seller wants to get. During the negotiation, we will expect to see a progressive relaxation of the agents’ initial positions (i.e. \(b^t_B\ge b^{t-1}_B\) and \(b^t_S\le b^{t-1}_S\)) until we reach the point of agreement (i.e. \(b^t_B=b^t_S\)) or the deadline expires. The relaxation speed of the agents’ positions will depend on the different agent bidding strategies (e.g. boulware, conceder, tit-for-tat [2]). This process can easily be seen as a belief competition. Both agents start out with different beliefs about how much they want to give or receive for the item (\(b^0_B\) and \(b^0_S\), respectively), and these beliefs get updated through the subsequents iterations of the protocol until an agreement is reached (i.e. the beliefs of both agents match) or the deadline expires. This belief competition perspective can be formalized into a factor graph and a belief propagation process [9], as we will see in the following subsection.

2.1 Negotiation as a Factorized Optimization Problem

Belief propagation (BP) techniques have been shown as successful heuristics for solving factorized optimization problems, that is, problems P of the form

$$\begin{aligned} minimize \sum _{i \in V}{\varPhi _i(x_i)}+\sum _{c \in C}{\varPsi _c(x_c)} \end{aligned}$$
(1)

where V is a finite set of variables and C is a finite collection of subsets of V representing constraints. \(\varPhi _i\) and \(\varPsi _i\) are real-valued functions called, respectively, variable functions and factor functions, representing the impact on the objective function of the value of each independent variable, and of combinations of variable values (i.e. interdependencies between variables).

We can easily map to this kind of problem most of the utility or social welfare functions used in automated negotiation, by choosing adequate expressions for the \(\varPhi _i\) and \(\varPsi _i\) functions. For instance, in the trivial buyer-seller negotiation example above we could choose

$$\begin{aligned} \varPhi _B = {\left\{ \begin{array}{ll} x-R_B &{} \text {if } x\le R_B\\ \infty &{} \text {otherwise}\\ \end{array}\right. }\qquad \qquad \varPhi _S = {\left\{ \begin{array}{ll} R_S-x &{} \text {if } x\ge R_S\\ \infty &{} \text {otherwise}\\ \end{array}\right. } \end{aligned}$$
$$\begin{aligned} \varPsi (x_B,x_S) = {\left\{ \begin{array}{ll} 0 &{} \text {if } x_B=x_S\\ \infty &{} \text {otherwise}\\ \end{array}\right. } \end{aligned}$$

where \(R_B\) and \(R_S\) are the reservation values of buyer and seller, respectively. In this trivial case, each \(\varPhi _i\) functions account for the preferences of agent i, and the \(\varPsi \) function represents that a disagreement is the worst possible outcome. Other \(\varPsi \) functions could be chosen depending on the desired outcome of the negotiation. For instance, we could choose a \(\varPsi \) function representing a Clarke tax (\(\varPsi (x_B,x_S)=\frac{x_S-x_B}{2}\)), or a fairness metric such as the one defined in [8].

A similar translation can be done in a linear-additive multi-issue negotiation setting, such as the one described in [6, 17]. Here there would be a \(\varPhi _{a,i}(x_{a,i})\) function for each agent a and issue i, corresponding to the valuation function of each agent for each issue. \(\varPsi _i\) functions would be defined for each issue depending on the desired outcome of the negotiation. For instance, to introduce the aforementioned fairness measure we could define:

$$\begin{aligned} \varPsi (x_B,i,x_S,i) = {\left\{ \begin{array}{ll} \frac{(\varPhi _B(x_B)+\varPhi _S(x_S))^2+(\varPhi _B(x_B)-\varPhi _S(x_S))^2}{2} &{} \text {if } x_B=x_S\\ \infty &{} \text {otherwise}\\ \end{array}\right. } \end{aligned}$$

Apart from the \(\varPhi \) and \(\varPsi \) functions, we can also derive the corresponding factor graph \(F_P\) of the factorized optimization problem P. This is a bipartite graph with a node per \(\varPhi \) and \(\varPsi \) function, and links between nodes which share variables.

2.2 The Negotiation Process as Belief Propagation

Once the negotiation problem has been expressed as a factorized optimization problem \(F_P\), we can solve it using belief propagation techniques. In particular, we use the min-sum version of BP described in [9], which we reproduce in Algorithm 1 for convenience.

figure a

The min-sum algorithm is a message-passing algorithm which defines a number of messages \(m^t_{X\rightarrow Y}\) to be passed among nodes of the factor graph \(F_P\) throughout the different iterations of the algorithm. We turn the algorithm into a multi-agent negotiation protocol by mapping the graph nodes to agents. In our example, we would map to each negotiating agent A and B the nodes corresponding to its own beliefs/preferences about the issue values, and the nodes corresponding to the \(\varPsi \) functions (in this case, incentivizing fairness) would be mapped to a mediator agent M. The negotiation would progress via message passing between factor and variable nodes assigned to different agents at each iteration.

3 Scaling Up: BP in the Wi-Fi Negotiation Problem

In our previous work, we proposed Wi-Fi channel assignment as a realistic and challenging benchmark for complex automated negotiations [3, 4]. In this setting, different Wi-Fi providers, acting as agents, have to collectively decide how to distribute the channels used by their access points (APs) in order to minimize interference between nodes and thus maximize the utility (i.e., network throughput) for their clients, which will be different kinds of wireless devices (WDs). A Wi-Fi negotiation scenario will be characterized by:

  • A Wi-Fi association graph G, which is a geometric graph (i.e., nodes have specific positions in space) with two kinds of vertices, representing APs and WDs. Edges in the graph represent the association of a particular WD to an AP. In Fig. 1 we show a graphical representation of a scenario with 26 APs and 400 WDs.

  • An interference graph I, which includes the same vertices as G in the same positions in space, but in this case edges represent potential interferences between devices, and edge weights account for the intensity of these interferences. For detailed description of the Wi-Fi interference model in this setting, the reader is advised to check [13]. The corresponding graph for the aforementioned scenario can be seen in Fig. 2.

  • A mapping of access points to different providers, which will be the negotiating agents. The goal of each agent will be to minimize the interference suffered by its APs and their associated WDs. In this paper, we will assume there are two providers.

Fig. 1.
figure 1

Wi-Fi association graph G for an scenario with 26 APs and 400 wireless devices.

Full size image
Fig. 2.
figure 2

Wi-Fi interference graph I for an scenario with 26 APs and 400 wireless devices.

Full size image

This is a particularly interesting problem, since it belongs to the family of Frequency Assignment Problems (which has been extensively studied from the perspective of discrete optimization) and it is strongly related to the prominent mathematical graph coloring problem [23] and to distributed constraint optimization models [10]. In the following, we will formally describe the negotiation problem, and the translation of the problem to the belief propagation model.

3.1 Negotiation Domain

For the scope of this work, we assume a multiattribute negotiation domain, where a deal or solution to the problem is defined as the set of attributes (issues), and each one of them can be in a certain range. In our case, for a channel assignment problem with \(n_{AP}\) access points, a solution or deal S can be expressed as \(S=\{s_i|i\in 1,...,n_{AP}\}\), where \(s_i\in \{1,\ldots ,11\}\) represents the assignation of a Wi-Fi channel to the i-th access point.

As stated above, we assume that there are two network providers or agents (commonly Internet Service Providers, ISPs), thus APs belong to one of the agents. Each provider only has control over the channel assignment for its own access points. According to this situation, \(P=\{p_1, p_2\}\) will be the set of agents that will negotiate the channel assignment. We find adequate to focus in the two-provider case because there are more works in complex bilateral negotiations than for the multilateral case (three or more agents).

Finally, each one of these agents \(p_i\) will compute its utility \(U_{p_i}\) for a certain solution according to the model described in [4, 13]. As we showed in our previous works, the problem settings (high cardinality of the solution space and attribute interdependence) will make the utility functions highly complex, with multiple local optima.

3.2 Channel Negotiation as a Factorized Optimization Problem

Given that \(U_{p_i}\) depends on the sum of the interferences suffered by their APs and their associated WDs, and that those interferences are caused by nearby APs and WDs using the same channel to transmit, intuitively we need to avoid using the same (or similar) channels in nearby devices. More specifically, we have to avoid using “close” channels in devices whose associated vertices in the interference graph I are connected, specially if the weight of the connecting edge is high.

This is quite similar to the Threshold Coloring Problem (TSC) [19], which is depicted in Fig. 3. In this problem, we have an undirected graph and a set of available colors (in the example, red, green and blue), with an associated interference matrix, which assigns an interference value for the occurrence of any pair of colors in any edge of the graph. The goal of the TSC problem is to find a coloring which minimizes the maximum interference per node (the optimal solutions for the example problem can be seen shadowed in the figure). Our hypothesis is that, by translating the problem of channel assignment to this problem, we will find suitable solutions in a reasonable time. We will have as the available color set the different Wi-Fi channels, and as the color interference matrix the co-channel interference index [13].

Fig. 3.
figure 3

Example of the Threshold Spectrum Coloring problem (TSC). (Color figure online)

Full size image

The translation from the Wi-Fi channel negotiation problem to the TSC problem is not straightforward. First of all, the variable/issue sets for both problems are different. TSC assumes all colorings are possible, while in Wi-Fi channel negotiation only channels chosen by the APs are negotiated, since all WDs associated to a given AP will use the same channel to communicate. To account for this, we propose to do a compactation of the interference graph I. That is, we will derive a compact graph C from the graph I as follows:

  • We will have a vertex in the graph C for every AP vertex in the graph I.

  • Two vertices in C will be connected if and only if there was an edge in I; (a) between them, (b) between one of the APs and one of the WDs associated to the other AP, or (c) between WDs of the two APs.

Such a compact graph for the example given in Figs. 1 and 2 is shown in Fig. 4. In addition, we will introduce edge weights in graph C according to two different strategies:

  • Uniform BP translation (BPu): we will assume that each existing edge between vertices i and j in the compact graph C has an associated weight \(w_{ij}=1\). This is the simplest possible translation (all edges equal), which loses most information from the interference graph I, so we expect it to give the less optimal results, but also to be the most efficient in terms of computation time.

  • Weighted BP translation (BPw): in this case, we will assign to each edge between vertices i and j in the compact graph C a weight \(w_{ij}\) equal to the number of edges in graph I between them, between one of the APs and one of the clients associated to the other AP, and between WDs of the two APs. This is a reasonable choice, since it will prioritize the edges between APs which have more potential interferences, but it is still a much more efficient choice computationally than evaluating the real interference between APs and their WDs.

Fig. 4.
figure 4

Compact graph C for an scenario with 26 APs and 400 wireless devices.

Full size image

The last step for the formalization is to translate the coloring of the compact graph C to a factorized optimization problem. To do this, we use our vertices representing APs as variables (which can take different values depending on which channel the AP uses to transmit) and the edges between pairs of vertices (which represent interferences between APs) as constraints. According to this, we define the corresponding functions as follows:

$$\begin{aligned} \varPhi _i(s_i) = 0 \end{aligned}$$
$$\begin{aligned} \varPsi _{C}(s_i,s_j) = w_{ij}c(s_i,s_j), \forall C\equiv (i,j) \end{aligned}$$

That is, we use a constant zero value for each variable function, and we use the product of the weight of the corresponding edge in the compact graph and the co-channel interference between the chosen channels (see [13] for details) for each factor function. With this formulation, we try to mitigate the impact of using “close” channels in close APs, which is coherent with the Wi-Fi interference model. It is worth noting that this formulation differs from the TSC problem, given that here we try to minimize the sum of the contributions for all nodes in the graph, while pure TSC aims to minimize the maximum contribution for any single node in the graph. However, as shown in [19], sum minimization is a good heuristic to minimize the maximum in this context, and therefore successful techniques proposed for TSC can be used here as benchmarks.

Finally, we need to build the factor graph \(F_P\) of our problem, which is a bipartite graph with variable nodes in one side of the partition and factor nodes corresponding to the constraints in the other side of the partition. Links between both partitions occur between a constraint and the variable nodes it refers to. For instance, in the graph example given in Fig. 3, the resulting factor graph \(F_P\) would be as shown in Fig. 5.

Fig. 5.
figure 5

Factor graph \(F_P\) (right) for our example TSC problem.

Full size image

3.3 A Scalable Negotiation Using Belief Propagation

To solve the factorized optimization problem we have proposed for our Wi-Fi negotiation scenario, we would have to apply the min-sum algorithm for BP [9]. The problem with applying directly the min-sum BP algorithm to our problem is that the algorithm only has correctness and convergence guarantees when the solution is unique and the factor graph is a tree. Although solution uniqueness can be achieved with randomized weights as suggested in [9], most of our scenarios do not create tree factor graphs. The usual junction tree technique used in machine learning to address this problem [25] is not applicable here, because it is centralized, which is not scalable (neither desirable) for competitive negotiation scenarios where sharing of private information should be minimized.

Taking this into account, to ensure convergence and correctness of the algorithm, we propose to divide the factor graph into trees using a distributed, gossip-inspired technique [5]. The technique we propose works as follows:

  • All AP nodes in the compact graph C are initialized to the unassigned state, which means they do not belong to any tree.

  • Nodes in unassigned state respond to the behaviour:

  • Decide with probability p whether to start a new tree (therefore changing their status to assigned) or to wait a random time.

  • Upon receiving a message from an assigned neighbour (that is, a neighbour already belonging to a tree), switch to assigned status and acknowledge the membership to the tree.

  • Nodes in assigned state respond to the behaviour:

  • Decide with probability p whether to invite a random subset of its (not already-invited) neighbors to its tree or to wait a random time.

This technique asynchronously divides the compact graph C into a set of disjoint trees, from which tree factor graphs can be derived so that BP converges. Of course, when we work with the resulting set of trees, we lose the information about the influencing factors \(\varPsi _{ij}\) corresponding to components \(c_i\) and \(c_j\) which are neighbors in the compact graph but have ended up in different trees. To minimize the impact of this simplification, we iteratively introduce this effect in the functions \(\varPhi _{i}\) of the frontier nodes (that is, the nodes in a tree which are neighbors of nodes in other trees). That is, the belief propagation process is repeated several times in an iterative manner, and at each iteration K the frontier nodes are assigned a variable function \(\varPhi _{i}^{K}(s_i)\) which is computed as follows:

$$\begin{aligned} \varPhi _{i}^{K}(s_i) = \sum \limits _{j\in \aleph (i)}{\varPsi _{ij}(s_{i},\hat{s}_{j}^{K-1})} \end{aligned}$$

Where \(\aleph (i)\) is the set of neighbors of component \(c_i\) in the compact graph and \(\hat{s}_{j}^{K-1}\) is the optimal assignment for neighbor \(c_j\) for the previous execution of the BP algorithm.

Computation of the \(\varPhi _{i}^{K}\) functions is performed at each corresponding provider agent for the AP i. Computation of the \(\varPsi _{C_{ij}}^{K}\) functions when APs i and j belong to different providers is randomly assigned to one of the provider agents to avoid agent manipulation of the belief propagation process.

Fig. 6.
figure 6

Polytechnic school building plan. (Color figure online)

Full size image

4 Experimental Evaluation

To validate our approach and assess the contribution of our mechanisms, we have conducted a set of experiments of the Wi-Fi real-world setting we used in [3], which uses the real layout of the first floor plant of our University (Fig. 6). The real positions of deployed APs are displayed with green dots, ranging their signal coverage from red (high coverage) to light blue (very low coverage). Note that the center of the plan represents a central courtyard, so it has low signal coverage. For the position of WDs we have considered that we have users attending classes in classrooms and also some students are located randomly in the building (resting, in the cafeteria, studying...). For this last group of students, we have considered that there are 100 students randomly located in the building following a uniform distribution. For the students in classrooms, we have tested several scenarios varying randomly the ratio of classrooms being used (\(\rho \), with \(\rho \in [0.25, 0.5, 0.75, 1.0]\)). As there are 48 classrooms in the building, we have considered scenarios with 12, 24, 36 and 48 classrooms. For each classroom, we have deployed 25 students in each one randomly using a normal distribution around the center of each classroom and a standard deviation normalized to the size of the scenario of 0.05. In Table 1 we show a summary of the real-world scenarios under study. Finally, as the specific random classrooms under use could affect the results, we have tested three experiments for each value of \(\rho \), so the total number of deployments studied has been 12. In each setting, APs have been randomly assigned to the two providers.

Table 1. Summary of scenarios of the real-world setting.
Full size table
Fig. 7.
figure 7

Normalized utility versus time for the different techniques.

Full size image
Fig. 8.
figure 8

Normalized utility versus time for the different techniques.

Full size image

We are interested in evaluating the performance of BPu and BPw in comparison with the well-known technique called Simulated Annealing (SA) [12, 16]. For a further description of how this technique has been deployed, see [4]. More specifically, we are interested in evaluating the performance of these techniques in terms of the normalized utility (\(U_n\)) that they can achieve in a certain computation time. The different values for the computation time have been obtained running the techniques with a different number of iterations.

Note that the normalized utility is defined as the sum of utilities for all nodes in the network (APs and WDs) divided by the graph order, i.e. divided by the number of nodes in the graph. Figures 7 and 8 show this comparison for the 12 scenarios under study. Results show that, except for the shortest runs where BP obtains worse results than SA, in almost all cases, BP is able to obtain a better performance (higher \(U_n\)) than SA for the same computation time. Comparing BPu with BPw we can conclude that BPw always outperforms BPu. This expected result is due to the fact that the compact graph of BPw includes more information than its counterpart of BPu. As a consequence of these results, we consider that the use of Belief Propagation, specially in its BPw setting, is very useful, as its efficiency is higher than the well-known, successful approach SA.

5 Conclusions and Future Work

Our research attempts to enable the use of complex automated negotiations in the management of complex systems with network structure, which are of increasing interest in many disciplines. One of the biggest challenges for this is the scalability of complex negotiation mechanisms when facing the large utility spaces and complex interdependencies of such systems. To address this challenge, in this paper we propose a novel perspective for the negotiation process as competitive belief propagation, which maps naturally to settings with a graph structure. We also propose an efficient mechanism to implement this competitive belief propagation process in large settings, which takes advantage of gossip-like techniques. Finally, we validate our approach on a realistic and challenging setting: Wi-Fi channel negotiation. Experiments show that our approach achieves better results that well-known successful nonlinear negotiation techniques in less computation time, which is a significant advance for the success of negotiation mechanisms in these settings.

Although our experiments yield satisfactory results, there is still plenty of work to be done in this area. We are interested in evaluating more sophisticated strategies than BPu and BPw for weighting the compact graph, in order to get as close as possible to the real interference model without imposing too much computational complexity in the mechanism. We want also to study the influence of different graph properties (e.g. diameter) in the performance of the BP techniques. Finally, we are interested in evaluating the strategic properties of the mechanisms, to see how the belief propagation process performs when agents are allowed to “lie” in their messages in order to try to influence the outcome of the mechanism to their advantage.