1 Introduction

Mechanism design is an area of economics where optimization is ubiquitous. The present paper aims to contribute to the interface of economics/mechanism design and optimization by investigating optimal pricing mechanisms for an indivisible object in a single seller/single buyer context where buyer valuations and their distribution, assumed to be discrete, are unknown to the seller in a Knightian uncertainty context. As in Bergemann and Schlag [8, 9], we relax the common priors assumption pervasive in the literature (i.e., the common priors assumption states that the buyer valuations, while not known to the seller, are drawn from a known distribution) and we assume that the distribution of valuations is not known to the seller. However, the seller, while risk neutral, is averse to any imprecision in the distribution in the spirit of Gilboa and Schmeidler [15]. In other words, the seller evaluates each action by its minimum expected revenue across all priors. He/she considers a set of distributions, and wishes to design a mechanism that is optimal in a worst-case sense, i.e., he/she maximizes the worst-case expected revenue with respect to nature/adversary’s choice of distribution.

We use the first m positive integers to denote the type of a buyer, and the mapping \(t \in \{t(1),t(2),\ldots ,t(m)\}\) from the first m positive integers to positive reals (we assume \(t(1)< t(2)< \cdots < t(m)\)) represents the m possible valuations of the buyer, where \(t(1) = {\mathbf k}\) and \(t(m)=M\) with \(t(i) = t(i-1) + \frac{(M-{\mathbf k})}{m-1} \) for \(i=2,\ldots ,m\). The symbol f represents the discrete probability mass from which types are drawn. For ease of reference we denote by \(\Delta \) the ratio \(\frac{(M-{\mathbf k})}{m-1}\). We exclude from our model marginal production costs. Hence we assume that either we are dealing with sales after the good has been produced, or a scenario where the seller does not attach any value to the good.

By virtue of the Revelation Principle [21] the seller wishes to optimally choose two discrete functions p (for price) and A (for allocation), both functions of type i, which determine a direct selling mechanism. In other words, the seller declares a price \(p_i\) and a quantity allocation \( A_i\) for each type i, where \(i \in \{1,\ldots ,m\}\). Thus, the problem of pricing the indivisible good is formulated as the following optimization problem. We define the decision variables \(p_i\) for all \(i \in \{1,\ldots ,m\}\) for the price quoted by the seller to a buyer of type i, in addition to the allocation variables \( A_i \in \{0,1\}\), i.e., the allocation variable represents whether or not the buyer gets the good. However, in the sequel we shall treat the allocation variables as continuous, i.e., we have \( A_i \in [0,1]\) in order to deal with the resulting optimization as a linear optimization problem. This is not a severe limitation since in three of our four cases of ambiguity specification we shall obtain binary allocations in the optimal solutions. When optimal allocation values fail to be binary valued we interpret the resulting value as the probability of a buyer getting the object. The utility of an agent declaring type i with valuation t(i) is equal to \(t(i) A_i - p_i\).

The seller’s goal is to maximize the expected profits from the sale:

$$\begin{aligned} \sum _{i=1}^m f_i p_i \end{aligned}$$
(1)

under the restrictions of Incentive Compatibility (IC), Individual Rationality (IR) and constraints on the allocation variables \(A_{i}\) that are, respectively:

$$\begin{aligned} t(i) ( A_i - A_j)\ge & {} p_i - p_j,\; \forall i,j \in \{1,\ldots ,m\} \end{aligned}$$
(2)
$$\begin{aligned} t(i) \cdot A_i - p_i\ge & {} 0,\;\forall i \in \{1,\ldots ,m\}. \end{aligned}$$
(3)
$$\begin{aligned} 0 \le A_{i}\le & {} 1,\;\forall i \in \{1,\ldots ,m\}. \end{aligned}$$
(4)

The constraint (IC) ensures that the utility of the agent that declares his/her type truthfully is at least as large as the utility derived from reporting a different type. The constraint (IR) is to ensure that the minimum (reservation) utility of any buyer of any type is at least zero, which leads to ensuring participation of the buyers into the mechanism.

In summary, the seller, with full knowledge of the probability mass f, seeks a pair \(p_i \ge 0, A_i \in [0,1]\) for each type \(i \in \{1,\ldots ,m\}\) that maximizes (1) under the restrictions (2)–(3). We can always define a dummy type \(i=0\) with \({A}_0=p_0 = 0\) and incorporate constraint (3) into (2); see [24]. Now using the development in [24] we have that for fixed \(A_i\), \(i \in \{1,\ldots ,m\}\), the inequalities for incentive compatibility

$$\begin{aligned} t(i) (A_i - A_j) \ge p_i-p_j, \forall i,j \in \{1,\ldots ,m\} \end{aligned}$$

hold for all \(p_i\), \(i \in \{1,\ldots ,m\}\) if and only if \(A_i\) is monotone non-decreasing in i by the theory of duality applied to the shortest path problem; see chapters 3 and 4 of [24] or [25] for an in-depth analysis of shortest path duality. Furthermore, at optimality one has

$$\begin{aligned} p_i = t(i) A_i - \Delta \sum _{j=1}^{i-1} A_j. \end{aligned}$$

For future ease of reference the set SP is defined as

Therefore, the problem of maximizing (1) under the restrictions (2)–(3) is equivalently posed as maximizing (1) under the restriction \((p,A) \in SP\).

In the continuous types case, it is well-known that the optimal mechanism here is a posted price mechanism, where there exists a cut-off price \(p^*\) such that any buyer with valuation above \(p^*\) or higher gets the object by paying the posted price \(p^*\) (see e.g. Chapter 2 of [11]). Translated to a discrete type spaceFootnote 1 the optimal mechanism is a solution of the form \(p_i = p\) and \(A_i=1\), for all \(i=i^*,\ldots ,m\), and zero everywhere else. This is the simplest possible direct mechanism that is taught in elementary microeconomics: set a price p and tell the buyer he can have the good if he is willing to pay the price p. Suppose the seller picks this procedure the question is now to decide the price he/she should choose. Buyer will purchase if his evaluation is at least as large as p. The probability of this event is \(1-F(p)\) (assuming p is a continuous random variable and F is its cumulative distribution function). Thus, expected revenue is \(p(1-F(p))\). Choose p to maximize this. Solving the sufficient first-order condition (if \(p(1-F(p))\) is concave), one obtains the posted price; see [23] for a complete treatment of pricing. The aforementioned posted price mechanism corresponds simply to a discrete analog of the previous argument.

Against this background we shall consider the following problem

$$\begin{aligned} \max _{p,A \in SP} \min _{f \in P} p^{T}f \end{aligned}$$

where P is a set of ambiguity for the prior f (uncertainty set in the jargon of robust optimization [5]). A Revelation Principle ensuring that the above formulation is valid is given in the Appendix. For more information on the Revelation Principle in ambiguity averse mechanism design, the reader is referred to e.g., [18]. We emphasize that the present paper restricts attention to deterministic mechanisms. We shall consider four choices for P: (1) a uniform box, i.e., a set where each \(f_i\) is constrained to be between two extreme values l and u, and (2) a set of distributions with mean valuation fixed to \(\alpha \), (3) a set of distributions with the mean valuation equal to \(\alpha \) and variance of valuations equal to \(\sigma ^2\). We refer to these cases as the uniform box ambiguity, the mean constrained ambiguity, and the mean-variance constrained ambiguity, respectively. We also consider a fourth representation of ambiguity, where a perturbation set around a reference prior is specified, and a worst-case solution that protects against ambiguity with respect to this ambiguity set is sought.

1.1 Related literature

The subject of this paper was inspired by the progress in robust optimization, a research effort initiated by Ben-Tal and Nemirovski [4, 5] where uncertain parameters of convex optimization problems were treated in a worst-case framework after confining the data in suitable uncertainty sets leading to tractable optimization problems. The search for robustness is not entirely new in mechanism design. In fact, robust mechanism design research was initiated with a paper by Bergemann and Morris [6] where the common knowledge assumptions were relaxed. An in-depth review can be found in [7]. More recent contributions include Bergemann and Schlag [8, 9] where the problem of a max-min utility seller with imperfect information about the valuation distribution of the buyer is considered and optimal pricing schemes are investigated, Auster [1] where a privately informed seller is assumed in the framework of [9], Bandi and Bertsimas [2, 3] where a robust optimization approach is applied in the context of auction design, Hartline and Karlin [16] where prior-free optimal mechanisms are studied, and Wolitzky [26] where the buyer and the seller know only the mean of each other’s valuations. In a similar vein, a recent paper by Kos and Messner [17], independently from our work, studies the optimal trading rule (without the mechanism design framework) where the only information about the valuation of the buyer is the mean confined to an interval. Kos and Messner [17] show that in this case the seller will be restricted to a zero pay-off, whereas if he/she has access to more information (e.g., the variance or upper bound on the support) he/she can attain a positive pay-off under a randomization of prices in some interval. They also consider the case where in addition to confining the mean of the valuation distribution to an interval the variance is also restricted to take values in a given interval. Again, in that case the unique optimal strategy is a randomized pricing strategy over some interval. An informative discussion of randomization over posted prices and connection to incentive compatible and individually rational mechanisms is also contained in [17].

