Rosenschein (1993) Consenting Agents: Negotiation Mechanisms for MultiAgent Systems

This is another paper I'm reading for my invited paper on agents and peer to peer computing. I'm not quite sure how I ended up with this paper by Rosenschein, which itself appears to be a summary of an invited talk at a conference.  Sycara referred to a number of Rosenschein papers in her AI Magazine article.  Maybe this invited talk was just what I could find online at the time.  Anyway, given that I have it printed out, it seemed like a good place to start.


The paper gives motivations for considering systems of interacting autonomous agents.  Telecommunications and electric grids seem like good examples, a conclusion I have been drawing from reading Sycara's papers, although I know little about the specific requirements from these industries.  It's when agent authors get on to systems designed to support user interfaces for the average user that things seem least realistic.  Rosenschein gives this example:

For example, with Personal Digital Assistants (PDAs), the individual's palmtop computer will be expected to coordinate schedules with others PDAs (e.g., my software agent determines whether my car has been fixed on time at the garage; if not, it contacts the taxi company, reschedules my order for a cab, and updates my day's schedule)

Which seems very unrealistic.  Of course one has to remember that this paper was written in 1993, before the web and mobile technologies were commonly accessible.  However there are several things that appear to serve as barriers to this kind of personal scheduling system.  One of them is that it requires the garage to have a computerized system and that information from it is exposed in some form.  I guess modern garages do now keep computer records of how work is progressing, as do modern taxi companies, although convincing them of the need to expose internal data seems hard.  I guess that's where having things in agent wrappers might reassure companies, but it's still a big leap.

However the biggest hurdle is that the current solution to this kind of problem, i.e. you sort it out yourself, is pretty damn robust.  I guess if you had a taxi company and a garage who didn't just have websites, but exposed RESTful APIs to their internal systems, then a mobile phone could co-ordinate these things, but getting a program to make the right choices; and step back, setting it up so that I can easily communicate my desires to that program seem like a huge challenge.  Alot of it comes down to human trust in "agents", but there is also the question of the business model.  Are there going to be people who are willing to pay for such a service, or for platforms that come bundled with these sorts of services?  I guess one could try seeing if Hertz and Quikfit (UK garage chain - I don't know any US one) would expose APIs the way Google and Twitter do, and then write something for Android or iPhone; however the notion of an open platform for multiple agents still seems fanciful, it mainly for complexity reasons.  It's almost always going to be simpler to build one mashup that consumes a small number of services and delivers a single interface to the user. 

Of course, clearly Rosenchein and other agent researchers will have updated their ideas in the last 15 years, but I guess I'm trying to write about the history of the agent community, and this paper does get explicit about what many agent researchers were focusing on:

What concerns us here are not the details of how to stuff information in to a packet on the network; it 's not even the higher-level issue of how agents will communicate with one another (in a common language, or perhaps using translation filters). Rather, once we assume that agents can communicate and understand one another, how will they come to agreements?

My personal experience working with the Plangent system at Toshiba was that in general, how to get communication going in distributed systems was the main issue.  One could construct planning and negotiating agents of one kind or another, and I guess this was the interesting area from an AI perspective, but the real hurdle to building effective distributed systems was the communication itself; and from where I sit now it sure seems like RESTful APIs are the solution.  Of course now that we have those more and more commonly available the interesting question is whether everything discovered about how agents interact and cooperate can be used to build successful agent systems on top of RESTful mashups. Rosenschein envisions the following:

With PDAs, for example, new agents (and even new types of agents) will constantly be entering the environment. My PDA, to be effective in negotiation and coordination, must be able to deal with these open, dynamic, configurations of agents.

I guess the key obstacles here are security related.  On my android phone I can download new software, and that software can communicate with existing software on my phone, but the interactions do not really involve negotiation.  The program can either access the data from local and remote services or it cannot.  The real hurdle seems to be what benefit does the user or developer see from the added complexity of supporting negotiations between agents.  I guess it all comes back to the concept of the digital butler - we'd all love to have a butler who was tirelessly working to make our life easier.  Rosenschein puts it like this:

we want our agents to faithfully act as our surrogates in encounters with other agents

So it certainly does come back to trust, but trust is not enough.  There has to be a value proposition there to.  I currently point my iCalendar at a number of Google calendars that other people can update.  The value proposition there is that I can easily see events other people are providing, and I know I can shut off those calendars at will (no need for trust really).  The value proposition is clear.  I guess I could install a calendar agent that would try to negotiate times for meetings with the agents of other users, but again it seems like a lot of effort to set up something that may work unreliably, when the simple exposure of socially translucent information across the calendars can achieve the same effect, e.g. my colleagues and I can all see the same calendar and if I move a meeting they can all see that.  Yes, a really really smart agent working for each of us could maybe save us a few minutes spent in email co-ordinating and avoid the occasional absent member or missed meeting, so the value proposition seems low.

So anyway, it's pretty clear that I'm not seeing the benefit of agents in the personal information management realm, but am open to their utility in industrial software.  Further on the paper we see the area that Rosenschein is really interested in which is domain theory, and he describes three domains:

• Task Oriented Domains (TOD) - sets of independent tasks
  
• State Oriented Domains (SOD) - moving the world from an initial state to a goal state
  
• Worth Oriented Domains (WOD) - similar to SOD, but with value is assigned to each state
  

and three classes of domain:

• Subadditive - where combining tasks may reduce but never increase the total cost
  
• Concave - where adding a set of tasks to some existing set Y will not add more than adding same to subset of Y
  
• Modular - where the cost of the combination of two sets of tasks is exactly the sum of their individual costs, minus the cost of their intersection
  

and he describes example problems including postmen delivering letters, database queries, and fax problems.  Several of these reminded me of the traveling salesman problem, and I think the main point here is that different domains will lead to different possible outcomes for the various negotiation strategies that agents might employ.  Rosenschein argues that game theory is a great match for agents, since the assumption of rational actors that doesn't apply so well to human actors has a better fit for agents.  Reading this was helpful in terms of seeing what agent research might offer p2p researchers, in that classification of domain types will be useful for understanding the properties of interacting peers in p2p systems; I guess the best example being something like BitTorrent's use of the TitForTat strategy.  Of course I'm probably late to the party now :-) but then I'm slow like that.  Yes, clearly there is a good fit for multi-agent game theory analysis of the interaction strategies employed in peer to peer systems like BitTorrent.

Cited by 36 [ATGSATOP]