---
abstract: |
    In the design of incentive compatible mechanisms, a common approach is to enforce incentive compatibility as constraints in programs that optimize over feasible mechanisms. Such constraints are often imposed on sparsified representations of the type spaces, such as their discretizations or samples, in order for the program to be manageable. In this work, we explore limitations of this approach, by studying whether all dominant strategy incentive compatible mechanisms on a set $T$ of discrete types can be extended to the convex hull of $T$.

    Dobzinski, Fu and Kleinberg (2015) answered the question affirmatively for all settings where types are single dimensional. It is not difficult to show that the same holds when the set of feasible outcomes is downward closed. In this work we show that the question has a negative answer for certain non-downward-closed settings with multi-dimensional types. This result should call for caution in the use of the said approach to enforcing incentive compatibility beyond single-dimensional preferences and downward closed feasible outcomes.
author:
- 'Submission Number: 9394'
- |
    Taylor Lundy and Hu Fu\
    University of British Columbia\
    tlundy@cs.ubc.ca, hufu@cs.ubc.ca\
bibliography:
- 'ref.bib'
date: May 2019
title: Limitations of Incentive Compatibility on Discrete Type Spaces
---

Introduction {#sec:intro}
============

Mechanism design studies optimization problems with private inputs from strategic agents. An agent’s input, known as her *type*, is her private information including her valuation for the social outcomes, which are to be decided upon by the mechanism. A mechanism needs to solicit such information to achieve certain goals, e.g. maximizing welfare, revenue, surplus or fairness measures. It needs to provide its participants with correct incentives, via both social outcomes and payments, so that the agents find it in their best interests to reveal their types.

Dominant strategy incentive compatibility (DSIC) is one of the strongest and most widely used solution concepts that guarantee such incentives. Under DSIC, every participant, no matter what type she possesses and no matter what types the other participants report to the mechanism, will maximize her utility by revealing her true type. Not only is this a strong guarantee for the mechanism designer that true information should be reported and optimized over, it also alleviates the burden of strategizing from the participating agents — telling truth is a dominant strategy regardless of the other agents’ types or strategies. Partly thanks to this strong incentive guarantee, the two fundamental auctions, namely, the VCG auction that maximizes social welfare [@Vic61; @Clarke71; @Groves73], and Myerson’s auction that maximizes expected revenue for selling a single item [@Myerson81], have been foundational in both the theory and practice of mechanism design.

As the scope of mechanism design expands beyond the classical settings, incentive compatible mechanisms that are optimal for various objective often lack the simple structures that characterize the VCG and Myerson’s mechanisms. By and large, there have been two approaches to the design of incentive compatible mechanisms. The first approach focuses on classes of mechanisms that, by their simple structures, have obvious incentive guarantees. For example, in a multi-item auction, a sequential pricing mechanism puts prices on items and asks each agent in turn to choose her favorite items that remain; the bidders are not asked about their values, and choosing utility-maximizing items (according to their true values) is the obvious strategy to adopt (see, e.g., [@CHMS10]; [@CMS10]; [@FGL15]). Another example is to optimize over parameterized “VCG-like” mechanisms which inherit incentive properties from the VCG mechanism (e.g. [@sandholm2015automated]). This approach is often used to search for mechanisms whose performance is a factor away from being optimal, since the optimal mechanism or its very close approximations are often not within the class of mechanisms being searched over.

The second approach forgoes structures that are easily interpretable, and exhaustively searches for the optimal mechanism. This is exemplified by solving mathematical programs (typically linear or convex programs) whose feasible regions contain the set of all incentive compatible mechanisms (see, e.g. [@conitzer2002complexity]; [@DFK15]; [@DDT17];[@FH18]). Typically, incentive requirements are hardwired as constraints in such programs.

Difficulty arises in the second approach when one would like to adopt strong incentive guarantees such as DSIC, which need at least one constraint per profile of types to specify. When the space of possible types is a continuum, this gives rise to uncountably many constraints. While this does not always make the program impossible to solve it considerably complicates the task. One way to work around this is to discretize the type space and only impose incentive compatible (IC) constraints on the set of discrete types used to represent the type space. Discretization is also embodied in the idea of a given prior distribution over a set of discrete types, on which the optimization can then be based (e.g. [@conitzer2002complexity]; [@DFK15]). The most common motivation for such prior distributions is that they naturally result from samples (e.g. from past observations or market research) from an underlying distribution, whereas the true distribution may be supported on a continuum of types. This approach motivates the question we study in this work.

#### Questions we study.

In this work we aim to answer the question: when one has a mechanism that is DSIC on a discretized subset of a type space, can one always find a mechanism that has the same behavior on the subset and yet is DSIC on the whole type space? To make the question more concrete, we study the natural case where the whole type space is the convex hull of the discrete subset. To make the presentation easier, in the following we denote by $\typespaces$ the discrete subset of types, and $\operatorname{Conv}(\typespaces)$ its convex hull.

We consider the question a fundamental one for the second approach to mechanism design that we described above. When one optimizes for a mechanism with IC constraints imposed only on $\typespaces$, if the resulting mechanism cannot be *extended* to the original type space, it loses incentive guarantees when put to use.

One objection may be that, given a mechanism that is DSIC on $\typespaces$, one may always run it on $\operatorname{Conv}(\typespaces)$, by restricting the “bidding language”, so that a type in $\operatorname{Conv}(\typespaces)$ but not in $\typespaces$ has to report a type in $\typespaces$. Such mechanisms, however, may lose the incentive guarantee which makes DSIC mechanisms attractive in the first place. Unless one can show that agents with types not in $\typespaces$ have a dominant strategy in such mechanisms, such agents need to strategize over which types in $\typespaces$ to report, depending on the types and strategies of their opponents. In the scenario where $\typespaces$ is a set of samples from a continuous distribution, the vast majority of types may not be in $\typespaces$ and have no incentive guarantee, which is clearly undesirable. In settings where the agents’ types are single dimensional, @DFK15 showed that “restricting the bidding language” does turn any mechanism DSIC on $\typespaces$ into a mechanism DSIC on any superset of $\typespaces$: each type in the superset has a dominant strategy, and by the revelation principle this gives rise to a DSIC mechanism that extends the given mechanism’s behavior on $\typespaces$. To the best of our knowledge, no such guarantees are known beyond single dimensional settings.

#### Our Results.

For agents with multi-dimensional types, we first give a condition under which any DSIC mechanism on $\typespaces$ can be extended to a DSIC mechanism on $\operatorname{Conv}(\typespaces)$, via an argument that is different from @DFK15’s yet still straightforward (Theorem \[thm:swap\]). In particular, the condition is satisfied whenever the set of feasible outcomes is *downward closed* (Theorem \[thm:downward\]).

Our main result, however, is a construction of a set $\typespaces$ of multi-dimensional types and a DSIC mechanism on it, for which we show that no DSIC mechanism on $\operatorname{Conv}(\typespaces)$ can output the same social outcomes on types in $\typespaces$. The impossibility result stands even if the extension mechanism is allowed to be randomized. This shows that, without conditions such as single-dimensional types or downward closed set of feasible outcomes, designing incentive compatible mechanisms by focusing on a discrete subset of types can be a questionable approach to designing mechanisms for the whole type space — there may not be any mechanism DSIC on the whole type space which behave the same way on the subset.

Near the end, we give a multi-dimensional setting where the expected *revenue* of a mechanism with only correct incentives for a set $\typespace$ of types can be unboundedly more than the revenue of a mechanism for $\operatorname{Conv}(\typespace)$. This example is much less involved than our main result, because revenue optimal mechanisms are meaningful only when they do not overcharge any reported type and guarantee non-negative utility. This constraint can be much more stringent when imposed for all types in $\operatorname{Conv}(\typespace)$ than for $\typespace$ only.

Related Works {#sec:related}
-------------

For multi-dimensional preferences, an allocation rule for any fixed agent is implementable if and only if it satisfies the so-called *cyclic monotonicity* property [@Rochet87]. When the type space is convex, it turns out the weaker condition of *weak monotonicity* suffices for implementability [@SY05; @AK14]. It is notable that the two solution concepts we compare in Section \[sec:mapping\] precisely correspond to the case where the type space is convex and that where it is not. However, nowhere in our arguments do we make use of this beautiful fact.

Another closely related body of work, is the literature on automated mechanism design. In automated mechanism design, mechanisms are optimized for the setting and objective automatically using information about agents’ type distributions. When this work was introduced by @conitzer2002complexity the input for this problem was an explicit description of the agents distributions, however recent work has moved towards replacing this explicit description with samples from the agents type distribution [@likhodedov2004methods; @likhodedov2005approximating; @sandholm2015automated]. Our work highlights how interpolating between discrete samples can effect not only the objective but the implementablility of the mechanism itself. Luckily, the research on sample based automated mechanism design is able to avoid the pitfalls of only having discrete samples. They do this either by optimizing over parameterized families of mechanisms which are guaranteed to be implementable on the entire typespace or by working in settings where the addition of new types has no effect on the objective (i.e. downward closed settings, see )[@sandholm2015automated; @guo2010computationally; @balcan2018; @morgenstern2016learning]. However, our work points out some difficulties that might arise if one wishes to take a more general, non-parameterized approach to automated mechanism design in settings which are not downward closed.

There are a variety of well-studied settings that are not downward closed in which extending a type space to its the convex hull could cause problems. One commonly studied not downward closed setting arises from the job scheduling problem introduced in @nisan2001algorithmic and later built upon by @schedule2 and @ashlagi2012optimal. since in this problem every job must eventually be scheduled and the set of feasible solutions is not downward closed. Another example of a non-downward closed setting is one-sided matching markets in which every agent must be matched with exactly one good. An example of a one-sided matching market is the fair housing allocation studied by @matchmarket. Finally, the facility location problem from @devanur2005strategyproof also not downward closed.

Preliminaries {#sec:prelim}
=============

We consider a setting with $N$ agents where each agent $i$ has a private type $\typei$ from her type space $\typespacei \subseteq \mathbb R_+^m$. The type profile $\types = (\typei[1], \ldots, \typei[N])$ denotes the vector of all agents’ types, from the joint type space $\typespaces \coloneqq \prod_i \typespacei$.

We adopt the standard shorthand notation to write $\typesmi \coloneqq (\type_{1}, \ldots, \type_{i-1}, \type_{i+1}, \ldots, \type_{n})$ from $\typespacesmi \coloneqq \prod_{j \neq i} \typespace_{j}$.

An outcome (or, interchangeably, allocation) for agent $i$ lies in $\mathbb R_+^m$; for an outcome $\alloci$, the agent with type $\typei$ has value $\langle \typei, \alloci \rangle = \sum_{j = 1}^m \type_{ij} \alloc_{ij}$. A social outcome is denoted by a vector $(\alloci[1], \ldots, \alloci[N]) \in \mathbb R_+^{mN}$. The set of all feasible social outcomes (or allocations) is denoted ${\mathscr{F}}\subseteq \mathbb R_+^{mN}$.

For example, in a single-item auction, $m = 1$, each $\typei \in \mathbb R_+$ represents agent $i$’s value for the item, and ${\mathscr{F}}\subseteq \mathbb R_+^N$ is the all zero vector (representing not selling) and the $N$ standard bases (each representing selling to a corresponding agent). As another example, in a $m$-unit auction with unit-demand buyers, ${\mathscr{F}}\subseteq \mathbb R_+^{N}$ is the set of all integral points in $\{(\alloci[1], \ldots, \alloci[N]) \in \mathbb R_+^{mN} \mid \sum_{i = 1}^N \alloci[ij] \leq 1, j = 1, 2, \ldots, m\}$.

#### Mechanisms.

A (direct revelation) mechanism consists of an *allocation rule* $\allocs: \typespaces \to {\mathscr{F}}$ and a *payment rule* $\pays: \typespaces \to \mathbb R_+^N$. The mechanism elicits type reports from the agents, and on reported type profile $\types$, decides on an allocation $\allocs(\types) \in {\mathscr{F}}$, with each agent $i$ making a payment of $\payi(\types)$. In general, allocation rules can be randomized, in which case $\allocs(\types)$ is a randomized variable supported on ${\mathscr{F}}$. $\allocs(\cdot)$ induces allocation rule $\alloci(\cdot)$ for each agent $i$: for all $\types$, $\alloci(\types) \in \mathbb R_+^m$ is the vector consisting of the $[(i-1)m + 1]$-st to the $im$-th coordinates in $\allocs(\types)$. When $\allocs(\types)$ is a random variable, so are $\alloci(\types)$’s.

When $\allocs(\types)$ is deterministic, we write $\allocs(\types) = \mathbf{y} \in {\mathscr{F}}$ as a shorthand for ${\operatorname{\mathbf{Pr}}_{}{{\mathchoice{ \left [ \allocs(\types) = \mathbf y  \right ]}{[ \allocs(\types) = \mathbf y ]}{[ \allocs(\types) = \mathbf y ]}{[ \allocs(\types) = \mathbf y ]} }}} = 1$.

Agents have quasi-linear utilities, that is, when reporting type $\typei'$, agent $i$’s utility is ${\operatorname{\mathbf E}_{}{{\mathchoice{ \left [ \langle \typei, \alloci(\typei', \typesmi) \rangle   \right ]}{[ \langle \typei, \alloci(\typei', \typesmi) \rangle  ]}{[ \langle \typei, \alloci(\typei', \typesmi) \rangle  ]}{[ \langle \typei, \alloci(\typei', \typesmi) \rangle  ]} }}} - \payi(\typei', \typesmi)$ (where the expectation is taken over the randomness in $\allocs(\types)$.

A mechanism is *dominant strategy incentive compatible* (DSIC) if, for all $\types \in \typespaces$, and for all $\typei' \in \typespacei$, ${\operatorname{\mathbf E}_{}{{\mathchoice{ \left [ \langle \typei, \alloc_{i}(\typei, \typesmi) \rangle  \right ]}{[ \langle \typei, \alloc_{i}(\typei, \typesmi) \rangle ]}{[ \langle \typei, \alloc_{i}(\typei, \typesmi) \rangle ]}{[ \langle \typei, \alloc_{i}(\typei, \typesmi) \rangle ]} }}} - \payi(\typei, \typesmi) \geq {\operatorname{\mathbf E}_{}{{\mathchoice{ \left [ \langle \typei,  \alloc_{i}(\typei', \typesmi) \rangle  \right ]}{[ \langle \typei,  \alloc_{i}(\typei', \typesmi) \rangle ]}{[ \langle \typei,  \alloc_{i}(\typei', \typesmi) \rangle ]}{[ \langle \typei,  \alloc_{i}(\typei', \typesmi) \rangle ]} }}} - \payi(\typei', \typesmi)$. An allocation rule $\allocs$ is said to be DSIC implementable or simply DSIC if there is a payment rule $\pays$ such that $(\allocs, \pays)$ is a DSIC mechanism. In this case, we say $\allocs$ is implemented by payment rule $\pays$.

#### Extensions.

Given a subset $S \subseteq \mathbb R^n$, we denote by $\operatorname{Conv}(S)$ the convex hull of $S$.

\[def:extension\] An allocation rule $\extallocs: \operatorname{Conv}(\typespaces) \to {\mathscr{F}}$ is an *extension* of an allocation rule $\allocs: \typespaces \to {\mathscr{F}}$ if for all $\types \in \typespaces$, $\extallocs(\types)$ has the same distribution as $\allocs(\types)$. Similarly, a payment rule $\extpays: \operatorname{Conv}(\typespaces) \to \mathbb R_+^N$ is an extension of payment rule $\pays: \typespaces \to \mathbb R_+^N$ if for all $\types \in \typespaces$, $\extpays(\types) = \pays(\types)$.

In Definition \[def:extension\], if $\allocs(\cdot)$ is deterministic, then $\extallocs(\cdot)$ being an extension simply means $\extallocs(\types) = \allocs(\types)$ for all $\types \in \typespaces$.

#### Downward closed settings.

The feasible allocation set ${\mathscr{F}}$ is *downward closed* if $\mathbf y \in {\mathscr{F}}$ entails $\allocs \in {\mathscr{F}}$ for all $\allocs \preceq \mathbf y$, where $\allocs \preceq \mathbf y$ denotes $\alloci[j] \leq y_j$ for $j = 1, \cdots, mN$.

#### Weak monotonicity.

A well-known necessary condition for an allocation rule to be DSIC implementable is weak monotonicity:

An allocation rule $\allocs: \typespaces \to {\mathscr{F}}$ is *weakly monotone* if for each agent $i$, any $\typei, \typei' \in \typespacei$ and $\typesmi \in \typespacesmi$, $$\begin{aligned}
        {\operatorname{\mathbf E}_{}{{\mathchoice{ \left [ \langle \typei - \typei', \alloci(\typei,\typesmi)  - \alloci(\typei', \typesmi) \rangle   \right ]}{[ \langle \typei - \typei', \alloci(\typei,\typesmi)  - \alloci(\typei', \typesmi) \rangle  ]}{[ \langle \typei - \typei', \alloci(\typei,\typesmi)  - \alloci(\typei', \typesmi) \rangle  ]}{[ \langle \typei - \typei', \alloci(\typei,\typesmi)  - \alloci(\typei', \typesmi) \rangle  ]} }}} \geq 0. 
    \end{aligned}$$