Some of the many connections between optimization theory and mechanism design were exposed by Vohra [25]. In particular, Vohra [25] showed how to derive the classical optimal auction design result due to Nobel laureate Myerson [21] using duality theory of linear programming, and polymatroid theory. The present paper aims to continue in this vein, exploring connections between optimization and economics by studying a basic problem of economic mechanism design under the lens of robust optimization with a slight twist where the uncertain data is the probability distribution itself.

Closest to our work, Bergemann and Schlag [8] study the problem of optimal pricing for a monopoly seller facing an unknown prior distribution for the buyer’s demand which can take values in a continuous interval [v,1]. The seller has a cost of production c, or a value attached to the good. Using the min-max regret and max-min utility criteria, the optimal (random) pricing strategy is characterized as well as the worst-case demand scenario. In a companion paper [9], the authors examine the same problem under the setting that a given prior may be subject to perturbation confined to a suitable set defined using the Prohorov metric in a continuous valuation environment. They establish that the profit minimizing distribution is independent of the price decision of the seller. In consequence, the seller maximizes profits by choosing the optimal deterministic price under the worst-case distribution. The afore-mentioned result is close to our findings in Sect. 2 where we also establish a worst-case prior independent of the optimal mechanism chosen by the seller. It is also shown in [9] that for every positive value of a perturbation parameter, there exists a pair of worst-case demand and price which is a saddle point of the max-min problem. In comparison, in Sect. 5 Theorem 3 we have shown that for every value of a perturbation parameter (our perturbation metric is the Euclidean metric) under a threshold, the posted price mechanism which is optimal for the reference prior retains its optimality.

In a recent and notable research program, Bandi and Bertsimas [2, 3] study optimal auction design (among other well-known problems of stochastic analysis such as queuing theory) where buyer valuations are not treated as random variables but rather as uncertain data restricted to lie in suitable uncertainty sets. They construct uncertainty sets for buyer valuations derived from historical data and consistent with axioms of probability theory. They work with dominant strategy incentive compatible mechanisms, and derive an algorithm for computing the optimal reserve price in an English auction setting. Their algorithm is shown experimentally to give improved revenues compared to the classical probabilistic approach. Our work differs from the Bandi-Bertsimas setting in that we treat the prior distribution as uncertain (valuations are assumed known) whereas they confine buyer valuations to uncertainty sets. We also consider a simpler setting with a single buyer while they deal with an auction framework with different specifications (e.g., budget constrained bidders). Hartline and Karlin [16] also study auctions after removing the common prior assumption. They derive approximately optimal mechanisms that are prior-free in a worst-case framework.

Other related work includes [10, 12, 14, 18] where more complex settings are assumed. Lopomo et al. [18] consider mechanism design problems with Knightian uncertainty formalized using incomplete preferences. Every type has a different set of beliefs on uncertain states of the world which affect her expected utility. They develop different incentive compatibility notions under ambiguity, namely maximal incentive compatibility and optimal incentive compatibility. They show in a continuum of types model that optimal incentive compatibility is equivalent to ex-post incentive compatibility. In a related study Bodoh-Creed [10] develops a payoff equivalence theorem for mechanisms with ambiguity averse participants in the sense of Gilboa and Schmeidler [15]. The payoff equivalence result is used to characterize explicitly the revenue maximizing private value auction mechanism for agents with arbitrary forms of ambiguous beliefs. Dong [14] considers the impact of ambiguity aversion of bidders on their bidding strategies in four classical auction mechanisms. Boze et al. [12] study the optimal auction problem allowing for ambiguity about the distribution of valuations. In their setting, agents may be ambiguity averse (modeled using the max–min expected utility model of Gilboa and Schmeidler [15].) When the bidders face more ambiguity than the seller they show that the seller can always increase revenue by switching to an auction providing full insurance to all types of bidders. Furthermore if the seller is ambiguity neutral and any prior that is close enough to the seller’s prior is included in the bidders’ set of priors then the optimal auction is a full insurance auction. An important difference between the above references [10, 12, 14, 18] and our present work is that we consider uncertainty in prior distribution from the viewpoint of the seller whereas these references attribute uncertainty aversion to every participant (buyer) into the auction or game. While the aforementioned references treat more general problems, our more specific and simpler setting allows more explicit characterizations of optimal policies.

1.2 Contributions

Our contributions are summarized as follows. We consider the more general setting of mechanism design rather than choosing the optimal worst-case price as in [8, 9] and establish optimality of a posted price scheme in three of our four specifications of ambiguity. It should be emphasized that our results are restricted to deterministic mechanisms as opposed to randomized mechanisms such as those used in e.g., [8, 9, 17]. While it is well-known that randomization can help achieve superior performance as demonstrated in [8, 9, 17], randomized prices may be difficult to implement. Hence, our decision to study deterministic mechanisms in this paper.

Returning to our specific contributions, we first show that for every prior f (independent of the characteristic of the hazard function \(i-(1-F(i))/f_{i} \)), the mechanism optimizing the worst-case expected profit is a posted price mechanism. Next we show that for the uniform box ambiguity, the problem boils down to finding the optimal cut-off type (the cut-off type is the type with valuation equal to the posted price) for each instance as in the unambiguous case with a given prior once the worst-case distribution is identified. Our result gives the worst-case prior in closed-form and we show that as m and \(\Delta \) get larger (while staying feasible) the cut-off type tends to \(\lceil m/2\rceil \) and never exceeds it.

For the mean constrained case, we show that there is a threshold \(\alpha ^*\) for \(\alpha \), which is a function of the problem data, such that for all \(\alpha \) exceeding \(\alpha ^*\), the optimal mechanism is an ascending price mechanism, and the problem again reduces to a simple one-dimensional search over the set of types for the cut-off type. For \(\alpha \) smaller than \(\alpha ^*\), the optimal mechanism is a trivial mechanism with a price equal to the lowest valuation for all types. We also characterize the optimal worst-case posted price mechanism, and compare it numerically to the optimal ascending price mechanism.

For the mean-variance constrained ambiguity specification we prove that a posted price mechanism is optimal under some easily verified conditions on the problem parameters. Furthermore, we give explicitly the optimal posted price. However, we experimentally observed that the optimal mechanism is a concatenation of an ascending price menu and a posted price after a threshold type if the aforementioned conditions on problem parameters fail to hold.

For the case of perturbation around the reference prior, we show using conic duality that there exists a value of the perturbation parameter such that for all perturbations within this value, the posted price mechanism optimal for the reference prior is also optimal in the max-min problem.

2 The optimal mechanism under uniform box ambiguity

In this section we look at the problem under uniform box ambiguity where our prior f is an element of the convex polytope I defined as \(I=\{ f | f \ge 0, f^{T}e = 1, l e \le f \le u e \}\) for any \( 0 < l \le 1/m \le u \le 1\), and e is the m-vector of all ones. Under this ambiguity specification we can define our problem as follows.

$$\begin{aligned} \max _{p,A \in SP} \min _{f \in I} p^{T}f. \end{aligned}$$

We use F to denote the cumulative distribution vector of probability mass f. While an upper bound on the probability of a type may be harder to justify (after all, most buyers may be of the same type), an upper bound may be useful when one has a distribution obtained from empirical data, such as the one used in the quality degradation of Cable TV services study in [13], where one may want to use an interval of confidence around the probability estimates. On the other hand, the intuition for the potential usefulness of a lower bound is the following. If there is a minimal probability on each type so that there is a minimal probability on a type above some valuation, the seller might as well target that part of the distribution constrained by the lower bound.

Before moving on to the analysis of this robust case we concentrate on the problem

$$\begin{aligned} \max _{p,A \in SP} p^{T}f \end{aligned}$$

for arbitrary prior f.

Proposition 1

For every probability distribution f the solution to the problem \(\max _{p,A \in SP} p^{T}f\) is a posted price mechanism.

Proof

We use a development similar to the one in [25]. For \(i \ge 2\), we have \(p_i=p_1+\sum _{j=2}^{i}(p_j-p_{j-1})\), and we can see that the optimal prices must have the largest possible increments. Hence, we have \(t(i) ( A_i - A_{i-1}) = p_i - p_{i-1}\) (observe that this condition guarantees \(t(i) ( A_i - A_j) \ge p_i - p_j,\forall i,j \), so it is sufficient) and the largest possible first price is \(t(1)A_{1} = p_{1}\) (observe that combined with the equality for increments this is sufficient for all the IR constraints to be satisfied). Under these equalities we have \(p_{i}=t(1)A_{1} + \sum _{j=2}^{i}t(j) ( A_j - A_{j-1})\) for \(i\ge 2\). Now using the afore-mentioned observations we can reduce the objective function to the following expression:

