# welfare_guarantees_from_data__a19f8c05.pdf

Welfare Guarantees from Data

Darrell Hoy University of Maryland darrell.hoy@gmail.com

Denis Nekipelov University of Virginia denis@virginia.edu

Vasilis Syrgkanis Microsoft Research vasy@microsoft.com

Analysis of efﬁciency of outcomes in game theoretic settings has been a main item of study at the intersection of economics and computer science. The notion of the price of anarchy takes a worst-case stance to efﬁciency analysis, considering instance independent guarantees of efﬁciency. We propose a data-dependent analog of the price of anarchy that reﬁnes this worst-case assuming access to samples of strategic behavior. We focus on auction settings, where the latter is non-trivial due to the private information held by participants. Our approach to bounding the efﬁciency from data is robust to statistical errors and mis-speciﬁcation. Unlike traditional econometrics, which seek to learn the private information of players from observed behavior and then analyze properties of the outcome, we directly quantify the inefﬁciency without going through the private information. We apply our approach to datasets from a sponsored search auction system and ﬁnd empirical results that are a signiﬁcant improvement over bounds from worst-case analysis.

1 Introduction

A major ﬁeld at the intersection of economics and computer science is the analysis of the efﬁciency of systems under strategic behavior. The seminal work of [6, 11] triggered a line of work on quantifying the inefﬁciency of computer systems, ranging from network routing, resource allocation and more recently auction marketplaces [10]. However, the notion of the price of anarchy suffers from the pessimism of worst-case analysis. Many systems can be inefﬁcient in the worst-case over parameters of the model, but might perform very well for the parameters that arise in practice.

Due to the large availability of datasets in modern economic systems, we propose a data-dependent analog of the price of anarchy, which assumes access to a sample of strategic behavior from the system. We focus our analysis on auction systems where the latter approach is more interesting due to the private information held by the participants of the system, i.e. their private value for the item at sale. Since efﬁciency is a function of these private parameters, quantifying the inefﬁciency of the system from samples of strategic behavior is non-trivial. The problem of estimation of the inefﬁciency becomes an econometric problem where we want to estimate a function of hidden variables from observed strategic behavior. The latter is feasible under the assumption that the observed behavior is the outcome of an equilibrium of the strategic setting, which connects observed behavior to unobserved private information.

Traditional econometric approaches to auctions [3, 8], address such questions by attempting to exactly pin-point the private parameters from the observed behavior and subsequently measuring the quantities of interest, such as the efﬁciency of the allocation. The latter approach is problematic in complex auction systems for two main reasons: (i) it leads to statistical inefﬁciency, (ii) it requires strong conditions on the connection between observed behavior and private information. Even for a single-item ﬁrst-price auction, uniform estimation of the private value of a player from T samples of observed bids, can only be achieved at O(T 1/3)-rates [3]. Moreover, uniquely identifying the private information from the observed behavior, requires a one-to-one mapping between the two

31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA.

quantities. The latter requires strong assumptions on the distribution of private parameters and can only be applied to simple auction rules.

Our approach bridges the gap between worst-case price of anarchy analysis and statistically and modeling-wise brittle econometric analysis. We provide a data-dependent analog of recent techniques for quantifying the worst-case inefﬁciency in auctions [13, 4, 10], that do not require characterization of the equilibrium structure and which directly quantify the inefﬁciency through best-response arguments, without the need to pin-point the private information. Our approach makes minimal assumptions on the distribution of private parameters and on the auction rule and achieves O(

T)- rates of convergence for many auctions used in practice, such as the Generalized Second Price (GSP) auction [2, 14]. We applied our approach to a real world dataset from a sponsored search auction system and we portray the optimism of the data-dependent guarantees as compared to their worst-case counterparts [1].

2 Preliminaries

