# envyfree_sponsored_search_auctions_with_budgets__bee8960f.pdf Envy-Free Sponsored Search Auctions with Budgets Bo Tang, Jinshan Zhang Dept. of Computer Science, University of Liverpool Liverpool, United Kingdom {Bo.Tang, Jinshan.Zhang}@liverpool.ac.uk We study the problem of designing envy-free sponsored search auctions, where bidders are budgetconstrained. Our primary goal is to design auctions that maximize social welfare and revenue two classical objectives in auction theory. For this purpose, we characterize envy-freeness with budgets by proving several elementary properties including consistency, monotonicity and transitivity. Based on this characterization, we come up with an envyfree auction, that is both social-optimal and bidderoptimal for a wide class of bidder types. More generally, for all bidder types, we provide two polynomial time approximation schemes (PTASs) for maximizing social welfare or revenue, where the notion of envy-freeness has been relaxed slightly. Finally, in cases where randomization is allowed in designing auctions, we devise similar PTASs for social welfare or revenue maximization problems. 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. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015) 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 P i N rij 1 and P j M rij 1. Thus, the allocation xi = P 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 P i N vixi and the revenue is P 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 pmin ij min k>i {Bk + 1 + Xk 2 ℓ=i vℓ+1(qj+ℓ i qj+ℓ i+1)} 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 pi min{Bi+1 + 1, vi+1(xi xi+1) + pi+1} min{Bi+1 + 1, vi+1(xi xi+1) + min k>i+1{Bk + 1 + Xk 2 ℓ=i+1 vl+1(xℓ xℓ+1)} = min k>i {Bk + 1 + Xk 2 ℓ=i vℓ+1(xℓ xℓ+1)} min k>i {Bk + 1 + Xk 2 ℓ=i vℓ+1(qj+ℓ i qj+ℓ i+1)} The equality comes from Pk 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 Pk 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 Auction 1: Auction for Proportional Bidders 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 viqj (Bk + 1 + Xk 2 ℓ=i vℓ+1(qj+ℓ i qj+ℓ i+1)) ℓ=i (vℓ vℓ+1)qj+ℓ i + vk 1qj+k i 1 Bk 1 ℓ=i (vℓ vℓ+1)qj +ℓ i + vk 1qj +k i 1 Bk 1 (vi vi )qj + Xk 2 ℓ=i (vℓ vℓ+1)qj +ℓ i + vk 1qj +k i 1 Bk 1 =(vi vi )qj + vi qj pi = viqj pi 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 + Pi 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 l=i vl+1(qj+l i qj+l i+1) Bk 1 l=i (vl vl+1)qj+l i + vk 1qj+k i 1 Bk 1 l=i (vl vl+1)qj +l i + vk 1qj +k i 1 Bk 1 l=i vl+1(qj +l i qj +l i+1) Bk 1 (20, 2000) 1 bidders positions (vi, Bi) qi Figure 1: An illustration of Example 3.7. The left nodes represent bidders with value and budget pairs. The right squares are positions with qualities. The dashed arrows are the bidder-optimal allocations while the normal arrows are the social-optimal allocations. 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, bid- der 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 Auction 2: PTAS for Social-optimal Auctions Input: An instance I = (v, B, q) and a value ϵ (0, 1) Output: An outcome (x, p) B maxi N Bi; W {Bi}n i=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 xa2 or (xa1 = xa2 and va1 va2) We set R[i1, i2; j1, j2; w1, w2] = maxj