Information Technology Reference
In-Depth Information
for i=0:m
{
a
+
i
∗
(
x
−
a
)
/
mw ea
= max(
x
,
x
/
2)
// uniform
l
i
←
1
/
α
+
i
∗
(2
/
α
m
)
// exponential
d
←
∞
while d
>
stopping condition,
l
0
←
arg max
l
0
E
ν
(
l
0
,...,
l
m
)
where
x
≥
l
0
<
l
1
for i=1:m-1
l
i
←
arg max
l
i
E
ν
(
l
0
,...,
l
m
)
where
l
i
−
1
<
l
i
<
l
i
+1
l
m
←
arg max
l
m
E
ν
(
l
0
,...,
l
m
)
where
l
m
−
1
<
l
m
≤
x
d
←
0
for i=0:m,
d
←
max(
d
,
abs(
l
i
−
l
i
))
l
i
←
l
i
Fig. 2.
Pseudo-code algorithm for calculating solutions for the optimal bid levels
4.1
Optimal Discrete Bid Levels
The expression presented in the last section describes the expected revenue of the auc-
tion when discrete bid levels
l
0
...
l
m
are used. Thus, in order to find the optimal bid
levels in this case, we must find the values
l
0
...
l
m
that maximise this expression. In
general, it is not possible to perform this maximisation analytically, so we must use
a numerical algorithm. Now, given that there are many numerical multi-dimensional
optimisation algorithms available (see Numerical Recipes [11] for examples), two key
features of this problem guide our choice. Firstly, since each term in the summation in
equation 7 contains only pairs of bid levels (i.e.
l
i
and
l
i
+1
), we note that maximising
this expression, and thus solving
l
i
= 0, is equivalent to solving a tri-diagonal set
of
m
+ 1 simultaneous equations, that, by denoting
δ
E
ν
/
δ
δ
E
ν
/
δ
l
i
as
f
i
, we can write as:
f
0
(
l
0
,
l
1
)=0
f
i
(
l
i
−
1
,
l
i
,
l
i
+1
)=0f r
i
= 1to
m
−
1
(8)
f
m
(
l
m
−
1
,
l
m
)=0
Secondly, the solutions to these equations are constrained such that their ordering re-
mains constant i.e.
l
i
−
1
<
l
i
<
l
i
+1
. A general purpose optimisation package will fail to
exploit the first feature and will be heavily constrained by the second. However, we can
produce a simple and efficient numerical algorithm by using Jacobi iteration whereby
we iteratively solve the
m
+ 1 simultaneous equations [5]. That is, we fix all other bid
levels, and we find the value of
l
i
that maximises equation 7 given that
l
i
−
1
<
l
i
<
l
i
+1
.
The expression is well behaved in this range and has a single maximum that can be
found using hill climbing or a gradient based method. We update all
l
i
and then iterate
the process until the bid levels converge to the necessary accuracy.
We present this algorithm in figure 2, noting that the expression
E
ν
(
l
0
,...,
l
m
) rep-
resents the revenue expression in equation 7. Whilst we do not prove the convergence
properties of this iterative algorithm here, in our experiments it converged reliably given
