On incentive issues in practical auction design

Algorithmic mechanism design studies the allocation of resources to selfish agents, who might behave strategically to maximize their own utilities. This thesis studies these incentive issues arsing from four different settings, that are motivated by real- life applications. We model the settings and problems by appropriately extending or generalizing classical economic models. After that we systematically analyze the auction design problems by using methods from both economic theory and computer science. The first problem is the auction design problem for selling online rich media ad- vertisement. In this market, multiple advertisers compete for a set of slots that are arranged in a line, such as a banner on a website. Each buyer desires a particular num- ber of consecutive slots and has a private per-click valuation while each slot is associated with a quality factor. Our goal is to maximize the auctioneer’s expected revenue given buyers’ consecutive demand. This is motivated by modeling buyers who may require these to display a large size ad. Three major pricing mechanisms, the Bayesian pric- ing model, the maximum revenue market equilibrium model and an envy-free solution model are studied in this setting. The second setting is for fund-raising scenarios, where a revenue target is usually specified. We are interested in designing truthful auctions that maximize the probability to achieve this revenue target, rather than in maximizing the expected revenue. We study this topic from the perspective of Bayesian auction design in digital good auctions. We present an algorithm to find the optimal truthful auction for two buyers with independent valuations and show the problem is NP-hard when the number of buyers is arbitrary or the distributions are correlated. We also investigate simple auctions in this setting and provide approximately optimal solutions. Third, we study double auction market design where the trading broker wants to maximize its total revenue by buying low from the sellers and selling high to the buyers in a Bayesian setting. For single-parameter setting, we develop a maximum mechanism for the market maker to maximize its own revenue. For the more general case where each seller’s product may be different, we consider a number of various settings in terms of constraints on supplies and demands. For each of them, we develop a polynomial time computable truthful mechanism for the market maker to achieve a revenue at least a constant factor times the revenue of any other truthful mechanism. Finally, we study the inefficiency of mixed equilibria of all-pay auctions in three different environments – combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where m all-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound by proving some structural properties of mixed Nash equilibria. Next, we design an all-pay mechanism with a randomized allocation rule for the multi-unit auction, which admits a unique, approximately efficient, pure Nash equilibrium. Finally, we analyze single-item all-pay auctions motivated by their connection to crowdsourcing contests and show tight bounds on the PoA of social welfare, revenue and maximum bid