We consider the single-dimensional mechanism design setting with n bidders. The mechanism designer wants to allocate a unit of good to the bidders, subject to some feasibility constraint on the vector of allocations (x1, . . . , xn). Let X be the space of feasible allocations. Each bidder i has a private value vi [0, H] per-unit of the good, and her utility when she gets allocation xi and is asked to make a payment pi is vi xi pi. The value of each bidder is drawn independently from distribution with CDF Fi, supported in Vi R+ and let F = i Fi be the joint distribution.

An auction A solicits a bid bi B from each bidder i and decides on the allocation vector based on an allocation rule X : Bn X and a payment rule p : Bn Rn. For a vector of values and bids, the utility of a bidder is: Ui(b; vi) = vi Xi(b) Pi(b). (1) A strategy σi : Vi B, for each bidder i, maps the value of the bidder to a bid. Given an auction A and distribution of values F, a strategy proﬁle σ is a Bayes-Nash Equilibrium (BNE) if each bidder i with any value vi Vi maximizes her utility in expectation over her opponents bids, by bidding σi(vi).

The welfare of an auction outcome is the expected utility generated for all the bidders, plus the revenue of the auctioneer, which due to the form of bidder utilities boils down to being the total value that the bidders get from the allocation. Thus the expected utility of a strategy proﬁle σ is

WELFARE(σ; F) = Ev F

i [n] vi Xi(σ(v))

We denote with OPT(F) the expected optimal welfare: OPT(F) = Ev F[maxx X P

i [n] vi xi].

Worst-case Bayes-Nash price of anarchy. The Bayesian price of anarchy of an auction is deﬁned as the worst-case ratio of welfare in the optimal auction to the welfare in a Bayes-Nash equilibrium of the original auction, taken over all value distributions and over all equilibria. Let BNE(A, F) be the set of Bayes-Nash equilibria of an auction A, when values are drawn from distributions F. Then:

POA = sup F,σ BNE(F)

OPT(F) WELFARE(σ; F) (3)

3 Distributional Price of Anarchy: Reﬁning the POA with Data

We will assume that we observe T samples b1:T = {b1, . . . , b T } of bid proﬁles from running T times an auction A. Each bid proﬁle bt is drawn i.i.d. based on an unknown Bayes-Nash equilibrium σ of the auction, i.e.: let D denote the distribution of the random variable σ(v), when v is drawn from F. Then bt are i.i.d. samples from D. Our goal is to reﬁne our prediction on the efﬁciency of the auction and compute a bound on the price of anarchy of the auction conditional on the observed data set. More formally, we want to derive statements of the form: conditional on b1:T , with probability at least 1 δ: WELFARE(σ; F) 1

ˆρOPT(F), where ˆρ is the empirical analogue of the worst-case price of anarchy ratio.

Inﬁnite data limit We will tackle this question in two steps, as is standard in estimation theory. First we will look at the inﬁnite data limit where we know the actual distribution of equilibrium bids D. We deﬁne a notion of price of anarchy that is tailored to an equilibrium bid distribution, which we refer to as the distributional price of anarchy. In Section 4 we give a distribution-dependent upper bound on this ratio for any single-dimensional auction. Subsequently, in Section 5, we show how one can estimate this upper bound on the distributional price of anarchy from samples.

Given a value distribution F and an equilibrium σ, let D(F, σ) denote the resulting equilibrium bid distribution. We then deﬁne the distributional price of anarchy as follows: Deﬁnition 1 (Distributional Price of Anarchy). The distributional price of anarchy DPOA(D) of an auction A and a distribution of bid proﬁles D, is the worst-case ratio of welfare in the optimal allocation to the welfare in an equilibrium, taken over all distributions of values and all equilibria that could generate the bid distribution D:

DPOA(D) = sup F,σ BNE(F) s.t. D(F,σ)=D

OPT(F) WELFARE(σ; F) (4)

This notion has nothing to do with sampled data-sets, but rather is a hypothetical worst-case quantity that we could calculate had we known the true bid generating distribution D.

