# automated_design_of_robust_mechanisms__47061f10.pdf

Automated Design of Robust Mechanisms

Michael Albert, Vincent Conitzer Department of Computer Science Duke University Durham, NC 27708, USA {malbert,conitzer}@cs.duke.edu

Peter Stone Department of Computer Science University of Texas at Austin Austin, TX 78712, USA pstone@cs.utexas.edu

We introduce a new class of mechanisms, robust mechanisms, that is an intermediary between ex-post mechanisms and Bayesian mechanisms. This new class of mechanisms allows the mechanism designer to incorporate imprecise estimates of the distribution over bidder valuations in a way that provides strong guarantees that the mechanism will perform at least as well as ex-post mechanisms, while in many cases performing better. We further extend this class to mechanisms that are with high probability incentive compatible and individually rational, ϵ-robust mechanisms. Using techniques from automated mechanism design and robust optimization, we provide an algorithm polynomial in the number of bidder types to design robust and ϵ-robust mechanisms. We show experimentally that this new class of mechanisms can significantly outperform traditional mechanism design techniques when the mechanism designer has an estimate of the distribution and the bidder s valuation is correlated with an externally veriﬁable signal.

Introduction Auctions are one of the fundamental tools of the modern economy for allocating resources. They are used to allocate online ad space, offshore oil drilling rights, famous artwork, small and medium lift capacity to planetary orbit, government supply contracts, FCC spectrum licenses, and almost limitless numbers of other things, large and small. Further, the sizes of these markets are economically enormous. In 2014, $10 billion dollars of ad revenue was generated through automated auctions (Interactive Advertising Bureau (IAB) 2015). In 2012, just four government agencies the Army, the Department of Homeland Security, the Department of the Interior, and the Department of Veteran Affairs purchased $800+ million of commercial items through auctions (Government Accountability Ofﬁce 2013). In 2014, NASA awarded contracts to Boeing and Space-X worth $4.2 billion and $2.6 billion respectively through an implicit auction process (NASA 2014). In an ongoing auction, the FCC is expected to allocate between $60 and $80 billion worth of broadcast spectrum. Given the economic magnitudes involved, it is crucial that these auctions are implemented optimally, for even small deviations from opti-

Copyright c 2017, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

mality can lead to millions of dollars worth of lost revenue, inefﬁciencies in resource allocation, and overspending. It has long been understood that revenue optimal auction mechanisms are prior-dependent (also known as Bayesian) mechanisms (Myerson 1981; Cremer and Mc Lean 1985; 1988; Lopomo 2001), i.e., mechanisms that assume some knowledge of the kinds of bidders that are likely to participate. For a seller trying to maximize revenue by selling a single item to independent bidders, she1 needs to set a reserve price below which she will not sell the item (Myerson 1981), and this reserve price is dependent on her belief about the bidders she is likely to face. However, much of the focus of the algorithmic mechanism design community has been on the approximate optimality of simple mechanisms (Bulow and Klemperer 1996; Hartline and Roughgarden 2009; Roughgarden and Talgam-Cohen 2013; Morgenstern and Roughgarden 2015), that is, mechanisms that are either prior-independent or weakly prior-dependent (this distinction will be made clear later on). This focus is due to two factors. First, prior-dependent mechanisms can be very brittle to mis-speciﬁed priors (Lopomo 2001; Albert, Conitzer, and Lopomo 2015). That is to say, if a prior-dependent mechanism is constructed using an incorrect prior it can perform much worse than simple mechanisms (Hartline and Roughgarden 2009). Second, competition can be an effective substitute for knowledge of the distribution (Bulow and Klemperer 1996), so instead of implementing prior-dependent mechanisms, practitioners generally implement prior-independent mechanisms under the assumption that there are many bidders, or that it will somehow be possible to acquire new bidders Unfortunately, in many auctions there is no feasible way to acquire more bidders. When NASA is awarding contracts to private space companies, they cannot generate more companies with the expertise to provide lift capacity, nor can Google ﬁnd more bidders who are interested in advertising on search results for obscure brand-related keywords. Thin auctions are an actively recognized concern for many organizations that use auction mechanisms. A Government Ofﬁce of Accountability report from 2013 (Government Accountability Ofﬁce 2013) examining the use of reverse auctions by

1In this paper, we will use he to denote bidders and she to denote mechanism designers/sellers.

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

