Models for Budget Constrained Auctions: An Application to Sponsored Search & Other Auctions

dc.contributor.advisorRaghavan, Subramanianen_US
dc.contributor.authorPani, Abhisheken_US
dc.contributor.departmentBusiness and Management: Decision & Information Technologiesen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2011-02-19T07:02:38Z
dc.date.available2011-02-19T07:02:38Z
dc.date.issued2010en_US
dc.description.abstractThe last decade has seen the emergence of auction mechanisms for pricing and allocating goods on the Internet. A successful application area for auctions has been sponsored search. Search firms like Google, Bing and Yahoo have shown stellar revenue growths due to their ability to run large number of auctions in a computationally efficient manner. The online advertisement market in the U.S. is estimated to be around $41 billion in 2010 and expected to grow to $50 billion by 2011 (http://www.marketingcharts.com/interactive/us-online-advertising-market-to-reach-50b-in-2011-3128/). The paid search component is estimated to account for nearly 50% of online advertising spend. This dissertation considers two problems in the sponsored search auction domain. In sponsored search, the search operator solves a multi-unit allocation and pricing problem with the specified bidder values and budgets. The advertisers, on the other hand, regularly solve a bid determination problem for the different keywords, given their budget and other business constraints. We develop a model for the auctioneer that allows the bidders to place differing bids for different advertisement slots for any keyword combination. Despite the increased complexity, our model is solved in polynomial time. Next, we develop a column-generation procedure for large advertisers to bid optimally in the sponsored search auctions. Our focus is on solving large-scale versions of the problem. Multi-unit auctions have also found a number of applications in other areas that include supply chain coordination, wireless spectrum allocation and transportation. Current research in the multi-unit auction domain ignores the budget constraint faced by participants. We address the computational issues faced by the auctioneer when dealing with budget constraints in a multi-unit auction. We propose an optimization model and solution approach to ensure that the allocation and prices are in the core. We develop an algorithm to determine an allocation and Walrasian equilibrium prices (when they exist) under additive bidder valuations where the auctioneer's goal is social welfare maximization and extend the approach to address general package auctions. We, also, demonstrate the applicability of the Benders decomposition technique to model and solve the revenue maximization problem from an auctioneer's standpoint.en_US
dc.identifier.urihttp://hdl.handle.net/1903/11198
dc.subject.pqcontrolledOperations Researchen_US
dc.subject.pquncontrolledBranch and priceen_US
dc.subject.pquncontrolledBudget Constraint Auctionen_US
dc.subject.pquncontrolledColumn Generationen_US
dc.subject.pquncontrolledConstraint Generationen_US
dc.subject.pquncontrolledCore Allocationen_US
dc.subject.pquncontrolledSponsored Searchen_US
dc.titleModels for Budget Constrained Auctions: An Application to Sponsored Search & Other Auctionsen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Pani_umd_0117E_11761.pdf
Size:
502.87 KB
Format:
Adobe Portable Document Format