Diffusion and Auction on Graphs
Diffusion and Auction on Graphs
复制标题
DOI：
10.24963/ijcai.2019/62
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Bin Li;Dong Hao;Dengji Zhao;M. Yokoo
中科院分区：
文献类型：
--
作者：
Bin Li;Dong Hao;Dengji Zhao;M. Yokoo
拍卖是解决人类社会基本问题之一的资源配置的普遍范式。现有的研究表明，在拍卖设计中，卖方收益和分配效率这两个主要目标通常是相互冲突的。我们首次将经典拍卖的领域扩展到社交图，并在图上正式识别出一类新的拍卖机制。这类机制都是激励相容的，也促进所有买家扩散拍卖信息给其他人，从而卖方的收入和分配效率显着提高相比，Vickrey拍卖。结果发现，最近提出的信息扩散机制是一个极端的情况下，在这个新的类的收入最低。我们的工作可能会激发一个新的视角，高效和最佳的拍卖设计，并可以应用到流行的在线社会和经济网络。
Auction is the common paradigm for resource allocation which is a fundamental problem in human society. Existing research indicates that the two primary objectives, the seller's revenue and the allocation efficiency, are generally conflicting in auction design. For the first time, we expand the domain of the classic auction to a social graph and formally identify a new class of auction mechanisms on graphs. All mechanisms in this class are incentive-compatible and also promote all buyers to diffuse the auction information to others, whereby both the seller's revenue and the allocation efficiency are significantly improved comparing with the Vickrey auction. It is found that the recently proposed information diffusion mechanism is an extreme case with the lowest revenue in this new class. Our work could potentially inspire a new perspective for the efficient and optimal auction design and could be applied into the prevalent online social and economic networks.