## 3 Automated Negotiation Techniques for Channel Selection
### Decision Mechanisms  
For the mediator, we have implemented a single-text mediation mechanism [38] for the generation of new contracts, which works as shown in Algorithm 1:  
* If at time \(t\) all agents have accepted the presented contract \(S_{t}^{c}\), this contract will be used as the base contract \(S^{b}\) to generate the next contract \(S_{t+1}^{c}\) (1). Otherwise, the last mutually-accepted contract will be used. * To generate the next candidate contract \(S_{t+1}^{c}\), the mediator takes the base contract \(S_{b}\) and mutates one of its issues randomly (2). In our case of study, this would correspond to choosing a random access point and selecting a new random channel for it. * After a fixed number of iterations, the mediator advertises the final contract, which will be the last mutually-accepted contract (3). For the agents, we have considered two different mechanisms to vote about the candidate contracts \(S^{c}\):  
* Hill-climber (HC): In this case, the agent behaves as a greedy utility maximizer (see Algorithm 2). The agent will only accept a contract when it has at least the same utility for her or him as the previous mutually-accepted contract (2). If there is no previous mutually-accepted contract (1), the agent will accept the presented one (this effectively makes the first contract generated by the mediator be the first mutually-accepted contract). * Annealer (simulated annealing (SA)): In this case, we use a widespread nonlinear optimization technique called simulated annealing [38, 39]. When a contract yields a utility loss against the previous mutually-accepted contract, there will be a probability for the agent to accept it nonetheless. As shown in Algorithm 3, this probability \(P_{a}\) depends on the utility loss associatedwith the new contract \(\Delta u\) and also depends on a parameter known as annealing temperature \(\tau\), so that \(P_{a}=e^{\frac{-\Delta u}{\tau}}\) (2). Annealing temperature begins at an initial value and linearly decreases to zero throughout the successive iterations of the protocol (1). ```
Input: \(P=\{p_{i}\}\): set of providers (for this work, \(|P|=2\)) \(A\): set of access points \(T\): maximum number of iterations Output: \(S\): final contract, corresponding to a channel assignment for each AP \(t=1\) \(S^{b}=generate\_random\_contract(A)\) while\(t\leq T\)do \(S^{c}_{t}=S^{b}\) \(V=request\_provider\_votes(P,S^{c}_{t})\) if\(reject\
otin V\)then \(S^{b}=S^{c}_{t}\) \(notify\_mutual\_agreement(P,S^{c}_{t})\)  end if \(S^{c}_{t+1}=mutate\_contract(S^{b})\)  end if \(t=t+1\) \(S=S^{b}\) \(notify\_final\_agreement(P,S)\)
```  
**Algorithm 1**Single-text mediation algorithm. ```
Input: \(A_{p}\in A\): set of access points belonging to the provider \(S^{c}_{t}\): candidate contract sent by the mediator at time \(t\)\(S^{b}\): last mutual agreement notified by the mediator Output: \(v\): vote of this provider (\(v\in\{accept,reject\}\)) if\(S^{b}=\varnothing\)then \(U^{b}=-\infty\) else \(U^{b}=compute\_utility(A_{p},S^{b})\) end if \(U^{c}=compute\_utility(A_{p},S^{c}_{t})\) if\(U^{c}\geq U^{b}\)then \(v=accept\) else \(v=reject\)  end if
```  
**Algorithm 2**Hill-climber voting algorithm. The choice of these two mechanisms is not arbitrary. Simulated annealing techniques have yielded very satisfactory results in negotiation for nonlinear utility spaces [40] and are the basis for several of our previous works [18, 19]. Furthermore, as discussed in [38], the comparison between hill-climbers and annealers allows one to assess whether the scenario under consideration is a highly complex one, since in such scenarios, greedy optimizers tend to get stuck in local optima, while the simulated annealing optimizer tends to escape from them. For a complexity analysis, we are using heuristics that are stopped when reaching a certain number of iterations (see Section 4.3).