An allocation rule is implementable only if it is weakly monotone.

In fact, @SY05 showed that, if $\typespaces$ is convex, then weak monotonicity is also a sufficient condition for DSIC implementability.

#### Revenue.

A mechanism $(\allocs, \pays)$ is ex post *individually rational* (IR) if for each agent $i$ and for every $\types \in \typespaces$, $\langle \typei, \alloc_{i}(\types) \rangle - \payi(\types) \geq 0$.

Given a distribution $D$ on $\typespaces$ and a mechanism $(\allocs, \pays)$ that is DSIC and ex post IR, the *expected revenue* of the mechanism is ${\operatorname{\mathbf E}_{\types \sim D}{{\mathchoice{ \left [ \sum_i \payi(\types)  \right ]}{[ \sum_i \payi(\types) ]}{[ \sum_i \payi(\types) ]}{[ \sum_i \payi(\types) ]} }}}$. The *optimal* revenue is the maximum expected revenue achievable among all DSIC, ex post IR mechanisms.

DSIC Convex Extensions {#sec:map}
======================

\[sec:mapping\] Before presenting our main result on the impossibility to extend DSIC allocation rules, we first complement @DFK15’s result in single-dimensional setting with a simple observation in multi-dimensional preference settings: whenever the feasible allocation space is downward closed, any DSIC allocation rule on a type space can be extended to its convex hull by another DSIC allocation rule.

\[thm:downward\] If the set of feasible allocations ${\mathscr{F}}$ is downward closed, for any DSIC allocation rule $\allocs$ on a type space $\typespaces$, there is a DSIC extension $\extallocs$ of $\allocs$ on $\operatorname{Conv}(\typespaces)$. If $\allocs$ is implemented with a payment rule $\pays$, $\extallocs$ can be implemented by an extension $\extpays$ of $\pays$. If $\pays$ is individually rational on $\typespaces$, so is $\extpays$ on $\operatorname{Conv}(\typespaces)$.

If we do not require the statement about individual rationality, extensibility is guaranteed by an even weaker condition, which we call *single swap feasible*.

A feasible allocation set ${\mathscr{F}}$ is *single swap feasible* (SSF) if for every agent $i$ there exists an allocation ${\boldsymbol{x}^{\mathrm{ssf}}}(i) \in {\mathscr{F}}$ such that for any $\allocs' \in {\mathscr{F}}$, $(\alloci',{\boldsymbol{x}^{\mathrm{ssf}}}_{-i}(i)) \in {\mathscr{F}}$.