four governmental organizations, found that of the 19,688 reverse auctions the organizations conducted in 2012 with a total worth of $800+ million, over one-third had only a single bidder. Further, the organizations discussed in the report each voiced concern over the lack of competition as a signiﬁcant hindrance to the effective application of auctions. In this paper, we develop a new class of mechanisms, robust mechanisms, that allow for some degree of uncertainty in the distribution over the bidders types while still performing better than weakly prior-dependent mechanisms such as ex-post mechanisms. We provide an algorithm for computing an optimal robust mechanism in polynomial time in the number of bidder types by combining techniques from the automated mechanism design literature (Conitzer and Sandholm 2002; 2004; Guo and Conitzer 2010; Sandholm and Likhodedov 2015) and the literature on robust optimization (Bertsimas and Sim 2004; Bergemann and Morris 2005; Aghassi and Bertsimas 2006). This mechanism design algorithm is primarily targeted at applications with few bidders, or thin markets, due to exponential scaling in the number of bidders. However, thin markets are likely to beneﬁt the most from these techniques (Bulow and Klemperer 1996; Hartline and Roughgarden 2009), so we do not consider this a signiﬁcant negative. We then introduce the notion of ϵ-robust mechanisms, or mechanisms that guarantee with high probability that the standard constraints of incentive compatibility and individual rationality hold but allow for a non-zero chance of violation. Finally, we show experimentally that ϵ-robust mechanisms can signiﬁcantly outperform other mechanism design procedures when the mechanism designer estimates the distribution over a bidder s type and a correlated external signal.

Preliminaries We consider a single monopolistic seller auctioning one object, which the seller values at zero, to a single bidder whose valuation is correlated with an external signal. The special case of a single bidder and an externally veriﬁable signal captures many of the important aspects of this problem while increasing ease of exposition relative to the case of many bidders, and this setting has been used in the literature on correlated mechanism design (Mc Afee and Reny 1992; Albert, Conitzer, and Lopomo 2015; 2016) for this purpose. The external signal can, but does not necessarily, represent other bidders bids. The bidder has a type θ drawn from a ﬁnite set of discrete types Θ = {1, ..., |Θ|}. Further, the bidder has a valuation function v : Θ R+ that maps types to valuations for the object. Assume, without loss of generality, that for all θ, θ Θ, if θ > θ then v(θ) v(θ ). The discrete external signal is denoted by ω Ω = {1, 2, . . . , |Ω|}. Throughout the paper, we will denote vectors as bold symbols. There is a probability distribution, π, over the types of the bidder and external signal where the probability of type and signal (θ, ω) is π(θ, ω). The probability distribution can be represented in many possible ways, but we will represent it as a matrix. Speciﬁcally, the distribution is a matrix of dimension |Θ| |Ω| whose elements are all positive and sum to one. Note that in contrast to much of the literature on

mechanism design, we do not require that the bidder type be distributed independently of the external signal. The distribution over the external signal ω given θ will be denoted by the |Ω| dimensional vector π( |θ). We will, in many cases, be primarily interested in the conditional distribution over the external signal given the bidder s type, π( |θ), so we will represent the full distribution as a marginal distribution over Θ, πθ, and a set of conditional distributions over Ω, π( | ) = {π( |1), π( |2), ..., π( ||Θ|)}. Therefore, if the true distribution is π, we will alternatively represent it as {πθ, π( | )}. A (direct) revelation mechanism is deﬁned by, given the bidder type and external signal (θ, ω), 1) a probability that the seller allocates the item to the bidder and 2) a monetary transfer from the bidder to the seller. We will denote the probability of allocating the item to the bidder as p(θ, ω), which is a value between zero and one, and the transfer from the bidder to the seller as x(θ, ω), where a positive value denotes a payment to the seller and a negative value a payment from the seller to the bidder. We will denote a mechanism as (p, x).

Deﬁnition 1 (Bidder s Utility). Given a realization of the external signal ω, reported type θ Θ, and true type θ Θ, the bidder s utility under mechanism (p, x) is:

U(θ, θ , ω) = v(θ)p(θ , ω) x(θ , ω)

