Information Technology Reference
In-Depth Information
Now, despite its apparent popularity, an auctioneer implementing an English auc-
tion with discrete bid levels is faced with two complementary challenges. Firstly, it
must determine the actual discrete bid levels to be used. The standard academic auction
literature provides little guidance here since it commonly assumes a continuous bid
interval, where bidders incrementally outbid one another by an infinitesimally small
amount. However, discrete bid levels do have an effect, and have been investigated by
Rothkopf and Harstad [13]. They showed that the revenue of the auction is dependent
on the number and distribution of discrete bid levels implemented and, in general, the
use of discrete bid levels reduces the revenue generated by the auction. Conversely, the
discrete bid levels also act to greatly reduce the number of bids that must be submitted
in order for the price to reach the closing price. This has the effect of increasing the
speed of the auction and, hence, reduces the time and communication costs of both the
auctioneer and bidders. By analysing the manner in which the discrete bid auction could
close and then calculating the expected revenue of the auctioneer in a number of limited
cases (which we detail in section 2), they were able to derive the optimal distribution of
bid levels that would maximise this revenue. In previous work, we extended this result
to the general case, and we can now determine the optimal bid levels for an auction in
which the environmental parameters are given [4]. Specifically, these parameters are the
number of bidders participating in the auction and the bidders' valuation distribution .
Thus, performing this optimal auction design introduces the second of the two chal-
lenges; that of determining, for the particular setting under consideration, the values of
these environmental parameters. While, in some settings these may be well known, in
most cases they will not. Thus, in this paper, we tackle the problem of determining the
optimal discrete bid levels when these values must be estimated through observations
of previous auctions. In so doing, we extend the state of the art in three ways:
1. We extend previous work by deriving an expression that describes the expected rev-
enue of a discrete bid auction when the number of bidders participating is unknown
but can be described by a probability distribution.
2. We use this expression to calculate the optimal bid levels that maximise the auc-
tioneers' revenue in this case. We demonstrate that the optimal discrete bid levels
produced by this method are dependent on the distribution of the number of partic-
ipating bidders and on the distribution that describes the bidders' valuations.
3. We show that this expression allows us to use machine learning, and specifically
Bayesian inference, in an online algorithm that generates sequentially better esti-
mates for the parameters that describe the two unknown distributions (i.e. the dis-
tribution of the number of bidders participating in any auction and the distribution
of the bidders' valuation) by observing only the closing price of previous auctions.
The results that we provide may be used in the design of online auctions or may be
used by automated trading agents that are adopting the role of an auctioneer within
a multi-agent system. In such settings these auction protocols are attractive as they
provide a relatively simple bidding strategy for the agents, yet, unlike second price
sealed bid auctions, do not require the bidders to reveal their full private information to
the auctioneer. In this setting, there is a need to fully automate the design of such auction
mechanisms, and the work presented here represents a key step in this direction.
