Envy-Free Sponsored Search Auctions with Budgets

1 Introduction

Sponsored search advertising via auctions is one of the most popular ways of Internet monetization, which account for a major part of search engines' revenue. Consequently, design and analysis of such auctions has drawn a lot of attention in artificial intelligence and electronic commerce. For example, in the pioneering work by Varian [2007] and Edelman et al. [2007], the "generalized second price" (GSP) auctions, used by Google, have been modeled as position auctions having several desirable properties. Variants of this model have been extensively studied from both theoretical and practical points of view [Kuminov and Tennenholtz, 2009; Graepel et al., 2010; He et al., 2013].

In practice, budget constraints are given by bidders to specify their monetary affordability. The issues arising from budgets have received some attention in prior study on auction design [Ashlagi et al., 2010; Dobzinski et al., 2012]. It has been observed that, in various settings, the imposition of bidders' budgets changes the problems dramatically. To see this change in sponsored search, we point out that an advertiser's utility function, which is the difference between her valuation for the ad slot and the money she pays, is no longer a continuous function of her payment.

Fairness is one of the most important criteria in auction design. In economic theory, fairness can be explained as a free market without discriminatory pricing. More precisely, buyers should be allocated their most desired items under their budget constraints. Unfortunately, auctions currently in use may produce unfair outcomes for budget-constrained bidders (e.g., simultaneous ascending auctions [Nisan et al., 2009]). It has been pointed out that the lack of fairness may lead to worse customer experience and fewer subsequent purchases from the firm [Anderson and Simester, 2010].

In this paper, we adopt a concept of fairness called envyfreeness in auctions. Envy-freeness is a classical criterion for analyzing mechanisms [Foley, 1967], which has been widely studied in artificial intelligence [Bouveret and Lang, 2005; Othman and Sandholm, 2010]. An outcome is envy-free if no buyer can improve her utility via exchanging her allocated items and payment with others. In sponsored search, envyfreeness is equivalent to the above explanation of fairness in a free market.

