Poster: 
Modeling Wearable Negotiation in a Opportunistic Task Oriented Domain [J1]
Jay Schneider, Jim Suruda
Advisor: Steve Fickas
University of Oregon
Deschutes Hall
Eugene, OR 97403 USA
{fickas, jay, jfs}@cs.uoregon.edu

Ubiquitous Wearable Computers provides a new environment for negotiating personal agents.  These agents will perform a broad array of tasks for the user, ranging from personal scheduling and task planning, to providing hardware services in foreign locales.  The local environment will also have its own series of tasks with agents attempting to carry them out.   There is often a great deal of redundancy in the tasks being performed by the wearable and its user, other nearby wearable and their users and the local environment.  Whenever redundancy occurs there is an opportunity for both parties to more efficiently accomplish their goals, through task sharing and trading. 
The tasks that are being negotiated by the wearable can take a wide variety of forms, both physical and virtual.  A trade could be "if you take my books back to the library, I'll pick up your copies from the printers" or "I'll handle all outgoing communications through my currently unused T-1 line if you process the data received."  Although it is beyond the range of the initial work in this field trades such as "I'll handle all visual data analysis if you pick up my dry cleaning" are also possible. Task sharing and trading requires the agents involved to negotiate.   Negotiation techniques developed using this system provide a solution to resolve many possible day to day conflicts by the wearable devices, for example two computer-driven cars both desiring to move into the same physical space can be resolved using negotiation techniques.  Negotiations take place over a given domain, with certain expectations of behavior for those agents as expressed in [1], [2], and [3]. 
The domain used for the current project is limited to a subset of the Task Oriented Domain (TOD).  A Task Oriented Domain is one in which agents are not required to negotiate.  Each and every agent has all of the tools needed to accomplish their goals and each agent's goals are independent.  However, it is possible to achieve a higher level of success (e.g. accomplishing all the goals in a shorter period of time) through negotiation. The TOD we are using is differs from the norm in that it allows for ubiquitous computing. In this Ubiquitous Task Oriented Domain (UTOD) the agents operate in an opportunistic fashion.  These agents take advantage of their current context, both physical and virtual, to decide if and with whom they will negotiate.  Their current context also will affect the expected worth of bargaining as per [2].
The agents involved in task sharing and trading originate from a variety of uncontrolled sources.  Maximizing its personal goals is assumed to be an agent's sole motivation.  These agents can and will use strategies in which they will lie, cheat or steal to maximize their benefits.  A primary goal of modeling agent negotiation in a UTOD is to find a set of rules for the negotiation environment where the honest agent will perform as well as the dishonest one.   These rules for the negotiating environment in games theory are referred to as the protocol.  As protocol designers it is in our best interest to protect the honest agent.  Honest agents are needed to accomplish the goal of the protocol designers - global optimality. [4] 
A protocol is globally optimal which it can be proven that maximal efficiency will be derived  by all parties negotiating under this protocol.  When tasks are being assigned by a single organization or when negotiations occur between agents working towards a joint goal this is the sole issue.  This is not the only concern when the parties in the negotiation are ambivalent towards each other goals or can achieve a higher goal by working towards their own ends.
In cases where the agents are concerned only with their own unshared goals, protocol design aimed at global optimality can be is restricted by the concept of Individual Rationality.  Individual Rationality means that any deal an agent will consider must offer utility that is at least as good as the utility prior to the negotiations.[J2]
The class of TOD domain we are using for our agents is a variation on the postman domain.  The traditional postman domain is described in [4] as: 
 "Agents have to deliver sets of letters to mailboxes, which are arranged on a weighted graph G=G(V,E). There is no limit to the number of letters that can fit in a mailbox. After delivering all letters agents must return to the starting point (the post office.) Agents can exchange letters at no cost while they are at the post office prior to delivery.
Task Set: The set of all addresses in the graph, namely V. If address x is in an agent's task set, it means that he has at least one letter to deliver to x.
Cost Function: The cost of a subset of addresses X Í V, i.e., c(X), is the length of the minimal path that starts at the post office, visits all members of X, and ends at the post office."
Our variation differs from the traditional postman domain in that it allows  n postmen and m post offices (n >= m), and uses the UTOD where negotiations can occur at any vertex, not just the post office.  The domain also allows for negotiation to occur in a continuous fashion, allowing for opportunistic negotiations along the edges of the graph.
The model we have implemented in the modified-postman domain is described as follows:
G=G(V,E), V={v1, v2...vn} with  m agents. Each agent has starting vertex {v1, v2...vm} and task set  {s1, s2...sm} and must return to starting vertex {v1, v2,...vm}.  Each agent m1 negotiates with agent m2 when their locations are within distance d of each other.
The negotiation protocol we are using is the Product Maximizing Mechanism (PMM) as presented in [4].  We chose this protocol as it is satisfies all of Nash's criteria in [2].  In short, this means PMM provides a efficient solution that is in Nash equilibrium when both parties negotiating have full knowledge of the other parties task set and starting vertex. 
The PMM protocol is a two-step protocol.  In the first step both parties disclose their task sets.  In the second step each party proposes a deal (division of tasks) that is pareto-optimal and individually rational (see [2] for more information on these terms.) The deal that is selected is the deal that has the highest utility when the utility to agent 1 and agent 2 are multiplied. 
Using the WALID system described in [5] we are testing this system using n agents and compute the benefits accrued through negotiation.  We can also add agents and determine average utility benefit as more agents are added to the simulation. This allows us to show a saturation point and to see what the expected utility gain is when an additional agent is added to the graph. 
As the agents in this task are wearable users we have also implemented a Cost of Negotiation (CoN).  CoN is a constant value subtracted from the utility of a new task set in step 2 of PMM.  This value relates to the human cost of changing the wearable users task set.  In the postman domain tasks relate to traveling to physical locations.  By adding a CoN value we prevent the wearable user from pointlessly trading tasks and spinning in place.

[1] John Von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, 1947.

[2] John F. Nash . The Bargaining Problem. Econometricia, 28:155-162, 1950.

[3] John F. Nash . Two-person cooperative games. Econometricia, 21:128-140, 1953.

[4] Jeffrey S. Rosenschein and Giliad Zlotkin. Rules of Encounter, Designing Conventions for Automated Negotiation among Computers. MIT Press, Cambridge Massachusetts, 1994.

[5] Fickas, Kortuem, et. al.  When Cyborgs Meet:  Building Communities of Cooperating Wearable Agents. Submitted for publication International Symposium of Wearable Computing, 1999.

[J1] Is it possible to mention untrusted agents in the title?
[J2] Embelishment
9


1