Extending Mechanisms

Introduction

Suppose that you have a mechanism that is defined and incentive compatible on a subdomain of possible valuations (types) of the participants. Can it always be extended to a mechanism that is incentive compatible for all possible valuations of the participants?

Let us look at an example in the simplest case of selling a single good to a single buyer, who is risk neutral and has quasi-linear preferences. Consider the mechanism in which the buyer with valuation 0 does not get the good (and pays nothing); the buyer with valuation 20 gets the good with probability 1/2 and pays 5; and the buyer with valuation 30 gets the good with certainty and pays 18; see Figure 1. This mechanism is defined on the subdomain of valuations $\{0, 20, 30\}$. On this subdomain the mechanism is indeed incentive compatible as no buyer with one of these valuations can gain by declaring any other valuation from this subdomain. Now, can we define an incentive-compatible mechanism for all possible buyer valuations in $\mathbb{R}$ that agrees with this mechanism on the subdomain?

buyer valuation	probability of getting the good	payment to seller	buyer payoff
0	0	0	0
20	1/2	5	5
30	1	18	12

At first sight, requiring incentive compatibility for all possible buyer valuations introduces many new constraints and it is not clear that this can be done consistently. However, it is well known and usually taken for granted that by just offering the menu of the possible outcomes, as defined for the given valuations in the subdomain, and letting every buyer valuation choose among them, one immediately gets an incentive-compatible mechanism for all possible buyer valuations in${}^{1}$ $\mathbb{R}$. In our example if we offer the menu that was already given to us, “the buyer can choose among getting the good with probability $1/2$ at a price of 5, getting it for sure at a price of 18, and not getting it at all and not paying anything,” one gets an incentive-compatible extension that is defined for all buyer valuations and its allocation probabilities are shown in Figure 2 as the red line.

But are there other (incentive-compatible) extensions? Figure 2 also shows another possible extension whose allocation probabilities are given by the blue dashed line. (The payments are not shown on the graph but can be immediately derived.) For example, in the “blue extension,” buyer valuations $20 < x < 30$ pay 9 and get the good with probability $7/10$ (and for $x = 20$ the buyer pays 5 and gets the good with probability $1/2$ and for $x = 30$ the buyer pays 18 and gets the good for sure). The price 9 for the allocation $7/10$ is the lowest price that preserves the choices of all original types. Indeed, at price 9 types 20 and 30 are getting their original payoffs:

(type 0 strictly prefers its original no-purchase option), and so any price less than 9 would make types 20 and 30 switch to the new allocation $7/10$. More generally, this extension offers every allocation at the lowest price that leaves the original choices optimal.¹ This example is developed fully in § 5 as part of our general framework which will, we hope, remove any mystery about how it is derived.

As mentioned, the “red extension” is obtained by offering the buyer the menu that was already defined in the subdomain; we call this the “keep-the-menu” extension. As we will see, the “blue extension” is obtained by offering each allocation at its “canonical” price in the original mechanism (the canonical price of an allocation is the lowest price that leaves all prescribed choices optimal); we call this the “keep-the-pricing” extension. It yields the richest possible menu to the buyer. These two extensions turn out to be the pointwise minimal and maximal extensions, respectively, in terms of the buyer’s payoff function. Moreover, they correspond to, respectively, the pointwise maximal and minimal canonical pricing functions.

These general results do not require the mechanism to be optimal for some distribution whose support is the given subdomain. Indeed, the mechanism above is not optimal for any random valuation with support $\{0,20,30\}$ (the payment of type 20 can be increased from 5 to, say, 6 while keeping incentive compatibility and individual rationality). Moreover, in the one-good case, we show that an optimal mechanism with finite positive revenue has a unique extension (see Appendix § 7.§ 2). With multiple goods, however, even a uniquely optimal restricted mechanism may have multiple extensions with different buyer payoff functions (see Example 2).

Setup

Our setup will be rather abstract (yet standard; [see 8, 9, 10] (Hart and Nisan 2012; Hart and Nisan 2013)). It has a single agent, and covers, in particular, a single seller selling multiple goods to a single buyer with additive demand or with unit demand, and general implementation problems with multiple options (see Hart and Nisan [9]). Our setting has a single risk-neutral quasi-linear buyer with $k$-dimensional valuation $x \in\mathbb{R}^{k}$. Let $\Gamma\subset\mathbb{R}^{k}$ be a fixed compact and convex set of allocations, such as the unit cube $[0,1]^{k}$ (which captures the setting of selling multiple goods to a buyer with an additive valuation), or a unit simplex $\{g \in\mathbb{R}_{+}^{k} : \sum_i g_i \le1\}$ or $\{g \in\mathbb{R}_{+}^{k} : \sum_i g_i = 1\}$ (which capture the unit-demand and implementation settings), etc. A mechanism on a domain $D \subseteq\mathbb{R}^{k}$ of valuations is a pair $\mu=(q,s)$, where $q:D\to\Gamma$ is the allocation function and $s:D\to\mathbb{R}$ is the payment function. A buyer with valuation $x\in D$ receives the allocation $q(x)\in\Gamma$ and pays $s(x)$ to the seller; his payoff is thus

