Non-bossy single object auctions

Abstract

We study deterministic single object auctions in the private values environment. We show that an allocation rule is implementable (in dominant strategies) and non-bossy if and only if it is a strongly rationalizable allocation rule. With a mild continuity condition, we show that an allocation rule is implementable and non-bossy if and only if it is a simple utility maximizer (with appropriate tie-breaking). All our characterizations extend the seminal result of Roberts (“Aggregation and Revelation of Preferences”, pp. 321–348, 1979) from the unrestricted domain to the restricted domain of single object auctions.

1 Introduction

We study single object auctions in the standard private values model. We are interested in characterizing deterministic allocation rules which can be implemented in dominant strategies using suitable payments. We provide precise characterizations of such rules under an additional condition called non-bossiness. Non-bossiness specifies that keeping the valuations of other agents fixed, if agent $i$ changes his valuation in such a manner such that his own allocation (i.e., whether he gets the object or not) does not change, then the allocation of no other agent should change.

We show that implementability of a non-bossy allocation rule in dominant strategies is equivalent to that allocation rule being a strongly rationalizable allocation rule. Under an additional continuity like condition, this characterization can be strengthened as follows: an implementable non-bossy allocation rule is equivalent to a simple utility maximizer allocation rule. Simple utility maximizers transform the valuation of each agent to a real number using non-decreasing functions that we call simple utility functions. Then, it gives the object to an agent who has the highest non-negative simple utility (breaking ties in a consistent manner). If all the agents have negative simple utility, then the object is not allocated. The simple utility maximizers are a large class of allocation rules—it includes the efficient allocation rule, constrained efficient allocation rule with a reserve price, revenue-optimal allocation rule in Myerson (1981) that maximizes virtual utilities of agents.

1.1 Relation to the literature

The primary objective of this paper is to characterize the set of implementable allocation rules in the single object private values model. While, Myerson (1981) provides a monotonicity condition that is necessary and sufficient, it is only an implicit characterization. We are interested in a functional form explicit characterization of implementable allocation rule.

A benchmark result that answers such a question for the unrestricted domain is Roberts (1979). Consider a general mechanism design set up with private values and quasi-linear utility. Let $A$ be a finite set of alternatives. Suppose $|A| \ge 3$. The type of agent $i$ is denoted as $v_i \in \mathbb {R}^{|A|}$ and $v_i(a)$ denotes the valuation of agent $i$ for alternative $a$. Roberts (1979) shows that if type space of every agent is $\mathbb {R}^{|A|}$, then for every onto and implementable allocation rule $f$, there exists $\lambda _1,\ldots ,\lambda _n \ge 0$, not all of them equal to zero, and $\kappa :A \rightarrow \mathbb {R}$ such that at every valuation profile $v$,

$$\begin{aligned} f(v) \in \arg \max _{a \in A}\left[ \,\sum _{i \in N}\lambda _iv_i(a)+\kappa (a)\right] . \end{aligned}$$

Such allocation rules are called affine maximizer allocation rules. The unrestricted type space plays a crucial role in Roberts’ theorem. It is well known that there are implementable allocation rules in restricted domains that are not affine maximizers. However, few concrete characterizations are known in any such restricted domain.

There have been some extensions of Roberts‘ affine maximizer theorem. Mishra and Sen (2012) show that if the type space is a multidimensional open interval, an additional condition neutrality along with implementability implies affine maximization. Carbajal et al. (2013) provide an extension where they consider infinite set of alternatives but types are continuous functions on these alternatives (or satisfy some topological properties). Marchant and Mishra (2012) show that the set of implementable allocation rules expand if we just have two alternatives. Lavi et al. (2003) characterize almost affine maximizers (affine maximizers for large enough values) in specific combinatorial auction domains using various additional conditions.

The single object auction model is a restricted domain since each agent only places a non-negative value on the alternative where he is allocated the object and places zero value on all the other alternatives. This is a severe restriction on the set of all possible types, and hence, all the earlier results do not have any implication on this model. As is well known, in a restricted domain, the possibility to manipulate is smaller for an agent, and hence, a larger set of allocation rules are implementable. Roberts’ theorem shows that if the domain is unrestricted, then every allocation rule maximizes an affine combination of valuations of agents. Our results show that in the single object auction model, we get some form of maximization but it is no longer an affine maximization. To our knowledge, this is one of the very few papers that has characterized non-affine maximizers. Because of this reason, our methodology of proof differs from proving the Roberts’ theorem.

A work related to ours is Archer and Tardos (2002). They consider the single object auction model and show that if the object is always allocated then the only implementable allocation rules satisfying non-bossiness and three more additional conditions are min function allocation rules. ¹ Min function allocation rules are simple utility maximizer allocation rules, but with some additional limiting and continuity properties. Though our characterization of simple utility maximizer is related to their result, it has several important differences. First, their result requires that we always sell the good. This rules out any allocation rule with a reserve price, such as Myerson’s revenue maximizing allocation rule. Further, our proof shows that allowing the object to be not sold adds several non-trivial complications in deriving our results. Second, they seem to require different types of range and tie-breaking conditions than our continuity requirement. On the other hand, our characterization of simple utility maximizer makes it explicit the way ties need to be broken. Finally, they have no analog of our other characterization.

There have been many simplifications of the original proof of Roberts (Jehiel et al. 2008; Lavi 2007; Dobzinski and Nisan 2009; Vohra 2011; Mishra and Sen 2012). But none of these proofs show how Roberts’ theorem can be extended to a restricted domain like the single object auction model. Unlike most of the literature, our goal is not to characterize “affine maximizers”—indeed, all our characterizations capture a larger class of implementable allocation rules than affine maximizers.

Instead of characterizing implementable allocation rules, one can characterize the set of dominant strategy mechanisms directly by imposing conditions on mechanisms rather than just on allocation rules. A contribution along this line is Ashlagi and Serizawa (2011). They show that any mechanism which always allocates the object, satisfies individual rationality, non-negativity of payments, anonymity in net utility, and dominant strategy incentive compatiblity must be the Vickrey auction. This result is further strengthened by Mukherjee (2013), who shows that any strategy-proof and anonymous (in net utility) mechanism which always allocates the object must use the efficient allocation rule. Further, Sakai (2012) characterizes the Vickrey auction with a reserve price using various axioms on the mechanism (this includes an axiom on the allocation rule which requires a weak version of efficiency). By placing minimal axioms on allocation rules, we are able to characterize a broader class of allocation rules than these papers.

2 The single object auction model

A seller is selling an indivisible object to $n$ potential agents (buyers). The set of agents is denoted by $N:=\{1,\ldots ,n\}$. The private value of agent $i$ for the object is denoted by $v_i \in \mathbb {R}_{++}$. The set of all possible private values of agent $i$ is $V_i \subseteq \mathbb {R}_{++}$—note that we do not allow zero valuations. We will use the usual notations $v_{-i}$ and $V_{-i}$ to denote a profile of valuations without agent $i$ and the set of all profiles of valuations without agent $i$, respectively. Let $V:=V_1 \times V_2 \times \cdots \times V_n$.

The set of alternatives is denoted by $A:=\{e^0,e^1,\ldots ,e^n\}$, where each $e^i$ is a vector in $\mathbb {R}^n$. In particular, $e^0$ is the zero vector in $\mathbb {R}^n$ and $e^i$ is the unit vector in $\mathbb {R}^n$ with $i$-th component $1$ and all other components zero. The $j$-th component of the vector $e^i$ will be denoted by $e^i_j$. The alternative $e^0$ is the alternative where the seller keeps the object and for every $i \in N$, $e^i$ is the alternative where agent $i$ gets the object. Notice that our model focuses on deterministic alternatives. Every agent $i \in N$ gets zero value from any alternative where he does not get the object. An allocation rule is a mapping $f:V \rightarrow A$. For every $v \in V$ and for every $i \in N$, the notation $f_i(v) \in \{0,1\}$ will denote if agent $i$ gets the object ($f_i(v)=1$) or not ($f_i(v)=0)$ at valuation profile $v$ in allocation rule $f$.

Payments are allowed and agents have quasi-linear utility functions over payments. A payment rule of agent $i \in N$ is a mapping $p_i:V \rightarrow \mathbb {R}$.

Definition 1

An allocation rule $f$ is implementable (in dominant strategies) if there exist payment rules $(p_1,\ldots ,p_n)$ such that for every agent $i \in N$ and for every $v_{-i} \in V_{-i}$

$$\begin{aligned} v_i f_i(v_i,v_{-i}) - p_i(v_i,v_{-i}) \ge v_i f_i(v'_i,v_{-i}) - p_i(v'_i,v_{-i}) \qquad \forall ~v_i,v'_i \in V_i. \end{aligned}$$

In this case, we say $(p_1,\ldots ,p_n)$ implement $f$ and the mechanism $(f,p_1,\ldots ,p_n)$ is incentive compatible.

Myerson (1981) showed that the following notion of monotonicity is equivalent to implementability: see also Laffont and Maskin (1980) for a similar characterization.

Definition 2