What does the extra information of knowing D give us? To answer this question, we ﬁrst focus on the optimization problem each bidder faces. At any Bayes-Nash equilibrium each player must be best-responding in expectation over his opponent bids. Observe that if we know the rules of the auction and the equilibrium distribution of bids D, then the expected allocation and payment function of a player as a function of his bid are uniquely determined:

xi(b; D) = Eb i D i [Xi(b, b i)] pi(b; D) = Eb i D i [Pi(b, b i)] . (5)

Importantly, these functions do not depend on the distribution of values F, other than through the distribution of bids D. Moreover, the expected revenue of the auction is also uniquely determined:

REV(D) = Eb D

Thus when bounding the distributional price of anarchy, we can assume that these functions and the expected revenue are known. The latter is unlike the standard price of anarchy analysis, which essentially needs to take a worst-case approach to these quantities.

Shorthand notation Through the rest of the paper we will ﬁx the distribution D. Hence, for brevity we omit it from notation, using xi(b), pi(b) and REV instead of xi(b; D), pi(b; D) and REV(D).

4 Bounding the Distributional Price of Anarchy

We ﬁrst upper bound the distributional price of anarchy via a quantity that is relatively easy to calculate as a function of the bid distribution D and hence will also be rather straightforward to estimate from samples of D, which we defer to the next section. To give intuition about the upper bound, we start with a simple but relevant example of bounding the distributional price of anarchy in the case when the auction A is the single-item ﬁrst price auction. We then generalize the approach to any auction A.

4.1 Example: Single-Item First Price Auction

In a single item ﬁrst price auction, the designer wants to auction a single indivisible good. Thus the space of feasible allocations X, are ones where only one player gets allocation xi = 1 and other players get allocation 0. The auctioneer solicits bids bi from each bidder and allocates the good to the highest bidder (breaking ties lexicographically), charging him his bid. Let D be the equilibrium distribution of bids and let Gi be the CDF of the bid of player i. For simplicity we assume that Gi is continuous (i.e. the distribution is atomless). Then the expected allocation of a player i from submitting a bid b is equal to xi(b) = G i(b) = Q

j =i Gj(b) and his expected payment is pi(b) = b xi(b), leading to expected utility: ui(b; vi) = (vi b)G i(b).

The quantity DPOA is a complex object as it involves the structure of the set of equilibria of the given auction. The set of equilibria of a ﬁrst price auction when bidders values are drawn from different distributions is an horriﬁc object.1 However, we can upper bound this quantity by a much simpler data-dependent quantity by simply invoking the fact that under any equilibrium bid distribution no player wants to deviate from his equilibrium bid. Moreover, this data-dependent quantity can be much better than its worst-case counterpart used in the existing literature on the price of anarchy.

Lemma 1. Let A be the single item ﬁrst price auction and let D be the equilibrium distribution of bids, then DPOA(D) µ(D) 1 e µ(D) , where µ(D) = maxi [n] Eb i D i[maxj =i bj]

Eb D[maxi [n] bi] .

Proof. Let Gi be the CDF of the bid of each player under distribution D. Moreover, let σ denote the equilibrium strategy that leads to distribution D. By the equilibrium condition, we know that for all vi Vi and for all b B,

ui(σi(vi); vi) ui(b ; vi) = (vi b ) G i(b ). (7)

We will give a special deviating strategy used in the literature [13], that will show that either the players equilibrium utility is large or the expected maximum other bid is high. Let Ti denote the expected maximum other bid which can be expressed as Ti = R 0 1 G i(z)dz. We consider the randomized deviation where the player submits a randomized bid in z [0, vi(1 e µ)] with PDF f(z) = 1 µ(vi z). Then the expected utility from this deviation is:

E b [ui(b ; vi)] = Z vi(1 e µ)

0 (vi z) G i(z)f(z)dz = 1

