Information Technology Reference
In-Depth Information
2.3 Monotonicity of Mixed Strategies
It is often argued [9,3] that the process of negotiation should be designed in a
way that agents make concessions, or seek for joint improvements, i.e. in the
form of trade-off proposals, in a negotiation. This implies monotonic behaviour:
an agent makes proposals such that the aggregated utility of its next offer is
equal (trade-off) or lower (concession) than the aggregated utility of its previous
offer, such that
t
n
+1
a→b
t
n
+1
a→b
U
a
(
≤ U
a
(
). In the following, we say that agents have
monotonic concession behaviour if they propose offers according to this principle.
In single-issue negotiations agents typically have opposing utility structures such
that a non-monotonic sequence of offers increases the risk of a withdrawal of the
opponent. In that sense an agent
x
)
x
is acting rational in single-issue negotiations
if it concedes towards the last offer of its opponent, thereby trying to increase
the opponent's utility such that the sequence of its own utilities is monotonically
decreasing. In multi-issue negotiations, however, an offer of an agent
a
a
with a
higher aggregated utility for
as compared to its previous offer can not eas-
ily be detected by the opponent as the utility structures are unknown to each
other. If, in turn, the opponent's utility for
a
a
's last offer is lower as
a
's previous
offers, the opponent may assume that
made a trade-off proposal and can there-
fore not detect the cause of such non-monotonic behaviour. It is also argued that
agents behaving non-monotonic under time-constraints can be advantageous and
the question whether automated negotiation should be designed in a way that
non-monotonic behaviour is ensured is widely discussed in the research liter-
ature [12]. However, non-monotonicity in the sequence of proposed offers and
their respective aggregated utilities of an agent can easily emerge at any time
as a result of the
dynamic effects of an agent system in which the agents use
mixed strategies
. Intuitively, non-monotonic behaviour can occur when an agent
changes its strategy, e.g. the mixing weights, during the encounter. However,
automatic non-monotonic behaviour can also be observed when imitative and
non-imitative tactics are mixed by a linear weighted combination without the
agent changing its strategy, i.e. even in the case of
static strategy settings and
mixing weights
. A simple example shall demonstrate this:
Example 1:
Assume a negotiation between two agents
a
a
and
b
at time
t
n
where agent
a
applies a mixed strategy with static weight
γ
using one time-
τ
time
(
dependent tactic
t
n
+1
) and one imitative tactic simply copying the con-
cession of the partner (basic absolute tit-for-tat):
x
t
n
−
2
b→a
,x
t
n
−
1
τ
beh
(
a→b
,x
t
b→a
)=
x
t
n
−
2
x
t
n
−
1
a→b
x
t
n
+1
a→b
b→a
−x
t
n
γ · τ
time
(
+
such that agent
a
's next offer is
=
t
n
+1
)+
b→a
t
n
−
2
t
n
−
1
t
n
−
2
t
n
−
1
· τ
beh
(
a→b
,x
t
n
a→b
,x
t
n
(1
− γ
)
x
b→a
,x
). Given the thread (
...,x
b→a
,x
)=
b→a
b→a
(
...,
30
,
10
,
20), agent
a
's next time-dependent proposal
τ
time
(
t
n
+1
)=11 and the
mixing weight
γ
=0
.
5, the next counteroffer is
x
t
n
+1
a→b
=0
.
5
·
11+0
.
5
·
20 = 15
.
5.
x
t
n
+2
b→a
Now assume, agent
b
replies with a comparatively small concession
=19
and agent
a
's next time-dependent proposal is
τ
time
(
t
n
+3
) = 12, then agent
a
's
x
t
n
+3
a→b
response is lower than its previous offer and thus non-monotonic with
=
0
25. In this example the non-monotonic behaviour emerges
in static mixed strategies with imitative and non-imitative tactics even though
.
5
·
12+0
.
5
·
16
.
5=14
.
