Designing And Learning Optimal Finite Support Auctions
Authors: Edith Elkind
Abstract:
A classical paper of Myerson [18] shows how to construct an optimal (revenue-maximizing)
auction in a model where bidders. values are drawn from known continuous distributions. In this
paper
we show how to adapt this approach to finite support distributions that may be partially unknown.
We
demonstrate that a Myerson-style auction can be constructed in time polynomial in the number of
bidders
and the size of the support sets. Next, we consider the scenario where the mechanism designer knows
the
support sets, but not the probability of each value. In this situation, we show that the optimal
auction may
be learned in polynomial time using a weak oracle that, given two candidate auctions, returns one
with a
higher expected revenue. To study this problem, we introduce a new class of truthful mechanisms
which
we call order-based auctions. We show that the optimal mechanism is an order-based auction and use
the
internal structure of this class to prove the correctness of our learning algorithm as well as to
bound its
running time.