An allocation rule $f$ is monotone if for every $i \in N$, for every $v_{-i} \in V_{-i}$, and for every $v_i,v'_i \in V_i$ with $v_i < v'_i$ and $f_i(v_i,v_{-i}) = 1$, we have $f_i(v'_i,v_{-i})=1$.

The equivalence of monotonicity and implementability does not require any restriction on the space of valuations [see Vohra (2011), for instance].

3 Implementation, non-bossiness, and rationalizability

We now introduce the notion of rationalizability in our model. At every profile of valuations, by choosing an alternative, the mechanism designer assigns values to each agent—zero to all agents who do not get the object but positive value to the agent who gets the object. Denote by $\mathbf {1}_{v_i}$ the vector of valuations in $\mathbb {R}^n_+$, where all the components except agent $i$ have zero and the component corresponding to agent $i$ has $v_i$. Further, denote by $\mathbf {1}_0$ the $n$-dimensional zero vector. For convenience, we will write $\mathbf {1}_0$ as $\mathbf {1}_{v_0}$ at any valuation profile. Using this notation, at a valuation profile $(v_1,\ldots ,v_n)$, a mechanism designer’s choice of an alternative in $A$ can lead to the selection of one of the following $(n+1)$ vectors in $\mathbb {R}^n_{+}$ to be chosen $-\mathbf {1}_{v_0}, \mathbf {1}_{v_1},\ldots ,\mathbf {1}_{v_n}$. We will refer to these vectors as utility vectors. Any allocation rule $f$ can alternatively thought of choosing utility vectors at every valuation profile. The domain of valuations $V_i$ of agent $i$ gives rise to a set of feasible utility vectors where only agent $i$ gets positive value. In particular, define for every $i \in N$, $D_i := \{\mathbf {1}_{v_i}: v_i \in V_i\}$. Further, let $D_0:=\{\mathbf {1}_{v_0}\}$ and $V_0=\{0\}$. Denote by $D:=D_0 \cup D_1 \cup D_2 \cup \ldots \cup D_n$, the set of all utility vectors consistent with the domain of profile of valuations $V$. To define the notion of a rational allocation rule, we will use orderings (reflexive, complete, and transitive binary relation) on the set of utility vectors $D$. For any ordering $\succeq$ on $D$, let $\succ$ be the asymmetric component of $\succeq$ and $\sim$ be the symmetric component of $\succeq$. A strict linear ordering is an anti-symmetric ordering with no symmetric component. An ordering $\succeq$ on $D$ is monotone if for every $i \in N$, for every $v_i,v'_i \in V_i$ with $v_i > v'_i$, we have $\mathbf {1}_{v_i} \succ \mathbf {1}_{v'_i}$. Our notion of rational allocation requires that at every profile of valuations it must choose a maximal element among the utility vectors at that valuation profile, where the maximal element is defined using a monotone ordering on $D$.

We now formally define a rationalizable allocation rule. For every allocation rule $f$, let $G^f:V \rightarrow D$ be a social welfare function induced by $f$, i.e., for all $v \in V$, $G^f(v)=\mathbf {1}_{v_j}$ if $f(v)=e^j$ for any $j \in \{0,1,\ldots ,n\}$.

Definition 3

An allocation rule $f$ is rationalizable if there exists a monotone ordering $\succeq$ on $D$ such that for all $v \in V$, $G^f(v) \succeq \mathbf {1}_{v_j}$ for all $j \in \{0,1,\ldots ,n\}$. In this case, we say $\succeq$ rationalizes $f$.

An allocation rule $f$ is strongly rationalizable if there exists a monotone strict linear ordering $\succ$ on $D$ such that for all $v \in V$, $\mathbf {1}_{v_i} \succ \mathbf {1}_{v_j}$ for all $j \in \{0,1,\ldots ,n\} {\setminus } \{i\}$, where $G^f(v) = \mathbf {1}_{v_i}$. In this case, we say $\succ$ strongly rationalizes $f$.

We will investigate the relationship between (strongly) rationalizable allocation rules and implementable allocation rules. The following lemma establishes that a rational allocation rule is implementable.

Lemma 1

Every rationalizable allocation rule is implementable.

Proof

Consider a rationalizable allocation rule $f$ and let $\succeq$ be the corresponding ordering on $D$. Fix an agent $i$ and valuation profile $v_{-i}$. Consider two valuations of agent $i$: $v_i$ and $v'_i$ with $v_i < v'_i$ with $f(v_i,v_{-i})=e^i$. By definition of $\succeq$, $\mathbf {1}_{v_i} \succeq \mathbf {1}_{v_j}$ for all $j \in (N \cup \{0\}) {\setminus } \{i\}$. Since $\succeq$ is monotone, $\mathbf {1}_{v'_i} \succ \mathbf {1}_{v_i}$. By transitivity, $\mathbf {1}_{v'_i} \succ \mathbf {1}_{v_j}$ for all $j \in (N \cup \{0\}) {\setminus } \{i\}$. Then, by the definition of $\succeq$, $f(v'_i,v_{-i})=e^i$. Hence, $f$ is monotone, and hence, implementable. $\square$

The converse of Lemma 1 is not true. The following example establishes that.

Example 1

Suppose there are two agents: $N=\{1,2\}$. Suppose $V_1=V_2=\mathbb {R}_{++}$. Consider an allocation rule $f$ defined as follows. At any valuation profile $(v_1,v_2)$, if $\max (v_1-2v_2,v_2 - v_1) < 0$, then $f(v_1,v_2)=e^0$. Else, if $v_1 - 2v_2 < v_2 - v_1$, then $f(v_1,v_2)=e^2$ and if $v_1 - 2v_2 \ge v_2 - v_1$, then $f(v_1,v_2)=e^1$. It is easy to verify that $f$ is monotone, and hence, implementable. $\square$

We argue that $f$ is not a rationalizable allocation rule. Assume for contradiction that $f$ is a rationalizable allocation rule and $\succeq$ is the corresponding monotone ordering. Consider the profile of valuation $(v_1,v_2)$, where $v_1=1$ and $v_2=2$. For $\epsilon > 0$ but arbitrarily close to zero, $f(v_1,v_2-\epsilon )=e^2$. Hence, $\mathbf {1}_{v_2-\epsilon } \succeq \mathbf {1}_{v_0}$. By monotonicity, $\mathbf {1}_{v_2} \succ \mathbf {1}_{v_0}$. Now, consider the profile of valuations $(v'_1,v_2)$, where $v'_1=2+\epsilon$ and $v_2=2$. Note that $f(v'_1,v_2)=e^0$. Hence, $\mathbf {1}_{v_0} \succeq \mathbf {1}_{v_2}$. This is a contradiction.

A feature of this example is that at valuation profile $(v_1,v_2)$, the allocation rule was choosing $e^2$. But when valuation of agent $1$ changed to $v'_1$, it chose $e^0$ at valuation profile $(v'_1,v_2)$. Hence, agent 1 could change the outcome without changing his own outcome. As we show next, such allocation rules are incompatible with rationalizability.

We will now show that the set of implementable and non-bossy allocation rules are characterized by strongly rationalizable allocation rules.

Definition 4

An allocation rule $f$ is non-bossy if for every $i \in N$, for every $v_{-i} \in V_{-i}$ and for every $v_i,v'_i \in V_i$ with $f_i(v_i,v_{-i}) = f_i(v'_i,v_{-i})$, we have $f(v_i,v_{-i})=f(v'_i,v_{-i})$.

Non-bossiness requires that if an agent does not change his own allocation (i.e., whether he is getting the object or not) by changing his valuation, then he should not be able to change the allocation of anyone. It was first proposed by Satterthwaite and Sonnenschein (1981).

Lemma 2

A strongly rationalizable allocation rule is non-bossy.

Proof

Let $f$ be a strongly rationalizable allocation rule with $\succ$ being the corresponding ordering on $D$. Fix an agent $i$ and $v_{-i} \in V_{-i}$. Consider $v_i,v'_i \in V_i$ such that $f(v_i,v_{-i})=e^j \ne e^i$. By definition, $\mathbf {1}_{v_j} \succ \mathbf {1}_{v_k}$ for all $k \in (N \cup \{0\}) {\setminus } \{j\}$. Suppose $f(v'_i,v_{-i})=e^l \ne e^i$. By definition, $\mathbf {1}_{v_l} \succ \mathbf {1}_{v_k}$ for all $k \in (N \cup \{0\}) {\setminus } \{l\}$. Assume for contradiction $e^l \ne e^j$. Then, we get that $\mathbf {1}_{v_j} \succ \mathbf {1}_{v_l}$ and $\mathbf {1}_{v_l} \succ \mathbf {1}_{v_j}$, which is a contradiction. $\square$

This leads to the formal connection between implementability and rationalizability.

Theorem 1

An allocation rule is implementable and non-bossy if and only if it is strongly rationalizable.

The proof of Theorem 1 is in the Appendix. Theorem 1 reveals a surprising connection between rationalizability and single object auction design. Notice that Theorem 1 does not require any restriction on $V_i$. If the strict linear ordering we constructed in the proof of Theorem 1 can be represented using a utility function, then the characterization will be even more direct. If for every agent $i \in N$, $V_i$ is finite, then it is possible. But, as the next example illustrates, this is not always possible.

Example 2

Suppose $N=\{1,2\}$ and $V_1=V_2=\mathbb {R}_{++}$. Consider the allocation rule $f$ such that for all valuation profiles $(v_1,v_2)$, $f(v_1,v_2)=e^1$ if $v_1 \ge 1$, $f(v_1,v_2)=e^2$ if $v_1 < 1$ and $v_2 \ge 1$, and $f(v_1,v_2)=e^0$ otherwise. It can be verified that $f$ is implementable (monotone) and non-bossy. By Theorem 1, $f$ is strongly rationalizable. Now, consider the strict linear order defined in the proof of Theorem 1 that strongly rationalizes $f$—denote it by $\succ ^f$. If $v_1=v_2=1$, we have $f(v_1,v_2)=e^1$. Hence, $\mathbf {1}_{v_1} \succ ^f \mathbf {1}_{v_2}$. $\square$

Now, consider the following definition.

Definition 5

An ordering $\succeq$ on the set $D$ is separable if there exists a countable set $Z \subseteq D$ such that for every $x,y \in D$ with $x \succ y$, there exists $z \in Z$ such that $x \succeq z \succeq y$.

It is well known that an ordering on $D$ has a utility representation if and only if it is separable Fishburn (1970). We show that $\succ ^f$ is not separable. Consider $v_1=v_2=1$. By definition of $f$, $\mathbf {1}_{v_1} \succ ^f \mathbf {1}_{v_2} \succ ^f \mathbf {1}_{v_0}$. Note that since $\succ ^f$ is monotone, any utility vector between $\mathbf {1}_{v_1}$ and $\mathbf {1}_{v_2}$ (according to $\succ ^f$) will be of the form $\mathbf {1}_{v_2+\epsilon }$ or $\mathbf {1}_{v_1-\epsilon }$ for some $\epsilon > 0$. But, $f(v_1,v_2+\epsilon )=e^2$ implies that $\mathbf {1}_{v_2+\epsilon } \succ ^f \mathbf {1}_{v_1}$ for all $\epsilon > 0$. Also, $f(v_1-\epsilon ,v_2)=e^2$ implies that $\mathbf {1}_{v_2} \succ ^f \mathbf {1}_{v_1-\epsilon }$ for all $\epsilon > 0$. Hence, there cannot exist $z \in D$ such that $\mathbf {1}_{v_1} \succ ^f z \succ ^f \mathbf {1}_{v_2}$.

3.1 Simple utility maximization

We saw that the strict linear ordering that strongly rationalizes an allocation rule may not have a utility representation. The aim of this section is to explore minimal conditions that allow us to define a new ordering for any implementable and non-bossy allocation rule which has a utility representation. Our extra condition is a continuity condition.

Definition 6

An allocation rule $f$ satisfies Condition $\varvec{\mathcal {C}}^*$ if for every $i,j \in N$ ($i \ne j$) and for every $v_{-ij}$, for every $\epsilon > 0$, there exists a $\delta _{\epsilon ,v_{-ij}} > 0$ such that for every $v_i,v_j$ with $f(v_i,v_j,v_{-ij})=e^i$, we have $f(v_i+\epsilon ,v_j + \delta _{\epsilon ,v_{-ij}},v_{-ij})=e^i$.

Condition $\mathcal {C}^*$ requires some version of continuity of the allocation rule. It says that if some agent $i$ is winning the object at a valuation profile, for every increase in value of agent $i$, there exists some increase in value of agent $j$ such that agent $i$ continues to win the object.

If $f$ is monotone (implementable) and non-bossy, then Condition $\mathcal {C}^*$ implies that for every $i,j \in N$ ($i \ne j$) and for every $v_{-ij}$, for every $\epsilon > 0$, there exists a $\delta _{\epsilon ,v_{-ij}} > 0$ such that for every $v_i,v_j$ with $f(v_i,v_j,v_{-ij})=e^i$, we have $f(v_i+\epsilon ,v_j + \delta ,v_{-ij})=e^i$ for all $0 < \delta < \delta _{\epsilon ,v_{-ij}}$. To see this, choose some $\delta \in (0,\delta _{\epsilon ,v_{-ij}})$ and assume for contradiction, $f(v_i+\epsilon ,v_j + \delta ,v_{-ij})=e^k$ for some $k \ne i$. If $k = j$, then by monotonicity, $f(v_i+\epsilon ,v_j + \delta _{\epsilon ,v_{-ij}},v_{-ij})=e^j$, which is a contradiction to Condition $\mathcal {C}^*$. If $k \ne \{i,j\}$, then by non-bossiness, $f(v_i+\epsilon ,v_j + \delta _{\epsilon ,v_{-ij}},v_{-ij}) \in \{e^j,e^k\}$, again a contradiction to Condition $\mathcal {C}^*$. Since we will use Condition $\mathcal {C}^*$ along with implementability and non-bossiness, we can freely make use of this implication.

We will now introduce a new class of allocation rules.

Definition 7

An allocation rule $f$ is a simple utility maximizer (SUM) if there exists a non-decreasing function $U_i:V_i \rightarrow \mathbb {R}$ for every $i \in N \cup \{0\}$, where $U_0(0)=0$, such that for every valuation profile $v \in V$, $f(v)=e^j$ implies that $j \in \arg \max _{i \in N \cup \{0\}}U_i(v_i)$.

Notice that an SUM allocation rule is simpler to state and, hence, more suitable for practical use than a strongly rationalizable allocation rule. The aim of this section is to show that the SUM allocation rules are not much different from the strongly rationalizable allocation rules.

It can be easily seen that not every SUM allocation rule is non-bossy. For instance, consider the efficient allocation rule that allocates the good to an agent with the highest value. Suppose there are three agents with valuations $10,10,8$, respectively, and suppose that the efficient allocation rule allocates the object to agent 1. Consider the valuation profile $(10,10,9)$ and suppose that the efficient allocation rule now allocates the object to agent 2. This violates non-bossiness. As we will show that such violations can happen in case of ties (as was the case here with ties between agents 1 and 2), and when ties are broken carefully, an SUM allocation rule becomes non-bossy.

Similarly, not every SUM allocation rule is implementable. For instance, consider an example with two agents $\{1,2\}$ with $V_1=V_2=\mathbb {R}_{++}$. Let $U_1(v_1)=1$ and $U_2(v_2)=v_2$. Now, suppose we pick agent 1 as the winner of the object at valuation profile $(1,1)$ but pick agent 2 as the winner of the object at valuation profile $(2,1)$. Note that this is consistent with simple utility maximization but violates monotonicity, and hence, not implementable.

Now, consider the following modification of the SUM allocation rule.

Definition 8

An allocation rule $f$ is a simple utility maximizer (SUM) with order-based tie-breaking if there exists a non-decreasing function $U_i:V_i \rightarrow \mathbb {R}$ for every $i \in N \cup \{0\}$, where $U_0(0)=0$, and a monotone strict linear ordering $\succ$ on $D$ such that for every valuation profile $v \in V$, $f(v)=e^j$ implies that $j \in \arg \max _{i \in N \cup \{0\}}U_i(v_i)$ and $\mathbf {1}_{v_j} \succ \mathbf {1}_{v_k}$ for all $k \ne j$ and $k \in \arg \max _{i \in N \cup \{0\}}U_i(v_i)$, i.e., $j$ is the unique simple utility maximizer according to $\succ$.

The tie-breaking rule that we specified is very general. It covers some intuitive tie-breaking rules such as having an ordering over $N \cup \{0\}$ and breaking the tie in simple utility maximization using this ordering.

Lemma 3

An SUM allocation rule with order-based tie-breaking is implementable.

Proof

Suppose $f$ is an SUM allocation rule with order-based tie-breaking. Let the corresponding simple utility functions be $U_0,U_1,\ldots ,U_n$ and $\succ$ be the ordering used to break ties. At any valuation profile $v$, let $W(v)=\{j \in N \cup \{0\}:U_j(v_j) \ge U_k(v_k)~\forall ~k \in N \cup \{0\}\}.$ Fix an agent $i$ and the valuation profile of other agents at $v_{-i}$. Consider $v_i,v'_i$ such that $v_i < v'_i$ and $f(v_i,v_{-i})=e^i$. Then, by SUM maximization, $i \in W(v_i,v_{-i})$. Further, by order-based tie-breaking $\mathbf {1}_{v_i} \succ \mathbf {1}_{v_j}$ for all $j \in W(v_i,v_{-i})$. Since $U_i$ is non-decreasing, $U_i(v'_i) \ge U_j(v_j)$ for all $j \in (N \cup \{0\}) {\setminus } \{i\}$. Hence, $i \in W(v'_i,v_{-i})$. Again, by order-based tie-breaking, $\mathbf {1}_{v'_i} \succ \mathbf {1}_{v_i} \succ \mathbf {1}_{v_j}$ for all $j \in W(v'_i,v_{-i})$. This implies that $f(v'_i,v_{-i})=e^i$. So, $f$ is monotone, and hence, implementable. $\square$

An SUM allocation rule with order-based tie-breaking is also non-bossy.

Lemma 4

An SUM allocation rule with order-based tie-breaking is non-bossy.

Proof

Let $f$ be an SUM allocation rule with order-based tie-breaking and $v$ be a valuation profile such that $f(v) \ne e^j$ for some $j \in N$. Suppose $f(v'_j,v_{-j}) \ne e^j$. Then, by definition, the unique simple utility maximizer of $f$ remains the same in $(v_j,v_{-j})$ and $(v'_j,v_{-j})$. So, $f(v_j,v_{-j})=f(v'_j,v_{-j})$, and hence, $f$ is non-bossy. $\square$

We are now ready to state the main result of this section.

Theorem 2

Suppose $V_i=(0,\beta _i)$, where $\beta _i \in \mathbb {R}_{++} \cup \{\infty \}$, for all $i \in N$ and $f$ is an allocation rule satisfying Condition $\mathcal {C}^*$. Then, $f$ is implementable and non-bossy if and only if it is a simple utility maximizer with order-based tie-breaking.

The proof of Theorem 2 is given in the Appendix. We note that the affine maximizers in Roberts’ theorem can be obtained using linear functions $U_i$ for every $i \in N$. The virtual utility maximizer in Myerson (1981) takes the form $U_i(v_i)=v_i - \frac{1-F_i(v_i)}{f_i(v_i)}$, where $F_i$ and $f_i$ are, respectively, the cumulative density function and density function of the distribution of valuation of agent $i$. Hence, many standard allocation rules in theory and practice are simple utility maximizers.

Further, it is well known that revenue equivalence Myerson (1981) implies that for any implementable allocation rule, the payments are determined uniquely up to an additive constant. Thus, by characterizing implementable allocation rules, we characterize the class of dominant strategy incentive compatible mechanisms.

Appendix: Omitted proofs

Proof of Theorem 1

By virtue of Lemmas 1 and 2, we only need to show that if an allocation rule $f$ is implementable and non-bossy then it is strongly rationalizable. We do the proof in several steps.

Step 1. For any $i,j \in N \cup \{0\}$ with $i \ne j$, consider $\mathbf {1}_{v_i}$ and $\mathbf {1}_{v_j}$ for some $v_i \in V_i$ and $v_j \in V_j$. Suppose for some $v_{-ij}$, we have $f(v_i,v_j,v_{-ij})=e^i$. We will show that if $f$ is non-bossy, then $f(v_i,v_j,v'_{-ij}) \ne e^j$ for all $v'_{-ij}$. Consider any $k \notin \{i,j\}$ and the profile $(v_i,v_j,v'_k,v_{-ijk})$. By non-bossiness, $f(v_i,v_j,v'_k,v_{-ijk}) \in \{e^i,e^k\}$. Repeating this argument for all $k \notin \{i,j\}$, we get $f(v_i,v_j,v'_{-ij}) \ne e^j$.

Step 2. We will first define binary relations $\succ$ on $D \times D$ ² using $f$ as follows. For every $i,j \in N \cup \{0\}$ with $i \ne j$, $\mathbf {1}_{v_i} \in D_i$ and $\mathbf {1}_{v_j} \in D_j$, define $\mathbf {1}_{v_i} \succ \mathbf {1}_{v_j}$ if there is some $v_{-ij}$ such that $f(v_i,v_j,v_{-ij})=e^i$. Further, for every $i \in N$ and every $v_i \in V_i$, define $\mathbf {1}_{v_i+\epsilon } \succ \mathbf {1}_{v_i}$ for all $\epsilon > 0$ such that $(v_i+\epsilon ) \in V_i$. Using Step 1, if $\mathbf {1}_{v_i} \succ \mathbf {1}_{v_j}$, then $\mathbf {1}_{v_j} \nsucc \mathbf {1}_{v_i}$. Hence, $\succ$ is anti-symmetric. Further, $\succ$ is irreflexive by definition.

Step 3. Let $D^f:=\{x \in D: G^f(v)=x~\mathrm for some ~v \in V\}$. We now show that $\succ$ satisfies the following conditions:

• 1 for every $x,y \in D^f$, either $x \succ y$ or $y \succ x$ (but not both), where $D^f=\{x \in D: G^f(v)=x~\mathrm for some ~v \in V\}$,

• 2 for every $x \in D^f$ and for every $y \notin D^f$, $x \succ y$,

• 3 for all $v \in V$, $\mathbf {1}_{v_i} \succ \mathbf {1}_{v_j}$ for all $j \in \{0,1,\ldots ,n\} {\setminus } \{i\}$, where $G^f(v)=\mathbf {1}_{v_i}$.

Proof of (1). Pick $x,y \in D^f$. By definition, there is $v \in V$, such that $G^f(v)=x$. If $x = \mathbf {1}_{v_i}$, then $f(v)=e^i$. Suppose $y=\mathbf {1}_{v'_i}$. Then, by definition, either $x \succ y$ or $y \succ x$. Hence, suppose $y=\mathbf {1}_{v'_j}$ for some $j \ne i$. Then, by monotonicity and non-bossiness, $f(v_i,v'_j,v_{-ij}) \in \{e^i,e^j\}$. Hence, either $x \succ y$ or $y \succ x$. Since $\succ$ is anti-symmetric, either $x \succ y$ or $y \succ x$ but not both.

Proof of (2). Pick $x \in D^f$ but $y \notin D^f$. By definition, there is $v \in V$, such that $G^f(v)=x$. If $x = \mathbf {1}_{v_i}$, then $f(v)=e^i$. Suppose $y=\mathbf {1}_{v'_i}$. Then, if $v'_i > v_i$, we have $f(v'_i,v_{-i})=e^i$ by monotonicity, and this contradicts the fact that $y \notin D^f$. Hence, $v'_i < v_i$, and by definition, $x \succ y$.

Suppose $y=\mathbf {1}_{v'_j}$ for some $j \ne i$. Then, by monotonicity and non-bossiness, $f(v_i,v'_j,v_{-ij}) \in \{e^i,e^j\}$. Using the fact that $y \notin D^f$, we get that $f(v_i,v'_j,v_{-ij})=e^i$. Hence, $x \succ y$.

Proof of (3). At any valuation profile $(v_1,\ldots ,v_n)$, if $f(v_1,\ldots ,v_n)=e^i$, then, by definition, $\mathbf {1}_{v_i} \succ \mathbf {1}_{v_j}$ for all $j \ne i$.

Step 4. We show that $\succ$ is transitive. Suppose for some $i \in N$, $\mathbf {1}_{v_i+\epsilon } \succ \mathbf {1}_{v_i}$ for some $\epsilon >0$ such that $v_i+\epsilon \in V_i$. Also, for some $j \ne i$, $\mathbf {1}_{v_i} \succ \mathbf {1}_{v_j}$. Then, by definition, for some $v_{-ij}$, $f(v_i,v_j,v_{-ij})=e^i$. By monotonicity, $f(v_i+\epsilon ,v_j,v_{-ij})=e^i$. Hence, $\mathbf {1}_{v_i+\epsilon } \succ \mathbf {1}_{v_j}$.

We also know that for some $i \in N$ and for some $\epsilon >0, \delta > 0$, if $\mathbf {1}_{v_i+\epsilon +\delta } \succ \mathbf {1}_{v_i+\epsilon }$ and $\mathbf {1}_{v_i+\epsilon } \succ \mathbf {1}_{v_i}$, then $\mathbf {1}_{v_i+\epsilon +\delta } \succ \mathbf {1}_{v_i}$.

Finally, pick $v_i \in V_i, v_j \in V_j$ and $v_k \in V_k$ such that $\mathbf {1}_{v_i} \succ \mathbf {1}_{v_j}$ and $\mathbf {1}_{v_j} \succ \mathbf {1}_{v_k}$, where $i,j,k$ are distinct. This means, $f(v_i,v_j,v'_{-ij})=e^i$ for some $v'_{-ij}$. By monotonicity and non-bossiness, $f(v_i,v_j,v_k,v'_{-ijk}) \in \{e^i,e^k\}$. But, $\mathbf {1}_{v_j} \succ \mathbf {1}_{v_k}$ implies that $f(v_i,v_j,v_k,v'_{-ijk}) \ne e^k$. Hence, $f(v_i,v_j,v_k,v'_{-ijk})=e^i$. Hence, $\mathbf {1}_{v_i} \succ \mathbf {1}_{v_k}$. This shows that $\succ$ is transitive.

Step 5. We show that $f$ is strongly rationalizable. Since $\succ$ is an anti-symmetric, irreflexive and transitive binary relation on $D \times D$, we can extend it to an anti-symmetric, irreflexive, complete, and transitive binary relation $\succ '$ on $D \times D$ due to Szpilrajn’s extension theorem: see Fishburn (1970) for instance. By definition of $\succ '$ and Step 3, at any valuation profile $(v_1,\ldots ,v_n)$, if $f(v_1,\ldots ,v_n)=e^i$, then, $\mathbf {1}_{v_i} \succ ' \mathbf {1}_{v_j}$ for all $j \ne i$. By definition, $\succ '$ is monotone. Hence, $f$ is strongly rationalizable.

Proof of Theorem 2.

By Lemmas 3 and 4, an SUM allocation rule with order-based tie-breaking is implementable and non-bossy. We show that every implementable and non-bossy allocation rule satisfying Condition $\mathcal {C}^*$ is an SUM allocation rule with order-based tie-breaking. We do the proof in various steps. Throughout we assume that $V_i=(0,\beta _i)$, where $\beta _i \in \mathbb {R}_{++} \cup \{\infty \}$, for all $i \in N$.

Step 1. In this step, we show that if $f$ is implementable and non-bossy allocation rule satisfying Condition $\mathcal {C}^*$, then there is an ordering $\succeq ^f$ on $D$ which rationalizes $f$. We construct this specific $\succeq ^f$ in this step. ³

Suppose $f$ is an implementable and non-bossy allocation rule satisfying Condition $\mathcal {C}^*$. We first define the notion of a winning set. The winning set of allocation rule $f$ at a valuation profile $v$ is denoted as $W^f(v)$, and defined as follows. For any $i \in N$, we say $e^i \in W^f(v)$ if for all $\epsilon > 0$, we have $f(v_i + \epsilon ,v_{-i})=e^i$, where $(v_i + \epsilon ) \in V_i$. We say that $e^0 \in W^f(v)$ if for all $\epsilon > 0$, we have $f(\{v_j - \epsilon \}_{j \in N})=e^0$, where $(v_j - \epsilon ) \in V_j$ for all $j \in N$. The first claim is that $W^f(v)$ is non-empty for all valuation profiles $v$.

Lemma 5

If $f$ is implementable and non-bossy, then for every value profile $v$, $f(v) \in W^f(v)$.

Proof

Consider an implementable and non-bossy allocation rule $f$ and a valuation profile $v$. If $f(v)=e^j \ne e^0$, then by monotonicity $f(v_j + \epsilon ,v_{-j})=e^j$ for all $\epsilon > 0$. Hence, $f(v) \in W^f(v)$.

If $f(v)=e^0$, then consider any $\epsilon > 0$ and a valuation profile $v'$ such that $v'_i - \epsilon > 0$ for all $i \in N$. We argue that $f(v')=e^0$, and hence, $e^0 = f(v) \in W^f(v)$. Assume for contradiction that $f(v') = e^j \ne e^0$. Now, we go from $v'$ to $v$ by increasing the valuation of one agent at a time. By monotonicity, $f(v_j,v'_{-j})=e^j$. Now, pick any $k \in N {\setminus } \{j\}$. Then, either $f(v_j,v_k,v'_{-jk})=e^k$ or by non-bossiness $f(v_j,v_k,v'_{-jk})=e^j$. In both cases, we see that $f(v_j,v_k,v'_{-jk}) \ne e^0$. Continuing in this manner, we will reach the valuation profile $v$ and get that $f(v) \ne e^0$, a contradiction. $\square$

Step 1.1. In this step, we show that an implementable and non-bossy allocation rule satisfying Condition $\mathcal {C}^*$ satisfies a form of independence property.

Definition 9

An allocation rule $f$ satisfies binary independence if for any pair of alternatives $e^j,e^k \in A$ and any pair of valuation profiles $v,v'$ such that $\mathbf {1}_{v_j}=\mathbf {1}_{v'_j}$ and $\mathbf {1}_{v_k}=\mathbf {1}_{v'_k}$, the following conditions hold: (1) if $e^k \in W^f(v)$ and $e^j \in W^f(v')$, then $e^k \in W^f(v')$ and (2) if $e^j \in W^f(v)$ and $e^k \notin W^f(v)$, then $e^k \notin W^f(v')$.

Intuitively, the binary independence property says that the comparison of any pair of utility vectors is independent of what the other utility vectors are.

Proposition 1

An implementable and non-bossy allocation rule satisfying Condition $\mathcal {C}^*$ satisfies binary independence.

Proof

We will use the following lemma to prove the proposition. $\square$

Lemma 6

Suppose $v$ and $v'$ are two distinct valuation profiles such that $v_i \ge v'_i$ for all $i \in N$. Let $B(v,v')=\{e^i \in A: v_i > v'_i\}$. If $f$ is an implementable and non-bossy allocation rule, then $W^f(v) {\setminus } B(v,v') \subseteq W^f(v')$.

Proof

Let $f$ be an implementable and non-bossy allocation rule and $v$ and $v'$ be two distinct valuation profiles with $v_i \ge v'_i$ for all $i \in N$. We will go from $v$ to $v'$ by lowering one agent’s value at a time. Pick any $e^j \in B(v,v')$. Consider a new type profile $v''$ such that the value of every agent $i \ne j$ remains $v_i$ and the value of agent $j$ is $v'_j$, which is strictly less than $v_j$. Pick any $e^k \in W^f(v)$ such that $e^k \ne e^j$. Then, we consider two cases.

Case 1: $e^k \ne e^0$. We argue that $e^k \in W^f(v'')$. Assume for contradiction that $e^k \notin W^f(v'')$. Then, for some $\epsilon > 0$, we have $f(v_k + \epsilon , v'_j,v_{-kj}) \ne e^k$. If $f(v_k+\epsilon , v'_j,v_{-kj}) = e^j$, then by monotonicity, we have $f(v_k+\epsilon ,v_j,v_{-kj})=e^j$. This is a contradiction since $e^k \in W^f(v)$. If $f(v_k+\epsilon ,v'_j,v_{-kj}) = e^l \notin \{e^j,e^k\}$, then monotonicity and non-bossiness implies that $f(v_k+\epsilon ,v_j,v_{-kj}) \in \{e^l,e^j\}$. But this contradicts $e^k \in W^f(v)$.

Case 2: $e^k = e^0$. Since $e^0 \in W^f(v)$, for any $\epsilon > 0$ such that $\bar{v}_i:=v_i - \epsilon > 0$ for all $i \in N$, we have $f(\bar{v}_1,\ldots ,\bar{v}_n)=e^0$. Note that $v'_i - \epsilon = v_i - \epsilon = \bar{v}_i$ for all $i \ne j$ for any $\epsilon$. Now, fix any $\epsilon > 0$ such that $v'_j - \epsilon > 0$. Consider the valuation profile $(\bar{v}_{-j},v'_j - \epsilon )$. Since $f(\bar{v}_1,\ldots ,\bar{v}_n)=e^0$ and $\bar{v}_j = v_j - \epsilon > v'_j - \epsilon$, by monotonicity and non-bossiness, we have $f(v'_j - \epsilon ,\bar{v}_{-j})=e^0$. Hence, $e^0 \in W^f(v'')$.

This establishes that $e^k \in W^f(v'')$ for any $e^k \ne e^j$. Hence, $W^f(v) {\setminus } \{e^j\} \subseteq W^f(v'')$. Repeating this argument for other elements of $B(v,v')$ one by one, we conclude that $W^f(v) {\setminus } B(v,v') \subseteq W^f(v')$. $\square$

Now, let $f$ be an implementable and non-bossy allocation rule satisfying Condition $\mathcal {C}^*$. Pick any pair of alternatives $e^j,e^k \in A$ and any pair of valuation profiles $v,v'$ such that $\mathbf {1}_{v_j}=\mathbf {1}_{v'_j}$ and $\mathbf {1}_{v_k}=\mathbf {1}_{v'_k}$. We will show that $f$ satisfies both (1) and (2) of Definition 9.

Property 1

Suppose $e^k \in W^f(v)$ and $e^j \in W^f(v')$. We will show that $e^k \in W^f(v')$. Construct a new type profile $v''$ such that $v''_i=\min (v_i,v'_i)$ for all $i \in N$. Note that $\mathbf {1}_{v''_j}=\mathbf {1}_{v_j}=\mathbf {1}_{v'_j}$ and $\mathbf {1}_{v''_k}=\mathbf {1}_{v_k}=\mathbf {1}_{v'_k}$. By Lemma 6, $e^j,e^k \in W^f(v'')$. Now, assume for contradiction that $e^k \notin W^f(v')$. We now consider various cases.

Case 1: $e^j,e^k \in A {\setminus } \{e^0\}$. Since $e^k \notin W^f(v')$, there exists $\epsilon > 0$ such that $f(v'_k+\epsilon ,v'_{-k}) \ne e^k$. By monotonicity and non-bossiness, for all $\epsilon ' > 0$ we have $f(v'_j+\epsilon ', v'_k+\epsilon ,v'_{-jk}) \ne e^k$. Further, we show that $f(v'_j+\epsilon ',v'_k+\epsilon ,v'_{-jk}) = e^j$ for all $\epsilon ' > 0$. To see this, suppose $f(v'_j+\epsilon ',v'_k + \epsilon ,v'_{-jk}) = e^l$ for some $e^l \notin \{e^j,e^k\}$. Then, by monotonicity and non-bossiness, we get $f(v'_j+\epsilon ',v'_k,v'_{-jk})=e^l$, and this contradicts $e^j \in W^f(v')$. Hence, $f(v'_j+\epsilon ',v'_k+\epsilon ,v'_{-jk}) = e^j$ for all $\epsilon ' > 0$. Now, applying monotonicity and non-bossiness again, for all $\epsilon ' > 0$, we have $f(v'_j+\epsilon ',v'_k+\epsilon ,v''_{-jk}) = e^j$. Since $e^k \in W^f(v'')$, we have $f(v'_j,v'_k+\frac{\epsilon }{2},v''_{-jk})=e^k$. By Condition $\mathcal {C}^*$, there is an $\epsilon ' > 0$ such that $f(v'_j+\epsilon ',v'_k+\epsilon ,v''_{-jk})=e^k$. This is a contradiction.

Case 2: $e^j=e^0$. We have to show that $e^0 \in W^f(v')$ implies $e^k \in W^f(v')$. Assume for contradiction that $e^k \notin W^f(v')$ but $e^0 \in W^f(v')$. For this, we first show that there is some $\epsilon _i > 0$ for every $i \in N$ such that $f(v'_k+\epsilon _k,\{v'_i-\epsilon _i\}_{i \ne k})=e^0$.

To see this, suppose $f(v'_k+\epsilon _k,\{v'_i-\epsilon _i\}_{i \ne k})=e^k$ for all $\{\epsilon _i\}_{i \in N}$. Fix any $l \ne k$. Then, by Condition $\mathcal {C}^*$, for every $\epsilon$ there is a $\delta$ such that, $f(v'_k + \epsilon _k+\epsilon , (v'_l - \epsilon _l + \delta ),\{v'_i - \epsilon _i\}_{i \ne k,l})=e^k$ for all $\{\epsilon _i\}_{i \in N}$. Fix some $\epsilon > 0$. By, Condition $\mathcal {C}^*$, we can choose $\epsilon _l=\delta$. Also, let $\epsilon _k=\epsilon$. Hence, we get $f(v'_k+2\epsilon ,v'_l,\{v'_i-\epsilon _i\}_{i \ne k,l})=e^k$. Repeating this, we reach $f(v'_k+(n-1)\epsilon ,v'_{-k})=e^k$. Since $n > 1$, we get that $e^k \in W^f(v')$. But this contradicts the fact that $e^k \notin W^f(v')$.

Similarly, suppose $f(v'_k+\epsilon _k,\{v'_i-\epsilon _i\}_{i \ne k})=e^l$ for some $l \ne 0,k$. Then, by monotonicity and non-bossiness, we get that $f(\{v'_i-\epsilon _i\}_{i \in N})=e^l$. This means $f(\{v'_i-\epsilon _i\}_{i \in N}) \ne e^0$. Now, choose $\epsilon ' < \min _{i \in N}\epsilon _i$. Then, consider the profile $\{v'_i - \epsilon '\}_{i \in N}$. By repeated application of monotonicity and non-bossiness, $f(\{v'_i-\epsilon '\}_{i \in N}) \ne e^0$. This contradicts $e^0 \in W^f(v')$.

This shows that there is some $\epsilon _i > 0$ for all $i \in N$ such that $f(v'_k+\epsilon _k,\{v'_i-\epsilon _i\}_{i \ne k})=e^0$. By monotonicity and non-bossiness, $f(v'_k+\epsilon _k,\{v''_i - \epsilon _i\}_{i \ne k})=e^0$. But $e^k \in W^f(v'')$ implies that $f(v''_k + \epsilon _k,v''_{-k})=e^k$ (to remind, $v'_k=v''_k$). But monotonicity and non-bossiness implies that $f(v'_k + \epsilon _k,\{v''_i - \epsilon _i\}_{i \ne k})=e^k$. This gives us a contradiction.

Case 3: $e^k=e^0$. We have to show that if $e^j \in W^f(v')$ then $e^0 \in W^f(v')$. Assume for contradiction $e^0 \notin W^f(v')$. We first show that for some $\epsilon > 0$ and $\epsilon ' > 0$, $f(v'_j - \epsilon ,\{v'_i - \epsilon '\}_{i \ne j})=e^j$.

To see this, suppose that $f(v'_j - \epsilon ,\{v'_i - \epsilon '\}_{i \ne j})=e^0$ for all $\epsilon , \epsilon '$. Then, by monotonicity and non-bossiness, we see that $f(\{v'_i - \min (\epsilon ,\epsilon ')\}_{i \in N})=e^0$ for all $\epsilon ,\epsilon '$. But this contradicts $e^0 \notin W^f(v')$.

Similarly, suppose that $f(v'_j - \epsilon ,\{v'_i - \epsilon '\}_{i \ne j})=e^l$ for some $l \in N {\setminus } \{j\}$ and for all $\epsilon , \epsilon '$. By Condition $\mathcal {C}^*$, there is some $\delta :=\delta _{\epsilon ',v'_{-lj}} < \epsilon '$ such that $f(v'_j - \epsilon + \delta , v'_l, \{v'_i - \epsilon '\}_{i \ne j,l})=e^l$ for all $\epsilon ,\epsilon '$. Since $\delta$ is independent of $\epsilon$, we can choose $\epsilon = \frac{\delta }{2}$ for every $\epsilon '$. Hence, we have $f(v'_j + \frac{\delta }{2},v'_l,\{v'_i - \epsilon '\}_{i \ne j,l})=e^l$ for every $\epsilon '$. Further, since $e^j \in W^f(v')$, we know that $f(v'_j + \frac{\delta }{2}, v'_{-j})=e^j$ for all $\epsilon '$. By repeatedly applying monotonicity and non-bossiness, we get that $f(v'_j + \frac{\delta }{2},v'_l,\{v'_i - \epsilon '\}_{i \ne j,l})=e^j$ for every $\epsilon '$. This gives us a contradiction.

This shows that $f(v'_j - \epsilon ,\{v'_i - \epsilon '\}_{i \ne j})=e^j$ for some $\epsilon > 0$ and $\epsilon ' > 0$. By repeatedly applying monotonicity and non-bossiness, we get that $f(v'_j - \epsilon ,\{v''_i - \epsilon '\}_{i \ne j})=e^j$ for some $\epsilon > 0$ and $\epsilon ' > 0$. Since $e^0 \in W^f(v'')$, we know that $f(\{v'_i - \min (\epsilon ,\epsilon ')\}_{i \in N})=e^0$. By repeatedly applying monotonicity and non-bossiness, we get that $f(v'_j - \epsilon ,\{v''_i - \epsilon '\}_{i \ne j})=e^0$. This is a contradiction.

This concludes the proof of Property (1) in Definition 9.

Property 2

This follows by applying Property (1). To see this, pick any $e^j, e^k \in A$ and $v,v'$ as in Definition 9. Suppose $e^j \in W^f(v)$ but $e^k \notin W^f(v')$. We need to show that $e^k \notin W^f(v')$. Assume for contradiction $e^k \in W^f(v')$. Then, by changing the role of $v$ and $v'$ in (1), we get that $e^k \in W^f(v)$, which is a contradiction.

Step 1.2. In this step, we define two binary relations on the set of utility vectors $D$. For any $i \in N$ and for any $v_i,v'_i \in V_i$ with $v_i > v'_i$, we define $\mathbf {1}_{v_i} \succ ^f \mathbf {1}_{v'_i}$. Further, for every $i \in N$ and every $v_i \in V_i$, we define $\mathbf {1}_{v_i} \sim ^f \mathbf {1}_{v_i}$ (reflexive). For any $i,j \in N \cup \{0\}$ (with $i \ne j$) and any $v_i \in V_i$ and $v_j \in V_j$, we define $\mathbf {1}_{v_i} \succ ^f\mathbf {1}_{v_j}$, if there exists $v'$ such that $\mathbf {1}_{v'_i}=\mathbf {1}_{v_i}$, $\mathbf {1}_{v'_j}=\mathbf {1}_{v_j}$, and $e^i \in W^f(v')$ but $e^j \notin W^f(v')$; and $\mathbf {1}_{v_i} \sim ^f \mathbf {1}_{v_j}$, if (a) there exists a valuation profile $v'$ such that $\mathbf {1}_{v'_i}=\mathbf {1}_{v_i}$, $\mathbf {1}_{v'_j}=\mathbf {1}_{v_j}$, and $e^i,e^j \in W^f(v')$ or (b) at every valuation profile $v'$ such that $\mathbf {1}_{v'_i}=\mathbf {1}_{v_i}$, and $\mathbf {1}_{v'_j}=\mathbf {1}_{v_j}$, we have $e^i,e^j \notin W^f(v')$.

Notice that $\sim ^f$ is a symmetric and reflexive binary relation. Further, $\succ ^f$ is anti-symmetric. To see this, fix some $x,y \in D$. If $x,y \in D_i$ for some $i \in N$, and $x=\mathbf {1}_{v_i}$ and $y=\mathbf {1}_{v'_i}$ with $v_i > v'_i$ then, by definition, $x \succ ^f y$. If $x \in D_i$ and $y \in D_j$ for some $i \ne j$, and there is a valuation profile $v$ with $\mathbf {1}_{v_i}=x$ and $\mathbf {1}_{v_j}=y$. Suppose $e^i \in W^f(v)$ but $e^j \notin W^f(v)$. Now, consider any other valuation profile $v'$ such that $\mathbf {1}_{v_i}=\mathbf {1}_{v'_i}=x$ and $\mathbf {1}_{v_j}=\mathbf {1}_{v'_j}=y$. By Proposition 1, $e^j \notin W^f(v')$. Hence, $\succ ^f$ is anti-symmetric.

Finally, we show that the relations $\succ ^f$ and $\sim ^f$ are disjoint. To see this, consider the case where $x \in D_i$ and $y \in D_j$ for some $i \ne j$, and there is a valuation profile $v$ with $\mathbf {1}_{v_i}=x$ and $\mathbf {1}_{v_j}=y$. Suppose $e^i, e^j \in W^f(v)$. Now, consider any other valuation profile $v'$ such that $\mathbf {1}_{v_i}=\mathbf {1}_{v'_i}=x$ and $\mathbf {1}_{v_j}=\mathbf {1}_{v'_j}=y$. By Proposition 1, $e^i \in W^f(v')$ if and only if $e^j \in W^f(v')$. Hence, $x \nsucc ^f y$ and $y \nsucc ^f x$.

Step 1.3. We define $\succeq ^f$ to be the union of the two binary relations $\succ ^f$ and $\sim ^f$. Notice that $\succeq ^f$ is a complete binary relation with symmetric part being $\sim ^f$ and anti-symmetric part being $\succ ^f$. In this step, we show that $\succeq ^f$ is transitive. For this, we will show that $\succ ^f$ and $\sim ^f$ are transitive, and this in turn will imply that $\succeq ^f$ is transitive. Pick any $x,y,z \in D$ such that $x \ne y \ne z$. We consider three cases.

Case 1. Suppose $x,y,z \in D_i$ for some $i \in N$ and $x=\mathbf {1}_{v_i}, y=\mathbf {1}_{v'_i}, z=\mathbf {1}_{v''_i}$. Suppose $x \succ ^f y$ and $y \succ ^f z$. Then, it must be $v_i > v'_i > v''_i$. By definition, we have $x \succ ^f z$.

Case 2. $x,y \in D_i$ but $z \in D_j$ for some $i,j$ where $i \ne j$. Suppose $x=\mathbf {1}_{v_i}, y=\mathbf {1}_{v'_i}$, and $z=\mathbf {1}_{v_j}$. Suppose $x \succ ^f y$ and $y \succ ^f z$. Note that $x \succ ^f y$ implies $v_i > v'_i$. We consider two subcases.

Case 2a. Suppose $j \ne 0$. Since $y \succ ^f z$, there is a valuation profile $v''$ such that $v''_i=v'_i$, $v''_j=v_j$, and $e^i \in W^f(v'')$ but $e^j \notin W^f(v'')$. Now consider the type profile $\bar{v}$, where $\bar{v}_k=v''_k$ if $k \ne i$ and $\bar{v}_i=v_i$. We show that $e^i \in W^f(\bar{v})$ and $e^j \notin W^f(\bar{v})$, and this will show that $x \succ ^f z$. Since $e^i \in W^f(v'')$, we know that $f(v'_i + \epsilon ,v_j,v''_{-ij})=e^i$ for all $\epsilon > 0$. By monotonicity, $f(v_i + \epsilon ,v_j,v''_{-ij})=e^i$ for all $\epsilon > 0$. Hence, $e^i \in W^f(\bar{v})$. Since $e^j \notin W^f(v'')$, there is some $\epsilon > 0$ such that $f(v'_i,v_j + \epsilon ,v''_{-ij}) \ne e^j$. By monotonicity and non-bossiness, $f(v_i,v_j + \epsilon ,v''_{-ij}) \ne e^j$. Hence, $e^j \notin W^f(\bar{v})$.

Case 2b. Suppose $j=0$. So, $z$ is the $n$-dimensional zero vector. Since $y \succ ^f z$, there is a valuation profile $\bar{v}$ with $\mathbf {1}_{\bar{v}_i}=\mathbf {1}_{v'_i}=y$ and $e^i \in W^f(\bar{v})$ but $e^0 \notin W^f(\bar{v})$. Now, consider the valuation profile $v'' \equiv (v_i,\bar{v}_{-i})$. Since $v_i > v'_i$, by monotonicity, we have $e^i \in W^f(v'')$.

Since $e^0 \notin W^f(\bar{v})$, there is some $\epsilon > 0$ such that $f(\{\bar{v}_k - \epsilon \}_{k \in N}) \ne e^0$. Now, since $v_i > v'_i$, by monotonicity and non-bossiness, $f(v_i - \epsilon ,\{\bar{v}_k - \epsilon \}_{k \ne i}) \ne e^0$. Hence, $e^0 \notin W^f(v'')$.

Case 3. $x \in D_i$, $y \in D_j$, $z \in D_k$, where $i,j,k$ are distinct. Suppose $x=\mathbf {1}_{v_i}, y = \mathbf {1}_{v_j}$, and $z=\mathbf {1}_{v_k}$. Here, we will consider transitivity of both $\succ ^f$ and $\sim ^f$.

Case 3a: Transitivity of $\succ ^f$. Suppose $x \succ ^f y$ and $y \succ ^f z$. Since $x \succ ^f y$, there is some valuation profile $v''$ where $\mathbf {1}_{v''_i}=x,\mathbf {1}_{v''_j}=y$, and $e^i \in W^f(v'')$ but $e^j \notin W^f(v'')$.

First, note that $i \ne 0$. To see this, since $y \succ ^f z$ there is a valuation profile $v'$ where $\mathbf {1}_{v'_j}=y, \mathbf {1}_{v'_k}=z$, and $e^j \in W^f(v')$ but $e^k \notin W^f(v')$. But $\mathbf {1}_{v'_i}=x$ implies that $y \succeq ^f x$, which contradicts $x \succ ^f y$. Hence, $i \ne 0$.

Suppose $v''_k < v_k$. Since $e^i \in W^f(v'')$, for every $\epsilon > 0$, $f(v''_i + \epsilon ,v''_j,v''_k,v''_{-ijk})=e^i$. By monotonicity and non-bossiness, $f(v''_i + \epsilon ,v''_j,v_k,v''_{-ijk}) \in \{e^i,e^k\}$ for every $\epsilon > 0$. But $f(v''_i + \epsilon ,v''_j,v_k,v''_{-ijk})=e^k$ for any $\epsilon > 0$ will imply that $z \succeq ^f y$, and this will contradict $y \succ ^f z$. Hence, $f(v''_i + \epsilon ,v''_j,v_k,v''_{-ijk}) = e^i$ for every $\epsilon > 0$. So, $e^i \in W^f(v''_i,v''_j,v_k,v''_{-ijk})$. Since $y \succ ^f z$, $e^k \notin W^f(v''_i,v''_j,v_k,v''_{-ijk})$. Hence, $x \succ ^f z$.

Suppose $v''_k \ge v_k$. As before, since $e^i \in W^f(v'')$, for every $\epsilon > 0$, $f(v''_i + \epsilon ,v''_j,v''_k,v''_{-ijk})=e^i$. By monotonicity and non-bossiness, $f(v''_i+\epsilon ,v''_j,v_k,v''_{-ijk})=e^i$ for every $\epsilon > 0$. Hence, $e^i \in W^f(v''_i,v''_j,v_k,v''_{-ijk})$. Since $y \succ ^f z$, $e^k \notin W^f(v''_i,v''_j,v_k,v''_{-ijk})$. Hence, $x \succ ^f z$.

Case 3b: Transitivity of   $\sim ^f$. Suppose $x \sim ^f y$ and $y \sim ^f z$. Suppose for every valuation profile $v'$ such that $\mathbf {1}_{v'_i}=x$ and $\mathbf {1}_{v'_j}=y$, we have $e^i,e^j \notin W^f(v')$. Further, suppose for every valuation profile $\bar{v}$ with $\mathbf {1}_{\bar{v}_j}=y$ and $\mathbf {1}_{\bar{v}_k}=z$, we have $e^j,e^k \notin W^f(\bar{v})$. Consider any valuation profile $v''$ such that $\mathbf {1}_{v''_i}=x$ and $\mathbf {1}_{v''_k}=z$. Assume for contradiction $e^i \in W^f(v'')$. Consider the valuation profile $\hat{v}$ such that $\mathbf {1}_{\hat{v}_j} = y$ and $\hat{v}_l=v''_l$ for all $l \ne j$. Since $\mathbf {1}_{\hat{v}_k}=z$, by definition $e^j,e^k \notin W^f(\hat{v})$. By monotonicity and non-bossiness, $e^i \in W^f(\hat{v})$. But, this is not possible since $\mathbf {1}_{\hat{v}_i}=x$ implies that $e^i,e^j \notin W^f(\hat{v})$. This means that at every valuation profile $v''$ with $\mathbf {1}_{v''_i}=x$ and $\mathbf {1}_{v''_k}=z$ we must have $e^i,e^k \notin W^f(v'')$. Hence, $x \sim ^f z$.

Now, consider the case where $y \sim ^f z$ and there is some valuation profile $v'$ such that $\mathbf {1}_{v'_j}=y$, $\mathbf {1}_{v'_k}=z$, and $e^j,e^k \in W^f(v')$. If $x=\mathbf {1}_{v_0}$, then by Proposition 1, $e^i \in W^f(v')$, and this immediately implies that $x \sim ^f z$. Suppose $x=\mathbf {1}_{v_i}$ and $i \ne 0$. Then, either $j \ne 0$ or $k \ne 0$. We consider the case of $j \ne 0$—the proof for $k \ne 0$ is similar. Since $e^j \in W^f(v')$, $f(v'_j+\epsilon ,v'_{-j})=e^j$ for all $\epsilon > 0$. By monotonicity and non-bossiness, $f(v'_j+\epsilon ,v_i,v'_{-ij}) \in \{e^i,e^j\}$ for all $\epsilon > 0$. If $f(v'_j+\epsilon ,v_i,v'_{-ij})=e^i$, then by monotonicity and non-bossiness, $e^i \in W^f(v'_j,v_i,v'_{-ij})$. Since, $x \succ ^f y$ and $y \succ ^f z$, by repeated application of Proposition 1, we get that $e^j,e^k \in W^f(v'_j,v_i,v'_{-ij})$. This implies that $x \succ ^f z$. Similarly, if $f(v'_j+\epsilon ,v_i,v'_{-ij})=e^j$, then $e^j \in W^f(v'_j,v_i,v'_{-ij})$. Again, using the fact that $x \succ ^f y$ and $y \succ ^f z$, by repeated application of Proposition 1, we get that $e^i,e^k \in W^f(v'_j,v_i,v'_{-ij})$. So, $x \succ ^f z$.

Step 1.4. We conclude Step 1 by showing that $f$ is a rationalizable allocation rule and $\succeq ^f$ rationalizes $f$. Note that the ordering $\succeq ^f$, defined in Steps 1.2 and 1.3, is a monotone ordering. By Lemma 5, for every valuation profile $v$, $f(v) \in W^f(v)$. Hence, by definition of $\succeq ^f$, $G^f(v) \succeq ^f \mathbf {1}_{v_i}$ for all $i \in N \cup \{0\}$. This shows that $f$ is a rationalizable allocation rule and $\succeq ^f$ rationalizes $f$.

Step 2. In this step, we show that if $f$ is a non-bossy allocation rule satisfying Condition $\mathcal {C}^*$, then it is implementable if and only if it is an SUM allocation rule. By Lemma 3, an SUM allocation rule is implementable. Suppose $f$ is an implementable and non-bossy allocation rule satisfying Condition $\mathcal {C}^*$. By Step 1, $f$ can be rationalized by the monotone ordering $\succeq ^f$, defined as in Step 1.2. We say that $\succeq ^f$ has a utility representation if there exists a utility function $U:D \rightarrow \mathbb {R}$ such that for all $x,y \in D$ we have $U(x) > U(y)$ if and only if $x \succ ^f y$.

Step 2.1. In this step, we will show that $\succeq ^f$ is separable in the sense of Definition 5. Let $Z:=\{x \in D: x = \mathbf {1}_{v_i}~\mathrm for some ~i \in N \cup \{0\}~\mathrm and ~v_i~\mathrm is rational \}$. Note that since the set of rational numbers is countable, $Z$ is a countable subset of $D$. Now, pick $x,y \in D$ such that $x \succ ^f y$. If $x,y \in D_i$ for some $i \in N$, then let $x=\mathbf {1}_{v_i}$ and $y=\mathbf {1}_{v'_i}$. By definition, $v_i > v'_i$. Then, we can find a rational $v''_i$ such that $v_i > v''_i > v'_i$ (this is because the set of rational numbers is a dense set). Let $z = \mathbf {1}_{v''_i}$. By definition, $z \in Z$ and $x \succ ^f z \succ ^f y$. Now, assume that $x=\mathbf {1}_{v_i}$ and $y= \mathbf {1}_{v_j}$ for some $i,j \in N \cup \{0\}$ with $i \ne j$. We consider various cases.

Case A. Suppose $i \ne 0$ and $j \ne 0$. Since $x \succ ^f y$, there is a valuation profile $v \equiv (v_i,v_j,v_{-ij})$ such that $e^i \in W^f(v)$ but $e^j \notin W^f(v)$. Since $e^j \notin W^f(v)$, there is some $\epsilon > 0$ such that $f(v_i,v_j + \epsilon , v_{-ij}) \ne e^j$. This means that $e^j \notin W^f(v_i,v_j + \frac{\epsilon }{2},v_{-ij})$. Consider any $\delta > 0$. Since $f(v_i,v_j + \frac{\epsilon }{2},v_{-ij}) \ne e^j$, by monotonicity and non-bossiness, $f(v_i + \delta ,v_j+\frac{\epsilon }{2},v_{-ij}) \ne e^j$. Since $e^i \in W^f(v)$, $f(v_i+\delta ,v_j,v_{-ij})=e^i$. By monotonicity and non-bossiness, $f(v_i + \delta ,v_j+\frac{\epsilon }{2},v_{-ij}) \in \{e^i,e^j\}$. This implies that $f(v_i + \delta ,v_j+\frac{\epsilon }{2},v_{-ij}) = e^i$. Hence, $e^i \in W^f(v_i,v_j + \frac{\epsilon }{2},v_{-ij})$. Then, $x=\mathbf {1}_{v_i} \succ \mathbf {1}_{v_j + \frac{\epsilon }{2}} \succ \mathbf {1}_{v_j}=y$. Since the set of rational numbers is dense, we can find a $z \in Z$ arbitrarily close to $\mathbf {1}_{v_j + \frac{\epsilon }{2}}$ such that $x \succ ^f z \succ ^f y$.

Case B. Suppose $i \ne 0$ and $j=0$. Since $x \succ ^f y$, there is a valuation profile $(v_i,v_{-i})$ such that $e^i \in W^f(v_i,v_{-i})$ but $e^0 \notin W^f(v_i,v_{-i})$. This means for some $\delta > 0$, we have $f(\{v_j - \delta \}_{j \in N}) \ne e^0$. Suppose $f(\{v_j - \delta \}_{j \in N}) = e^k$ for some $k \ne 0$. Then, $\mathbf {1}_{v_k - \delta } \succeq ^f y$. Since $e^i \in W^f(v_i,v_{-i})$, we get that $x=\mathbf {1}_{v_i} \succeq ^f \mathbf {1}_{v_k} \succ ^f \mathbf {1}_{v_k-\delta }$. Hence, $x \succ ^f \mathbf {1}_{v_k-\delta } \succeq ^f y$. Since the set of rational numbers is dense, we can choose a $z \in Z$ arbitrarily close to $\mathbf {1}_{v_k - \delta }$ such that $x \succ ^f z \succeq ^f y$.

Case C. Suppose $i=0$ and $j \ne 0$. Since $x \succ ^f y$, there is a valuation profile $(v_j,v_{-j})$ such that $e^j \notin W^f(v_j,v_{-j})$ but $e^0 \in W^f(v_j,v_{-j})$. Then, for some $\epsilon > 0$, we have $f(v_j+\epsilon ,v_{-j}) = e^k$, where $k \ne j$. This implies that $\mathbf {1}_{v_k} \succeq ^f \mathbf {1}_{v_j +\epsilon } \succ ^f \mathbf {1}_{v_j}=y$. But $e^0 \in W^f(v_j,v_{-j})$ implies that $x \succeq ^f \mathbf {1}_{v_k}$. Hence, $x \succeq ^f \mathbf {1}_{v_j+\epsilon } \succ ^f y$. Since the set of rational numbers is dense, we can find $z \in Z$ arbitrarily close to $\mathbf {1}_{v_j + \epsilon }$ such that $x \succeq ^f z \succ ^f y$.

This shows that $\succeq ^f$ is separable. Hence, $\succeq ^f$ has a utility representation. Let $U: D \rightarrow \mathbb {R}$ be a utility function representing $\succeq ^f$. Without loss of generality, we can assume $U(\mathbf {1}_{v_0})=0$. Now, for every $i \in N \cup \{0\}$, define $U_i: V_i \rightarrow \mathbb {R}$ as follows: $U_i(v_i)=U(\mathbf {1}_{v_i})$ for all $v_i \in V_i$. Note that by the definition of $\succeq ^f$, each $U_i$ is well defined and increasing.

Since $U$ represents $\succeq ^f$ and $f$ is a rationalizable allocation rule with $\succeq ^f$ being the corresponding ordering, we get that for all valuation profiles $v$, $f(v) \in \arg \max _{i \in N \cup \{0\}}U_i(v_i)$. Hence, $f$ is an SUM allocation rule.

By Theorem 1, $f$ is a strongly rationalizable allocation rule. Let $\succ$ be the strict linear ordering that strongly rationalizes $f$. By definition, for all $x \in D^f$ and for all $y \notin D^f$, $x \succ y$. Further, for all $v \in V$ if $f(v)=e^j$, then $\mathbf {1}_{v_j} \succ \mathbf {1}_{v_i}$ for all $i \ne j$. In that case, $\mathbf {1}_{v_j} \succ \mathbf {1}_{v_k}$ for all $k \ne j$ and $k \in \arg \max _{i \in N \cup \{0\}}U_i(v_i)$. Hence, $f$ is an SUM allocation rule with order-based tie-breaking.