Proof of 1. As an auxiliary step, we show that the homothety class \[\mathop{\mathrm{HC}}(M)=\{(\lambda,t)\in \mathbb{R}_+\times\mathbb{R}^d \mid \lambda \mathop{\mathrm{ext}}M + t\subset A \}\] of \(M\in\mathcal{M}\) is a polytope. \(\mathop{\mathrm{HC}}(M)\) is bounded because \(A\) is bounded. Therefore, it suffices to show that \(\mathop{\mathrm{HC}}(M)\) is the intersection of finitely many halfspaces. Define \[\begin{align} \mathop{\mathrm{HC}}_-(M,H)&= \{(\lambda,t)\in \mathbb{R}\times\mathbb{R}^d \mid \lambda\mathop{\mathrm{ext}}M + t\subset H_- \}\\ &= \left\{(\lambda,t)\in \mathbb{R}\times\mathbb{R}^d \;\middle\vert \;\lambda \max_{a\in \mathop{\mathrm{ext}}M} a \cdot n_H + t \cdot n_H \leq c_H\right\}, \end{align}\] where \(H_-=\{z \in \mathbb{R}^d: z \cdot n_H \leq c_H \}\) is the halfspace that contains \(A\) and is bounded by the facet-defining hyperplane \(H\in\mathcal{F}\) of \(A\). Each \(\mathop{\mathrm{HC}}_-(M,F)\) is a halfspace in \(\mathbb{R}^{d+1}\) (with normal \((\max_{a\in \mathop{\mathrm{ext}}M} a \cdot n_H,n_H)\)). Thus, letting \(Z=\mathbb{R}_{+}\times\mathbb{R}^d\), we conclude that \(\mathop{\mathrm{HC}}(M)=Z\cap \bigcap_{H\in\mathcal{F}} \mathop{\mathrm{HC}}_-(M,H)\) is a polytope.

