THESIS
2018
x, 104 pages : illustrations ; 30 cm
Abstract
How to maximize the revenue of a seller, who intends to sell a single indivisible item to a
number of buyers, is a central problem in microeconomics. The Bayesian version of this
problem was settled by Myerson. Although illustrating theoretical beauty, Myerson's auction
rarely appears in real-world applications, mainly because of three reasons: (1) it discriminates
different buyers with different value priors. This may incur some fairness issues, and is
not feasible in some markets; (2) it requires the buyers to report their private values, rather
than to make take-it-or-leave-it decisions. This may raise some privacy concerns for the
buyers; (3) it is an auction scheme rather than a pricing scheme, and therefore incorporates
far more communication between the seller and the buy...[
Read more ]
How to maximize the revenue of a seller, who intends to sell a single indivisible item to a
number of buyers, is a central problem in microeconomics. The Bayesian version of this
problem was settled by Myerson. Although illustrating theoretical beauty, Myerson's auction
rarely appears in real-world applications, mainly because of three reasons: (1) it discriminates
different buyers with different value priors. This may incur some fairness issues, and is
not feasible in some markets; (2) it requires the buyers to report their private values, rather
than to make take-it-or-leave-it decisions. This may raise some privacy concerns for the
buyers; (3) it is an auction scheme rather than a pricing scheme, and therefore incorporates
far more communication between the seller and the buyers.
In contrast, Anonymous Pricing totally avoids these complications, which makes it the
most dominant mechanism in practice. It is natural to inquire, compared with Myerson's
auction, that how much revenue can Anonymous Pricing generate. In this thesis, we prove
the tight approximation ratio for Anonymous Pricing: it guarantees at least 1/2.62-fraction of revenue as Myerson's auction; there is a matching lower-bound instance.
Next, we concentrate on another canonical revenue-maximization setting: a seller has n
indivisible items to sell to a unit-demand buyer; the buyer independently draws his values
for the items from n distributions. Conceivably, the seller may acquire more revenue via
specifying distinct prices for the items. However, finding the optimum among such Item
Pricing mechanisms is NP-hard. Instead, we would adopt the simplest mechanism Uniform
Pricing: carefully chose a price, and then set it on all items. In this unit-demand single-buyer
setting, we prove the tight approximation ratio between Uniform Pricing and the optimal
Item Pricing: in terms of revenue, the former admits a 2.62-approximation of the later; we
further validate the tightness of this ratio.
These results settle two open problems asked in a series of papers. Moreover, the first result automatically improves the approximation ratio of Second-Price Auction with Anonymous Reserve to 2.62 (with respect to Myerson's auction; in the single-item setting), which breaks the state-of-the-art upper bound of e ≈ 2.72. En route, we reveal an abundance of new structures for the aforementioned mechanisms, which may be instructive for conquering many other relevant problems.
Post a Comment