Digital advertising constitutes one of the main revenue sources for online platforms. In recent years, some advertisers tend to adopt auto-bidding tools to facilitate advertising performance optimization, making the classical \emph{utility maximizer} model in auction theory not fit well. Some recent studies proposed a new model, called \emph{value maximizer}, for auto-bidding advertisers with return-on-investment (ROI) constraints. However, the model of either utility maximizer or value maximizer could only characterize partial advertisers in real-world advertising platforms. In a mixed environment where utility maximizers and value maximizers coexist, the truthful ad auction design would be challenging since bidders could manipulate both their values and affiliated classes, leading to a multi-parameter mechanism design problem. In this work, we address this issue by proposing a payment rule which combines the corresponding ones in classical VCG and GSP mechanisms in a novel way. Based on this payment rule, we propose a truthful auction mechanism with an approximation ratio of $2$ on social welfare, which is close to the lower bound of at least $\frac{5}{4}$ that we also prove. The designed auction mechanism is a generalization of VCG for utility maximizers and GSP for value maximizers.
翻译:数字广告是在线平台的主要收入来源之一。 近年来,一些广告商倾向于采用自动招标工具来促进广告绩效优化,使得拍卖理论中的古典 \ emph{pility最大化模式不合适。最近的一些研究提出了一个新的模式,名为 emph{valuly最大化 }, 供受投资回报限制的自动广告商使用。然而,公用事业最大化或价值最大化模式只能给真实世界广告平台中部分广告商定性。在公用事业最大化者和价值最大化者共存的混合环境中,真实的拍卖设计将具有挑战性,因为投标人可以操纵其价值和附属类别,从而导致多参数机制设计问题。在这项工作中,我们提出了一个付款规则,将传统的VCG和普惠制机制中的相应规则结合起来,从而解决这一问题。根据这项付款规则,我们提议一个真实的拍卖机制,在社会福利上贴近2美元的近似比值,接近于至少$\frac{{5 ⁇ 4}的低约束值,因此真实的拍卖设计将具有挑战性,因为投标人可以操纵其价值和附属类别,从而导致多参数机制设计上的问题。在这项工作中,我们提出的最高程度拍卖机制是为了最大程度的通用G。