Note that \((\lambda,t)=(1,0)\in\mathop{\mathrm{ext}}\mathop{\mathrm{HC}}(M)\) if and only if there do not exist \(M',M''\in\mathcal{M}\) homothetic to \(M\) such that \(M=\frac{1}{2}M'+\frac{1}{2}M''\). If \(M'\) is homothetic to \(M\), then \(M''\) is also homothetic to \(M\) or \(M''=t+\Theta^\circ\) for some \(t\in\mathbb{R}^d\).

Thus, we complete the proof by showing that \(M\) is exhaustive if and only if \((\lambda,t)=(1,0)\in\mathop{\mathrm{ext}}\mathop{\mathrm{HC}}(M)\). Note that \((\lambda,t)=(1,0)\) does not lie on the boundary of \(Z\). Every other halfspace \(\mathop{\mathrm{HC}}_-(M,H)\) of \(\mathop{\mathrm{HC}}(M)\) corresponds to a facet-defining hyperplane \(H\in\mathcal{F}\) of \(A\), and \(H\in\mathcal{F}(\lambda M+t)\) if and only if \((\lambda,t)\in\mathop{\mathrm{bndr}}\mathop{\mathrm{HC}}_{-}(M,H)\) (i.e., \(\lambda\max_{a\in \mathop{\mathrm{ext}}M} a\cdot n_H+t\cdot n_H=c_H\)). By definition, \(M\) is exhaustive if there is no \((\lambda,t)\in \mathop{\mathrm{HC}}(M)\) such that \(\mathcal{F}(M)\subseteq\mathcal{F}(\lambda M+t)\). Then, by construction, \(M\) is exhaustive if and only if \((\lambda,t)=(1,0)\) lies on an inclusion-wise maximal set of facet-defining hyperplanes of \(\mathop{\mathrm{HC}}(M)\). The latter condition is equivalent to \((\lambda,t)=(1,0)\in\mathop{\mathrm{ext}}\mathop{\mathrm{HC}}(M)\). ◻

Proof of 2. By 1, \(M\in \mathcal{M}\) is not exhaustive if and only if \(M\) has a decomposition into homothets in \(\mathcal{M}\), that is, there exist \(M',M''\in\mathcal{M}\) homothetic to \(M\) such that \(M=\frac{1}{2}M'+\frac{1}{2}M''\). Suppose \(\mathop{\mathrm{ext}}M=\{a\}\) is a singleton. Then, \(M\) has a decomposition into homothets in \(\mathcal{M}\) if and only if \(a\notin\mathop{\mathrm{ext}}A\). Thus, for the remainder of the proof, assume that \(\mathop{\mathrm{ext}}M\) is not a singleton.

\(M\) has a decomposition into homothets in \(\mathcal{M}\) if and only if one of the following holds:

1. There exists a direction \(t \in\mathbb{R}^d\setminus\{0\}\) such that \(\mathop{\mathrm{ext}}M+t\) and \(\mathop{\mathrm{ext}}M-t\) are both subsets of \(A\) (translation).

2. There exists a point \(z\in\mathbb{R}^d\) and \(\varepsilon>0\) such that \(z+(1+\varepsilon) (\mathop{\mathrm{ext}}M-z)\) and \(z+(1-\varepsilon) (\mathop{\mathrm{ext}}M-z)\) are both subsets of \(A\) (dilation with center \(z\)).

This is because any homothety is itself either a translation or dilation.⁴¹ We complete the proof by showing that (1) and (2) above are equivalent, respectively, to the negations of (1) and (2) in the statement of the lemma.

Suppose (1) holds. Then \(t\) is orthogonal to all the normals of the hyperplanes in \(\mathcal{F}(M)\) for otherwise there is a point \(a\in \mathop{\mathrm{ext}}M\cap H\), for some \(H\in\mathcal{F}(M)\), such that \(a+t\notin H\) or \(a-t\notin H\), which contradicts that \(\mathop{\mathrm{ext}}M+t\) and \(\mathop{\mathrm{ext}}M-t\) are subsets of \(A\). Hence the spanning condition \(\mathop{\mathrm{span}}\{n_H\}_{H\in\mathcal{F}(M)} =\mathbb{R}^d\) is violated. Conversely, if the spanning condition is violated, there is a direction \(t\in\mathbb{R}^d\setminus\{0\}\) such that \(t\) is orthogonal to all the facet normals in \(\mathcal{F}(M)\). Then, \(\mathop{\mathrm{ext}}M+t\) and \(\mathop{\mathrm{ext}}M-t\) will still satisfy the facet-defining inequalities of \(A\) for \(||t||\) sufficiently small, that is, \(\mathop{\mathrm{ext}}M+t,\mathop{\mathrm{ext}}M-t\subset A\).

Suppose (2) holds. Consider any \(H\in\mathcal{F}(M)\) and \(a\in \mathop{\mathrm{ext}}M\cap H\). Then \(z\in H\), for otherwise \(z+(1+\varepsilon)(a-z)\) or \(z+(1-\varepsilon)(a-z)\) is not in \(A\). Thus, since \(z\in H\) for any \(H\in\mathcal{F}(M)\) such that \(\mathop{\mathrm{ext}}M\cap H\neq\emptyset\), we have \(\bigcap_{H\in\mathcal{F}(M)} H\neq\emptyset\). Conversely, if \(\bigcap_{H\in\mathcal{F}(M)} H\neq\emptyset\), choose any \(z\in \bigcap_{H\in\mathcal{F}(M)} H\). For \(\varepsilon>0\) sufficiently small, \(z+(1+\varepsilon) (\mathop{\mathrm{ext}}M-z)\) and \(z+(1-\varepsilon) (\mathop{\mathrm{ext}}M-z)\) are both subsets of \(A\). This is because \(\mathop{\mathrm{ext}}M\) is uniformly bounded away from facet-defining hyperplanes \(H\notin\mathcal{F}(M)\) and because \(a\in H\in\mathcal{F}(M)\) implies \((z+(1\pm\varepsilon) (a-z))\in H\). ◻

Proof of 1. Let \(M\in\mathop{\mathrm{ext}}\mathcal{M}\) be the extended menu associated with a mechanism \(x\in\mathop{\mathrm{ext}}\mathcal{X}\). Recall that \(\mathop{\mathrm{menu}}(x)=\mathop{\mathrm{ext}}M\) by 3 (\(\mathop{\mathrm{ext}}M\) is closed since \(d=2\)); thus, we show \(|\mathop{\mathrm{ext}}M|\leq |\mathcal{F}|\).

If \(\mathop{\mathrm{cone}}\Theta\neq\mathbb{R}^2\), then some vertex in \(\mathop{\mathrm{ext}}M\) is inflexible for otherwise \(M\in\mathop{\mathrm{ext}}\mathcal{M}\) has a flexible chain. If \(\mathop{\mathrm{cone}}\Theta=\mathbb{R}^2\) and no vertex in \(\mathop{\mathrm{ext}}M\) is inflexible, then \(M\) can only not have a flexible chain or loop if every vertex in \(\mathop{\mathrm{ext}}M\) is semi-flexible. In this case, \(|\mathop{\mathrm{ext}}M|\leq |\mathcal{F}|\). Thus, we assume that \(\mathop{\mathrm{ext}}M\) contains an inflexible vertex.

Consider any two inflexible vertices \(a,a'\in\mathop{\mathrm{ext}}M\) such that the chain \(S=(a_1,\ldots,a_n)\) in between \(a\) and \(a'\) in the adjacency relation consists of flexible and semi-flexible allocations (\(a=a'\) if there is only one inflexible vertex in \(\mathop{\mathrm{ext}}M\)). Without loss, assume \((a,a_1,\ldots,a_n,a')\) are ordered clockwise. Let \((H_1,\ldots,H_k)\subset\mathcal{F}\) be the sequence of feasibility constraints traversed when moving from \(a\) to \(a'\) clockwise along the boundary of \(A\).

We show that \(n\leq k-1\). Since \(M\in\mathop{\mathrm{ext}}\mathcal{M}\), \(S\) does not contain a flexible chain. Thus, \(S\) contains either (1) at most one flexible vertex or (2) two adjacent flexible vertices \(a_i\) and \(a_{i+1}\) such that \(\overline{a_ia_{i+1}}\subset H_j\) for some \(j=2,\ldots,k-1\). In the first case, since \(a\in H_1\) and \(a'\in H_k\), there are at most \(k-2\) semi-flexible vertices in \(S\); hence \(n\leq k-1\). In the second case, since \(a\in H_1\), \(a'\in H_k\), and \(a_i,a_{i+1}\in H_j\), there are at most \(k-3\) semi-flexible vertices in \(S\); hence \(n\leq k-1\).

In total, we then have \(|\mathop{\mathrm{ext}}M|\leq |\mathcal{F}|\). The necessity of exhaustiveness follows from 1. ◻

Proof of 2. The necessity of exhaustiveness follows from 1. Denseness in the exhaustive mechanisms follows from 2 below. Since \(\mathcal{X}\) is a compact and convex subset of a normed vector space ([lem:isomorphisms,lem:Hausdorff]), the set of extreme points is a \(G_\delta\) (aliprantis2007infinite?). ◻

Proof of 3. Immediate from [lem:indecomposable+exhaustive,lem:general_position_indecomposable]. ◻

Proof of 1. Let \(x\in\mathcal{X}\) be exhaustive with associated extended menu \(M\in\mathcal{M}\) such that \(\mathop{\mathrm{menu}}(x)=\mathop{\mathrm{ext}}M\) is finite and non-separating. Note that general position is preserved under small perturbations of the points in \(\mathop{\mathrm{ext}}M\). Openness then follows since two extended menus with the same number of extreme points are close in the Hausdorff distance if and only if the extreme points can be matched bijectively with pairwise small Euclidean distance (cf.13).

We also use that non-separation is preserved under small perturbations of the points in \(\mathop{\mathrm{ext}}M\). For a given extreme point \(a\in\mathop{\mathrm{ext}}M\) of the polyhedron \(M\in\mathcal{M}\), the normal cone \[\label{eq:normalcone} N_M(a):=\bigl\{\theta\in\mathop{\mathrm{cone}}\Theta:\;a\in\mathop{\mathrm{arg\,max}}_{\tilde{a}\in\mathop{\mathrm{ext}}M} \tilde{a}\cdot\theta\bigr\}\tag{5}\] is closed. For every \(\varepsilon>0\), sufficiently small perturbations of the menu items in \(\mathop{\mathrm{ext}}M\) produce a polyhedron \(\tilde{M}\in\mathcal{M}\) with corresponding extreme point \(a'\in\mathop{\mathrm{ext}}\tilde{M}\) such that \(N_{\tilde{M}}( a')\cap\Theta\) lies entirely within the \(\varepsilon\)-neighborhood of \(N_M(a)\cap \Theta\). Thus, if \(\Theta\setminus N_M(a)\) is connected, then \(\Theta\setminus N_{\tilde{M}}(a')\) is connected whenever the perturbations are sufficiently small.

We prove denseness by constructing extended menus \(\tilde{M}\in\mathop{\mathrm{ext}}\mathcal{M}\) that are arbitrarily close to \(M\) in the Hausdorff distance and satisfy \(|\mathop{\mathrm{ext}}M|=|\mathop{\mathrm{ext}}\tilde{M}|\).

For this, we perturb \(\mathop{\mathrm{ext}}M\) into general position while preserving exhaustiveness; call the resulting set \(W\). More explicitly, if \(\mathop{\mathrm{ext}}M\) is a singleton, then \(M\in\mathop{\mathrm{ext}}\mathcal{M}\). If \(|\mathop{\mathrm{ext}}M|\geq 2\), select an inclusion-wise minimal subset \(V\subseteq\mathop{\mathrm{ext}}M\) such that the hyperplanes in \(\mathcal{F}\) that contain a point of \(V\) satisfy conditions (1) and (2) in 2 (this necessitates \(2\le |V|\le d+1\)). For each \(a\in V\), if \(a\in \mathop{\mathrm{aff}}(V\setminus\{a\})\), move \(a\) outside \(\mathop{\mathrm{aff}}(V\setminus\{a\})\) while keeping \(a\) on the hyperplanes in \(\mathcal{F}\) intersected by \(a\), that is, in the face \(F=\bigcap\{H\in\mathcal{F}\mid a\in H\}\cap A\). To see that this is possible, note that if \(a\) intersects \(1\leq k\leq d\) hyperplanes in \(\mathcal{F}\), then \(\mathop{\mathrm{dim}}F \geq (d-k)\) whereas \(\mathop{\mathrm{dim}}\mathop{\mathrm{aff}}(V\setminus\{a\})\leq (d-k)\) by the minimality of \(V\). Also by the minimality of \(V\), \(F\not\subseteq \mathop{\mathrm{aff}}(V\setminus\{a\})\), hence the desired perturbation is possible. By construction, the resulting perturbed set \(V\) is in general position. Now iteratively perturb the remaining points in \(\mathop{\mathrm{ext}}M\setminus V\) until the resulting set \(W\) is in general position. Obviously \(|W|=|\mathop{\mathrm{ext}}M|\).

Define \(\tilde{M}=\mathop{\mathrm{conv}}W+\Theta^\circ\). By construction, \(\tilde{M}\) is a polyhedron in \(\mathcal{M}\) that is arbitrarily close to \(M\). For all sufficiently small perturbations, \(W\) is in convex position, that is, no point of \(W\) lies in the convex hull of the others, because \(\mathop{\mathrm{ext}}M\) was in convex position. In addition, for all \(a,a'\in W\), we have \(a\notin a'+\Theta^\circ\) since the same holds for all \(a,a'\in\mathop{\mathrm{ext}}M\) and since \(\Theta^\circ\) is closed. Thus, \(\mathop{\mathrm{ext}}\tilde{M}=W\). Moreover, \(\tilde{M}\) is exhaustive by the construction of \(V\). Since \(\mathop{\mathrm{ext}}\tilde{M}\) is also in general position and non-separating, \(\tilde{M}\in\mathop{\mathrm{ext}}\mathcal{M}\) by 3. ◻

Proof of 2. Fix an exhaustive extended menu \(M\in\mathcal{M}\) and \(\varepsilon>0\). Choose a finite set \(V\subseteq \mathop{\mathrm{ext}}M\) such that the facet-defining hyperplanes in \(\mathcal{F}\) that contain a point in \(V\) are exactly the hyperplanes in \(\mathcal{F}(M)\) and such that, for every \(a\in \mathop{\mathrm{ext}}M\), there exists \(v\in V\) with \(||a-v||\leq \varepsilon\). Let \(M_0:=\mathop{\mathrm{conv}}V+\Theta^\circ\in\mathcal{M}\). By 2, \(M_0\) is exhaustive. By 13, \(d(M_0,M)\leq \varepsilon\). By construction, \(|\mathop{\mathrm{ext}}M_0|<\infty\).

We iteratively perturb \(M_0\) to eliminate all separating vertices \((a_1,\ldots,a_n)\), i.e., those vertices of \(M_0\) for which \(\mathop{\mathrm{cone}}\Theta\setminus N_{M_0}(a_i)\) is disconnected (cf.@eq:eq:normalcone ).

Suppose \(M_{i-1}\in \mathcal{M}\) is exhaustive, has separating vertices \((a_{i},\ldots,a_n)\), and is arbitrarily close to \(M_0\).

We construct an exhaustive \(M_i\in \mathcal{M}\) with separating vertices \((a_{i+1},\ldots,a_n)\) arbitrarily close to \(M_{i-1}\). Pick a hyperplane \[H_i:=\{\theta\in \mathop{\mathrm{cone}}\Theta:\; n_i\cdot \theta=0\}\] with \(H_i\cap \mathop{\mathrm{int}}N_{M_{i-1}}(a_i)\neq\emptyset\) such that both subcones \[C_i^\pm:=N_{M_{i-1}}(a_i)\cap\{\pm n_i\cdot\theta\ge 0\}\] have connected complements in \(\mathop{\mathrm{cone}}\Theta\). If for small \(\varepsilon>0\) we have \(a_i+ \varepsilon n_i\in A\), set \(a_{i}^{-}:=a_i\) and \(a_{i}^{+}:=a_i+\varepsilon n_i\). Otherwise, if \(a_i- \varepsilon n_i\in A\), set \(a_{i}^{+}:=a_i\) and \(a_{i}^{-}:=a_i-\varepsilon n_i\). If \(a_i\pm \varepsilon n_i\notin A\), then the line \(L(a_i)=\{a_i+\alpha n_i:\alpha\in\mathbb{R}\}\) intersects \(M_{i-1}\) only in the point \(a_i\). For \(a\in A\), define the smallest face of \(A\) containing \(a\): \[F(a):= A \cap \bigcap_{H \in \mathcal{F}(a)} H, \quad \text{where} \quad \mathcal{F}(a):= \{ H \in \mathcal{F} : a \cdot n_H = c_H \}.\] Choose \(a'_i\in \mathop{\mathrm{int}}A\) with \(||a_i-a'_i||\leq\varepsilon\) such that \(\dim F(a_i^-)=\dim F(a_i)+1\) or \(\dim F(a_i^+)=\dim F(a_i)+1\), where \(a_i^-\) and \(a_i^+\) are the endpoints of the line segment \(L(a_i')\cap A\). Let \[M_i:=\mathop{\mathrm{conv}}\left((\mathop{\mathrm{ext}}M_{i-1}\setminus\{a_i\})\cup\{a_{i}^{-},a_{i}^{+}\}\right)+\Theta^\circ.\] By construction, \(d(M_i,M_{i-1})=O(\varepsilon)\). Up to a set of types of measure \(O(\varepsilon)\), types in \(C_i^+\) select \(a_{i}^{+}\), types in \(C_i^-\) select \(a_{i}^{-}\), and all other types make the same choices as from \(M_{i-1}\). Hence \(\mathop{\mathrm{cone}}\Theta\setminus N_{M_i}(a_{i}^{\pm})\) is connected by the choice of \(H_i\). By construction, \[\mathop{\mathrm{span}}\{n_H\}_{H\in\mathcal{F}(a_i)}=\mathop{\mathrm{span}}\{n_H\}_{H\in\mathcal{F}(a_i^+)\cup\mathcal{F}(a_i^-)}.\] By 2, \(M_i\) is exhaustive. Thus, \(M_i\) has all the desired properties.

Finally, by 1, \(M_n\) is arbitrarily close to an element of \(\mathop{\mathrm{ext}}\mathcal{M}\) with finite menu size, which completes the proof. ◻

Proof of 4. We begin with a few definitions. For \(\tilde{\mathcal{M}}\subseteq \mathcal{M}\), let \(\mathop{\mathrm{exh}}\tilde{\mathcal{M}}\) denote the set of exhaustive extended menus in \(\tilde{\mathcal{M}}\). Let \(\mathcal{B}_k\subset\mathop{\mathrm{exh}}\mathcal{M}\) denote the set of exhaustive extended menus that have a bounded face \(f\) with \(\mathop{\mathrm{diam}}(f)\geq \frac{1}{k}\) and outer unit normal vector \(n_f\in\Theta\) such that \(d(n_f,\mathop{\mathrm{bndr}}\mathop{\mathrm{cone}}\Theta)\geq 1/k\) (which is satisfied by convention if \(\mathop{\mathrm{bndr}}\mathop{\mathrm{cone}}\Theta=\emptyset\), that is, \(\mathop{\mathrm{cone}}\Theta=\mathbb{R}^d\)).⁴⁴

We define \(\mathop{\mathrm{exh}}\mathcal{M}^{sc}:=\mathop{\mathrm{exh}}\mathcal{M}\setminus\bigcup_{k=1}^\infty \mathcal{B}_k\) and note that the mechanism \(x\in\mathcal{X}\) associated with an extended menu \(M\in\mathop{\mathrm{exh}}\mathcal{M}^{sc}\) is continuous on \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) (in particular, \(\mathop{\mathrm{menu}}(x)\) is uncountable whenever it is not a singleton). This is because, for each \(M\in\mathop{\mathrm{exh}}\mathcal{M}^{sc}\) and \(\theta\in\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\), \(\mathop{\mathrm{arg\,max}}_{a\in M} \theta\cdot a\) is a singleton for otherwise the boundary of \(M\) would contain a line segment connecting two extreme points of \(M\). In particular, \(x(\theta)\) is uniquely determined by \(M\) on \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) in the payoff-equivalence class. Therefore, the associated indirect utility function \(U\in\mathcal{U}\) is differentiable on \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\). A differentiable convex function on an open domain is continuously differentiable on that domain (rockafellar1997convex?). Hence, \(U\) is continuously differentiable on \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) and therefore \(x=\nabla U\) is continuous on \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\).

Using the previous observation, we complete the proof by showing that \(\mathop{\mathrm{ext}}\mathcal{M}\cap \mathop{\mathrm{exh}}\mathcal{M}^{sc}\) is a dense \(G_\delta\) in \(\mathop{\mathrm{exh}}\mathcal{M}\). \(\mathcal{M}\) is a compact metric space (13), hence a Baire space. The same holds for the closed, hence compact subset \(\mathop{\mathrm{exh}}M\subset \mathcal{M}\). By the Baire category theorem and since \(\mathop{\mathrm{ext}}\mathcal{M}\) is a dense \(G_\delta\) in \(\mathop{\mathrm{exh}}\mathcal{M}\) (2), it remains to show that \(\mathop{\mathrm{exh}}\mathcal{M}^{sc}\) is a dense \(G_\delta\) in \(\mathop{\mathrm{exh}}\mathcal{M}\).

By definition, \(\mathop{\mathrm{exh}}\mathcal{M}^{sc}\) is a \(G_\delta\) if each \(\mathcal{B}_k\) is closed. Consider any convergent sequence \(\{M_i\}_{i\in\mathbb{N}}\subset\mathcal{B}_k\) with limit \(M\in\mathop{\mathrm{exh}}\mathcal{M}\). We show \(M\in\mathcal{B}_k\). By definition, for each \(i\in\mathbb{N}\), there exists a line segment \(L_i\subseteq\mathop{\mathrm{bndr}}M_i\) of length \(\geq \frac{1}{k}\) with normal vector \(n_i\in\mathop{\mathrm{cone}}\Theta\cap\mathbb{S}^{d-1}\) such that \(d(n_i,\mathop{\mathrm{bndr}}\mathop{\mathrm{cone}}\Theta)\geq \frac{1}{k}\). By selecting a subsequence if necessary, we may assume that the line segments \(\{L_i\}_{i\in\mathbb{N}}\) and the normal vectors \(\{n_i\}_{i\in\mathbb{N}}\) converge to limits \(L^*\subset A\) and \(n^*\in\mathop{\mathrm{cone}}\Theta\cap\mathbb{S}^{d-1}\), respectively, because \(\mathop{\mathrm{cone}}\Theta\cap\mathbb{S}^{d-1}\) and \(A\) are compact. It is routine to verify that \(L^*\subseteq \mathop{\mathrm{bndr}}M\), \(L^*\) has length \(\geq \frac{1}{k}\), \(n^*\) is normal to \(L^*\) on \(\mathop{\mathrm{bndr}}M\), and \(d(n^*,\mathop{\mathrm{bndr}}\mathop{\mathrm{cone}}\Theta)\geq \frac{1}{k}\). Thus, \(M\in\mathcal{B}_k\).

To show denseness of \(\mathop{\mathrm{exh}}\mathcal{M}^{sc}\), consider the set \(\mathop{\mathrm{exh}}\mathcal{M}\setminus\mathcal{B}_k\) for some arbitrary \(k\in\mathbb{N}\). By the previous paragraph, \(\mathop{\mathrm{exh}}\mathcal{M}\setminus \mathcal{B}_k\) is relatively open in \(\mathop{\mathrm{exh}}\mathcal{M}\). Moreover, \(\mathop{\mathrm{exh}}\mathcal{M}\setminus \mathcal{B}_k\) is dense in \(\mathop{\mathrm{exh}}\mathcal{M}\) because every extended menu \(M\in\mathop{\mathrm{exh}}\mathcal{M}\) can be approximated by an extended menu in \(\mathop{\mathrm{exh}}\mathcal{M}\) whose bounded faces have diameter \(< \frac{1}{k}\).⁴⁵ We have that \(\mathop{\mathrm{exh}}\mathcal{M}^{sc}=\bigcap_{k=1}^\infty(\mathop{\mathrm{exh}}\mathcal{M}\setminus\mathcal{B}_k)\) is a countable intersection of relatively open and dense sets in a Baire space. Thus, by the Baire category theorem, \(\mathop{\mathrm{exh}}\mathcal{M}^{sc}\) is dense in \(\mathop{\mathrm{exh}}\mathcal{M}\). ◻

Proof. Suppose \(x\) satisfies the hypotheses but \(x'\) dominates \(x\).

We first show that \(U'\geq U\). Extend \(U\) and \(U'\) to \(\mathop{\mathrm{cone}}\Theta\) by 1-homogeneity. By dominance, \[\nabla_{\bar v} U'(\theta)\geq \nabla_{\bar v} U(\theta) \quad \text{for a.e. } \theta\in\mathop{\mathrm{cone}}\Theta,\] where \(\bar v =(0,\ldots,0,1)\). For a given \(\theta\in\mathop{\mathrm{cone}}\Theta\) and \(t\in\mathbb{R}_-\), define \(z(t)=\theta+t \bar v\) and \(h(t)=U'(z(t))-U(z(t))\). Note that \(h\) is the difference of two convex functions restricted to the ray \(z(\mathbb{R}_-)\subset\mathop{\mathrm{cone}}\Theta\), hence absolutely continuous on compact intervals and differentiable almost everywhere. By Fubini’s theorem, for a.e. \(\theta\in\mathop{\mathrm{cone}}\Theta\), \(\nabla_{\bar v} U'(z(t))\geq \nabla_{\bar v} U(z(t))\) holds for a.e. \(t\in\mathbb{R}_-\). For such \(t\), \(\dot{h}(t)\geq 0\) by the chain rule, so \(h\) is non-decreasing. If \(\lim_{t\to-\infty} U(z(t))>0\), then \(x\) would have to allocate some goods with positive probability without charging any payment, which would contradict that \(x\) excludes the lowest type. Hence, \(\lim_{t\to-\infty}h(t)\geq 0\). Thus, \(h\geq 0\). Since this holds for a.e. \(\theta\in\mathop{\mathrm{cone}}\Theta\) and indirect utility functions are continuous, \(U'\geq U\), as desired.

Since \(x\) has no distortion at the top \(\theta^*=(1,\ldots,1,-1)\), we must have \(U'(\theta^*)=U(\theta^*)\). Otherwise, if \(U'(\theta^*)>U(\theta^*)\), then revenue at \(x'(\theta^*)\) is lower than revenue at \(x(\theta^*)\) (since \(x(\theta^*)\) maximizes surplus). The same would hold in an open neighborhood of \(\theta^*\) by IC since our no-distortion condition requires that \(\theta^*\) uniquely prefers to buy the grand bundle of all goods, contradicting dominance.

We next construct an auxiliary objective \(\tilde{v}:\mathop{\mathrm{cone}}\Theta\to\mathbb{R}^d\). For each \(i=1,\ldots,m=d-1\), let \[\tilde{v}_i(\theta)=\begin{cases} 0 &\text{if } |\theta_i/\theta_d|<1-\varepsilon_i\\ -1+\varepsilon_i &\text{if } |\theta_i/\theta_d|\geq 1-\varepsilon_i \end{cases} \quad\text{and}\quad \tilde{v}_d(\theta)=1,\] where a small perturbation vector \(\varepsilon\in\mathbb{R}^{m}_{++}\) will be needed to rigorously address non-differentiabilities. The objective \(\tilde{v}\) differs from revenue-maximization only if \(\theta\) is willing to pay (nearly) the maximum amount for good \(i=1,\ldots,d-1\), in which case a cost of (nearly) \(1\) is incurred when good \(i\) is sold to \(\theta\). Crucially, since \(x\) has no marginal distortions at the top in each dimension (meaning type \(\theta\in\Theta\) with \(\theta_i=1\) strictly prefers allocations where good \(i=1,\ldots,m\) is allocated with probability 1), we have \[x'(\theta)\cdot \tilde{v}(\theta)\geq x(\theta)\cdot \tilde{v}(\theta)-\delta(\varepsilon)\] for a.e. \(\theta\in\Theta\), where \(\delta(\varepsilon)\to 0\) as \(||\varepsilon||_\infty\to 0\) by IC and the compactness of \(\Theta\). Using a.e. differentiability and 1-homogeneity, for a.e. \(\theta\in\mathop{\mathrm{cone}}\Theta\), \[\label{eq:dominance95monopoly} \nabla_{\tilde{v}(\theta)} U'(\theta)\geq \nabla_{\tilde{v}(\theta)} U(\theta)-\delta(\varepsilon).\tag{6}\]

Since \(U'\neq U\) and \(U'\geq U\), there exists \(\theta^0\in\Theta\) such that \(U'(\theta^0)>U(\theta^0)\). For the sake of clarity, we complete the proof with a slightly informal argument; the footnote below fills in the gaps. The integral curve of (a smoothed version) of the vector field \(\theta\mapsto\tilde{v}(\theta)\) with initial condition \(\theta^0\) connects \(\theta^0\) to \(\lambda\theta^*\) for some \(\lambda\in\mathbb{R}_{++}\) as \(\varepsilon\to 0\). By 6 , \(U'(\lambda\theta^*)-U'(\lambda\theta^*)+O(\delta(\varepsilon))\geq U'(\theta^0)-U(\theta^0)>0\), a contradiction with \(U'(\theta^*)=U(\theta^*)\) by the 1-homogeneity of indirect utilities.⁴⁶ ◻

Proof of 9 (Monopoly Problem). Suppose not, that is, \(V(\theta)=x(\theta)\cdot\bar v=x'(\theta)\cdot\bar v\) for undominated IC and IR mechanisms \(x\) and \(x'\). With the same arguments as in 10, we get \(\dot{h}=0\). Since \(x\) and \(x'\) necessarily exclude the lowest type (otherwise they allocate goods for free), \(\lim_{t\to\infty} h(t)=0\). Thus, \(h=0\) and \(U=U'\). We conclude \(x=x'\). ◻

Proof of 5. The first claim about weak rationalizability is immediate from [lem:undomi_monopoly,lem:undominated_optimal]. For the denseness claim, take any \(M\in\mathcal{M}\) associated with an IC and IR mechanism \(x\in\mathcal{X}\). Define the pricing function \(p:[0,1]^m\to\mathbb{R}_+\) (cf.hart2015maximal?) via \[p(b)=\min\{t\in\mathbb{R}_+\mid (b,t)\in M\}.\] Since \(M\) is closed and convex, \(p\) is well-defined and convex and \(p(0)=0\) by IR. The form of the polar cone \(\Theta^\circ\) for the monopoly problem implies \(\nabla_{e_i} p(b)\in[0,1]\) for the directional derivative in unit direction \(e_i\) for all \(b\in[0,1)^m\) and \(i=1,\ldots,m\). For all sufficiently small \(\varepsilon>0\), define the pricing function \(p^\varepsilon(b)=(1-2\varepsilon)p(b)+\varepsilon \mathbf{1}\cdot b\) for all \(b\in[0,1]^m\) and \(M^\varepsilon=\mathop{\mathrm{epi}}p^\varepsilon + \Theta^\circ\). Then, \(p^\varepsilon\) is also convex, \(p^\varepsilon(0)=0\), and \(\nabla_{e_i} p^\varepsilon(b)=(1-2\varepsilon)\nabla_{e_i} p(b)+\varepsilon\in[\varepsilon,1-\varepsilon]\). As \(\varepsilon\to 0\), the Hausdorff distance \(d(\mathop{\mathrm{epi}}p, \mathop{\mathrm{epi}}p^{\varepsilon})\to 0\). By 13, \(d(M^\varepsilon,M)\to 0\). The IC and IR mechanisms \(x^\varepsilon\) associated with the extended menus \(M^\varepsilon\) must exclude the lowest type and have no marginal distortion at the top in each dimension because the marginal prices \(\nabla_{e_i} p^\varepsilon(b)\) are bounded away from 0 and 1, so the lowest type prefers to buy nothing whereas any type with \(\theta_i=1\) prefers to buy the maximum amount of good \(i\).

We observe that the undominated extreme points are dense in the set of 1 and 3 mechanisms when \(m\geq 2\). As in the previous paragraph, for any extended menu \(M\in\mathcal{M}\) corresponding to some 1 and 3 mechanism, take an extended menu \(M^\varepsilon\) with \(d(M,M^\varepsilon)\leq\varepsilon\) and corresponding marginal prices in \([\varepsilon,1-\varepsilon]\), which is hence undominated. In particular, \((0,\ldots,0,0),(1,\ldots,1,p)\in\mathop{\mathrm{ext}}M^\varepsilon\) for some price \(p>0\) for the grand bundle, hence \(M^\varepsilon\) is exhaustive by 2. As in the proofs for [cor:open_dense_finite,cor:dense], apply an arbitrarily small perturbation to \(M^\varepsilon\) to obtain an extended menu \(M^*\in \mathop{\mathrm{ext}}\mathcal{M}\) with \((0,\ldots,0,0),(1,\ldots,1,p)\in\mathop{\mathrm{ext}}M^*\). As long as all perturbations are sufficiently small and carried out in the price dimension, the marginal prices of \(M^*\) are still bounded away from 0 and 1, hence \(M^*\) is undominated.

We complete the proof by showing that the strongly rationalizable mechanisms are dense in the undominated extreme points. Fix any undominated extreme point \(x\in\mathop{\mathrm{ext}}\mathcal{X}\). Let \(V\in\mathop{\mathrm{ext}}\mathcal{V}\) be the associated principal’s indirect utility function. 8 shows that there is a sequence \((V^n)_{n\in\mathbb{N}}\subset\exp_+\mathcal{V}\) such that \(V^n\to V\). By 9, for each \(n\in\mathbb{N}\) there is a unique IC and IR mechanism \(x^n\in\mathcal{X}\) that generates \(V^n\); hence each \(x^n\) is strongly rationalizable (with a strictly positive belief density). Since \(\mathcal{X}\) is compact, up to taking a subsequence, \(x_n\to x'\in\mathcal{X}\) in \(L^1\). By continuity of the map \(\mathcal{X}\to\mathcal{V}\), \(x'\) must generate \(V\). Again by 9, \(x=x'\), as desired. ◻

Proof. If not, give the agent discretion to choose \(0\) in addition to \(\mathop{\mathrm{menu}}(x)\). Since \(b\in\mathbb{R}_{++}\), whenever the agent prefers \(0\) over \(\mathop{\mathrm{menu}}(x)\), so does the principal. Since \(0\in\mathop{\mathrm{ext}}A\), a positive measure of types prefers 0 to \(\mathop{\mathrm{menu}}(x)\); hence the mechanism with menu \(\{0\}\cup\mathop{\mathrm{menu}}(x)\) dominates \(x\).

Let \(x,x'\in\mathcal{X}\) with indirect utilities \(U,U'\in\mathcal{U}\) and assume \(0\in \mathop{\mathrm{menu}}(x)\). Suppose for contradiction that \(x'\) dominates \(x\), that is, \[(\theta-b)\cdot\bigl(x'(\theta)-x(\theta)\bigr)\;\ge\;0 \quad\text{for a.e.\;}\theta\in\mathbb{S}^{d-1},\] with strict inequality on a set of positive measure. By the same argument as in the first paragraph, \(0\in \mathop{\mathrm{menu}}(x')\). Since \(x\in\partial U\) and \(x'\in\partial U'\) and using 1-homogeneity of indirect utilities, \[\label{eq:dom} \frac{U'(\theta)-U(\theta)}{||\theta||}\;\ge\;\nabla_b\bigl(U'(\theta)-U(\theta)\bigr) \qquad\text{for a.e.\;}\theta\in\mathbb{R}^d.\tag{7}\]

Fix a generic \(\theta\in\mathbb{S}^{d-1}\) and consider the ray \(z(t):=\theta+tb\) with \(t\in\mathbb{R}\) and its norm \(r(t):=\|z(t)\|\) (which is bounded away from 0 for \(\theta\) not collinear with \(b\)). Define \[h(t)\;:=\;U'\bigl(z(t)\bigr)-U\bigl(z(t)\bigr).\] Note that \(h\) is the difference of two convex functions restricted to a line, hence absolutely continuous on compact sets and differentiable almost everywhere. For a.e. \(\theta\in\mathbb{S}^{d-1}\), 7 holds a.e. along the ray \(z(t)\) (Fubini) and, by the chain rule, \[\label{eq:ode} \dot{h}(t)\;\le\;\frac{h(t)}{r(t)} \quad\text{for a.e. } t\in\mathbb{R}.\tag{8}\]

Because \(0\in \mathop{\mathrm{menu}}(x)\cap \mathop{\mathrm{menu}}(x')\), there exists \(T\in\mathbb{R}\) such that \(U(z(t))=U'(z(t))=0\) for all \(t\leq T\). Let \[\Psi(t) := \exp\left(-\int_{T}^{t}\frac{ds}{r(s)}\right)\,h(t),\] so that \[\dot{\Psi}(t) = \exp\left(-\int_{T}^{t}\frac{ds}{r(s)}\right)\left(\dot{h}(t)-\frac{h(t)}{r(t)}\right)\;\le\;0 \quad\text{for a.e.\;}t.\] Hence \(\Psi(t)\) is nonincreasing. By construction, \(\Psi(T)=0\). Thus, \(\Psi\leq 0\) and \(h\leq 0\), so \(h\) is also nonincreasing by 8 . Since \(\theta\in\mathbb{S}^{d-1}\) was generic and \(U\) and \(U'\) are continuous, we have \(U'\leq U\).

As an intermediate step, we note \(\lim_{t\to\infty}\frac{h(t)}{r(t)}=0\) whenever \(||b||<1\). Since \(U'\leq U\) and \(x'\) dominates \(x\), we have \[1\leq \frac{x'(\theta^*)\cdot(\theta^*-b)}{x(\theta^*)\cdot(\theta^*-b)}=\frac{U'(\theta^*)}{U(\theta^*)}\leq 1,\] so \(U'(\theta^*)=U(\theta^*)\). Continuity and 1-homogeneity of \(U\) and \(U'\) imply \[\lim_{t\to\infty}\frac{h(t)}{r(t)}=\lim_{t\to\infty} (U'-U)\left(\frac{\theta+tb}{||\theta+tb||}\right)=0.\]

To conclude, we show \(h\equiv 0\). Since \(h\leq 0\) and \(h\) is non-increasing, if \(h\not\equiv 0\), then \(h(t)<0\) for all sufficiently large \(t\). Note that \(\dot{r}(t)=\frac{(\theta+tb)\cdot b}{||\theta+tb||}\to||b||\in(0,1)\) as \(t\to\infty\). Thus, for all sufficiently large t, \[\frac{d}{dt}\left(\frac{h}{r}\right)(t)=\frac{\dot{h} r-h\dot{r}}{r^2}\leq \frac{\frac{h}{r}r-h\dot{r}}{r^2}=\frac{(1-\dot{r})h}{r^2}<0.\] Since \(h/r<0\), we contradict \(\lim_{t\to\infty}\frac{h(t)}{r(t)}=0\). Thus, \(h\equiv 0\). Since \(\theta\in\mathbb{S}^{d-1}\) was generic and \(U\) and \(U'\) are continuous, we have \(U'= U\), so \(x'=x\), a contradiction. ◻

Proof of 9 (Delegation Problem). Suppose not, that is, \(V(\theta)=x(\theta)\cdot v(\theta)=x'(\theta)\cdot v(\theta)\) for undominated IC mechanisms \(x\) and \(x'\). Then, in the proof of 11, 7 and 8 hold with equality. Hence \(\Psi=0\) implies \(h=0\) implies \(U=U'\). We conclude \(x=x'\). ◻

Proof. We first show that the conditions given in the statement are necessary. For this, fix any IC and IR mechanism \(x\). It is clear that \(\underaccent{\bar}{a}\in\mathop{\mathrm{menu}}(x)\) for otherwise \(x\) is not IR since there is a type \(\underaccent{\bar}{\theta}\) for which \(\underaccent{\bar}{a}\) is their (unique) most preferred alternative in \(A\). If \(\mathop{\mathrm{menu}}(x)\) does not contain the principal’s favorite alternative \(a^*\in\mathop{\mathrm{ext}}A\), obtain a new IC and IR mechanism \(x'\) by letting the agent choose from \(\mathop{\mathrm{menu}}(x)\cup\{a^*\}\). Thus, for all \(\theta\in\Theta\), either \(x'(\theta)=x(\theta)\) or \(x'(\theta)=a^*\). Since \(a^*\in\mathop{\mathrm{ext}}A\), there is a positive measure of types for which \(a^*\) is their most preferred allocation in \(A\). Thus, \(x'\) dominates \(x\).

For sufficiency, suppose \(x\) is an IC and IR mechanism such that \(\underaccent{\bar}{a}, a^*\in \mathop{\mathrm{menu}}(x)\). For the sake of contradiction, suppose the IC and IR mechanism \(x'\) dominates \(x\). By the same argument as in the previous paragraph, \(\underaccent{\bar}{a},a^*\in\mathop{\mathrm{menu}}(x')\). Let \(U\) and \(U'\) be the agent’s indirect utility functions associated with \(x\) and \(x'\), respectively.

We complete the proof. Since \(x\in\partial U\) and \(x'\in\partial U'\) and using 1-homogeneity of indirect utilities and dominance, \[\label{eq:dom2} \nabla_b\bigl(U'(\theta)-U(\theta)\bigr)\geq 0 \qquad\text{for a.e.\;}\theta\in\mathbb{R}^d.\tag{9}\] Fix a generic \(\theta\in\mathbb{S}^{d-1}\) and consider the ray \(z(t):=\theta+tb\) with \(t\in\mathbb{R}\). Define \[h(t)\;:=\;U'\bigl(z(t)\bigr)-U\bigl(z(t)\bigr).\] Note that \(h\) is the difference of two convex functions restricted to a line, hence absolutely continuous on compact sets and differentiable almost everywhere. For a.e. \(\theta\in\mathbb{S}^{d-1}\), 9 holds a.e. along the ray \(z(t)\) (Fubini) and, by the chain rule, \(\dot{h}(t)\;\ge 0\) for a.e. \(t\in\mathbb{R}\). Because \(\underaccent{\bar}{a},a^*\in \mathop{\mathrm{menu}}(x)\cap \mathop{\mathrm{menu}}(x')\), there exists \(T\in\mathbb{R}_+\) such that \(U(z(t))=U'(z(t))=0\) for all \(t\leq -T\) and \(U(z(t))=U'(z(t))=a^*\cdot z(t)\) for all \(t\geq T\). Hence, \(h(t)=0\) for all \(t\leq -T\) and \(t\geq T\). Since \(\dot{h}(t)\;\ge 0\), \(h\equiv 0\). Since \(\theta\in\mathbb{S}^{d-1}\) was generic and \(U\) and \(U'\) are continuous, we have \(U'= U\), so \(x'=x\), a contradiction. ◻

Proof of 9 (Veto Bargaining Problem). Immediate from the proof of 12. ◻

Proof of 13. We have \[\begin{align} d(M,M')&=\inf\left\{\varepsilon>0:\: M\subseteq M'+\varepsilon B \text{ and } M'\subseteq M+\varepsilon B \right\}\\ &=\inf\left\{\varepsilon>0:\: \begin{multlined} \mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M+\Theta^\circ\subseteq \mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M'+\Theta^\circ+\varepsilon B \text{ and } \\ \mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M'+\Theta^\circ\subseteq \mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M+\Theta^\circ+\varepsilon B \end{multlined} \right\}\\ &\leq \inf\left\{\varepsilon>0:\: \begin{multlined} \mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M\subseteq \mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M'+\varepsilon B \text{ and } \\ \mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M'\subseteq \mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M+\varepsilon B \end{multlined} \right\}\\ &=d(\mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M,\mathop{\mathrm{conv}}\mathop{\mathrm{ext}}M')<\infty, \end{align}\] where the first inequality is because \(Z_1\subseteq Z_2\) implies \(Z_1+Z_3\subseteq Z_2+Z_3\) for \(Z_1,Z_2,Z_3\subset\mathbb{R}^d\), and the second inequality is because \(A\) is compact.

We conclude that \((\mathcal{M},d)\) is a metric space since extended menus are closed, since the Hausdorff distance is an extended metric on the space of all closed subsets of \(\mathbb{R}^d\), and since the distance is finite by the first paragraph.

It remains to show that \((\mathcal{M},d)\) is compact. Consider any sequence \(\{M_n\}_{n\in\mathbb{N}}\subset\mathcal{M}\). By Blaschke’s selection theorem, \(\{\mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}\mathop{\mathrm{ext}}M_n\}_{n\in\mathbb{N}}\) has a convergent subsequence \(\{\mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}\mathop{\mathrm{ext}}M_{n_k}\}_{k\in\mathbb{N}}\) with compact convex limit \(K\subseteq A\). Let \(M=K+\Theta^\circ\in\mathcal{M}\). By the first paragraph, the subsequence \(\{ M_{n_k}\}_{k\in\mathbb{N}}\) convergences to \(M\in\mathcal{M}\). Thus, \(\mathcal{M}\) is compact. ◻

Proof of 3. We first show that \(\Phi_1,\Phi_2,\) and \(\Phi_3\) are well defined and bijective.

The map \(\Phi_1:\mathcal{X}\to\mathcal{M}\) is well-defined. To see this, let \(M=\mathop{\mathrm{conv}}\mathop{\mathrm{menu}}(x)+\Theta^\circ\). We have \(\mathop{\mathrm{ext}}M=\mathop{\mathrm{ext}}(\mathop{\mathrm{conv}}\mathop{\mathrm{menu}}(x)+\Theta^\circ)\subseteq \mathop{\mathrm{ext}}(\mathop{\mathrm{conv}}\mathop{\mathrm{menu}}(x))\subset A\) since \(\Theta^\circ\) is a cone. \(M\) is closed and convex because it is a sum of a compact convex set and a closed convex set.

The map \(\Phi_2:\mathcal{M}\to\mathcal{U}\) is also well-defined. To see this, observe that the support function \(U:z\mapsto\sup_{y\in M} y\cdot z\) of \(M\in\mathcal{M}\) is an indirect utility function in \(\mathcal{U}\). This is because \(\sup_{y\in M} y\cdot z <\infty\) if and only if \(z\in \mathop{\mathrm{cone}}\Theta\) since \(\mathop{\mathrm{recc}}M = \Theta^\circ\). In this case, \(\mathop{\mathrm{arg\,max}}_{a\in \mathop{\mathrm{ext}}M} a\cdot\theta\subset A\) is non-empty for all \(\theta\in\Theta\) and every selection from the argmax defines an IC mechanism with indirect utility function \(U\).

We next show that the composition \(\Phi_2\circ\Phi_1\) assigns to each IC mechanism \(x\in\mathcal{X}\) its indirect utility function \(U\in\mathcal{U}\). This is because \[U(\theta) = \max_{a\in \mathop{\mathrm{menu}}(x)} a\cdot \theta = \max_{y\in \mathop{\mathrm{conv}}\mathop{\mathrm{menu}}(x)+\Theta^\circ} y\cdot \theta = ((\Phi_2\circ\Phi_1)(x))(\theta).\] To see the first equality, note that by the definition of the essential range, \(x(\theta)\in\mathop{\mathrm{arg\,max}}_{a\in \mathop{\mathrm{menu}}(x)} a\cdot \theta\) for a.e. \(\theta\in\Theta\). Thus, \(U(\theta) =\max_{a\in \mathop{\mathrm{menu}}(x)} a\cdot \theta\) for a.e. \(\theta\in\Theta\). Since \(U\) is continuous and the essential range \(\mathop{\mathrm{menu}}(x)\) is closed (support of a measure on \(A\)), the equality holds for every \(\theta\in\Theta\).

We observe that the composition \(\Phi_2\circ\Phi_1\) is bijective. It is injective by the definition of payoff-equivalence and surjective since \(\mathcal{U}\) is defined as the set of all indirect utility functions associated with the mechanisms in \(\mathcal{X}\).

We can now conclude that \(\Phi_1:\mathcal{X}\to\mathcal{M}\) and \(\Phi_2:\mathcal{M}\to\mathcal{U}\) are bijective because \(\Phi_2\circ\Phi_1\) is bijective and \(\Phi_2\) is injective. The latter holds since support functions \(U\) defined on \(\mathbb{R}^d\), where we set \(U(z)=\infty\) for \(z\notin \mathop{\mathrm{cone}}\Theta\), uniquely determine their associated closed convex sets (hiriart1996convex?).

It remains to verify that the inverse of \(\Phi_2\circ\Phi_1:\mathcal{X}\to\mathcal{U}\) is given by \(\Phi_3:\mathcal{U}\to\mathcal{X}\). Take any mechanism \(x\in\mathcal{X}\) with \(M=\Phi_1(x)\in\mathcal{M}\) and \(U\in\Phi_2(M)\in\mathcal{U}\). We have \(x(\theta)\in \mathop{\mathrm{arg\,max}}_{a \in M} a \cdot \theta\) since the indirect utility function \(U\) is the support function of \(M\). \(\partial U(\theta)=\mathop{\mathrm{arg\,max}}_{a \in M} a \cdot \theta\) is a standard property of support functions (hiriart1996convex?).

We next show that \(\Phi_1,\Phi_2,\) and \(\Phi_3\) are affine. That \(\Phi_2:\mathcal{M}\to\mathcal{U}\) commutes with convex combinations is standard property of support functions (hiriart1996convex?). That \(\Phi_3:\mathcal{U}\to\mathcal{X}\) commutes with convex combinations follows immediately from the linearity of the gradient map, which is defined almost everywhere. Thus, \(\Phi_1:\mathcal{X}\to\mathcal{M}\) must also commute with convex combinations.

A sequence of closed convex sets converges in the Hausdorff distance if and only if the associated support functions converge with respect to the sup norm on any compact set (salinetti1979convergence?). Thus, since the Hausdorff distance between any two extended menus in \(\mathcal{M}\) is finite (13), \(\Phi_2\) is a homeomorphism. Since \(\mathcal{M}\) is compact, \(\mathcal{U}\) is also compact.

We next show that \(\Phi_3\) is continuous. Consider any convergent sequence \(\{U_n\}_{n\in\mathbb{N}}\subset\mathcal{U}\) with limit \(U\in\mathcal{U}\). Let \(D_n\subset\mathop{\mathrm{cone}}\Theta\) be the set of points where \(U_n\) is differentiable, and let \(D\subset\mathop{\mathrm{cone}}\Theta\) be the set of points where \(U\) is differentiable (extend indirect utility functions to \(\mathop{\mathrm{cone}}\Theta\) using 1-homogeneity). Let \(D^*=D\cap\bigcap_{n\in\mathbb{N}} D_n\). Indirect utility functions are convex and therefore almost everywhere differentiable. Moreover, the countable union of nullsets is null; thus \(\mathop{\mathrm{cone}}\Theta\setminus D^*\) is null. We have \(\nabla U_n(\theta) \to \nabla U(\theta)\) for all \(\theta\in D^*\) (hiriart1996convex?). Thus, \(x_n=\Phi_3(U_n)\to \Phi_3(U) = x\) pointwise almost everywhere. Since support functions are sublinear, the Dominated Convergence theorem implies convergence in \(L^1\).

Finally, a continuous bijection \(\Phi_3:\mathcal{U}\to\mathcal{X}\) from a compact space to a Hausdorff space is a homeomorphism; consequently, \(\Phi_1=(\Phi_3\circ\Phi_2)^{-1}\) is a homeomorphism.

It remains to show that for an IC mechanism \(x\in\mathcal{X}\) with associated extended menu \(M=\Phi_1(x)\in\mathcal{M}\) and associated indirect utility function \(U=\Phi_2(M)\in\mathcal{U}\), \[\mathop{\mathrm{menu}}(x)=\mathop{\mathrm{cl}}\{\nabla U(\theta):\: U \text{ is differentiable at } \theta\}=\mathop{\mathrm{cl}}\mathop{\mathrm{ext}}M.\]

For the first equality, let \(D=\{\theta\in\Theta:\: U \text{ is differentiable at } \theta\}\). Suppose \(a\notin\mathop{\mathrm{cl}}\nabla U(D)\). Then, \(\nabla U^{-1}(\tilde{A})=\emptyset\) for any sufficiently small open neighborhood \(\tilde{A}\) of \(a\). Since \(x=\nabla U\) almost everywhere, \(x^{-1}(\tilde{A})\) is a nullset. Hence, \(a\notin \mathop{\mathrm{menu}}(x)\). Conversely, suppose \(a\in\mathop{\mathrm{cl}}\nabla U(D)\). Let \(\tilde{A}\) be any open neighborhood of \(a\). Then there exists \(\theta^*\in D\) with \(\nabla U(\theta^*)\in\tilde{A}\). Choose an open set \(B\) such that \(\nabla U(\theta^*)\in B\subset\tilde{A}\). Since \(\partial U\) is upper hemi-continuous (hiriart1996convex?) and \(\partial U(\theta^*)=\{\nabla U(\theta^*)\}\), there exists an open neighborhood \(\tilde{\Theta}\) of \(\theta^*\) such that \(\partial U(\theta)\subset B\) for all \(\theta\in\tilde{\Theta}\). In particular, for almost every \(\theta\in\tilde{\Theta}\), \(\nabla U(\theta)\in B\subset\tilde{A}\). Hence \(x^{-1}(\tilde{A})\) has positive measure. Since \(\tilde{A}\) was arbitrary, \(a\in\mathop{\mathrm{menu}}(x)\).

For the second equality, \(\partial U(\theta)=\{a^*\}\), that is, \(U\) is differentiable at \(\theta\), if and only if \(\max_{a\in M} a\cdot\theta\) has the unique solution \(a^*\) (hiriart1996convex?). Thus, \(a^*\) is an exposed point of \(M\). Conversely, any exposed point \(a^*\) of \(M\) is the unique maximizer of \(\max_{a\in M} a\cdot\theta\) for some \(\theta\in\Theta\). Hence, \(\{\nabla U(\theta):\: U \text{ is differentiable at } \theta\}=\exp M\). Straszewicz’s theorem shows that \(\mathop{\mathrm{ext}}M\subseteq\mathop{\mathrm{cl}}\exp M\) for a closed convex set \(M\). ◻

Proof of 4. We show the converse assuming that \(A\) is the unit simplex and \(\Theta\) is unrestricted. In this case, extended menus are exactly the convex bodies (non-empty compact convex sets) contained in the allocation space. By 1, if \(M\) is not exhaustive, then \(M\notin\mathop{\mathrm{ext}}\mathcal{M}\). Thus, it remains to show that if \(M\) is decomposable, then \(M\notin\mathop{\mathrm{ext}}\mathcal{M}\).

For any convex body \(K\subset\mathbb{R}^d\), let \[\Delta(K)=\left\{z\in\mathbb{R}^d\;\middle \vert \;\sum_{i=1}^d z_i\leq \max_{a\in K} \sum_{i=1}^d a_i \right\}\cap\bigcap_{i=1}^d \left\{z\in\mathbb{R}^d\;\middle \vert \; z_i\geq \min_{a\in K} a_i \right\}\] denote the smallest simplex that contains \(K\) and is homothetic to the allocation simplex \(A\). \(\Delta(\cdot)\) commutes with Minkowski addition because the function \(K\mapsto \max_{z\in K} z\cdot\theta\) commutes with Minkowski addition for any \(\theta\in\mathbb{R}^d\) and because the non-empty intersection of parallel translates of facet-defining halfspaces of a simplex is homothetic to that simplex.

Suppose the extended menu \(M \in \mathcal{M}\) is decomposable; that is, there exist convex bodies \(K', K'' \subset \mathbb{R}^d\) not homothetic to \(M\) such that \(M = K' + K''\). By the previous paragraph, \[\label{eq:simplices} \Delta(M)=\Delta(K')+\Delta(K'')\subseteq A.\tag{10}\] By definition of \(\Delta(\cdot)\), there exist \(s,t\in\mathbb{R}^d\) and \(\lambda,\rho>0\) such that \[\label{eq:simplex95transform} \dfrac{\Delta(K')-s}{\lambda}=\Delta(M)=\dfrac{\Delta(K'')-t}{\rho}\tag{11}\] Solving 11 for \(\Delta(K')\) and \(\Delta(K'')\), respectively, and plugging into 10 yields \(s+t=0\) and \(\rho+\lambda=1\). Now, \[M=K'+K''=\lambda\underbrace{\dfrac{K'-s}{\lambda}}_{=M'} + (1-\lambda)\underbrace{\dfrac{K''+s}{1-\lambda}}_{=M''}.\] \(M',M''\in\mathcal{M}\) are convex bodies in \(A\) not homothetic to \(M\) because \(\Delta(M')=\Delta(M'')=\Delta(M)\subseteq A\). ◻

Proof of 5. For the unrestricted type space, that is, \(\mathop{\mathrm{cone}}\Theta=\mathbb{R}^2\), extended menus are convex bodies. meyer1972decomposing? and silverman1973decomposition? show that the indecomposable convex bodies in the plane are exactly points, line segments, and triangles; hence \(|\mathop{\mathrm{ext}}M|\leq 3\). For a restricted type space, the same bound \(|\mathop{\mathrm{ext}}M|\leq 3\) holds trivially because a mechanism/extended menu that is not an extreme point on the unrestricted type space is not an extreme point on any restricted type space either. Suppose, then, the type space is restricted. Since \(|\mathop{\mathrm{ext}}M|\leq 3\), \(\mathop{\mathrm{ext}}M\) is in general position. Moreover, \(\mathop{\mathrm{ext}}M\) is non-separating if and only if \(|\mathop{\mathrm{ext}}M|\leq 2\). 6 completes the proof. ◻

Proof of 6. Suppose \(M\in\mathcal{M}\) and \(\mathop{\mathrm{ext}}M\) with \(|\mathop{\mathrm{ext}}M|<\infty\) is separating the type space. Pick \(a\in\mathop{\mathrm{ext}}M\) so that \(\{\theta\in\mathop{\mathrm{cone}}\Theta:\;a\notin\mathop{\mathrm{arg\,max}}_{\tilde{a}\in \mathop{\mathrm{ext}}M}\tilde{a}\cdot\theta\}\) is disconnected with components \(\{\theta\in\mathop{\mathrm{cone}}\Theta:\;\mathop{\mathrm{arg\,max}}_{\tilde{a}\in \mathop{\mathrm{ext}}M}\tilde{a}\cdot\theta\cap(A^2\cup\{a\})=\emptyset\}\) and \(\{\theta\in\mathop{\mathrm{cone}}\Theta:\;\mathop{\mathrm{arg\,max}}_{\tilde{a}\in \mathop{\mathrm{ext}}M}\tilde{a}\cdot\theta\cap(A^1\cup\{a\})=\emptyset\}\), where \(A^1\cup A^2\cup\{a\}=\mathop{\mathrm{ext}}M\). For \(\varepsilon>0\) sufficiently small, set \[A^1_\pm:=\{a+(1\pm\varepsilon)(b-a):\;b\in A^1\} \quad \text{and} \quad M_\pm:=\mathop{\mathrm{conv}}(A^1_\pm\cup A^2\cup\{a\})+\Theta^\circ\in\mathcal{K}.\] Define \(T_\pm:\mathop{\mathrm{ext}}M\to\mathop{\mathrm{ext}}M_\pm\) by \(T_\pm(a)=a\), \(T_\pm(b)=a+(1\pm\varepsilon)(b-a)\) for \(b\in A^1\), and \(T_\pm(c)=c\) for \(c\in A^2\).

We claim that, for every \(\theta\in\Theta\), the maximizers in \(M_\pm\) are the image under \(T_\pm\) of the maximizers in \(M\), that is, \[\mathop{\mathrm{arg\,max}}_{y\in\mathop{\mathrm{ext}}M_\pm}y\cdot\theta = T_\pm\big(\mathop{\mathrm{arg\,max}}_{y\in\mathop{\mathrm{ext}}M}y\cdot\theta\big).\] This is because: (i) within \(A^1\), \(\mathop{\mathrm{arg\,max}}_{b\in A^1}(a+(1\pm\varepsilon)(b-a))\cdot\theta=\mathop{\mathrm{arg\,max}}_{b\in A^1}(b-a)\cdot\theta\); (ii) points in \(A^2\cup\{a\}\) are fixed under \(T_\pm\); (iii) for any \(b\in A^1\), \((a+(1\pm\varepsilon)(b-a))\cdot\theta-a\cdot\theta=(1\pm\varepsilon)(b-a)\cdot\theta\), so the sign of \(b\cdot\theta-a\cdot\theta\) is preserved; (iv) by the choice of \(a\), there are no \(A^1\)–\(A^2\) ties. Using the isomorphism between extended menus and mechanisms/choice functions (3), we conclude \(M=\frac{1}{2}M_+ +\frac{1}{2}M_-\). Since \(M_\pm\) are not homothetic to \(M\), \(M\) is not indecomposable.

For the converse, suppose \(M\in\mathcal{M}\) and \(\mathop{\mathrm{ext}}M\) with \(|\mathop{\mathrm{ext}}M|<\infty\) is in general position and non-separating. If \(\mathop{\mathrm{cone}}\Theta=\mathbb{R}^d\), then \(M\) is a polytope and, by general position of \(\mathop{\mathrm{ext}}M\), it is a simplicial polytope. We can therefore apply shephard1963decomposable? to conclude that \(M\) is indecomposable. Thus, henceforth suppose \(\mathop{\mathrm{cone}}\Theta\neq\mathbb{R}^d\), which implies \(0\notin\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\).

Say that \(a,b\in\mathop{\mathrm{ext}}M\) are adjacent if \(\{a,b\}=\mathop{\mathrm{arg\,max}}_{\tilde{a}\in \mathop{\mathrm{ext}}M} \tilde{a}\cdot\theta\) for some \(\theta\in\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\); equivalently, if the normal cones \(N_M(a)\) and \(N_M(b)\) intersect in a common \((d-1)\)-dimensional face, where we remind the reader that \(N_M(a)=\bigl\{\theta\in\mathop{\mathrm{cone}}\Theta:\;a\in\mathop{\mathrm{arg\,max}}_{\tilde{a}\in\mathop{\mathrm{ext}}M} \tilde{a}\cdot\theta\bigr\}.\)

We observe that \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\setminus N_M(a)\) is path-connected. Since \(\mathop{\mathrm{ext}}M\) is non-separating, \(\mathop{\mathrm{cone}}\Theta\setminus N_M(a)\) is connected; in fact, path-connected because both sets are closed and convex. Any path connecting \(\theta,\theta'\in\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) through \(\mathop{\mathrm{cone}}\Theta\) admits a uniform neighborhood that does not intersect \(N_M(a)\) because a path is compact and \(N_M(a)\) is closed. Hence, \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\setminus N_M(a)\) is path-connected.

We next show that \(\mathop{\mathrm{bndr}}N_M(a)\cap\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) is path-connected. Fix any arbitrary \(\theta^*\in\mathop{\mathrm{int}}N_M(a)\), which is non-empty because normal cones to extreme points are full-dimensional. Define the gauge \[\phi(\theta)=\inf\{\lambda>0:\: (\theta-\theta^*)\in \lambda(N_M(a)-\theta^*)\}.\] Since the gauge of the closed convex set \((N_M(a)-\theta^*)\) is continuous (e.g., hiriart1996convex?), the map \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\setminus N_M(a)\to\mathop{\mathrm{bndr}}N_M(a)\cap \mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) given by \(\theta\mapsto\theta^*+\frac{\theta-\theta^*}{\phi(\theta)}\) is continuous. It has values in \(\mathop{\mathrm{bndr}}N_M(a)\) by construction and in \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) because \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) is convex. Fix any \(\theta,\theta'\in\mathop{\mathrm{bndr}}N_M(a)\cap\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\). Let \(\varepsilon>0\) be so small that \(\theta+(1+\varepsilon)(\theta-\theta^*),\theta'+(1+\varepsilon)(\theta'-\theta^*)\in\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\). By the previous paragraph, find a path \(\gamma:[0,1]\to \mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\setminus N_M(a)\) such that \(\gamma(0)=\theta+(1+\varepsilon)(\theta-\theta^*)\) and \(\gamma(1)=\theta'+(1+\varepsilon)(\theta'-\theta^*)\). Then the image of \(\gamma\) under the continuous map \(\theta\mapsto\theta^*+\frac{\theta-\theta^*}{\phi(\theta)}\) is a path in \(\mathop{\mathrm{bndr}}N_M(a)\cap\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) from \(\theta\) to \(\theta'\).

We further observe that any two points in \(\mathop{\mathrm{bndr}}N_M(a)\cap\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) can be connected by a path that does not traverse any face of \(N_M(a)\) of dimension \(d-3\) or lower (except at the endpoints) because \(\mathop{\mathrm{bndr}}N_M(a)\cap\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) is relatively open in \(\mathop{\mathrm{bndr}}N_M(a)\).

Let \(\mathcal{T}\) denote the set of bounded \(2\)-dimensional faces of \(M\), that is, triangular faces of \(M\) since \(\mathop{\mathrm{ext}}M\) is in general position. We say that \(\mathcal{T}'\subseteq\mathcal{T}\) is strongly connected if for any two triangles \(\Delta_1,\Delta_n\in\mathcal{T}'\) there exists a sequence of triangles \((\Delta^1,\Delta^2,\ldots,\Delta^{n-1},\Delta^n)\), each in \(\mathcal{T}'\), such that consecutive triangles share a common edge.

We next claim that if \(\mathop{\mathrm{ext}}|M|\geq 3\), then every \(a\in \mathop{\mathrm{ext}}M\) has an adjacent vertex \(b\in\mathop{\mathrm{ext}}M\) such that \(\mathcal{T}(a)\cap\mathcal{T}(b)\neq\emptyset\). This is because \(a\) has a least two neighbors, for otherwise the removal of \(N_M(b)\) disconnects \(\mathop{\mathrm{cone}}\Theta\), so the path connecting the corresponding \((n-1)\)-dimensional faces of \(N_M(a)\) can be chosen to traverse a common \((n-2)\)-dimensional face of \(a\) and \(b\), which corresponds to a triangle containing both \(a\) and \(b\).

Let \(\mathcal{T}(a)\subseteq\mathcal{T}\) denote the subset of triangles containing the vertex \(a\in \mathop{\mathrm{ext}}M\); we show that \(\mathcal{T}(a)\) is strongly connected. Triangles containing \(a\) correspond to \((d-2)\)-dimensional faces of \(N_M(a)\) contained in \(\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\), and two triangles share an edge containing \(a\) if the corresponding \((d-2)\)-dimensional faces of \(N_M(a)\) are contained in a common \((d-1)\)-dimensional face of \(N_M(a)\). Consider any path joining two \((d-2)\)-dimensional faces in \(\mathop{\mathrm{bndr}}N_M(a)\cap\mathop{\mathrm{int}}\mathop{\mathrm{cone}}\Theta\) that traverses no faces of dimension \((d-3)\) or less. The \((d-2)\)-dimensional faces traversed along this path correspond to the desired sequence of triangles.

Suppose \(\mathcal{T}\neq\emptyset\). By the previous two paragraphs, \(\mathcal{T}(a)\) is non-empty for all \(a\in \mathop{\mathrm{ext}}M\) and \(\mathcal{T}\) is strongly connected. smilansky1987decomposability? implies that \(M\) is indecomposable.⁴⁸ Lastly suppose \(\mathcal{T}=\emptyset\). Then necessarily \(|\mathop{\mathrm{ext}}M|\le 2\), in which case \(M\) is indecomposable. ◻

Proof. Fix any \(V\in \underline{\mathop{\mathrm{und}}}\mathcal{V}\). We show the claim by constructing a convergent sequence of points in \(\mathcal{V}\) that are convex combinations of points in \(\exp_+\mathcal{V}\) with limit \(V\).

For \(\varepsilon\geq 0\), let \[F_\varepsilon=\{f\in L^\infty(\Theta)\mid \varepsilon \leq f \leq 1\}.\] Up to renormalization, these functions are essentially bounded probability densities that are uniformly bounded away from zero. By the Banach-Alaoglu theorem, \(F_\varepsilon\) is weak*-compact because it is a weak*-closed subset of the dual unit ball.

Recall that \(V\in \underline{\mathop{\mathrm{und}}}\mathcal{V}\), that is, \(V\) is strictly suboptimal for every density \(f\in L^\infty(\Theta)\) that is uniformly bounded away from 0. Thus, for every \(f\in F_\varepsilon\), there exists \(V_f\in \mathcal{V}\) such that \(\langle V_f, f \rangle>\langle V, f \rangle.\) By the continuity of the evaluation (aliprantis2007infinite?), for every \(f\in F_\varepsilon\), there exists a weak*-open neighborhood \(O_f\) of \(f\) such that for all \(f'\in O_f\), \(\langle V_f, f' \rangle>\langle V, f' \rangle.\) Thus, \(\{O_f:\: f\in F_\varepsilon\}\) is a weak*-open cover of \(F_\varepsilon\). The functionals \(f\in F_\varepsilon\) that expose a point in \(\mathcal{V}\) are norm-dense in \(F_\varepsilon\) (see lau1976strongly? and note that \(F_\varepsilon\) has non-empty interior in \(L^\infty(\Theta)\)).

By compactness, we may then select a finite subcover \(\{O_m:\:m=1,\ldots,M\}\) such that, for every \(m=1,\ldots,M\), there exists \(f'\in O_m\) such that \(V_m:=V_{f'}\in\exp_+ \mathcal{V}\). Let \[G=\left\{\left(\langle V_1-V, f \rangle,\ldots,\langle V_m-V, f \rangle\right)\mid f\in F_\varepsilon\right\}\subset\mathbb{R}^M.\] The set \(G\) is compact and convex (because it is the image of the weak*-compact convex set \(F_\varepsilon\) under a weak*-continuous linear map). Moreover, by construction of the open cover \(\{O_m\}\), \(G\cap \mathbb{R}^M_{-}=\emptyset\), where \(\mathbb{R}^M_{-}\) the negative orthant. By the Separating Hyperplane theorem, there exists a vector \(\alpha\in \mathbb{R}^M_+\setminus\{0\}\), such that \(\alpha \cdot y> 0\) for all \(y\in G\). Renormalize \(\sum_{i=1}^M \alpha_i=1\).

Define \(\tilde{V}_\varepsilon=\sum_{i=1}^M \alpha_iV_i\in \mathcal{V}.\) For all \(f\in F_\varepsilon\), \[\langle \tilde{V}_\varepsilon, f \rangle-\langle V, f \rangle=\alpha\cdot \left(\langle V_1-V, f \rangle,\ldots,\langle V_m-V, f \rangle\right)>0.\]

Now consider a sequence \(\varepsilon_n\to 0\) and the corresponding sequence of \(\tilde{V}_{\varepsilon_n}\) constructed above. Since \(\mathcal{V}\) is norm-compact, a subsequence of \((\tilde{V}_{\varepsilon_n})\) converges to some \(\tilde{V}\in \mathcal{V}\). We show \(\tilde{V}=V\), which proves the lemma. Recall that \(V\) is undominated and suppose \(\tilde{V}\neq V\). Then there exists a set \(\tilde{\Theta}\subset\Theta\) of non-zero Lebesgue measure such that \(V(\theta)>\tilde{V}(\theta)\) for all \(\theta\in\tilde{\Theta}\). Thus, any density \(f\) concentrated on \(\tilde{\Theta}\) is such that \(\langle V, f \rangle>\langle \tilde{V}, f \rangle.\) By norm-norm continuity of the evaluation, there exists a strictly positive density \(f'\) and some \(\tilde{V}_{\varepsilon_n}\) for \(n\) large enough such that \(\langle V, f \rangle>\langle \tilde{V}_{\varepsilon_n}, f' \rangle,\) a contradiction. ◻

Proof of 7. Similar to the proof for 14. Begin by assuming that \(V\) is undominated but strictly suboptimal for all probability densities \(f\in L^\infty(\Theta)\). Then, repeat the previous construction with \(\varepsilon=0\) to obtain \(\tilde{V}\in\mathcal{V}\) such that \(\langle \tilde{V}-V, f \rangle>0\) for all probability densities \(f\in L^\infty(\Theta)\). This implies \(\tilde{V}>V\) a.e., a contradiction. ◻

Proof. Suppose not, that is, \(V\in \mathop{\mathrm{und}}\mathcal{V}\setminus \mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})\). By 14, \(V\notin \underline{\mathop{\mathrm{und}}}\mathcal{V}\), that is, \(V\) is optimal for some probability density \(f^*\in L^\infty(\Theta)\) that is uniformly bounded away from 0. Since \(\mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})\) is a closed subset of the norm-compact convex set \(\mathcal{V}\), it is norm-compact. By the Hahn-Banach Separation theorem, there exists \(f\in L^\infty(\Theta)\) such that \[\langle V, f \rangle>\max_{V'\in \mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})} \langle V', f \rangle.\] Then \(\tilde{f}=\varepsilon f +(1-\varepsilon) f^*\) (renormalized so that \(\int \tilde{f}=1\)) is a probability density for all sufficiently small \(\varepsilon\in (0,1)\) since \(f^*\) is uniformly bounded away from 0. Moreover, \(\langle V, \tilde{f} \rangle>\max_{V'\in \mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})} \langle V', \tilde{f} \rangle\) by norm-norm continuity of the evaluation and Berge’s maximum theorem (for the right-hand side). By the result due to lau1976strongly? used in 14, there is another density \(\hat{f}\) arbitrarily close to \(\tilde{f}\) in \(L^\infty(\Theta)\) and therefore also uniformly bounded away from \(\varepsilon\) that exposes a point \(\hat{V}\in \mathcal{V}\). Again by continuity and Berge’s maximum theorem, \(\langle V, \hat{f} \rangle>\max_{V'\in \mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})} \langle V', \hat{f} \rangle.\) By definition, \(\langle \hat{V}, \hat{f} \rangle>\langle V, \hat{f} \rangle\). Thus, the point \(\hat{V}\) exposed by \(\hat{f}\) cannot be in \(\exp_+ \mathcal{V}\), a contradiction. ◻

Proof of 8. The claim is a consequence of Milman’s converse to the Krein-Milman theorem (see, e.g., klee1957extremal?, Theorem 1.1). The theorem implies that \(\mathop{\mathrm{ext}}\mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})\subseteq \mathop{\mathrm{cl}}\exp_+\mathcal{V}\) since \(\mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})\) is compact and convex. In particular, by 15, every undominated extreme point of \(\mathcal{V}\) must be in \(\mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})\). But since \(\mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})\) is a convex subset of \(\mathcal{V}\), every undominated extreme point of \(\mathcal{V}\) must also be in \(\mathop{\mathrm{ext}}\mathop{\mathrm{\mathop{\mathrm{cl}}\mathop{\mathrm{conv}}}}(\exp_+\mathcal{V})\) and therefore arbitrarily close to a point in \(\exp_+\mathcal{V}\). ◻