Methodology for Designing Reasonably Expressive Mechanisms with Application to Ad Auctions

1 Introduction

A key trend on the Internet is a move toward more expressiveness in the mechanisms that mediate interactions such as the allocation of resources, matching of peers, and elicitation of opinions. Intuitively, one would think that more expressiveness leads to higher efficiency (sum of the agents' utilities) of the outcome (e.g., due to better matching of supply and demand). Efficiency improvements have indeed been reported from combinatorial and multi-attribute auctions (e.g., [Sandholm, 2007]), as well as expressive ad auction variants (e.g., [Lahaie et al., 2008; Parkes and Sandholm, 2005; Even-Dar et al., 2007; Boutilier et al., 2008]). Yet, adding expressiveness does not always improve the outcome of a mechanism in practice. It generally increases the overhead

Tuomas Sandholm

Computer Science Department Carnegie Mellon University sandholm@cs.cmu.edu

associated with running the mechanism (e.g., time and effort to collect data, computation requirements) [Martin et al., 2008]. For some populations, increased expressiveness can be unnecessary [Abrams et al., 2007] and can give rise to additional equilibria of poor efficiency [Milgrom, 2007]. It can even confuse (e.g., Herb Simon's "bounded rationality" [1955]), or aggravate (e.g., Barry Schwartz's "tyranny of choice" [2004]) people. What is missing is an operational methodology to quantify the expected efficiency gains from increasing expressiveness.

Work on information complexity of mechanisms has a long history (e.g., [Mount and Reiter, 1974; Hurwicz, 1972]). Recent theoretical work based on the notion of shattering from computational learning theory provided the foundations for studying expressiveness in a domain-independent manner [Benisch et al., 2008]. In this paper we operationalize that theory with a methodology for comparing mechanisms with different degrees and forms of expressiveness. We apply it to sponsored search, or ad auctions conducted online for placement alongside search results.

The sponsored search industry accounts for tens of billions of dollars in revenue annually. The most frequent variant of these auctions, the generalized second price (GSP) mechanism used by Google, Yahoo!, MSN, etc. solicits a single bid from each advertiser (i.e., agent) for a keyword and assigns the advertisers to positions on a search result page according to the bids (roughly speaking, with the first position going to the highest bidder, the second position to the second highest, etc.). Since agents cannot offer a separate bid price for each ad position, the GSP mechanism is fundamentally inexpressive. We will attempt to characterize the loss of economic efficiency caused by this inexpressiveness, and to explore the conditions that affect that loss.

We begin by adapting our recent theoretical framework for studying expressiveness [Benisch et al., 2008] to analyze the GSP. We find that for some preference distributions the GSP is arbitrarily inefficient.

In order to measure the inefficiency in practice we must be able to predict the outcome of the mechanism. The equilibrium of the GSP is known when it is assumed that agents have complete information (i.e., no private information about valuations) and monotonic preferences over positions (i.e., higher positions are always preferred) [Varian, 2007]; however when we relax these somewhat restrictive assumptions, the equilibrium behavior is unknown. In fact, it is often difficult to characterize equilibrium behavior in less than fully expressive mechanisms when agents have complex preferences [Rosenthal and Wang, 1996; Wilenius and Andersson, 2007; Szentes and Rosenthal, 2003]. For that reason, we develop a general tree search technique for computing an upper bound on a mechanism's expected efficiency, that involves finding social welfare maximizing strategies for the agents. In the worst case our search algorithm takes time that is exponential in the number of agents and types, but it can be applied to any preference distribution and provides an upper bound that tightens in an anytime manner.

We conclude with a series of experiments comparing the GSP to our slightly more expressive mechanism, which solicits an extra bid for premium ad positions, which we coin Premium GSP (PGSP). We generate a range of realistic synthetic preference distributions based on published industry knowledge, and apply our search technique to compare the efficiency bounds achieved by social welfare maximizing strategies in the two mechanisms. We also examine the performance of the two mechanisms when agents use a straightforward heuristic bidding strategy.

While we must be careful not to read too much into experiments on synthetic data, they suggest that the GSP's efficiency loss can be dramatic. It is greatest in the practical case where some agents ("brand advertisers") prefer top positions while others ("value advertisers") prefer middle positions (since customers who click on ads in middle positions are more likely to take action, resulting in revenue). The loss is also worst when agents have small profit margins. Despite the fact that our PGSP mechanism is only slightly more expressive (and thus not much more cumbersome), it removes almost all of the efficiency loss in all of the settings we study.

2 Setting and background results

The setting we study is a one-shot auction for a set of k advertising positions that are ranked from 1 to k (rank 1 is the highest rank). In the model there are n agents. Each agent i has some private information (not known by the mechanism or any other agent) denoted by a type, ti, (e.g., a vector of valuations, one for each of the k positions) from the space of the agent's possible types, Ti.

Settings where each agent has a utility function, ui(ti, O), that depends only on its own type and the outcome (matching of agents to positions), O ∈ O, chosen by the mechanism are called private values settings. We also discuss more general interdependent values settings, where ui = ui(tn ,O), i.e., an agent's utility depends on the others' private signals as well (for example, if one agent's value for a position depends on market estimates of the other agents). In both settings, agents report expressions to the mechanism, denoted θi, based only on their own types. In the GSP mechanism each agent can report a single real value indicating his/her bid. A mapping from types to expressions is called a pure strategy.

Based on these expressions the mechanism computes the value of an outcome function, f (θn ), which chooses an outcome. In the GSP mechanism the outcome function maps agents to positions based on the order of their bids (the highest bidder is assigned the first position, the second highest bidder is assigned the second, etc.). 1 The mechanism may also compute the value of a payment function, π(θn ), which determines how much each agent must pay or get paid. In this paper, we ignore the mechanism's payment function because expressiveness is tied directly to a mechanism's outcome function. 2

We denote by W (tn , o) the social welfare of outcome o when agents have private types tn, i.e., W (tn , o) = ∑i ui(tn , o). Assuming that the expression of each agent in the mechanism's most efficient Nash equilibrium is given by a function mi(ti), we can describe the mechanism's expected efficiency under that equilibrium, E(f, π), with the following equation (expectation is taken over the types of the agents, and their randomized equilibrium expressions).

2.1 A framework for characterizing expressiveness

The theoretical framework that we developed in our earlier work [Benisch et al., 2008], provides the foundations for understanding the impact of making mechanisms more or less expressive, by providing meaningful, general definitions of a mechanism's expressiveness.

In that work, we defined an impact vector to capture the impact of a particular expression by an agent under the different possible types of the other agents, and an expressiveness concept based on a notion called shattering, which we adapted from the field of computational learning theory [Vapnik and Chervonenkis, 1971]. The adapted notion captures an agent's ability to distinguish among each of the impact vectors involving a subset of outcomes.

We also introduced a slightly weaker adaptation of shattering, called semi-shattering, for analyzing the more restricted setting where agents have private values. It captures an agent's ability to cause each of the unordered pairs of outcomes (with replacement) to be chosen for every pair of types of the other agents, but without being able to control the order of the outcomes (i.e., which outcome happens for which type). We defined a measure of expressiveness based on the size of the largest outcome space that an agent can shatter or semi-shatter. It is called the (semi-)shatterable outcome dimension.

In addition to defining the expressiveness notions, we tied those notions to an upper bound on the expected efficiency of a mechanism's most efficient equilibrium. We derived the bound by making the optimistic assumption that the agents play strategies which, taken together, attempt to maximize social welfare. The bound is given by the following equation

1 In practice the bids are adjusted by predicted click-through rates (CTR) before conducting the ranking. For simplicity, we do not weight by CTR. However, our formulation can be easily extended to account for this by multiplying each agent's original bid by its CTR.

2 Since the efficiency bound that we study does not directly depend on equilibrium behavior, this is without loss of generality, as long as agents do not care about each others' payments.

(the max is taken over all possible joint pure strategies).

Our earlier work provided several results relating this bound to a mechanism's expressiveness. For the purposes of this paper the following result will prove useful.

Theorem 1 (reworded from [Benisch et al., 2008]). For any setting, there exists a distribution over agent preferences such that the upper bound on expected efficiency for the best outcome function where agent i has semi-shatterable outcome dimension di < |O| is arbitrarily lower than that of the best outcome function where agent i has semi-shatterable outcome dimension di + 1.

3 Expressiveness in ad auctions

In order to study the expressiveness properties of the GSP's outcome function, we first derive a mathematical representation of the function. Let R(i, o) be the rank of the position given to the i'th agent in the matching of agents to positions denoted by outcome o. For analysis purposes we will assume, without loss of generality, that each agent's bid, θi, is restricted to be between 0 and 1 (this is not a limiting assumption due to the fact that we can losslessly map from any real valued space to this interval). Under this assumption, the following is functionally equivalent to the GSP's outcome function.

Each bid in the sum is weighted by 10 raised to the negative power of the corresponding agent's rank under the chosen outcome. Thus, agents with higher bids will contribute significantly more to the overall sum when they are placed in the first position.

We will now show that the outcome function of the GSP mechanism is inexpressive according to the notion of outcome semi-shattering introduced in the previous section. 3

Theorem 2. Consider a set of outcomes, {A,B,C,D}, under which agent i is assigned different positions. In the GSP mechanism, agent i cannot semi-shatter both pairs of outcomes {A, B} and {C, D} if the other agents have more than one joint type and the ranks satisfy R(i,A) < R(i,C) < R(i, D) < R(i, B).

This result, in conjunction with Theorem 1, implies that under some preference distributions the efficiency bound for the GSP is arbitrarily inefficient, and since it is an upper bound, the inefficiency exists under any strategy profile.

Corollary 1. For any setting there exists a distribution over agent preferences such that the upper bound on expected efficiency (Equation 2) for the GSP mechanism's outcome function is arbitrarily less than fully efficient.

3 Proof of Theorem 2 can be found in this paper's appendix.

4 PremiumGSPmechanism

To address GSP's inexpressiveness without making the mechanism much more cumbersome, we introduce a new mechanism that only slightly increases the expressiveness. Later we show that this slight increase is extremely important in that it removes most of the efficiency loss entailed by GSP's inexpressiveness.

The new mechanism separates the positions into two classes: premium and standard, and each agent can submit a separate bid for each class. We call this the premium generalized second price (PGSP) mechanism. The premium class might contain, for example, only the top position-as in our experiments.

The premium position(s) are assigned as if a traditional GSP were run on the premium bids (the top premium position goes to the agent with the highest premium bid, etc.). The standard positions are then assigned among the remaining agents according the traditional GSP mechanism run on their standard bids.

5 Computing the efficiency bound

The results in Section 3 prove that there exist distributions over agent preferences for which the GSP is arbitrarily inefficient. However, in order to measure the inefficiency in practice we must be able to compute the value of the efficiency bound for any particular distribution over agent preferences. In this section we describe two general techniques for doing that. They take as input a distribution over agent preferences with a finite number of types (this distribution could be learned from data or approximated by a domain expert) and provide the value of the upper bound on the mechanism's most efficient equilibrium. Although we present our techniques in the context of ad auctions, they can easily be generalized for use in other domains.

5.1 Integer programming formulation

First we will describe an integer programming formulation for computing the bound. The program includes a binary decision variable, z to , for each outcome and each joint type of the agents. A value of 1 for z to denotes that outcome o will be chosen by the mechanism when the agents have the joint type t, a value of 0 indicates that the outcome will not be chosen under t. The program also includes continuous variables representing the agents' expressions (bids in the context of sponsored search) under each of their types, θti i . (We limit these expressions to be between 0 and 1, without loss of generality.) The following objective function is used to maximize the expected efficiency of the mechanism.

The first set of constraints enforces that exactly one outcome is chosen for each joint type. There are |T n| such constraints.

The next set of constraints ensures that for each z to variable that is set to 1, the agents' expressions under type t do indeed cause the outcome function to choose outcome o. This set includes one constraint for each joint type and each pair of distinct outcomes. Thus there are |T n| × (|O|2 - |O|) such inequality constraints. 4 These constraints depend on the outcome function of the mechanism we are studying. For GSP's outcome function, the constraints are as follows (we use M to denote a sufficiently large number such that the sum of all the agents' expressions cannot exceed it):

Finally, we have constraints on the decision variables:

An ad auction with k positions and n agents with two types each has n! (n-k)! distinct outcomes and 2n joint types. The integer program has |O| × |T n| binary decision variables, making it prohibitively large for general purpose integer program solvers, such as CPLEX, for mechanisms with more than 3 agents. These solvers do not explicitly take advantage of certain aspects of the problem structure, for example the fact that only one outcome can be chosen for each joint type.

5.2 Tree search for computing the bound

To address this problem, we developed a general tree search technique based on A* for computing the bound. We have applied the technique to GSP and PGSP on instances with up to five agents to find provable inefficiency. (In this paper we only report results with four agents in order to provide a larger number of experiments.)

Each level of the search tree corresponds to a different joint type. Each branch corresponds to the assignment of an outcome to the joint type. The tree has maximum depth |T n| and branching factor |O|. Figure 1 illustrates the search tree.

At any node j a partial assignment of outcomes to joint types can be constructed by traversing the edges from j to the root. We will denote the set of all joint types in the partial assignment at node j as T n j . For each type tnj ∈ T n j we will denote the outcome it is assigned under the partial assignment at node j as otj . In addition, for each joint type tn we will denote any one of the outcomes that maximize social welfare as o∗t (i.e., o∗t = argmaxoW (tn, o)).

As usual, our search orders the nodes in its open queue according to an admissible (i.e., optimistic) heuristic. The heuristic approximates the expected efficiency of the best assignment originating from a particular node under the assumption that any unassigned types will be assigned optimally. 5 The priority of a node j, ˜ f (j ), is given by the expected welfare of its current partial assignment plus the expected welfare of the optimal assignment for any unassigned types:

4 In practice we ensure that these inequality constraints are strict by adding a small ϵ term to one side.

5 We need only calculate o* once at the beginning of the search. It can be reused later by removing outcomes that are assigned.

The ˜ f (j ) approximation is guaranteed to be greater than or equal to the true optimal value of any feasible assignment that descends from node j. It may overestimate this value if the optimal assignment is not achievable due to inexpressiveness, but it has the benefit of serving as a valid upper bound on the expected efficiency achievable by the mechanism. By using the A* node selection strategy, our search ensures that any node that it visits has a lower (or equal) ˜ f value than any previously visited node. Thus, the ˜ f value of the current node is a continually tightening upper bound on the mechanism's expected efficiency, and it can be provided at any time during the search.

Whenever a node is popped off the front of the open queue, its feasibility is checked. In both types of ad auction mechanisms we study, this check involves solving a linear feasibility problem (LFP). The LFP involves a set of constraints similar to those described in Equation 6, however the assignment of outcomes to types is fixed and there are no binary decision variables. If the node is not feasible, its children are not placed on the open queue.

6 Experiments

In this section we discuss the results of experiments using our search technique to compute the upper bound for the GSP mechanism and the slightly more expressive PGSP mechanism.

In order to gain additional insight, we also discuss the performance of the two mechanisms when agents use the straightforward strategy of always bidding their valuation for the top position (in the PGSP they bid their valuation for the top premium position and the top non-premium position as their two bids). We call the resulting efficiency GSP heuristic and PGSP heuristic, respectively.

Our experiments consist of collections of runs, each involving randomly generated instances with different parameter settings. The parameters are chosen to investigate circumstances under which the inexpressiveness of the GSP mechanism is costly (i.e., when the upper bound is low) and when it is not. Each instance in one of our experiments represents a single auction for a single keyword with four agents.

Based on recent work examining different advertising attitudes on the Internet, in our experiments each agent is either a brand advertiser (with probability pB) or a value advertiser (with probability 1 - pB) [Baye and Morgan, 2005]. Brand advertisers always prefer higher positions over lower ones. A value advertiser generally does not prefer the highest positions because middle positions tend to have higher conversion rates (e.g., the user's probability of buying something conditional on having clicked is higher). Figure 2 illustrates prototypical brand and value preferences over different positions based on their rank.

We now describe how we generate preferences for brand and value advertisers. Let "clk" denote the event that the ad is clicked, and "cnv" denote that the click results in a conversion (e.g., a sale or user registration). Let Ci denote the amortized cost per click of running agent i's web site, and Vi(cnv) be the expected value of a conversion to agent i. Then, the expected value to agent i of having an ad in position ranked R is

In order to keep the experiments simple and to focus on the impact of expressiveness, we assume that agents in the same instance are relatively similar. For one, we assume that the marginal cost of a click Ci = C = $1 for all agents. Unless otherwise specified, we assume that Vi(cnv) = V (cnv) = $50 for all agents. We assume that P(cnv|clk, i) = P(cnv|clk) = 10% for all agents. We also assume that click-through rates conditional on the rank of an ad's position are the same for all agents. The specific rates are given in Table 1, along with the default values for all parameters. These click-through rates are from an Atlas Institute Digital Marketing publication [Brooks, 2007]. They were also used by Even-Dar et al. in their experiments [Even-Dar et al., 2007].

Rather than generating arbitrary values of P (cnv|clk, R, i), we assume that the probability of a conversion coming from a particular rank, P(R|cnv, i), is normally distributed. The mean, μ, of this distribution is randomly chosen from [0, 1]

for each agent, once for the case where she is a brand advertiser and once for the case where she is a value advertiser. (We also normalize the value of R to be between 0 and 1, so that, for example, the third position out of four has rank 0.25.) Values of μ closer to 1 indicate that the agent's conversions tend to come from higher ranked ads, those closer to 0 indicate that conversions tend to come from lower ranked ads. The values of μ for the brand and value advertisers are given in Table 1, unless otherwise specified.

We transform P(R|cnv, i) into P(cnv|clk,R, i) using Bayes' rule (and the observation that the cnv event implies the clk event):

Each data point in each figure below is the average over 50 instances. 6 The confidence intervals represent standard error. (They are often so tight that they are barely visible.)

6.1 Experiment 1: Varying agents' profit margin

In our first set of results we vary the expected value of a conversion, V (cnv), between $35 and $150 (i.e., 35 to 150 times the cost per click of running the site), Figure 3.

These results demonstrate that when conversions generate relatively low profits, the efficiency loss due to inexpressiveness in the GSP mechanism, as measured by the upper bound, is more than 30%. As the profit margin of the agents increases, this loss decreases to around 10%.

6 On occasion the search does not find the optimal value within our time limit of 20 minutes; this occurred on approximately 25% of the instances evenly distributed between mechanisms. For those instances we use the lowest ˜ f value discovered prior to termination.

Additionally, the results show that the efficiency bound for the slightly more expressive PGSP mechanism is nearly 100% in all cases. This suggests that the added expressiveness in the PGSP is well suited to capture all the different types of preferences we generated.

We also see that the efficiency of the heuristic bidding strategy follows a similar qualitative pattern to the upper bound, which lends additional support to our findings. Specifically, this suggests that 1) the bound is meaningful in describing the efficiency of the mechanism, and 2) the conclusions apply more broadly than for fully rational game-theoretic agents.

6.2 Experiment 2: Varying agent diversity

The second experiment examines how the loss due to inexpressiveness depends on how similar value advertisers are to brand advertisers. Specifically, we vary the position that generates the most value for value advertisers. (Brand advertisers still always prefer the highest position the most.) In each run the mean of P(R|cnv, i) for each value advertiser is drawn uniformly from an interval of size 0.2 (i.e., μ ∼ Uniform[a, a + 0.2]). The results are shown in Figure 4. The x-axis indicates the mid-point of the interval used in each run, which is also the expected value of μ for each value advertiser.

These results demonstrate that the need for additional expressiveness is greatest when the value advertisers prefer middle ranking positions, as is typically the case in practice. For example, when those agents prefer the middle rank, the GSP can achieve at most 85% efficiency (with the heuristic bidding strategy achieving less than 75%) on average, whereas the PGSP can achieve over 95% (with the heuristic bidding strategy achieving about 85%). The expressiveness is less necessary when the value advertisers become more like the brand advertisers (i.e., large E[μ]) or when they are drastically different than the brand advertisers (i.e., small E[μ]).

Again the efficiency of the heuristic bidding strategy follows a similar qualitative pattern to the upper bound.

7 Conclusions and future research

A key trend on the Internet is a move toward more expressiveness in mechanisms. Yet, adding expressiveness does not always improve the outcome of a mechanism in practice. In this paper we operationalized a recent theoretical framework for studying expressiveness with a methodology for comparing mechanisms with different degrees and forms of expressiveness, and applied it to sponsored search.

We began by proving that for some preference distributions the most commonly used sponsored search mechanism, GSP, is arbitrarily inefficient. In order to measure the inefficiency in practice we developed a general tree search technique for computing an upper bound on a mechanism's expected efficiency. We concluded with a series of experiments comparing the GSP to our slightly more expressive mechanism, PGSP, which solicits an extra bid for premium ad positions. We generated a range of realistic preference distributions based on published industry knowledge, and applied our search technique to compare the efficiency bounds in the two mechanisms. We also examined the performance of the mechanisms when agents use a straightforward heuristic bidding strategy.

Our results suggest that the GSP's efficiency loss due to inexpressiveness can be dramatic. It is greatest in the practical case where some agents ("brand advertisers") prefer top positions while others ("value advertisers") prefer middle positions. The loss is also worst when agents have small profit margins. Despite the fact that our PGSP mechanism is only slightly more expressive (and thus not much more cumbersome), it removes almost all of the efficiency loss in all of the settings we study.

Future research includes using our methodology to study efficiency in sponsored search with real data. We also plan to apply our methodology to other domains in order to design mechanisms that are not unnecessarily expressive yet remove most of the inefficiency of today's inexpressive mechanisms.

8 Acknowledgement

This work has been supported by the National Science Foundation under grants IGERT-9972762, ITR-0205435, IIS0427858, and CNS-0627513.