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.