In this work we introduce a new class of mechanisms composed of a traditional Generalized Second Price (GSP) auction and a fair division scheme, in order to achieve some desired level of fairness between groups of Bayesian strategic advertisers. We propose two mechanisms, $\beta$-Fair GSP and GSP-EFX, that compose GSP with, respectively, an envy-free up to one item, and an envy-free up to any item fair division scheme. The payments of GSP are adjusted in order to compensate advertisers that suffer a loss of efficiency due the fair division stage. We investigate the strategic learning implications of the deployment of sponsored search auction mechanisms that obey to such fairness criteria. We prove that, for both mechanisms, if bidders play so as to minimize their external regret they are guaranteed to reach an equilibrium with good social welfare. We also prove that the mechanisms are budget balanced, so that the payments charged by the traditional GSP mechanism are a good proxy of the total compensation offered to the advertisers. Finally, we evaluate the quality of the allocations through experiments on real-world data.
翻译:在这项工作中,我们引入了由传统的普遍第二次价格(普惠制)拍卖和公平分割计划组成的新一类机制,以实现巴伊西亚战略广告商集团之间某种理想的公平程度;我们提出了两个机制,即美元-公平普惠制和普惠制-EFX,分别构成普惠制,一个项目不受嫉妒,一个项目不受嫉妒,另一个项目公平分割计划不受嫉妒;普惠制的付款进行调整,以补偿因公平分化阶段而蒙受效率损失的广告商;我们调查采用受赞助的符合这种公平标准的搜索拍卖机制的战略学习影响;我们证明,对于这两种机制,如果投标人能够最大限度地减少外部遗憾,保证他们能够达到与良好社会福利的平衡;我们还证明,机制预算平衡,传统普惠制机制所收取的付款是向广告商提供的全部报酬的良好替代物;最后,我们通过实际世界数据实验评估拨款的质量。