Approximately Optimal Mechanisms In Auction Design Search Theory And Matching Markets PDF Download

In this dissertation, we design and analyze auctions that are more practical than those in the traditional auction theory in several settings. The first setting is the search advertising market, in which the multi-keyword sponsored search mechanism is the dominant platform. In this setting, a search engine sells impressions generated from various search terms to advertisers. The main challenge is the sheer diversity of the items for sale -- the number of distinct items that an advertiser wants is so large that he cannot possibly communicate all of them to the search engine. To alleviate this communication problem, the search engine introduces a bidding language called broad match. It allows an advertiser to submit a single bid for multiple items at once. Popular models such as the GSP auction do not capture this aspect of sponsored search. We propose a model, named the broad match mechanism, for the sponsored search platform with broad match keywords. The analysis of the broad match mechanism produces many insights into the performance of the sponsored search platform. First, we identify two properties of the broad match mechanism, namely expressiveness and homogeneity, that characterize the performance of the mechanism. Second, we show that, unlike the GSP auction, the broad match mechanism does not necessarily have a pure equilibrium. Third, we analyze two variants of the broad match mechanism, the pay-per-impression variant and the pay-per-click variant. Under a common model of advertiser valuation, we show that the pay-per-click variant is more economically efficient than the pay-per-impression variant. This result justifies the prevalent use of the pay-per-click scheme in search advertising. In addition, the broad match mechanism can be viewed as an auction of which the bidding language is crucial to its performance. In the second part, we design and analyze approximately revenue-maximizing auctions in single-parameter settings. Bidders have publicly observable attributes and we assume that the valuations of bidders with the same attribute are independent draws from a common distribution. Previous works in revenue-maximizing auctions assume that the auctioneer knows the distributions from which the bidder valuations are drawn \cite{M81}. In this dissertation, we assume that the distributions are a priori unknown to the auctioneer. We show that a simple auction which does not require any knowledge of the distributions can obtain revenue comparable to what could be obtained if the auctioneer had the distributional knowledge in advance. Our most general auction has expected revenue at least a constant fraction of that of the optimal distributional-dependent auction in two settings. The first setting concerns arbitrary downward-closed single-parameter environments and valuation distributions that satisfy a standard hazard rate condition, called monotone hazard rate. In this setting, the expected revenue of our auction is improved to a constant fraction of the expected optimal welfare. In the second setting, we allow a more general class of valuation distributions, called regular distributions, but require a more restrictive environment called the matroid environment. In our results, we assume that no bidder has a unique attribute value, which is obviously necessary with unknown and attribute-dependent valuation distributions. Our auction sets a reserve price for a bidder using the valuation of another bidder who has the same attribute. Conceptually, our analysis shows that even a single sample from a distribution -- another bidder's valuation -- is sufficient information to obtain near-optimal expected revenue, even in quite general settings. In the third part, we design and analyze auctions that approximately maximize residual surplus in single-parameter settings. Residual surplus is defined to be the surplus less the sum of the bidders' payments. The guarantee of our auction is of the same type as the auctions in the second part, i.e., its expected residual surplus is a fraction of that of the optimal distributional-dependent auction. Instead of the no-unique-attribute assumption made in the second setting, in this setting we assume that the distributions of bidder valuations can be ordered, that is, the distribution of the first bidder stochastically dominates that of the second bidder and the distribution of the second bidder stochastically dominates that of the third and so on. In every downward-closed stochastic-dominance environment where the distributions of bidder valuations satisfy the monotone hazard rate condition, our auction produces residual surplus that is a $\Omega(\tfrac{1}{\log n})$ fraction of the optimal residual surplus, without taking any bid (although it makes use of the ordering), where $n$ is the number of bidders.