# Can Social Agents Efficiently Perform in Automated Negotiation?
## 3 Proposed Social Agent
### Concession Mechanism
#### 3.2.2 Target Utility Update  
After explaining the concept of a bid window, let us formalize some parameters and data employed by the target utility update mechanism, which is carried out only when the concession mechanism is executed (i.e., after comparing two non-sliding windows as described in the previous subsection). Coupled with the non-sliding window mechanism, the target utility update mechanism is what makes our proposed Tit-for-Tat strategy different from classic variants. First, \(o_{best}\) represents the best offer received from the opponent, considering our utility function. Second, \(c_{max}\) represents the maximum utility update at each concession step. This new parameter, which is not included in classic Tit-for-Tat variants, avoids abrupt concessions and forces a more thorough exploration of the utility space. The details of our proposed target utility update mechanism can be found in Algorithm 1. Next, let us explain how this mechanism works in detail. ```
Data:\(W_{recent}\): The most recent bid window received from the opponent, \(\mathcal{W}\): the previous bid windows received from the opponent, \(o_{best}\): the best offer received from the opponent Result:\(\mathcal{U}_{target}\): the current target utility for our agent. \(U_{r}=\{\mathcal{U}(o)\mid o\in\mathcal{W}_{recent}\}\); \(P_{r,z}=\textit{percentile}(U_{r},z)\); \(U_{best,t}=\{o\mid o\in U_{r}\wedge\ o\geq P_{r,z}\}\); \(M_{r}=\textit{median}(U_{best,r})\); \(M_{p}=0\); foreach\(W_{i}\in\mathcal{W}\)do \(U_{i}=\{\mathcal{U}(o)\mid o\in\mathcal{W}_{i}\}\); \(P_{i,z}=\textit{percentile}(U_{i},z)\); \(U_{best,i}=\{o\mid o\in U_{i}\wedge\ o\geq P_{i,z}\}\); \(M_{i}=\textit{median}(U_{best,i})\); if\(M_{i}>M_{p}\)then \(M_{p}=M_{i}\);  end if  end for \(\Delta=\textit{min}(c_{max},M_{r}-M_{p})\); \(U_{target}=\textit{min}(1,\textit{max}(\mathcal{U}(o_{best}),U_{target}-\Delta))\);
```  
**Algorithm 1**The target utility update mechanism. Figure 3: The bid windows that split the negotiation history into partitions of K bids. The first steps (lines 1-4) consist of estimating a central measure of utility received from the opponent in the current window of bids. For that, bids in a window first need to be transformed to a utility space. The agent uses a median utility calculation mechanism as a measure of centrality due to the abrupt and unintended changes in utilities of bids sent by the opponent. In fact, instead of considering the whole window of bids, we propose for the agent to just consider those offers whose utility are above a given percentile (i.e., \(P_{r,z}\), with \(z\) being the specific percentile). We experimentally found that many windows of bids only contain a few reasonable offers for the agent even though the opponent may have conceded. In some scenarios, this is caused by inaccurate opponent models in the early and middle stages and, in others, just due to the exploratory nature of the opponent. Therefore, we believe that concessions should only be detected with the top offers from the window of bids \(U_{best,r}\) rather than just two consecutive offers or from the whole set of offers, as proposed by classic Tit-for-Tat variants. After filtering out those offers above the percentile in the windows of bids, its median \(M_{r}\) is calculated. From this point on, we refer to this median calculation on the top bids in a window as the _top median_. Figure 4 shows a bid window collected from a real negotiation and illustrates how calculating the median on the offers above a given percentile (\(z=80\), \(20\%\) top offers) may better represent concessions carried out by the opponent. After that, the agent checks the previous window of bids to calculate the best _top median_ received so far from previous windows (lines 5-12). Please, notice that this median calculation follows the same procedure as described in the paragraph above (i.e., median on the top offers from the window of bids).