$$\begin{aligned} \sum _{i=1}^m f_i \left( t(i) - (t(i+1)-t(i))\left( \frac{1-F(i)}{f_i}\right) \right) A_{i}. \end{aligned}$$

This objective function is a linear function of A alone, and the only constraint on \(A_{i}\) is that it belongs to the polytope defined as \(\{A \in R^{m} | 0\le A_1 \le A_2 \le \ldots \le A_m \le 1\} \). Since this is a linear program our optimum will always be satisfied by an extreme point of the polytope we have just given. It is then enough to show that each extreme point of this polytope leads to a posted price mechanism.

Take any \(x \in \{A \in \mathbb {R}^{m} | 0\le A_1 \le A_2 \le \ldots \le A_m \le 1\} \) such that at least one element of x is not an integer. Let \(i_1=\max \{i|x_i<1\}\) and \(i_2=\max \{i|x_i<x_{i_1}\}\) (if there is no such \(i_2\) then take \(i_2=0\) and \(x_{i_2}=0\)). Let \(x'\) and \(x''\) be two points in the same polytope such that for \(i\le i_2\) and \(i>i_1\), \(x_i=x'_i=x''_i\) and for \(i_2 < i \le i_1\) \(x'_i=x_{i_2}\), \(x''_i=1\). Since \( x'_{i_1}<x_{i_1}<x''_{i_1}\) there exists \(\lambda \in (0,1)\) such that \(x=\lambda x' + (1- \lambda )x''\) and because \(x\ne x'\), \(x\ne x''\) such x can not be an extreme point of our polytope. So every extreme point of the polytope \(\{A \in \mathbb {R}^{m} | 0\le A_1 \le A_2 \le \ldots \le A_m \le 1\}\) has to be integer valued. From the monotonicity condition we can see that A is an extreme point only if there exists a \(j \in \{1,...,m\}\) such that \(A_i=0\) for \(i < j \) and \(A_i=1\) for \(i \ge j\), which leads to the optimal price vector p where \(p(i)=0\) for \(i < j\) and \(p(i)=t(j)\) for \(i \ge j\). This concludes the proof. \(\square \)

Now, we return to the sub-problem of \(\min _{f \in I}\) \(p^{T}f\). Since we are dealing with a convex polytope and a linear objective function, once again the extreme points will provide us an easy way to calculate the optimum points. We start with the characterization of the extreme points of I.

Lemma 1

\(x \in R^{m}\) is an extreme point of I iff x has \(0 \le k \le m-1\) elements having value l, \(m-k-1\) elements having value u, moreover \(\exists j \in \{1,...,m\}\) such that, \(l \le x_j=1-kl-(m-k-1)u \le u \) and \(e^{T}x=1\).

Proof

Define \(C_{lu}\) as the cube whose elements lie in [l, u] on each one of the standard basis, that is \(C_{lu}=\{x \in R^{m}| l \le x_{i} \le u, \forall i \}\). We can see that \(I=\{x | x^{T}e=1\} \cap C_{lu}\), moreover for the choice of \( 0 \le l \le 1/m \le u \le 1\), it is non-empty. Since I is the intersection of the hyperplane \(\{x | x^{T}e=1\}\) and \(C_{lu}\), everyone of its extreme points must come from the intersection of a one-dimensional face (intersection with higher dimensional faces will lie on an at least one dimensional subspace with non-empty relative interior) of the cube \(C_{lu}\) and the hyperplane. The edges of the cube \(C_{lu}\) which intersects the hyperplane \(\{x | x^{T}e=1\}\) have either an endpoint on the hyperplane or each of its two endpoints on different subspaces separated by this hyperplane (observe that none of the edges is parallel to the hyperplane). Since the points on any edge of \(C_{lu}\) differ in only one index (the element corresponding to index j in the lemma) it is easy to see that any extreme point has to have the structure given in the lemma.

To prove the opposite direction take an x as given in the lemma. If \(x_j \in \{l,u\}\) then it is an extreme point of \(C_{lu}\) hence it is also an extreme point of the intersection. If \(x_{j} \in (l,u)\) then take two extreme points of the cube \(C_{lu}\), namely \(x^{l},x^{u}\), such that \(x_{j}^l=l\), \(x_{j}^u=u\) and for every \(i \ne j\) \(x_{i}^l = x_{i}^u=x_{i}\) (they must be the endpoints of an edge of \(C_{lu}\)). The point x is on the edge connecting \(x^{l}\) and \(x^{u}\) since \((x^{l})^{T}e < 1,(x^{u})^{T}e > 1\) then x is the only intersection point of this edge with the hyperplane \(\{x | x^{T}e=1\}\), hence an extreme point of I. \(\square \)

Lemma 2

Let p be an ordered price vector such that \(p_1\le p_2 \le \ldots \le p_m\). Define \(x^{*}\) as \(x^{*}_i=u\) for \(i=1,...,k\), \(x^{*}_{k+1}=1-ku-(m-k-1)l\), \(x^{*}_i=l\) for \(i=k+2,...,m\) where \(k\in \{1,...,m-1\}\) and \(e^{T}x^{*}=1\). Then we have \(p^{T}x^{*}=min_{f \in I}\) \(p^{T}f\).

Proof

Observe that x is and extreme point of I if and only if there exist a permutation \(\mu \) of indices such that \(\forall i\) we have \(x_{\mu (i)}=x^{*}_{i}\) (follows from Lemma 1). Since our sub-problem \(\min _{f \in I}\) \(p^{T}f\) has a linear objective function, there exists an extreme point which will lead to the minimum (easy to see that any permutation of the elements of the price vector will lead to the same minimum value since all extreme points are permutations of one another). Since every extreme point is just a permutation of each other, our objective becomes selecting the order of the elements. The given price vector p has elements in non-decreasing order hence the extreme point \(x^{*}\) having elements in non-increasing order will achieve the minimum. \(\square \)

The lemma below characterizes the worst-case prior. As in Bergemann and Schlag [9], the worst-case prior is achieved by concentrating the cumulative probability to smaller valuations, and furthermore, the worst-case prior is independent of the pricing mechanism of the seller.

Lemma 3

\(\max _{p,A \in SP}\) \(\min _{f \in I}\) \(p^{T}f\) \(=\) \(\max _{p,A \in SP}\) \(p^{T}x^{*}\) where \(x^{*}_i=u\) for \(i=1,...,k\), \(x^{*}_{k+1}=1-ku-(m-k-1)l\), \(x^{*}_i=l\) for \(i=k+2,...,m\) where \(k\in \{1,...,m-1\}\) and \(e^{T}x^{*}=1\).

Proof

For the types 1, .., m (which are increasing in order) the IC constraints in SP dictate that the price vector must be in non-decreasing order, that is, every \(p \in SP\) must satisfy \(p_1 \le p_2 \le \cdots \le p_m\). Since the order in p is preserved from Lemma 2 our sub-problem reduces to \(p^{T}x^{*}\) and the result follows. \(\square \)

Now we can show that the optimal mechanism for the robust problem is a posted price mechanism and give a precise relation between u, l and the threshold as follows.

Theorem 1

  1. 1.

    The solution to the problem \(\max _{p,A \in SP} \min _{f \in I} p^{T}f\) is the posted price \(p_{t_{i^{*}}}\) such that \(i^{*}\) maximizes \(p_{t_{j}}^{T}x^{*}\), where \((p_{t_{j}})_{i} =t(j)\) if \(t(i) \ge t(j)\), \((p_{t_{j}})_{i}=0\) otherwise, and \(x^{*}_i=u\) for \(i=1,...,k\), \(x^{*}_{k+1}=1-ku-(m-k-1)l\), \(x^{*}_i=l\) for \(i=k+2,...,m\) where \(k=m- \lceil \frac{um - 1}{u-l} \rceil \).

  2. 2.

    The cut-off type for the optimum mechanism cannot exceed \(\lceil m/2 \rceil \).

  3. 3.

    When l, u are fixed, for sufficiently large m and \(\Delta \) the cut-off type is arbitrarily close to \(\lceil m/2 \rceil \).

Proof

In Lemma 3 we have shown that the solution to the original problem simplifies into the one written for the worst case prior and from Proposition 1 we know that the solution must be a posted price mechanism. Now the only thing we need to determine is the threshold for the worst case prior and this is given by the relation in the statement of the theorem.

For part 2, the difference in between the expected payoffs for the cut-off types i and \(i+1\) is \(\sum _{j=i+1}^{m}f_{j}t(i+1)-\sum _{j=i}^{m}f_{j}t(i)=\sum _{j=i+1}^{m}f_{j}(t(i+1)-t(i)) - f_{i}t(i)\). Since our worst case prior is monotonically non-increasing then \(\sum _{j=i+1}^{m}f_{j}(t(i+1)-t(i)) - f_{i}t(i) \le f_{i} ((m-i)\Delta - (i-1)\Delta -t(1))\) and for \(i\ge \lceil m/2 \rceil \) this expression is strictly negative so increasing the cut-off type beyond this point will decrease our expected profit hence cut-off type can not be larger than \(\lceil m/2 \rceil \).

