Multi-item Auction Mechanism Design Over Social Networks

Auction,as an effective methods of resource allocation,is one of the most classic and successful applications in the field of mechanism design.In recent years,the popularity of diffusion auctions on social networks has been growing.Diffusion auctions aim to incentivize bidders to truthfully bid and invite their neighbors to participate in the auction through social connections.Compared to traditional auction mechanisms,these models optimize key properties in the auction,such as social welfare and seller revenue,by attracting more bidders.In the research on single-item diffusion auctions,many studies have provided profound theoretical foundations and real-world characterizations.However,in the context of multi-item auctions,there is an increased possibility for bidders to deviate from truthful strategies and obtain potential additional profits,rendering single-item auction models inadequate.Additionally,existing research on multi-item diffusion auctions suffers from the drawback of failing to incentivize bidders to disclose their true preferences.Therefore,in the context of multi-item diffusion auctions,there is an urgent need to address the challenge of ensuring social welfare and seller revenue while guaranteeing truthful disclosure of valuation and neighbor information by bidders.This research focuses on multi-item diffusion auction problems.Firstly,the homogeneous multi-item diffusion auction scenario is theoretically analyzed.In this analysis,the paper presents counterexamples showing that existing mechanisms,i.e.,GIDM mechanism and the DNA-MU mechanism,do not satisfy incentive compatibility.In these examples,bidders benefit by concealing their neighbor information,which violates incentive compatibility.Based on these counterexamples,the paper analyzes the lack of monotonicity characterization in the allocation rules as the core issue behind the truth-telling problem in the GIDM and DNA-MU mechanisms.The paper highlights the importance of monotonicity in the propagation dimension of allocation rules for designing multi-item viral auction mechanisms that satisfy incentive compatibility.Based on the impact of diffusion strategies on allocation rules,the paper provides two paradigms of multi-item networked diffusion auction mechanisms that satisfy allocation monotonicity.Furthermore,it proves that these two paradigms satisfy individual rationality,incentive compatibility,and provides corresponding mechanism examples based on the two paradigms.Building upon the theoretical findings mentioned above,the paper further investigates the application of reverse procurement auctions and extends this scenario to be implemented on social networks.Under the paradigms of multi-item diffusion auction mechanisms that satisfy individual rationality and incentive compatibility,this work designs networked diffusion auction mechanisms for homogeneous procurement(Diff-CRAHM)and heterogeneous procurement(Diff-CRA-HT)scenarios,respectively.Moreover,the paper theoretically proves that these two mechanisms satisfy individual rationality,incentive compatibility,weak budget balance,computational feasibility,and other desirable properties.Finally,the paper conducts experimental simulations based on multiple real-world social network datasets.The results demonstrate that the Diff-CRA-HM and Diff-CRA-HT mechanisms outperform the traditional VCG mechanism,showcasing their practical feasibility and robustness under different social network structures.