Information Technology Reference
In-Depth Information
j
++
end while
if
T
1
(
X
)
then
disagree
B
(
O
2
)
else
agree
B
(
O
2
)
end if
end if
end dialogue
W
The algorithm given above is for open persuasion; for partial persuasion the inquiries
will concern
τ
2
j
only. As noted above, each pass through the while loop is referred to
as a
step
in the remainder of the paper. Each step establishes or verifies the truth values
for one attribute.
5R su s
In this section we describe a series of results that show our strategy
to be an opti-
mal strategy for a number of representative situations. The first of these is where the
persuadee has no initial opinions as to the facts: the attributes of the options will be dis-
covered from the dialogue, and are all considered equally likely at the outset. Theorem
1showsthat
S
is optimal for this scenario
1
.
S
Theorem 1:
Suppose we have two options
O
1
and
O
2
of equal prior utility,
m
attributes,
which are equally likely to be true or false for each option, and
m
positive weights
assigned to the attributes. Then an optimal strategy, in the sense that the algorithm
terminates in the expected fewest number of steps, is to inquire about the attributes in
descending order of weight (strategy
S
). First we prove two preliminary lemmas.
Lemma 1:
Given a set
A
of
n
attributes, the probability that the algorithm will terminate
in not more than
n
steps is independent of the order in which we inquire about these
attributes. We term this probability
P
(
X
)
where
X
=
{
w
Ag
(
a
j
):
a
j
∈
A
}
.
Since we are concerned with the opinions of only one agent (the persuadee), we shall
use the simplified notation
w
j
for
w
Ag
(
a
j
)
.
Proof of Lemma 1:
Let
X
=
{
w
1
, ...w
n
}⊆
W
be the set of weights associated with
T
1
(
X
)
holds, the algorithm terminates in at most
n
steps, by
the attributes examined. If
Definition 9.
Conversely if
O
1
is determined in
n
1
≤ n
steps after considering
X
1
⊆ X
then
T
1
(
X
1
)
holds.
Subtracting
w
j
from both sides of
T
1
(
X
1
)
gives
w
j
∈X\X
1
[Inequality 1]:
w
j
∈X
1
w
j
>
w
j
∈
τ
1
j
w
j
−
τ
2
j
w
j
−
w
j
,
w
j
∈X
1
w
j
∈
X
\
X
1
W
\
X
since (
W
\
X
1
)
\
(
X
\
X
1
)
=
W
\
X
.
1
We would like to thank Michael Bench-Capon for his insights regarding the proof strategy
used in this section.
