  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.
