Mechanism Design

How to design a mechanism that maximizes 1)social welfare 2)the seller's revenue,is a central question in algorithmic mechanism design area.The two objectives are quite intuitive:the former one maximizes the satisfaction of the whole society given the allocation,while the latter one maximizes the amount of money an auctioneer can extract from the auction.Different from the traditional optimization objective,in an auction scenario each agent has a value to the item which is private information.A simple optimization scheme may lead to strategic behavior from the agents.The traditional VCG mechanism [1–3] gives the optimal auction that maximizes social welfare,while the remarkable Myerson's auction [4] achieves revenue-optimal auction for single-item setting.Both mechanisms are truthful auctions that the agents do not have incentive to lie.However,the two Nobel Prize-winning-work have lots of limitations,both in theory and practice.This thesis aims at studying some basic challenges that lie in practical auction scenarios,with the goal of establishing mechanism design theory from practice.The first challenge in a practical auction scenario is that each agent may have a budget constrain,which means that this agent can not pay more than a certain amount.If the objective is to maximize social welfare,and we apply VCG mechanism here,there is a possibility that the agent may not afford to pay.Based on this,Dobzinski and Leme propose the notion of liquid welfare [5],which means that each agent cannot contribute more than the minimum of her value and budget.In Chapter 3 we improve and generalize existing results.We design random sampling based mechanisms and prove that this mechanism achieves constant approximation ratio for single item setting.For the more challenging multi-item setting,we also achieve a constant approximation ratio under the Large Market Assumption.The second challenge in a practical auction scenario is that the allocation rule of Myerson's auction is “counter-intuitive”.Note that in a Myerson's auction,it is possible that the agent with the highest bid is not allocated with the item,which makes it hard to explain to the non-experts that this auction is indeed truthful,thus hard to apply in practice.On the other hand,Sequential Posted Pricing,Anonymous Reserve and Anonymous Pricing are robust to this issue,with lots of applications in practice.Understanding the revenue gaps among these mechanisms are also central questions in the Economic and Computation area.In Chapter 4 we provide several tight bounds among these mechanisms.Particularly,the tight bound between Myerson's auction and anonymous pricing answers the central question proposed by Hartline and Roughgarden [6] that remained to be open for a decade.The third challenge in a practical auction scenario is that strategic behavior can actually make the Myerson's auction run with data different from each agent's actual value.Note that Myerson's auction relies on prior knowledge of the agents,which is usually learned via interaction with the actual auction environment.A central game-theoretical issue raises: if the agents know that their bid information will be used in designing mechanisms,the intellectual agents will strategically respond to achieve higher utility in a Myerson's auction.In Chapter 5,we study this scenario,model it as a Private Data Manipulation model.We analyse under this model,for different bidding strategy space,the equilibrium of revenue-optimal auction.As an application,we show that in sponsored search auction scenario,under Private Data Manipulation model,revenue-optimal auction is equivalent to Generalized First Price auction.