Intuitively, ${\boldsymbol{x}^{\mathrm{ssf}}}(i)$ is a feasible allocation vector such that if we replace the $i^{\text{th}}$ element of this vector with the $i^{\text{th}}$ element from any other feasible allocation the resulting allocation is still feasible. If ${\mathscr{F}}$ is a product space or is downward closed, it must be SSF. [^1]

\[thm:swap\] If the set of feasible allocations ${\mathscr{F}}$ is SSF, any DSIC allocation rule $\allocs$ on a type space $\typespaces$, there is a DSIC extension $\extallocs$ of $\allocs$ on $\operatorname{Conv}(\typespaces)$.

The proofs for both and can be found in the supplementary materials. The main result of this paper is that without this condition a DSIC extension may not exist.

\[thm:rand\] There is a two agent type space $\randtypespaces$ with a DSIC allocation rule $\randallocs$, such that $\randallocs$ cannot be extended by a DSIC allocation rule to $\operatorname{Conv}(\randtypespaces)$.

We prove the theorem in two steps. We first present a setting with three-dimensional preferences for which we show the non-existence of *deterministic* extensions. We then build on the construction, lifting it to a higher dimension, where we strengthen the argument and show the non-existence of extensions that even allow randomization.

Non-existence of deterministic extensions
-----------------------------------------

We first present type space $\dettypespaces = \dettypespacei[1] \times \dettypespacei[2]$ and the allocation rule $\detallocs$, and then show that $\detallocs$ is DSIC and yet cannot be extended by any deterministic DSIC allocation rule on $\operatorname{Conv}(\dettypespaces)$.

The two agents have identical type spaces: for $i = 1, 2$, $\dettypespacei = \dettypespace \coloneqq \{A = [1, 0, 0], B = [0, 1, 0], C = [0, 0, 1], D = [\tfrac 1 3, \tfrac 1 3, \tfrac 1 3]\}$. A visual representation of this typespace and its convex hull can be found in figure 1 in the supplementary materials.