Z vi(1 e µ)

0 G i(z)dz (8)

Adding the quantity 1

µ R vi(1 e µ) 0 (1 G i(z))dz 1

µTi on both sides, we get: Eb [ui(b ; vi)] +

1 µTi vi 1 e µ

µ . Invoking the equilibrium condition we get: ui(σi(vi); vi) + 1

µTi vi 1 e µ

µ . Subsequently, for any x i [0, 1]:

ui(σi(vi); vi) + 1

µTi x i vi x i 1 e µ

If x i is the expected allocation of player i under the efﬁcient allocation rule X i (v) 1{vi = maxj vj}, then taking expectation of Equation (9) over vi and adding across all players we get:

i E vi [ui(σi(vi); vi)] + 1

i Ti X i (v)

OPT(F)1 e µ

The theorem then follows by invoking the fact that for any feasible allocation x: P

i Ti xi maxi Ti = µ(D)REV(D), using the fact that expected total agent utility plus total revenue at equilibrium is equal to expected welfare at equilibrium and setting µ = µ(D).

Comparison with worst-case POA In the worst-case, µ(D) is upper bounded by 1, leading to the well-known worst-case price of anarchy ratio of the single-item ﬁrst price auction of (1 1/e) 1, irrespective of the bid distribution D. However, if we know the distribution D then we can explicitly estimate µ, which can lead to a much better ratio (see Figure 1). Moreover, observe that even if we had samples from the bid distribution D, then estimating µ(D) is very easy as it corresponds to the ratio of two expectations, each of which can be estimating to within an O( 1

T ) error by a simple average and using standard concentration inequalities. Even thought this improvement, when compared to the worst-case bound might not be that drastic in the ﬁrst price auction, the extension of the analysis in the next section will be applicable even to auctions where the analogue of the quantity µ(D) is not even bounded in the worst-case. In those settings, the empirical version of the price of anarchy analysis is of crucial importance to get any efﬁciency bound.

1Even for two bidders with uniformly distributed values U[0, a] and U[0, b], the equilibrium strategy requires solving a complex system of partial differential equations, which took several years of research in economics to solve (see [15, 7])

0 1 2 3 4 1

Price of Anarchy