Our key objective is to design "optimal" envy-free auctions with respect to two classical objective functions in auction theory - social welfare and revenue. To this end, we characterize envy-freeness with budget-constrained bidders by proving several elementary properties including consistency, monotonicity and transitivity for all envy-free outcomes. Based on this characterization, we have designed an envy-free auction which is both social-optimal (maximizing social welfare) and bidder-optimal (maximizing every bidder's utility) for a wide class of bidder types. More generally, for all bidder types, we devise two polynomial-time approximation schemes (PTASs) to maximize social welfare or revenue where the notion of envy-freeness has been relaxed slightly. Furthermore, we present similar PTASs for designing optimal randomized auctions.

Our work is closely related to existing results on designing envy-free auctions for budget-constrained bidders. We review them briefly and identify their differences from our work.

Ashlagi et al. [2010] first investigated the effect of budget constraints in designing sponsored search auctions. They showed that a modification of the Generalized English Auction introduced by Edelman et al. [2007] is envy-free and Pareto optimal (a weaker condition than social welfare maximizing). However, the mechanism they developed cannot provide any guarantee for social welfare or revenue.

Aggarwal et al. [2009] and D¨utting et al. [2011] developed more expressive auctions with discontinuous utilities including the case with budgets. They presented envy-free and bidder-optimal mechanisms for matching markets that is a more general setting than sponsored search. Unfortunately, no bidder-optimal auction always maximizes social welfare even in the context of sponsored search (see Example 3.7).

Feldman et al. [2012] first studied the revenue maximization problem in designing envy-free auctions for budgetconstrained bidders. However they worked in a multi-unit setting with identical items and multi-demand buyers.

Devanur et al. [2013] analyzed clinching auctions introduced by Ausubel [2004] in the context of sponsored search. They showed that, when all bidders have a common budget, the clinching auction is envy-free and approximates optimal social welfare and revenue within a constant factor. Instead, our results aim at optimizing social welfare and revenue without the common budget assumption.

Revenue maximization in envy-free auctions has been extensively studied in a more general setting. Guruswami et al. [2005] showed that it is APX-hard to maximize the revenue among envy-free outcomes in matching markets. After that, both positive [Chen and Deng, 2010] and negative results [Briest, 2008] have been proved for this problem without budget constraints. Relaxed notions of envy-freeness have been also used in solving several problems (e.g., [Cohler et al., 2011], [Brˆanzei and Miltersen, 2013]).

Much effort has been made to design incentive compatible auctions for bidders with budgets. Dobzinski et al. [2012] generalized clinching auctions to multi unit environment with budget constraints. This result was also extended to ordinal environments including sponsored search scenario in [Goel et al., 2012]. For multiple keyword sponsored search auctions with budgets, Colini-Baldeshi et al. [2012] developed a randomized incentive compatible and Pareto optimal mechanism. Dobzinski and Paes Leme [2014] designed truthful auctions to approximate "liquid welfare" within a constant factor in multi-unit environments. But these mechanisms may produce unfair outcomes for budget-constrained bidders.

When considering social welfare or revenue maximization, Incentive Compatibility and Envy-freeness are not compatible in several settings with budgets (see [Feldman et al., 2012] and references therein). Example 3.7 shows that no truthful mechanism can always output social-optimal envyfree outcomes. Therefore, in this paper we forgo truthfulness and concentrate on envy-free outcomes.

2 Preliminaries

In sponsored search, m advertisement positions are allocated to n bidders. Let N = {1, . . . , n} and M = {1, . . . ,m} denote the set of bidders and positions respectively. Each position j ∈ M is characterized by a quality number qj, representing the number of clicks it could provide. This model is able to describe the setting where the value of the click may depend on the position it appears. We assume positions are indexed in decreasing order of qj, i.e. q1 ≥ . . . ≥ qm. Each bidder i ∈ N is associated with a pair (vi,Bi), where vi represents her monetary valuation per click and Bi is the maximum payment she could afford. Note that bidder i is only interested in getting a single position, which is also called unit-demand. So bidder i's valuation for position j is viqj. We assume all vi, Bi and qj are integers. We also use I = (v,B, q) to denote an instance of a sponsored search auction, where v = (v1, . . . , vn), B = (B1, . . . ,Bn) and q = (q1, . . . , qm). An outcome of an auction can be represented by an allocation vector x = (x1, . . . , xn) and a payment vector p = (p1, . . . , pn), where xi denotes the expected number of clicks allocated to bidder i and pi is the corresponding payment. In deterministic auctions, an allocation vector x can be viewed as a matching between bidders and positions. That is, if bidder i is matched to position j then xi = qj. In randomized auctions, a bidder may be allocated a distribution over positions. More precisely, for each bidder i and position j, rij is the probability that i gets j such that ∑i∈N rij ≤ 1 and ∑j∈M rij ≤ 1. Thus, the allocation xi = ∑j∈M rijqj is the expected number of clicks that bidder i gets from the allocated distribution.

In this paper, we restrict our attention to outcomes (x, p) with the following properties: for all bidder i ∈ N, pi ≤ Bi (budget feasible), xivi - pi ≥ 0 (individual rational) and pi ≥ 0 (no positive transfer). So we omit the word "feasible" for brevity in the remainder of this paper.

To formalize fairness, we adopt the following notion of envy-freeness. A set of bidders S ⊆ N is said to be envyfree in an outcome (x, p), if for any pair of bidders, i, j ∈ S, i does not envy j, i.e., pj ≤ Bi implies xivi-pi ≥ xjvi-pj. An outcome is envy-free if all bidders are envy-free in it. Moreover, an auction is envy-free if its outcome for any instance is envy-free. In order to get approximation schemes, we also use a weaker notion of envy-freeness called relaxed ϵ-envy-freeness. An outcome (x, p) is said to be relaxed ϵenvy-free if it is feasible and for any pair of bidders i, j ∈ N such that pj ≤ Bi - ϵ, xivi - pi ≥ xjvi - pj - ϵ. We consider two classical objective functions - social welfare, and revenue. Given an outcome (x, p), the social welfare of the outcome is ∑i∈N vixi and the revenue is ∑i∈N pi. We say that an envy-free auction A is social-optimal (or revenueoptimal) if for any instance, no envy-free auction can produce an outcome with higher social welfare (or revenue) than A. Note that our social-optimal envy-free auction may obtain lower social welfare than the optimal social welfare without envy-freeness.

3 Deterministic Auctions

In this section, we describe our approach to designing socialoptimal or revenue-optimal deterministic auctions for budgetconstrained bidders. Before presenting our auctions, we show several properties of envy-free outcomes.

Lemma 3.1 (Consistency). For any envy-free outcome, the order of the allocation vector should be consistent with the order of the payment vector. That is, for any two bidders i and j, xi > xj ⇔ pi > pj and xi = xj ⇔ pi = pj .

Proof. We only show the proof for xi > xj ⇒ pi > pj ; similar proofs can be derived for the other three cases. Assume the opposite that, there exists two bidders i and j such that xi > xj and pi < pj. It is easy to see j will envy i since pi < pj ≤ Bj by budget feasibility.

Intuitively, consistency means no bidder can get a better position than another without paying more. Furthermore, the bidders with the same budget can be characterized below.

Lemma 3.2 (Monotonicity). Suppose bidders i and j have the same budget and i has higher value than j. Then i must get a better position and pay more than j in any envy-free outcome. That is, vi ≥ vj implies xi ≥ xj and pi ≥ pj.

Proof. Recall that the envy-free conditions for i and j are vixi-pi ≥ vixj-pj and vjxj-pj ≥ vjxi-pi. By summing these two inequalities, we have (vi -vj)(xi -xj) ≥ 0. Since vi ≥ vj , we have xi ≥ xj . Furthermore pi ≥ pj follows from the consistency (Lemma 3.1).

Although the above lemma reveals the structures of envyfree outcomes for bidders with the same budget, we need the following transitivity of envy-freeness to characterize bidders with different budgets.

Lemma 3.3 (Transitivity). Suppose that for three bidders i, j and k, Bi = Bj and vi ≥ vj . If xk < xj or (xk = xj and vk ≤ vj), then {i, j} and {j, k} are envy-free implies {i, k} is envy-free.

Proof. We first prove that i does not envy k. By consistency and monotonicity, we have xi ≥ xj ≥ xk and pi ≥ pj ≥ pk. Due to the assumption that {j, k} is envy-free, we have vj(xj-xk) ≥ pj-pk by rearranging the terms. Since vi ≥ vj and xj ≥ xk, we get vi(xj - xk) ≥ vj(xj - xk) ≥ pj - pk. So the utility of bidder i is vixi-pi ≥ vixj -pj ≥ vixk-pk. Therefore, i does not envy k. It remains to show k does not envy i. We consider two cases. (a) pj > Bk, then we have pi ≥ pj > Bk. So the payment of bidder i exceeds bidder k's budget and the envy-freeness follows. (b) pj ≤ Bk: We first show vj ≥ vk in this case. By rearranging the terms in the envy-free conditions for j and k, we get vk(xj - xk) ≤ pj - pk ≤ vj(xj - xk). If xj > xk, we have vj ≥ vk by the above inequality. Otherwise vj ≥ vk follows from the assumption that xj = xk and vj ≥ vk. Then we have vk(xj - xi) ≥ vj(xj - xi) ≥ pj - pi since vk ≤ vj, xj ≤ xi and vjxj -pj ≥ vjxi -pi. By using the envy-freeness between j and k and rearranging the terms in the above inequalities, we have vkxk -pk ≥ vkxj -pj ≥ vkxi -pi. This shows that k does not envy i.

The next lemma shows that, in envy-free outcomes, we can restrict our attention to integer payments.

Lemma 3.4. Suppose (x, p) is an envy-free outcome for budget constrained bidders. Then there exists a non-negative integer price vector p′ such that (x, p′ ) is also an envy-free outcome and p′i ≥ pi for all bidder i.

Proof. Recall that we assume all vi, Bi and qj are integers. Given any outcome (x, p), let p′i = ⌈pi⌉, for any i ∈ N. It is easy to check that (x, p′ ) still satisfies all constraints and must be an envy-free outcome.

3.1 Proportional Bidder Types

Here we use the properties of envy-free outcomes to design a social-optimal envy-free auction for proportional bidders. The bidders are called proportional if for any bidders i, j ∈ N, Bi > Bj implies vi ≥ vj. Thus, we can order the bidders such that i < j implies Bi ≥ Bj and vi ≥ vj. For convenience, we define qj = 0 for all j > m and Bn+1 = -1.

Lemma 3.5. In any envy-free outcome with proportional bidders, bidder i's minimum payment for getting position j is

Proof. Given any envy free outcome (x, p), we have for any bidder i, pi ≥ min{Bi+1 + 1, pi+1 + vi+1(xi - xi+1)} since vi+1xi+1 - pi+1 ≥ vi+1xi - pi if pi ≤ Bi+1. The lemma follows by using the above rule from bidder n to bidder 1 inductively. For the base case, we have pn ≥ 0. For the inductive step, we have

The equality comes from ∑k-2 ℓ=i vℓ+1(xℓ - xℓ+1) = 0 when k = i+1. The last inequality is from setting xℓ = qj+ℓ-i for all ℓ ≥ j that minimizes ∑k-2 ℓ=i vℓ+1(xℓ -xℓ+1).

Our social-optimal auction for proportional bidders can be described as Auction 1. Besides social optimality, we are able to show that Auction 1 is also bidder-optimal. That is for any instance I, no bidder can improve her utility vixi -pi in any envy-free outcome.

Theorem 3.6. For instances with proportional bidders, Auction 1 is envy-free, bidder-optimal and social-optimal.

Proof. First, we show the outcome of Auction 1 is envy-free. For any two bidders i and i′ such that i < i′ , we use j and j ′ to denote the position they get in the outcome of Auction 1. It is not hard to see that j < j ′ and j-i ≤ j ′ -i′ from the process of the auction. So it suffices to prove (a) viqj-pi ≥ viqj ′-pi′

Input: An instance I = (v, B, q) Output: An outcome (x, p) Initialize x = 0, p = 0 and i = 1; for Position j = 1 to m do if pmin ij ≤ Bi then Set xi = qj and pi = pmin ij ; Consider next bidder by increasing i by one;

and (b) vi′qj ′-pi′ ≥ vi′qj-pi if pi ≤ Bi′ . For the inequality (a), let k > i′ be the bidder such that pi′ = pmin ij (k). So viqj -pi is at least

For the inequality (b), since pi ≤ Bi′ , i′ - i = j ′ - j. This is because for any bidder ℓ between i and i′ , we have pℓ ≤ pi ≤ Bi′ ≤ Bℓ when Auction 1 tries to allocate position j + ℓ - i to bidder ℓ. Then by a simple calculation, we can show that pi equals to pi′ + ∑i′-1 k=i vk+1(qk+j-i - qk+j-i+1) ≥ pi′ + vi′ (qj -qj ′ ). Envy-freeness follows by rearranging the terms. Next we show Auction 1 is social-optimal. Suppose there exists an envy-free outcome (x′ , p′ ) such that some bidder can get a better position than (x, p) outputted by Auction 1. Let i be the first bidder (with the smallest index) who gets a better position. Let j be the position that i gets from (x′ , p′ ). By the process of Auction 1, for all position j ′ such that qj ′ > qj, either j ′ is allocated to a bidder preceding i or pmin ij ′ > Bi. Thus, there must exist a bidder i′ who gets a position j ′ such that qj ′ < qj in x′ and i′ < i, otherwise i cannot get a better position. So vi′ ≥ vi and Bi′ ≥ Bi by the order of bidders. Since (x′ , p′ ) is envy-free, we have vi′x′i′ - p′i′ ≥ vi′x′i - p′i and vix′i - p′i ≥ vix′i′ - p′i′ since j ′ > j implies p′i ≥ p′i′ by Lemma 3.1 (Consistency). By summing the above two inequalities, we have (vi′ - vi)(x′i′ - x′i ) ≥ 0. Since x′i′ = qj ′ < qj = x′i , we must have vi′ ≤ vi. Combine this with vi′ ≥ vi, we have vi = vi′ . Thus we can modify (x′ , p′ ) by swapping the allocation and payment of bidder i and i′ without changing the social welfare. By repeating this modification, we get Auction 1 is social-optimal.

Finally, we show Auction 1 is bidder-optimal. Assume to the contrary that there exists another envy-free outcome where some bidder can improve her utility. Let bidder i be the first bidder who gets higher utility from (x′ , p′ ) than that from (x, p), the outcome of Auction 1. Let j and j ′ be the positions that i gets from (x, p) and (x′ , p′ ) respectively. Case 1: j ′ ≥ j. By Lemma 3.5, p′i ≥ pmin ij ′ . So it suffices to show that viqj -pi ≥ viqj ′ -pmin ij ′ . For any k > i, bidder i's utility viqj -pi is at least

By taking the minimum over all k > i, we prove viqj - pi ≥ viqj ′ - pmin ij ′ . Case 2: j ′ < j. Let bidder i′ be the bidder who gets j ′ in (x, p). By the arguments in the previous paragraph, we have i′ < i and vi = vi′ . Let ui and u′i denote the utility of bidder i in the outcome (x, p) and (x′ , p′ ). Since i is the first bidder who improves her utility, we have u′i′ ≤ ui′ = ui < u′i which contradicts the envy-freeness of (x′ , p′ ). Therefore Auction 1 is also bidder-optimal.

Finally, we present an example to show if the bidders are not proportional, no bidder-optimal auction always maximizes social welfare.

Example 3.7. Consider four bidders with v1 = 20, v2 = 40, v3 = 30, v4 = 5, B1 = 2000 and B2 = B3 = B4 = 1400. There are also six positions with qualities q1 = 100, q2 = 50, q3 = 49, q4 = 48, q5 = 46 and q6 = 1. For convenience, we use B that equals 1400 to denote the budget of bidder 2. In order to compute the maximum social welfare, we consider two cases: Case 1: p1 ≤ B. By using Auction 1, we are able to show that the optimal allocation is x1 = q4, x2 = q2, x3 = q3 and x4 = q5, which gives the social welfare 4660. Case 2: p1 > B. Suppose the allocation is x, we can show that there exists a price vector p such that (x, p) is an envy-free outcome if and only if (i) v3(x2 -x3)+v4(x3 -x4) ≤ B;(ii) v1(x1 - x2) + v2(x2 - x3) + v3(x3 - x4) + v4x4 > B; (iii) x1 ≥ x2 ≥ x3 ≥ x4. By using these conditions, we can solve the social welfare maximization problem by simple calculations. As a result, the optimal social welfare is 5475 with the allocation x1 = q1, x2 = q2, x3 = q3 and x4 = q6.

This example shows that there does not exist a bidderoptimal and social welfare maximizing auction. To see this, note that in Case 2 where social welfare is maximized, bidder 1 can get utility at most 20 · 100 - 1410 = 590 (otherwise bidder 2 will envy bidder 1). However, in Case 1, we can compute an envy-free price vector for the bidders p = (p1, p2, p3, p4) = (10, 60, 30, 0) such that (x, p) is an envy-free outcome, where (x1, x2, x3, x3) = (q4, q2, q3, q5). In this outcome, bidder 1 obtains utility 48 · 20-10 = 950 > 590. Hence, the social welfare maximizing outcome in this instance is not bidder-optimal. In fact, one can show that (x, p) is a bidder-optimal outcome for this instance. Similarly, it is easy to see bidder 1 can manipulate her budget or valuation to increase her own utility. That implies in this setting no truthful mechanism can always output social-optimal and envy-free outcomes.

3.2 All Bidder Types

In this section, we provide a polynomial-time approximation scheme (PTAS) for computing social-optimal or revenueoptimal deterministic envy-free auctions where the notion of envy-freeness has been relaxed slightly. More precisely, for any fixed parameter ϵ, our auction is a relaxed ϵB-envy-free and social-optimal auction that can be computed in time polynomial in n and m. The general idea of our PTAS can be described in four steps:

1. Partition the bidders into groups such that bidders with similar budget are in the same group.
2. Use Lemma 3.2 (Monotonicity) to characterize the structure of the bidders in the same group.
3. Use Lemma 3.3 (Transitivity) to establish the relations between different groups.
4. Compute the approximately-optimal envy-free auction via solving a dynamic programming.

For convenience, we say {i, k} is ϵ-envy-free when vixi - pi ≥ vixk-pk-ϵ if pk ≤ Bi and vkxk-pk ≥ vkxi-pi-ϵ if pi ≤ Bk and the outcome is feasible for bidder i and bidder k. Given an instance I = (v, B, q) and a parameter ϵ ∈ (0, 1), let W = {b | b = Bi for some bidder i or b is a multiple of ϵB/n at most B}. Clearly, the size of W is at most n/ϵ + n.

We describe the auction in detail as follows. First of all, we round the bidders' budgets down to a closest multiple of ϵB, that is Bi - ϵB ≤ B′i ≤ Bi. Then we solve the instance I ′ = (v,B′ , q) instead of I = (v,B, q). For I ′ , we partition the bidders into groups such that the bidders in the same group have the same budget. Clearly, the number of groups is at most 1/ϵ. For simplicity of presentation, we only present the auction as Auction 2 in which the bidders can be divided into two groups. It is straightforward to generalize the auction to many groups. After that, we sort bidders in each group with decreasing order of their valuations. We use G1 and G2 to denote bidders in these two groups and n1 and n2 be the size of G1 and G2 respectively. Let R[i1, i2; j1, j2;w1,w2] be the optimal social welfare we can get from the first iℓ bidders in each group ℓ when the iℓth bidder in group ℓ gets position jℓ by paying wℓ for all ℓ = 1, 2. For all iℓ = 0, . . . , nℓ, jℓ = 0, . . . ,m and wℓ ∈ [0,B] that is a multiple of ϵB/n, we compute R[i1, i2; j1, j2; w1, w2] in the following dynamic programming. Let bidder aℓ be the iℓth bidder in Gℓ for ℓ = 1, 2. So we have xaℓ = qjℓ and

Input: An instance I = (v, B, q) and a value ϵ ∈ (0, 1) Output: An outcome (x, p) B ← maxi∈N Bi; W ← {Bi}ni=1∪ {multiples of ϵB/n at most B}; Round Bi down to a multiple of ϵB for all i ∈ N; Partition N into groups such that bidders in the same group have the same rounded budget; /* We only present the auction for two groups. */ Sort bidders in each group with decreasing order of vi; nℓ ← the number of bidders in group ℓ; Initialize R[0] = 0; for i1 = 0 to n1 and i2 = 0 to n2 and i1i2 ̸= 0 do for j1 = 0 to m and j2 = 0 to m do for w1 ∈ W and w2 ∈ W in increasing order do aℓ ← the iℓth bidder in group ℓ with ℓ = 1, 2; xaℓ ← qj1 and paℓ ← wℓ; if (a1, a2) are ϵB/n-envy-free and j1 ̸= j2 then Compute R[i1, i2, j1, j2, w1, w2] by using (⋆); else R[i1, i2, j1, j2, w1, w2] = -∞;;

SW ← maxj1,j2,w1,w2 {R[n1, n2, j1, j2, w1, w2]}; Construct (x, p) by tracking back the computation of R;

paℓ = wℓ for all ℓ = 1, 2. If (a1, a2) are not ϵB n -envy-free or j1 = j2, R[i1, i2; j1, j2; w1, w2] = -∞.

Computation (⋆): If (a1, a2) are ϵB n -envy-free and j1 ̸= j2, consider two cases.

Case 1: xa1 < xa2 or (xa1 = xa2 and va1 < va2 ). We set R[i1, i2; j1, j2; w1, w2] = maxj<j1,w∈W {R[i1 - 1, i2; j, j2; w,w2] + qj1 va1 |(b, a1) are ϵB n -envy-free.} where b is the (i1 - 1)th bidder in G1 with xb = qj and pb = w.

Case 2: xa1 > xa2 or (xa1 = xa2 and va1 ≥ va2 ) We set R[i1, i2; j1, j2; w1, w2] = maxj<j2,w∈W {R[i1, i2 - 1; j1, j; w1,w] + qj2 va2 |(b, a2) are ϵB n -envy-free.} where b is the (i2 - 1)th bidder in G2 with xb = qj and pb = w.

At last, the optimal social welfare is

Moreover the outcome (x, p) can be derived by tracking back the computation of R. It is not hard to see the same dynamic programming can be used to compute optimal revenue by changing qj1 va1 to w1. So the outcome (x, p) is the output of our auction for the instance I. Note that Auction 2 can be generalized when the number of groups is more than 2. So when we mention Auction 2 in next theorems, we refer the general auction for any number of groups. We summarize the result in the following theorem.

Theorem 3.8. Given a parameter ϵ ∈ (0, 1), Auction 2 is a relaxed ϵB-envy-free and social-optimal auction. Moreover, the running time of the auction is O((n2m/ϵ)1/ϵ ).

Proof. We first show that the outcome (x, p) outputted by Auction 2 is relaxed ϵB-envy-free. Since B′i ≥ Bi - ϵB, it suffices to show for any bidder i, k, vixi-pi ≥ vixk-pk-ϵB if pk ≤ B′i by the definition of relaxed ϵB-envy-freeness. It follows from a slight modification of Lemma 3.3 (Transitivity) for ϵ-envy-free transitive: given the same assumption, if i and j are ϵ1-envy-free and j and k are ϵ2-envy-free, we also have j and k are (ϵ1 +ϵ2)-envy-free. This is because the bidders in each group are considered in decreasing order of vi and we check the ϵB/n-envy-freeness of the bidders that are considered consecutively in Auction 2.

Then we show Auction 2 is social-optimal. More specifically, no envy-free outcome can raise higher social welfare than the outcome of Auction 2. Given an envy-free outcome (x, p), we round pi up to p′i that is a value in W and round Bi down to B′i that is a multiple of ϵB for all bidder i ∈ N. It is not difficult to see that any pair of bidders are ϵB n -envy-free and p′i ≤ Bi. Hence the social welfare of (x, p′ ) is at most the social welfare of the outcomes outputted by Auction 2 by the optimality of the dynamic programming. So Auction 2 is social-optimal.

Finally, we estimate the running time of Auction 2. The total number of states in the dynamic programming is (nm(n/ϵ + n))1/ϵ and for each state we need O(nm/ϵ) to compute the entry. Therefore the overall running time is (n2m(1 + 1/ϵ))1+1/ϵ ≈ (n2m/ϵ)1/ϵ when ϵ is small.

Corollary 3.9. Given a parameter ϵ ∈ (0, 1), Auction 2 can be modified to a relaxed ϵB-envy-free and revenue-optimal auction with running time O((n2m/ϵ)1/ϵ ).

4 Randomized Auctions

In this section, we study envy-free randomized auctions and present a PTAS for computing optimal envy-free outcomes. Unlike the deterministic case, the allocation of a randomized mechanism can be any real numbers. We also need that the allocation vector x can be implemented by a distribution of deterministic allocation rules. Formally, this condition is called the majorization condition, studied in [Feldman et al., 2008; Goel et al., 2012]. That is, a randomized allocation can be implemented iff the allocation vector is weakly majorized by the quality vector, i.e. ∑ki=1 xi ≤ ∑ki=1 qi, for all k = 1, . . . ,min{n,m} where {x1, . . . , xn} are the bidders' allocations and sorted in decreasing order. Note that the allocations satisfying majorization condition form a convex set. However the set of all envy-free outcomes is not convex.

Example 4.1. Consider two bidders with (v1, B1) = (1, 100) and (v2, B2) = (2, 80) and one position with q1 = 100. Consider the following two outcomes x1 = x2 = 50, p1 = p2 = 50 and x′1 = 100, x′2 = 0, p′1 = 100, p′2 = 0. It is easy to check that both outcomes are envy-free. However there is no pricing vector p such that ( x+x′ 2 , p) is an envy-free outcome.

Although the set of feasible outcomes is not convex, we are able to show that the set of all envy-free outcomes can be represented by a union of n1/ϵ polytopes. Given an instance I = (v,B, q) and a parameter ϵ ∈ (0, 1), let W be the set of all multiples of ϵB that is at most B. We use d = 1/ϵ to denote |W| and {w1, . . . , wd} to denote the set W where the elements in W are ordered increasingly. For convenience, we add w0 = -1 into W. Then we partition the set of bidders into d groups {G1, . . . ,Gd} such that for all bidder i in Gℓ, pi ∈ (wℓ-1,wℓ]. We use ℓ(i) to denote index of the group that i belongs to. We observe that the proofs of Lemma 3.1 and Lemma 3.2 do not use any fact about deterministic auctions. So the lemmas also hold for randomized auctions. By monotonicity, the number of all possible partitions for envyfree outcomes is at most (nd) ≤ nd .

Given a partition G = {G1, . . . ,Gd}, we are able to sort the bidders such that i ≤ j implies pi ≥ pj. By consistency, we also have pi ≥ pj implies xi ≥ xj. That is the majorization condition can be represented by n linear inequalities given the partition G. Moreover, the relaxed envy-freeness can be expressed as vixi - pi ≥ vixj - pj if wℓ(j) ≤ Bi for all i, j ∈ N since pj ≤ Bi - ϵB implies wℓ(j) ≤ Bi. Note that the above conditions are also linear constraints given the partition G. So the set of all feasible envy-free outcomes can be represented by a polytope for a given partition. Let f(x, p) be an objective function of (x, p), which is either the social welfare ∑i vixi or the revenue ∑i pi. Given the partition G, we can compute the optimal objective via solving the following linear programming in polynomial time.

Theorem 4.2. Given an instance I = (v,B, q) and a parameter ϵ ∈ (0, 1), the randomized auction obtained via solving the above linear programming is a relaxed ϵB-envy-free and social-optimal (or revenue-optimal) auction running in time polynomial in m, 1/ϵ and n1/ϵ .

Proof. By the optimality of linear programming, it suffices to show two claims. First, the solution computed by the linear program is relaxed ϵB-envy-free. Second, any envy-free outcome is a feasible outcome in the linear program. The first claim follows from the definition of relaxed ϵB-envyfreeness. For the second one, note that an envy-free outcome (x, p) is also relaxed envy-free. So the claim follows by dividing the bidders into groups according to p.

5 Conclusion

In this paper, we study the social welfare and revenue maximization problems in envy-free sponsored search auctions, for budget-constrained bidders. Our main contribution is a general approach to devise PTASs for maximizing social welfare and revenue in both deterministic and randomized settings. In addition, we provide an alternative understanding of the effects of budgets on envy-free auction design. There are several promising directions for future work. One of them is to generalize our auctions to more general settings, for instance matching markets and combinatorial auctions. Another promising direction is to consider fairness issues in some other settings such as TV advertising or labor markets.

Acknowledgment

We thank Paul W. Goldberg and the anonymous IJCAI reviewers for their useful comments. Jinshan Zhang is supported by EPSRC project EP/K01000X/1.