Due to the well-known revelation principle (e.g., Gibbons (1992)), the seller can restrict her attention to incentive compatible mechanisms, i.e., mechanisms where it is always optimal for the bidder to truthfully report his valuation. However, incentive compatibility can be speciﬁed in multiple ways. For the sake of presentation, we will restrict our focus to two of the most common, ex-post incentive compatibility and Bayesian incentive compatibility. Ex-post incentive compatible mechanisms guarantee that for any realization of the external signal, the bidder always ﬁnds it optimal to report his value truthfully. In contrast, Bayesian incentive compatible mechanisms only guarantee that, given the beliefs of the bidder over the external signal, the bidder will have the highest expected utility if he reports truthfully: after seeing the realization of the external signal, he may regret his report.

Deﬁnition 2 (Ex-Post Incentive Compatibility). A mechanism (p, x) is ex-post incentive compatible (IC) if:

θ, θ Θ, ω Ω : U(θ, θ, ω) U(θ, θ , ω)

Deﬁnition 3 (Bayesian Incentive Compatibility). A mechanism (p, x) is Bayesian incentive compatible (IC) if:

ω Ω π(ω|θ)U(θ, θ, ω)

ω Ω π(ω|θ)U(θ, θ , ω)

Bayesian incentive compatibility is a statement about the beliefs of the bidder over the external signal, π(ω|θ). Specifically, it allows the seller to determine payments by lottery. The lottery that bidder i faces can be dependent on his valuation, but the lottery itself is over the external signal (see Albert, Conitzer, and Lopomo (2016) for a full discussion).

Bayesian incentive compatibility is a strict relaxation of expost in the sense that any mechanism that is ex-post incentive compatible is also Bayesian incentive compatible. In addition to incentive compatibility, we are interested in mechanisms that are individually rational, i.e., it is rational for a bidder to participate in the mechanism. We will deﬁne ex-post individual rationality (a bidder is never worse off by participating in the mechanism) and ex-interim individual rationality (the bidder has non-negative expected utility for participating in the mechanism). Again, ex-interim individual rationality is a strict relaxation of ex-post.

Deﬁnition 4 (Ex-Post Individual Rationality). A mechanism (p, x) is ex-post individually rational (IR) if:

θ Θ, ω Ω : U(θ, θ, ω) 0

Deﬁnition 5 (Ex-Interim Individual Rationality). A mechanism (p, x) is ex-interim individually rational (IR) if:

ω Ω π(ω|θ)U(θ, θ, ω) 0

We will refer to mechanisms that satisfy ex-post individual rationality and incentive compatibility as ex-post mechanisms and mechanisms that satisfy Bayesian incentive compatibility and ex-interim individual rationality as Bayesian mechanisms. Bayesian mechanisms are what we have been referring to as prior-dependent mechanisms, while ex-post is weakly prior-dependent, i.e., only the objective function depends on the distribution, not the constraints over incentive compatibility and individual rationality. To illustrate the importance of prior-dependent mechanisms, it is necessary to review a few important results in the literature on revenue maximization with correlated valuation distributions when the distribution is perfectly known.

Deﬁnition 6 (Cremer-Mc Lean Condition). The distribution over types π, is said to satisfy the Cremer-Mc Lean condition if the set of beliefs associated with the bidder, {π( |θ) : θ Θ}, are linearly independent.

Theorem 1 (Cremer and Mc Lean (1985)). If the Cremer Mc Lean condition is satisﬁed by the distribution π, then there exists an ex-interim IR and ex-post IC mechanism that extracts the full social surplus as revenue.

This result due to Cremer and Mc Lean (1985) states that under the apparently reasonable Cremer-Mc Lean condition, i.e., a condition that holds with probability one for a random distribution, the mechanism designer can generate as much revenue in expectation as if she knew the bidder s valuation. This is a remarkable result and it can be relaxed further, for both ex-post and Bayesian IC, by the results in Albert, Conitzer, and Lopomo (2016).

Theorem 2 (Albert, Conitzer, and Lopomo (2016)). A Bayesian IC and ex-interim IR mechanism can extract full social surplus as revenue if and only if there exists a convex function G : R|Ω| R such that for all θ Θ, G(π( |θ)) = v(θ).

