Auction Mechanism Design Powered By Social Networks

Mechanism design is a representative interface integrating economics and artificial intelligence.It utilizes game theoretic tools to model interactions between agents,and design the interaction environment from a systematic view,guiding selfish agents to realize the desiderata of the mechanism designer.Resource allocation plays an important role in economics,and is also a key research content in computer science.As a classic application in mechanism design,auction is the most effective tool for recourse allocation,whose applications vary from allocating the wireless spectrum worldwide to assigning sponsored slots to advertisers.Auction mechanism design aims to design proper auction rules,or equivalently an auction-based game environment,to regularize each bidder's behaviors and achieve the seller's goal.In principle,social welfare maximization and revenue maximization are two conflicting objectives in auction mechanism design.That is,if the seller wants to achieve the maximal social welfare,the revenue given in the auction cannot be maximized,and vice verse.In this dissertation,I build a general framework to improve the overall performance of the auction mechanism.Specifically,I extend traditional auction model to a social network setting,where the seller and potential buyers are regarded as strategic individuals in the network.In the abstract,the social network can be modeled as a directed graph,where the individuals and their social links correspond to the nodes and the directed edges in the graph.Due to information asymmetry,each node in the graph can only exchange information with her neighboring nodes.Under all classic auction protocols,including the VCG mechanism and the Myerson's optimal auction,buyers are in perfect competition and will not invite others to the auction.Such behavior not only limits the seller's revenue,but also fails to allocate the resources to the ones who value them most.To break the information barriers,I incorporate “sharing incentives” into auction design and propose novel mechanisms to incentivize all bidders to share the auction information to other bidders.Through this kind of information sharing,all potential buyers can join in the auction and the resources can be allocated globally.This dissertation addresses the problem for the first time and provides a systematic solution.Firstly,based on the theory of mechanism design,I propose the very first framework for selling one item in a social network.Secondly,I characterize a general theory of auction design within the framework.Finally,based on the developed theory,several novel auction mechanisms are proposed under different scenarios.Comparing to traditional auctions,these auction mechanisms improve both the seller's revenue and the social welfare.Due to the prevalent of large-scale online social networks,our solutions are significant both in theory and applications.