The allocation rule $\detallocs$ is also symmetric, in the sense that $\detalloci[1](\typei[1], \typei[2]) = \detalloci[2](\typei[2], \typei[1])$ for any $\typei[1], \typei[2] \in \dettypespace$. We summarize $\detalloci[1]$ with the diagram below. The rows are indexed by agent $1$’s own type $V_1$, and the columns by agent $2$’s type $V_2$: $$\begin{aligned}
\begin{blockarray}{c cccc}
 & A & B & C & D \\
\begin{block}{c(cccc)}
A & [1,1,0] & [2,0,2] & [3,0,3] & [4,0,4] \\ 
B & [0,1,1] & [2,2,0] & [3,3,0] & [4,4,0] \\ 
C & [1,0,1] & [0,2,2] & [0,3,3] & [0,4,4] \\ 
D & [0,1,1] & [2,2,0] & [3,3,0] & [4,4,0]  \\
\end{block}
\end{blockarray} \end{aligned}$$

The set of all feasible allocations is then ${\mathscr{F}}= \{(\detalloci[1](V_1, V_2), \detalloci[2](V_1, V_2) )\}_{V_1, V_2 \in \dettypespace}$. We hasten to point out that ${\mathscr{F}}$ is *not* the product between the two agents’ respective set of feasible allocations. For example, $[1, 1, 0, 1, 1, 0]$ is in ${\mathscr{F}}$ as it is $\detallocs(A, A)$, but $[1, 1, 0, 0, 1, 1]$ is not. This is important for the proof.

$\detallocs$ is DSIC implementable.

Let the payment be 0 for both agents and all type profiles. As the allocation and payment rules are both symmetric, consider either agent $i$. If $\typei[-i] = A$, the maximum value agent $i$ could get, when her type is $A$, $B$, or $C$, is 1, attained with truthful bidding. For $\typei = D$, the four allocations all give the same value $\tfrac 2 3$. Similar arguments hold when $\typei[-i]$ is $B$, $C$ or $D$.

\[thm:det\] There exists no deterministic DSIC extension of $\detallocs$.

Before proving Theorem \[thm:det\], we make several preparatory observations.

A key difficulty with multi-dimensional preferences is the the lack of a payment identity à la Myerson [@Myerson81]. In order to argue that any extension of an allocation rule is not DSIC, one has to either check the many cyclic (or weak) monotonicity conditions, or show that no payment rule can support the extension in a DSIC mechanism. We designed $\dettypespaces$ and $\detallocs$ carefully so that the allocations “lock” the payment rules.

\[lem:equal-pay\] For any allocation rule $\extallocs$ that is an extension of $\detallocs$, if $\extallocs$ can be implemented by a DSIC mechanism with payment rule $\pays$, then for any $V \in \{A, B, C, D\}$, $\payi[1](A, V) = \payi[1](B, V) = \payi[1](C, V) = \payi[1](D, V)$, and $\payi[2](V, A) = \payi[2](V, B) = \payi[2](V, C) = \payi[2](V, D)$.

We prove the lemma for agent $1$, and the statement for agent $2$ follows by symmetry.

By DSIC, for any $V \in \dettypespace$, we have $$\begin{aligned}
    \langle A , \detalloci[1](A,V)\rangle & -\payi[1](A,V)  \\
     & \geq  \langle A , \detalloci[1](C,V)\rangle -\payi[1](C,V); \\
    \langle B , \detalloci[1](B,V)\rangle & -\payi[1](B,V) \\
    & \geq \langle B , \detalloci[1](A,V)\rangle -\payi[1](A,V);
     \\
     \langle C, \detalloci[1](C,V)\rangle & -\payi[1](C,V) \\
     & \geq \langle C , \detalloci[1](B,V)\rangle -\payi[1](B,V).\end{aligned}$$ Note that $$\begin{aligned}
    \langle A , \detalloci[1](A,V)\rangle = \langle A , \detalloci[1](C,V)\rangle; \\
    \langle C , \detalloci[1](C,V)\rangle = \langle C , \detalloci[1](B,V)\rangle; \\
    \langle B , \detalloci[1](B,V)\rangle = \langle B , \detalloci[1](A,V)\rangle.
    \end{aligned}$$ Therefore $\payi[1](A,V) \leq  \payi[1](C,V) \leq \payi[1](B, V) \leq \payi[1](A, V)$. Hence all inequalities are tight and we have $\payi[1](C,V) = \payi[1](A,V) =  \payi[1](B,V)$.

For type $D$’s payment, note that $\detalloci[1](B, V)= \detalloci[1](D, V)$. If $\payi[1](B, V) \neq \payi[1](D, V)$, one of $B$ and $D$ must be incentivized to misreport the other type. Therefore $\payi[1](B, V) = \payi[1](D, V)$.

In figure 2 in the supplementary materials we give a $3$ dimensional visualization of the agent’s value for each allocation which gives intuition into the proof of \[lem:equal-pay\].

\[lem:fixed-menu\] If $\tilde{x}$ is a deterministic DSIC extension of $\detallocs$, then for $\typei[1] = $ $\frac{1}{3}A + \frac{1}{3}B + \frac{1}{3}D$, and any $V_2 \in \dettypespace$, $\extalloci[1](\typei[1], V_2) \in $ $\{\extalloci[1](A, V_2), \extalloci[1](B, V_2),$ $\extalloci[1](C, V_2),$ $ \extalloci[1](D, V_2)\}$.

For the sake of contradiction, assume $\extallocs$ is a DSIC extension of $\detallocs$, implementable by payment rule $\pays$, and for $\typei[1]$ and $V_2 \in \dettypespace$, $\extalloci[1](\typei[1], V_2) = \detalloci[1](V_1, V_2')$ for some $(V_1, V_2') \in \dettypespaces$ and $V_2' \neq V_2$.

For any $V_2$, one of $\detalloci[1](A, V_2)$ and $\detalloci[1](B, V_2)$ gives an equal positive value to both $A$ and $B$. Let $V_1^*$ be the type that induces this equally valued allocation. (For example, if $V_2 = B$, then $\detalloci[1](A, B) = [2, 0, 2]$ and $\detalloci[1](B, B) = [2, 2, 0]$. Both $A$ and $B$ have the same value for $\detalloci[1](B, B)$ and so type $B$ would be $V_1^*$.)