Consistent Sets of Distributions While Theorems 1 and 2 make relatively weak assumptions about the distributions in order to guarantee full revenue extraction, they do require that the mechanism designer knows the distribution exactly. If instead of precise knowledge of the distribution of bidder types and external signals the mechanism designer has an imprecise estimate of the distribution, the prior-dependent mechanism can fail to be both incentive compatible and individually rational. This failure can be a signiﬁcant problem for two reasons. First, if the mechanism is not individually rational bidders will not participate in the mechanism. If the market is thin, the loss of even a single bidder can lead to signiﬁcant decreases in expected revenue, even relative to simple mechanisms (Bulow and Klemperer 1996). Second, if the mechanism is not incentive compatible, the bidder may optimally choose to mis-report his true valuation, leading both to biases in future estimates of the distribution and difﬁculty in reasoning about the performance of the mechanism, since it is unclear a-priori how the bidder will report. It is in this sense that Bayesian incentive compatible and ex-interim individually rational mechanisms are, in general, strongly prior-dependent. The mechanism depends not only on the seller s estimate of the distribution, but also the bidder s belief over the distribution. The consequences of these being mis-aligned is not just slightly lower expected revenue, as would be the case for weakly prior-dependent mechanisms such as a second price auction with reserve; it is a failure of the mechanism to maintain fundamental characteristics (Hartline 2014; Albert, Conitzer, and Lopomo 2015). Therefore, unless the seller has perfect knowledge of the bidder s beliefs, standard mechanism design techniques will leave only the option of using sub-optimal, weakly prior-dependent mechanisms. A more realistic assumption is that the distribution is not perfectly known, but instead estimated. The seller estimates the distribution π as π. Assume that this estimation is imperfect, and that there exists a set of distributions that are consistent with the estimated distribution.

Deﬁnition 7 (Set of Consistent Distributions). Let P(A) be the set of probability distributions over a set A. Then the space of all probability distributions over Θ Ω can be represented as the Cartesian product P(Θ) θ Θ P(Ω). A subset P(ˆπ) = P({ˆπθ, ˆπ( | )}) P(Θ)

θ Θ P(Ω) is a consistent set of distributions for the estimated distribution {ˆπθ, ˆπ( | )} if the true distribution, {πθ, π( | )}, is guaranteed to be in P(ˆπ).

With a consistent set of distributions, we can relax the notion of ex-interim IR and Bayesian IC by requiring that the mechanism be IR and IC for all distributions in the consistent set. However, since the distribution π is also private information, by the revelation principle, the mechanism designer can also elicit the true distribution from the bidder and condition the mechanism on the reported distribution. Therefore, we modify the deﬁnitions of the mechanism, (p, x), such that they depend not only on the reported type and external signal, but also the reported distribution π . We similarly modify the deﬁnition of bidder utility.

Deﬁnition 8 (Robust Individual Rationality). A mechanism is robust individually rational for estimated bidder distribution ˆπ and consistent set of distributions P(ˆπ) if for all θ Θ and π P(ˆπ),

ω Ω π(ω|θ)U(θ, π, θ, π, ω) 0

Deﬁnition 9 (Robust Incentive Compatibility). A mechanism is robust incentive compatible for estimated bidder distribution ˆπ and consistent set of distributions P(ˆπ) if for all θ, θ Θ and π, π P(ˆπ),

ω Ω π(ω|θ)U(θ, π, θ,π, ω)

ω Ω π(ω|θ)U(θ, π, θ , π , ω)

Note that we can restrict our attention to settings where the bidder only reports π P(ˆπ) by setting the allocation probability p to zero if the bidder reports π P(ˆπ).

Robust Mechanisms Existing mechanism design techniques are inadequate to optimize revenue over these situations. Speciﬁcally, Bayesian mechanisms can have very unintuitive formulations consisting of multiple lotteries over the value of the external signal making it unlikely that a standard class of simple intuitive mechanisms will be able to implement revenue efﬁcient robust mechanisms. Therefore, we will combine techniques from automated mechanism design and robust convex optimization to automate the design of robust mechanisms. Further, while it is theoretically possible to allow bidders to report both their valuations and their beliefs, and design optimal mechanisms given this joint report, standard automated mechanism design techniques require ﬁnitely speciﬁed input, and we are explicitly interested in inﬁnite sets of distributions. We will simplify the mechanism design process by only considering mechanisms for which the payments, x, and probabilities of allocations, p, depend only on the reported bidder types and the realization of the external signal. While this is not without loss of generality, it will be sufﬁcient to signiﬁcantly outperform ex-post mechanisms in our experiments. Deﬁnition 10 (Optimal Robust Mechanism). An optimal robust mechanism given an estimated distribution ˆπ and a consistent set of distributions P(ˆπ) is a mechanism that is an optimal solution to the following program:

θ,ω ˆπ(θ, ω)x(θ, ω)

