{'fraction_non_alphanumeric': 0.04920876300907665, 'fraction_numerical': 0.009741956945302476, 'mean_word_length': 4.101454545454545, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
LEARNING FAIR EQUILIBRIA IN SPONSORED SEARCH AUCTIONS

In this work we investigate the strategic learning implications of the deployment of sponsored search auction mechanisms that obey to fairness criteria. We introduce a new class of mechanisms composing a traditional Generalized Second Price auction (GSP) with different fair division schemes to achieve some desired level of fairness between two groups of Bayesian strategic advertisers. We propose two mechanisms, β-Fair GSP and GSP-EFX, that compose GSP with, respectively, an envy-free up to one item (EF1), and an envy-free up to any item (EFX) fair division scheme. The payments of GSP are adjusted in order to compensate the advertisers that suffer a loss of efficiency due the fair division stage. 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 of the two mechanisms through experiments on real-world data.


Introduction
Over the last decades, online advertising has been one of the main tools for small and medium business (SMB) to grow. Online advertising allows SMBs to reach potential customers without geographical or demographic barriers. Moreover, it offers better return-on-investments than other advertising mediums thanks to its highly personalized system. Given its crucial role in the growth of businesses (and, in its turn, society), it is natural to study how the mechanisms implemented in online advertising platforms can be improved to obey to different fairness criteria for the advertisers. For those reasons, we studied how standard fairness notions borrowed from the fair division literature can be used to model advertisers' fairness. One of the main advantages of employing those notions is that it's easy to integrate them into widely adopted sponsored search mechanisms. The same notions from fair division have been studied in many different settings, and already found applications in online advertising [21,44]. In the fair division literature, the dominant notion of fairness aims at providing guarantees for individual agents (see, e.g., [11,58]). However, we argue that a group approach would be more practical, better aligned with societal expectations, and easier to implement. Following recent works in group fair division literature [49,53,54,63], we propose to use envy-freeness [34] to study group fairness. Group envy-freeness guarantees that no group of agents envies the allocation obtained by any other group. Unfortunately, envy-freeness cannot be guaranteed for indivisible items. In particular, even in simple settings with two agents and one item, it is impossible to compute an allocation with any reasonable worst-case approximation guarantee. Thus, we focus on two natural relaxations of the original notion of envy-freeness: envy-freeness up to one good (EF1) [14,51], and envy-freeness up to any good (EFX) [16,40].
In practice, any attempt to guarantee such properties in real advertising platforms will inevitably collide with real-world engineering constraints. Therefore, a credible solution should be a mechanism that can be easily integrated with a pre-existing auction framework, without requiring substantial changes to it. We focus on the generalised second price (GSP) auction framework [30], which is one of the most frequently adopted mechanisms for the allocation of advertising opportunities in large Internet advertising companies. In this setting, we show the existence of simple mechanisms arXiv:2107.08271v1 [cs.GT] 17 Jul 2021 that guarantee some notion of group EF1 (resp., group EFX) for advertisers. Moreover, those mechanisms can be implemented as a post-auction layer to be run after a standard GSP mechanism. In the spirit of the work by Dwork and Ilvento [27], we study the properties of such composite mechanism.

Original contributions
Inspired by real-world applications, we focus on the Bayesian setting with incomplete information (i.e., the valuations for advertising opportunities are stochastic, and each bidder does not observe the realized valuations of the other bidders). For each auction, bidders are divided in two groups (a majority group and a minority group) based on their characteristics and competitiveness. Given the different characteristics, the users interact in different ways with the ads from the two groups. This is modeled through group specifics click-through rates and quality factors. 1 Our main contributions are the following: 1. We introduce two notions of group envy-freeness, which we call group β-EF1 and group β-EFX, parametrized on a factor β which allows the platform to tune the strength of the fairness requirement. We show that group β-EF1 and group β-EFX allocations always exist for two groups with monotonic click-through rates. Moreover, they can be computed efficiently with two fair division schemes which are, respectively, "group versions" of the standard round robin procedure, and the envy-cycle elimination algorithm by Lipton et al. [51].
2. We study the efficiency and budget-balance of the mechanisms resulting from the composition of GSP with the two fair division schemes. We show that the social welfare of the composite mechanisms is a good approximation of the optimum. Moreover, we prove that the welfare loss experienced by the advertisers due to the fairness constraints can be partly compensated for group β-EF1 via redistribution of the GSP payments. Therefore, the β-EF1 mechanism is 2-budget balanced. Similarly, we prove that the β-EFX mechanism is 4-budget balanced. 3. Finally, when bidders behave as no-regret learning agents (i.e., they take decisions so as to minimize their external regret), we show that the learning dynamic originating from the interaction with our composite mechanisms converges to a Bayesian coarse correlated equilibrium with good social welfare properties expressed in terms of the price of anarchy [47], here called price of composition, of the resulting game. This result is obtained by relating the strategies played by the agent for the fair ad auction mechanisms to the strategies of the agents in the original GSP mechanism. On the way to the analysis of the fair sponsored search auction equilibria, we also extend previous methods to the specific ad-type setting [16]. 4. We complement our theoretical investigation by evaluating the quality of our fair sponsored search mechanisms on real-world data.

Related work
The process of skewing ads delivery in ways that some users are less likely than others to see particular ads based on their demographic characteristics has recently been studied in several works [2,3,50]. Moreover, a recent line of work studies how to design advertising mechanisms that ensure diversity and fairness between users. In this context, individual fairness [28] and group fairness [33] are the most widely adopted paradigms. Celis et al. [17] propose an optimal Bayesian auction to maximize the platform's revenue conditioned on ensuring that the audience seeing an advertiser's ad is distributed appropriately across sensitive types such as gender or race. Gelauff et al. [38] studies the problem of advertising for demographically representative outcomes, with the goal of seeking fairness in the realized conversions generated by the advertising campaigns. Nasr and Tschantz [60] presents bidding strategies that advertisers can use to avoid gender discrimination at the user level.
In [44] it is proposed a model of fairness that combines the complementary notions of envy-freeness and individual fairness. Moreover, Chawla and Jagadeesan [21] study the trade-offs between social welfare maximization and fairness in the context of ad auctions while Dwork and Ilvento [26] address the problem of designing truthful ad auctions that satisfy individual fairness. The work by Dwork et al. [29] investigates individual fairness under pipeline composition, motivated by the fact that a system built from individually fair components may not itself be individually fair.
Fairness in online learning for ad auctions has also been studied within the the stochastic multi-armed bandit contextual setting. Specifically, there is a set of arms/advertisers described by latent vectors that is drawn from an unknown distribution. At each round a new user is drawn from the distributions of the contexts of two groups, a majority group and a minority group. Joseph et al. [45] study the problem of designing a learning algorithm that ensures individual fairness between the arms/advertisers. Moreover, Raghavan et al. [61] analyses the problem of designing a bandit algorithm that achieves a regret for each group that is as close as possible to the regret experienced when the group plays in isolation under the same algorithm.
Envy-freeness has been extensively studied in fair division [34,64] and in online advertising [23,24,12,22,41]. Unfortunately, envy-freeness does not always admit a solution for indivisible items and, therefore, various relaxations of this concept have been proposed in literature. The notion of envy-freeness up to one good (EF1) has been introduced by Budish [13], and in the work by Lipton et al. [51]. Budish [13] also defines the notion of maximin share allocation (MMS), based on concepts introduced by Moulin [57]. Then, Caragiannis et al. [16] introduced the notions of envy freeness up to any good (EFX) and pairwise maximin share allocation (PMMS), and more recently, Barman et al. [6] proposed to study groupwise maximin share fairness (GMMS) allocations. The notion of group EF1 allocation has recently been studied in [49], whereas the notion of approximation in several fair division schemes has been explored in [4]. Fair division problems have been extensively applied in many different settings, from apartment renting [37] to allocating blood donations to blood banks [56], and other applications [10,39,46,48,1].
The price of anarchy of GSP equilibria have been studied in various works (see, e.g., [52,62,15]). Moreover, given that no-external regret learning dynamics converge to the set of coarse correlated equilibria (see [8,20]), Blum et al. [9] study the price of total anarchy in games in which players take decisions so as to minimize their external regret. No-regret learning dynamics converging to correlated equilibria have been studied in various settings (see, e.g., [36,42,18,19,32]). Moreover, Hartline et al. [43] and Caragiannis et al. [15] study the quality of outcomes emerging from no-regret dynamics in Bayesian settings.

Preliminaries
This section describes the game-theoretic allocation mechanism and the online Bayesian framework which we adopt in the remainder of the paper. Throughout the paper, bold case letters denote column vectors. Given a vector y, its i-th component is denoted by y i . The set {1, . . . , x} is denoted by [x], and ∆ X is the |X |-dimensional simplex over the discrete set X . Formally, ∆ X := {y ∈ R |X | ≥0 : i y i = 1}.

The Generalized Second Price auction
There is a set I of n bidders and a set J of m slots. An outcome is an assignment of bidders to slots. Each bidder i has a private type v i , representing their valuation on the item which is being sold. The vector of types is denoted as v = (v 1 , . . . , v n ). Each bidder i belongs to a group from a finite set of possible groups G. The function g : [n] → G maps bidders to their specific group. Therefore, we write g(i) to denote the group to which bidder i belongs. The bidders may belong to two groups G = {h, } (e.g., a majority group and a minority group) and the two groups may have different sizes. We denote the set of bidders belonging to the two groups by I h and by I . As it is customary in the literature, we use the model of separable click probabilities (see, e.g., the work by Edelman et al. [30], Varian [65]), in which each slot j is associated with a click-through rate α j,g(i) for group g(i). We assume that for each group g ∈ G α 1,g ≥ α 2,g ≥ . . . ≥ α m,g and, without loss of generality, n = m. Each group g ∈ G is associated with a quality factor γ g ∈ [0, 1], which reflects the clickability of ads from bidders belonging to group g. Quality factors are private knowledge of the advertising platform, and not known by the bidders.
A mechanism elicits a bid b i ∈ R ≥0 for each bidder i, which is interpreted as a type declaration, and computes an outcome as well as a price p i (b, γ) for each bidder i. We denote by π(b, γ, j) the bidder assigned to slot j when the mechanism observes the bid vector b and vector of quality factors γ. We also denote by ν(b, γ, i) the slot assigned to bidder i when the mechanism observes the bid vector b and vector of quality factors γ. When the vectors of bids and quality factors are clear from the context we simplify the notation by writing π(j), ν(i), and p i in place of π(b, γ, j), ν(b, γ, i), and p i (b, γ), respectively. Bidder i assigned to slot ν(i) receives a value α ν(i),g(i) γ g(i) · v i and utility We focus on a family of mechanisms derived from the Generalized Second Price (GSP) auction (see, e.g., [65]). In a GSP auction the mechanism assigns the slots in order from 1 to m and sets π(b, γ, j) to be the bidder with the highest effective bid γ g(i) α j,g(i) · b i not yet assigned (breaking ties arbitrarily). For any bid profile b, quality factors γ and for each j ∈ [m], i = π(j), the price charged to bidder i is computed as where we set b n+1 = 0. 2 The mechanism is Individually Rational (IR) if for each bidder i ∈ I, u i (b, v, γ) ≥ 0, for all b, v, and γ.

Online Bayesian framework
The n bidders participate in a series of GSP auctions. At each iteration t, each bidder i observes a valuation v t i for the item being sold at time t. Let V i be the finite set of types of bidder i. The vector of types v t = (v t 1 , . . . , v t n ) is drawn, at each t, from a (possibly correlated) probability distribution F supported on a finite set of joint types V, that is, V := × i∈[n] V i . Moreover, at each t, a vector of quality factors γ t ∈ [0, 1] |G| is drawn from a (possibly correlated) distribution G.
Bidding strategies Each bidder i has an arbitrary finite set of available bids B i ⊆ R ≥0 , withB i := max B i and B i ≥ sup V i . Moreover, we denote by B := × i∈[n] B i the set of all possible joint bid profiles. A bidding strategy σ i for bidder i is a (possibly randomized) mapping from their types V i to their available bids B i . We represent such strategies as a |V i | × |B i | right stochastic matrix in which each row specifies a well-defined probability distribution over bids. Formally, bidder i's strategy space is defined as: We observe that bidders cannot condition their bids on their quality factors γ, since they are only known to the platform, and not to advertisers. Finally, we define the set of joint bidding strategies as Therefore, a joint strategy σ ∈ Σ is a well defined probability distribution over V × B such that its v-marginals are consistent with F.
Utility function At each iteration t, bidder i places bids according to a bidding strategy σ t i ∈ Σ i . In particular, bidder i observes its own type v t i , and then submits a bid Then, bidder i experiences a reward which we define as a function u t i : B i → R. The utility function u t i observed at time t implicitly depends on the realized vector of bids b t −i , and quality factors γ t , and it is such that, for each possible bid b ∈ B i , i is the price charged to bidder i at time t according to Equation (2). Regret and equilibria Given a sequence of decisions (b 1 i , . . . , b T i ) up to time T , the external regret of bidder i in type v i is how much they regret not having played the best fixed action in hindsight at each iteration in which they observed type v i . Formally, the regret experienced by bidder i under a certain type v i ∈ V i is Therefore, the cumulative external regret of bidder i at time T reads as follows Let (b t ) T t=1 be the sequence of decisions made by the bidders up to time T . Then, the empirical frequency of plaȳ σ T ∈ ∆ V×B obtained from the realized sequence of types (v t ) T t=1 , and from the sequence of play If each bidder i plays so as to obtain a regret R T i growing sublinearly in T , then, in the limit as T → ∞, the empirical frequency of playσ T is guaranteed to converge almost surely to a Bayesian coarse correlated equilibrium [15,43]. The 2 Alternatively, we could charge bidder π(j) with the threshold price, which is the smallest effective bid p T i that guarantees them the same slot. Observe that pi ≤ p T i since the next highest bidder on slot j is not necessarily π(j + 1) if the bidders have different quality factors. 3  notion of Bayesian coarse correlated equilibrium (see, e.g., [35,7]) generalizes the standard notion of coarse correlated equilibrium for games with complete information by Moulin and Vial [59] to settings with incomplete information. In particular, we define a Bayesian coarse correlated equilibrium as follows.
where F vi is the posterior distribution over × i =i V i having observed type v i for bidder i, and u i is defined as in Equation (1).
We denote by Σ * ⊆ Σ the set of all Bayesian coarse correlated equilibria of the underlying game.

Group fairness in GSP Auctions
In this section we present the two group fair division schemes that will be added as a post-auction layer to GSP. Let be the set of slots assigned to group h ∈ G at some time t. Time t will be omitted when clear from the context. Consider an arbitrary stage of the repeated auctions process. We identify by I h (j) the bidder belonging to I h with the j-th valuation in decreasing order (i.e., I h (1) is the bidder of group h with the highest valuation). Analogously, J h (j) denotes the slot with the j-th click-through rate among slots in the set J h . We denote by ALG h (J h ) and ALG (J ) the value obtained by a generic mechanism for group h and on a bid vector b, and on a set of slot J h and J , respectively. Then, the value obtained by group h from the slots assignment J h on bid vector b is Intuitively, ALG h (J h ) is the value computed on bid vector b under the best allocation of the slots in J h to bidders in group I h . The value ALG (J ) for group is defined analogously. Observe that, in general, the value ALG (·) (J (·) ) differs from the social welfare does not correspond to the valuation vector v. The first mechanism that we describe employs a fair division scheme that achieves the following notion of group fairness.
Definition 2. (Group β-EF1 fairness) Let β := ξ /ξ h , with ξ h , ξ ∈ N + , and ξ h ≥ ξ . We say that an allocation is group β envy-free up to one good (β-EF1 fair) for β ≤ 1 if, for each pair of groups h, ∈ G, there exists one item A group β-EF1 fair allocation can be obtained through a Round Robin procedure that assigns ξ h slots to group h for each ξ slots assigned to group . The proof of this result is very similar to the one for the classical EF1 fair division scheme by Markakis [55]. As an example, if we assume group h to be the majority group (i.e., advertisers from group h are allocated the highest slots in the ranking), then the result of the application of the group β-EF1 round robin procedure is the shift of advertisers assigned to a position j ∈ J h to position at most (1 + β)j − 1. For additional details on how this fair division scheme is implemented see the pseudo-code in Appendix B.
Now, we introduce the second notion of fairness which we consider, that is group β-EFX fairness.
Definition 3. (Group β-EFX fairness) An allocation is group β-envy free up to any good (β-EFX fair) for β ≤ 1 if, for each pair of groups h, ∈ G, for each item j h ∈ J , for each bid vector b, it holds A group β-EFX fair division scheme can be obtained through a "group version" of the envy-cycle elimination algorithm by Lipton et al. [51]. In particular, we propose the group envy-cycle-elimination algorithm, which we denote by GECE. The GECE algorithm can be summarized as follows: denote by J h and J the set of slots assigned, respectively, to group h and . We say that group h envies group if ALG h (J h ) < βALG h (J ). Initially, all the slots are not assigned, that is, J h = J = ∅. Then, the algorithm iterates through the slots in decreasing order of click-through rate. The first slot is assigned to group h. For each subsequent slot j, the algorithm checks if groups h and envy each other, and, if this is the case, the algorithm swaps their allocations. Otherwise, if group does not envy group h, then the next slot is assigned to group h, else, if envies h, the slot is assigned to group . The pseudo-code of GECE is given in Appendix B. In the following theorem, we prove that the GECE algorithm is guaranteed to obtain a β-EFX allocation. All the omitted proofs can be found in Appendix C.
Theorem 1. The allocation computed by the group envy-cycle-elimination (GECE) algorithm is group β-EFX fair.

Efficiency and budget balance of the composite mechanisms
In this section, we study the efficiency and budget balance of the two mechanisms obtained by combining GSP with the two fair division schemes described in Section 3. Let us denote one such composite mechanism by C. The post-auction layer of the composite mechanism C is modifying the GSP allocation of slots to bidders. Ideally, no bidder should be penalized for this re-allocation. Therefore, we need to update the payments so that bidders' utility is not negatively affected by the composition of GSP with the fair division scheme. Interestingly, we can do so starting from the payments of GSP. In particular, denote by p G i and by p C i , the payments charged to advertiser i computed by GSP and by the composite mechanism, respectively. Moreover, let ν G (i) and ν C (i) be the slots assigned to advertiser i by GSP and by the composite mechanism, respectively. Then, we define the payments charged by the composite mechanism C as: The pricing rule shows that the composite mechanism C compensates the loss of social welfare of the advertisers that obtain a worse slot by reducing their payments. In order to ensure individual rationality, the advertisers that obtain a better slot are not asked to compensate with a higher payment.
Now, let us first define an appropriate notion of budget balance for a composite mechanism which assigns a payment p C i to bidder i ∈ I, with respect to a GSP mechanism that charges the same bidder with payment p G i . Definition 4. A composite mechanism is α-budget balanced, for α ≥ 0, if the following holds An α-budget balanced mechanism is therefore able to cover with the GSP payments at least an α fraction of the compensations given to the bidders by the composite mechanisms.
In this section, we denote by ALG(b) the value obtained by a generic mechanism on a bid vector b, and by ALG h (b) and ALG (b) the values obtained from the first and the second groups. Therefore, We'll denote by ALG G (b) and ALG C (b), respectively, the value of the GSP mechanism and of the fair composite mechanism on any bid vector b.
We use the following two assumptions in the analysis of the composite mechanisms.
Assumption 1. The value of the second group increases after the application of the composite mechanism, i.e., Assumption 2. The first slot is assigned by GSP to I h (1), i.e., the first bidder of group h.
The β-Fair GSP mechanism We provide efficiency and budget balance results for the β-Fair GSP mechanism. More specifically, we prove that: (i) the β-Fair mechanism is group β-EF1, (ii) the mechanism is 2-budget balance.
We prove the following guarantee on the efficiency of the β-Fair GSP mechanism: Theorem 2. The β-Gair GSP mechanism achieves a value that is at least a 1/(1 + β) fraction of the value of GSP, i.e., for all bid vectors b ∈ B, ALG C (b) ≥ 1 (1+β) ALG G (b). Moreover, the following property holds.
The GSP-EFX mechanism We study efficiency and budget balance of the GSP-EFX mechanism. The allocation done by the mechanism is described in Section 3 and it is obtained by the composition of the GSP mechanism with the group EFX fair division scheme. The payments of GSP-EFX are computed as in Equation (4), i.e., the payments are reduced appropriately for those agents that are assigned to a worse slot in the composite mechanism. As for the efficiency of GSP-EFX, the following holds. Theorem 4. GSP-EFX achieves a value that is at least a fraction 1/3 of the value of GSP, i.e., for all bid vectors b ∈ B, ALG C (b) ≥ 1 3 ALG G (b). Finally, we prove that GSP-EFX is able to compensate at least 1/4 of the total welfare loss generated by the application of the EFX mechanism. Formally, Theorem 5. The GSP-EFX mechanism is 4-budget balance.

Price of composition of the fair GSP mechanisms
Equipped with the results from Section 4 we can study the performance of the proposed mechanisms at equilibrium. In particular, we are interested in understanding the quality of the equilibria emerging as the results of the no-regret learning dynamics in which each bidder behaves as an external-regret minimizer. To do so, we propose the price of composition (PoC) as a natural measure to evaluate the social welfare guarantee of our mechanisms at equilibrium. For an arbitrary mechanism, the social welfare attained under given bid profile b ∈ Σ, valuation profile v ∈ V, and quality factor profile γ is α j,g(π(j)) γ g(π(j)) v π(j) .
Given an equilibrium strategy σ ∈ Σ * in an incomplete-information game, its social welfare is evaluated by comparing it to the expected ex-post social welfare of the GSP mechanism, which we denote by E v,γ [SW G (v, γ)]. In particular, we can define the following worst-case ratio Definition 5. The price of composition (PoC) of a composite mechanism C is defined as .
Notice that by the definition of the composite mechanisms here introduced, the social-welfare of the composite mechanism is at most equal to the social welfare of the GSP mechanism (see Section 4), i.e., POC ∈ [0, 1]. We observe that bounding the worst case POC automatically yields a POC/2 guarantee on the price of total anarchy of the game as defined by Blum and Mansour [8]. This is because SW G (v, γ) ≥ SW * (v, γ)/2, where SW * is the optimal social welfare with valuations v. 4 Lucier and Paes Leme [52] introduce semi-smoothness as an extension of the notion of smoothness originally introduced by Roughgarden [62], which implies price of anarchy bounds even in the Bayesian setting with arbitrarily correlated types. Formally, by letting SW (σ) be the social welfare generated by strategy σ for some (implicitly defined) game, the definition of (λ, µ)-semi-smoothness reads as follows.
Definition 6. [Def. 2 by Lucier and Paes Leme [52]] A game is (λ, µ)-semi-smooth if there exists some strategy σ = (σ 1 , . . . , σ n ) ∈ × i Σ i maximizing the social welfare such that, for any joint strategy profile σ ∈ Σ it holds i∈[n] where SW is the social welfare of the mechanism with an arbitrary (fixed) vector of valuations.
We introduce a generalization of Definition 6 which is a natural smoothness condition for composite mechanisms. Let SW G be the social welfare of the baseline mechanism (that is, in our setting, GSP), and let SW C be the social welfare provided by the composite mechanism (in our case, β-Fair GSP or GSP-EFX) given an arbitrary vector or valuations. Then, our notion of smoothness states that social welfare gaps between the social welfare at the baseline mechanism with truthful bid vector v, and the social welfare for an arbitrary joint strategy profile σ ∈ Σ in the composite mechanism, can be captured by the marginal increases in the individual agents' utilities when unilaterally switching to a deviation strategy profile σ = (σ 1 , . . . , σ n ). Formally, a composite mechanism C is (λ, µ)-semi-smooth with respect to a baseline mechanism G if there exists a profile of individual bidding strategies σ = (σ 1 , . . . , σ n ) ∈ × Σ i such that, for any joint bidding strategy σ ∈ Σ, v ∈ V, and γ, it holds where expectations are taken over random bits of strategies σ, σ . In our Bayesian framework with ad types we prove the following result.
Therefore, by exploiting the fact that (λ, µ)-semi smoothness implies a λ 1+µ price of composition, we can characterize the POC of the two mechanisms as follows.
Analogously, it is possible to prove the following result for GSP-EFX: Theorem 7. The price of composition with uncertainty of GSP-EFX is POC = 1/8.

Experimental evaluation
We provide an experimental evaluation of the quality of the equilibria emerging as the results of no-regret learning dynamics in which agents interact through the β-Fair GSP mechanism.
Regret minimization for the Bayesian setting For each bidder i, we consider a discrete set of bids B i . We focus on the partial-information setting, in which, at each time instant t, each bidder observes only the reward u t i (b t i ) associated to its choice b t i ∈ B i . This is in line with what happens in real-world sponsored search auctions, where advertisers do not observe competing bids (i.e., they cannot compute a counterfactual utility u t i (b) for each b ∈ B i ), but can only observe the outcome associated to their decision b t i . We instantiate an external-regret minimizer R i,v for each bidder i and v ∈ V i . In practice, we use the EXP3 algorithm by Auer et al. [5] for each external regret minimizer. Then, we build a regret minimizer for the Bayesian bidder i as follows: at each t, bidder i observes their realized type v t ∈ V i and selects b t i ∈ B i according to R i,vi . Then, after utility u t i (b t i ) is observed, only R i,vi is updated. This simple procedure guarantees that lim sup T →∞ R T i /T ≤ 0, which implies that the empirical frequency of playσ T of the dynamic converges almost surely in the limit to a Bayesian coarse correlated equilibrium (see, e.g., Hartline et al. [43,Lemma 10]).
Experimental setting We construct a real-world dataset through logs of a large Internet advertising company. We test our β-Fair GSP mechanism in an artificial environment where we have 20 advertisers, equally distributed among two groups, and. competing for ad opportunities over a sequence of T = 10 4 auctions. For each i, we set V i = {x/100 : x ∈ [100] ∪ {0}}. Moreover, in order to be able to create a steep unbalance between the two groups, we let, for each v ∈ V, F(v) = F 1 (v 1 ) · . . . · F n (v n ), with F i ∈ ∆ Vi for each i. Then, for each i ∈ I h (i.e., advertiser i belongs to the majority group), we artificially set value distributions to be such that F i (1) = 1, and F i (v) = 0 for each v ∈ V i \ {1}. Each bidder i ∈ I has a value distribution F i built by normalizing the distribution of bids observed from real-world bidding data of a large Internet advertising company. Due to the nature of the bidding system, the bids provide a good approximation to the true valuations of advertisers. Discount curves are computed by averaging and normalizing in [0, 1] real-world discount factors. In particular, we estimate discount curves on ads optimizing for two distinct conversion types, one per group. This models different per-group preferences on the slots. Quality factors are set to be γ = (1, 1). Experiments are run on a 24-core machine with 57Gb of RAM.
Results Each advertiser takes decisions so as to minimize their external regret according to the procedure described above. Then, we analyse the equilibrium outcomes originating from regret-minimizing advertisers interacting through GSP and β-Fair GSP, respectively. To do so, we compute the empirical frequency of playσ T in the two settings. Let σ T,G andσ T,C be the empirical frequency of play obtained via the GSP mechanism, and the empirical frequency of play obtained via the β-Fair GSP mechanism, respectively. Figure 1-Left, and Figure 1-Center report a comparison between the expected social welfare attained atσ T,G (i.e., SW G ), the expected social welfare attained atσ T,C (i.e., SW C ) for different values of ξ h , while for simplicity we keep ξ = 1 (see Definition 2), and the expected social welfare obtained when advertisers are not strategic and submit bids truthfully to a GSP mechanism (i.e., SW OPT ). Each value is computed over 20 repetitions of the dynamics, and figures display the resulting mean and standard deviation. In particular, Figure 1-Left reports the overall social welfare, and shows that, as expected, lower values of k increase ∆SW , that is, the gap between the social welfare provided by the GSP solution and the social welfare provided by the β-Fair GSP solution. The gap is negligible for most values of β = 1/ξ h , and in the worst case, the empirical gap is approximately 10% of the social welfare provided by GSP. Figure 1-Center reports the per-group social welfare at equilibrium. Finally, Figure 1-Right describes the fraction of the revenue which is lost due to compensation for advertisers as defined in Equation (4). We observe that, in practice, the fraction of the GSP prices used for compensation significantly lower than the worst case bound of Theorem 3. In particular, the composite mechanism looses nearly 40% of GSP revenue when ξ h = 1 (i.e., when the group fairness constraint is as tight as possible). However, for higher values of ξ h , the fraction of p G which has to be used for compensations stabilizes around 20%. This suggests that there may be a trade-off between guarantees for advertisers and revenue losses incurred by the platform where this type of mechanisms could be viable in practice. A Summary of the notation Table 1 summarizes the main notation used throughout the paper.

Symbol Description
V i Set of types of bidder i. V Set of joint bidders' types, V := × V i .

F
Probability distribution over V. G Distribution of quality factors.
G Set of bidders' groups. g Function g : [n] → G such that g(i) is the group of bidder i.
Bidder with the j-th highest valuation among bidders of group (·).
Slot with the j-th highest click-through rate among slots assigned to group (·). Abbrev.: p i when b and γ are clear from the context. π(b, γ, j) Bidder assigned by the mechanism to slot j.
Abbrev.: π(j) when clear from context. ν(b, γ, i) Slot assigned by the mechanism to bidder i.
Utility observed by bidder i under bids vector b, realized valuations v, and quality factors γ (see Equation (1)).

ALG(b)
Value obtained by the mechanism under bid vector b. SW (b, v, γ) Overall social welfare provided by the mechanism under bid vector b, realized valuations v, and quality factors γ (see Equation (5)). SW (·) (J ) Social welfare for bidders in group (·) ∈ G under the best allocation of slots in J ⊆ [m] to bidders in I (·) . Table 1: Summary of notation used in the paper.

B Group fair division schemes
In this section, we report the the pseudocode for the two fair division schemes described in Section 3.
The β-Fair GSP mechanism The first fair division scheme (see Algorithm 1) takes as input the two groups of advertisers I h and I , the β = ξ /ξ h parameter, the GSP allocation π G , and returns the allocation of β-EF1 GSP. Let I G (·) (j) be the bidder of group (·) ∈ G with the j-th highest effective bid within that group. This means that, given the GSP allocation, , and analogously for group . The Round-Robin scheme allocates the first ξ h slots to the majority group h (if there are enough bidders from group h, see Line 5). Then, it proceeds by allocating ξ slots to group (Line 9). Bidders belonging to the same group are allocated following the GSP ordering (i.e., in descending order of effective bid (see Lines 6,10,13,16). Finally, when at least one of the two groups has been fully assigned, the algorithm completes the allocation by allocating the remaining slots to the group that still has bidders which have not been given a slot (Lines 12, 15).
Group envy-cycle elimination The second fair division scheme (Algorithm 2) takes as input the two groups of advertisers I h and I , the β parameter, the GSP allocation π G , and returns the allocation obtained via the GECE algorithm to be employed by GSP-EFX. First, the algorithm computes an allocation of slots to groups (Lines from 3 to 9). Then, the algorithm proceeds by allocating slots within each group by following the GSP ordering (Lines from 10 to 17). Algorithm 2 starts by assigning the first slot to group h, and the second slot to group , respectively. Then, the algorithm iterates through the slots in decreasing order of click-through rate. For each subsequent slot j, the algorithm checks if groups h and envy each other, and, if this is the case, the algorithm swaps their allocations (Line 5). Otherwise, if group does not envy group h, then the next slot is assigned to group h, else, if envies h, the slot is assigned to group . Finally, the allocation π C is built by assigning the per-group allocations J h and J in decreasing order of effective bid (i.e., by following the GSP ordering within each group).
Proof. The claim of the proof clearly holds for the base case when J h = J = ∅. For the inductive hypothesis, assume it holds before the next item x ∈ [m] is assigned. We distinguish between three cases: • Let us first consider the case of a slot x assigned to group . The set of slots assigned to is J ∪ {x}. EFX clearly holds for group , since it is allocated one additional slot. Let us consider group h. We know that, for any y ∈ J , , y has higher click through rate than x). This proves β-EFX for group h.
• Next, we consider the case of a swap between the two allocations (Line 5 of Algorithm 2). Before a swap happens, it holds ALG h (J h ) < βALG h (J ) and ALG (J ) < βALG (J h ), and, therefore, EFX immediately holds after the swap for any β ≤ 1.
• Finally, we consider the case of ALG h (J h ) ≥ βALG h (J ) and ALG (J ) ≥ βALG (J h ) before slot x is assigned to group h. In this last case, β-EFX still holds for group h that receives one more item. It also holds for group since This proves the statement.
Theorem 2. The β-Gair GSP mechanism achieves a value that is at least a 1/(1 + β) fraction of the value of GSP, i.e., for all bid Proof. We use the the results of Section Section 3 on Group β-EF1 fairness. The social welfare obtained through the composition of the two mechanisms can be lower bounded as follows.
≥ i∈I h γ g(i) biα ν G (i),g(i) + i∈I γ g(i) biα ν G (i),g(i) − i∈I h : ν C (i)>ν G (i) γ g(i) bi(α ν G (i),g(i) − α ν C (i),g(i) ) = i∈I γ g(i) biα ν G (i),g(i) + i∈I h : ν C (i)≤ν G (i) γ g(i) biα ν G (i),g(i) + i∈I h : ν C (i)>ν G (i) γ g(i) biα ν C (i),g(i) ≥ ALG G (b) + n/(1+β) j=1 γ g(π G (j)) b π(j) α (1+β)j −1,g(π G (j))) (8) ≥ ALG G (b) + 1 (1 + β) n j=1 γ g(π G (j)) b π G (j) α j,g(π G (j)) (9) Equation (7) follows from Assumption 1 stating that the application of the composite mechanism will always increase the social welfare of the minority group , while the majority group h will experience a social welfare loss. Equation (8) follows since the welfare loss of a bidder π G (j) is positive if assigned by round robin to a slot with lower quality. We observe that this can only happen for the first n(1/(1 + β)) bidders in the GSP solution that are shifted from a position j to a position of lower quality. Given that round robin alternates ξ h bidders of group h with ξ bidders of group , with β = ξ /ξ h , the landing position of the bidder assigned from GSP at position j is never worse than position (1 + β)j − 1. Clearly, the bound also holds for the bidders of group h and that are not shifted in the composed mechanism. Equation (9) follows from the fact that n/(1+β) j=1 γ g(π G (j)) b π G (j) α (1+β)j −1,g(π G (j))) has always the term of the first slot followed by at least ξ h terms out of ξ h + ξ , with ξ ≤ ξ h , corresponding to bid values that are at least as high as those of GSP, and, therefore, at least a ξ h ξ h +ξ = 1 (1+β) fraction of ALG G (b) is recovered. This completes the proof.
Proof. We prove that the loss in the value obtained through the β-Fair GSP mechanisms is at most equal to the payments of GSP. We derive the 2-budget balance result given that the compensation for each bidder is equal to twice the loss in social welfare according to the pricing rule in Equation (4) computed on the bid vector b.
Given the GSP allocation π G , it can be observed that the loss in social welfare computed on bid vector b is: b π G (j) γ g(π G (j)) (α j,g(π G (j)) − α (1+β)j −1,g(π G (j)) ) ≤ n/(1+β) j=1 b π G (j+1) γ g(π G (j+1)) α j+1,g(π G (j+1)) ≤ n j=1 p G π G (j) , The above derivation is based on the observation that, in the worst case, the round robin mechanism is shifting the first n/(1 + β) bidders to a worse slot of index at most equal to (1 + β)j − 1. Moreover, the second inequality holds true since, by construction of Algorithm 1 and by Equation (4), the first term of the summation (i.e., for j = 1) is equal to 0 since by Assumption 2 the first slot is assigned by GSP to the majority group, and since γ (·) ∈ [0, 1] for each group (·) ∈ G. This concludes the proof.
If the GSP-EFX assignment of the first bidder of the two groups is not in agreement with the solution of GSP, by Assumption 2, the first advertiser 1 of group h gets assigned slot 1 in GSP and slot 2 in GSP-EFX. The loss in social welfare of advertiser 1 is equal to b1γ h (α 1,h − α 2,h ). If group is assigned at least two slots, we know by the definition of EFX on bid declarations that ALG h (J C h ) ≥ b1γ h α 1,h , since the first slot is assigned to group h. If group is assigned only the first slot, we know that there have been a swap that gave slot 1 to group , after the swap no item has been assigned to group h, and therefore the above expression holds at time of swap and at any later time. Therefore, we can bound the loss in value for the first bidder as follows