Alternating-offers bargaining with one-sided uncertain deadlines: an efficient algorithm

In the arena of automated negotiations we focus on the principal negotiation protocol in bilateral settings, i.e. the alternating-offers protocol. In the scientific community it is common the idea that bargaining in the alternating-offers protocol will play a crucial role in the automation of electronic transactions. Notwithstanding its prominence, literature does not present a satisfactory solution to the alternating-offers protocol in real-world settings, e.g. in presence of uncertainty. In this paper we game theoretically analyze this negotiation problem with one-sided uncertain deadlines and we provide an efficient solving algorithm. Specifically, we analyze the situation where the values of the parameters of the buyer are uncertain to the seller, whereas the parameters of the seller are common knowledge (the analysis of the reverse situation is analogous). In this particular situation the results present in literature are not satisfactory, since they do not assure the existence of an equilibrium for every value of the parameters. From our game theoretical analysis we find two choice rules that apply an action and a probability distribution over the actions, respectively, to every time point and we find the conditions on the parameters such that each choice rule can be singularly employed to produce an equilibrium. These conditions are mutually exclusive. We show that it is always possible to produce an equilibrium where the actions, at any single time point, are those prescribed either by the first choice rule or by the second one. We exploit this result for developing a solving algorithm. The proposed algorithm works backward by computing the equilibrium from the last possible deadline of the bargaining to the initial time point and by applying at each time point the actions prescribed by the choice rule whose conditions are satisfied. The computational complexity of the proposed algorithm is asymptotically independent of the number of types of the player whose deadline is uncertain. With linear utility functions, it is O(m . (T) over bar) where m is the number of the issues and (T) over bar is the length of the bargaining. (C) 2007 Elsevier B.V. All rights reserved.