Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(lcgft). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Hong Kong University of Science and Technology

1. Jin, Yaonan IELM. Tight approximation ratio of anonymous pricing.

Degree: 2018, Hong Kong University of Science and Technology

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.

Subjects/Keywords: Pricing; Mathematical models; Restraint of trade; Prices; Approximation algorithms; Academic theses; lcgft

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Jin, Y. I. (2018). Tight approximation ratio of anonymous pricing. (Thesis). Hong Kong University of Science and Technology. Retrieved from https://doi.org/10.14711/thesis-991012671266103412 ; http://repository.ust.hk/ir/bitstream/1783.1-97769/1/th_redirect.html

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16th Edition):

Jin, Yaonan IELM. “Tight approximation ratio of anonymous pricing.” 2018. Thesis, Hong Kong University of Science and Technology. Accessed November 21, 2019. https://doi.org/10.14711/thesis-991012671266103412 ; http://repository.ust.hk/ir/bitstream/1783.1-97769/1/th_redirect.html.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7th Edition):

Jin, Yaonan IELM. “Tight approximation ratio of anonymous pricing.” 2018. Web. 21 Nov 2019.

Vancouver:

Jin YI. Tight approximation ratio of anonymous pricing. [Internet] [Thesis]. Hong Kong University of Science and Technology; 2018. [cited 2019 Nov 21]. Available from: https://doi.org/10.14711/thesis-991012671266103412 ; http://repository.ust.hk/ir/bitstream/1783.1-97769/1/th_redirect.html.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Jin YI. Tight approximation ratio of anonymous pricing. [Thesis]. Hong Kong University of Science and Technology; 2018. Available from: https://doi.org/10.14711/thesis-991012671266103412 ; http://repository.ust.hk/ir/bitstream/1783.1-97769/1/th_redirect.html

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.