Lies in State Oriented Domains

Abstract. This paper explores the use of genetic algorithms in identifying effective lies for use in negotiations with incomplete information in State Oriented Domains (SOD's). The aim is to seek lies which are not just safe (i.e. they will not lead to a disgraceful outcome) but also yield the highest possible utility. In this work a GAs based representation for goals and corresponding operators are proposed. 1. Introduction In the simplest possible scenario for a non-trivial negotiation, agents will state their objectives and then work their way towards a satisfying solution [Garcia Martinez & Borrajo, 2000]. Finding such a solution will probably include agreeing on a final situation that is acceptable to every agent, as well as dividing the work necessary to reach that situation. Thus different roles will be designed, and in general the roles will have different costs. Fair enough, the agent with the most onerous objective will play the most expensive role. Naturally, it is in an agent's best interest to achieve his goal at the lowest possible cost [Garcia Martinez et al., 2006]. That is where an agent may be tempted into stating an objective that is different from his actual goal. Lies can be beneficial, inasmuch as pretending to have a cheaper goal might result in doing less work in the joint plan. Provided there exists a mechanism that will guarantee the simultaneity of the exchange of information on the goals, speculation with lies is not just greatly restricted but also dangerous, since the negotiation could result in a solution that will not satisfy the agent's true goal. Nevertheless, in a context where abiding by such a mechanism is not mandatory, there may come to occur that an agent will become acquainted with the other agent's goal before the latter learns his. Should this be the case, lying can be safe, for it is possible to ensure that the outcome will not be disgraceful. Moreover, the agent can focus on finding a lie which is not just safe but also yields the highest possible utility. Firstly we present the reader with a simplified version of state oriented domains (section 2) and a genetic representation of a goal (section 3). Then we discuss how to assess the satisfaction of a goal (section 4), generate lies (section 5), assess their aptitude (section 6) and improve them through sensible mechanisms of selection (section 7), crossover (section 8) and