COMP6203-2019/20 Intelligent Agents Coursework
Specification
Enrico H. Gerding, [email protected]
Updated on: November 8, 2019
Deliverable Deadline Feedback Marking Scheme Weight
Negotiation
Agent
Dec 10,
4pm
Jan 7 The score that your agent achieves in the class
tournament will determine 20% of the total mod-
ule mark. The score will be an average of the per-
formance based on multiple criteria and negotia-
tion scenarios.
20%
Group
Report
Jan 7,
4pm
Feb 4 Top scoring reports will describe in detail the chal-
lenge that the agent faces, and the design of the
strategy implemented. They will present qualita-
tive and quantitative analysis of the agents perfor-
mance, and will show evidence that related litera-
ture has been read, understood and applied.
20%
Table 1: Deliverables and Deadlines
Contents
1 Introduction 2
2 Negotiation Setup 2
3 Submitting the Agent 2
4 The Tournament 3
5 The Report 4
6 Individual Contribution and Team Coordinator 5
7 Plagiarism 5
8 Late Submissions 5
9 The International Automated Negotiating Agents Competition 7
10 A Brief Negotiation Tutorial 7
1 Introduction
This assignment is about building your own negotiation agent. Negotiation is a form of interaction in
which two (or more) parties, with conflicting interests and a desire to cooperate, try to reach a mutually
acceptable agreement. Negotiation between parties can in many ways be modeled as a game, and game
theory is useful to analyze the behavior of negotiating parties. Negotiation is, however, also different from
many board games such as chess and reversi. One of the most important differences is that negotiation
as we will study it in this practical assignment never is a zero-sum game. That is, a typical negotiation
does not have a winner who takes all and a loser who gets nothing. In order to start a negotiation, it is
only reasonable for both parties to believe that there is a win-win situation where both parties can gain
by obtaining a deal through negotiation. Another difference is that the domain of negotiation (what the
negotiation is about) may be quite different from one negotiation to the other. Finally, in negotiation there
is a lot of uncertainty: a negotiation agent typically does not know the negotiation strategy used by its
opponent, or even know what outcome the other agent prefers. In fact, as we will see, an agent may not
even know his own preferences entirely.
For this assignment you will build your own negotiating software agent to participate in the agent
negotiation competition, which uses the GENIUS framework. The implementation is in Java and you will
work in a team of up to 4 people. In addition, you will need to submit a group report describing the agent
and performing an analysis of the agents. See Table 1 for the hand in dates.
2 Negotiation Setup
The negotiation will run using the GENIUS framework. It will be a bilateral negotiation between 2 agents,
using the Stacked Alternating Offers Protocol. Negotiations are conducted using various multi-issue
preference domains, which are described by additive weighted utility functions. In the negotiation tour-
nament setup that will be used for the coursework there is preference uncertainty, i.e. the agents have
uncertainty about their own preferences. Specifically, the agents will have a ranking of a limited set of
outcomes, and no access to their entire utility function. However, the agent can elicit additional informa-
tion from a virtual user at a fixed cost (see Section 10.5 for more details). Also, the agents will not have
any knowledge of the preferences of its opponent. Negotiation is time based (as opposed to round based)
and each negotiation lasts 90 seconds (1.5 minutes). Negotiations will have imperfect information about
their own preferences, which means that they only have a partial order of the preferences. More details are
available in Section 10 below.
3 Submitting the Agent
Please follow the next instructions carefully or your agent will not work and so the group will receive
no marks for agent performance. All your code should be placed in a package called groupn, where
n is the group number that will be allocated to you.1 The main agent class (containing an implementation
of the methods chooseAction, receiveMessage, etc.) should be named Agentn, where n is the
group number. For example, for group 5, the resulting fully qualified name of the agent object becomes
group5.Agent5.2.
You then need to produce a JAR file containing all the relevant binaries (.class files) to run the agent
as well as the corresponding source code (.java files). You should not include any files or classes that
are already part of the genius framework (such as genius-xxx.jar). The name of the JAR file does
not matter as long as it has the jar extension.
Most IDEs such as Eclipse support the generation of JAR files. However, you can also do this on the
command line by using the program jar.exe. If this executable is not found, this is typically located
1If you are not familiar with the concept of a java package, check out various online tutorials such as https://www.
w3schools.in/java-tutorial/packages/.
2Note that the dot here indicates that object Agent5 is in package group5, and the term ”fully qualified name” refers to the
complete path including all the packages.
2
(on a PC) inside the Program Folder, e.g. C:\Program Files\Java\jdk1.8.0 60\bin\jar. The
exact directory will vary depending on the version of java that you have installed.
For example, for group 1, if your source files are in a folder called src and the binaries in a folder
called bin, then you can create the jar file by the following steps:
1. Create a new group1.jar file and add the source code files by using the create (c) option as
follows:
jar cvf group1.jar -C src .
2. Next, add the binary files using the update (u) option:
jar uvf group1.jar -C bin .
3. Finally, check that all the necessary files are there:
jar tvf group1.jar
When executing these commands, the output should look something like this:
In particular, make sure that both the java and class files are included and they both within the group1
directory (if your group is 1).
Finally, the JAR file needs to be submitted through the handin system by the deadline. Only one agent
per group should be submitted. You can submit multiple times. The most recent valid submission will
be the one used in the final competition, irrespective of who uploads the agent.
Submission Check List. When submitting your agent make sure that:
• The agent object has the appropriate name.
• The agent object is contained in the appropriate package.
• The JAR file contains both the sourcecode and binaries necessary to run your agent.
• You have NOT included any jar files or classes from the GENIUS platform.
4 The Tournament
The submitted agent will participate in a tournament with other agents from the module. Given the number
of participants it may not be possible for each agent to play against all other agents. In that case, each
agent will be randomly grouped with other agents to form a tournament. Within each tournament, each
agent will play against each other on several domains in the configuration as mentioned above. Your agent
should be generic enough to play on different domain sizes and work with different degrees of preference
uncertainty. In this year’s tournament only domains with discrete issues will be used during the competition
(see the GENIUS manual for what these terms mean). Domain sizes will vary from very small (less than
10 different offers possible) to very large (up to 25,000 possible offers).
Each agent will participate in thousands of negotiations against agents designed by other teams in the
same cohort. The agent’s mark is proportional to its average performance. This performance is based on
two factors: (1) the individual utility achieved, and (2) the Euclidean distance of the agreement from the
3
Nash bargaining solution. The latter is given by:√
m
∑
i=1
(Ui(o∗)−Ui(oNBS))2
where Ui(·) is the utility for agent i for an offer (and the reserve price in case of a disagreement), o∗ is
the agreed offer (or a disagreement), oNBS is the Nash bargaining solution (see Section 10.2), and m is the
number of agents (normally 2).
In addition, the agents will be tested on domains of different sizes. For each of the two categories and
for each domain, the mark will be scaled such that the best agent (i.e. the highest individual utility for the
first category, and the lowest distance for the second category) will receive the maximum score and the
average score across the cohort will be around 65%. The score will be scaled separately for each category
and domain. Therefore, one group might receive the highest score for the individual utility category,
whereas another group might have the highest score for getting the lowest distance. Both categories have
equal weight.
Agents may be disqualified and receive zero marks if they violate the spirit of fair play. In partic-
ular, the following behaviors are strictly prohibited: designing an agent in such a way that it benefits
some specific other agent, starting new Threads, or hacking the API in any way.
5 The Report
Each group needs to submit a report of up to 2500 words excluding abstract, tables, figures, references
and appendix (this is an upper limit and should not be a goal) and no more than 6 double column pages in
total including references and appendices. Any report exceeding the word limit will be penalised and those
exceeding the page limit may not be marked. The report should be written in the style of a research paper
and describe at a minimum:
1. The overall design of the agent including various aspects of the strategy (e.g. the concession strategy,
how your agent deals with preference uncertainty, the acceptance strategy, etc), using pseudocode
where applicable.
2. The reasons behind the specific design of the strategy that it employed, and how it compares to and/or
varies from existing approaches. It should refer to relevant literature as appropriate.
3. An extensive evaluation of the agents performance based on your chosen metrics, which compares
your agent against some benchmarks (e.g. other agents).
4. A critical evaluation of the agent and how this can be improved.
5. A statement regarding the contribution of individual team members.
You are encouraged to evaluate different variants of the agent strategy and use this to motivate the final
design decisions, and/or how your submitted agent could be improved. You could also evaluate specific
aspects of the strategy, e.g. the utility estimation approach. It is expected that the report will contain several
graphs and/or tables showing the results of the analysis. It should also cite relevant literature especially for
motivating the design choices but also comparing and contrasting the strategy to existing literature. Note
that there is no need to describe the competition itself in detail. A brief overview may be included or if
specific details of the competition are needed to motivate the strategy.
The report should contain the author names, student numbers, group number, word count, and
be formatted as a double column academic paper. You will find a template for this on the course website.
Please see Table 2 for an indicative marking scheme.
4
6 Individual Contribution and Team Coordinator
To recognize that the contributions of each individual in the team may vary, we ask each team to specify the
individual contribution of each group member in a brief statement and to include this as part of the report.
The individual contribution can comprise up to 25% of the overall mark. The statement should contain the
relative percentage contribution for the each individual on the agent development and a separate one for
the report and evaluation. For example:
AGENT: Alice 30%, Bob 20%, Charlie 30%, Dominic 20%.
REPORT AND EVALUATION: Alice 20%, Bob 30%, Charlie 20%, Dominic 30%.
In addition, this needs to be supported by a short explanation, justifying any differences. The percent-
ages along with the supporting statement should be placed in a section entitled ‘Individual Contribution’
and does not count towards the word count (although the entire document should be within the page limit).
These individual contributions need to be agreed by all team members. The module leader retains the
option to deviate from the stated individual contributions (e.g. if no justification is included).
In deciding on individual contributions, note that contributions are not limited to programming or report
writing. Reading the literature, attending the labs, running experiments, managing the team and organising
meetings, also all count as contributions towards the coursework. Also, some teams may decide to develop
several versions of the agent, and so even when the code is not used in the the final version, this can still
be considered as a contribution. It is advisable that a record of effort is kept in case of disputes, e.g. in the
form of commits and meeting minutes.
Each team should appoint a team coordinator who should be the main point of contact with the lecturer
and submits the final report. Also, although the individual contributions need to be agreed by all, the team
coordinator should be responsible for writing up the individual contribution section.
7 Plagiarism
Both the agent sourcecode and the report need to be the student’s own work unless mentioned otherwise.
For the report, also tables and figures etc should be your own (unless they are from an existing paper and
source is cited appropriately). Be careful with sharing your material (such as tables and figures) with other
groups since enabling others to plagiarise is equally a breach of academic integrity. Hence, if multiple
reports are found with identical text/figures/tables/etc, ALL will be subject to plagiarism penalties and
reported to the Academic Integrity Offer.
For the agent, you can use the code from the ExampleAgent provided, but anything else needs to be
clearly acknowledged in the report and when submitting the agent. Note that you are not allowed to
directly use code of agents programmed by others, including agents who have previously participated in
the international competition. However, you are allowed to use ideas and strategies reported in academic
papers, as long as you implement these strategies yourselves and you acknowledge the papers in your
report. In case of doubt, feel free to ask! Any violations, deliberate or otherwise, will be reported to the
Academic Integrity Officer with no exception.
More information about academic integrity can be found here.
8 Late Submissions
Late submissions will be penalised according to the standard rules. If agents are submitted late, they may
not participate in the full tournament. Note that, if the submission is late due to an invalid submission, this
is still subject to late penalties. It is your responsibility that you submit on time and that the submitted
agent validates correctly.
5
Category Sample Feedback
Indicative
Marks
Structure and
Writing (max.
5 points)
The report does not follow a proper layout and structure and contains
many spelling and/or grammar mistakes
0
The report conforms with the requirements, and contains few/no
spelling and grammar mistakes
5
Description
and Under-
standing
(max. 30
points)
The agent description is inadequate/missing 0
The agent is explained but some parts are incomplete, not sufficiently
formal (e.g. using mostly words with few equations or algorithms), and
with very little motivation
10
The agent is explained and mostly complete, containing some formal
algorithms, and motivation for some of the choices, showing a good
level of understanding
20
There is an excellent agent description which is complete and clear,
yet concisely written and using formal notation and algorithms. The
strategy is well motivated and demonstrates an excellent understanding.
30
Challenge,
sophistica-
tion,
originality
(max. 15
points)
The strategy is very basic and shows no originality 0
The strategy is largely based on a single paper with no/ few new ele-
ments
5
The strategy is based on existing literature and has been adapted to show
some innovation
10
The strategy has many novel and sophisticated elements, mixing ideas
from several papers
15
Literature
(max. 10
points)
The report contains no references to the literature 0
There are some references to the literature but it is not clear how these
references are used to inform the strategy of the agent
5
There is clear evidence that the literature was read and understood, and
used to motivate and support the development of the agent strategy
10
Evaluation
and Analysis
(max. 40
points)
There is no evaluation of the agent performance 0
There is some evaluation of the agent performance, showing tables and
graphs, but little/no analysis of the results
10
There is an adequate evaluation and some discussion of the results but
little/no critical evaluation or ways to improve the agents
20
There is a very good evaluation and the discussion shows a good un-
derstanding of the performance of the agent, and some ways to improve
the strategy
30
The evaluation is extensive considering various metrics and bench-
marks, and there is an excellent critical discussion of the performance
of the agent, and ways to overcome the deficiencies and improving the
agent
40
Table 2: Indicative Report Marking Scheme. Indicative marks are given out of a 100 points. The report is
worth 20% of the overall mark.
6
9 The International Automated Negotiating Agents Competition
An international agent negotiation competition (ANAC) is being held on a yearly basis, and the coursework
is based on this competition. The University of Southampton is actively involved in shaping this compe-
tition. Last year was the 10th installment, which is typically held at a high profile conference. In the last
few years, it was held at the International Joint Conference on Artificial Intelligence (IJCAI), one of the
very top AI conferences. Groups are encouraged to submit their agent to next year’s competition, which in
2020 will be held at IJCAI in Japan. Some previous competitions can be found here:
• ANAC 2019
• ANAC 2018
10 A Brief Negotiation Tutorial
This section provides a more detailed description of the negotiation process, the challenges, and points to
some of the existing literature on this topic.
10.1 Overview
A negotiation is defined by its negotiation domain, which tells you what issues are negotiable and what
value-range each issue can take. Negotiation can involve a range of issues, from quite personal ones such
as deciding on a holiday destination to business deals such as trading orange juice in international trade. For
example, the party domain, which is one of the pre-defined domains, is about organizing a party together
with some friends and negotiating what you want to spend the available money on. The domain specifies a
preference profile for each agent, that captures each agent’s individual preferences with regards to the party
domain. The result will be a formal preference function that maps each possible outcome of a negotiation
to a utility in the range of 0 to 1.
Given the domain, the next task involves thinking about a strategy used to perform the negotiation itself.
In negotiation you need at least two strategies: an offering strategy (what to bid when), and an acceptance
strategy (when to accept or reject offers, and when to stop negotating - walk away). The most important
part of this assignment concerns the negotiation phase itself, i.e. the exchange of offers between you (or
your software agent) and an opponent.
A negotiation instance is also called a negotiation session. In a session two agents negotiate with each
other to settle a conflict and negotiate a deal. Each negotiation session is limited by a fixed amount of time.
At the end of a session, a score is determined for both agents based on the utility of the deal for each agent
if there is a deal, otherwise the score equals the reservation value (which may be zero but is not always the
case). In a sense, there is no winner since each agent will obtain a score based on the outcome and its own
utility function. A failed negotiation, in the sense that no deal is reached, thus is a missed opportunity for
both parties. In the tournament that will be played, each agent will negotiate with many other agents and
the scores of each session are recorded and averaged to obtain an overall score for the agent. A ranking
will be compiled using these overall scores.
10.2 Understanding a Negotiation Outcome
A negotiation outcome can be assessed based on an agent’s individual benefit, or it can be assessed at a
joint level, e.g. to see whether a better outcome could have been achieved which would benefit both agents,
and whether the outcome is fair and how this is defined.
In terms of the benefit of the outcome to the individual, this is described by a so-called utility function.
As explained, negotiations involve multiple issues. In GENIUS and in this assignment, we assume utility
functions linearly additive, i.e. they are a weighted function of the utility for individual issues, where the
weight indicates the importance of an issue (e.g. price vs travel time when buying flight tickets). More
formally, let o be an offer, where o j is the proposed value for issue j (e.g. the price). Moreover, let ui, j(o j)
be the utility of agent i for that value. Then the overall utility of the offer, Ui(o), is given by:
7
Offer Utility Agent 1 Utility Agent 2
o1 = 〈0.5,0.5〉 U1(o1) = 0.7∗0.5+0.3∗0.5 = 0.5 U2(o1) = 0.3∗ (1−0.5)+0.7∗ (1−0.5) = 0.5
o2 = 〈1,0〉 U1(o2) = 0.7∗1+0.3∗0 = 0.7 U2(o2) = 0.3∗ (1−0.7)+0.7∗ (1−0.3) = 0.7
o3 = 〈0,1〉 U1(o3) = 0.7∗0+0.3∗1 = 0.3 U2(o3) = 0.3∗ (1−0.3)+0.7∗ (1−0.7) = 0.3
o4 = 〈0,0〉 U1(o3) = 0.7∗0+0.3∗0 = 0 U2(o3) = 0.3∗1+0.7∗1 = 1
o5 = 〈1,1〉 U1(o3) = 0.7∗1+0.3∗1 = 1 U2(o3) = 0.3∗0+0.7∗0 = 0
Table 3: Example of additive utilities for individual agents with 2 negotiation issues.
Ui(o) =
n
∑
j=1
wi, j ·ui, j(o j)
where n is the number of issues under negotiation, and wi, j is the weight of issue j for agent i. Crucially,
both the utility function for each issue, and the weights can be different for different agents, which enables
mutually beneficial outcomes.
For example, consider a setting with 2 agents and 2 issues, where o1,o2 ∈ 0,0.1,0.2, . . . ,1.0 and we
have that u1, j = o j and u2, j = 1−o j for agents 1 and 2 respectively. That is, agent 1 prefers a higher value
for each issue (e.g. the agent is a seller and the value is price), and agent 2 prefers a lower value (e.g.
the agent is a buyer). Also, the agents have different weights: w1 = 〈0.7,0.3〉 and w2 = 〈0.3,0.7〉. That
is, agent 1 finds the first issue more important and agent 2 the second issue. Consider 3 different offers:
o1 = 〈0.5,0.5〉 (both agents get something in the middle), o2 = 〈1,0〉 (agent 1 is happy about the value of
issue 1 but not of issue 2, and vice versa for agent 2) and o3 = 〈0,1〉 (the opposite to the previous). Now
consider the utility for each offer in Table 3. Note that there are many other possible offers/negotiation
outcomes (in this case, with 2 issues and 11 values per issue, there are 112 possible outcomes). Take time
to make sure you understand the table and how these values are calculated. As an exercise, try and derive
the utility for some other offers not in the table.
All of these 3 offers are ‘fair’ in the sense that, for each offer, both agents get the same utility. However,
some are clearly better than others. In particular, offer o2, where agent 1 gets the best value for his most
preferred issue, and agent 2 gets the best value for her most preferred issue, has a utility of 0.7 for both
agents, compared to the lower utility in other cases. This is called a win-win outcome, since both agents
benefit.
It is important to note that, as seen in the example, these win-win outcomes exist even when the agents
have diametrically opposing preferences for individual issues. Indeed, in such cases with diametrically
opposed preferences, it is only possible to obtain win win situations by having multiple issues. If negoti-
ation is only about a single issue, e.g. price, it is typically not possible to get a win-win outcome. Such
negotiations are also referred to as competitive: the only way for one agent to gain, is for the other to lose.
A multi-issue negotiation where win-win outcomes are available, as in the example, are called integrative.
Often, in practice, additional issues are introduced with the specific aim to make the negotiations less com-
petitive and more integrative. For example, a second-hand car dealer may offer a discount on the warranty,
and so the warranty gets introduced as an additional issue alongside the price of the car.
We now analyse the properties of an outcome more formally in terms of the joint utility. A desirable
property is for an outcome to be so-called Pareto optimal (also often referred to as Pareto efficient). An
outcome is Pareto optimal when there does not exist another outcome where both agents can do better. Said
differently, an outcome is Pareto optimal if, for any agent to be better off, the other agent has to be strictly
worse off. In the example, o1 is not Pareto optimal since there exists another offer (e.g. o2) where both
agents are better off. Here, o2 is Pareto optimal, but so are o4 and o5 (see Table 3). This is because there
is no other outcome where both agents are better off. By connecting all the Pareto optimal solutions we
obtain the so-called Pareto frontier. This is visualised in Figure 1, which shows the offers from the table
in terms of both agent’s utilities. Take time to understand these concepts before moving on.
Clearly, aiming to achieve an outcome on the Pareto frontier seems to be the sensible option (although
this in itself is already challenging since there is a lot of uncertainty, as explained further below). However,
a Pareto optimal solution is not unique since there can be many different outcomes on the frontier (as an
8
Figure 1: The outcome space and the Pareto frontier for the 2-issue negotiation domain example.
exercise, try and determine how many outcomes in the example lie on the frontier other than the ones in
the table). Some of these favour one agent over another. Also, in many of the negotiation domains there
can be dozens of issues and hundreds of offers, and the Pareto frontier can look very complex. An example
of a slightly more complex frontier is seen in Figure 2. So what agreement should we aim for? One
possibility is to aim for a ‘fair’ outcome, i.e. one that is good for both parties, since such an outcome is
likely to get accepted by both parties. There are many ways of defining this, but a well known concept
is the Nash bargaining solution or simply Nash solution (note that this notion is NOT related to the Nash
equilibrium other than the fact that they are both introduced by the late Nobel laureate John Nash). A Nash
solution is an outcome that satisfies certain bargaining axioms and may be viewed as ‘fair’ outcome which
is reasonable to accept for both parties. An outcome is said to be a Nash solution whenever it maximises
the product of the utilities minus the disagreement utility (i.e. reserve value). More formally, let Ui(d)
denote the utility of a disagreement, then the aim is to find the outcome o which maximises (for 2 agents):
(U1(o)−U1(d)) · (U2(o)−U2(d))
This solution has some interesting properties, e.g. it is invariant to how the utility functions are scaled
(invariant to so-called affine transformations), it is Pareto optimal, and also it satisfied the symmetry prop-
erty. The latter means that, if the two agents are symmetric (e.g. diametrically opposed and having the
same reservation values), as in our example, then the agents should get the same utility. In the example
with 2 issues, o2 is the Nash bargaining solution. Note that this solution is typically unique.
Other types of solution concepts include: maximising social welfare, which is the sum of utilities
(instead of the product); the egalitarian solution, which maximises the utility of the agent with the lowest
utility; the Kalai-Smorodinski bargaining solution, which chooses the point on the Pareto frontier which is
closest to linear line which goes through the Umax1 ,U
max
2 , where U
max
i is the maximum utility agent i could
achieve individually (see e.g. [8] for more details).
10.3 Deadlines and Discount Factors
Besides considering the utility of the outcomes of a negotiation, time pressure often plays an important
role. Often, negotiations have firm deadlines. For example, if the date of the party has already been fixed,
then the agents should come to an agreement on how to spend the money in organizing the party well in
9
Figure 2: A more complex Pareto frontier example from the Laptop domain.
advance of that day. In the assignment there is a deadline for reaching an agreement. Both agents have
exactly the same deadline and this is common knowledge (both agents ‘know’ when the deadline is). If
they fail to reach an agreement each participant gets their disagreement utility.
Deadlines ensure that negotiations do not last forever, but often result in a deal being clinched at the
last minute. Hence, in addition to a deadline, negotiations can have a different type of time pressure in the
form of a discount factor. Discount factors model the fact that the desirability of the good being traded
may decline with time or other types of urgency (e.g. lost opportunities). This happens when the good is
perishable, for example fruits or other types of perishable food.
The formal modelling of discount factors in the context of automated negotiation and the GENIUS
platform is as follows. Let δ ∈ [0,1] be the discount factor of a domain, and o be a certain outcome. Let t
in [0,1] be the current normalized time, as defined by the timeline. We compute the discounted utility Udisi,t
as follows:
Udisi,t (o) =Ui(o) ·δ t (1)
At the deadline t = 1, the original utility is multiplied by the discount factor. If δ = 1 or not specified at all,
the utility is not affected by time, and such a domain is considered to be undiscounted, while if δ is very
small there is high pressure on the parties to reach an agreement quickly. Note that in GENIUS, discount
factors are part of the preference profiles and therefore can differ between parties.
10.4 Opponent Modelling
Although achieving a Pareto efficient and fair outcome may be desirable, the challenge is that a negotiation
agent has no knowledge of the opponent’s preferences, nor does it have knowledge of the negotiation
strategy. Even the discount factor may be different and unknown. To address this, there is a wide range
of literature on opponent modelling. These papers propose algorithms which try to infer the preferences
and negotiation strategies of the opponent. In terms of additive utility preferences, this means inferring the
weights as well as inferring the utility for individual values for each issue.
There are a wide range approaches, from simple heuristic to machine learning. A simple approach is
to assume that the opponent will start with what is the best offer for them, and will slowly concede. This
will give some indication of which issues the opponent finds more important. A related approach is by
10
using frequency analysis, which has been successfully used by the Hardheaded agent [18]. The assumption
here is that values for issues who appear more frequently in the offers received by the opponent are more
likely to have a high utility for the opponent. Similarly, if certain values for certain issues persist compared
to other issues where there are more frequent changes, this might mean that the weight for that particular
issue is higher.
Examples of agents using more sophisticated approaches include IAMHaggler [24, 25, 23], which uses
Gaussian process regression technique to predict the opponent’s behavior and OMAC Agent [4, 3, 5, 2],
which models the opponent using wavelet decomposition and cubic smoothing spline. In [14], a guessing
heuristic is introduced to infer the opponent preferences.
10.5 Preference Uncertainty and Elicitation
In addition to having no initial knowledge of the opponent, another challenge introduced in the competition
is uncertainty about the agent’s own preferences and the possibility to elicit additional information at a cost.
To understand why preference uncertainty occurs in practice, it is important to understand where the agent
preferences come from in the first place. By definition, autonomous agents act on behalf of people or
organisations. Hence, the preferences need to reflect what people and/or organisations want. The process
of obtaining these preferences is called preference elicitation and is generally costly, both in terms of time,
and hiring experts to do so. Preferences can be very complex (a good classic book that describes this nicely
is by Raiffa [20]). Typically, people find it very difficult to give exact utility values for certain outcomes, or
understanding what the weights might mean. It is typically much easier for people to compare offers in a
pairwise manner and to say which of the two they would prefer [9]. By doing many pairwise comparisons
one can get closer to understanding the true utility function, but in complex negotiations there are simply
too many pairs to compare. As a result, often what you end up with is a partial ordering of preferences.
In the competition, preference uncertainty means that the agent only has ordinal information about
different offers, and only of a subset of the full offer space. Therefore, it may know that it prefers A over
B, but not by how much (i.e. it knows the order but not the utility) and it may not know anything about C.
There are two main ways in which to deal with such situation. One way is to derive an estimated (additive)
utility function from the information given, and then use this utility function during the negotiation. Some
built in functions are provided to help with this (see the GENIUS manual for more detail) but you are
encouraged to come up with your own approach or use an existing approaches from the literature (e.g. that
are used for opponent modelling). For example, a more sophisticated approach to derive the preferences
has been developed in [22] using linear programming. Another way is to negotiate with the incomplete set
of ordinal preferences directly, without the ‘translation’ step.
In addition, there is the option to elicit or ‘buy’ additional information about an offer. That is, the agent
can ask to add any unranked offer as part of the ordinal preference ranking, but this comes at a fixed cost.
The cost is set as part of the domain. This simulates the idea of having to ask the user, and that preference
elicitation is costly in terms of effort. The elicitation aspect raises many interesting research questions to
decide how many offers to elicit information about, and which ones.
10.6 Negotiation Strategies and Techniques
As already mentioned, a negotiation strategy needs to determine what to bid (the offering strategy), and
whether to accept if an offer is received (the acceptance strategy). These are typically related. Assuming the
agent knows or has estimated its own utility, a common approach is to split the strategy into two separate
components: (1) determining the utility threshold level at which to make and accept offers, often referred
to as the concession strategy, and (2) finding the ‘best’ offer at or above the chosen utility threshold.
Regarding the concession strategy, this can be a time-based schedule or adaptive which responds to the
opponent. Examples of time-based concession strategies are Boulware (concede slow to begin with, and
then concede faster as you get closer to the deadline), Conceder (concede fast from the beginning), Linear
(concede linearly), Hardheaded (don’t concede until the very end). See e.g. [6]. A well known adaptive
strategy is tit-for-tat, which concedes a similar amount to what the opponent is perceived to concede ([7, 1]).
Many approaches use one of the time-based strategies but then change the parameters of this strategy in
response to what the apponent is doing, e.g. changing the target utility (which is the utility threshold at the
11
deadline). A notable ANAC winner agent is Agent K [16, 17], which calculates its target utility based on the
average and variance of previous bids and employs a sophisticated acceptance strategy. Furthermore, the
CUHK Agent [10, 11] adaptively adjusts its acceptance threshold based on domain and opponent analysis.
Another crucial factor is finding the best offer given the current utility level, i.e. deciding on a specific
value for each issue. An early approach is by Faratin et al. [7] which chooses an offer that is closest in
terms of similarity to the opponent’s previous offer, but at the same time is above the utility threshold of
the proposing agent. A similar approach is taken by [21], who propose the Orthogonal strategy which
minimises the Euclidean distance between the most recent offer made by the opponent, and offers at the
agent’s utility threshold level. They show that, for certain types of domains, if concession is sufficiently
slow, and both agents use this approach, the agreed offer is guaranteed to be Pareto optimal. Another
common approach is to first estimate the opponent model (as discussed before), and then choosing amongst
all the offers above the utility thresholds the one which has the highest utility for the opponent. This
maximises the chances that the offer is above the opponent acceptance threshold, and therefore will be
accepted.
There is a vast range of other negotiation agents in the literature that have been developed over the
past decades, e.g. Zeng and Sycara [26], who introduce a generic agent called Bazaar; Karp et al. [15],
who take a game-theoretic view and propose a negotiation strategy based on game trees; Jonker et al. [14],
who propose a a concession oriented strategy called ABMP; and Lin et al. [19], who propose an agent
negotiator called QOAgent; The Fawkes, which combines the best bidding, learning, and accepting strategy
components; Meta-Agent [12, 13], which, for any given negotiation domain, dynamically selects the most
successful ANAC agent to produce an offer, and many more.
In designing your own agent, you should search for and read relevant papers, including those from past
ANAC competitions. See also the Student WIKI where a list of papers is maintained.
References
[1] Tim Baarslag, Koen V. Hindriks, and Catholijn M. Jonker. A tit for tat negotiation strategy for
real-time bilateral negotiations. In Takayuki Ito, Minjie Zhang, Valentin Robu, and Tokuro Matsuo,
editors, Complex Automated Negotiations: Theories, Models, and Software Competitions, volume
435 of Studies in Computational Intelligence, pages 229–233. Springer Berlin Heidelberg, 2013.
[2] Siqi Chen, Haitham Bou Ammar, Karl Tuyls, and Gerhard Weiss. Optimizing complex automated
negotiation using sparse pseudo-input gaussian processes. In Proceedings of the 2013 International
Conference on Autonomous Agents and Multi-agent Systems, AAMAS ’13, pages 707–714, Richland,
SC, 2013. International Foundation for Autonomous Agents and Multiagent Systems.
[3] Siqi Chen and Gerhard Weiss. An efficient and adaptive approach to negotiation in complex environ-
ments. In Luc De Raedt, Christian Bessiere, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik
Heintz, and Peter J.F. Lucas, editors, ECAI, volume 242 of Frontiers in Artificial Intelligence and
Applications, pages 228–233. IOS Press, 2012.
[4] Siqi Chen and Gerhard Weiss. A novel strategy for efficient negotiation in complex environments.
In Ingo J. Timm and Christian Guttmann, editors, Multiagent System Technologies, volume 7598 of
Lecture Notes in Computer Science, pages 68–82. Springer Berlin Heidelberg, 2012.
[5] Siqi Chen and Gerhard Weiss. An efficient automated negotiation strategy for complex environments.
Engineering Applications of Artificial Intelligence, 2013.
[6] P. Faratin, C. Sierra, and N.R. Jennings. Negotiation decision functions for autonomous agents.
Robotics and Autonomous Systems, 24(3):159–182, 1998.
[7] Peyman Faratin, Carles Sierra, and Nicholas R. Jennings. Using similarity criteria to make issue
trade-offs in automated negotiations. Artificial Intelligence, 142(2):205 – 237, 2002.
[8] Enrico H Gerding, DDB van Bragt, and JA La Poutre. Scientific approaches and techniques for
negotiation. Report. SEN: Software engineering/Centrum voor wiskunde en informatica, 2000.
12
[9] Shengbo Guo and Scott Sanner. Real-time multiattribute bayesian preference elicitation with pair-
wise comparison queries. In Proceedings of the Thirteenth International Conference on Artificial
Intelligence and Statistics, pages 289–296, 2010.
[10] Jianye Hao and Ho-fung Leung. ABiNeS: An adaptive bilateral negotiating strategy over multiple
items. In Proceedings of the The 2012 IEEE/WIC/ACM International Joint Conferences on Web
Intelligence and Intelligent Agent Technology, volume 2 of WI-IAT ’12, pages 95–102, Washington,
DC, USA, Dec 2012. IEEE Computer Society.
[11] Jianye Hao and Ho-fung Leung. CUHK agent: an adaptive negotiation strategy for bilateral negotia-
tions over multiple items. In Ivan Marsa-Maestre, Miguel A. Lopez-Carmona, Takayuki Ito, Minjie
Zhang, Quan Bai, and Katsuhide Fujita, editors, Novel Insights in Agent-based Complex Automated
Negotiation, volume 535 of Studies in Computational Intelligence, pages 171–179. Springer, Japan,
2014.
[12] L. Ilany and Y. (K.) Gal. The simple-meta agent. In I. Marsa-Maestre, M.A. Lopez-Carmona, T. Ito,
M. Zhang, Q. Bai, and K. Fujita, editors, Novel Insights in Agent-based Complex Automated Negoti-
ation, volume 535 of Studies in Computational Intelligence, pages 197–200. Springer, Japan, 2014.
[13] Litan Ilany and Yakov Gal. Algorithm selection in bilateral negotiation. In Proceedings of the Twenty-
Seventh AAAI Conference on Artificial Intelligence (AAAI 2013), 2013.
[14] Catholijn M. Jonker, Valentin Robu, and Jan Treur. An agent architecture for multi-attribute ne-
gotiation using incomplete preference information. Autonomous Agents and Multi-Agent Systems,
15:221–252, 2007.
[15] Alan H. Karp, Ren Wu, Kay-yut Chen, and Alex Zhang. A game tree strategy for automated negoti-
ation. In Proceedings of the 5th ACM conference on Electronic commerce, EC ’04, pages 228–229,
New York, NY, USA, 2004. ACM.
[16] Shogo Kawaguchi, Katsuhide Fujita, and Takayuki Ito. Compromising strategy based on estimated
maximum utility for automated negotiating agents. In Takayuki Ito, Minjie Zhang, Valentin Robu,
Shaheen Fatima, and Tokuro Matsuo, editors, New Trends in Agent-based Complex Automated Ne-
gotiations, Seriesof Studies in Computational Intelligence, pages 137–144, Berlin, Heidelberg, 2012.
Springer-Verlag. URL = http://link.springer.com/content/pdf/10.1007
[17] Shogo Kawaguchi, Katsuhide Fujita, and Takayuki Ito. Agentk2: Compromising strategy based
on estimated maximum utility for automated negotiating agents. In Takayuki Ito, Minjie Zhang,
Valentin Robu, and Tokuro Matsuo, editors, Complex Automated Negotiations: Theories, Models,
and Software Competitions, volume 435 of Studies in Computational Intelligence, pages 235–241.
Springer Berlin Heidelberg, 2013.
[18] Thijs Krimpen, Daphne Looije, and Siamak Hajizadeh. Hardheaded. In Takayuki Ito, Minjie Zhang,
Valentin Robu, and Tokuro Matsuo, editors, Complex Automated Negotiations: Theories, Models,
and Software Competitions, volume 435 of Studies in Computational Intelligence, pages 223–227.
Springer Berlin Heidelberg, 2013.
[19] Raz Lin, Sarit Kraus, Jonathan Wilkenfeld, and James Barry. Negotiating with bounded rational
agents in environments with incomplete information using an automated agent. Artificial Intelligence,
172(6-7):823 – 851, 2008.
[20] Howard Raiffa. The Art and Science of Negotiation. Belknap Press, reprint edition, 2005.
[21] DJA Somefun, Enrico H Gerding, and Johannes A La Poutre´. Efficient methods for automated multi-
issue negotiation: Negotiating over a two-part tariff. International Journal of Intelligent Systems,
21(1):99–119, 2006.
13
[22] Dimitrios Tsimpoukis, Tim Baarslag, Michael Kaisers, and Nikolaos G Paterakis. Automated negotia-
tions under user preference uncertainty: A linear programming approach. In International Conference
on Agreement Technologies, pages 115–129. Springer, 2018.
[23] Colin R. Williams. Practical Strategies for Agent-Based Negotiation in Complex Environments. PhD
thesis, University of Southampton, Dec 2012.
[24] Colin R. Williams, Valentin Robu, Enrico H. Gerding, and Nicholas R. Jennings. Iamhaggler: A
negotiation agent for complex environments. In Takayuki Ito, Minjie Zhang, Valentin Robu, Shaheen
Fatima, and Tokuro Matsuo, editors, New Trends in Agent-based Complex Automated Negotiations,
Series of Studies in Computational Intelligence, pages 151–158, Berlin, Heidelberg, 2012. Springer-
Verlag. URL = http://eprints.soton.ac.uk/271662/1/acan2010.pdf.
[25] Colin R. Williams, Valentin Robu, Enrico H. Gerding, and Nicholas R. Jennings. Iamhaggler2011:
A gaussian process regression based negotiation agent. In Takayuki Ito, Minjie Zhang, Valentin
Robu, and Tokuro Matsuo, editors, Complex Automated Negotiations: Theories, Models, and Soft-
ware Competitions, volume 435 of Studies in Computational Intelligence, pages 209–212. Springer
Berlin Heidelberg, 2013.
[26] Dajun Zeng and Katia P. Sycara. Bayesian learning in negotiation. International Journal of Human-
Computer Studies, 48(1):125 – 141, 1998.
14