Figure 1: The upper bound on the distributional price of anarchy of an auction µ(D) 1 e µ(D as a function of µ(D).

Comparison with value inversion approach Apart from being just a primer to our main general result in the next section, the latter result about the data-dependent efﬁciency bound for the ﬁrst price auction, is itself a contribution to the literature. It is notable to compare the latter result with the standard econometric approach to estimating values in a ﬁrst price auction pioneered by [3] (see also [8]). Traditional non-parametric auction econometrics use the equilibrium best response condition to pin-point the value of a player from his observed bid, by what is known as value inversion. In particular, if the function: ui(b ; vi) = (vi b ) G i(b ) has a unique maximum for each vi and this maximum is strictly monotone in vi, then given the equilibrium bid of a player bi and given a data distribution D we can reverse engineer the value vi(bi) that the player must have. Thus if we know the bid distribution D we can calculate the equilibrium welfare as Eb D [P

i vi(bi) Xi(b)]. Moreover, we can calculate the expected optimal welfare as: Eb D [maxi vi(bi)]. Thus we can pin-point the distributional price of anarchy.

However, the latter approach suffers from two main drawbacks: (i) estimating the value inversion function vi( ) uniformly over b from samples, can only happen at very slow rates that are at least O(1/T 1/3) and which require differentiability assumptions from the value and bid distribution as well as strong conditions that the density of the value distribution is bounded away from zero in all the support (with this lower bound constant entering the rates of convergence), (ii) the main assumption of the latter approach is that the optimal bid is an invertible function and that given a bid there is a single value that corresponds to that bid. This assumption might be slightly benign in a single item ﬁrst price auction, but becomes a harsher assumption when one goes to more complex auction schemes. Our result in Lemma 1 suffers neither of these drawbacks: it admits fast estimation rates from samples, makes no assumption on properties of the value and bid distribution and does not require invertibility of the best-response correspondence. Hence it provides an upper bound on the distributional price of anarchy that is statistically robust to both sampling and mis-speciﬁcation errors. The robustness of our approach comes with the trade-off that we are now only estimating a bound on the efﬁciency of the outcome, rather than exactly pinpointing it.

4.2 Generalizing to any Single-Dimensional Auction Setting

Our analysis on DPOA is based on the reformulation of the auction rules as an equivalent pay-yourbid auction and then bounding the price of anarchy as a function of the ratio of how much a player needs to pay in an equivalent pay-your-bid auction, so as to acquire his optimal allocation vs. how much revenue is the auctioneer collecting. For any auction, we can re-write the expected utility of a bid b:

ui(b; vi) = xi(b) vi pi(b)

This can be viewed as the same form of utility if the auction was a pay-your-bid auction and the player submitted a bid of pi(b)

xi(b). We refer to this term as the price-per-unit and denote it ppu(b) = pi(b)

xi(b). Our analysis will be based on the price-per-unit allocation rule x( ), which determines the expected allocation of a player as a function of his price-per-unit. Given this notation, we can re-write the utility that an agent achieves if he submits a bid that corresponds to a price-per-unit of z as: ui(z; vi) = x(z)(vi z). The latter is exactly the form of a pay-your-bid auction.

Our upper bound on the DPOA, will be based on the inverse of the PPU allocation rule; let τi(z) = x 1 i (z) be the price-per-unit of the cheapest bid that achieves allocation at least z. More formally,

τi(z) = minb|xi(b) z{ppu(b)}. For simplicity, we assume that any allocation z [0, 1] is achieveable by some high enough bid b.2 Given this we can deﬁne the threshold for an allocation: Deﬁnition 2 (Average Threshold). The average threshold for agent i is

0 τi(z) dz (12)

In Figures 3 and 2 we provide a pictorial representation of these quantities. Connecting with the previous section, for a ﬁrst price auction, the price-per-unit function is ppu(b) = b, the price-per-unit allocation function is xi(b) = G i(b) and the threshold function is τi(z) = G 1 i (z). The average threshold Ti is equal to R 1 0 G 1 i (z)dz = R 0 1 G i(b)db, i.e. the expected maximum other bid.

xi(ppu) = τ 1 i (ppu)

E[Allocation]

Figure 2: For any bid b with PPC ppu(b), the area of a rectangle between (ppu(b), xi(ppu(b))) and (vi, 0) on the bid allocation rule is the expected utility ui(b). The BNE action b is chosen to maximize this area.

E[Allocation]

Figure 3: The average threshold is the area to the left of the price-per-unit allocation rule, integrate from 0 to 1.

We now give our main theorem, which is a distribution-dependent bound on DPOA, that is easy to compute give D and which can be easily estimated from samples of D. This theorem is a generalization of Lemma 1 in the previous section. Theorem 2 (Distributional Price of Anarchy Bound). For any auction A in a single dimensional setting and for any bid distribution D, the distributional price of anarchy is bounded by DPOA(D) µ(D) 1 e µ(D) , where µ(D) = maxx X Pn i=1 Ti xi REV(D) .

Theorem 2 provides our main method for bounding the distributional price of anarchy. All we need is to compute the revenue REV of the auction and the quantity:

T = maxx X Pn i=1 Ti xi, (13)

under the given bid distribution D. Both of these are uniquely deﬁned quantities if we are given D. Moreover, once we compute Ti, the optimization problem in Equation (13) is simply a welfare maximization problem, where each player s value per-unit of the good is Ti. Thus, the latter can be solved in polynomial time, whenever the welfare maximization problem over the feasible set X is polynomial-time solvable.

Theorem 2 can be viewed as a bid distribution-dependent analogue of the revenue covering framework [4] and of the smooth mechanism framework [13]. In particular, the quantity µ(D) is the datadepenent analogue of the worst-case µ quantity used in the deﬁnition of µ-revenue covering in [4] and is roughly related to the µ quantity used in the deﬁnition of a (λ, µ)-smooth mechanism in [13].

5 Distributional Price of Anarchy Bound from Samples

In the last section, we assumed we were given distribution D and hence we could compute the quantity µ = T REV, which gave an upper bound on the DPOA. We now show how we can estimate this

2The theory can be easily extended to allow for different maximum achievable allocations by each player, by simply integrating the average threshold only up until the largest such allocation.

quantity µ when given access to i.i.d. samples b1:T from the bid distribution D. We will separately estimate T and REV. The latter is simple expectation and thereby can be easily estimated by an average at 1

T rates. For the former we ﬁrst need to estimate Ti for each player i, which requires estimation of the allocation and payment functions xi( ; D) and pi( ; D).

Since both of these functions are expected values over the equilibrium bids of opponents, we will approximate them by their empirical analogues:

t=1 Xi(b, bt i) bpi(b) = 1

t=1 Pi(b, bt i). (14)

To bound the estimation error of the quantities ˆTi produced by using the latter empirical estimates of the allocation and payment function, we need to provide a uniform convergence property for the error of these functions over the bid b.

Since b takes values in a continuous interval, we cannot simply apply a union bound. We need to make assumptions on the structure of the class of functions FXi = {Xi(b, ) : b B} and FPi = {Pi(b, ) : b B}, so as uniformly bound their estimation error. For this we resort to the technology of Rademacher complexity. For a generic class of functions F and a sequence of random variables Z1:T , the Rademacher complexity is deﬁned as:

RT (F, Z1:T ) = E σ1:T

t=1 σtf(Zt)

where each σt { 1/2} is an i.i.d. Rademacher random variable, which takes each of those values with equal probabilities. The following well known theorem will be useful in our derivations: Theorem 3 ([12]). Suppose that for any sample Z1:T of size T, RT (F, Z1:T ) RT and suppose that functions in F take values in [0, H]. Then with probability 1 δ:

t=1 f(Zt) E[f(Z)]

This Theorem reduces our uniform error problem to bounding the Rademacher complexity of classes FXi and FPi, since we immediately have the following corollary (where we also use that the allocation functions lie in [0, 1] and the payment functions lie in [0, H]): Corollary 4. Suppose that for any sample b1:T of size T, the Rademacher complexity of classes FXi and FPi is at most RT . Then with probability 1 δ/2, both sup b B | bxi(b) xi(b)| and sup b B |bpi(b) pi(b)|

are at most 2RT + H p

2 log(4/δ) / T.

We now provide conditions under which the Rademacher complexity of these classes is O(1/

T). Lemma 5. Suppose that B = [0, B] and for each bidder i and each bi B, the functions Xi(bi, ) : [0, B]n 1 7 [0, 1] and Pi(b, ) : [0, B]n 1 7 [0, H] can be computed as ﬁnite superposition of (i) coordinate-wise multiplication of bid vectors b i with constants; (ii) comparison indicators 1{ > } of coordinates or constants; (iii) pairwise addition + of coordinates or constants. The Rademacher complexity for both classes on a sample of size T is O p

log(T) / T .

The proof of this Lemma follows by standard arguments of Rademacher calculus, together with VC arguments on the class of pairwise comparisons. Those arguments can be found in [5, Lemma 9.9] and [9, Lemma 11.6.28]. Thereby, we omit its proof. The assumptions of Lemma 5 can be directly veriﬁed, for instance, for the sponsored search auctions where the constants that multiply each bid correspond to quality factors of the bidders, e.g. as in [2] and [14] and then the allocation and the payment is a function of the rank of the weighted bid of a player. In that case the price and the allocation rule are determined solely by the ranks and the values of the score-weighted bids γibi, as well as the position speciﬁc quality factors αj, for each position j in the auction.

Next we turn to the analysis of the estimation errors on quantities Ti. We consider the following plugin estimator for Ti: We consider the empirical analog of function τi( ) by bτi(z) = inf b [0,B], b xi(b) z

Then the empirical analog of Ti is obtained by:

0 bτi(z) dz. (17)

To bound the estimation error of b Ti, we need to impose an additional condition that ensures that any non-zero allocation requires the payment from the bidder at least proportional to that allocation.

Assumption 6. We assume that pi(x 1 i ( )) is Lipschitz-continuous and that the mechanism is worstcase interim individually rational, i.e. pi(b) H xi(b).

Under this assumption we can establish that O(

T) rates of convergence of b Ti to Ti and of the empirical analog ˆT = maxx X Pn i=1 ˆTi xi of the optimized threshold to T as well as the empirical analog d REV of the revenue to REV. Thus the quantity ˆµ = ˆT d REV, will also converge to µ = T REV at that rate. This implies the following ﬁnal conclusion of this section. Theorem 7. Under Assumption 6 and the premises of Lemma 5, with probability 1 δ:

OPT(F) WELFARE(σ; F) bµ 1 e bµ + O

n max{L, H}

6 Sponsored Search Auction: Model, Methodology and Data Analysis

We consider a position auction setting where k ordered positions are assigned to n bidders. An outcome m in a position auction is an allocation of positions to bidders. m(j) denotes the bidder who is allocated position j; m 1(i) refers to the position assigned to bidder i. When bidder i is assigned to slot j, the probability of click ci,j is the product of the click-through-rate of the slot αj and the quality score of the bidder, γi, so ci,j = αjγi (in the data the quality scores for each bidder are varying across different auctions and we used the average score as a proxy for the score of a bidder). Each advertiser has a value-per-click (VPC) vi, which is not observed in the data and which we assume is drawn from some distribution Fi. Our benchmark for welfare will be the welfare of the auction that chooses a feasible allocation to maximize the welfare generated, thus OPT = Ev[maxm P

i γiαm 1(i)vi].

We consider data generated by advertisers repeatedly participating in a sponsored search auction. The mechanism that is being repeated at each stage is an instance of a generalized second price auction triggered by a search query. The rules of each auction are as follows: Each advertiser i is associated with a click probability γi and a scoring coefﬁcient si and is asked to submit a bid-per-click bi. Advertisers are ranked by their rank-score qi = si bi and allocated positions in decreasing order of rank-score as long as they pass a rank-score reserve r. All the mentioned sets of parameters θ = (s, α, γ, r) and the bids b are observable in the data.

We will denote with πb,θ(j) the bidder allocated in slot j under a bid proﬁle b and parameter proﬁle θ. We denote with π 1 b,θ(i) the slot allocated to bidder i. If advertiser i is allocated position j, then he pays only when he is clicked and his payment, i.e. his cost-per-click is the minimal bid

he had to place to keep his position, which is: cpcij(b; θ) = max n sπb,θ(j+1) bπb,θ(j+1),r o

si . Mapping this setting to our general model, the allocation function of the auction is Xi(b) = απ 1 b,θ(i) γ, the payment function is Pi(b) = απ 1 b,θ(i) γ cpciπ 1 b,θ(i)(b; θ) and the utility function is:

Ui(b; vi) = απ 1 b,θ(i) γi vi cpciπ 1 b,θ(i)(b; θ) .

Data Analysis We applied our analysis to the Bing Ads sponsored search auction system. We analyzed eleven phrases from multiple thematic categories. For each phrase we retrieved data of auctions for the phrase for the period of a week. For each phrase and bidder that participated in the auctions for the phrase we computed the allocation curve by simulating the auctions for the week under any alternative bid an advertiser could submit (bids are multiples of cents).

See Figure 4 for the price-per-unit allocation curves xi( ) = τ 1 i ( ) for a subset of the advertisers for a speciﬁc search phrase. We estimated the average threshold ˆTi for each bidder by numerically

ˆµ = ˆT d REV 1 DPOA = 1 e ˆ µ ˆµ phrase1 .511 .783 phrase2 .509 .784 phrase3 2.966 .320 phrase4 1.556 .507 phrase5 .386 .829 phrase6 .488 .791 phrase7 .459 .802 phrase8 .419 .817 phrase9 .441 .809 phrase10 .377 .833 phrase11 .502 .786

Figure 4: (left) Examples of price-per-unit allocation curves for a subset of six advertisers for a speciﬁc keyword during the period of a week. All axes are normalized to 1 for privacy reasons. (right) Distributional Price of Anarchy analysis for a set of eleven search phrases on the Bing Ads system.

integrating these allocation curves along the y axis. We then applied the approach described in Section 3 for each of the search phrases, computing the quantity ˆT = maxx X P

i [n] ˆTi xi =

i ˆTi γi αm 1(i). The latter optimization is simply the optimal assignment problem where each player s value-per-click is ˆTi and can be performed by greedily assigning players to slots in decreasing order of ˆTi. We then estimate the expected revenue by the empirical revenue d REV.

We portray our results on the estimate ˆµ = ˆT d REV and the implied bound on the distributional price of anarchy for each of the eleven search phrases in Table 4. Phrases are grouped based on thematic category. Even though the worst-case price of anarchy of this auction is unbounded (since scores si are not equal to qualities γi, which is required in worst-case POA proofs [1]), we observe that empirically the price of anarchy is very good and on average the guarantee is approximately 80% of the optimal. Even if si = γi the worst-case bound on the POA implies guarantees of approx. 34% [1], while the DPOA we estimated implies signiﬁcantly higher percentages, portraying the value of the empirical approach we propose.

[1] Ioannis Caragiannis, Christos Kaklamanis, Maria Kyropoulou, Brendan Lucier, Renato Paes Leme, and Éva Tardos. Bounding the inefﬁciency of outcomes in generalized second price auctions. pages 1 45, 2014.

[2] Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. The American economic review, 97(1):242 259, 2007.

[3] Emmanuel Guerre, Isabelle Perrigne, and Quang Vuong. Optimal nonparametric estimation of ﬁrst-price auctions. Econometrica, 68(3):525 574, 2000.

[4] Jason Hartline, Darrell Hoy, and Sam Taggart. Price of Anarchy for Auction Revenue. In ACM Conference on Economics and Computation, pages 693 710, New York, New York, USA, 2014. ACM Press.

[5] Michael R Kosorok. Introduction to empirical processes and semiparametric inference. Springer Science & Business Media, 2007.

[6] Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In STACS 99, pages 404 413. Springer, 1999.

[7] Vijay Krishna. Auction Theory. Academic Press, March 2002.

[8] H. J. Paarsch and H. Hong. An Introduction to the Structural Econometrics of Auction Data. MIT Press, 2006.

[9] D. Pollard. Convergence of Stochastic Processes. Springer-Verlag, 1984.

[10] Tim Roughgarden, Vasilis Syrgkanis, and Éva Tardos. The price of anarchy in auctions. Co RR, abs/1607.07684, 2016.

[11] Tim Roughgarden and Eva Tardos. How bad is selﬁsh routing? J. ACM, 49(2):236 259, March 2002.

[12] S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.

[13] Vasilis Syrgkanis and Eva Tardos. Composable and efﬁcient mechanisms. In ACM Symposium on Theory of Computing, pages 211 220, 2013.

[14] Hal R Varian. Online ad auctions. The American Economic Review, pages 430 434, 2009.

[15] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8 37, 1961.