SIMPLE AND APPROXIMATELY OPTIMAL MECHANISMS DESIGN ADissertation PresentedtotheFacultyoftheGraduateSchool ofCornellUniversity inPartialFulfillmentoftheRequirementsfortheDegreeof DoctorofPhilosophy by HuFu August2013 (cid:13)c 2013HuFu ALLRIGHTSRESERVED SIMPLEANDAPPROXIMATELYOPTIMALMECHANISMSDESIGN HuFu,Ph.D. CornellUniversity2013 Mechanism design studies optimization problems with inputs from selfishly behaving agents. To a class of relatively simple questions, classical auction theory gives optimal solution which are often too complicated for practical use. This dissertation presents techniques and results on the design and analysis of simple and practical auctions that have provably approximately optimal performances. For single-parameter revenue op- timization, we present the k-lookahead auction, which works for coorelated valuation distributions, and we discuss its consequences, which encompass a family of reserve- price-basedauctionswithapproximatelyoptimalrevenue. Formoregeneralsettings,we present the marginal revenue mechanisms as a framework for designing simple mech- anisms in very general settings. Both frameworks are motivated with clear economic intuitions. For social welfare maximization in combinatorial auctions, we present an equilib- rium analysis for simultaneous item auctions. In particular, we show that when val- uations exhibit no complements, the welfare loss in these auctions at Bayesian Nash equilibriaisboundedbysmallconstants. BIOGRAPHICALSKETCH Hu Fu was born in Qingdao, China in 1984. Piano practice and performance occupied much of his childhood and has ever since been a nontrivial diversion. Hu won a gold medal in the Chinese National Biology Olympiad in 2002, and went on to the Depart- ment of Automation at Tsinghua University for his college education. There he won the prestigious Jiang Nanxiang Scholarship in 2004, and obtained his bachelor degree in 2007. Since then he has been pursuing his graduate study in computer science at CornellUniversity. iii Thisdissertationisdedicatedtomyparents,andtothememoryofmygrandfather, HuizanFu. iv ACKNOWLEDGMENTS It is most certain that the luckiest thing that happened to me in graduate school was to have found Bobby Kleinberg as my advisor. Not only did Bobby allure me to the wonderland of theoretical computer science, set me a model of academic brilliancy brimmingwithdazzlingideas,andprovidecrucialhelpwithallmykeycareerdecisions, butalso,inthetruespiritofacademicgenealogy,heinculcatedinmeatasteforresearch and mathematics in general, an influence whose effect I expect to perceive for years to come. ItwasadditionalblisstohaveBobbyasagenuinefriend,toshareandplaymusic andtodiscussallintellectualmatterswithhim. Among the colleagues I have collaborated with, Jason Hartline and Shahar Dobzin- skihavevirtuallycometoassumetheroleofsecondadvisors. Iowetothemtheinspira- tionofsomeofmybestresearchoutputs,andhaverepeatedlybenefitedfromtheirwise advice. I was born into a family whose intellectual tradition was disrupted for a generation by social upheavals. Fostering my intellectual growth therefore exacts additional sacri- fice and patience from my parents, for which I am forever grateful. My grandparents, especially my late grandfather, sowed in me the scholarly seed. Under their and my parents’ care, it budded through hardships not easily conceived in this country, and is now finally bearing some flowers. To think of the joy and pride this brings to them emboldensmebeforeallobstaclesinlife. ThewayIthinkaboutmathwasgreatlychangedandripenedbycoursesItookfrom Eugene Dynkin and Ken Brown. My enjoyment in graduate school was enriched by piano lessons taken from Xak Bjerken, and my intellectual horizon was tremendously broadened by my three years of residence in the Telluride House. Friendships I formed in the Computer Science Department and at the Telluride House, such as those with Tha`nhNguyen,TuanCao,HuijiaLin,ChenhaoTan,HussamAbu-Libdeh,JudahBellin, v Kate Scheibel, Liz Solten, Sarah Asman, Jacob Krell and Srinath Reddy, are cherished inmemoryandwillforsurebealifelongtreasure. vi TABLEOFCONTENTS BiographicalSketch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v TableofContents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction 1 1.1 (Approximately)OptimalAuctionsBeyondMyerson. . . . . . . . . . . 2 1.2 TowardsMoreRealisticMechanisms . . . . . . . . . . . . . . . . . . . 4 1.3 BibliographicNotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 BackgroundMaterial 6 3 LookaheadAuctionsandTheirConsequences 11 3.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Thek-lookaheadAuction . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.1 Analysisofthek-LookaheadAuction . . . . . . . . . . . . . . 13 3.3 Reserve-price-basedAuctionsforIndependentDistributions . . . . . . 17 3.3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3.2 SingleItemSettings . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.3 MatroidSettings . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 MarginalRevenueMechanisms 29 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.2 Warmup: Single-dimensionalLinearPreference . . . . . . . . . . . . . 38 4.3 Multi-dimensionalandNonlinearPreferences . . . . . . . . . . . . . . 44 4.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.4.1 MonotoneExAnteConstrainedLotteryPricings . . . . . . . . 54 4.4.2 GeneralExAnteConstrainedLotteryPricings . . . . . . . . . 56 4.5 Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.5.1 Agent-basedApproximation . . . . . . . . . . . . . . . . . . . 57 4.5.2 Feasibility-basedApproximation . . . . . . . . . . . . . . . . . 62 4.6 ExtendingTechniquesFromSingle-DimensionalLinearUtilitySettings 66 5 SimultaenousItemAuctions 68 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.2.1 CombinatorialAuctionsandEquilibria . . . . . . . . . . . . . 75 5.2.2 SubadditiveValuations . . . . . . . . . . . . . . . . . . . . . . 78 5.2.3 Overbidding . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.3 BiddingUnderUncertainPrices . . . . . . . . . . . . . . . . . . . . . 80 5.4 BPoAofFirstPriceAuctions . . . . . . . . . . . . . . . . . . . . . . . 84 5.5 BPoAofSecondPriceAuctions . . . . . . . . . . . . . . . . . . . . . 87 vii A ProofsfromChapter4 90 A.1 Single-dimensionalProofs . . . . . . . . . . . . . . . . . . . . . . . . 90 A.2 ProofsfromSection4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.3 Linearity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 A.4 ProofsfromSection4.4.2 . . . . . . . . . . . . . . . . . . . . . . . . . 95 A.5 Proofsforunit-demandapproximation . . . . . . . . . . . . . . . . . . 98 viii CHAPTER1 INTRODUCTION Mechanism design studies optimization systems that take into account participants’ private information and selfish behaviors. The past ten years have seen a fruitful mar- riage of this subfield of microeconomics with computer science, accelerated by the ad- vent of the Internet and the ensuing business on it, such as display ad auctions run by search engine companies and large scale, dynamic auctions run by websites like Price- line or eBay. Algorithmic ideas and tools have been brought to bear on decades-old problems of economic theory, yielding new economic insights in addition to potential impactsonindustries. This thesis focuses on two aspects of this development. First, economic characteri- zationsofoptimalmechanismsbeyondclassicscenariostendtobetoocomplexforprac- ticaluse. Athemeofthechapterstofollowtothat,whentheviewpointofapproximation is adopted, much more structure and insights can be revealed and applied. Second, and relatedly, the use of mechanisms in practice often favors simplicity over theoretical op- timality, when the two design goals come into conflict. Simplicity here may refer to systems having succinct specifications, requiring less self-deliberation and private in- formation disclosure by market participants, tolerating the lack of certain information onthemechanismimplementer’spart,andsoon. Thisthesispresentsresearchprogress showing, on one hand, that the structure gained from adopting approximations often guides the design of simple mechanisms, and on the other hand, that mechanisms used in practice can often be analyzed and evaluated as approximations to optimal bench- marks. Background. A mechanism involves the participation of strategic agents with private information. The agents’ information, summarized as types, is unknown to us, while a decision on a social outcome needs to be made from interactions with them. In an 1