Advances in information technology have created radically new business models, most notably the integration of advertising with keyword-based targeting, or "keyword advertising." Keyword advertising has two main variations: advertising based on keywords employed by users in search engines, often known as "sponsored links," and advertising based on keywords embedded in the content users view, often known as "contextual advertising." Keyword advertising providers such as Google and Yahoo! use auctions to allocate advertising slots. This dissertation examines the design of keyword auctions. It consists of three essays. The first essay "Ex-Ante Information and the Design of Keyword Auctions" focuses on how to incorporate available information into auction design. In our keyword auction model, advertisers bid their willingness-to-pay per click on their advertisements, and the advertising provider can weigh advertisers' bids differently and require different minimum bids based on advertisers' click-generating potential. We study the impact and design of such weighting schemes and minimum-bids policies. We find that weighting scheme determines how advertisers with different click-generating potential match in equilibrium. Minimum bids exclude low-valuation advertisers and at the same time may distort the equilibrium matching. The efficient design of keyword auctions requires weighting advertisers' bids by their expected click-through-rates, and requires the same minimum weighted bids. The revenue-maximizing weighting scheme may or may not favor advertisers with low click-generating potential. The revenue-maximizing minimum-bid policy differs from those prescribed in the standard auction design literature. Keyword auctions that employ the revenue-maximizing weighting scheme and differentiated minimum bid policy can generate higher revenue than standard fixed-payment auctions. The dynamics of bidders' performance is examined in the second essay, "Keyword Auctions, Unit-price Contracts, and the Role of Commitment." We extend earlier static models by allowing bidders with lower performance levels to improve their performance at a certain cost. We examine the impact of the weighting scheme on overall bidder performance, the auction efficiency, and the auctioneer's revenue, and derive the revenue-maximizing and efficient policy accordingly. Moreover, the possible upgrade in bidders' performance levels gives the auctioneer an incentive to modify the auction rules over time, as is confirmed by the practice of Yahoo! And Google. We thus compare the auctioneer's revenue-maximizing policies when she is fully committed to the auction rule and when not, and show that she should give less preferential treatment to low-performance advertisers when she is fully committed. In the third essay, "How to Slice the Pie? Optimal Share Structure Design in Keyword Auctions," we study the design of share structures in keyword auctions. Auctions for keyword advertising resources can be viewed as share auctions in which the highest bidder gets the largest share, the second highest bidder gets the second largest share, and so on. A share structure problem arises in such a setting regarding how much resources to set aside for the highest bidder, for the second highest bidder, etc. We address this problem under a general specification and derive implications on how the optimal share structure should change with bidders' price elasticity of demand for exposure, their valuation distribution, total resources, and minimum bids. / text

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 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. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Not available / text

No description available.

Basically, my dissertation focuses on License Auctions. Four chapters of my dissertation are theoretical analysis of license auctions. Broadly speaking, I analyze the effects of different auction rules on revenue, efficiency and social welfare. The first chapter studies the flaw in the design of the 2000 Turkish GSM auction. In this auction, the Turkish government wants to raise as much revenue as possible and to increase competition in the cell-phone market by selling two licenses to new firms via a sequential auction, but it ends up with only one license sold. I identify this auction design failure. And I also show that if the auction were designed as a “simultaneous auction”, the government would sell two licenses and receive more revenue. In the second chapter, I show that if the cost asymmetry between the bidding firms is large enough, then having fewer firms in the market will surprisingly result in higher social welfare. This result is contrast to the common or general case in which “social welfare” will be higher if there are more firms competing in the market. In the third chapter, I characterize the optimal bidding strategies of local and global bidders for two heterogeneous licenses in a multi-unit simultaneous ascending auction with synergies. I determine the optimal bidding strategies in the presence of an exposure problem and show that global bidders may accept a loss even when they win all licenses and moreover, if a “bid-withdrawal” rule is introduced to the auction, the exposure problem disappears, and the simulation results show that revenue will be higher. In the last chapter, I study the Canadian AWS auction in which 40 percent spectrum are set aside for new firms. I characterize the effect of spectrum set-aside auctions on seller's revenue, consumer surplus and social welfare. I show that a spectrum set aside may not only encourage new entry and increase competition in the downstream market, but also under some circumstance, decreases the seller's revenue and consumer surplus. But a spectrum set aside results in inefficient allocation, and this inefficient entry further reduces social welfare.

