File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: Mechanism design for auctions and pricing
Title  Mechanism design for auctions and pricing 

Authors  
Advisors  Advisor(s):Ting, HF 
Issue Date  2014 
Publisher  The 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 
Abstract  Recent 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 unitdemand. 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 envyfree 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 multiunit 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 nonlinear. For the model, we design an adaptive clinching auction mechanism. The mechanism is proved to be incentivecompatible, which encourages bidders to reveal their true values, and Paretooptimal, 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 timeslots 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 timeslots could learn her payment immediately after winning these timeslots.
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 unitdemand and each seller has b items on sale, the online pricing problem can be modelled by online weighted bmatching problem. For the problem, we show a randomized algorithm which achieves nearoptimal competitive ratio. When buyers are not unitdemand, things are much more complicated. We consider a general model in which each buyer wants to buy a bundle of items and has a nonincreasing valuation function for those items. We design a randomized algorithm which achieves low competitive ratio and derive a nontrivial lower bound on the competitive ratios. 
Degree  Doctor of Philosophy 
Subject  Auctions  Computer simulation Pricing  Computer simulation 
Dept/Program  Computer Science 
Persistent Identifier  http://hdl.handle.net/10722/202375 
DC Field  Value  Language 

dc.contributor.advisor  Ting, HF   
dc.contributor.author  Xiang, Xiangzhong   
dc.contributor.author  項祥中   
dc.date.accessioned  20140918T02:28:15Z   
dc.date.available  20140918T02:28:15Z   
dc.date.issued  2014   
dc.identifier.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   
dc.identifier.uri  http://hdl.handle.net/10722/202375   
dc.description.abstract  Recent 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 unitdemand. 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 envyfree 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 multiunit 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 nonlinear. For the model, we design an adaptive clinching auction mechanism. The mechanism is proved to be incentivecompatible, which encourages bidders to reveal their true values, and Paretooptimal, 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 timeslots 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 timeslots could learn her payment immediately after winning these timeslots. 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 unitdemand and each seller has b items on sale, the online pricing problem can be modelled by online weighted bmatching problem. For the problem, we show a randomized algorithm which achieves nearoptimal competitive ratio. When buyers are not unitdemand, things are much more complicated. We consider a general model in which each buyer wants to buy a bundle of items and has a nonincreasing valuation function for those items. We design a randomized algorithm which achieves low competitive ratio and derive a nontrivial lower bound on the competitive ratios.   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.rights  Creative Commons: Attribution 3.0 Hong Kong License   
dc.subject.lcsh  Auctions  Computer simulation   
dc.subject.lcsh  Pricing  Computer simulation   
dc.title  Mechanism design for auctions and pricing   
dc.type  PG_Thesis   
dc.identifier.hkul  b5295526   
dc.description.thesisname  Doctor of Philosophy   
dc.description.thesislevel  Doctoral   
dc.description.thesisdiscipline  Computer Science   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.5353/th_b5295526   