ω Ω π (ω|θ)U(θ, θ, ω) 0 θ Θ, π P(ˆπ)

ω Ω π (ω|θ)U(θ, θ, ω)

ω Ω π (ω|θ)U(θ, θ , ω)

θ, θ Θ, π P(ˆπ) 0 p(θ, ω) 1 θ Θ, ω Ω

Note that the linear program in Deﬁnition (10) still contains an inﬁnite number of constraints over a, potentially, non-convex set, and therefore is in general computationally intractable. However, the following assumption allows computational tractability. Assumption 1. The set P(ˆπ) is such that for all θ Θ, P(ˆπ( |θ)) is a convex n-polyhedron where n is polynomial in the number of bidder types. Assumption 1 includes very reasonable cases such as the case where for all θ Θ and ω Ω, π (ω|θ) [π(ω|θ), π(ω|θ)]. Further, any set that does not satisfy Assumption 1 can be contained in a set that does. Therefore, we can always make the assumption hold by using a larger consistent set. Theorem 3. For a given (p, x) and P(ˆπ) that satisfy Assumption 1, there exists a polynomial time algorithm that determines whether there exists a π ( |θ) P(ˆπ( |θ)) such that robust individual rationality or robust incentive compatibility is violated.

Proof. For each θ Θ, solve the following linear program

min π ( |θ)

ω π (ω|θ)(v(θ)p(ω, θ) x(ω, θ))

π ( |θ) P(ˆπ( |θ))

Note that in the program (1), (p, x) are no longer variables but coefﬁcients. If (1) has an objective value of less than 0, then the robust IR constraint with distribution π is violated. If the objective value is at least 0, there is no robust IR constraint violated for θ. There are |Θ| linear programs that must be solved, each with a polynomial number of variables and constraints, due to Assumption 1. Therefore, violated robust IR constraints can be generated in polynomial time. Similarly for robust incentive compatibility, the following program, for all θ, θ Θ, ﬁnds violated constraints:

min π ( |θ)

ω π (ω|θ)(v(θ)p(ω, θ) x(ω, θ)

(v(θ)p(ω, θ ) x(ω, θ ))) subject to

π ( |θ) P(ˆπ( |θ))

Corollary 4. If P(ˆπ) satisﬁes Assumption 1, the optimal robust mechanism can be computed in time polynomial in the number of types of the bidder and external signal.

Proof. By Theorem 3, we can determine whether or not a robust IR or robust IC constraint is violated in polynomial time, and add the constraint to the linear program. There are 2|Θ||Ω| variables in the linear program in Deﬁnition 10, and there are 2|Θ||Ω| non-IC and IR constraints. Therefore, by the ellipsoid method, the optimal robust mechanism can be computed in polynomial time (Kozlov, Tarasov, and Khachiyan 1980).

Note that Corollary 4 states that the optimal robust mechanism is polynomial in the number of bidder types, not the number of bidders. The current formulation is exponential in the number of bidders. However, as stated in the introduction, the advantage of prior-dependent mechanisms is primarily for thin auctions, so we do not view this as a signiﬁcant weakness of this approach. Since for ex-post mechanisms, incentive compatibility and individual rationality are independent of the distribution, it would be expected that when we have no useful information about the distribution, the optimal robust mechanism should be equivalent to the optimal ex-post mechanism. The following proposition shows that this is indeed the case.

Proposition 5. If for all θ Θ, and ω Ω, P(ˆπ) is such that the distribution π (ω |θ) = 1 if ω = ω and 0 otherwise is in P(ˆπ), then an optimal robust mechanism is an optimal ex-post mechanism for the distribution ˆπ.

Proof. If for all θ Θ and ω Ω, the distribution such that π (ω |θ) = 1 if ω = ω and 0 otherwise is in P(ˆπ), the robust IR constraints contain the following set of constraints

v(θ)p(θ, ω) x(θ, ω) 0 ω Ω, θ Θ

which implies ex-post IR. Conversely, ex-post IR implies robust IR. By an identical argument, the robust IC constraints imply the ex-post IC constraints, and vice-versa.

ϵ-Robust Mechanisms

While, so far we have been assuming that there is a well deﬁned set, P(ˆπ), such that the mechanism designer can guarantee that the true distribution, π, is in the set, this is unlikely to be a realistic assumption in practice. It is far more reasonable that the mechanism designer would have a set such that the true distribution is in the set with some high probability. If this is the case, we can still design mechanisms that are likely to outperform weakly prior dependent mechanisms, such as ex-post mechanisms, by relaxing the requirement that the mechanism be always incentive compatible and always individually rational. We will deﬁne the set of ϵ-consistent distributions as follows.

Deﬁnition 11 (Set of ϵ-Consistent Distributions). A subset Pϵ(ˆπ) = Pϵ({ˆπθ, ˆπ( | )}) P(Θ)

θ Θ P(Ω) is an ϵ-consistent set of distributions for the estimated distribution {ˆπθ, ˆπ( | )} if the true distribution, {πθ, π( | )}, is in Pϵ(ˆπ) with probability 1 ϵ.

Now we can deﬁne the notion of ϵ-robust individual rationality and incentive compatibility. These deﬁnitions are analogous to Deﬁnitions 8 and 9.

Deﬁnition 12 (ϵ-Robust Individual Rationality). A mechanism is ϵ-robust individually rational for estimated bidder distribution ˆπ and ϵ-consistent set of distributions Pϵ(ˆπ) if for all θ Θ and π Pϵ(ˆπ),

ω Ω π(ω|θ)U(θ, π, θ, π, ω) 0

102 103 104 105 106 Number of Samples

Relative Revenue

Ex-Post Robust Bayesian

Figure 1: The performance of the ex-post, ϵ-robust, and Bayesian mechanisms using the estimated distribution. All revenue is scaled by the full social surplus, denoted as 1. Note that the Number of Samples is in log scale. The parameters used were as follows: Correlation = .5, ϵ = .05. Each experiment was repeated 200 times, and the 95% conﬁdence interval is included for the ϵ-robust and ex-post mechanisms. The Bayesian mechanism conﬁdence interval is off the plot.

Deﬁnition 13 (ϵ-Robust Incentive Compatibility). A mechanism is ϵ-robust incentive compatible for estimated bidder distribution ˆπ and ϵ-consistent set of distributions Pϵ(ˆπ) if for all θ, θ Θ and π, π Pϵ(ˆπ),

ω Ω π(ω|θ)U(θ, π, θ,π, ω)

ω Ω π(ω|θ)U(θ, π, θ , π , ω)

Similarly to Deﬁnition 10, we can deﬁne the optimal ϵrobust mechanism. Again, for tractability of mechanism design, and to obtain more practical mechanisms, we will restrict attention to mechanisms that only depend on the reported bidder type and the external signal. Deﬁnition 14 (Optimal ϵ-Robust Mechanism). An optimal ϵ-robust mechanism given an estimated distribution ˆπ and an ϵ-consistent set of distributions Pϵ(ˆπ) is a mechanism that is an optimal solution to the following program:

max x(θ,ω),p(θ,ω)

θ,ω ˆπ(θ, ω)x(θ, ω)

ω Ω π (ω|θ)U(θ, θ, ω) 0 θ Θ, π Pϵ(ˆπ)

ω Ω π (ω|θ)U(θ, θ, ω)

ω Ω π (ω|θ)U(θ, θ , ω)

θ, θ Θ, π Pϵ(ˆπ) 0 p(θ, ω) 1 θ Θ, ω Ω

Proposition 6. If Pϵ(ˆπ) satisﬁes Assumption 1, the optimal ϵ-robust mechanism can be computed in time polynomial in the number of bidder types and external signals.

102 103 104 105 106 Number of Samples

Relative Revenue

Corr = .25 Corr = .5

(a) Number of Samples versus Correlation

102 103 104 105 106 Number of Samples

Relative Revenue

Epsilon = .01 Epsilon = .05

Epsilon = .1 Epsilon = .5

(b) Number of Samples versus ϵ

102 103 104 105 106 Number of Samples

Relative Revenue

Signals = 2 Signals = 5

Signals = 10

(c) Number of Samples versus Signal Space

Figure 2: The performance of the robust and ex-post mechanisms using the estimated distribution. All revenue is scaled by the full social surplus, which is denoted as 1. Shown are the 95% conﬁdence intervals for the robust mechanism. For any variable not explicitly shown the following values were used: Correlation = .5, ϵ = .05

Experimental Results

Throughout the experiments, we have a single bidder with type θ {1, 2, ..., 10} and valuation v(θ) = θ. The external signal is ω {1, 2, ..., 10}. We model the true distribution as a categorical distribution with 10 10 elements, with each element corresponding to a tuple (θ, ω). There are not, to our knowledge, standard distributions to test correlated mechanism design procedures available, so we use a discretized bi-variate normal distribution. Specifically, we discretize the area under the bi-variate standard normal distribution between [ 1.96, 1.96] in both dimensions as a 10 10 grid and normalize. We chose the bivariate normal distribution for its broad relevance to many empirically observed distributions and the ability to easily vary the correlation. Note that the bi-variate normal distribution always satisﬁes the Cremer-Mc Lean condition if the correlation is positive. To estimate the distribution, we sample from the true distribution and use Bayesian updating with a maximally uninformative Dirichlet prior (α = [1, ..., 1]) to arrive at a Dirichlet posterior over the distribution of bidder types and external signals. We then calculate empirical conﬁdence intervals by sampling from the Dirichlet posterior and observing the ϵ/(2 10 10) and (1 ϵ/(2 10 10)) quantiles for each element of the conditional distributions π(ω|θ) and use the quantiles as the ϵ-consistent set. Note that we do not simply use the ϵ/2 and (1 ϵ/2) quantiles due to jointly estimating conﬁdence intervals for 100 variables; the expression for the quantiles above is based on applying a union bound. For our experiments, we solve for the optimal ex-post, ϵ-robust, and Bayesian mechanisms given our estimated distribution ˆπ and our ϵ-consistent set. Given that both the optimal ϵ-robust and Bayesian mechanisms can fail to be incentive compatible and/or individually rational due to the difference between the estimated and true distribution, we compute the optimal action for the bidder: either report truthfully, strategically misreport, or do not participate. We then calculate the revenue accordingly.

In Figure 1, we show the performance of the optimal expost, robust, and Bayesian mechanisms using our estimated distribution as we increase the number of samples. We report conﬁdence intervals for both the ex-post mechanisms and the robust mechanisms; however for the Bayesian mechanisms, the conﬁdence intervals were off the chart. Figure 1 demonstrates how badly the Bayesian mechanism performs when the distribution is not exactly known. Even after 10, 000 samples from the true distribution, the Bayesian mechanism fails to outperform the ex-post mechanism. By contrast, the optimal ϵ-robust mechanism generates revenue indistinguishable from the ex-post mechanism for low numbers of samples, while signiﬁcantly outperforming the expost mechanism starting at about 10, 000 samples. In Figures 2a and 2b, we vary correlation and ϵ with increasing numbers of samples. As the bidder type and external signal are more highly correlated, the ϵ-robust mechanism requires fewer samples to perform well, Figure 2a. Also, we see that the ϵ-robust mechanism is not very sensitive to the choice of ϵ, Figure 2b, a fact that we attribute to being overly cautious in requiring all elements of the distribution to be in the bounded intervals. In Figure 2c, we bin some of the external signals together in order to explore the trade-off between estimating a lower dimensional distribution and constructing a mechanism over the full information. Speciﬁcally, for the Signals = 2 case we put all of ω = {1, ..., 5} into one bin and ω = {6, ..., 10} to a second bin. Note the true signal still has 10 values, we are just binning the observed signal. We ﬁnd that for a low number of samples, we do much better by binning the external signal, but, while difﬁcult to see on the plot, at higher numbers of samples, it is better to use the full distribution. Note that we consider the results here to be lower bounds on the performance of optimal ϵ-robust mechanisms. We assume a completely uninformative prior, increasing the required sample size. Further, we have used a na ıve distribution estimation procedure, so there is likely signiﬁcant room to improve upon the estimation.

Conclusion We have presented a new paradigm in mechanism design that formally addresses the problem of uncertainty about the bidder distribution. We do this by introducing a new notion of individual rationality and incentive compatibility that spans a spectrum between ex-post and Bayesian notions and demonstrate that this class of mechanisms can be optimized over efﬁciently. We further relax these notions to allow for some probability of mechanisms failing to be IR or IC. While much work needs to be done in exploring the performance of these mechanisms, experimental results suggest that they may generate signiﬁcantly higher revenue than either ex-post or Bayesian mechanisms when the underlying correlated distribution is estimated.