For part 3, we assume that l is fixed to a positive value. Observe that for the largest feasible m (recall that for l fixed we must have \(l \le 1/m\)) we have the worst case prior as \(f_{i}=l\) for \(i \ge 2\) and since for the largest feasible m equal to \(\lfloor 1/l \rfloor \) we have \(k=0\) it is immediate to see that \(2l > f_{1} \ge l\). To see this note that either \(m l = 1\) in which case \(f_1=l\) or \(m l< 1\) and we have \(1-(m-1)l< (m+1)l-(m-1)l=2 l\). Now, we know from part 2 that the difference in between the expected pay-offs for the cut-off types i and \(i+1\) is \(\sum _{j=i+1}^{m}f_{j}t(i+1)-\sum _{j=i}^{m}f_{j}t(i)=\sum _{j=i+1}^{m}f_{j}(t(i+1)-t(i)) - f_{i}t(i)\) is at most \( f_{i} ((m-i)\Delta - (i-1)\Delta -t(1))\). We now distinguish two cases.

Case 1 1 / l is integer: In this case, we have \(f_i=l\) for all \(i=1,\ldots ,m\) and \(\sum _{j=i+1}^{m}f_{j}t(i+1)-\sum _{j=i}^{m}f_{j}t(i)=\sum _{j=i+1}^{m}f_{j}(t(i+1)-t(i)) - f_{i}t(i)\) is equal to \( f_{i} ((m-i)\Delta - (i-1)\Delta -t(1))\) For any i, if we normalize the expression \(f_{i} ((m-i)\Delta - (i-1)\Delta -t(1))\) by t(1) we obtain \(f_i (m-1) \Delta /t(1) - f_{i}(i-1)\Delta /t(1)- f_{i}\). Since we have \(f_i (m-i) = (1-F_i)\) for all i in general, and \(f_{\lceil m/2 \rceil }(\lceil m/2 \rceil -1) \le 1-F(\lceil m/2 \rceil )\) for the largest possible m (this is easy to verify for the largest possible m for which we have just given the worst case prior), for all \(i\le \lceil m/2 \rceil \) we must have \(f_{i}(i-1) < 1-F(i)\). But then for every \(j \le \lceil m/2 \rceil \) we can find a large enough \(\Delta /t(1)\) such that \((1-F(i))\Delta /t(1) - f_{i}(i-1)\Delta /t(1)- f_{i} > 0 \) for all \(i \le j\), which shows that the optimal cut-off must approach \(\lceil m/2 \rceil \) since by by part 2 we know that the cut-off type cannot exceed \(\lceil m/2 \rceil \).

Case 2 1 / l is not integer, in this case we have \(f_i=l\) for all \(i=2,\ldots ,m\), and \(l< f_1 < 2 l\). For \(i=2,\ldots ,m\), the argument used in Case 1 above is valid. For \(i=1\), the difference in between the expected payoffs for the cut-off type \(i=1\) and \(i+1=2\), that is the expression \(\sum _{j=i+1}^{m}f_{j}t(i+1)-\sum _{j=i}^{m}f_{j}t(i)\), is equal to \((m-1) \Delta l - f_1 t(1)\) which is again positive for sufficiently large \(\Delta \).

Hence, in both cases we have shown that for the largest possible m and sufficiently large \(\Delta \) the cut-off type approaches \(\lceil m/2 \rceil \).

This argument remains valid for all m large enough such that \(k=0\) (\(f_1\) is not bounded above by 2l in that case). To treat this case, let \(m < \lfloor 1/l \rfloor \) with \(k=0\). We have \(f_i=l\) for all \(i=2,\ldots ,m\) with \(f_1 > l\), and \(\sum _{j=i+1}^{m}f_{j}t(i+1)-\sum _{j=i}^{m}f_{j}t(i)=\sum _{j=i+1}^{m}f_{j}(t(i+1)-t(i)) - f_{i}t(i)\) is equal to \( f_{i} ((m-i)\Delta - (i-1)\Delta -t(1))\). For any i, if we normalize the expression \(f_{i} ((m-i)\Delta - (i-1)\Delta -t(1))\) by t(1) we obtain \(f_i (m-1) \Delta /t(1) - f_{i}(i-1)\Delta /t(1)- f_{i}\). Since we have \(f_i (m-i) = (1-F_i)\) for all i in general, and \(f_{\lceil m/2 \rceil }(\lceil m/2 \rceil -1) \le 1-F(\lceil m/2 \rceil )\) as above, for all \(i\le \lceil m/2 \rceil \) we must have \(f_{i}(i-1) < 1-F(i)\). But then for every \(j \le \lceil m/2 \rceil \) we can find a large enough \(\Delta /t(1)\) such that \((1-F(i))\Delta /t(1) - f_{i}(i-1)\Delta /t(1)- f_{i} > 0 \) for all \(i \le j\). For \(i=1\), the difference in between the expected pay-offs for the cut-off type \(i=1\) and \(i+1=2\), that is the expression \(\sum _{j=i+1}^{m}f_{j}t(i+1)-\sum _{j=i}^{m}f_{j}t(i)\), is equal to \((m-1) \Delta l - f_1 t(1)\) which is again positive for sufficiently large \(\Delta \). \(\square \)

Figure 1 illustrates parts 2 and 3 of Theorem 1. We have \(m = 110\) for \(l=0.009\) and we increase \(\Delta \), the difference between consecutive types.

Fig. 1
figure 1

The cut-off valuation as a function of \(\Delta \) for \(m=110\), \(l=0.009\) and \(u=1\). It is seen that the cut-off valuation is always less than m / 2, and converges to it as \(\Delta \) increases

Full size image

It is easy to see that under no restriction to the type distribution as in Bergemann and Schlag [8] the optimal price is equal to the lowest valuation \(t(1) = {\mathbf k}\). On the other hand, in another paper [9] the two authors constrain the type distribution to an uncertainty set built around a reference prior using the Prohorov metric. Our box-uncertainty specification can be seen as an alternative or a simple variant to the Bergemann-Schlag proposal in [9]. Indeed, if a reference prior is derived from available data as in the cable TV market study of [13], one may incorporate box uncertainty around it and use the results of the present paper. Box uncertainty would correspond to a \(\infty \)-norm specification around a reference prior. A numerical experiment summarized in Fig. 2 below starting with \(m=100\), \(l=0.0061\), \(u=0.1\), \({\mathbf k}=21\) and \(M=120\) shows that the maximum worst-case expected profit is significantly higher than the expected worst-case profit valid for all distributions (equal to \({\mathbf k}\)), and it increases with increasing l, the lower bound specification. The cut-off type \(i^*\) oscillates between 40 and 41 (i.e., 60 and 61 for the valuation), throughout the experiment.

Fig. 2
figure 2

The maximum worst-case expected profits plotted as a function of the lower bound l when it varies from 0.0061 to 0.008 for \({\mathbf k}=21\), \(M=120\) and \(\Delta =1\) (hence 120 types). The uppermost curve is the maximum worst-case expected profit obtained from the optimal posted price mechanism. The worst-case expected profit when no constraint is put on the distribution is equal to 21, the lowest valuation. It corresponds to a horizontal line that sits on the l-axis

Full size image

We also note that the result of Theorem 1 above is akin to the result of Bergemann and Schlag (Corollary 1 of [8]) where the mini–max regret seller, when constrained to pure strategies, chooses either the mean \(\frac{1+c}{2}\) of the interval c and 1 where c is the value of the good to the seller and 1 is the upper limit of the buyer valuation, or the lower limit of the buyer valuation interval v.

3 The optimal mechanism under mean constrained ambiguity

In this section we consider the following problem that we shall refer to as MCAS (for Mean Constrained Ambiguity Screening)

$$\begin{aligned} \max _{p,A \in SP} \min _{f \in \mathcal{M}} p^{T}f \end{aligned}$$

where \(\mathcal{M}\) is a convex polytope defined as \(\mathcal{M}=\{ f | f \ge 0, f^{T}e = 1, \sum _{i=1}^m t(i) f_i = \alpha \}\) for any real number \( \alpha \in [{\mathbf k},M]\), and \(\mathcal{M}\) is assumed to be non-empty. Here, the seller is assumed to have an idea of the mean valuation of the buyer, and incorporates this belief into the set of probability distributions \(\mathcal{M}\). A similar set of distributions was used in Neeman [22] to describe how high, on average, the buyer valuations are in an English auction setting.