Basically, my dissertation focuses on License Auctions. Four chapters of my dissertation are theoretical analysis of license auctions. Broadly speaking, I analyze the effects of different auction rules on revenue, efficiency and social welfare. The first chapter studies the flaw in the design of the 2000 Turkish GSM auction. In this auction, the Turkish government wants to raise as much revenue as possible and to increase competition in the cell-phone market by selling two licenses to new firms via a sequential auction, but it ends up with only one license sold. I identify this auction design failure. And I also show that if the auction were designed as a “simultaneous auction”, the government would sell two licenses and receive more revenue. In the second chapter, I show that if the cost asymmetry between the bidding firms is large enough, then having fewer firms in the market will surprisingly result in higher social welfare. This result is contrast to the common or general case in which “social welfare” will be higher if there are more firms competing in the market. In the third chapter, I characterize the optimal bidding strategies of local and global bidders for two heterogeneous licenses in a multi-unit simultaneous ascending auction with synergies. I determine the optimal bidding strategies in the presence of an exposure problem and show that global bidders may accept a loss even when they win all licenses and moreover, if a “bid-withdrawal” rule is introduced to the auction, the exposure problem disappears, and the simulation results show that revenue will be higher. In the last chapter, I study the Canadian AWS auction in which 40 percent spectrum are set aside for new firms. I characterize the effect of spectrum set-aside auctions on seller's revenue, consumer surplus and social welfare. I show that a spectrum set aside may not only encourage new entry and increase competition in the downstream market, but also under some circumstance, decreases the seller's revenue and consumer surplus. But a spectrum set aside results in inefficient allocation, and this inefficient entry further reduces social welfare.

The goal of this dissertation is to understand the market-based mechanisms that enable shippers to allocate lanes in an efficient way for truckload (TL) transportation procurement despite the self-interest of carriers. To understand the market-based mechanisms, we focus on proposing some novel models and mechanisms to enhance the use of combinatorial auction for TL transportation procurement. In this dissertation, our approach to gaining the understanding consists of three parts: 1. We develop a carrier optimal bid generation model for carriers (bidders) to discover the best sets of lanes to bid for at a given round. The optimal bid generation model simultaneously generates alternative tours and selects the most profitable package bid for the carrier under a myopic strategy, which has never been considered before. The simultaneous tour generation and selection significantly lessen the computational complexities of a carrier's optimization problem since it is unnecessary for the carrier to calculate the values for all possible packages. 2. We present an iterative combinatorial auction design that integrates the optimization problems for both the shipper and the bidders where the approximate dual prices derived from the result of a winner determination solution are used by the bidders in identifying profitable lanes. The auctions also allow the bidders to submit exclusive-OR (XOR) bids and are able to deal with some common business considerations. The extension of the concept of active bids enables this mechanism to effectively mitigate the exposure problem, the threshold problem, and the free-riding problem. Furthermore, both the shippers and the carriers are better off compared to multi-round auctions that do not integrate the shippers' and carriers' optimizations. 3. We extend a deterministic winner determination model to a two-stage stochastic winner determination model for TL transportation procurement under shipment volume uncertainty. We demonstrate that the value of the stochastic solution is always at least as good as one obtained by a deterministic model based on using expected shipment volumes. The sWDP model is to the best of our knowledge the first winner determination formulation of any kind that explicitly incorporates demand uncertainty.

By the emergence of electronic commerce and low transaction costs on the Internet, an interest in the design of new auction mechanisms has been arisen. Recently many researchers in computer science, economics, business, and game theory have presented many valuable studies on the subject of online auctions, and auctions theory. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging ones. Combinatorial auctions, that is, auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auction mechanisms in multi-item multi-unit situations where the agents&rsquo / valuations of the items are not additive. However, determining the winners to maximize the revenue is NP-complete. In this study, we first analyze the existing approaches for combinatorial auction problem. Based on this analysis, we then choose three different approaches, which are search approach, descending simultaneous auctions approach, and IP (Integer Programming) formulation approach to build our models. The performances of the models are compared using computer simulations, where we model bandwidth allocation system. Finally a combinatorial auction tool is built which can be used for online auctions and e-procurement systems.

Reverse auctions for ecological goods and services are an alternative to current agri-environmental government programs to provide incentives for farmers. This thesis reports on a testbed of laboratory auction experiments to assess efficiency and cost effectiveness of different design treatments. These were developed using estimated costs of wetland restoration in southern Manitoba. The testbed included a comparison of payment type (discriminatory versus uniform payments), and ranking rule for both budget based and target based auctions over repeated auction rounds and reserve prices for the target based auctions. It was found that 1) uniform payments outperformed discriminatory payments under a budget constraint, 2) discriminatory payments were superior to uniform payments under a target constraint, 3) where there is no budget constraint a reserve price can greatly increase efficiency and cost effectiveness. These findings highlight the complexity of auction design and may be used as an aid to guide policy decisions and agri-environmental program design. / Agricultural and Resource Economics

Thesis (doctoral) - Universität, Karlsruhe, 2005. / Includes bibliographical references (p. [171]-178).