AUTOMATED NEGOTIATION
ARTICLE 1
ARTICLE 1
by Dharmalingam Girivendhen
Introduction
Distributed Artificial Intelligence : An Overview
Game Theory : A Definition
Intelligent Agent And Game Theory : The Relationship
Reasoning About An Agent's Likely Action
Applications Of The Relationship
Summary
References
The importance of automated negotiation is likely to increase as distributed systems of computers play an increasingly important role in society.Since informations and tasks are shared in distributed enviornment and agents have limited functionality, it will be necessary to consider ways in which these agents can be made to interact for resourses and/or information effectively.
We consider how concepts from fields such as decision theory and game thory can provide standards to be used in the design of appropriate negotiation and interaction enviornments.This design is highly sensitive to the domain in which the interaction is taking place.
The approach of Artificial Intelligence provides methods for the control of distributed network in which knowledge is distributed. Distributed Artificial Intelligence (DAI) allows several processes, called agents, to solve a single problem. Each process uses local power and communicates with remote hosts. The organisation of them allows the distribution of the resolution of a shared problem. The problem solving process is distributed, i.e. each agent has to share a common infomation set allowing the entire group of agents to reach the solution. This group of agents is decentralized, meaning that data and controls are often logically and physically distributed, as the DAI approach is used in a changing and unpredictable enironment, centralized control over the entire network is impossible. or software program developed to assist users in a range of different ways: they hide the complexity of difficult tasks, they perform tasks on the user's behalf, they help different users to collaborate, etc. The set of tasks or applications an IA can assists in is virtually unlimited: information filtering, information retrieval, email management, meeting scheduling, selection of books, movies, music and so forth. They can be regarded as computerized personal assistants.
Research in distributed artificial intellegence is concerned with how automated agents can be designed to interact effectively.One important capability that could aid inter-agent cooperation is negotiation; agents could be built that are able to communicate their respective desires and compromise to reach mutually benificial agreements.
One of the persumed difficulties in using negotiation as a way of reaching mutual benifit is that negotiation is a costly and time-consuming process.In the present of time constraints, planning and negotiation time should be taken into consideration.The negotiation may be either about job sharing or resourse allocation. In both cases we want to prevent the agents from spending too much time on negotiation and therefore not keeping to their timetables for satisfying thier goals.
Research in DAI is devided into two basic classes:Distributed problem solving (DPS) and Multi agent Systems (MA).Reserch in DPS considers how the work involved can be devided among a number of modules or "nodes".The modules in DPS system are centrally designed to improve performance, stability, modularity, and/or reliability.They include the development of cooperation mechanisms designed to find a solution to a given problem.
Research in MA concerned with coordinating intelligent behaviour among a collection of autonomous (possibly heterogeneous) intelligent (possibly pre_existing)agents. In MA, there is no global control, no globally consistent knowledge, and no globally shared goals or success criteria.There is a real compitition among agents.
Here we will describe MA as it deals with interactions among self_motivated, rational and autonomous agents.
A set of agents shares a joint resource.The joint resource can only be used by one agent at a time.Agreement is sought so that all the agents will be able to use the resource.
A communication satellite is a good example of shared resource, due to the high cost of it's launching and maintenance.In many cases the only way a company can get access to a communicatin satellite is by sharing one with other companies.Even competing companies may find it mutually benificial to participate in such a joint project.
Sharing a common resource requires a coordination mechanism that will manage the usage of the resource.A coordination mechanism can be a static devision of frequencies or time slots.On the other hand, it can be an on-line negotiation mechanism that dynmically resolves local conflicts over the usage of the common resource.Those are the two extreme poles of the coordination mechanism spactrum.On this spaectrum there are also coordination mechanisms that generate agreements on long term (an hour, a day, ...) global schedules. d
As in the case of communications satellite, common resources are shared by different companies with possibly different and even conflicting goals.Therefore, to ensure efficiency, the mechanism should also be be stable and symmetric.This article formally defines these attributes and presents symmetric, stable and simple on-line coordination mechanisms that resolve local conflicts without delay and result in an efficient joint usage of the resource.
In a multiagent competition situation there is a need to define a mechanism (a protocol) that allows agents to resolve their conflicts and to reach a coopereative agreement. What are the conditions that a Negotiation Protocol should satisfy(for any specific distributed multi-agent domain), such that it should be accepted by all the designers of agents (for that specific domainb)?
Distributed -The decision making process should be distributed.There should be no central unit or agent that is managing the process.
Instantaneously -Conflict should be resolved without delay.
Efficiency -The outcome of the negotiations should be efficient
-Conflict should be avoided when possible and the mechanism should allow the agents to reach Pareto optimal agreements with high probability.An agreement is Parito optimal if there is no other agreement that dominates it, i.e., there is no other deal that is better for some of the agents and not worse for the others.
-In the resource allocation problem, the resource is not in use only when there is no agent in the group that currently needs the resource (there are no deadlocks).
Simplicity -The negotiation process itself shoud be simple and efficient.It should be short and consume only a reasonable amount of communication and computation resources.
Symmetric -The coordination mechanism should not treat agents differently because of non-relevant attributes.In the The IA must be able to anticipate and understand the actions of another agent/opponent, and given its multiple goals, limited resources and dynamic environment, it must decide which of the many possible actions to execute at each point in time to counteract the opponent's moves. This requires the IA to possess the ability to learn from past experiences, to be able to reason about and perhaps by using analogy to past experiences, make decisions that represent the best interests of its user.
For example, after analyzing a situation, an IA asserts "If I were her, I would do X" but then asserts "But determining that X will work requires her to know some advanced tactics which I don't think she is familiar with, so I think she will probably do Y instead". This type of reasoning involves several steps:
By using this relationship between intelligent agent and game theory, a machine or knowledge-based system could be build to aid the users in carrying out their tasks in 2 main situations :
Adversarial condition
which requires Adversarial Problem Solving(APS) e.g.
Military Strategy Business/Corporate Strategy Computer Games e.g. Chess and War Games
Cooperation through negotiation strategy, e.g.
Computerized Personal Assistant Routing Of Telecommunication Network Distribution Of Electricity in Electrical Grids Air Traffic Controlling Electronic Service Management And Communication NetworksThe question remained is how do the agents, acting as our surrogates in encounters with other intelligent agents, make constuctive or optimal decisions that best represent our interests, and compromise when that is to our advantage. In multi-agent environment, effective planning or strategy requires that the automated IA have an ability to reason about the beliefs, intentions and likely actions of other agents. Also, these agents must be capable of detecting that there is a conflict between them, deciding how the conflict can be resolved and then execute the best action available which will satisfy all of them.
The link between intelligent agent and game theory is established. The intelligent agents apply game theory to develop strategies that are essential in implementations of the users' tasks. Various stages of analyzing, reasoning, understanding, evaluating, predicting and executing an action must be performed by applying an optimal strategy for optimum results.
Back to Survey Home Page