and we refer to $b:D\to\mathbb{R}$ as the buyer payoff function.

From now on, “mechanism” will always mean an incentive-compatible (IC) $\Gamma$-mechanism.³

Let $\mu_0=(q_0,s_0)$ be a mechanism defined on a nonempty domain $D_0\subseteq\mathbb{R}^k$ (for instance, $D_0$ is the support of a $k$-good random valuation $X$); i.e., $(q_0,s_0):D_0\to\Gamma\times\mathbb{R}$. Let $Q_0:=q_0(D_0)\subseteq\Gamma$ be the range of allocations of $\mu_0$. The buyer payoff function $b_0:D_0\to\mathbb{R}$ is given by

for every $x\in D_0$, and the pricing function $p_0:Q_0\to\mathbb{R}$ by

for every $g\in Q_0$ (this is well defined by IC). The IC constraints $b_0(x)=q_0(x)\cdot x-s_0(x)\ge q_0(y)\cdot x-s_0(y)$ for every $x,y\in D_0 are equivalently expressed as $b_0(x)\ge g\cdot x-p_0(g)$ for every $g\in Q_0$, or $p_0(g)\ge g\cdot x-b_0(x)$ for every $x\in D_0$, with equality when $g=q_0(x)$. Equivalently, $b_0(x)+p_0(g)\ge g\cdot x$ for every $x\in D_0$ and $g\in Q_0$, with equality when $g=q_0(x)$. Thus,

Extensions

We use the above formulas to extend $b_0$ and $p_0$ to their entire spaces, $\mathbb{R}^k$ and $\Gamma$, respectively.⁴ we define $b:\mathbb{R}^k \to\mathbb{R}$ and $p:\Gamma\to\overline{\mathbb{R}} := \mathbb{R} \cup\{\infty\}$ by

thus, $b(x) = b_0(x)$ for every $x \in D_0$ and $p(g) = p_0(g)$ for every $g \in Q_0$.

Remark. The function $b$ is everywhere finite, because it is finite on the nonempty set $D_0$ (where it coincides with $b_0$), and, for $y \in\mathbb{R}^k$ and $x \in D_0$, we have $b(y) \le b(x) + \sup_{g \in Q_0} g \cdot(y-x) \le b_0(x) + \gamma\lVert y-x \rVert$, where $\gamma:= \max_{g \in\Gamma} \lVert g \rVert$.

The function $p$, however, may take infinite values, as shown in Ben Moshe, Hart, and Nisan [1]. For example: there are two goods ($k = 2$), and $\mu_0$ sells the first good at a price of 1; if $D_0$ contains points $(0, x_2)$ with arbitrarily large $x_2$ then the price of the second good must be $\infty$.

The same applies to the functions $\overline{b}$ and $\overline{p}$ defined below: $\overline{b}$ is everywhere finite, while $\overline{p}$ may take infinite values.

A mechanism $\mu= (q,s):D \to\Gamma\times\mathbb{R}$ defined on a domain $D \subseteq\mathbb{R}^k$ is a (mechanism-)extension of $\mu_0$ if $D \supseteq D_0$ and $\mu$ coincides with $\mu_0$ on $D_0$ (i.e., $(q,s)(x) = (q_0,s_0)(x)$ for every $x \in D_0$). Let $Q := q(D) \supseteq Q_0$ be the range of allocations of $\mu$, and let $b:D \to\mathbb{R}$ and $p:Q \to\mathbb{R}$ be its buyer payoff and pricing functions. Then for every $x \in D$ we have

(the first equality is by (1) applied to $\mu$). Similarly, for every $g \in Q$ we have

(the first equality is by (2) applied to $\mu$).

The functions $\underline{b} : \mathbb{R}^{k} \to\mathbb{R}$ and $\underline{p} : \Gamma\to\overline{\mathbb{R}}$ thus provide lower bounds on $b$ and $p$, respectively:

We can then use the above inequalities to get upper bounds, as follows. Define $\overline{b} : \mathbb{R}^{k} \to\mathbb{R}$ and $\overline{p} : \Gamma\to\mathbb{R}$ by⁵

Then for every $x \in D$ we have

and for every $g \in Q$ we have

