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 