Decision strategies for automated negotiation with limited knowledge

This thesis focuses on decision strategies in automated negotiation when only limited knowledge about the negotiation partner or environment is available. Negotiation between self-interested agents is a key mechanism in distributed and autonomous software systems which facilitates multi-stage decision-making between two or more parties that are in conflict about their goals or preferences. In such systems, when agents are competitive and act rationally, the agents do not disclose information about their decision models and preferences, and behave in various ways to achieve their goals. Because of this, the available information for the decision-making of an agent is limited as it can only be derived from the current encounter or previous interactions. Therefore, an agent needs to find a decision strategy that obtains high payoffs while at the same time reaches an agreement given this limited knowledge. Decision-making in such situations is known to be hard and, while many approaches have been proposed, most assume that agents either have sufficient or precise knowledge about their opponents in the form of empirical data, domain knowledge or the decision models of their counterparts, or have enough time to learn it during their encounters. The thesis proposes novel solutions to the above problem and, in particular, focuses on the strategic concession behaviour of agents in competitive environments. The fundamental setting considered is that of bilateral negotiation in which two agents bargain for a product or service by exchanging offers alternately until one party agrees or withdraws from the encounter. In such a setting, the work first presents and investigates two decision mechanisms, an existing heuristic-based approach and a novel decision model based on multistage fuzzy decision-making, that are suitable for situations in which an agent has only limited knowledge, and then proposes a mechanism for coordinating these strategies in more complex and realistic concurrent negotiation scenarios. The heuristic-based approach linearly combines individual decision functions to create multi-tactic negotiation strategies that can react to a range of factors such as the opponent’s behaviour, time, or the state of a resource. While the advantage is that only observable information from the current encounter is required, the mixing mechanism itself and its effect on the strategic concession behaviour of the agents has not been investigated before. As the traditional linear combination can not guarantee monotonic concession curves, even when all involved tactics are monotonic and weights are static, agreements can be delayed and outcomes can differ significantly. We propose new mixing mechanisms based on linear combinations of individual negotiation threads or single concessions, which guarantee monotonic concession curves for monotonic tactics in static and dynamic strategies. The second decision mechanism models the negotiation process as a multistage fuzzy decision problem in which fuzzy state transitions represent the limited knowledge of the opponent’s behaviour, for example, by using only a few reference cases. This enables the use of dynamic programming algorithms in order to find the best course of actions that achieves a desired outcome. In this model, the preferences of an agent are modelled using a fuzzy goal and fuzzy constraints that also allow an agent to combine a preferred strategy with the fuzzy state transitions in order to create different strategic concession behaviours. Due to the fuzzy transition model and the ability to impose fuzzy constraints on the decision-making process, agents are able to negotiate competitively by utilizing their limited knowledge about their opponents. The coordination of negotiation strategies in concurrent bilateral encounters is demonstrated using an example scenario with one-to-many negotiations in the domain of service-oriented computing. In this scenario, a number of service level agreements need to be negotiated with service providers in order to establish aworkflow-based composite service. It shows that the mechanism increases the number of compound agreements by the method of utility boundary decomposition and surplus redistribution of successfully finished negotiations, while simultaneously allowing the individual agents to use their own decision strategies for negotiation. The major advantage of the proposed mechanisms is their ability to create negotiation strategies that successfully cope with situations in which the available knowledge about the opponents and the environment is limited. The example scenario also demonstrates the applicability of the mechanisms in a more complex and realistic scenario. Both decision models and the coordination mechanism are validated experimentally.