Information Technology Reference
In-Depth Information
Learning Environmental Parameters for the Design of
Optimal English Auctions with Discrete Bid Levels
A. Rogers
1
,E.David
1
,J.Schiff
2
,S.Kraus
3
, and N.R. Jennings
1
1
Electronics and Computer Science, University of Southampton, Southampton, SO17 1BJ, UK
2
Department of Mathematics, Bar-Ilan University, Ramat-Gan 52900, Israel
3
Department of Computer Science, Bar-Ilan University, Ramat-Gan 52900, Israel
{
acr, ed, nrj
}
@ecs.soton.ac.uk,
{
schiff@math, sarit@cs
}
.biu.ac.il
Abstract.
In this paper we consider the optimal design of English auctions with
discrete bid levels. Such auctions are widely used in online internet settings and
our aim is to automate their configuration in order that they generate the maxi-
mum revenue for the auctioneer. Specifically, we address the problem of estimat-
ing the values of the parameters necessary to perform this optimal auction design
by observing the bidding in previous auctions. To this end, we derive a general
expression that relates the expected revenue of the auction when discrete bid lev-
els are implemented, but the number of participating bidders is unknown. We
then use this result to show that the characteristics of these optimal bid levels are
highly dependent on the expected number of bidders and on their valuation distri-
bution. Finally, we derive and demonstrate an online algorithm based on Bayesian
machine learning, that allows these unknown parameters to be estimated through
observations of the closing price of previous auctions. We show experimentally
that this algorithm converges rapidly toward the true parameter values and, in
comparison with an auction using the more commonly implemented fixed bid
increment, results in an increase in auction revenue.
1 Introduction
The popularity of online internet auctions has increased dramatically over recent years,
with total online auction sales currently exceeding $30 billion annually. This popularity
has prompted much research into agent mediated auctions and specifically the develop-
ment of autonomous software agents that are capable of fulfilling the role of auctioneer
or bidder on behalf of their owner. Now, much of the theoretical work on these agent
mediated auctions has focused on direct sealed bid protocols, such as the second-price
(Vickrey) auction. These protocols are attractive as they are economically efficient and
provide simple dominant bidding strategies for participating agents. However, despite
these properties, such sealed bid protocols are rarely used in practice [14]. The vast ma-
jority of current online and real world auctions implement variants of a single auction
protocol, specifically, the oral ascending price (English) auction with discrete bid levels
[8]. Under this protocol, the auctioneer announces the price of the next bid and waits
until a bidder indicates their willingness to pay this amount. Upon receiving such an
indication, the price moves on to another higher discrete bid price, again proposed by
the auctioneer. The auction continues until there are no bidders willing to pay the bid
price requested by the auctioneer. At this point, the object is allocated to the current
highest bidder and that bidder pays the last accepted discrete bid price.
