Fair Equilibria in Sponsored Search Auctions: The Advertisers’ Perspective

1 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 advertisers. There are indeed various settings where one may care about balancing ads allocations, even just between a majority and a minority group of advertisers. For example, one setting is when large companies and small businesses are competing for the same set of users, and the platform may want to ensure that small companies get reasonable visibility despite smaller budgets. As another example, there may be businesses based in different geographical locations but offering similar products/services. These businesses may have unbalanced budgets due to their location, but one may want to guarantee to each business some visibility in a target set of users regardless of geographical attributes. More in general, one could think of incorporating fairness in sponsored search auctions whenever two different parties are advertising to increase users' awareness about some sensitive topic.

We study how fairness notions borrowed from the fair division literature can be used to model fairness with respect to advertisers. Notions from fair division already found applications in online advertising [Chawla and Jagadeesan, 2020; Ilvento et al., 2020]. In the fair division literature, the dominant notion of fairness aims at providing guarantees for individual agents (see, e.g., [Brandt et al., 2016; Moulin, 2003]). 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 [Kyropoulou et al., 2020; Manurangsi and Suksompong, 2017; Manurangsi and Suksompong, 2019; Segal-Halevi and Suksompong, 2019], we propose to use envy-freeness [Foley, 1967] to study group fairness. Group envy-freeness guarantees that no group of agents envies the allocation obtained by any other group. Unfortunately, envyfreeness cannot be guaranteed for indivisible items even in simple settings with two agents and one item. Thus, we focus on two natural relaxations: envy-freeness up to one good (EF1) [Budish, 2011; Lipton et al., 2004], and envyfreeness up to any good (EFX) [Caragiannis et al., 2019; Gourv`es et al., 2014]. 1

In practice, any attempt to guarantee such properties in real advertising platforms will inevitably collide with realworld 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 [Edelman et al., 2007], 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 that guarantee some notion of group EF1 (resp., group EFX) for advertisers. Such 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, 2019], we study the properties of such composite mechanisms.

1 See the full paper for additional discussion of related work.

Original contributions We focus on a 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 clickthrough rates and quality factors. 2 First, in Section 3, we introduce two notions of group envy-freeness (group β-EF1 and group β-EFX), parameterized 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 round robin procedure, and the envy-cycle elimination algorithm by Lipton et al. [2004]. We define fairness with respect to reported bidder's valuations. Indeed, we argue that an auction is perceived to be fair if the slots are divided between the majority/minority group in a fair way, given that prices are not publicly known to all advertisers in real-world sponsored search auctions. Considering the social welfare of the allocation is also the customary approach in the fair division literature, in which notions such as EF1 and EFX are defined on valuations (see, e.g., [Budish, 2011; Amanatidis et al., 2019]). Then, in Section 4, 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 through monetary incentives via redistribution of the GSP payments. Finally, Section 5 studies the behavior of the composite mechanisms when bidders behave as no-regret learning agents (i.e., they take decisions so as to minimize their external regret) and they are conservative (i.e., they do not overbid). 3 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 characterized through their price of composition. We complement our theoretical results by evaluating the quality of our fair sponsored search mechanisms on real-world data (Section 6).

2 The online advertising problem with group specifics clickthrough rates has already been formalized in literature in the AdTypes setting [Colini-Baldeschi et al., 2020; Elzayn et al., 2021].

3 The assumption of having conservative bidders has often been used in the analysis of ad auction mechanisms (see, e.g., [Leme and Tardos, 2010; Christodoulou et al., 2016; Feldman et al., 2013]). The rationale for this is usually that, in practice, bidders are only partially informed and, thus, they may be more inclined to avoid risks (i.e., to submit bids that might yield negative payoffs).

2 Preliminaries

Throughout the paper, bold case letters denote column vectors. Given a vector y, its i-th component is denoted by yi. The set {1, . . . , x} is denoted by [x], and ∆X is the |X|- dimensional simplex over the discrete set X.

Sponsored search framework 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 vi, representing their valuation on the item which is being sold. The vector of types is denoted as v = (v1, . . . , vn). Each bidder i belongs to a group from a finite set of possible groups G. The function g : [n] → G maps bidders to their group, that is, we write g(i) to denote the group to which bidder i belongs. We assume that bidders may belong to one of 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 Ih and by Iℓ. We make the assumption that |Ih| ≥ m and |Iℓ| ≥ m. This assumption is reasonable in the context of large Internet advertising markets. As it is customary in the literature, we use the model of separable click probabilities (see, e.g., [Edelman et al., 2007; Varian, 2007]), in which each slot j is associated with a clickthrough rate αj,g(i) for group g(i). We assume that, for each group w ∈ G, α1,w ≥ α2,w ≥ . . . ≥ αm,w, and without loss of generality we take n = m. Group-specific clickthrough rates can model, for example, cases in which different groups of advertisers mainly resort to different media types. Finally, each group w ∈ G is associated with a quality factor γw ∈ [0, 1], which reflects the clickability of ads from bidders belonging to group w. For example, ads coming from advertisers in the majority group may have higher clickability than ads from advertisers in the minority groups because of differences in the available budgets to develop the campaigns. Quality factors are private knowledge of the advertising platform, and not known by the bidders. 4

GSP auction A mechanism elicits a bid bi ∈ R≥0 for each bidder i, which is interpreted as a type declaration, and computes an outcome as well as a price pi(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 pi in place of π(b, γ, j), ν(b, γ, i), and pi(b, γ), respectively. The value perceived by bidder i when they are allocated ν(i) is αν(i),g(i)γg(i)vi, and their utility is ui(b, v, γ) := αν(i),g(i)γg(i)vi - pi. We focus on a family of mechanisms derived from the Generalized Second Price (GSP) auction [Varian, 2007]. 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)bi not yet assigned (breaking ties arbitrarily).

4 Our results hold also in the case of advertiser-dependent clickability, because that does not alter the relative ordering of items.

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 bn+1 = 0. 5 The mechanism is Individually Rational (IR) if, for each bidder i ∈ I, ui(b, v, γ) ≥ 0, for all b, v, and γ. The mechanism is Individually Rational at the Equilibrium (IRE) if it is IR at the equilibrium bid vectors.

Online Bayesian framework The n bidders participate in a series of GSP auctions. At each iteration t, each bidder i observes a valuation vt i for the item being sold at time t. Let Vi be the finite set of types of bidder i. The vector of types vt = (vt1 , . . . , vtn ) 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]Vi. Moreover, at each t, a vector of quality factors γ t ∈ [0, 1]|G| is drawn from a (possibly correlated) distribution G. Each bidder i has an arbitrary finite set of available bids Bi ⊆ R≥0, with ¯Bi := maxBi and ¯Bi ≥ supVi. Moreover, we denote by B := ×i∈[n]Bi the set of all possible joint bid profiles. A bidding strategy σi for bidder i is a (possibly randomized) mapping from their types Vi to their available bids Bi. We represent such strategies as a |Vi| × |Bi| right stochastic matrix in which each row specifies a well-defined probability distribution over bids: bidder i's strategy space is Σi := {σi ∈ R|Vi|×|Bi| ≥0 : σi1 = 1}. 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

At each iteration t, bidder i places bids according to a bidding strategy σt i ∈ Σi. In particular, bidder i observes its own type vt i , and then submits a bid bti ∼ σt i [vt i ]. Then, bidder i experiences a reward which we define as a function uti : Bi →R. The utility function uti observed at time t implicitly depends on the realized vector of bids bt-i , and quality factors γ t , and it is such that, for each possible bid b ∈ Bi, uti (b) := αtj,g(i)γ tg(i) vt i - pi((b, bt-i ), γ), with j = ν((b, bt-i ), γ t , i).

Regret and equilibria Given a sequence of decisions (b1i , . . . , bTi ) up to time T, the external regret of bidder i in type vi is how much they regret not having played the best fixed action in hindsight at each iteration in which they observed type vi. Formally, the regret experienced by bidder i under a certain type vi ∈ Vi is

5 Alternatively, we could charge bidder π(j) with the threshold price, which is the smallest effective bid pT i that guarantees them the same slot. Observe that pi ≤ pT i since the next highest bidder on j is not necessarily π(j +1) if the bidders have different quality factors.

6 Given a matrix M, we denote by M[i] its i-th row vector, and by M[i, j] the entry in position (i, j).

Then, the cumulative external regret of bidder i at time T is RT i := ∑vi∈Vi RT vi . Let (bt )Tt=1 be the sequence of decisions made by the bidders up to time T. Then, the empirical frequency of play ¯σT ∈ ∆V×B obtained from the realized sequence of types (vt )Tt=1 , and from the sequence of play (bt )Tt=1 is such that, for every (v, b) ∈ V ×B:

If each bidder i plays so as to obtain a regret RT 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 (BCCE) [Caragiannis et al., 2015; Hartline et al., 2015].We denote by Σ∗ ⊆ Σ the set of all Bayesian coarse correlated equilibria of the game.

3 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.

Preliminary definitions Consider an arbitrary stage t of the repeated auctions process (dependence on t will be omitted when clear from the context). For each group w ∈ G, let ALGw(b) := ∑i∈Iw γwαν(i),wbi be the value obtained by group w via a generic mechanism with allocation rule ν, on bid vector b. Since G = {h, ℓ}, the overall value is ALG(b) = ALGh(b) + ALGℓ(b). Moreover, given a set of slots J ′ ⊆ [m] assigned to group w ∈ G, we define

where J ′ [j] denotes the slot with the j-th click-through rate among slots in J ′ , and Iw[j] is the bidder belonging to Iw with the j-th effective bid in decreasing order (e.g., Ih(1) is the bidder of group h with the highest effective bid). Intuitively, ALGw(J ′ , b) is the maximum value attainable by group w when it is allocated J ′ and the bid vector is b.

β-EF1 mechanism The first mechanism that we describe employs a fair division scheme that guarantees the following notion of group fairness.

Definition 1. (Group β-EF1 fairness) Let β := ξℓ/ξh, with ξh, ξℓ ∈ N+, ξh ≥ ξℓ, and ξh + ξℓ ≤ m. We say that an allocation is group β envy-free up to one good (β-EF1 fair) for β ≤ 1 and bid profile b if, for each pair of groups h, ℓ ∈ G, there exists one item jh ∈ Jℓ such that ALGh(Jh, b) ≥ β ALGh(Jℓ \ {jh}, b).

We fix ξℓ and ξh to be the smallest integers such that β = ξℓ/ξh. 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 [2017]. 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 ∈ Jh to position at most ⌈(1 + β)j⌉ - 1. For more details on how this fair division scheme is implemented see the extended version of the paper. We observe that a round robin procedure guarantees group EF1 even when the number of groups is |G| > 2. The reason is that, for any pair w,w′ ∈ G, and positions j ∈ [|Jw|], j ′ ∈ [|Jw′ |], with j ≤ j ′ , it holds αJw[j],w ≥ αJw′ [j ′ ],w. Moreover, it is possible to show that a round robin procedure also guarantees group β-EF1 with respect to valuations (proofs can be found in the extended version of the paper).

Theorem 1. Given a bid profile b, the allocation computed by the composite mechanism is β-EF1 fair with respect to the valuation profile v. In particular, given the allocation of slots to the two groups Jh, Jℓ, for each pair of groups h, ℓ ∈ G, there exists one item j ∈ Jℓ such that ALGh(Jh, v) ≥ β ALGh(Jℓ \ {j}, v).

Intuitively, this is because the β-EF1 mechanism computes Jh, Jℓ without employing the reported bid profile, which is used only to determine the per-group ranking.

β-EFX mechanism The second notion of fairness which we consider is group β-EFX fairness.

Definition 2. (Group β-EFX fairness) An allocation is group β-envy free up to any good (β-EFX fair) for β ≤ 1 and bid profile b if, for each pair of groups h, ℓ ∈ G, and for each item jh ∈ Jℓ, it holds ALGh(Jh, b) ≥ β ALGh(Jℓ \ {jh}, b).

A group β-EFX fair division scheme can be obtained through a "group version" of the envy-cycle elimination algorithm by Lipton et al. [2004]. In particular, we propose the Group Envy-Cycle-Elimination algorithm (GECE). The GECE algorithm can be summarized as follows: denote by Jh and Jℓ the set of slots assigned, respectively, to group h and ℓ. We say that group h envies group ℓ if ALGh(Jh, b) < βALGh(Jℓ, b). Initially, all the slots are not assigned, that is, Jh = 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 ℓ. In the following theorem, we prove that the GECE algorithm is guaranteed to obtain a β-EFX allocation.

Theorem 2. The allocation computed by the group envycycle-elimination (GECE) algorithm is group β-EFX fair.

It is possible to show that a variation of GECE yields a group EFX fair allocation (i.e., β-EFX with β = 1) even with more than 2 groups.

Corollary 1. The allocation computed by the k-group envycycle-elimination (k-GECE) algorithm is group EFX.

4 Efficiency and Budget Balance

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 pG i and by pC 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. Observe that the pricing rule does not exclude positive transfers to the advertisers.

Now, let us first define an appropriate notion of budget balance for a composite mechanism which assigns a payment pC i to bidder i ∈ I, with respect to the GSP mechanism. Let pG := ∑i∈I pG i , and pC := ∑i∈I pC i .

Definition 3. A composite mechanism is α-budget balanced, for α ≥ 0, if pG - pC ≤ α pG .

An α-budget balanced mechanism is therefore able to cover via the GSP payments at least an α fraction of the compensations given to the bidders by the composite mechanisms.

Let ALG G (b) and ALG C (b) be, respectively, the value of the GSP mechanism, and of the fair composite mechanism on an arbitrary bid vector b. Moreover, we use the following two assumptions in the analysis of the composite mechanisms.

Assumption 1. The value of the minority group increases after the application of the composite mechanism, i.e., ALG C ℓ (b) ≥ ALG G ℓ (b).

Assumption 2. The first slot is assigned by GSP to Ih(1), i.e., the first bidder of group h.

Assumption 1 is natural since the basic goal of the proposed mechanisms would be to make the minority group better off with respect to the GSP case. Assumption 2 only requires that the advertiser with the highest bid belongs to the majority group. This is natural, for example, in settings where groups have different economic power. First, we provide efficiency and budget balance results for the β-Fair GSP mechanism.

Theorem 3. The β-Fair 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) ≥ ALG G (b)/(1 + β).

Theorem 4. The β-Fair GSP mechanism is 2-budget balance.

This result does not rule out that the mechanismmay suffer a net loss. However, such loss is bounded by a small constant (see Section 6 for an empirical evaluation of such loss).

Second, 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 (2). Then, we have the following.

Theorem 5. 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 fair division scheme. Formally,

Theorem 6. The GSP-EFX mechanism is 4-budget balance.

Remark 1. Given a number of groups k > 2 and β = 1, Theorem 3 and Theorem 5 can be extended to show that the group EF1 (resp., group EFX) mechanism achieves a value that is at least a 1/2k fraction (resp., a fraction 1/3k) of the value of GSP.

5 Price of Composition

Equipped with the results from Section 4 we can study the performance of the proposed mechanisms at equilibrium. We study 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 for bids b, valuations v ∈ V, and quality factors γ is

Given an equilibrium strategy σ ∈ Σ∗ in an incompleteinformation game, its social welfare is evaluated by comparing it to the expected ex-post social welfare of the GSP mechanism, which we denote by Ev,γ[SW G (v, γ)]. In particular, we can define the following worst-case ratio.

Definition 4. The price of composition (PoC) of a composite mechanism C is defined as

By the definition of the composite mechanisms, their socialwelfare is at most equal to the social welfare of the GSP mechanism (see Section 4), i.e., POC ∈ [0, 1]. Moreover, bounding the worst case POC automatically yields a POC/2 guarantee on the price of total anarchy [Blum and Mansour, 2007]. This is because SW G (v, γ) ≥ SW ∗ (v, γ)/2, where SW ∗ is the optimal social welfare with valuations v. 7

In order to characterize the PoC of our mechanisms, we introduce a natural smoothness condition for composite mechanisms, which is a generalization of the notion of semismoothness by Lucier and Paes Leme [2011]. 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 GSPEFX) 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 strategy σ ∈ Σ, v ∈ V, and γ,

7 The value of the GSP solution for the Ad-Types problem with group-specific CTRs is at least 1/2 of the optimal solution provided by maximum weighted matching [Colini-Baldeschi et al., 2020].

In this setting, we make the additional assumption that bidders are conservative and, therefore, they do not overbid. This is in line with previous works studying the price of anarchy of auctions with conservative bidders (see, e.g., [Leme and Tardos, 2010; Christodoulou et al., 2016; Feldman et al., 2013]). 8 Under this assumption, the following holds.

Lemma 1. The β-Fair GSP mechanism is (1/2, (1+β))- semi-smooth, and the GSP-EFX mechanism is (1/2, 3)-semismooth. Both mechanisms are individually rational at the equilibrium.

By the fact that (λ, µ)-semi smoothness implies a λ 1+µ POC, we characterize the POC of the mechanisms as follows.

Theorem 7. The price of composition with uncertainty of βFair GSP is POC = (2(2 + β))-1 .

This result shows that, even if the bidders are self-interested (i.e., they take decisions so as to minimize their own individual regret), our composite mechanism can guarantee group fairness, as well as convergence to a good equilibrium point. Analogously, it is possible to prove the following for GSPEFX:

Theorem 8. The price of composition with uncertainty of GSP-EFX is POC = 1/8.

6 Experimental Evaluation

We experimentally evaluate 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 Bi. We focus on the partial-information setting, in which, at each time instant t, each bidder observes only the reward uti (bti ) associated to Expected overall SW at equilibrium

8 Our bounds on PoC can be adapted with minor modifications to the case in which bidders are δ-conservative [Bhawalkar and Roughgarden, 2011], i.e., bi ≤ δvi, ∀i. In particular, all price of composition factors are multiplied by an additional δ factor.

4.8

4.6

4.4

4.2

SW OPT

SW G

SW C

1

2

3

4

5

6

7

8

9

5

4

3

2

1

0

SW OPT

h

SW G

h

SW C

h

SW OPT

ℓ

SW G

ℓ

SW C

ℓ

1

2

3

4

5

6

7

8

9

Values of ξh Values of ξh

its choice bti ∈ Bi. This is in line with what happens in realworld sponsored search auctions, where advertisers do not observe competing bids (i.e., they cannot compute a counterfactual utility uti (b) for each b ∈ Bi), but can only observe the outcome associated to their decision bti . We instantiate an external-regret minimizer Ri,v for each bidder i and v ∈ Vi. In practice, we use the EXP3 algorithm by [Auer et al., 2002] 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 vt ∈ Vi and selects bti ∈ Bi according to Ri,vi . Then, after utility uti (bti ) is observed, only Ri,vi is updated. This simple procedure guarantees that lim supT→∞ RT 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., 2015, 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 = 104 auctions. For each i, we set Vi = {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) = F1(v1) · . . . · Fn(vn), with Fi ∈ ∆Vi for each i. Then, for each i ∈ Ih (i.e., advertiser i belongs to the majority group), we artificially set value distributions to be such that Fi(1) = 1, and Fi(v) = 0 for each v ∈ Vi \ {1}. Each bidder i ∈ Iℓ has a value distribution Fi built by normalizing the distribution of bids observed from real-world bidding data of a large Internet advertising company. We use bids as a proxy for true valuations of advertisers. Discount curves are computed by averaging and normalizing in [0, 1] real-world

Expected SWh and SWℓ at equilibrium 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 advertisers behaving so as to minimize their regret, and 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-(Top-Left), and Figure 1-(Top-Right) 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 1), 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-(Top-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-(Top-Right) reports the per-group social welfare at equilibrium. Finally, Figure 1-(Bottom) describes the fraction of the revenue which is lost due to compensation for advertisers as defined in Equation (2). We observe that, in practice, the fraction of the GSP prices used for compensation significantly lower than the worst case bound of Theorem 4. 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 pG 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.

7 Discussion and FutureWorks

We proposed a class of composite mechanisms constructed through the combination of GSP with different fair division schemes. We show that these composite mechanisms yield group fairness guarantees for advertisers, and we characterized the costs which the platform has to incur. In the future, it would be interesting to study fairness guarantees in the space of valuations, and in the space of utilities. We already provided some preliminary results going in this direction (Theorem 1). Extending this to EFX presents non-trivial additional challenges, such as showing that there exists a monotone version of GECE. We leave this as a future research direction.

Acknowledgements

The Sapienza team was supported by the ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mechanism DesignResearch inOnlineMarkets", theMIURPRINproject ALGADIMAR "Algorithms, Games, and Digital Markets", and the Meta Research grant on "Fairness and Mechanism Design".