Strategyproofness and Monotone Allocation of Auction in Social Networks
Yuhang Guo, Dong Hao, Bin Li, Mingyu Xiao, Bakh Khoussainov
网络拍卖中的战略证明要求竞标者不仅如实报告其估值,而且还尽最大努力邀请来自社交网络的邻居。 与规范拍卖相反,在 Myerson 的 Lemma 中的价值货币分配是一个基石,但战略网络拍卖的分配规则的一般原则仍然缺失。 我们表明,由于缺乏这样的原则,即使是单单位需求的多单元网络拍卖的扩展也带来了意想不到的困难,所有开创性的研究都未能证明战略。 在这个领域,我们首次确定了两类关于网络的单调分配规则:邀请-抑郁单调性(ID-MON)和邀请-促进单调性(IP-MON)。 它们包括网络拍卖的所有现有分配规则作为特定实例。 对于任何给定的ID-MON或IP-MON分配规则,我们描述了策略性支付规则的存在和充分条件,并表明在所有此类支付规则中,收入最大化规则存在并且计算可行。 有了这些结果,现在解决了与一心一意的竞标者进行组合网络拍卖的障碍。
Strategyproofness in network auctions requires that bidders not only report their valuations truthfully, but also do their best to invite neighbours from the social network. In contrast to canonical auctions, where the value-monotone allocation in Myerson's Lemma is a cornerstone, a general principle of allocation rules for strategyproof network auctions is still missing. We show that, due to the absence of such a principle, even extensions to multi-unit network auctions with single-unit demand ...