Monday, June 8, 2009

Sycara (1991) Problem Restructuring in Negotiation

I read about this paper in Sycara's (1998) Multiagent systems paper, which I blogged about recently. In that blog post I was saying that I found it really difficult to imagine artificial agents handling negotiation in anything other than an inflexible and trivial fashion. Now I have read Sycara's (1991) paper "Problem Restructuring in Negotiation" which describes her PERSUADER system, I have a much better idea of how an expert system can be structured to handle negotiation. The PERSUADER system is a very thorough expert system that encapsulates knowledge from real world experts, and uses Case Based Reasoning, Goal Graph Search, Situations Assessment and Persuasive Argumentation to mediate labour disputes. The mediator agent maintains dynamic belief and goal networks for the negotiating parties and performs search over these networks in order to determine likely settlements.

The PERSUADER system is complex, and I won't attempt a detailed description of it here, but suffice to say that it feels like the process of negotiation performed by humans has been dissected and analyzed and broken into its component parts. As soon as I had caught the gist of one component, e.g. matching case histories of settlements with the current negotiation, when we were on to other approaches that involved generating settlements from scratch by reasoning about the goals and beliefs of the negotiating parties. I would have thought that even small parts of the system would be very complex, but the paper goes on and on to describe more and more involved meta-strategies that are designed to resolve different types of conflicts. It also seems that the system can learn based on the failure of proposed settlements as they are added to it's memory of cases, and the goal and belief networks of the negotiating parties are updated, although I didn't read specific details about this latter aspect.

I guess my main questions were has this system ever been evaluated in a real world context, and did anyone ever use it? It seems that the PERSUADER was developed as part of Sycara's PhD thesis, so I may need to read that and other subsequent publications to get to answer my questions here. I was able to grab a couple of other of Sycara's publications on PERSUADER from Google Scholar, but I couldn't find any mention of evaluation. In her classic paper on multiagent systems Sycara (1998) mentions that one of the key obstacles to the adoption of agent technology was individuals becoming comfortable with the idea of delegating a task to an agent. I find it difficult to imagine either party in a real labour dispute being willing to accept an AI expert system as a mediator; although not impossible - I would be very interested to know if such a thing had ever happened. There are hints in this paper that PERSUADER was applied to real world scenarios, but it is not clear if this was as part of a real negotiation, or after the fact.

Sycara mentions in passing knowledge-based work that provides support for human negotiators (Kersten et al., 1990; Jarke and Goeltner, 1987), and it seems that this is the kind of approach that is much more likely to see real usage. I sense a parallel with machine translation and machine support for human translators.

Even with the overall complexity of the PERSUADER system there are some issues that appear glossed over such as the functions that generate the bargaining power of a local union, which takes arguments of the economic context and the international union and returns numerical values. However I was impressed that nine months were spent filling the case base from labour relations literature, published arbitration awards, two human experts and the systems own learning mechanism. There is a saying that as soon as a computer does something we say that intelligence is not required for the task, thus making artificial intelligence an unreachable goal. Reading about the PERSUADER I felt that this was a carefully crafted expert system that encapsulated many of the techniques that would be employed by a human negotiator, but was also one that might miss many of the subtleties of human negotiation where agents are not always rational. It seems like the system would work well to the extent that it's model of the problem space was well designed, but in some ways that is the real trick isn't it. I get the feeling that really intelligent human negotiators are modifying the classification categories over time. Sort of what I am trying to do with our meta-analysis of second language vocabulary acquisition. There are existing categorizations implicit and explicit in the various papers, and they are not always perfectly aligned. We are trying to dig down to the information bearing categorizations through a process of adjusting the granularity of representation. Perhaps it's just my imagination, but it feels like that's the kind of thing that would be required for the system to impress me with its intelligence. Although at the end of the day any of these kinds of expert systems that are comprehensible to humans are going to feel a little like the emperor with no clothes; that there are sets of mindless computations going on and no real understanding, but that's a separate debate.

Bottom line here for my purposes is that I can certainly see what Sycara is talking about when referring to the literature on what Agents have to offer, and it certainly informs my "agents and p2p" invited paper, where I had been struggling to understand what agents had to offer. Sycara points out that the restructuring process and algorithms of PERSUADER are domain independent, and these are certainly a technique like a P2P distributed hash table, or search pruning that the field of agents has in its armory. On the flip side this seems like not such a good example because the question immediately arises how do we know the techniques employed by PERSUADER are any good? I guess that I should assume that different approaches to expert systems have been evaluated at some point in the literature and that the fields of AI and agent practitioners are aware of these results. However this kind of heavy reasoning just doesn't seem of much practical use in the P2P field; which now appears to me to have much more in common with reactive agents (as Sycara (1998) describes), which have the advantage of speed making them useful in rapidly changing environments. Interestingly Sycara (1998) says that:
In reactive systems the relationships between individual behavior, environment and overall behavior is not understandable, which necessarily makes if hard to engineer agents to fulfill specific tasks.
Although I feel that many P2P systems have done a pretty good job of engineering desirable system level behavior; and it is still not clear to me that reasoning agents with complex representations bring huge benefits. I guess they may in auction systems running trading software, but I am not aware of many plug and play expert systems that can be used for helping with general programming. At least PERSUADER feels like a giant heuristic - maybe it has some reusable parts, and if I read more recent papers on expert systems I would see more clearly the AI equivalents of distributed hashtables or swarmcasting.

It also occurs to me that one of the significant challenges is getting all the data into the expert system. It seems like a lot of effort it spent turning data from experts and historical data into a form that the machine can process. Being able to extract that info from conversations and reading documents (which are huge AI problems themselves) would have a big impact on the practicality of this kind of approach.

This paper inspired me to search for ruby code that supported AI techniques like Case Based Reasoning. I found this interesting blog post.

Cited by 92 [ATGSATOP]

No comments: