Consider a seller selling an item to a buyer, whose private value 𝑉 is drawn from some known distribution D. The overall social welfare is maximized when the seller sells the item for $0, assuming the seller has no cost for the item. In contrast, to maximize the (average) revenue, the seller's optimal strategy is to sell at a revenue-maximizing price, which may lead to welfare loss due to the item going unsold.
More generally, in a single-item Bayesian auction with 𝑛 buyers with independent private valuations, a welfare-optimal mechanism is the second-price (or VCG) auction, which always gives the item to the highest-valued buyer. In contrast, even when the buyers have i.i.d. regular valuations, the revenue-optimal mechanism was shown by Myerson [19] to be a second-price auction with a reserve price; this may lead to the item going unsold. The situation is more complex for non-regular distributions, and/or non-i.i.d. buyers, where the revenue-optimal mechanism may in addition sell the item to a buyer with lower value than the highest, leading to additional welfare loss. We visualize this via a revenue-CS trade-off diagram (Fig. 1b), where, for different mechanisms and value distributions, we plot expected consumer-surplus (i.e., value minus payment), denoted CS, versus expected seller-revenue, denoted by R. Any welfare-maximizing mechanism including VCG (point 𝑉 ) lies on the R + CS = W * line. In contrast, Myerson's mechanism (point 𝑀) has revenue R 𝑀 greater than that under VCG, but can also lie below the maximum-welfare line.
Information Intermediary. Now consider the same setting, but with an additional information intermediary: a third-party who knows the true buyer values ì 𝑉 = (𝑉 1 , 𝑉 2 , . . . , 𝑉 𝑛 ) and can provide a łsignalž or side-information to the seller and the buyers. Both the signal and signaling scheme are common knowledge to all agents (buyers and seller), who can thus use Bayes' rule to update the prior over valuations given the signal. The signal łre-shapesž the joint prior over the buyer valuations in a Bayes-plausible manner (i.e., such that the posterior averaged over signals equals the prior). Though the intermediary can modulate information, it does not control the mechanism, which still resides with the seller. Such a setting is motivated by ad exchanges, where the platform (or intermediary) acts only as a clearinghouse, and does not itself run a mechanism. Therefore, given the signal, the seller then proposes the revenue-maximizing mechanism, and buyers bid optimally, under the posterior distribution. We illustrate this in Fig. 1a.
Formally, consider a setting where 𝑛 buyers have independent private valuations ì 𝑉 drawn from a distribution D = D 1 × D 2 × • • • × D 𝑛 . The valuations ì 𝑉 are known to the intermediary, who maps them to a signal 𝜎 via a public signaling scheme Z. Given 𝜎, all agents compute the posterior S over buyer values; note these can now be correlated. The seller then proposes a mechanism M S (comprising allocation and payment rules) which maximizes its expected revenue assuming buyers act in a manner which is ex-post incentive-compatible (IC) and interim individually-rational (IR) given S. If 𝜎 is such that S = D, then M S is Myerson's auction (point 𝑀 in Fig. 1b); on the other hand, if the signal fully reveals ì 𝑉 , then the seller can extract full surplus (i.e., get revenue W * , point 𝐴 in Fig. 1b). Moreover, the seller gets revenue at least R 𝑀 under any signaling scheme, as she can always ignore the signal (see Section 2). Thus any signaling scheme Z must give a point in the shaded triangle with consumer surplus CS(Z) and revenue R (Z), and the maximum possible surplus Opt is achieved at point 𝑂 in Fig. 1b. Now we can ask:
What revenue-CS trade-offs can an information intermediary achieve via signaling? More specifically, what is the maximum possible consumer surplus that is achievable?
In the single-buyer case, the seminal work of Bergemann, Brooks, and Morris [2] completely answer these questions by showing that the entire shaded region is always achievable. In particular, the point 𝑂 is met by a simple signaling scheme where the revenue is exactly R 𝑀 , and the item is always sold thus the mechanism is efficient.
In this work we study the effectiveness of an information intermediary in a multi-buyer (i.e., 𝑛 ≥ 2 buyers) Bayesian auction. In brief, we expose a sharp separation between the single and multi-buyer settings, as in the latter, no signaling scheme can guarantee more than a constant fraction of the optimal consumer surplus (Opt in Fig. 1b). On the positive side, we obtain a novel yet simple signaling scheme with strong approximation guarantees for a wide range of settings. While our main focus is on theoretical results, our work has broader practical relevance. Consider an agency like the FCC with privileged information about bidders in a spectrum auction, or a bid optimizer working for multiple competing clients in an ad-exchange. These intermediaries have private information about the buyers, and can selectively release it to influence the auction. For instance, in an ad exchange, the platform running the exchange (intermediary) typically uses machine learning and advertiser features to infer true valuations. However, the pricing rules are decided by the publishers (seller) and not the exchange. For its own long term viability, the platform clearly has incentives to make both parties ś publisher and advertisers ś as happy as possible, and would therefore like to release information selectively to the publisher in order to maximize advertiser happiness (consumer surplus) while keeping publisher happiness (revenue) at least what it is without its presence. In effect, we use the alternate view of the market segmentation problem in [2] as a special case of a signaling problem where a more informed intermediary works for the benefit of the buyers.
Our work also fits in a broader space of multi-criteria optimization where a third-party platform or government agency can release information about agents to a principal in charge of an activity such as admissions or hiring, so as to trade-off the principal's objective such as maximizing quality of hire, with a societal objective such as fairness or diversity.
We consider a single-item auction with 𝑛 buyers with discrete valuations. We assume the buyer valuations are independent, so
where D 𝑖 has support size K 𝑖 , and the size of the union of the supports is K. We parametrize our results in terms of 𝑛, K 𝑖 , and K.
Our first set of results (Section 3) shows a sharp demarcation between the cases of 𝑛 = 1 and 𝑛 ≥ 2 buyers. In contrast with the former case (where signaling achieves the entire shaded region in Fig. 1b), we show in the latter case, the entire segment 𝐵𝑂 is not achievable; indeed, the only achievable points on segment 𝐴𝑂 are arbitrarily close to 𝐴. Therefore, achieving full welfare requires sacrificing an arbitrarily large fraction of consumer surplus compared to the no-signaling baseline.
Session 7A: Information Design • EC '22, July 11-15, 2022, Boulder, CO, USA Theorem 1.1 (Proved in Section 3). For any given constant 𝜀 > 0, there are instances with 𝑛 = 2 buyers each with K 𝑖 = 2, where any signaling scheme Z under which the revenue-optimal auction obtains full welfare (i.e., allocates to highest-value buyer), has CS(Z) ≤ 𝜀 • CS(D), where CS(D) is the consumer surplus of Myerson's auction without signaling.
We next ask if we can sacrifice on welfare, but raise a consumer surplus arbitrarily close to Opt? We again answer in the negative, and show a lower bound of 2 on the approximation ratio.
Theorem 1.2 (Proved in Section 3). For any constant 𝜀 > 0, there are problem instances with 𝑛 = 2 buyers each with K 𝑖 = 2, where any signaling scheme Z has CS(Z) ≤foot_0 2 + 𝜀 • Opt. We note that the above results are existential impossibility results, and do not depend on the complexity of the signaling scheme. 1 Overall, the negative results in Theorems 1.1 and 1.2 strongly suggest that in this setting, the focus should be on approximating the consumer surplus.
The situation improves in Section 3.3 when we restrict to D 𝑖 that are identical and (discrete-)regular. Here, we first circumvent Theorem 1.1 by showing a simple signaling scheme that achieves the point 𝐵 (i.e., optimal welfare, and same consumer surplus as under Myerson's auction). One problem that remains, however, is that Myerson's auction may have arbitrarily poor CS: for example, if the D 𝑖 are regular, and chosen such that the reserve price is the highest value in the support, then CS = 0, while Opt > 0 (and so the approximation factor of Myerson's auction is unbounded). Indeed, even restricting to MHR priors, one can construct instances where the reserve price is close to the maximum value in the support, leading Myerson's auction to have vanishing CS relative to Opt. This is one reason why getting any non-trivial approximation to Opt is challenging, and we present more discussion in Section 4.1.
In Section 4, we present our main technical result, where we show that when buyers' valuations are drawn from i.i.d. regular distributions, then a simple signaling scheme achieves a constantapproximation to Opt. In more detail, our Rank 𝑡 signaling scheme is based on two simple but critical steps: First, the intermediary can use its knowledge of agent valuations to perform a prescreening step that eliminates all but the top-𝑡 buyers (for a carefully chosen 𝑡). Second, given the top 𝑡 buyers, it can then choose a uniform buyer among this set to serve as a hold-out buyer, who the seller can sell to in case she is unable to raise sufficient revenue from the remaining 𝑡 -1 buyers via an auction; this can be achieved by using the single-buyer signaling scheme of Bergemann et al. [3] on the chosen buyer. Using a combination of these two ideas, we get the following: Theorem 1.3 (Proved in Section 4). When the D 𝑖 's are identical and regular, there is a signaling scheme achieves an 𝑂 (1)-approximation to the optimal consumer surplus Opt, and has computation time polynomial in 𝑛 and K.
The nice feature of Rank 𝑡 is that it generates signals with posteriors that are (non-identical) product distributions, so that the seller's optimal auction is Myerson's auction [19], which is also ex-post IC and IR. This scheme also turns out to achieve Opt for the special case when K = 2 and 𝑛 is arbitrary.
In the full paper [1], we extend this scheme to when the buyers are independent, but not necessarily identical or regular. We obtain the following theorem for this case.
Theorem 1.4 (Proved in the full paper [1]). When the D 𝑖 's are arbitrary, the Rank 𝑡 scheme achieves an 𝑂 min 𝑛 log 𝑛, K 2 -approximation to the optimal consumer surplus Opt, and has computation time polynomial in 𝑛 and K.
For any 𝑛, the optimal signaling scheme for maximizing surplus can be obtained via an infinite-sized linear program (see Eq. ( 2) in Section 3) with variables for every possible signal, i.e., every possible joint distribution over buyer valuations. Further, for each such signal, the quantity of interest is the consumer surplus of the revenue-optimal auction given the signal. For 𝑛 = 1 case, Bergemann et al. show this LP has a special structure in that it admits a basis comprising of łequal-revenue distributionsž containing the revenue-maximizing price (see Section 2.2). Our work shows that this breaks down for optimal auctions with signaling involving 𝑛 ≥ 2 buyers.
To understand why things change dramatically from 𝑛 = 1 to 𝑛 ≥ 2 buyers, in the former case, the optimal mechanism is a simple posted price scheme and its revenue is continuous in the distribution D. However, with multiple buyers, the optimal auction does not have simple structure even for independent buyers (see Algorithm 1), and we need to analyze the consumer surplus of this auction, which can be a discontinuous function of the prior. (See Section 3 for examples.) Further, for correlated buyers, the revenue of the auction itself may not be continuous in the prior! Indeed, a celebrated result of Crémer and McLean [8] shows that slightly perturbing an independent prior to a correlated one can discontinuously increase the revenue to W * , hence decreasing consumer surplus to 0. (See Theorem 2.1 in Section 2.) This makes it tricky to reason about the optimal signaling scheme, leading to the gap between our upper and lower bounds.
In more detail: Our proofs of Theorems 1.1 and 1.2 use a special case of the Crémer-McLean characterization [8]: for 𝑛 = 2 buyers each with K 𝑖 = 2, under any non-independent prior the seller can extract full social surplus as revenue. This lets us focus on signaling schemes where buyers' posterior given each signal are product distributions. Using Myerson's characterization of the optimal auction for discrete valuations [13], we show a structural characterization that reduces the space of optimal signals to a sufficiently simple form, yielding the desired counterexamples. Note that we still need to reason about a large space of possible product distributions as signals, which makes our constructions quite non-trivial.
The technically most interesting result in the paper is the 𝑂 (1)-approximation signaling scheme for i.i.d. buyers (Theorem 1.3 in Section 4). The challenge is the following: Even if we restrict the space of signals so that the posteriors are (non-identical) product distributions, this space is still infinite size, with CS being a discontinuous function in this space. Our signaling scheme in Section 4 balances the trade-off between revealing enough information about valuations so that the item is sold to a high-value buyer, and revealing too much information such that the seller extracts all the surplus. Balancing these is delicate; nevertheless, our final scheme is simple with polynomial computation time and signal complexity. We present more intuition in Section 4.1, where we argue that the guarantee in Theorem 1.3 cannot be achieved in a straightforward fashion.
The general problem of information structure design considers how sharing additional information can influence the outcome of a mechanism. Different variants of this problem have been formulated and studied; we refer the reader to [4,10] for surveys. Of particular importance to us is the Bayesian persuasion problem formulated by Kamenica and Gentzkow [16], where a receiver selects a utilitymaximizing action based on incomplete information about the state of nature. A sender who knows the state of nature can signal side-information to the receiver so that the action taken by the receiver is utility-maximizing for the sender. This general problem has been widely studied in different domains such as monopoly pricing and advertising [2,7,15,22]. For this problem, there is a distinction between existence and computational results, and the work of Dughmi and Xu [12] Session 7A: Information Design • EC '22, July 11-15, 2022, Boulder, CO, USA studies the computational complexity of finding the optimal signaling scheme under different input models.
The restriction of our problem to one buyer is the monopoly pricing problem. Here, the intermediary is the sender whose utility is consumer surplus, and the seller is the receiver whose action space is take-it-or-leave-it prices and whose utility is revenue. Beginning with the work of Bergemann et al. [2], several works [6,9,11,15,17,18,20] have considered various extensions and modifications to this basic problem. Unlike monopoly pricing where the buyer is perfectly informed, in our setting, not only the seller, but also all the buyers are receivers, in the sense that they have imperfect knowledge of the true valuations of other buyers, and modify their respective bidding strategies in response to the intermediary's signal to maximize their own utilities. Our setting is therefore a Bayesian persuasion problem with multiple receivers, and this aspect makes it significantly more complex.
There has been work on signaling in auctions that cannot be modeled as Bayesian persuasion, i.e., in which the common signal is not generated by an intermediary who knows all the true values of the buyers. For instance, in the work of Bergemann and Pesendorfer [5], the auctioneer has perfect information about buyer valuations and controls the precision to which buyers can learn it, and in the work of Fu et al. [14], the seller's signal is drawn from a distribution that is correlated with the buyer's value, In both these works, the goal is to maximize seller revenue. Finally, Shen et al. [21] studies equilibria of optimal auctions when each buyer commits to a signaling scheme with imperfect knowledge of other buyers' valuations, while Bergemann et al. [3] studies equilibria in first price auctions when buyers are provided correlated signals about other buyers' valuations. In contrast with the former, our work considers a richer space of signals via an information intermediary, while compared to the latter, in our setting the seller's mechanism is not fixed, but is instead also a function of the information structure.
We consider Bayesian single-item auctions with 𝑛 buyers, with independent private valuations ì 𝑉 = (𝑉 1 , 𝑉 2 , . . . , 𝑉 𝑛 ) drawn from a known product distribution D = D 1 × • • • × D 𝑛 . Unless otherwise stated, we present our results for the setting in which each D 𝑖 is discrete. We denote by K 𝑖 the size of the support of D 𝑖 , and by K the size of the union of these supports.
For distribution D 𝑖 , we use 𝑓 𝐷 𝑖 to denote its probability mass function, and define
Given any shared prior D ′ on the valuations of the buyers, which in the case of signaling, can be different from D and arbitrarily correlated, the seller runs an optimal (revenue maximizing) auction that satisfies ex-post incentive compatibility and interim individual rationality. The standard description of these constraints is relegated to the full paper [1].
For any prior D ′ , let (R (D ′ ), W (D ′ ), CS(D ′ )) denote the expected revenue, welfare (or total surplus) and consumer surplus under the revenue-maximizing auction. Then we have CS(D ′ ) = W (D ′ ) -R (D ′ ), and:
where 𝑥 * (ì 𝑣) ≥ 0 and 𝜃 * (ì 𝑣) are the allocation rule and the payment rule of the optimal auction given any realized valuation profile ì 𝑣. Our work builds on two special cases ś independent valuations, and full surplus extraction.
the optimal auction has a simple form given by Myerson [19]. For distribution D 𝑖 with support 𝑧 1 < 𝑧 2 < • • • < 𝑧 𝑘 , its virtual value function 𝜑 D 𝑖 is defined as:
If buyer 𝑖 is the only buyer in the system, the optimal auction sets a fixed price, and the buyer buys the item when her valuation is at least this price. The reserve price of D 𝑖 , denoted 𝑟 D 𝑖 is the smallest value 𝑟 in the support of D 𝑖 that maximizes the corresponding revenue 𝑟𝑆 D 𝑖 (𝑟 ). It is easy to check that 𝜑 D 𝑖 (𝑟 D 𝑖 ) ≥ 0.
Throughout this paper, we assume the distributions D 𝑖 are regular, so that 𝜑 D 𝑖 (𝑧) is a nondecreasing function of 𝑧. Therefore, for all 𝑣 < 𝑟 D 𝑖 , we have 𝜑 D 𝑖 (𝑣) < 0. Our results for the non-i.i.d. case also hold when the distributions are non-regular, by using the non-decreasing ironed virtual value function [13,19] instead.
For discrete regular distributions, Myerson's auction takes the form [13] in Algorithm 1. Note that this auction is also ex-post IC and IR.
ALGORITHM 1: Myerson's Auction with prior D and valuations ì 𝑣. Sort the buyers in decreasing order of 𝑞 𝑖 = 𝜑 D 𝑖 (𝑣 𝑖 ). Assume no two values are identical (can be ensured by using a fixed tie-breaking rule). Allocate to the bidder 𝑗 with highest virtual value 𝑞 𝑗 , provided 𝑞 𝑗 ≥ 0. Let 𝑚 be the bidder with second highest virtual value, and let 𝑤 = max(0, 𝑞 𝑚 ). Charge 𝑗 the smallest value 𝑧 in the support of D 𝑗 such that 𝜑 D 𝑗 (𝑧) > 𝑤.
Extracting full surplus as revenue. At the other extreme, a celebrated result of Crémer and McLean [8] shows that for distributions D ′ which are łsufficiently correlatedž, the optimal auction extracts full surplus (i.e., the revenue equals the maximum valuation in each valuation profile). Formally, the result requires that for each agent, their conditional distribution over others' values given their own value is full rank; for our purposes, we require a restriction of their result to 𝑛 = 2 buyers, each with two possible valuations.
). For 𝑛 = 2 buyers, where each buyer 𝑖 has K 𝑖 = 2 and the joint distribution over the valuations is D ′ , the seller (who faces an interim IR constraint) can extract the entire social welfare (i.e. get expected revenue equal to the expected value of the maximum of the buyer's valuations) when D ′ is a correlated (i.e. not independent) distribution.
We next formalize the model of an information intermediary illustrated in Fig. 1a. Since the effect of the intermediary's signal is captured by the resulting posterior distribution over valuations, for ease of notation, we henceforth use łsignalž to refer to a distribution S over valuations.
A signaling scheme Z = {𝛾 𝑞 , S 𝑞 } 𝑞 ∈ [𝑚] comprises a collection of signals (i.e., joint distributions over valuations) S 1 , S 2 , . . . , S 𝑚 and corresponding non-negative weights 𝛾 1 , 𝛾 2 , . . . , 𝛾 𝑚 . The scheme Z is feasible (or łBayes plausiblež [16]) if it satisfies 𝑞 𝛾 𝑞 = 1 and 𝑞 𝛾 𝑞 S 𝑞 = D. The intermediary commits to scheme Z before the auction, and it is known to the seller and all buyers.
The intermediary maps observed valuation profile ì 𝑣 ∼ D to signal S 𝑞 with probability
The seller uses S 𝑞 as the shared prior and runs an optimal auction on the buyers. Note that though D is a product distribution, the {S 𝑞 } can be correlated. Abusing the notations introduced earlier in Section 2.1, we denote the revenue generated by signaling scheme Z as R (Z) = 𝑞 𝛾 𝑞 R (S 𝑞 ), its consumer surplus by CS(Z) = 𝑞 𝛾 𝑞 CS(S 𝑞 ), and its welfare by W (Z) = 𝑞 𝛾 𝑞 W (S 𝑞 ).
When D is a product distribution, the revenue from any signaling scheme must be at least the optimal revenue of Myerson's auction without signaling, R (D). To see this, we note that Myerson's auction on D is ex-post IC and IR. This means that this allocation and payment rule is still a feasible (interim IC and IR) mechanism conditioned on receiving any signal, completing the argument. Therefore, the consumer surplus CS(Z) under any signaling scheme Z is bounded by the difference of the maximum possible welfare W * = E ì 𝑉 ∼D [max 𝑖 𝑉 𝑖 ] and the maximum revenue without signaling R (D). We henceforth denote this bound as Opt, which is defined as follows:
We say that Z is a 𝜏-approximation signaling scheme if CS(Z) ≥ Opt 𝜏 . Our goal is to find the best approximation factor 𝜏 via a signaling scheme whose computation time is polynomial in 𝑛 and K.
In the rest of the paper, we omit the dependence on D when clear from context.
Optimal signaling for a single buyer. For 𝑛 = 1 buyer, Bergemann et al. [2] present a signaling scheme with consumer surplus exactly equal to Opt (i.e., implementing the point 𝑂 in Fig. 1b. Their signaling scheme constructs distributions (signals) S 1 , S 2 , . . . , S 𝑚 and assigns weights 𝛾 1 , 𝛾 2 , . . . , 𝛾 𝑚 to them such that 𝑞 𝛾 𝑞 S 𝑞 = D.
Let prior D takes value 𝑣 𝑖 with probability 𝜂 𝑖 , where 0
In each iteration ℓ, the algorithm constructs an equal revenue distribution S ℓ and subtracts it from the prior D. This equal revenue distribution assigns positive probability 𝜂 𝑖ℓ to 𝑣 𝑖 if 𝜂 𝑖 > 0 and assigns 𝜂 𝑖ℓ = 0 if 𝜂 𝑖 = 0. In S ℓ , the seller raises equal revenue by setting the price to be any of the values 𝑣 𝑖 with 𝜂 𝑖 > 0. It is easy to see that the equal revenue condition specifies a unique distribution S ℓ . Note that since this signal is equal revenue, (we may assume) the seller sets the lowest value as price, so that the item always sells and the consumer surplus is maximum possible.
Let ì 𝜂 ℓ be the probability vector of S ℓ . We set the largest weight 𝛾 ℓ such that ì 𝜂 -𝛾 ℓ ì 𝜂 ℓ ≥ 0. We update D by setting ì 𝜂 to ì 𝜂 -𝛾 ℓ ì 𝜂 ℓ , and increase ℓ by one. We repeat this till the support of D becomes empty. The {𝛾 ℓ , S ℓ } specifies the signaling scheme. We illustrate this procedure by an example.
Example 2.2. Suppose the type space is {1, 2, 3} and D = ⟨ 1 3 , 1 3 , 1 3 ⟩ are the probabilities of these types. The monopoly price is 𝜃 = 2 with revenue R (D) = 4 3 , while the point 𝐴 in Fig. 1b has
; and S 3 = ⟨0, 1, 0⟩ with 𝛾 3 = 1 6 . It is easy to check that the monopoly price for each signal is the lowest price in its support so that the item always sells, and 𝛾 𝑖 R (S 𝑖 ) = 4 3 . Therefore, 𝛾 𝑖 CS(S 𝑖 ) = 2 -4 3 = 2 3 = Opt, which corresponds to point 𝑂 in Fig. 1b. We henceforth use BBM(𝑣, 𝐷) to refer to this scheme when the buyer has valuation distribution 𝐷 and the realized value is 𝑣 ∼ 𝐷. Below we state some critical properties of the BBM scheme which we use in our results.
Lemma 2.3 (Implicit in [2]). For a single buyer with value distribution D (with reserve price 𝑟 D ), the BBM mechanism satisfies the following properties:
(1) For any signal S 𝑞 , 𝜑 S 𝑞 (𝑣) ≥ 0 for all 𝑣 in the support of S 𝑞 .
(
We now prove Theorems 1.1 and 1.2. We note that though our lower bounds assume that the seller runs interim IR and ex-post IC mechanisms, and the intermediary can send arbitrary signals, the same lower bounds hold even when the seller runs ex-post IC and IR mechanisms, provided we restrict the intermediary's signals to induce posteriors that are product distributions.
Our lower bounds are based on a 2-buyer instance illustrated in Fig. 2: given values 𝑎 > 𝑏 > 𝑐 > 𝑑, buyer 1 has value 𝑉 1 ∈ {𝑎, 𝑏} with probabilities 𝛼 and 1 -𝛼 respectively, while buyer 2 has value 𝑉 2 ∈ {𝑐, 𝑑 } with probabilities 𝛽 and 1 -𝛽 respectively. We choose 𝛼𝑎 = 𝑏 and 𝛽𝑐 = 𝑑; thus, the virtual values satisfy: 𝜑 1 (𝑎) = 𝑎, 𝜑 2 (𝑐) = 𝑐, and 𝜑 1 (𝑏) = 𝜑 2 (𝑑) = 0. Call this distribution D.
Characterization of optimal signaling. By Theorem 2.1, we know any signal that correlates the buyers raises zero consumer surplus. Therefore, the only signals S of interest are those under which buyer values are independent. Abusing notation we denote such a signal as 𝑠 = (𝛼 ′ , 𝛽 ′ ), where Pr[𝑣 1 = 𝑎] = 𝛼 ′ and Pr[𝑣 2 = 𝑐] = 𝛽 ′ . Note that in this instance, for a signal to get maximum welfare the resulting optimal mechanism must always award buyer 1, and for non-zero consumer surplus it must award the item to buyer 1 at price 𝑏, or buyer 2 at price 𝑑.
Let CS(𝑠) denote the consumer surplus under any such a signal 𝑠, and 𝜑 1 (𝑏 |𝑠) and 𝜑 2 (𝑑 |𝑠) denote the new virtual values (note that by definition, 𝜑 1 (𝑎|𝑠) = 𝑎 and 𝜑 2 (𝑐 |𝑠) = 𝑐 under any signal 𝑠 with 𝛼 ′ , 𝛽 ′ > 0). We can use Myerson's characterization (Section 2.1) to exhaustively characterize the resulting optimal mechanisms as a function of (𝜑 1 (𝑏 |𝑠), 𝜑 2 (𝑑 |𝑠)): Proposition 3.1. Conditioned on receiving a signal 𝑠, we have the following cases: (1) If 𝜑 1 (𝑏) ≥ 𝑐, then the optimal mechanism is to sell to Buyer 1 at price 𝑏. CS(𝑠) = (𝑎 -𝑏)𝛼 ′ .
(2) If 𝜑 2 (𝑑) ≥ max(0, 𝜑 1 (𝑏)), then the optimal mechanism is to try selling to Buyer 1 at price 𝑎 then to Buyer 2 at price 𝑑. CS(𝑠) = (1 -𝛼 ′ )𝛽 ′ (𝑐 -𝑑).
(3) If 𝜑 1 (𝑏) ≤ 0 and 𝜑 2 (𝑑) ≤ 0, then the optimal mechanism is to try selling to Buyer 1 at price 𝑎 then to Buyer 2 at price 𝑐. CS(𝑠) = 0. (4) If 0 ≤ 𝜑 1 (𝑏) ≤ 𝑐 and 𝜑 2 (𝑑) ≤ 𝜑 1 (𝑏), then the optimal mechanism is to sell to Buyer 1 at price 𝑏 if Buyer 2 has valuation 𝑑; otherwise, it tries selling to Buyer 1 at price 𝑎 then to Buyer 2 at price 𝑐. CS(𝑠) = 𝛼 ′ (1 -𝛽 ′ ) (𝑎 -𝑏).
Our main insight, however, is that the setting can be further simplified to get the following structural property for the optimal signaling scheme. Theorem 3.2 (Structural Theorem). In an optimal signaling scheme, the only signals 𝑠 = (𝛼 ′ , 𝛽 ′ ) that raise non-zero consumer surplus have the following form:
( Proof. Recall that we restrict ourselves to signals S under which the buyer valuations remain independent. Any such signal can be alternately written as 𝑠 = (𝛼 ′ , 𝛽 ′ ) where 𝛼 ′ = Pr[𝑣 1 = 𝑎] and Session 7A: Information Design • EC '22, July 11-15, 2022, Boulder, CO, USA
For ease of notation, we henceforth drop the conditioning of virtual valuations on signal 𝑠 (i.e., write 𝜑 (•) for 𝜑 (•|𝑠)) when clear from context.
Next, let 𝛾 𝑠 denote the weight of any signal 𝑠 = (𝛼 ′ , 𝛽 ′ ). The signaling scheme that maximizes consumer surplus is the solution to the following linear program written over signals 𝑠 = (𝛼 ′ , 𝛽 ′ ):
We examine the cases in Proposition 3.1 with positive consumer surplus, and characterize the optimal solution:
• In Case (1), we have 𝜑 1 (𝑏) = 𝑐. To see this, consider any signal 𝑠 with 𝜑 1 (𝑏) > 𝑐. Suppose we increase 𝛼 ′ and decrease 𝛾 𝑠 while preserving the product 𝛼 ′ 𝛾 𝑠 . Since 𝛾 𝑠 CS(𝑠) = 𝛾 𝑠 𝛼 ′ (𝑎 -𝑏), this is preserved by the change. Therefore, the objective of LP ( 2) is preserved, and so are the first two constraints. Further, since (1 -𝛼 ′ ) and 𝛾 𝑠 decrease, this only makes the third and fourth constraints more feasible. This transformation decreases 𝜑 1 (𝑏). • In Case ( 2) and ( 4), we have 𝜑 2 (𝑑) = 𝜑 1 (𝑏). It does not help to make them unequal by a similar argument as above: In case (2), if 𝜑 2 (𝑑) > 𝜑 1 (𝑏), we can increase 𝛽 ′ while preserving 𝛾 𝑠 𝛽 ′ . Since 𝛾 𝑠 CS(𝑠) = 𝛾 𝑠 (1 -𝛼 ′ )𝛽 ′ (𝑐 -𝑑), this does not change the contribution to the objective of LP (2), and preserves all constraints. This transformation decreases 𝜑 2 (𝑑). In case (4), if 𝜑 2 (𝑑) < 𝜑 1 (𝑏), we can increase 𝛼 ′ while preserving 𝛾 𝑠 𝛼 ′ . Since 𝛾 𝑠 CS(𝑠) = 𝛾 𝑠 𝛼 ′ (1 -𝛽 ′ ) (𝑎 -𝑏), this does not change the contribution to the objective of LP (2), and preserves all constraints. This transformation decreases 𝜑 1 (𝑏).
Therefore, the only two types of signals 𝑠 that give positive CS are
As (1 -𝛽 ′ ) (𝑏 -𝑑) ≥ 0, we have
Notice that in Case (2'), we have
Thus, the two types of signals 𝑠 that give positive CS become
Using the above structural theorem, the proofs of Theorems 1.1 and 1.2 follow by different choices of the parameters (𝑎, 𝑏, 𝑐, 𝑑). Suppose the virtual values of 𝑏 and 𝑑 are slightly above zero with 𝜑 1 (𝑏) > 𝜑 2 (𝑑) so that Case (4) in Proposition 3.1 is uniquely optimal for the seller. The optimal auction generates consumer surplus
Session 7A: Information Design • EC '22, July 11-15, 2022, Boulder, CO, USA
To prove Theorem 1.1, we set 𝑏 → 𝑐 + . 2 Now in Proposition 3.1, in Case (1), we must have 𝛼 ′ → 0 + since 𝑏 → 𝑐 + , so that CS → 0. Also if 𝛼 ′ = 1 in a signal then CS = 0 here. The only other signal where the item is allocated to the higher bidder is in Case (4) when 𝛽 ′ = 0. Let 𝛾 denote the probability of the signal of this type 𝑠 = (𝛼 ′ , 0). (Having multiple signals of this form gives the same CS as having a single signal as their average.) Since 𝜑 1 (𝑏) ≥ 𝜑 2 (𝑑), we have 𝛼 ′ ≤ 𝑏 -𝑑 𝑎-𝑑 . By the constraints of LP (2), we have:
which simplifies to 𝛾 ≤ (𝑎-𝑑 ) • (𝑐 -𝑑 )
. The consumer surplus in this case is therefore:
Setting 𝑑 = 1 -𝜀 2 𝑏 and combining with the fact that CS → 0 in Case (1), we have the consumer surplus of any efficient signaling, CS → 𝜀 2 • CS(D) so CS < 𝜀 • CS(D). ) gives the same CS as having a single signal as their average.) Denoting the valuation of the first buyer by 𝑣 1 and the second buyer by 𝑣 2 , the constraints in LP (2) imply the two constraints:
2 𝜑 1 (𝑏 ) -𝜑 2 (𝑑 ) and 𝜑 2 (𝑑 ) can be arbitrarily small as long as positive, so we take the limits for them first, i.e., we are calculating lim 𝑏→𝑐 + lim 𝜑 2 (𝑑 )→0 + ,𝜑 1 (𝑏)→𝜑 2 (𝑑 ) + CS in the following part of the proof. This allows us to treat 𝛼 = 𝑏 𝑎 and 𝛽 = 𝑑 𝑐 in calculating (1 -𝛼 ) (1 -𝛽 ), as 𝛼 and 𝛽 are not infinitesimally close to 1 for any fixed 𝜀. (We will define 𝑑 = (1 -𝜀/2)𝑏.)
The total consumer surplus therefore is:
Here the second inequality follows from Constraint (I), and 𝛼 ′ 1 < 1 2 by the condition of (1'). The third inequality uses the implication of
) . The fourth inequality uses Constraint (II). This establishes a lower bound of 2, since Opt = 2𝛿 2 (1 + 𝑜 (1)).
We now ask if there are cases where we can circumvent Theorem 1.1 and maximize welfare while ensuring at least as much surplus as Myerson's auction (that is, achieve a point on the line 𝐵𝑂 in Fig. 1b). Note that Theorem 1.1 rules this out for non-i.i.d. distributions. Surprisingly, however, for i.i.d. regular distributions D 𝑖 , the following simple signaling scheme turns out to be sufficient for achieving point 𝐵 in Fig. 1b. Morally this shows why our lower bound constructions are delicate.
Suppose the common reserve price of D 𝑖 is 𝑟 , and the maximum value of any buyer is 𝑣 𝑚 .
(1) If 𝑣 𝑚 < 𝑟 , then the intermediary reveals 𝑣 𝑚 and the identity of the highest buyer to the seller, who then sells to this bidder at price 𝑣 𝑚 . (2) If 𝑣 𝑚 ≥ 𝑟 , the intermediary only reveals the information that some buyer has value ≥ 𝑟 (but does not reveal either 𝑣 𝑚 or the identity of the highest bidder). In this case, though the posterior is not a product distribution anymore, it can be shown that the seller's optimal auction remains the second price auction with reserve 𝑟 .foot_2 It is easy to check that the item always sells to the highest buyer, and the CS is exactly the same as in Myerson's auction without signaling, thereby achieving point 𝐵. Note however that this scheme does not give any guarantees on approximating CS itself, since the surplus of Myerson's auction is not an approximation to Opt. The question of approximating Opt is much more challenging even for the i.i.d. regular setting, and this is what we focus on in the next section.
In this section, we present our main result (Theorem 1.3): An 𝑂 (1)-approximation to Opt when the buyers' valuation distributions D 𝑖 are identical and regular.
Recall we start with a product distribution
be the supports of value distributions. R (D) denotes the revenue of the optimal auction (Algorithm 1) on D, and
When D 𝑖 's are identical and regular, since the highest virtual-value and highest value buyers coincide, the optimal auction (Algorithm 1) assigns the item to the buyer with highest value if this value is above the common reserve price. Therefore, we decompose Opt into two components:
• Myerson's surplus: The CS generated by Myerson's auction, denoted by CS(D).
• Non-allocation surplus: The loss in CS due to Myerson's auction not allocating the item, denoted by CS 0 .
We therefore have Opt = CS(D) + CS 0 . In the remainder, we will present an 𝑂 (1)-approximation for the non-allocation surplus CS 0 , which will imply Theorem 1.3 when CS 0 ≥ CS(D). (When CS(D) > CS 0 , sending no signal is already a 2-approximation.)
Our approximation bound for the non-allocation surplus will also apply when D 𝑖 are independent but not necessarily identical, which will be required for showing Theorem 1.4. Therefore, in the sequel, we will proceed assuming the more general case that D 𝑖 's are not necessarily identical, and derive signaling schemes that approximate the non-allocation surplus CS 0 for this case.
We denote a realization from D by ì
for any buyer 𝑖, where 𝑟 D 𝑖 is the reserve price of D 𝑖 . Let 𝑌 𝑖 = D 𝑖 |<𝑟 D 𝑖 denote the distribution of D 𝑖 conditioned on being smaller than 𝑟 D 𝑖 . Suppose we draw a sample independently from each distribution 𝑌 𝑖 . Let 𝑍 ℓ denote the distribution for the ℓ th largest value among these 𝑛 draws.
We first derive an expression for CS 0 .
Lemma 4.1.
Note that CS 0 is the expected surplus lost due to not allocating the item in Myerson's mechanism. This happens only when all realized values are below their corresponding reserve price. In this case, the value lost is the maximum valuation, since this value contributes to the welfare, and the revenue raised is zero. Therefore, we have:
where the expectation is over ì 𝑣 ∼ D. This is equal to 𝑃
Vanilla Signaling Schemes. Before presenting our general signaling scheme, it is instructive to first consider simpler schemes to understand the challenges posed by this problem. One possible scheme is to pick a random buyer and apply the single-buyer BBM signaling scheme defined in Section 2 to it. Denote this buyer by 𝑖. Such a single-buyer signaling scheme will construct the set of BBM signals for buyer 𝑖 by decomposing D 𝑖 and pretending the other buyers don't exist. Given the valuation 𝑣 𝑖 ∼ D 𝑖 of this buyer, the scheme will send a signal BBM(𝑣 𝑖 , D 𝑖 ) just as in single-buyer case, and reveal the identity of this buyer. There is no signal sent for the other buyers, so that the seller's information for 𝑗 ≠ 𝑖 is their prior D 𝑗 .
The nice property of the BBM signaling scheme is that the virtual value of buyer 𝑖 is always nonnegative (Lemma 2.3). Therefore, in the event when all buyers 𝑗 ≠ 𝑖 have values 𝑣 𝑗 < 𝑟 D 𝑗 (so that their virtual values are negative), the seller allocates the item to 𝑖. Since 𝑣 𝑖 is independent of other buyers' values, the mechanism therefore behaves exactly as BBM(𝑣 𝑖 , D 𝑖 ) from the perspective of buyer 𝑖. In other words, with probability 𝑗≠𝑖 𝑝 𝑗 , we generate the single-buyer CS from Lemma 2.3, which is at least:
Session 7A: Information Design • EC '22, July 11-15, 2022, Boulder, CO, USA Since buyer 𝑖 is a randomly chosen buyer, the overall CS generated is:
where 𝑃 = 𝑛 𝑗=1 𝑝 𝑗 . Therefore, comparing the expression above with that in Lemma 4.1, this scheme yields an 𝑛-approximation to CS 0 . Further, we can construct identical regular distributions for which the expected value of the max is comparable to the expected value of the sum, that is,
). Therefore, this analysis cannot be improved. On the other hand, the above scheme does achieve CS = Opt for two-valued i.i.d. distributions (K = 2 and arbitrary 𝑛). To see this, assume the support is 𝑎 < 𝑏, and let 𝑞 = Pr[D 𝑖 = 𝑎]. If the reserve price is 𝑎, Myerson's auction is already efficient, that is, CS(D) = Opt; else Myerson's auction has CS(D) = 0. We now have 𝑍 𝑖 = 𝑎 for all 𝑖 and 𝑝 𝑖 = 𝑞, so that the above scheme has surplus 𝑞 𝑛 𝑎 = 𝑞 𝑛 E[𝑍 1 ] = CS 0 = Opt. Therefore, in either case, we extract CS = Opt. Interestingly, this also shows that our lower bounds in Theorems 1.1 and 1.2 do require non-i.i.d. distributions when each K 𝑖 = 2 regardless of the number 𝑛 of buyers.
Moving beyond the K = 2 setting to general K and 𝑛, it is tempting to run the BBM signaling scheme directly on the buyer with highest value, hoping to extract surplus 𝑃 E[𝑍 1 ]. However, this requires revealing the identity of the highest buyer to the seller, since the signaling scheme itself is public knowledge. But if the seller knows the identity of the highest buyer, she can always increase the reserve price to be the second highest bid. In other words, the posterior of the highest buyer is truncated at 𝑍 2 . This case needs a more careful construction of the signal and analysis, since the event of a buyer being the largest and hence BBM being applied to it is now correlated with the surplus this buyer generates in BBM. We perform this construction and analysis in Lemma 4.3. Intuitively, signaling using BBM on the largest buyer will only yield CS ≥ 𝑃 E[𝑍 1 -𝑍 2 ], which is again an Ω(𝑛)-approximation to 𝑃 E[𝑍 1 ].
Our signaling scheme in the next section chooses a middle ground between these extremes ś we will choose a rank 𝑡 ∈ {1, 2, . . . , 𝑛} carefully, and choose a buyer whose value lies in the top 𝑡 ranks at random. We will then perform the single-buyer BBM scheme on this buyer as we describe below. Surprisingly, this improves the naïve 𝑛-approximation to an 𝑂 (1)-approximation!
We now introduce the family of signaling schemes Rank 𝑡 . We will derive a lower bound for the CS obtained by these schemes in our key lemma, Lemma 4.3. As mentioned before, since this scheme will also form the basic subroutine for the non-i.i.d. case (Theorem 1.4), we present this scheme assuming D 𝑖 can be non-identical.
Recall the definitions of 𝑝 𝑖 , 𝑟 D 𝑖 , 𝑌 𝑖 , 𝑍 ℓ from above. In order to define the signaling scheme, we need an additional definition. For agent 𝑖 with 𝑉 𝑖 ∼ D 𝑖 , we use D 𝑖 |>𝑎 to denote the conditional distribution of 𝑉 𝑖 given 𝑉 𝑖 > 𝑎, and D 𝑖 |<𝑎 to denote the conditional distribution of 𝑉 𝑖 given 𝑉 𝑖 < 𝑎. Moreover, we use D 𝑖 |>𝑎 -𝑏 to denote the distribution of 𝑉 𝑖 -𝑏 given 𝑉 𝑖 > 𝑎; we refer to it as the distribution of 𝑉 𝑖 truncated at 𝑎 and reduced by 𝑏.
The following result relates the reserve price of the truncated and the original distributions. The Rank 𝑡 signaling scheme. We now present the family of signaling schemes Rank 𝑡 parameterized by the rank 𝑡 ∈ {1, . . . , 𝑛}. For any realized joint valuation profile ì 𝑣 = (𝑣 1 , 𝑣 2 , . . . , 𝑣 𝑛 ), the signal sent by Rank 𝑡 consists of two parts. In the first part, Rank 𝑡 observes ì 𝑣 and outputs (𝑣 • ,𝑇 ), where 𝑣 • is the value of (𝑡 + 1) st largest realized value (or 0 when 𝑡 = 𝑛), and 𝑇 is the subset of buyers with realized value strictly greater than 𝑣 • . For the second part of the signal, Rank 𝑡 chooses a buyer 𝑗 uniformly at random from 𝑇 , and computes her excess distribution D 𝑗 |>𝑣 • -𝑣 • . It then reveals both the identity of 𝑗, as well as the signal BBM(𝑣 𝑗 -𝑣 • , D 𝑗 |>𝑣 • -𝑣 • ) generated by the single-buyer BBM scheme on a buyer with value distribution D 𝑗 |>𝑣 • -𝑣 • . The scheme is formalized in Algorithm 2.
Optimal mechanism under Rank 𝑡 . Conditioned on receiving the signal generated by Rank 𝑡 , the seller is guaranteed a revenue of 𝑣 • from the (𝑡 + 1) st largest buyer, and knows that only buyers in 𝑇 can pay more than 𝑣 • . The seller can now charge at least 𝑣 • to any buyer in 𝑇 , and can further run an auction over the excess value of buyers in 𝑇 , where for buyer 𝑖 ∈ 𝑇 , her excess value has distribution D ′ 𝑖 = D 𝑖 |>𝑣 • -𝑣 • . Note that for any buyer 𝑖 ∈ 𝑇 except the randomly chosen buyer 𝑗, a value drawn from D ′ 𝑖 represents how much more than 𝑣 • she is willing to pay. Moreover, distributions D ′ 𝑖 are independent, and also, since the identity of 𝑗 is chosen uniformly at random, the BBM scheme modifies the distribution of buyer 𝑗 in a fashion that is independent of D ′ 𝑖 . By Lemma 2.3, we know that the BBM scheme ensures the virtual value of buyer 𝑗 is always non-negative. From the characterization of the optimal auction [13,19], since the item is always allocated to the highest virtual value buyer as long as this value is non-negative, the item will always be allocated to buyer 𝑗 if all other buyers 𝑖 ∈ 𝑇 , 𝑖 ≠ 𝑗 have excess values 𝑣 𝑖 -𝑣 Consumer surplus under Rank 𝑡 . We require the following key lemma, that gives a lower bound for the consumer surplus generated under Rank 𝑡 . This lemma forms the crux of our subsequent analysis, helping us quantify how the BBM signal recovers much of CS lost by Myerson's auction. The difficulty in proving it arises because the random choice of buyer 𝑗 in Algorithm 2 is correlated with its rank, which in turn is correlated with its winning the auction and the surplus it generates in BBM. We get around this correlation by carefully coupling the surplus generated when buyer values are above the reserve with the order statistics of buyer valuations below the reserve. Lemma 4.3. For 1 ≤ 𝑡 ≤ 𝑛, the consumer surplus of Rank 𝑡 satisfies:
Session 7A: Information Design To bound Alg, we also need to simplify the term E[𝑍 1 | 𝑍 1 ≥ 𝑢 + ∧ 𝑍 2 ≤ 𝑢 -]. For this, let 𝑌 1 , . . . , 𝑌 𝑛 be independent draws from 𝑌 . We have:
Here, the first equality follows since any 𝑌 𝑖 is equally likely to the maximum value, and the third equality follows by the independence of 𝑌 𝑖 's. Putting all this together, we bound Alg as:
where the last inequality uses 𝑛 • Pr[𝑌 ≥ 𝑢 + ] ≤ 4. □
We next bound Core and the proof is relegated to the full paper [1]. This proof will crucially use the Θ (via Lemma 4.7).
Note that our Rank 𝑡 mechanism can be viewed as a screening procedure ś the intermediary only allows a fixed number of high-value bidders to bid. When the intermediary is an independent (typically, governmental) agency, such screening would map to łpre-certifyingž bidders entering into private auctions. Similarly, when real-estate agencies have agents representing both sellers and buyers, they could (and often do) recommend a particular listing only to a chosen set of buyers based on better knowing their utilities. Therefore, as a side-effect, our procedures yield realistic mechanisms for an intermediary to increase surplus for both buyers and the seller.
In terms of open questions, beyond improving the lower and upper bounds in our specific setting (both existence and computational), it would be interesting to explore the equilibria in optimal auctions when the intermediary can send different signals to the seller and to the buyers, much like in [3,21]. At an even higher level, our work can be considered a special case of a larger problem of information intermediaries for multi-agent mechanisms. As mentioned before, in our case, the optimal auction is the mechanism, and the intermediary can change the information to this mechanism in order to achieve łfairnessž between producer and consumer surplus. It would be interesting to explore the question of achieving fairness by selectively regulating information to a black-box optimizer or mechanism in more general settings.
Our proofs also imply the same lower bounds when the seller is constrained to run an ex-post IR mechanism, provided the intermediary's signals induce a product-form posterior distribution.Session 7A: Information Design • EC'22,
2022, Boulder, CO, USA
Note this is the only case when the seller gets non-zero revenue in the optimal auction for the original product distribution. Suppose for the purpose of contradiction that the seller can do better for this posterior, she can also do better than the optimal auction for the original distribution.