Observe that, for the allocation $\detalloci[1](V_1, V_2')$, $V_1$ has positive value $\langle V_1, \detalloci[1](V_1, V_2') \rangle$, and no other type has higher value for it. Therefore, type $\typei[1]$ has value at most $\langle \frac{2}{3} V_1 + \frac{1}{3} D, \detalloci[1](V_1, V_2') \rangle$ for the allocation. In order for $\typei[1]$ to have no incentive to misreport $V_1^*$, we must have $$\begin{gathered}
\langle \frac{2}{3} V_1 + \frac{1}{3} D, \detalloci[1](V_1, V_2') \rangle - \payi[1](\typei[1], V_2) 
\\ 
\geq \langle \frac{2}{3} V_1^* + \frac{1}{3} D, \detalloci[1](V_1^*, V_2) \rangle - \payi[1](V_1^*, V_2) 
\label{eq:t1-V1}\end{gathered}$$

On the other hand, in order for type $V_1$ not to have incentive for deviating to $\typei[1]$, we have $$\begin{gathered}
    \langle V_1, \detalloci[1](V_1, V_2) \rangle - \payi[1](V_1, V_2) 
    \\
    = \langle V_1^*, \detalloci[1](V_1^*, V_2) \rangle - \payi[1](V_1^*, V_2) 
    \\
    \geq \langle V_1, \detalloci[1](V_1, V_2') \rangle - \payi[1](\typei[1], V_2);
    \label{eq:V1-t1}
    \end{gathered}$$ where for the equality we used the fact that the value obtained by reporting truthfully is the same for every type in $\{A, B, C\}$ given a fixed type of the opponent, and that $\payi[1](V_1, V_2) = \payi[1](V_1^{*}, V_2)$ by Lemma \[lem:equal-pay\].

Similarly, in order for type $D$ not to have incentive for deviating to $\typei[1]$, we have $$\begin{gathered}
    \langle D, \detalloci[1](D, V_2) \rangle - \payi[1](D, V_2) 
    \\
    = \langle D, \detalloci[1](V_1^*, V_2) \rangle - \payi[1](V_1^*, V_2) 
    \\
    \geq \langle D, \detalloci[1](V_1, V_2') \rangle - \payi[1](\typei[1], V_2),
    \label{eq:D-t1}\end{gathered}$$ where for the equality we used the fact that type $D$ has the same value for all allocations given a fixed type of the opponent, and that $\payi[1](D, V_2) = \payi[1](V_1, V_2)$ by Lemma \[lem:equal-pay\]. Crucially, and  cannot both be tight, because by construction, for any $V_2 \neq V_2'$, $$\begin{gathered}
\langle V_1, \detalloci[1](V_1, V_2) - \detalloci[1](V_1, V_2') \rangle \\
= \frac{3}{2} \langle D, \detalloci[1](D, V_2) - \detalloci[1](V_1, V_2') \rangle \neq 0.  \end{gathered}$$ Therefore, $\frac{2}{3} \cdot$ $+ \frac{1}{3} \cdot$ gives $$\begin{gathered}
\langle \frac{2}{3} V_1^* + \frac{1}{3} D, \detalloci[1](V_1^*, V_2) \rangle - \payi[1](V_1^*, V_2)
\\ 
> \langle \frac{2}{3} V_1 + \frac{1}{3} D, \detalloci[1](V_1, V_2') \rangle - \payi[1](\typei[1], V_2),\end{gathered}$$ which contradicts .

By the same reasoning as for Lemma \[lem:equal-pay\], the following lemma follows from Lemma \[lem:fixed-menu\].

\[lem:general-equal-pay\] If $\extallocs$ is a deterministic DSIC extension of $\detallocs$, implementable by payment rule $\pays$, then for any $\typei[1]$ in the interior of $\operatorname{Conv}(\dettypespace)$ and any $V_2 \in \dettypespace$, $\payi[1](\typei[1], V_2) = \payi[1](A, V_2)$.

We are now ready to prove Theorem \[thm:det\].

Suppose $\extallocs$ is a deterministic DSIC extension of $\detallocs$. We show a contradiction by showing that $\extallocs$ must violate weak monotonicity.

Consider $\typei[1] = \tfrac 1 3 A + \tfrac 1 3 B + \tfrac 1 3 D$ and when agent $2$’s type is $A$. Since $\typei[1]$ could report any type in $\dettypespace$, she has as options $\detalloci[1](A, A), \detalloci[1](B, A), \detalloci[1](C, A)$ and $\detalloci[1](D, A) \}$, all at the same price by Lemma \[lem:general-equal-pay\]. By Lemma \[lem:fixed-menu\], these are also all the allocations she could possibly get.

Since $[1, 1, 0]$ is the only allocation for which both types $A$ and $B$ have positive value, it is $\typei[1]$’s preferred allocation, i.e., $\extalloci[1](\typei[1], A)$ must be $[1, 1, 0]$. This in turn implies $\extalloci[2](\typei[1], A) = [1, 1, 0]$. (Recall that ${\mathscr{F}}$ is not a product space, and the only allocation in which agent $1$ gets $[1, 1, 0]$ is $\detallocs(A, A) = [1, 1, 0, 1, 1, 0]$.)

Similarly, one can show $\extalloci[1](\typei[1], D) = [4, 4, 0]$, which implies $\extalloci[2](\typei[1], D) = [2, 2, 0]$ or $[4, 4, 0]$. But in either case, weak monotonicity is violated for agent $2$’s types $A$ and $D$. For example, if $\extalloci[2](\typei[1], D) = [2, 2, 0]$, we have $$\begin{aligned}
    \langle A, [1, 1, 0] \rangle + \langle D, [2, 2, 0] \rangle < \langle A, [2, 2, 0] \rangle + \langle D, [1, 1, 0] \rangle.\end{aligned}$$ Therefore, no deterministic DSIC extension of $\detallocs$ is possible.

Non-existence of randomized extensions
--------------------------------------

We need a more convoluted construction and a more careful argument to prove the impossibility of extensions that are possibly randomized. We build on $\dettypespaces$ and $\detallocs$ to construct $\randtypespaces$ and $\randallocs$ and prove Theorem \[thm:rand\].

We first raise types in $\dettypespace$ to a space of seven dimensions. Define $A' = [1, 0, 0, 0, 0, 0, 0]$, $B' = [0, 1, 0, 0, 0, 0, 0]$, $C' = [0, 0, 1, 0, 0, 0, 0]$ and $D' = \frac 1 3 (A' + B' + C')$. For ease of notation, we define a mapping $\det: \{A', B', C', D'\} \to \dettypespace$, with $\det(A') = A, \det(B') = B, \det(C') = C$ and $\det(D') = D$. We also introduce four new types, $E' = [0, 0, 0, 1, 0, 0, 0]$, $F'=[0,0,0,0,1,0,0]$, $G'=[0,0,0,0,0,1,0]$ and $H'=[0,0,0,0,0,0,1]$. Define $\randtypespace = \{A', B', C', D', E', F', G'\}$, and $\randtypespaces = \randtypespace \times \randtypespace$.

We now define $\randallocs$, which is again symmetric, in the sense that $\randalloci[1](V_1, V_2) = \randalloci[2](V_2, V_1)$ for every $V_1, V_2 \in \randtypespace$. We therefore only describe $\randalloci[1]$. When both agents report types in $\{A', B', C', D'\}$, the first three coordinates of each agent’s allocation are given by $\detallocs$ when fed by the corresponding types in $\dettypespaces$, and the remaining coordinates are filled in according to the opponent’s report. More specifically, $$\begin{gathered}
\forall V_1 \in \{A',B',C',D'\}, \\
\randalloci[1](V_1, A')=[\detalloci[1](\det(V_1), A), 0, 100, 100,100],\\
\randalloci[1](V_1, B')=[\detalloci[1](\det(V_1), B),100 , 0, 100, 100],\\
\randalloci[1](V_1, C')=[\detalloci[1](\det(V_1), C),100, 100, 0, 100], \\
\randalloci[1](V_1, D')=[\detalloci[1](\det(V_1), D), 100, 100, 100,0]\end{gathered}$$ For the other types, we have $$\begin{gathered}
    \forall V_1 \in \{E', F', G', H'\}, \forall V_2 \in \{A', B', C', D'\}, \\
    \randalloci[1](V_1, V_2) = \randalloci[1](C', V_2).\\
    \forall V_2 \in \{E', F', G', H'\}, \forall V_1 \in \randtypespace, \\
    \randalloci[1](V_1, V_2) = [0, 0, 0, 100, 100, 100, 100].\end{gathered}$$

Note that $\randallocs$ itself is deterministic. The difficulty we need to overcome in this section is that the *extension* of $\randallocs$ may be randomized, and we must show that any extension to $\operatorname{Conv}(\randtypespaces)$ cannot be DSIC.

The set of feasible allocations is ${\mathscr{F}}$ $= $ $\{\randallocs(V_1, V_2)\}_{V_1, V_2 \in \randtypespace}$. Again we emphasize that the set of feasible allocations is *not* a product space.

We first show that a subset of the payments are still “locked” as they were in the deterministic setting.

\[lem:randequal-pay\] For any allocation rule $\extallocs$ that is an extension of $\randallocs$, if $\extallocs$ can be implemented by a DSIC mechanism with payment rule $\pays$, then for any $V \in \{A', B', C', D'\}$ and any $V',V'' \in \randtypespace$, $\payi[1](V', V) = \payi[1](V'', V)$, and $\payi[2](V, V') = \payi[2](V, V'')$.

The proof for types in $\{A',B',C',D'\}$ follows the same steps as . For any type in $\{E',F',G',H'\}$ note that they receive the same allocation as type $C'$ and therefore if they are charged a payment that is different from the payment $C'$ is charged than either $C'$ or that type would be incentivized to deviate.

In order to have a DSIC convex extension in this setting we must satisfy a condition similar to \[lem:fixed-menu\] with the higher dimensional versions of the types from $\dettypespaces$.

If $\extallocs$ is a DSIC extension of $\randallocs$, then for $\typei[1] = \frac{1}{3}A' + \frac{1}{3}B' + \frac{1}{3}D'$, and any $V_2 \in \{A',B',C',D'\}$, $\extalloci[1](\typei[1], V_2)$ is supported on $\{\extalloci[1](A', V_2), \extalloci[1](B', V_2), \extalloci[1](C', V_2), \extalloci[1](D', V_2)\}$.

\[lma:invariant-random\]

For the sake of contradiction, assume $\extallocs$ is a DSIC extension of $\randallocs$, implementable by payment rule $\pays$, and for some $V_2 \in \{A',B',C',D'\}$,

there exist a pair of types $\vertypei[1], \vertypei[2]'$ such that ${\operatorname{\mathbf{Pr}}_{}{{\mathchoice{ \left [ \extallocs(\typei[1], \vertypei[2]) = \randallocs(\vertypei[1], \vertypei[2]')  \right ]}{[ \extallocs(\typei[1], \vertypei[2]) = \randallocs(\vertypei[1], \vertypei[2]') ]}{[ \extallocs(\typei[1], \vertypei[2]) = \randallocs(\vertypei[1], \vertypei[2]') ]}{[ \extallocs(\typei[1], \vertypei[2]) = \randallocs(\vertypei[1], \vertypei[2]') ]} }}} > 0$ for a $\vertypei[2]'\neq\vertypei[2]$. Let ${X_{V_2}}$ denote the set of allocations $\{\extalloci[1](A', V_2), \extalloci[1](B', V_2), \extalloci[1](C', V_2), \extalloci[1](D', V_2)\}$.

Let $\alpha = {\operatorname{\mathbf{Pr}}_{}{{\mathchoice{ \left [ \extalloci[1](\typei[1], \vertypei[2]) \in {X_{V_2}}\right ]}{[ \extalloci[1](\typei[1], \vertypei[2]) \in {X_{V_2}}]}{[ \extalloci[1](\typei[1], \vertypei[2]) \in {X_{V_2}}]}{[ \extalloci[1](\typei[1], \vertypei[2]) \in {X_{V_2}}]} }}}$ and $\beta = {\operatorname{\mathbf{Pr}}_{}{{\mathchoice{ \left [ \extalloci[1](\typei[1], \vertypei[2]) \not \in {X_{V_2}}\right ]}{[ \extalloci[1](\typei[1], \vertypei[2]) \not \in {X_{V_2}}]}{[ \extalloci[1](\typei[1], \vertypei[2]) \not \in {X_{V_2}}]}{[ \extalloci[1](\typei[1], \vertypei[2]) \not \in {X_{V_2}}]} }}}.$ Then by assumption, $\beta > 0$.

Also let $\extalloci[1]^{\alpha}(\typei[1]) = {\operatorname{\mathbf E}_{}{{\mathchoice{ \left [ \extalloci[1](\typei[1],\vertypei[2])  \mid \extalloci[1](\typei[1],\vertypei[2]) \in {X_{V_2}}\right ]}{[ \extalloci[1](\typei[1],\vertypei[2])  \mid \extalloci[1](\typei[1],\vertypei[2]) \in {X_{V_2}}]}{[ \extalloci[1](\typei[1],\vertypei[2])  \mid \extalloci[1](\typei[1],\vertypei[2]) \in {X_{V_2}}]}{[ \extalloci[1](\typei[1],\vertypei[2])  \mid \extalloci[1](\typei[1],\vertypei[2]) \in {X_{V_2}}]} }}}$ and $\extalloci[1]^{\beta}(\typei[1]) = {\operatorname{\mathbf E}_{}{{\mathchoice{ \left [ \extalloci[1](\typei[1],\vertypei[2])  \mid \extalloci[1](\typei[1],\vertypei[2]) \not\in {X_{V_2}}\right ]}{[ \extalloci[1](\typei[1],\vertypei[2])  \mid \extalloci[1](\typei[1],\vertypei[2]) \not\in {X_{V_2}}]}{[ \extalloci[1](\typei[1],\vertypei[2])  \mid \extalloci[1](\typei[1],\vertypei[2]) \not\in {X_{V_2}}]}{[ \extalloci[1](\typei[1],\vertypei[2])  \mid \extalloci[1](\typei[1],\vertypei[2]) \not\in {X_{V_2}}]} }}}$. Then the expected value for agent $1$ truthfully reporting $\typei[1]$ is $\langle \typei[1], \alpha \extalloci[1]^\alpha (\typei[1])+ \beta \extalloci[1]^\beta(\typei[1]) \rangle$.

In order for $\extallocs$ to be DSIC, it must provide type $\typei[1]$ with at least as much utility as it could receive from deviating to any type in $\randtypespace$.

Let $\vertypei[\text{max}] \in \operatorname{argmax}_{\vertypei[1]'\in \randtypespace} \langle \typei[1],\randalloci[1](\vertypei[1]',\vertypei[2])) \rangle$ then $\extallocs$ must satisfy the following DSIC constraint, $$\begin{aligned}
    \alpha &\langle \typei[1],  \extalloci[1]^{\alpha}(\typei[1]) \rangle + \beta \langle \typei[1], \extalloci[1]^{\beta}(\typei[1])\rangle - \payi[1](\typei[1],\vertypei[2]) \geq \nonumber \\ &\langle \typei[1],\randalloci[1](\vertypei[\text{max}],\vertypei[2])) \rangle - \payi[1](\vertypei[\text{max}],\vertypei[2]). \label{eq:randIC-contr}\end{aligned}$$ We use this constraint to place an upper bound on $\payi[1](\typei[1],\vertypei[2])$.

By definition of $V_{\text{max}}$, $$\begin{aligned}
    \langle \typei[1],\randalloci[1](\vertypei[\text{max}],\vertypei[2])) \rangle \geq \langle \typei[1], \extalloci[1]^{\alpha}(\typei[1]) \rangle.\end{aligned}$$ Subtracting $\langle \typei[1],\randalloci[1](\vertypei[\text{max}],\vertypei[2])) \rangle$ from both sides of \[eq:randIC-contr\] and utilizing the fact that $\alpha+\beta=1$ we have $$\begin{aligned}
    \beta \langle \typei[1], \extalloci[1]^{\beta}(\typei[1]) \rangle - \beta \langle \typei[1],\randalloci[1](\vertypei[\text{max}],\vertypei[2]) \rangle \\ \geq \payi[1](\typei[1],\vertypei[2]) - \payi[1](\vertypei[\text{max}],\vertypei[2]).\end{aligned}$$ Now using the fact that $\typei[1]$’s maximum difference in value for any two allocations in ${\mathscr{F}}$ is upper bounded by 3, we get $$\begin{aligned}
    3\beta+\payi[1](\vertypei[\text{max}],\vertypei[2]) &\geq \payi[1](\typei[1],\vertypei[2]). \label{eq:pay-bound}\end{aligned}$$

By construction, for $\vertypei[2] \in \{A', B', C', D'\}$, there exists a type $\vertypei[\text{not}] \in \{E',F',G',H'\}$ which has value $0$ for every allocation in ${X_{V_2}}$. (For example if $V_2=A'$ then all of the allocations in $\{\extalloci[1](A',A'), \extalloci[1](B',A'), \extalloci[1](C', A'), \extalloci[1](D', A')\}$ have a $0$ in the $4^{\text{th}}$ coordinate and in this case $V_{\text{not}}=E'$). Now by , $V_{\text{not}}$ receives utility $-\payi[1](V_{\text{not}}, \vertypei[2]) = -\payi[1](\vertypei[\text{max}],\vertypei[2])$ when reporting truthfully against opponent type $\vertypei[2]$.

Therefore, in order to keep $\vertypei[\text{not}]$ from deviating to type $\typei[1]$, we must satisfy the following DSIC constraint, $$\begin{aligned}
    -\payi[1](\vertypei[max],\vertypei[2]) \geq & \alpha \langle \vertypei[\text{not}],  \extalloci[1]^{\alpha}(\typei[1]) \rangle \nonumber + \beta \langle \vertypei[\text{not}], \extalloci[1]^{\beta}(\typei[1])\rangle \\
    & - \payi[1](\typei[1],\vertypei[2]). 
    \label{eq:tempDSIC}\end{aligned}$$ Since $\extalloci[1]^{\alpha}(\typei[1])$ is the expected allocation conditioned on the resulting allocation being an element of ${X_{V_2}}$, and $V_{\text{not}}$ has zero value for any allocation in ${X_{V_2}}$, we have $\langle V_{\text{not}}, \extalloci[1]^\alpha \rangle = 0$.

Therefore,

$$\begin{aligned}
    \payi[1](\typei[1],\vertypei[2])  &\geq \beta \langle \vertypei[\text{not}], \extalloci[1]^{\beta}(\typei[1])\rangle + \payi[1](\vertypei[\text{max}],\vertypei[2]). \label{eq:pay-bound2}\end{aligned}$$

Notice that for every allocation outside of ${X_{V_2}}$ the type $\vertypei[\text{not}]$ has value exactly $100$ and therefore $\langle \vertypei[\text{not}], \alloc_{\beta}(\type)\rangle = 100$. We now use this fact along with \[eq:pay-bound\] and \[eq:pay-bound2\] and derive the following contradiction, $$\begin{aligned}
    3\beta+\payi[1](\vertypei[\text{max}],\vertypei[2])- \payi[1](\vertypei[\text{max}],\vertypei[2]) &\geq \beta \langle \vertypei[\text{not}], \alloc_{\beta}\rangle, \\
    \Rightarrow \quad 3\beta &\geq 100 \beta.\end{aligned}$$ Since by assumption $\beta > 0$, this is a contradiction.

We are now ready to prove Theorem \[thm:rand\].

Consider $\typei[1] = \tfrac 1 3 A' + \tfrac 1 3 B' + \tfrac 1 3 D'$ and assume ${\operatorname{\mathbf{Pr}}_{}{{\mathchoice{ \left [ \extalloci[1](\typei[1],A') = \randalloci[1](A', A')  \right ]}{[ \extalloci[1](\typei[1],A') = \randalloci[1](A', A') ]}{[ \extalloci[1](\typei[1],A') = \randalloci[1](A', A') ]}{[ \extalloci[1](\typei[1],A') = \randalloci[1](A', A') ]} }}} <1$.

We know from that $\extalloci[1](\typei[1], A')$ is supported on $\{\extalloci[1](A',A'), \extalloci[1](B',A'), \extalloci[1](C', A'), \extalloci[1](D', A')\}$. Since $\randalloci[1](A',A')$ is the only allocation for which both $A'$ and $B'$ have positive value, $\typei[1]$ satisfies $$\begin{aligned}
    \forall \vertype' \neq A', \quad \langle \typei[1], \randalloci[1](\vertype',A') \rangle < \langle \typei[1], \randalloci[1](A',A') \rangle.\label{eq:strictval}\end{aligned}$$ But in order for $\typei[1]$ to have no incentive to report $A'$ when agent $2$’s type is $A'$, we have $$\begin{aligned}
    {\operatorname{\mathbf E}_{}{{\mathchoice{ \left [ \langle \typei[1], \extalloci[1](\typei[1],A') \rangle  \right ]}{[ \langle \typei[1], \extalloci[1](\typei[1],A') \rangle ]}{[ \langle \typei[1], \extalloci[1](\typei[1],A') \rangle ]}{[ \langle \typei[1], \extalloci[1](\typei[1],A') \rangle ]} }}} & - \payi[1](\typei[1],A') \geq \\
    & \langle \typei[1], \randalloci[1](A', A') \rangle - \payi[1](A', A').\end{aligned}$$ Using eq. , we have $$\begin{aligned}
    \payi[1](A', A') &> \payi[1](\typei[1],A')\label{eq:strictpay}.\end{aligned}$$ We now show that, similar to , a strictly lower payment for $\typei[1]$ as in would violate DSIC constraints. The DSIC constraint that keeps type $D'$ from deviating to type $\typei[1]$ when the opponents type is $A'$ is $$\begin{aligned}
        \langle D', \randalloci[1](D', A') \rangle - \payi[1](D', A') \nonumber \\ \geq \langle D' , \extalloci[1](\typei[1],A') \rangle -\payi[1](\typei[1],A') \label{eq:Dconstraint}.\end{aligned}$$ Since $\extalloci[1](\typei[1],A')$ is supported on $\{\extalloci[1](A',A'),$ $ \extalloci[1](B',A'),$ $ \extalloci[1](C', A'),$ $\extalloci[1](D', A')\}$ and type $D'$ values all of these allocations equally we have $$\begin{aligned}
    \langle D', \extalloci[1](\typei[1],A') \rangle = \langle D', \randalloci[1](D', A') \rangle,\end{aligned}$$ and by we have $\payi[1](D',A') = \payi[1](A',A')$. Using these facts we write as $$\begin{aligned}
     \payi[1](\typei[1],A') &\geq \payi[1](A',A').\end{aligned}$$ This contradicts .

Therefore, $\extalloci[1](\typei[1], A')$ must be deterministically $\randalloci[1](A', A')$. But the only allocation in ${\mathscr{F}}$ with agent $1$’s allocation being this is $\randallocs(A', A')$, and hence $\extalloci[2](\typei[1], A')$ is deterministically $[1, 1, 0,0,100,100,100]$. Using the same argument, one can show $\extalloci[1](\typei[1], D') = [4, 4, 0,100,100,100,0]$ with probability 1, which implies $\extalloci[2](\typei[1], D')$ is supported on $\{[2, 2, 0,100,0,100,100],[4, 4, 0,100,100,100,0]\}$. For any allocation with this support, weak monotonicity is violated for agent $2$’s types $A'$ and $D'$.

Revenue Gap {#sec:revenue}
===========

In this section we explore the revenue gap between mechanisms that satisfy DSIC and IR on $\operatorname{supp}(D)$ and mechanisms that satisfy DSIC and IR on $\operatorname{Conv}(\operatorname{supp}(D))$. Any type that is in $\operatorname{Conv}(\operatorname{supp}(D))$ and not $\operatorname{supp}(D)$ occurs with probability zero and does not itself contribute to the revenue. It is therefore not obvious that enforcing constraints on these additional types will impact revenue. In fact, shows that if the feasible set is downward closed there is no gap in revenue between these two typespaces. However, for arbitrary feasibility sets, a gap can arise because not every mechanism which is DSIC and IR can be extended to $\operatorname{Conv}(\operatorname{supp}(D))$ without changing the payment rules on the support. We show that for some feasibility sets and distributions the gap in revenue between the optimal DSIC and IR mechanism on $\operatorname{supp}(D)$ and the optimal mechanism on $\operatorname{Conv}(\operatorname{supp}(D))$ is unbounded.

For a feasible set of allocations ${\mathscr{F}}$ and a distribution $\mathbf{D}$ we, let $\operatorname{OPT}({\mathscr{F}},\mathbf{D})$ denote the optimal revenue extractable by a DSIC and IR mechanism on $\operatorname{supp}(D)$, and let $\widetilde{\operatorname{OPT}}({\mathscr{F}},\mathbf{D})$ denote the maximum revenue extractable by a mechanism that is DSIC and IR on $\operatorname{Conv}(\operatorname{supp}(D))$.

We focus on the single agent case and show that the ratio between $\operatorname{OPT}({\mathscr{F}}, D)$ and $\widetilde{\operatorname{OPT}}({\mathscr{F}}, D)$ is unbounded.

\[thm:revenue\] $\forall \alpha$, there exists a feasible set ${\mathscr{F}}$ and distribution $\mathbf{D}$ such that $\operatorname{OPT}({\mathscr{F}},\mathbf{D}) \geq \alpha \widetilde{\operatorname{OPT}}({\mathscr{F}}, \mathbf{D})$.

Let ${\vec{\mathbf{1}}}$ be the “all-ones” vector of length k and define the set $$\begin{aligned}
{\mathcal{S}_{1}}= \{ \type \in \mathbb{R}^k  \mid \exists j \text{ s. t. } \typei[j] =1 \\ \text{ and } \forall h \neq j, \: \typei[h]=0\}.\end{aligned}$$ Intuitively, ${\mathcal{S}_{1}}$ is the set of all vectors of length k with exactly one coordinate being $1$ and the rest of the coordinates being zero. We define the support, $\operatorname{supp}(D) = {\mathcal{S}_{1}}\cup \vec{\mathbf{1}}$ and the set of feasible allocations ${\mathscr{F}}= {\mathcal{S}_{1}}$.

We can show that $\operatorname{OPT}({\mathscr{F}}, \mathbf{D})=1$ for any distribution $\mathbf{D}$ that shares this support. This is obtained by giving each $\type \in {\mathcal{S}_{1}}$ an allocation $\alloc$ equal to their type i.e. $\type = \alloc(\type)$ and giving type $\type = {\vec{\mathbf{1}}}$ any allocation in the feasible set. We can now charge a payment of $1$ to every type.

Without loss of generality assume $\alpha>1$. Now for any $\alpha$ define $\epsilon< \frac{1}{\alpha}$ and consider the distribution where $Pr[\type= \vec{\mathbf{1}}] = 1- \epsilon$ and $Pr[\type \neq \vec{\mathbf{1}}] = \epsilon$. One of the types contained in $\operatorname{Conv}(\operatorname{supp}(D))$ is $\type^{k} = [\frac{1}{k}, \frac{1}{k} \ldots \frac{1}{k}]$. $\type^{k}$ has a value of $\frac{1}{k}$ for every feasible allocation and every lottery of existing allocations, therefore the maximum payment we can charge without violating IR constraints is $\frac{1}{k}$. However, the all ones type has value $1$ for every feasible allocation and can now gain utility of $\frac{k-1}{k}$ by deviating to type $\type^k$. Therefore to maintain incentive compatibility we must lower the price we charge the all ones type to $\frac{1}{k}$ (as well as the payment charged to one of the types ${\mathcal{S}_{1}}$). Therefore the revenue generated on the convex hull if we take $k$ to be large is, $\widetilde{\operatorname{OPT}}({\mathscr{F}}, \mathbf{D})\leq \lim_{k\rightarrow \infty} (1-\epsilon)(\frac{1}{k})+\epsilon \leq \frac{1}{\alpha}$.

Conclusion and Future Work {#sec:disc}
==========================

We presented a DSIC mechanism on a discrete type space which cannot be implemented if DSIC is required on the convex hull of its type space. Extension from discrete to convex domains is a common step in automated mechanism design, and it is unfortunate that, as an implication of our result, there exists no general procedure for extending an arbitrary DSIC mechanism to the convex hull of its domain. However, as we showed, such extensions are possible in specific settings, with special type spaces (e.g. single dimensional) or special feasible set of allocations (e.g. downward closed or, more generally, single swap feasible). Other sufficient conditions for extensibility should be useful to have. Another possibility we leave open is conditions on an allocation rule (rather than the type space or the set of feasible allocations) that would guarantee its extensibility. We know that an allocation rule is DSIC implementable if and only if it is cyclic monotone. Is there a condition stronger than cyclic monotonicity which guarantees both implementability and extensibility?

The mechanism we constructed for the impossibility result is intricate. A third question we leave open is whether one may find a succinct property that is *necessary* for extensibility; in other words, is there a natural condition whose violation must result in inextensible mechanisms?

Supplementary Material {#sec:supp}
======================

[^1]: To see that a downward closed ${\mathscr{F}}$ is SSF, observe that we can let ${\boldsymbol{x}^{\mathrm{ssf}}}(i)$ be the all zero vector for each agent $i$.