We shall prove that the above problem reduces to a one-dimensional search over a restricted set of positive integers between 1 and m, (or, over the set of valuations \(\{t(1),\ldots ,t(m)\}\)) and that the optimal mechanism is an increasing price mechanism as opposed to the posted price mechanism of the previous section when the mean valuation \(\alpha \) as viewed by the seller is above a certain threshold value \(\alpha ^*\) entirely characterized by the problem data. If \(\alpha \) is less than or equal to the threshold \(\alpha ^*\) the optimal mechanism is a trivial posted price mechanism where every buyer type can get the object paying the lowest valuation t(1). We do this in two steps.

Lemma 4

There exists a threshold \(\alpha ^*\) such that the solution to problem MCAS is an ascending price mechanism for \(\alpha \ge \alpha ^*\).

Proof

As a first step, after a straightforward application of linear programming duality to the inner \(\min \) problem we pose the above problem as the linear programming problem

$$\begin{aligned} \max _{p,A, y,z} y + \alpha z \end{aligned}$$

subject to

$$\begin{aligned}&\displaystyle p_i \ge y + z t(i), \forall \; i=1,\ldots ,m\\&\displaystyle (p,A) \in SP, \end{aligned}$$

where we introduced the additional scalar variables y and z that are unrestricted in sign.

Now we postulate the existence of an optimal solution to the above problem using \(i^* \in [1,m]\) such that \(i^*\) is the smallest integer i where \(p_i = y + z t(i)\), i.e., we have \(p_i = y + z t(i)\) for all \(i=i^*,i^*+1,\ldots ,m\), all allocations up to and including \(i^*\) are zero, i.e.,

$$\begin{aligned} A_1=\cdots =A_{i^*} = 0, \end{aligned}$$

as well as all prices up to and including type \(i^*\) are zero, i.e.,

$$\begin{aligned} p_1=\cdots =p_{i^*}=0. \end{aligned}$$

Furthermore, the posited solution has the first \(i^*-1\) constraints \(p_i \ge y + z t(i)\) non binding, i.e., we have

$$\begin{aligned} p_i > y + z t(i), i=1,\ldots ,i^*-1, \end{aligned}$$

the prices \(p_{i^*},p_{i^* + 1}, p_{i^*+2}, \ldots ,p_m\) as well as \(A_{i^* + 1}, A_{i^*+2}, \ldots ,A_m\) are strictly increasing with \(A_m =1\).

We shall indeed construct an optimal solution in this form, and obtain conditions under which such optimal solutions exist. We do this by forming the dual of the linear program above, and constructing a feasible dual solution, satisfying complementary slackness and strong duality properties along with the suggested primal solution. The dual linear program is the following problem in positive variables \(f=\{f_i\}_{i=1}^m\), and \(w_i\), \(i=0,1,\ldots ,m\):

$$\begin{aligned} \max w_m \end{aligned}$$

subject to

$$\begin{aligned} t(i) f_i= & {} \Delta \sum _{j=i+1}^m f_j - w_{i-1} + w_i, \forall \;i=1,\ldots ,m\nonumber \\ f\in & {} \mathcal{M}. \end{aligned}$$
(5)

First we define the sequence \(\mathcal{H}_i^j\) by the formula

$$\begin{aligned}&\mathcal{H}_i^j = \frac{1}{t(j)} + \text{ sum } \text{ of } \text{ all } \text{ two } \text{ term } \text{ fractions } \text{ of } \text{ the } \text{ form } \; \frac{\Delta }{t(k) t(j)} +\\&\text{ sum } \text{ of } \text{ all } \text{ three } \text{ term } \text{ fractions } \text{ of } \text{ the } \text{ form } \; \frac{\Delta ^2}{t(l) t(k) t(j)} +\cdots + \frac{\Delta ^{j-i}}{t(i) t(i+1) \ldots t(j)}. \end{aligned}$$

E.g., we have \(\mathcal{H}_4^6 = \frac{1}{t(6)} + \Delta (\frac{1}{t(4) t(6)}+ \frac{1}{t(5) t(6)}) + \frac{\Delta ^2}{t(4) t(5) t(6)}.\)

We shall pick a dual solution with \(w_m=\zeta \) for some positive \(\zeta \) Footnote 2 and set the remaining w variables as follows:

$$\begin{aligned}&\displaystyle w_j = 0, j=i^*,\ldots ,m-1,\\&\displaystyle w_{i^*-1} = t(i^*) (\zeta \mathcal{H}_{i^*}^m- 1),\\&\displaystyle w_{i^*-j} = w_{i^*-(j-1)} + \Delta , \forall \; j=2,3,\ldots ,i^*. \end{aligned}$$

We set

$$\begin{aligned} f_j= & {} 0, \forall j=1,\ldots ,i^*-1, \end{aligned}$$
(6)
$$\begin{aligned} f_{i^*}= & {} 1 - \zeta \mathcal{H}_{i^*+1}^m,\; f_m = \zeta \mathcal{H}_m^m, \end{aligned}$$
(7)

and,

$$\begin{aligned} f_{i} = \zeta (\mathcal{H}_i^m - \mathcal{H}_{i+1}^m), \forall \;i=i^*+1,\ldots ,m-1. \end{aligned}$$
(8)

It is immediate to verify that these choices for f and w satisfy the constraints \(\sum _{i=1}^m f_i = 1\), (5), and non-negativity restrictions on f and w provided \(\zeta \ge \frac{1}{\mathcal{H}_{i^*}^m}\). We shall return to this condition later.

Now, using the equation \(\sum _{i=1}^m t(i) f_i = \alpha \), we obtain the identity

$$\begin{aligned} \alpha = \zeta \Delta \sum _{k=i^* + 1}^m \mathcal{H}_k^m + t(i^*), \end{aligned}$$
(9)

which results in

$$\begin{aligned} \zeta = \frac{\alpha -t(i^*)}{\Delta \sum _{k=i^* + 1}^m \mathcal{H}_k^m}. \end{aligned}$$

Now, to enforce strong duality of linear programming, we set \(\zeta = y + \alpha z\), which results in

$$\begin{aligned} y= & {} - \frac{t(i^*)}{\Delta \sum _{k=i^* + 1}^m \mathcal{H}_k^m }, \end{aligned}$$
(10)
$$\begin{aligned} z= & {} \frac{1}{\Delta \sum _{k=i^* + 1}^m \mathcal{H}_k^m}. \end{aligned}$$
(11)

These choices of y, z lead to the choice of p and A according to complementary slackness as follows. For the prices we have

$$\begin{aligned} p_i = \frac{i - i^*}{ \sum _{k=i^* + 1}^m \mathcal{H}_k^m}, \forall \; i=i^*,\ldots ,m \end{aligned}$$
(12)

and

$$\begin{aligned} p_i = 0, \forall \;i=1,\ldots ,i^*-1. \end{aligned}$$
(13)

The allocation variables \(A_i\) are set recursively using the equations

$$\begin{aligned} A_i= & {} 0, \forall \;i=1,\ldots ,i^*,\nonumber \\ A_i= & {} \frac{p_i + \Delta \sum _{j=1}^{i-1} A_j}{t(i)}, \forall \;i=i^*+1,\ldots ,m. \end{aligned}$$
(14)

Simple algebraic manipulation results in the formula:

$$\begin{aligned} A_{i^* + j} = \frac{1}{\sum _{k=i^* + 1}^m \mathcal{H}_k^m} \sum _{k=1}^j \mathcal{H}_{i^*+k}^{i^*+j}, \;\text{ for }\; j=1,\ldots ,m-i^*. \end{aligned}$$
(15)

It is immediate to see that \(A_i \ge 0\), for all \(i \in \{1,\ldots ,m\}\), \(A_m = 1\), and they are monotone increasing. These observations ensure that the allocation variable values indeed satisfy the primal constraints defining the set SP.

Hence, we have constructed a primal-dual pair of points (p, A), and (f, w, y, z) satisfying primal feasibility, dual feasibility, complementary slackness (and also strong duality). All this depends on the initial supposition that \(\zeta \ge \frac{1}{\mathcal{H}_{i^*}^m}\), which is assured provided that

$$\begin{aligned} \alpha \ge t(i^*) + \frac{\Delta \sum _{k=i^* + 1}^m \mathcal{H}_k^m}{\mathcal{H}_{i^*}^m}. \end{aligned}$$
(16)

Note that as \(\alpha \) gets smaller, \(i^*\) moves down to one. Setting \(i^*\) one in (16) shows that the above derivation is valid for \(\alpha \ge \alpha ^* \equiv t(1) + \frac{\Delta \sum _{k=2}^m \mathcal{H}_k^m}{\mathcal{H}_{1}^m}\). \(\square \)

It remains to investigate the case when \(\alpha \in [t(1),\alpha ^*)\). In this case, we shall prove that the optimal mechanism is to set \(p_i=t(1)\), \(A_i =1\) for all \(i =1,\ldots ,m\) and \(y=1\) with \(z=0\).

Lemma 5

For \(\alpha \in [t(1),\alpha ^*)\) the solution to MCAS is a posted price mechanism where all types are entitled to the object in return for a payment equal to t(1), the lowest valuation.