Before stating the results, we recall the notion of the “canonical” extension of the pricing function ([10 see also Ben Moshe, Hart,] and (and Nisan 2022), which assigns to each unused allocation the lowest possible price that does not affect the choices in the mechanism. Let $\mu=(q,s)$ be a $\Gamma$-mechanism with domain of valuations $D$ and domain of allocations $Q=q(D)$, and let $p:Q\to\mathbb{R}$ be its pricing function. Let $g\in\Gamma\setminus Q$ be an allocation that is not used in $\mu$; what price $\tilde{p}(g)$ should be assigned to it so that no valuation $x\in D$ would strictly prefer to pay $\tilde{p}(g)$ for the allocation $g$ to its current choice? This requirement, which is $g\cdot x-\tilde{p}(g)\leq b(x)$ for every $x\in D$, gives the condition $\tilde{p}(g)\geq\sup_{x\in D}(g\cdot x-b(x))$. The right-hand side, denoted $p^{c}(g)$, is thus the minimal, or canonical, price of $g$:

(for $g\in Q$ we have $p^{c}(g)=p(g)$ by (2) applied to $\mu$). To summarize: $\tilde{p}:\Gamma\to\overline{\mathbb{R}}$ is an extended pricing function of $\mu$ if and only if $\tilde{p}(g)\geq p^{c}(g)$ for all $g\in\Gamma$, with equality for $g\in Q$.

Main Result

We can now state the main result:

on $\mathbb{R}^{k}$ that extends $\mu_{0}$ with buyer payoff function $\bar{b}$ and canonical pricing function $\underline{p}$.

(ii) For every mechanism $\mu$ that extends $\mu_{0}$, with domain $D$, range of allocations $Q$, buyer payoff function $b$, and pricing function $p$, we have

with equalities for $x \in D_{0}$ and $g \in Q_{0}$.

(iii) The function $\underline{p}$ is the canonical pricing function of $\mu_{0}$, i.e.,

and the canonical pricing function $p^{c}$ of every mechanism $\mu$ that extends $\mu_{0}$ satisfies⁶

The mechanism$^{7}$ $\mu_{\mathrm{MENU}}$, with buyer payoff function $\underline{b}$ and canonical pricing function $\bar{p}$, is the standard “keep-the-menu” extension of $\mu_{0}$: every valuation chooses from the minimal possible set, namely, the original menu $\{(q_{0}(x),s_{0}(x)) : x \in D_{0}\}$ (or its closure when necessary).$^{8}$ Consequently, $\underline{b}$ yields the lowest possible buyer payoff for every valuation outside $D_{0}$. Equivalently, the price of each allocation $g$ outside $Q_{0}$ is kept just high enough (specifically, given by $\bar{p}$), so that no valuation in $\mathbb{R}^{k}$ (not just those in $D_{0}$) would strictly prefer this allocation $g$ to the original menu.

The mechanism $\mu_{\mathrm{PRICE}}$, with buyer payoff function $\bar{b}$ and canonical pricing function $\underline{p}$, is the “keep-the-pricing” extension of $\mu_{0}$: its canonical pricing function is identical to the canonical pricing function of the original mechanism $\mu_{0}$. These prices are the absolutely lowest possible for $\mu_{0}$ (anything strictly less would induce some valuation in $D_0$ to change its choice), and so the buyer payoff (given by $\bar{b}$) of each valuation outside $D_0$ is the highest possible.

Writing $b_{\mathrm{MENU}}$ and $p_{\mathrm{MENU}}^c$ for the buyer payoff function and the canonical pricing function of the mechanism $\mu_{\mathrm{MENU}}$, and similarly for $\mu_{\mathrm{PRICE}}$, we thus have:

for every extension $\mu$ of $\mu_0$ with domain $D$, buyer payoff function $b$, and canonical pricing function $p^c$.

We emphasize that an inequality between pricing functions $p$ does not imply the same inequality between the resulting payments $s(x)$ of a fixed type $x$, because the allocations may change; for instance, in Example 1 below we have $s_{\mathrm{PRICE}}(x) = 9 > 5 = s_{\mathrm{MENU}}(x)$ for, say, $x = 25$ (while $p_{\mathrm{PRICE}}^c \le p_{\mathrm{MENU}}^c$).

Finally, a function $b : D \to\mathbb{R}$ on a domain $D$ is $\Gamma$-convex if at each point $x \in D$ it has a subgradient⁹ in $\Gamma$. We have

Proof. Necessity follows from Theorem 1. For sufficiency, note first that $\underline{b} \le b \le\overline{b}$ on $D$ implies $b = b_0$ on $D_0$ (where $\underline{b}$ and $\overline{b}$ coincide with $b_0$). Second, from $b = b_0$ on $D_0$ and $b \ge\bar{b}$ on $D$ we get, for every $x \in D_0$ and $y \in D$,

Hence the original allocation $q_0(x)$ is a supporting allocation for $b$ at each $x \in D_0$. Choosing supporting allocations in $\Gamma$ at the remaining points and setting $s(x) = q(x) \cdot x - b(x)$ gives the required extension.

As a consequence, whenever the two bounds $b$ and $\bar{b}$ differ, there is a continuum of distinct extensions to the entire space (with buyer payoff functions $\lambda b + (1-\lambda)\bar{b}$ for $\lambda\in[0,1]$; use the convexity of $\Gamma$).

Examples

Before we get to the simple proof, we proceed with three examples.

Example 1 Selling one good: $k = 1$, $\Gamma= [0,1]$, and $\mu_0$ is given by the table specified in the introduction:

$x$	$q_0(x)$	$s_0(x)$	$b_0(x)$
0	0	0	0
20	$\frac{1}{2}$	5	5
30	1	18	12

$g$	$p_0(g)$
0	0
$\frac{1}{2}$	5
1	18

Thus, $D_0 = \{0,20,30\}$ and $Q_0 = \{0,\frac{1}{2},1\}$. We then get (see Figure 3 and Figure 4):

The corresponding mechanisms, as depicted in Figure 2, are then obtained by setting $q(x)=b'(x)$ where the derivative $b'$ of $b$ is defined (which is at almost every $x$) and an arbitrary subgradient otherwise (with $q(x)=q_0(x)$ for types $x\in D_0$), and then $s(x)=q(x)\cdot x-b(x)$.

The keep-the-menu extension whose allocation probability is depicted by the red line in Figure 2 can be recovered from $\bar{b}$ (with its associated pricing $\bar{p}$): $q_{\mathrm{MENU}}(x)=0$ for $x<10$, $q_{\mathrm{MENU}}(x)=1/2$ for $10<x<26$, and $q_{\mathrm{MENU}}(x)=1$ for $x>26$, where at the transition points $x=10$ and $x=26$ one can arbitrarily choose any value¹⁰ $0\le q_{\mathrm{MENU}}(10)\le1/2$ and $1/2\le q_{\mathrm{MENU}}(26)\le1$.

The keep-the-pricing extension whose allocation probability is depicted by the blue line in Figure 2 can be recovered from $\bar{b}$ (with its associated pricing $p$): $q_{\mathrm{PRICE}}(x)=0$ for $x<0$, $q_{\mathrm{PRICE}}(x)=1/4$ for $0<x<20$, $q_{\mathrm{PRICE}}(x)=7/10$ for $20<x<30$, and $q_{\mathrm{PRICE}}(x)=1$ for $x>30. Here, the transition points $x\in\{0,20,30\}$ are the subdomain points, and so for $q_{\mathrm{PRICE}}$ to extend $q_0$ we must choose the subgradients to agree with it: $q_{\mathrm{PRICE}}(0)=0$, $q_{\mathrm{PRICE}}(20)=1/2$, and $q_{\mathrm{PRICE}}(30)=1$. Thus, the keep-the-pricing mechanism is uniquely determined here.

Example 2 Selling $k\ge2$ additive goods: $\Gamma=[0,1]^k$, the subdomain is $D_0=\{(0,\ldots,0),(1,\ldots,1)\}$, and the mechanism $\mu_0$ sells the whole bundle $(1,\ldots,1)$ to valuation $(1,\ldots,1)$ at price $k$:

$x$	$q_0(x)$	$s_0(x)$	$b_0(x)$
$(0,\ldots,0)$	$(0,\ldots,0)$	$0$	$0$
$(1,\ldots,1)$	$(1,\ldots,1)$	$k$	$0$

$g$	$p_0(g)$
$(0,\ldots,0)$	$0$
$(1,\ldots,1)$	$k$

We get

Thus, the keep-the-menu extension is the bundling mechanism with bundle price $k$, and the keep-the-pricing extension is the separate-selling mechanism with price 1 for each good (i.e., each good is sold at price 1 independently of the other goods).

Now, $\mu_0$ extracts all the surplus (i.e., $s_0(x)=\sum_i x_i$ for every $x\in D_0$), and so it is the unique optimal mechanism for any random valuation $X$ with support $D_0$. This shows that for multiple goods, the mechanism being optimal, and even uniquely optimal, does not guarantee a unique extension (in contrast to the one-good case: see Appendix § 7.§ 2).

Example 3 Selling two additive goods: $k=2$, $\Gamma=[0,1]^2$, and $\mu_0$ is the following variant of the nonmonotonic mechanism of Hart and Reny [10]:

$x$	$q_0(x)$	$s_0(x)$	$b_0(x)$
(0, 0)	(0, 0)	0	0
(10, 0)	(1, 0)	10	0
(0, 20)	(0, 1)	20	0
(20, 30)	(1, 1)	40	10

$g$	$p_0(g)$
(0, 0)	0
(1, 0)	10
(0, 1)	20
(1, 1)	40

Thus,

and we get

To compute $\bar{b}$, the points that matter are $(g,\underline{p}(g))$ where $g$ is one of the four vertices of $[0,1]^2$ (i.e., $g\in Q_0$), and in addition the point $g^\#=(2/5,1/5)$, where $\underline{p}(g^\#)=4$ (which is an extreme point of the epigraph of $\underline{p}$); we get

Similarly, for $\bar{p}$ the points that matter are $(x,\underline{b}(x))$ where $x$ is one of the four points of $D_0$ (in fact, only $x=(20,30)$ matters), and in addition the point $x^\#=(10,20)$, where $\underline{b}(x^\#)=0$ (which is an extreme point of the epigraph of $\underline{b}$); we get

Thus, $\underline{b}$ and $\bar{b}$ coincide everywhere except in the region $\Delta$ where $g^\#$ is uniquely optimal, which is the interior of the triangle with vertices $(10,0)$, $(0,20)$, and $(20,30)$. This implies that every extension $b$ coincides with them outside $\Delta$ as well, and so in particular every extension to $\mathbb{R}^2$ (or $\mathbb{R}_+^2$) yields a nonmonotonic mechanism: take for instance the two points $y=(1,21)\ll(20,29)=z$ (which are outside the above triangle), then we have $s(y)=20>10=s(z)$. In contrast, the payment function $s_0$ of the given mechanism $\mu_0$ is monotonic on its restricted domain $D_0$.

Proof

Before proving Theorem 1, we summarize the properties of the $b$ and $p$ functions in the following Proposition.

Proof. (i) The four functions are convex since they were defined as suprema of affine functions. The function $\underline{b}$ coincides with $b_0$ on $D_0$ by definition, and similarly $\underline{p}$ coincides with $p_0$ on $Q_0$.

The function $\bar{b}$ is everywhere above $\underline{b}$, because for every $x \in\mathbb{R}^k$ we have

(we used $\underline{p} = p_0$ on $Q_0$). Similarly, $\bar{p} \ge\underline{p}$.

To see that the function $\bar{b}$ is an extension of $b_0$: let $x \in D_0$; for every $g \in\Gamma$ we have $\underline{p}(g) \ge g \cdot x - b_0(x)$ (by the definition of $\underline{p}$), and so $b_0(x) \ge$ $g \cdot x - \bar{p}(g)$; taking the supremum over $g \in\Gamma$ yields $\bar{b}_0(x) \ge\bar{b}(x)$, and so $\bar{b}_0(x) \ge\bar{b}(x) \ge b(x) = b_0(x)$. Similarly, $\bar{p} = p_0$ on $Q_0$.

(ii) We show (9): for every $x \in\mathbb{R}^k$ and $g \in\Gamma$ we have $\bar{b}(x) \ge g \cdot x - p(g)$ (from the definition of $\bar{b}$), and so $p(g) \ge g \cdot x - \bar{b}(x)$, which yields $p(g) \ge\sup_{x \in\mathbb{R}^k}(g \cdot x - \bar{b}(x))$; for the converse inequality, $p(g) = \sup_{x \in D_0}(g \cdot x - b_0(x)) = \sup_{x \in D_0}(g \cdot x - \bar{b}(x)) \le\sup_{x \in\mathbb{R}^k}(g \cdot x - \bar{b}(x))$. Similarly for (8).

(iii) We have $b_0(x) = g \cdot x - p_0(g)$. For every $y \in\mathbb{R}^k$ it then follows that $\bar{b}(y) \ge b(y) \ge g \cdot y - p_0(g)$ (by (i) and the definition of $b$), with equality at $y = x$ (by (i)), and so $g$ is a subgradient at $x$ of both $\bar{b}$ and $b$, and thus also of their restriction $b_0$ to $D_0$. Similarly, $x$ is a subgradient at $g$ of $\bar{p}$, $p$, and $p_0$. ■

We can now prove Theorem 1.

Proof of Theorem 1. (i) Let $B_\Gamma$ be the set of all $\Gamma$-convex functions on $\mathbb{R}^k$: convex functions $b : \mathbb{R}^k \to\mathbb{R}$ that have a subgradient in $\Gamma$ at every $x$, i.e., $\partial b(x) \cap\Gamma\ne\varnothing$ (see Hart and Nisan [9]; note that here we do not require that $b(0,\ldots,0) = 0$). It is well established (Rochet 1985; see also Hart and Nisan 2026) that $b \in B_\Gamma$ if and only if there is a $\Gamma$-mechanism $\mu$ with buyer payoff function $b$: the allocation $q(x)$ is a subgradient of $b$ at $x$.

Now the functions $b$ and $\bar{b}$ are each defined as a supremum of a collection of affine functions with slopes in $\Gamma$ and are everywhere finite, and so they are in$^{12}$ $B_\Gamma$. To make $\mu_i = (q_i,s_i)$, for $i \in\{\mathrm{MENU},\mathrm{PRICE}\}$, an extension of $\mu_0$, set $(q_i,s_i)(x) := (q_0,s_0)(x)$ for every $x \in D_0$ (this is possible since, by Proposition 3 (iii), $q_0(x)$ is a subgradient at $x$ of both $b$ and $\bar{b}$). The canonical pricing functions are $p^\mathrm{c}_\mathrm{MENU} = \bar{p}$ by (6) and $p^\mathrm{c}_\mathrm{PRICE} = p$ by (9).

(ii) These inequalities were established in the text above.

(iii) The definitions of $\bar{p}$ and $p_0^\mathrm{c}$ (see (4), and (7) for $\mu_0$) are identical.

Next, for the canonical pricing function $p^\mathrm{c}$ of an extension $\mu$ of $\mu_0$, for every $g \in\Gamma$ we have, first,

(we used $b\geq\bar{b}$ by (ii) and $D\subseteq\mathbb{R}^{k}$); and second,

(we used $b=b_{0}$ on $D_{0}$ and $D_{0}\subseteq D$). ■

Remarks. (a) By Proposition 3 (i) and (iii), the functions $\underline{b}$ and $\bar{b}$ are “value-and-subgradient” extensions of $b_{0}$, in the sense that they preserve not only the values $b_{0}(x)$ but also the subgradients $q_{0}(x)$, for all $x\in D_{0}$. Moreover, among all $\Gamma$-convex (i.e., in $B_{\Gamma}$) value-and-subgradient extensions of $b_{0}$, the function $\underline{b}$ is the (pointwise) minimal one, and the function $\bar{b}$ is the (pointwise) maximal one. See Figure 3 for the one-good Example 1 above. Similarly, $\underline{p}$ and $\bar{p}$ are the (pointwise) minimal and (pointwise) maximal, respectively, closed¹³ convex value-and-subgradient extensions of $p_{0}$: they preserve the values $p_{0}(g)$ and the subgradients $x$ for which $q_{0}(x)=g$, for all $g\in Q_{0}$. Proposition 4 in Appendix § 7.§ 1 provides a precise statement of these minimality and maximality results. Geometrically, $\underline{b}$ is the upper envelope of the prescribed supporting affine functions (with slopes given by the subgradients), whereas $\bar{b}$ is the largest $\Gamma$-convex extension of the prescribed values (the “$\Gamma$-convexification” of $b_{0}$).

(b) A strengthening of Proposition 3 (iii): For $x\in D_{0}$ and $g\in Q_{0}$, the following are all equivalent: $g$ is optimal for $x\in D_{0}$ in $\mu_{0}$ (i.e., $b_{0}(x)=g\cdot x-p_{0}(g)$, which holds in particular for $g=q_{0}(x)$); $g$ is a subgradient at $x$ of any of the functions $b_{0}$, $\underline{b}$, or $\bar{b}$; and $x$ is a subgradient at $g$ of any of the functions $p_{0}$, $\underline{p}$, or $\bar{p}$ (the proof of Proposition 3 (iii) above holds for any optimal $g$; the rest is straightforward).

(c) One may check that replacing throughout $\mathbb{R}^{k}$ with its nonnegative orthant $\mathbb{R}_{+}^{k}$ does not affect the results (some of the functions may change).

The Fenchel conjugacy in Proposition 3 (ii) is now with respect to $\mathbb{R}_{+}^{k}$ and $\Gamma$ only, and the maximality and minimality of $\bar{p}$ and $\underline{p}$ are within the class of closed nondecreasing convex value-and-subgradient extensions of $p_{0}$ (the functions $\underline{p}$ and $\bar{p}$ are nondecreasing since they are suprema of affine functions of the form $g \cdot x-b(x)$ with $x \in\mathbb{R}_{+}^{k}$, which are thus nondecreasing; see the Remark in Appendix § 7.§ 1 for the modification needed in the proof of Proposition 4 (ii)).

Finally, when the optimal mechanism for a random valuation $X$ with support $D_{0}$ (e.g., a finite support) is unique, this means that its restriction $\mu_{0}$ to $D_{0}$ is unique ($X$-almost surely). Among mechanisms defined on the entire space, there can be many whose restriction to $D_{0}$ is $\mu_{0}$, and hence all of them are optimal for$^{14}$ $X$.

Appendix

The Extreme Buyer Payoff and Pricing Functions

We show here the minimality and maximality properties of the corresponding $b$ and $p$ functions (see Remark (a) after the proof of Theorem 1).

Proof. $(i)$ Upper bound: Let $y \in\mathbb{R}^{k}$; since $\tilde{b}$ is $\Gamma$-convex there is $g \in\partial\tilde{b}(y) \cap\Gamma$, and thus for every $x \in D_{0}$ we have $b_{0}(x) = \tilde{b}(x) \ge\tilde{b}(y) + g \cdot(x-y)$, and so $\tilde{b}(y) \le g \cdot y - (g \cdot x - b_{0}(x))$. This holds for every $x \in D_{0}$, and thus $\tilde{b}(y) \le g \cdot y - \sup_{x \in D_{0}}(g \cdot x - b_{0}(x)) = g \cdot y - \underline{p}(g) \le\bar{b}(y)$. Lower bound: For every $g \in Q_0$ let $x \in D_0$ be such that $g=q_0(x)$, then $g \in\partial\widetilde{b}(x)$, and so $\widetilde{b}(y) \ge\widetilde{b}(x)+g\cdot(y-x)=g\cdot y-(g\cdot x-b_0(x))=g\cdot y-p_0(g)$. This holds for every $g \in Q_0$, and thus $\widetilde{b}(y) \ge\sup_{g\in Q_0}(g\cdot y-p_0(g))=b(y)$.

(ii) Upper bound: Extend $\widetilde{p}$ to $\mathbb{R}^k$ by putting $\widetilde{p}(g)=\infty$ for $g\notin\Gamma$. Denoting the Fenchel conjugate of $f$ by $f^*$, for every $x\in\mathbb{R}^k$ we have $\widetilde{p}^*(x)=\sup_{g\in\mathbb{R}^k}(g\cdot x-\widetilde{p}(g))\ge\sup_{g\in Q_0}(g\cdot x-\widetilde{p}(g))=\sup_{g\in Q_0}(g\cdot x-p_0(g))=b(x)$. Thus $\widetilde{p}^*\ge b$, and so $\widetilde{p}=\widetilde{p}^{**}\le b^*=\overline{p}$ (the first equality by Theorem 12.2 of Rockafellar [14], since $\widetilde{p}$ is closed; the inequality since conjugacy reverses order; and the second equality by (6)).

Lower bound: Let $h\in\Gamma$; for every $x\in D_0$ let $g:=q_0(x)$, then $x\in\partial\widetilde{p}(g)$, and so $\widetilde{p}(h)\ge\widetilde{p}(g)+(h-g)\cdot x=h\cdot x-(g\cdot x-p_0(g))=h\cdot x-b_0(x)$. This holds for every $x\in D_0$, and thus $\widetilde{p}(h)\ge\sup_{x\in D_0}(h\cdot x-b_0(x))=p(h)$. ■

Remark. The proof of the inequality $\widetilde{b}\le\overline{b}$ does not use the subgradient-extension property (only the value-extension property), and that of the inequality $\widetilde{b}\ge b$ does not use the $\Gamma$-convexity property. Similarly, $\widetilde{p}\le\overline{p}$ does not use the subgradient-extension property, and $\widetilde{p}\ge p$ does not use the closedness of $\widetilde{p}$. When dealing with $\mathbb{R}_+^k$ instead of $\mathbb{R}^k$ (see Remark (c) following the proof of Theorem 1) one needs to adapt the proof of $\widetilde{p}\le\overline{p}$: before using conjugacy, extend $\widetilde{p}$ to the nondecreasing closed convex function $\widetilde{P}$ on $\mathbb{R}^k$ given by $\widetilde{P}(h):=\inf_{h\le g\in\Gamma}\widetilde{p}(g)$; then $\widetilde{P}^*(x)=\infty$ for $x\notin\mathbb{R}_+^k$ and $\widetilde{P}^*(x)\ge\sup_{g\in Q_0}(g\cdot x-p_0(g))=b(x)$ for $x\in\mathbb{R}_+^k$, and so $\widetilde{p}(g)=\widetilde{P}(g)=\sup_{x\in\mathbb{R}_+^k}(g\cdot x-\widetilde{P}^*(x))\le\sup_{x\in\mathbb{R}_+^k}(g\cdot x-b(x))=\overline{p}(g)$ for every $g\in\Gamma$.

One-Good Optimal Mechanisms Have Unique Extensions

Consider the case of one good, i.e., $k=1$. A mechanism $\mu_0$ on $D_0$ is optimal for a random valuation $X$ with support¹⁵ $D_0$ if it maximizes the revenue among all IC and IR mechanisms on $D_0$. We will show here that optimal one-good mechanisms have a unique extension.

However, this result holds only for one good: for multiple goods there are in general multiple extensions¹⁶ of an optimal mechanism, even if the mechanism is the unique optimal mechanism. Indeed, Example 2 above is such an instance: $\mu_0$, which is the unique optimal mechanism for any random valuation $X$ with support $D_0$, has $b \ne\bar{b}$, and thus multiple extensions. Thus, for more than one good, even unique optimality does not yield a unique extension as in the one-good case.

To see why the extension is unique for one dimension, let $\mu_0$ be an optimal mechanism for a random valuation $X$ with support $D_0 \subset\mathbb{R}$, which we assume for now to be finite and consist of the points $x_1 < x_2 < \ldots< x_n$ in $\mathbb{R}$. It is easy to see¹⁷ that if $\mu_0$ is optimal then each valuation $x_i$ (for $i \ge2$) is indifferent between its choice $(q_0,s_0)(x_i)$ and the choice $(q_0,s_0)(x_{i-1})$ of the valuation $x_{i-1}$ just below it (see (10) in the proof below). Geometrically, this means that the point $(x_i,b_0(x_i))$ on the graph of $b_0$ lies on the line tangent to $b_0$ at $x_{i-1}$ with slope $q_0(x_{i-1})$. By the value-and-subgradient condition, the buyer payoff function $b$ of any extension $\mu$ of $\mu_0$ must then coincide with this tangent in the interval $[x_{i-1},x_i]$ (because it is a convex function that coincides with $b_0$ at the two end points and it is weakly above the tangent). See Figure 5 (and compare it with Figure 3, where there are multiple extensions, because $(x_i,b_0(x_i))$ is strictly above the tangent at $x_{i-1}$). In multiple dimensions, binding IC constraints may link types in different directions, and there is no analogous linear ordering of types.

For simplicity assume that $0 \in D_0$ and $\mu_0$ satisfies $q_0(0) = 0$ and $s_0(0) = 0$, and so IR is just IC with respect to $0$.

Proof. Let $\mu=(q,s)$ be an extension of $\mu_0$ to the entire space $\mathbb{R}$ (its existence is guaranteed by our main result), and so its buyer payoff function $b$ is a value-and-subgradient $\Gamma$-convex (and thus nondecreasing and nonexpansive) extension of $b_0$. Since $D_0$ is closed, its complement $D_0^C:=\mathbb{R}\backslash D_0$ is an open set, and thus the union of open bounded intervals $(y,z)$ with $y,z\in D_0$, together with, possibly, two open half-lines $(-\infty,y)$ and $(z,\infty)$ with $y,z\in D_0$. We will show that $b(x)$ is uniquely determined on $D_0^C$ and affine on each such connected component of $D_0^C$; consequently $q(x)=b'(x)$ and $s(x)=q(x)x-b(x)$ are uniquely determined there as well.

Consider first an interval $(y,z)\subseteq D_0^C$ with $y<z$ and $y,z\in D_0$. By IC we have $b_0(z)=q_0(z)z-s_0(z)\geq q_0(y)z-s_0(y)$. We claim that the optimality of $\mu_0$ implies equality, i.e.,

since otherwise increasing the payments of all $x\geq z$ in $D_0$ by the same sufficiently small $\epsilon>0$ preserves all IC and IR constraints and strictly increases the revenue.¹⁸ Geometrically, (10) says that the point $(z, b_0(z))$ lies on the line through $(y, b_0(y))$ with slope $q_0(y)$, and so $b$ must coincide with this line on the interval $[y,z]$; i.e., $b(x) = L(x)$ for every $x \in[y,z]$, where $L$ is the affine function $L(x) := q_0(y)x - s_0(y)$. Indeed, since $b(y) = b_0(y) = L(y)$ and $b(z) = b_0(z) = L(z)$, and $L$ is affine and $b$ is convex, we have, first, $b(x) \le L(x)$ for every $x$ in $[y,z]$; and second, $b(x) \ge L(x)$ for every $x$ by the value-and-subgradient condition at $y \in D_0$. Thus $b(x) = L(x)$, and so $q(x) = b'(x) = L'(x) = q_0(y)$, for every $x$ in $(y,z)$.

Next, assume that $(z,\infty) \subseteq D_0^C$, and so $z \in D_0$ is the maximal point in $D_0$. Then $q_0(z) = 1$ (otherwise the revenue, which we assumed finite and positive, can be increased: multiply $q_0$ and $s_0$ by $1+\varepsilon$ for small enough $\varepsilon> 0$ so that $(1+\varepsilon)q_0(z) \le1$, which preserves IC and IR and multiplies the revenue by $1+\varepsilon$), and thus for every $x$ we have $b(x) \ge q_0(z)x - s_0(z) = x - s_0(z)$ (by the value-and-subgradient condition at $z \in D_0$), and for $x > z$ we have $b(x) \le b(z) + (x-z) = z - s_0(z) + x - z = x - s_0(z)$ (by nonexpansiveness). Thus $b(x) = x - s_0(z)$ and its derivative $b'(x) = q(x) = 1$ are uniquely determined for all $x > z$.

Finally, assume that $(-\infty,y) \subseteq D_0^C$, and so $y \in D_0$ is the minimal point in $D_0$. Then $b_0(y) = 0$ (because $b_0(y) \ge0$ by IR, and $b_0(y) \le b_0(0) = 0$ since $y \le0 \in D_0$ and $b_0$ is nondecreasing). Therefore $b(x) \le b(y) = b_0(y) = 0$ for every $x < y$ (because $b$ is nondecreasing), and $b(x) \ge q_0(0)x - s_0(0) = 0$ (by the value-and-subgradient condition at $0 \in D_0$). Thus $b(x) = 0$ and $q(x) = b'(x) = 0$ are uniquely determined for all $x < y$.

Thus $b$ and $q = b'$ (and thus $s(x) = q(x)x - b(x)$) are uniquely determined on the complement $D_0^C$ of $D_0$; since on $D_0$ they are given by $\mu_0$, the uniqueness of $\mu$ has been established. ■

The proof shows the uniqueness of the extension of the optimal $\mu_0$ to any domain $D$ that contains $D_0$.