Acknowledgements Albert and Conitzer are thankful for support from NSF under awards IIS-1527434 and CCF-1337215, ARO under grants W911NF-12-1-0550 and W911NF-11-1-0332, and a Guggenheim Fellowship. This work has partially taken place in the Learning Agents Research Group (LARG) at UT Austin. LARG research is supported in part by NSF (CNS-1330072, CNS1305287, IIS-1637736, IIS-1651089), ONR (21C184-01), and AFOSR (FA9550-14-1-0087). Peter Stone serves on the Board of Directors of, Cogitai, Inc. The terms of this arrangement have been reviewed and approved by the University of Texas at Austin in accordance with its policy on objectivity in research.

References Aghassi, M., and Bertsimas, D. 2006. Robust game theory. Mathematical Programming 107(1):231 273. Albert, M.; Conitzer, V.; and Lopomo, G. 2015. Assessing the robustness of Cremer-Mc Lean with automated mechanism design. In Proceedings of the Twenty-Ninth AAAI Conference on Artiﬁcial Intelligence, AAAI 15, 763 769. Austin, TX, USA: AAAI Press. Albert, M.; Conitzer, V.; and Lopomo, G. 2016. Maximizing revenue with limited correlation: The cost of ex-post incentive compatibility. In Proceedings of the Thirtieth AAAI Conference on Artiﬁcial Intelligence (AAAI-16). Bergemann, D., and Morris, S. 2005. Robust mechanism design. Econometrica 73(6):1771 1813. Bertsimas, D., and Sim, M. 2004. The price of robustness. Operations Research 52(1):35 53. Bulow, J., and Klemperer, P. 1996. Auctions versus negotiations. The American Economic Review 86(1):pp. 180 194. Conitzer, V., and Sandholm, T. 2002. Complexity of mechanism design. In Proceedings of the 18th Annual Conference on Uncertainty in Artiﬁcial Intelligence, UAI 02, 103 110. Alberta, Canada: Morgan Kaufmann. Conitzer, V., and Sandholm, T. 2004. Self-interested automated mechanism design and implications for optimal combinatorial auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce, EC 04, 132 141. New York, NY, USA: ACM.

Cremer, J., and Mc Lean, R. P. 1985. Optimal selling strategies under uncertainty for a discriminating monopolist when demands are interdependent. Econometrica 53(2):pp. 345 361. Cremer, J., and Mc Lean, R. P. 1988. Full extraction of the surplus in Bayesian and dominant strategy auctions. Econometrica 56(6):pp. 1247 1257. Gibbons, R. 1992. Game Theory for Applied Economists. Princeton University Press. Government Accountability Ofﬁce. 2013. Reverse auctions: Guidance is needed to maximize competition and achieve cost savings. Technical report, Government Accountability Ofﬁce. Guo, M., and Conitzer, V. 2010. Computationally feasible automated mechanism design: General approach and case studies. In Proceedings of the Twentieth AAAI Conference on Artiﬁcial Intelligence, AAAI 10, 1676 1679. Atlanta, GA, USA: AAAI Press. NECTAR track. Hartline, J. D., and Roughgarden, T. 2009. Simple versus optimal mechanisms. In Proceedings of the 10th ACM Conference on Electronic Commerce, EC 09, 225 234. New York, NY, USA: ACM. Hartline, J. D. 2014. Mechanism design and approximation. http://jasonhartline.com/MDn A/. Interactive Advertising Bureau (IAB). 2015. IAB programmatic revenue report 2014 results. http://www.iab.net/ media/ﬁle/Pw C IAB Programmatic Study.pdf. Kozlov, M.; Tarasov, S.; and Khachiyan, L. 1980. The polynomial solvability of convex quadratic programming. USSR Computational Mathematics and Mathematical Physics 20(5):223 228. Lopomo, G. 2001. Optimality and robustness of the English auction. Games and Economic Behavior 36(2):219 240. Mc Afee, R. P., and Reny, P. J. 1992. Correlated information and mechanism design. Econometrica 60(2):pp. 395 421. Morgenstern, J., and Roughgarden, T. 2015. The pseudodimension of nearly-optimal auctions. In NIPS, Forthcoming. Myerson, R. B. 1981. Optimal auction design. Mathematics of Operations Research 6(1):58 73. NASA. 2014. NASA chooses american companies to transport U.S. astronauts to international space station. https: //www.nasa.gov/. Roughgarden, T., and Talgam-Cohen, I. 2013. Optimal and near-optimal mechanism design with interdependent values. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC 13, 767 784. New York, NY, USA: ACM. Sandholm, T., and Likhodedov, A. 2015. Automated design of revenue-maximizing combinatorial auctions. Operations Research 63(5):1000 1025.