Proof

Let us first observe that for \(\alpha =\alpha ^*\) we have \(p_i=t(1)\) and \(A_i=1\) for all \(i=1,\ldots ,m\) as a result of our derivation above. Define \(e_i\) as the probability mass such that \(e_i(i) =1\) and \(e_i(j)=0\) for \(j\ne i\) (these are the extreme points of the probability simplex). By a similar argument to the box uncertainty case we know that every extreme point of \(\mathcal{M}\) must be an intersection of an edge of the simplex \(\{x: \sum _{i=1}^m x_i=1, x_j \ge 0, j=1,\ldots ,m\}\) and the hyperplane \(\{x: \sum _{i=1}^m t(i) x_i = \alpha \}\). For an edge of the unit simplex to have a non-empty intersection, there must be exactly one of its end-points in each of the two sub-spaces separated by the hyperplane \(\{x: \sum _{i=1}^m t(i) x_i = \alpha \}\). Hence, \(\hat{x}\) is an extreme point iff there exist \(l \ne k \in \{1,\ldots ,m\}\) and \(\lambda \in [0,1]\) such that \(\hat{x} = \lambda e_l + (1-\lambda ) e_k\) where \(t(l) \le \alpha ^* \le t(k)\).

Let \(\alpha ' < \alpha ^*\) and \(\max _{p,A \in SP} \min _{f \in M'}\sum _{i=1}^m f_i p_i = \min _{f \in M'}\sum _{i=1}^m f_i p_i'\) where the mean set corresponding to \(\alpha '\) and \(\alpha ^*\) are represented as \(\mathcal{M}'\) and \(\mathcal{M}^*\), respectively. Let \(f''= \lambda '' e_l + (1-\lambda '') e_k \) be an extreme point of \(\mathcal{M}^{*}\) such that \(\sum _{i=1}^m f_i'' p_i' = \min _{f \in \mathcal{M}^*} \sum _{i=1}^m f_i p_i'\) where \(t(l) \le \alpha ^* \le t(k)\). Moreover, since t(1) is the maximum achievable expected price for \(\alpha ^{*}\)we have

$$\begin{aligned} t(1)= & {} \max _{p,A \in SP} \min _{f \in \mathcal{M}^{*}}\sum _{i=1}^m f_i p_i \ge \min _{f \in \mathcal{M}^*} \sum _{i=1}^m f_i p_i'\nonumber \\= & {} \sum _{i=1}^m f_i'' p_i' \Rightarrow t(1) \ge \lambda '' p_l' + (1-\lambda '') p_k'. \end{aligned}$$
(17)

Now, if \(t(l) \le \alpha ' \le t(k)\) then there exists an \(f'\) such that \(f'= \lambda 'e_l + (1-\lambda ')e_k\) where \(\lambda ' t(l) + (1-\lambda ')t(k) = \alpha '\) and \(\lambda ' > \lambda ''\)(since \(\alpha '<\alpha ^{*}\)). We have

$$\begin{aligned} \min _{f \in \mathcal{M}'} \sum _{i=1}^m p_i' f_i \le \sum _{i=1}^m p_i' f_i' = \lambda ' p_l' + (1-\lambda ')p_k' \le \lambda '' p_l' + (1-\lambda '') p_k' \le t(1) \end{aligned}$$
(18)

since \(k > l\) and for every feasible price vector we must have \(p_1 \le p_2 \cdots \le p_m\) (so, \(p'_l \le p_k'\)).

For \(t(1)< \alpha ' < t(l)\) let us take the extreme point \(f'= \lambda ' e_1 + (1-\lambda ') e_l\) such that \(\lambda ' t(1) + (1-\lambda ')t(l) = \alpha '\). Again we must have

$$\begin{aligned} \min _{f \in \mathcal{M}^*} \sum _{i=1}^m p_i' f_i \le \lambda ' p_1' + (1-\lambda ')p_l' \le p_l' \le \lambda '' p_l' + (1-\lambda '') p_k' \le t(1) \end{aligned}$$
(19)

since \(p_1' \le p_l' \le p_k'\).

Therefore, from (18), (19) we see that for all \(\alpha < \alpha ^*\) we must have

$$\begin{aligned} \max _{p,A \in SP} \min _{f \in \mathcal{M}} \sum _{i=1}^m p_i f_i \le t(1). \end{aligned}$$

For the price vector \(p_i = t(1)\) \(\forall \) \(i=1,\ldots ,m\) we have \(\min _{f \in \mathcal{M}} \sum _{i=1}^m p_i f_i = t(1)\) hence we conclude that

$$\begin{aligned} t(1)\ge \max _{p,A \in SP} \min _{f \in \mathcal{M}} \sum _{i=1}^m p_i f_i \ge t(1) \Rightarrow \max _{p,A \in SP} \min _{f \in \mathcal{M}} \sum _{i=1}^m p_i f_i = t(1) \end{aligned}$$

for \(t(1) \le \alpha < \alpha ^*\), moreover the optimal price vector is \(p_1=p_2=\cdots =p_m = t(1)\) with allocations \(A_1=A_2 = \cdots =A_m=1\).

We summarize the above results below as our main result in this section.

Theorem 2

  1. 1.

    For \(\alpha \ge \alpha ^*\), the problem MCAS reduces to finding the largest positive integer \(i^* \in \{1,m\} \) satisfying the inequality

    $$\begin{aligned} \alpha \ge \ t(i^*) + \frac{\Delta \sum _{k=i^*+1}^m \mathcal{H}_k^m}{\mathcal{H}_{i^*}^m}. \end{aligned}$$

    Furthermore, the optimal mechanism is a linearly ascending price mechanism described by equations (12)–(15), and with a worst-case distribution given by (6)–(8) and maximum worst-case profit equal to \( \frac{\alpha -t(i^*)}{\Delta \sum _{k=i^* + 1}^m \mathcal{H}_k^m}. \)

  2. 2.

    For \(1\ \le \alpha < \alpha ^*\), the optimal mechanism is trivial, i.e., it is to set a price equal to t(1) for all types, where any type is entitled to the object.

Note that in part 1 of Theorem 2, the optimal cut-off type \(i^*\) need not be unique. Take e.g., the example given in Fig. 3 with \(\alpha =4.4701948\), then both \(i^*=1\) and \(i^*=2\) are optimal to a six-digit accuracy.

We also give a simple procedure for computing the optimal worst-case posted price mechanism under mean constrained ambiguity.

Proposition 2

The optimal worst-case profit of the best posted price mechanism under mean constrained ambiguity is given by

$$\begin{aligned} \max \left\{ t(1), \max _{j \in \{2,\ldots ,m\}} \frac{t(j)(\alpha -t(j-1))}{M-t(j-1)} \right\} . \end{aligned}$$

If \(\alpha \le t(1)(M-t(j-1))/t(j) + t(j-1)\) for all \(j \in \{2,\ldots ,m\}\) then the maximum is attained at t(1), and all types are entitled to the object with a payment equal to t(1). Otherwise, the \(j^*\) which achieves the maximum results in the optimal mechanism \(p_i=t(j^*)\) and \(A_i=1\) for \(i=j^*,\ldots ,m\).

Proof

The best posted price mechanism corresponding to our problem is found by solving the integer optimization problem:

$$\begin{aligned} \max _{p,A \in SP^i} \min _{f \in \mathcal{M}} p^{T}f \end{aligned}$$

where

Hence we have the problem

$$\begin{aligned} \max _{p,A, y,z} y + \alpha z \end{aligned}$$

subject to

$$\begin{aligned}&\displaystyle p_i \ge y + z t(i), \forall \; i=1,\ldots ,m\\&\displaystyle (p,A) \in SP^i. \end{aligned}$$

This problem admits either an optimal solution where \(A_i\)’s are equal to one with all \(p_i\)’s equal to t(1) (the trivial mechanism) or a solution such that \(A_j=p_j=0\) for \(j=1,\ldots ,j^*-1\), and \(A_j = 1\) and \(p_j = t(j^*)\) for \(j=j^*,\ldots ,m\) where \(j^* \ge 2\). In the first trivial mechanism, the objective function is equal to t(1) by setting \(y=1\) and \(z=0\). In the second case, consider the LP

$$\begin{aligned} \max _{y,z} y + \alpha z \end{aligned}$$

subject to

$$\begin{aligned} p_i \ge y + z t(i), \forall \; i=1,\ldots ,m \end{aligned}$$

for a fixed \((p,A) \in SP^i\). The dual of this LP is simply

$$\begin{aligned} \min _f \{p^t f : f \in \mathcal{M}\}. \end{aligned}$$

Construct the following primal dual pair

$$\begin{aligned} z = \frac{t(j^*)}{M-t(j^*-1)}, y = -t(j^*-1) \frac{t(j^*)}{M-t(j^*-1)} \end{aligned}$$

and

$$\begin{aligned} f_m = \frac{\alpha -t(j^*-1)}{M-t(j^*-1)}, f_{j^*-1} = 1 - \frac{\alpha -t(j^*-1)}{M-t(j^*-1)}, \end{aligned}$$

all other \(f_i\)’s are equal to zero. \(\square \)

The increasing price mechanism advocated by Theorem 2 may indeed be beneficial in comparison to a posted price mechanism under mean constrained distribution ambiguity. A numerical experiment summarized in Fig. 3 illustrates this point. We have 51 types uniformly spread over the interval [2, 7] with \(\Delta =0.1\). The maximum worst-case expected profit obtained for increasing values of \(\alpha \) from 5 to 6 are plotted as well as the maximum worst case expected profit for the optimal posted price mechanism. While the superiority of the ascending price mechanism is evident, one notes in favor of the posted price mechanism that one may prefer to implement it withstanding a loss of 25 to 30 % in maximum worst-case expected profit.

Fig. 3
figure 3

The maximum worst-case expected profits plotted as a function of \(\alpha \) when \(\alpha \) varies from 5 to 6 for \({\mathbf k}=2\), \(M=7\) and \(\Delta =0.1\) (hence 51 types). The upper curve MCAS is the maximum worst-case expected profit obtained from the optimal ascending price mechanism. The curve PP underneath is the maximum worst-case expected profit obtained by using an optimal posted price mechanism

Full size image

4 Mean-variance constrained ambiguity

In this section we consider a mean-variance constrained set of prior distributions, and examine the robust screening problem posed as follows:

$$\begin{aligned} \max _{p,A \in SP} \min _{f \in \mathcal{V}} p^{T}f \end{aligned}$$

where \(\mathcal{V}\) is a convex polytope defined as \(\mathcal{V}=\{ f | f \ge 0, f^{T}e = 1, \sum _{i=1}^m t(i) f_i = \alpha , \sum _{i=1}^m f_i (t(i) - \alpha )^2 = \sigma ^2\}\) for any real number \( \alpha \in [{\mathbf k},M]\) and a positive real number \(\sigma ^2\). For ease of reference, we shall refer to the above problem as MVCAS below for Mean-Variance Constrained Ambiguity Screening. Our work in this section is related to the recent (and, independent) contribution by Kos and Messner [17] where robust optimal selling prices are investigated in cases where the seller does not know the distribution of buyer valuations, but can confine the mean valuation, and also the variance, to some intervals. They show that the optimal strategy for the seller is to commit to a randomization over some interval. In contrast, our result below departs from incentive compatible and individually rational mechanisms, and obtains a deterministic posted price as the optimal selling mechanism under some conditions. In general, the optimal mechanism is a concatenation of an ascending menu of prices and a posted price. It can be argued that while randomization may lead to better performance (i.e. the seller is shown to achieve a higher profit in [17] by using a randomized pricing policy), a deterministic posted price mechanism is simpler and easier to implement. We also note that we assume the first moment and the variance known while in [17] they are only known to belong to some given interval. However, their analysis shows that in the case of the mean belonging to some interval, only the lower end-point of the interval of uncertainty plays a role in their results. A similar observation holds for the upper end-point of the interval of uncertainty for the variance; see [17]. Therefore, it is the two end-point values rather than the intervals themselves, which are critical in [17].

Since it is easier to handle, we shall work with the equivalent variance constraint \(\sum _{i=1}^m f_i t(i)^2 = \sigma ^2 + \alpha ^2\). Naturally, we assume \(\mathcal{V}\) to be non-empty. The problem MVCAS is less conservative than the problem MCAS of the previous section. Using duality of linear programming, the problem MVCAS is posed as the following linear programming problem in variables w, y, z, p, A:

$$\begin{aligned} \max w + \alpha y + (\alpha ^2 + \sigma ^2)z \end{aligned}$$

subject to

$$\begin{aligned}&\displaystyle p_i \ge w + t(i) y + t(i)^2 z, \forall i=1,\ldots ,m\\&\displaystyle (p,A) \in SP. \end{aligned}$$

Numerical experiments show that the above problem usually results in an optimal strategy that is a mix of an ascending price menu and a posted price scheme after a threshold type. More precisely, for a sequence of types starting from a first threshold type as in the previous section an ascending price menu is applied up to a second threshold type at which point a price is stabilized and a posted price scheme for all types above and including the second threshold type is in effect. On the other hand, it is possible to obtain a posted price optimal mechanism which is readily found under certain conditions as we shall demonstrate below.

We need to define the following three inequalities that are the key to the result below:

$$\begin{aligned}&\displaystyle (x-\alpha )^2 + \sigma ^2 \le \frac{ (3x-\alpha ) \Delta ^2}{ 2 x + \Delta }, \end{aligned}$$
(20)
$$\begin{aligned}&\displaystyle 0 \le (x-\alpha )^2 + \sigma ^2 + \Delta (x-\alpha ) \le 2 \frac{\Delta ^3}{x}, \end{aligned}$$
(21)
$$\begin{aligned}&\displaystyle 0 \le (x-\alpha )^2 + \sigma ^2 - \Delta (x-\alpha ). \end{aligned}$$
(22)

We define a to be the largest valuation t(i) smaller or equal to \(\alpha \), and b the smallest valuation greater than \(\alpha \), i.e., we have \(a \le \alpha < b\). Now, if the above conditions hold at a (respectively, at b), we show below that the optimal strategy is a posted price mechanism with price equal to a (respectively b).

Proposition 3

The problem MVCAS admits an optimal posted price mechanism provided that inequalities (20–22) hold with \(x=a\) or \(x=b\), with maximum worst-case profit equal to \(\frac{x}{2}[2 -\frac{(x-\alpha )^2}{\Delta ^2} - \frac{\sigma ^2}{\Delta ^2}-\frac{x-\alpha }{\Delta }]\).

Proof

The proof is based on construction of primal and dual feasible solutions satisfying complementary slackness conditions under the premises of the proposition. The dual problem to MVCAS is given by the problem over non-negative variables \(\gamma _1,\ldots ,\gamma _{m+1}\) and non-negative variables \(f_1,\ldots ,f_m\):

$$\begin{aligned} \min \gamma _{m+1} \end{aligned}$$

subject to

$$\begin{aligned}&\displaystyle t(i) f_i - \Delta \sum _{j=i+1}^m f_j + \gamma _i - \gamma _{i+1}=0, i=1,\ldots ,m,\\&\displaystyle f=(f_1,\ldots ,f_m) \in \mathcal{V}. \end{aligned}$$

Let us fix \(x=a\) (the argument is identical for \(x=b\)). Let \(i^*\) be such that \(t(i^*)=a\). Now, we fix a primal solution candidate as \(p_j=0\) for all \(j=1,\ldots ,i^*-1\) and \(p_j = a\) for all \(j=i^*,\ldots ,m\), and \(A_j=0\) for all \(j=1,\ldots ,i^*-1\) and \(A_j =1\) for all \(j=i^*,\ldots ,m\).

First, we shall deal with the dual problem. We fix all \(f_i\)s to zero except \(f_{i^*-1},f_{i^*},f_{i^*+1}\). Solving for these three components of f from the three equations

$$\begin{aligned}&\displaystyle f_{i^*-1} + f_{i^*}+ f_{i^*+1} = 1,\\&\displaystyle t(i^*-1) f_{i^*-1} + t(i^*) f_{i^*}+ t(i^*+1) f_{i^*+1} = \alpha ,\\&\displaystyle t^2(i^*-1) f_{i^*-1} + t^2(i^*) f_{i^*}+ t^2(i^*+1) f_{i^*+1} = \alpha ^2 + \sigma ^2, \end{aligned}$$

defining the set \(\mathcal{V}\) (notice that the resulting \(3 \times 3\) set of linear equations always admits a solution since the determinant of the matrix is equal to \(2 \Delta ^3\)), we obtain the solution

$$\begin{aligned} f_{i^* -1}= & {} \frac{1}{2}\left[ \frac{(a-\alpha )^2}{\Delta ^2} + \frac{\sigma ^2}{\Delta ^2} + \frac{a-\alpha }{\Delta }\right] ,\\ f_{i^*}= & {} 1-\frac{(a-\alpha )^2}{\Delta ^2} - \frac{\sigma ^2}{\Delta ^2},\\ f_{i^* +1}= & {} \frac{1}{2}\left[ \frac{(a-\alpha )^2}{\Delta ^2} + \frac{\sigma ^2}{\Delta ^2} - \frac{a-\alpha }{\Delta }\right] . \end{aligned}$$

By the inequality (20) (the right-hand side of this inequality is always smaller or equal to \(\Delta ^2\) by our choice of a and b, which ensures that \(f_{i^*} \ge 0\)), the left-hand inequality of (21) and by (22), the above solution is non-negative. Now, using complementary slackness conditions between the primal monotonicity constraints \(0 \le A_1 \le A_2 \le \cdots \le A_m \le 1\) and the variables \(\gamma _i\), we set \(\gamma _{i^*} = 0\), and solve for the remaining \(\gamma \) variables using the triplet \(f_{i^*-1},f_{i^*},f_{i^*+1}\) computed above. It is easy to see that the critical components of \(\gamma \) variables are only \(\gamma _{i^*-1}\) and \(\gamma _{i^*+1}\) for which there is the risk of being negative. Notice that \(\gamma _j = \gamma _{j+1} + \Delta \) for \(j=1,\ldots ,i^*-2\). By direct calculation we have

$$\begin{aligned}&\displaystyle \gamma _{i^*-1} = \frac{1}{2}\left[ 2\Delta -a \frac{(a-\alpha )^2}{\Delta ^2} + \frac{\sigma ^2}{\Delta ^2} + a \frac{a-\alpha }{\Delta }\right] ,\\&\displaystyle \gamma _{i^*+1}= -a \left[ \frac{(a-\alpha )^2+ \sigma ^2 -\Delta ^2}{\Delta ^2}\right] - \frac{1}{2}\left[ \frac{(a-\alpha )^2 + \Delta (\alpha -a) +\sigma ^2}{\Delta }\right] . \end{aligned}$$

The right-hand inequality of (21) and inequality (20) ensure that the pair \(\gamma _{i^*-1}, \gamma _{i^*+1}\) are non-negative. Hence, we have a feasible dual solution. Using the complementarity between the triplet \(f_{i^*-1},f_{i^*},f_{i^*+1}\) and the corresponding primal inequalities, and the supposed posted price scheme, we have the three equations corresponding to \(p_{i^*-1} = 0\) and \(p_{i^*} = p_{i^*+1}=a\):

$$\begin{aligned}&\displaystyle w+y (a-\Delta )+z(a-\Delta )^2 = 0,\\&\displaystyle w+y a+z a^2 = a,\\&\displaystyle w+y (a+\Delta )+z(a+\Delta )^2 = a. \end{aligned}$$

Solving this system (it is always solvable since the matrix is the transpose of the matrix of the dual equation system above), we obtain the solution \( w = -\frac{1}{2} \frac{a(a^2 + a \Delta - 2 \Delta ^2)}{\Delta ^2} \), \( y= \frac{1}{2} \frac{a(2a + \Delta )}{\Delta ^2} \), \( z = -\frac{1}{2} \frac{a}{\Delta ^2} \). It is easily verified by direct computation that the remaining inequalities hold in this primal construction. More precisely, the slack in the subset of inequalities

$$\begin{aligned} p_j \ge w + t(j) y + t(j)^2 z, \forall j=1,\ldots ,i^*-2 \end{aligned}$$

is equal to \(a(\frac{1}{2}k^2 + \frac{1}{2}k - 1)\) for \(k=i^*-j\), and the slack in slack in the subset of inequalities

$$\begin{aligned} p_j \ge w + t(j) y + t(j)^2 z, \forall j=i^*+2,\ldots ,m \end{aligned}$$

is equal to \(a(\frac{1}{2}k^2 + \frac{1}{2}k)\) for \(k=j-i^*\). Thus, we have a primal-dual feasible pair satisfying complementary slackness, hence optimal in their respective problems. \(\square \)

The proof of the proposition furnishes a simple recipe to compute the posted price mechanism: just check the three inequalities with \(x=a\) first, if they hold, the posted price is equal to a; otherwise check with \(x=b\), if they hold, the posted price is equal to b. If the conditions fail on both cases, then the optimal mechanism is a concatenation of an ascending price menu from a first threshold type to a second threshold at which point it is a posted price afterwards. The proof of the latter observation appears to be much more involved, and will be presented elsewhere. As an example consider the problem instance with 6 types, \(t(1)=2\), \(\Delta =3\), \(\alpha =10.1\) and \(\sigma ^2=2\). With \(x=8\), the inequalities (20)–(22) are satisfied, and the posted price equal to 8 is optimal, and results in an expected worst-case profit equal to 7.951. If \(\alpha = 10.5\) while all other parameters are kept constant, the inequalities are satisfied with \(x=11\) (with \(x=8\) the first inequality does not hold), hence a posted price equal to 11 is optimal, and results in an expected worst-case profit equal to 8.708. The fact that MCAS is more conservative than MVCAS may be one of the reasons why in MCAS a non-trivial posted price mechanism is not optimal. While it is not easy to give an economic meaning to conditions (20)–(22), we observed numerically that for \(\alpha \) and \(\Delta \) fixed, one can find an interval for \(\sigma ^2\) at which the conditions hold and a posted price scheme is found. For example, for 10 types, \(t(1)=2\), \(\Delta =2\), and \(\alpha =9.5\), for any \(\sigma ^2 \in [0.75,0.9721]\) a posted price equal to 8 is optimal. For values of \(\sigma ^2\) below 0.75, the set \(\mathcal{V}\) is empty. For values above 0.9721, the posted price scheme is lost. In the examples above the seller obtained a higher expected pay-off for a higher mean specification, all other things being constant. This result is in line with the findings of [17] where the seller’s pay-off increases with increasing lower end-point of the interval of uncertainty for the mean. On the other hand, Proposition 3 shows that the expected worst-case profit decreases with increasing variance specification (when all else remains constant), which is in agreement with the results of [17] concerning the upper end-point of the interval uncertainty for the variance.

The main insight obtained from mean-variance constrained ambiguity model of this section is that the additional information about the distribution in the form of the variance helps in obtaining a posted price mechanism (at least in some cases) which is a natural and simple mechanism to implement. This finding agrees with the insights obtained in [17] where it is beneficial for the seller knowing the mean to have access to additional information about the variance or the upper bound of the support (while additional information about the mean has no effect on the pay-off).

5 Perturbation of a reference prior

Finally, we investigate the pricing mechanism when the ambiguity set is taken as all priors which are at most at a (EuclideanFootnote 3) distance \(\epsilon \) from a reference prior in the spirit of [9]. Hence, the seller seeks protection for every prior distribution around a reference probability mass \(\bar{f}\):

$$\begin{aligned} \mathcal{P}=\{f| f \ge 0, e^T f = 1, \Vert f-\bar{f}\Vert _2 \le \epsilon \}. \end{aligned}$$

We are interested in direct mechanisms that will maximize expected revenue under ambiguity of probability mass:

$$\begin{aligned} \max _{(p, \mathcal{A}) \in SP} \min _{f \in \mathcal{P}} p^T f \end{aligned}$$

We transform the \(\max {-}\min \) problem using conic duality into:

$$\begin{aligned} \max _{y,z,q,p, A } y - \bar{f}^T q - \epsilon z \end{aligned}$$

subject to

$$\begin{aligned} p + q\ge & {} y e\\ \Vert q \Vert _2\le & {} z\\ (p, A )\in & {} SP. \end{aligned}$$

Simplifying the problem we obtain the following equivalent problem:

$$\begin{aligned} \max _{y, q,p, A } y - \bar{f}^T q - \epsilon \Vert q\Vert _2 \end{aligned}$$

subject to

$$\begin{aligned} p + q\ge & {} y e\\ (p, A)\in & {} SP \end{aligned}$$

It is easy to show using elementary arguments that at optimality one has \(ye = p+q\). Thus, further simplification results into:

$$\begin{aligned} \max _{y, p, A } \bar{f}^T p- \epsilon \Vert y e - p\Vert _2 \end{aligned}$$

subject to

$$\begin{aligned} (p, A ) \in SP. \end{aligned}$$

Theorem 3

There exists \(\epsilon ^* > 0\) such that for \(\epsilon \in [0,\epsilon ^*]\) the optimal direct (posted price) mechanism for \(\bar{f}\) solves the above problem.

Proof

The result follows by applying Theorem 1 of [19] to the simplified problem.   \(\square \)

Note that as soon as \(\epsilon \) exceeds the threshold \(\epsilon ^*\), the posted price mechanism is lost. The resulting mechanism does not appear to be economically meaningful. In a related result in [9] the authors showed that for every perturbation around a prior based on the Prohorov metric, there exists a pair of worst-case prior and associated optimal price in a continuous valuation setting. Our result, while in a discrete valuation and Euclidean distance setting, complements the aforementioned result by showing that the optimal mechanism associated with the given prior continues to be optimal for an interval of the perturbation parameter.

6 Concluding remarks

In this paper we have considered a very simple, and well-solved, well-understood instance of economic mechanism design, namely the problem of the sale of an indivisible object to a buyer whose valuation of the object is private information unknown to the seller. Removing the assumption that the valuation distribution is known to the seller, we confined the distribution to a suitable ambiguity set, and for an ambiguity-averse (max-min) seller we characterized the optimal mechanism for different representations of ambiguity using geometric and algebraic arguments typical of mathematical programming toolbox. An interesting immediate extension would be to consider the minimax regret criterion of [8] in the setting of the present paper. A more substantial extension will be to consider an auction setting. These are left as topics for future studies.