File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Mechanism design for auctions and pricing

TitleMechanism design for auctions and pricing
Authors
Advisors
Advisor(s):Ting, HF
Issue Date2014
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
Xiang, X. [項祥中]. (2014). Mechanism design for auctions and pricing. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5295526
AbstractRecent years have seen extensive studies on the pricing problem, as well as its many variances. They have found important applications in computational economics. Nowadays typical applications can be found in internet advertising, Google’s Auction for TV ads and many other resource allocation problems in electronic markets. In electronic markets, thousands of trading activities are processed in the internet or done automatically by computer programs. It is highly required that the trading mechanisms are efficient enough. In the thesis, we will study various pricing problems from different perspectives. The first problem we study is the design of auction mechanism when bidders are unit-demand. It can be applied in internet advertising. Thousand of advertisers bid for space in webpages to show their advertisements. We model the new problem and apply the General Second Price (GSP) mechanism to the problem. GSP is an efficient mechanism with linear time complexity. Moreover, we show that GSP has an envy-free equilibrium which can maximize the profit of advertisers. Auction mechanisms where bidders can bid for multiple items are also studied. A famous example of such auction is the Dutch flower auction. Such multi-unit auctions are widely studied these years. But budget constraints are not considered in many previous works. We study the scenario that each bidder has a budget on the money paid to the auctioneer and the valuation functions of bidders are non-linear. For the model, we design an adaptive clinching auction mechanism. The mechanism is proved to be incentive-compatible, which encourages bidders to reveal their true values, and Pareto-optimal, which ensures that no bidder can improve her utility without decreasing those of others. In some auctions, the items on sale are not available at the same time. For example, TV stations sell time-slots for advertisements on a daily basis. The advertisers are arriving and departing online and bidding for a set of timeslots. For the auction, we design a competitive mechanism which is truthful, i.e., all bidders have the incentive to submit their true private values to the auctioneer. Another important property the mechanism achieves is promptness, which makes sure that any advertiser that wins some time-slots could learn her payment immediately after winning these time-slots. In some pricing problems, upon the arrival of a new buyer, the seller needs to decide immediately whether he will sell his goods or not and what is the price. When buyers are unit-demand and each seller has b items on sale, the online pricing problem can be modelled by online weighted b-matching problem. For the problem, we show a randomized algorithm which achieves near-optimal competitive ratio. When buyers are not unit-demand, things are much more complicated. We consider a general model in which each buyer wants to buy a bundle of items and has a non-increasing valuation function for those items. We design a randomized algorithm which achieves low competitive ratio and derive a non-trivial lower bound on the competitive ratios.
DegreeDoctor of Philosophy
SubjectAuctions - Computer simulation
Pricing - Computer simulation
Dept/ProgramComputer Science
Persistent Identifierhttp://hdl.handle.net/10722/202375

 

DC FieldValueLanguage
dc.contributor.advisorTing, HF-
dc.contributor.authorXiang, Xiangzhong-
dc.contributor.author項祥中-
dc.date.accessioned2014-09-18T02:28:15Z-
dc.date.available2014-09-18T02:28:15Z-
dc.date.issued2014-
dc.identifier.citationXiang, X. [項祥中]. (2014). Mechanism design for auctions and pricing. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5295526-
dc.identifier.urihttp://hdl.handle.net/10722/202375-
dc.description.abstractRecent years have seen extensive studies on the pricing problem, as well as its many variances. They have found important applications in computational economics. Nowadays typical applications can be found in internet advertising, Google’s Auction for TV ads and many other resource allocation problems in electronic markets. In electronic markets, thousands of trading activities are processed in the internet or done automatically by computer programs. It is highly required that the trading mechanisms are efficient enough. In the thesis, we will study various pricing problems from different perspectives. The first problem we study is the design of auction mechanism when bidders are unit-demand. It can be applied in internet advertising. Thousand of advertisers bid for space in webpages to show their advertisements. We model the new problem and apply the General Second Price (GSP) mechanism to the problem. GSP is an efficient mechanism with linear time complexity. Moreover, we show that GSP has an envy-free equilibrium which can maximize the profit of advertisers. Auction mechanisms where bidders can bid for multiple items are also studied. A famous example of such auction is the Dutch flower auction. Such multi-unit auctions are widely studied these years. But budget constraints are not considered in many previous works. We study the scenario that each bidder has a budget on the money paid to the auctioneer and the valuation functions of bidders are non-linear. For the model, we design an adaptive clinching auction mechanism. The mechanism is proved to be incentive-compatible, which encourages bidders to reveal their true values, and Pareto-optimal, which ensures that no bidder can improve her utility without decreasing those of others. In some auctions, the items on sale are not available at the same time. For example, TV stations sell time-slots for advertisements on a daily basis. The advertisers are arriving and departing online and bidding for a set of timeslots. For the auction, we design a competitive mechanism which is truthful, i.e., all bidders have the incentive to submit their true private values to the auctioneer. Another important property the mechanism achieves is promptness, which makes sure that any advertiser that wins some time-slots could learn her payment immediately after winning these time-slots. In some pricing problems, upon the arrival of a new buyer, the seller needs to decide immediately whether he will sell his goods or not and what is the price. When buyers are unit-demand and each seller has b items on sale, the online pricing problem can be modelled by online weighted b-matching problem. For the problem, we show a randomized algorithm which achieves near-optimal competitive ratio. When buyers are not unit-demand, things are much more complicated. We consider a general model in which each buyer wants to buy a bundle of items and has a non-increasing valuation function for those items. We design a randomized algorithm which achieves low competitive ratio and derive a non-trivial lower bound on the competitive ratios.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subject.lcshAuctions - Computer simulation-
dc.subject.lcshPricing - Computer simulation-
dc.titleMechanism design for auctions and pricing-
dc.typePG_Thesis-
dc.identifier.hkulb5295526-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineComputer Science-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b5295526-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats