Mechanism design with two alternatives in quasi-linear environments

Abstract

We study mechanism design in quasi-linear private values environments when there are two alternatives. We show that under a mild range condition, every implementable allocation rule is a generalized utility function maximizer. In unbounded domains, if we replace our range condition by an independence condition, then every implementable allocation rule is an affine maximizer. Our results extend Roberts’ affine maximizer theorem (Roberts, In: Laffont J-J (ed) The characterization of implementable choice rules, 1979) to the case of two alternatives.

1 Introduction

This paper considers dominant strategy implementation of deterministic (no randomization) allocation rules in quasi-linear environments with two alternatives, e.g. bilateral trading, provision of a public good, choosing one out of two locations for locating a facility or any situation with a status-quo alternative and a new alternative. The private information of each agent is a two dimensional vector, representing the valuation (a real number) for each alternative. Given the reported valuations of agents, an allocation rule chooses an alternative and a payment rule determines the payments of each agent. The net utility of each agent is quasi-linear in the payment he makes. An allocation rule is implementable (in dominant strategies) if there is a payment rule which makes truth-telling a weakly dominant strategy for each agent. We answer the following fundamental question in our model.

Which allocation rules are implementable?

We offer two main results.¹ Under a mild range condition, we show that an allocation rule is implementable if and only if it is a generalized utility function (GUF) maximizer. At every valuation profile, a GUF of an agent translates his valuation vector to a pair of real numbers, which we call his generalized utilities for these two alternatives at this valuation profile. At every valuation profile, a GUF maximizer allocation rule chooses an alternative that maximizes the sum of generalized utilities of agents.

Our second result shows that an implementable allocation rule satisfying an independence condition is an affine maximizer. Affine maximizer allocation rules, introduced in Roberts (1979), are generalizations of the efficient allocation rule. They can be thought of as linearized GUF maximizer allocation rules. Conversely, every affine maximizer satisfies our independence condition. It is well known that under a mild condition, an affine maximizer is implementable.

To prove the latter result, we prove another result, which is of independent interest. We show that if an implementable allocation rule satisfies unanimity and transitivity ² in our model, then it must be a weighted efficient allocation rule. Weighted efficient allocation rules are a special class of affine maximizer allocation rules. Conversely, every weighted efficient allocation rule satisfies unanimity and transitivity.

Though a mechanism design problem with two alternatives seems far-fetched, many well-studied problems fall into this category. First, the bilateral trading problem has two agents (a buyer and a seller) and two alternatives—trade or no trade. Second, the non-excludable public good provision problem is a problem with two alternatives—whether to provide the public good or not. Since the valuation for the status-quo alternative (no trade in the case of bilateral trading problem and not providing the public good in case of public good provision problem) is zero in these problems, the private information of each agent is uni-dimensional here. However, there are two-dimensional problems where our results can be applied. For instance, consider the problem of locating a facility in one of two locations. Each agent has a two-dimensional valuation vector representing his valuation for each location. All our results can be applied to this problem to identify the set of implementable allocation rules. Our results can also be applied to some extensions of classical bilateral trading problem and public good provision problem. The classical versions of these problems assume that the status-quo alternative has zero valuation for all the agents. Our model of two alternatives can allow agents to have non-zero private valuation for such a status-quo alternative.

A characterization of implementable allocation rules in the two-alternatives model is also an important step to achieving similar characterization for models with more than two alternatives. This is shown in Carbajal et al. (2013), who show that in a specific model (discussed later) with arbitrary number of alternatives, the set of implementable allocation rules can be defined recursively with the starting point being the two alternatives case. They refer to our characterizations for the two alternatives case.

1.1 Relation to the literature

The pursuit of identifying the set of implementable allocation rules in voting models goes back to the seminal work of Gibbard (1973) and Satterthwaite (1975), who establish that dictatorship is the only implementable allocation rule under a mild range condition with unrestricted domain, when there are at least three alternatives. In quasi-linear environments, the analogue of the Gibbard–Satterthwaite theorem is due to Roberts (1979). In a remarkable result, Roberts (1979) showed that under a mild range condition, every implementable allocation rule is an affine maximizer if there are at least three alternatives and the domain of valuations for each alternative is unrestricted. It is well known that an affine maximizer is implementable using generalized Groves payment rules (Vickrey 1961; Clarke 1971; Groves 1973) if it satisfies a mild tie-breaking condition.

When the domain of valuations is restricted or the number of alternatives is two, Roberts’ affine maximizer theorem is no longer true, and the set of implementable allocation rules is significantly enlarged. However, there has been very little progress in understanding the extensions of Roberts’ theorem in restricted domains of valuations or in problems with two alternatives. We note some exceptions. Jehiel et al. (2008) show that Roberts’ theorem extends to certain environments with interdependent valuations. Mishra and Sen (2012) show that in multidimensional open interval domains, every neutral and implementable allocation rule is a weighted efficient allocation rule if the number of alternatives is at least three.

Carbajal et al. (2013) show that if the domain of valuation profiles is restricted to the space of continuous functions defined on a topological space, or the space of piecewise linear functions defined on an affine space, or the space of smooth functions defined on a compact differentiable manifold, then an allocation rule is implementable if and only if it is a lexicographic affine maximizer. Their results do not require the set of alternatives to be finite. Lexicographic affine maximizers, which are defined recursively, are generalizations of affine maximizer allocation rules. Thus, they generalize Roberts’ theorem to a restricted environment. Lexicographic affine maximization does not require the number of alternatives to be at least three. However, when the number of alternatives is two, lexicographic affine maximization in Carbajal et al. (2013) is a monotonicity condition (or equivalently a cutoff in differences condition). This monotonicity is similar to the monotonicity condition used to characterize implementability in the single object auction setting (Myerson 1981). Further, this is equivalent to the 2-cycle monotonicity condition widely used in the multidimensional mechanism design literature (Bikhchandani et al. 2006; Saks and Yu 2005; Ashlagi et al. 2010).

The difference between the “monotonicity” characterizations and the “maximization” characterizations (a la Roberts 1979 and our GUF maximization) is significant. A monotonicity characterization will say that for every agent and for every valuation vector of other agents, the allocation rule must be “monotone” in some sense when the valuation vector of this agent is changed. On the other hand, a maximization characterization is more explicit. It tells you the exact parameters that define an implementable allocation rule. Thus, it is a direct prescription for designing a dominant strategy mechanism.

Because of this reason, there have been several attempts at simplifying the proof in Roberts’ theorem—Lavi et al. (2009), Dobzinski and Nisan (2009), Vohra (2011). Dobzinski and Nisan (2011) show that in combinatorial auction domains (a restricted domain) involving two agents, there are non-affine maximizer allocation rules which give good approximation to efficiency. However, they do not provide any general characterization result (except for a specific case of auction of two goods among two agents).

Another related paper is Mishra and Quadir (2014). They characterize the set of implementable allocation rules in the model of single object auctions. Like the current paper, their characterization captures a larger class of allocation rules than affine maximizers. However, since single object auctions is a very different domain, their results cannot be applied in our model of two alternatives.

Some specific models with two alternatives have been studied extensively in the literature. We review them below.

• One such model is the bilateral trading model, where there is one buyer and one seller who want to trade a good (owned by the seller). Myerson and Satterthwaite (1983) showed that Bayes–Nash implementation, budget-balance, efficiency, and individual rationality are incompatible in bilateral trading. Hagerty and Rogerson (1987) showed that the only mechanisms which are dominant strategy incentive compatible, budget-balanced, and individually rational are posted-price mechanisms. Our GUF maximizer result applies to the bilateral trading model. Indeed, our results can be applied to the bilateral trading models where the no-trade alternative (outside option) also has some non-zero value (which can be a private information of the agents). Further, our characterizations are of implementable allocation rules and not of mechanisms (allocation rule and payments). Thus, we do not impose additional properties like budget-balance and individual rationality, which are all properties of payments.

• Another model with two alternatives is the public good provision problem, where a planner is deciding whether to provide the public good or not. An excellent treatment of this problem is given in Borgers (2010)—see also Güth and Hellwig (1986). Like in the bilateral trading problem, our results can be applied to this problem. Our results are applicable even if agents have private valuation for the status quo alternative. Unlike the literature, where the focus has been to find incentive compatible mechanisms satisfying additional properties like budget-balance, individual rationality etc., our results characterize implementable allocation rules.

We will like to note that in the voting model of Gibbard (1973) and Satterthwaite (1975), the implications of having only two alternatives on strategy-proofness is well known (Fishburn and Gehrlein 1977)—see also the surveys of Moulin (1983) and Barbera (2011). The strategy-proof rules identified in this voting model continue to be implementable in our model. However, these allocation rules are ordinal rules—the ordinal ranking of alternatives, and not their cardinal valuations, matter. The range condition we use in our main characterization and the independence condition we use in our affine maximizer characterization are not satisfied by such ordinal allocation rules. Hence, the allocation rules we characterize in this paper do not capture the ordinal strategy-proof allocation rules in the voting model.

Finally, though we characterize implementable allocation rules, we can use revenue equivalence to pin down the class of payments in our model. This allows us to describe the entire class of incentive compatible mechanisms.

2 The model and a preliminary result

The set of agents is $N:=\{1,\ldots ,n\}$. There are exactly two alternatives: $a_1$ and $a_2$. The set of alternatives is denoted by $A:=\{a_1,a_2\}$. Each agent $i \in N$ has a valuation for each alternative, and this is denoted as $v_i(a_j)$ for every $j \in \{1,2\}$. A valuation vector for agent $i$ is denoted as $v_i$. For any agent $i \in N$, let $V_i$ denote the set of all valuation vectors for agent $i$. A valuation profile is denoted as $v:=(v_1,\ldots ,v_n)$ and the set of all valuation profiles is $V:=V_1 \times \cdots \times V_n$. We will use the standard notations $v_{-i}$ to denote a valuation profile of agents other than agent $i$ and $V_{-i}$ to denote the set of all such valuation profiles.

An allocation rule is a mapping $f:V \rightarrow A$. Note that we focus on deterministic allocation rules. A payment rule of agent $i$ is a mapping $p_i: V \rightarrow \mathbb {R}$.

An allocation rule $f$ is (dominant strategy) implementable if there exists payment rules $p_1,\ldots ,p_n$ such that for every agent $i \in N$ and for every $v_{-i} \in V_{-i}$ the following inequality holds for every $v_i,v'_i \in V_i$,

$$\begin{aligned} v_i(f(v_i,v_{-i})) - p_i(v_i,v_{-i})&\ge v_i(f(v'_i,v_{-i})) - p_i(v'_i,v_{-i}). \end{aligned}$$

In this case, we say that the payment rules $p_1,\ldots ,p_n$ implement $f$. A mechanism is an allocation rule $f$ and payment rules $(p_1,\ldots ,p_n)$. A mechanism $M \equiv (f,p_1,\ldots ,p_n)$ is incentive compatible if $(p_1,\ldots ,p_n)$ implement $f$.

For every agent $i \in N$ and for any valuation vector $v_i \in V_i$, define $\partial v_i := v_i(a_1)-v_i(a_2)$.

Definition 1

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$, if $\partial v_i > \partial v'_i$ and $f(v'_i,v_{-i})=a_1$, then $f(v_i,v_{-i}) = a_1$.

The following preliminary result, due to Carbajal et al. (2013), characterizes implementable allocation rules. We use this result to prove our main results.

Proposition 1

(Carbajal et al. 2013) An allocation rule is implementable if and only if it is monotone.

The monotonicity condition we use to characterize implementability in Proposition 1 is equivalent to the well-known 2-cycle monotonicity. It is well known that such monotonicity is necessary and sufficient for implementability in one-dimensional value models such as single object auctions (Myerson 1981). Though agents have two-dimensional values in our model, what matters for implementability is their difference of value between the two alternatives. This ensures that monotonicity is still necessary and sufficient in our model.

3 Complete characterization

We present our main result in this section. We give a characterization of implementable allocation rules under a mild condition. Before presenting this characterization, we discuss Roberts’ affine maximizer theorem (Roberts 1979).

3.1 Roberts’ affine maximizers

In this subsection we let $A$ to be any finite set of alternatives, and do not put the restriction that $|A|=2$. An allocation rule $f$ is an affine maximizer if there exist non-negative real numbers $\lambda _1,\ldots ,\lambda _n$ and a mapping $\gamma :A \rightarrow \mathbb {R}$ such that at every valuation profile $v$, we have

$$\begin{aligned} f(v)&\in \arg \max _{a \in A}\big [\sum _{i \in N}\lambda _i v_i(a) + \gamma (a) \big ] \end{aligned}$$

An affine maximizer allocation rule $f$ with weights $\lambda _1,\ldots ,\lambda _n \ge 0$ and $\gamma :A \rightarrow \mathbb {R}$ satisfies unresponsiveness to irrelevant agents (UIA) if for every $i \in N$ such that $\lambda _i=0$, we have $f(v_i,v_{-i})=f(v'_i,v_{-i})$ for every $v_{-i} \in V_{-i}$ and for every $v_i, v'_i \in V_i$. It is well known that an affine maximizer that satisfies UIA can be implemented using generalized Groves (1973) payment rules—see for instance Mishra and Sen (2012).

Note that in the definition of an affine maximizer, we can choose, without loss of generality, $\lambda _i$ for all $i \in N$ such that $\sum _{i \in N}\lambda _i=1$ if $\lambda _i > 0$ for some $i \in N$. We call such an affine maximizer a responsive affine maximizer. Roberts (1979) showed that if $|A| \ge 3$ and $V_i=\mathbb {R}^{|A|}$ for all $i \in N$, then every onto implementable allocation rule is a responsive affine maximizer. To remind, an allocation rule $f$ is onto if for every $a \in A$, there exists a valuation profile $v \in V$ such that $f(v)=a$.

Hence, Roberts (1979) almost characterizes the set of implementable allocation rules in unrestricted domains (i.e., when $V_i=\mathbb {R}^{|A|}$ for all $i \in N$) and when $|A| \ge 3$.

Example 1

Roberts’ affine maximizer theorem is no longer true if $|A|=2$. For instance, consider the following allocation rule $\bar{f}$ with two agents $\{1,2\}$ and $V_1=V_2=\mathbb {R}^2$. For every $v \in V$,

$$\begin{aligned} \bar{f}(v) = \left\{ \begin{array}{l@{\quad }l} a_1 &{} \mathrm if ~(\partial v_1)^3 + \partial v_2 \ge 0 \\ a_2 &{} \mathrm if ~(\partial v_1)^3 + \partial v_2 < 0. \end{array} \right. \end{aligned}$$

It is easy to verify that $\bar{f}$ is monotone, and hence, implementable by Proposition 1. But $\bar{f}$ is not an affine maximizer. Next, we provide a characterization of implementable allocation rules extending Roberts’ affine maximizer theorem. Our characterization covers allocation rules of the form $\bar{f}$.

3.2 Generalized utility function maximizers

The main tool of our characterization is the notion of a generalized utility function.

Definition 2

A generalized utility function (GUF) is a mapping $u:A \times V \rightarrow \mathbb {R}$ for all $v \in V$.

We associate a GUF with every agent. The GUF associated with agent $i$ is denoted by $u_i$. At any $v \in V$, let

$$\begin{aligned} \partial u_i(v)&= u_i(a_1,v) - u_i(a_2,v). \end{aligned}$$

In other words, $\partial u_i(v)$ denotes the difference in “generalized utility” of agent $i$ at valuation profile $v$. We concentrate on a particular class of GUFs.

Definition 3

A GUF $u_i$ of agent $i$ is strictly monotone if

• (1) for every $v_{-i} \in V_{-i}$, for every $v_i,v'_i \in V_i$ with $\partial v_i > \partial v'_i$, we have

  $$\begin{aligned} \partial u_i(v_i,v_{-i})&> \partial u_i(v'_i,v_{-i}). \end{aligned}$$

• (2) for every $j \ne i$, for every $v_{-j} \in V_{-j}$, and every $v_j,v'_j \in V_j$ with $\partial v_j > \partial v'_j$, we have

  $$\begin{aligned} \partial u_i(v_j,v_{-j})&\ge \partial u_i(v'_j,v_{-j}). \end{aligned}$$

Using the notion of GUFs, we define a broad class of allocation rules.

Definition 4

An allocation rule $f$ is a GUF maximizer if there exist strictly monotone GUFs $(u_1,\ldots ,u_n)$ such that for all $v \in V$, we have

$$\begin{aligned} f(v)&\in \arg \max _{a \in A}\sum _{i \in N}u_i(a,v). \end{aligned}$$

In this case, we say that $f$ is representable by $(u_1,\ldots ,u_n)$.

We now show that every GUF maximizer is implementable.

Lemma 1

Every GUF maximizer allocation rule is implementable.

Proof

Consider a GUF maximizer allocation rule $f$, and suppose $f$ is representable by $(u_1,\ldots ,u_n)$. Fix an agent $i$ and $v_{-i} \in V_{-i}$. Consider $v_i,v'_i \in V_i$ such that $\partial v_i > \partial v'_i$. Suppose $f(v'_i,v_{-i}) = a_1$. Then, by definition of $f$, we have

$$\begin{aligned} \sum _{j \in N}u_j(a_1,v'_i,v_{-i})&\ge \sum _{j \in N}u_j(a_2,v'_i,v_{-i}). \end{aligned}$$

Hence, we get that

$$\begin{aligned} \sum _{j \in N}\partial u_j(v'_i,v_{-i})&\ge 0. \end{aligned}$$

By strict monotonicity, $\partial u_i(v_i,v_{-i}) \!>\! \partial u_i(v'_i,v_{-i})$ and $\partial u_j(v_i,v_{-i}) \!\ge \! \partial u_j(v'_i,v_{-i})$ for all $j \ne i$. Hence, we get

$$\begin{aligned} \sum _{j \in N}\partial u_j(v_i,v_{-i})&> 0. \end{aligned}$$

This implies that

$$\begin{aligned} \sum _{j \in N}u_j(a_1,v_i,v_{-i})&> \sum _{j \in N}u_j(a_2,v_i,v_{-i}). \end{aligned}$$

By the definition of GUF maximizer, $f(v_i,v_{-i})=a_1$. Hence, $f$ is monotone, and by Proposition 1, $f$ is implementable. $\square$

A GUF maximizer can be quite involved. In particular, GUF of an agent may depend on the valuations of all the agents. We illustrate this with an example.

Example 2

Consider an example with $N=\{1,2\}$, $V_1=V_2=\mathbb {R}^2$ and the generalized utility function of agent $1$ as

$$\begin{aligned} u_1(a_1,v_1,v_2)&= [v_1(a_1) - v_1(a_2)]^2+[v_2(a_1)-v_2(a_2)] \\ u_1(a_2,v_1,v_2)&= 0, \end{aligned}$$

where $v_1$ and $v_2$ are valuation functions of agents $1$ and $2$ respectively. It is clear that $u_1$ strictly monotone. Hence, $u_1$ is a valid GUF maximizer. Notice that $u_1$ depends on the valuations of both the agents.

Our main result shows that under a mild range condition, GUF maximizers are the only implementable allocation rules.

Definition 5

An allocation rule $f$ satisfies agent sovereignty if for every agent $i \in N$, every $v_{-i} \in V_{-i}$, and every $a \in A$, there is a $v_i \in V_i$ such that $f(v_i,v_{-i})=a$. An allocation rule $f$ satisfies weak agent sovereignty if for every agent $i \in N$, every $v_{-i} \in V_{-i}$, there is a $v_i \in V_i$ such that $f(v_i,v_{-i})=a_1$.

Agent sovereignty requires every agent to have some decisive power irrespective of the values of other agents. It has been used extensively in public good provision problems (Moulin 1999; Moulin and Shenker 2001). Lavi et al. (2009) use agent sovereignty³ to give a clean proof of Roberts’ affine maximizer theorem (Roberts 1979).

For every $i \in N$, define $D_i:=\{\partial v_i: v_i \in V_i\}$. Note that $D_i \subseteq \mathbb {R}$.

Theorem 1

Let $f$ be an allocation rule. Suppose one of the following conditions holds:

Ca :

$f$ satisfies agent sovereignty and for every $i \in N$, $D_i$ is an interval.

Cb :

$f$ satisfies weak agent sovereignty and for every $i \in N$, $D_i$ is an interval bounded from below.

Then, $f$ is implementable if and only if it is a GUF maximizer.

The natural domains where condition Ca and Cb can be satisfied are product interval domains. Denote by $V_i^a$ the set of possible valuations on alternative $a \in A$ for agent $i \in N$. Let $V_i=V_i^{a_1} \times V_i^{a_2}$. Condition Ca holds if $f$ satisfies agent sovereignty and $V_i^a$ is an interval for every $a \in A$. Condition Cb holds if $f$ satisfies weak agent sovereignty and $V_i^{a_1}$ and $V_i^{a_2}$ are intervals, and $V_i^{a_1}$ is bounded from below (for instance $\mathbb {R}_+$) and $V_i^{a_2}$ is bounded from above (for instance any compact interval). These domain restrictions cover the classical problems of bilateral trading, public good provision, and their extensions.

In the Appendix, we give examples that illustrate that the conditions used in Theorem 1 are required.

3.3 Proof of Theorem 1

Before proving Theorem 1, we establish some claims. Suppose $f$ is an implementable allocation rule. Then, for every $i \in N$ and every $v_{-i} \in V_{-i}$, define $d^f_i(v_{-i})$ as follows:

$$\begin{aligned} d^f_i(v_{-i})&= \inf \{\partial v_i \in D_i: f(v_i,v_{-i})=a_1\}. \end{aligned}$$

We prove a series of claims. In each claim, we assume that $f$ is an implementable allocation rule. Further, $f$ satisfies agent sovereignty and for every $i \in N$, $D_i$ is an interval.

The first claim shows when $d^f_i(v_{-i})$ is well defined for every $i \in N$ and for every $v_{-i} \in V_{-i}$.

Claim 1

For every $i \in N$ and for every $v_{-i} \in V_{-i}$, $d^f_i(v_{-i})$ exists.

Proof

Fix agent $i$ and $v_{-i} \in V_{-i}$. Under conditions (Ca) or (Cb), there is some value $v_i \in V_i$ such that $f(v_i,v_{-i})=a_1$.

If condition (Ca) holds, then for some $v'_i$, $f(v'_i,v_{-i})=a_2$. Since $f$ is implementable, it is monotone (Proposition 1). Hence, $\partial v'_i \le \partial v_i$. Since $D_i$ is an interval, we get that $\inf \{\partial v_i \in D_i: f(v_i,v_{-i})=a_1\}$ is a real number.

If condition (Cb) holds, then since $D_i$ is an interval bounded below, $\inf \{\partial v_i \in D_i: f(v_i,v_{-i})=a_1\}$ is a real number. $\square$

We now define a payment rule. For every agent $i \in N$, define $p^f_i$ as follows:

$$\begin{aligned} p^f_i(v_i,v_{-i}) = \left\{ \begin{array}{l l} 0 &{} \quad \mathrm if \quad ~f(v_i,v_{-i}) = a_2 \\ d^f_i(v_{-i}) &{} \quad \mathrm if \quad ~f(v_i,v_{-i}) = a_1. \end{array} \right. \end{aligned}$$

These payments are counterparts of Myerson’s cutoff-based payments for single object auction (Myerson 1981).

Claim 2

The payment rule $(p^f_1,\ldots ,p^f_n)$ implements $f$.

Proof

Fix an agent $i \in N$ and $v_{-i} \in V_{-i}$. Consider $v_i,v'_i \in V_i$. We will show that

$$\begin{aligned} v_i(f(v_i,v_{-i}) - p^f_i(v_i,v_{-i})&\ge v_i(f(v'_i,v_{-i})) - p^f_i(v'_i,v_{-i}). \end{aligned}$$

If $f(v_i,v_{-i})=f(v'_i,v_{-i})$, we are done. So, assume that $f(v_i,v_{-i}) \ne f(v'_i,v_{-i})$. We consider two cases.

Case 1. Suppose $f(v_i,v_{-i})=a_1$ and $f(v'_i,v_{-i})=a_2$. Then, $v_i(f(v_i,v_{-i})) - p^f_i(v_i,v_{-i}) = v_i(a_1) - d^f_i(v_{-i})$. Since $d^f_i(v_{-i}) \le \partial v_i$, we get that $v_i(a_1) - d^f_i(v_{-i}) \ge v_i(a_2) = v_i(f(v'_i,v_{-i})) - p^f_i(v'_i,v_{-i})$, where we used the fact that $p^f_i(v'_i,v_{-i})=0$ since $f(v'_i,v_{-i})=a_2$.

Case 2. Suppose $f(v_i,v_{-i})=a_2$ and $f(v'_i,v_{-i})=a_1$. We argue that $\partial v_i \le d^f_i(v_{-i})$. Assume for contradiction that $\partial v_i > d^f_i(v_{-i})$. By definition of $d^f_i(v_{-i})$, there is $v''_i$ such that $f(v''_i,v_{-i})=a_1$ and $\partial v''_i$ is arbitrarily close to $d^f_i(v_{-i})$. Hence, $\partial v_i > \partial v''_i$. Then, since $f$ is monotone, $f(v_i,v_{-i})=a_1$, which is a contradiction.

Hence, $v_i(a_2) \ge v_i(a_1) - d^f_i(v_{-i})$. Using the fact that $p^f_i(v_i,v_{-i})=0$ since $f(v_i,v_{-i})=a_2$ and $p^f_i(v'_i,v_{-i})=d^f_i(v_{-i})$ since $f(v'_i,v_{-i})=a_1$, we get that $v_i(f(v_i,v_{-i})) - p^f_i(v_i,v_{-i}) = v_i(a_2) \ge v_i(a_1) - d^f_i(v_{-i}) = v_i(f(v'_i,v_{-i})) - p^f_i(v'_i,v_{-i})$. $\square$

Claim 2 has other implications. If $V_i$ is connected for each $i \in N$, then by well-known results on revenue equivalence (Heydenreich et al. 2009), we can conclude that any other payment rule $p_i$ of agent $i$ must look as follows: $p_i(v)=p^f_i(v) + h_i(v_{-i})$ for all $v \in V$, where $h_i:V_{-i} \rightarrow \mathbb {R}$ is any function.

The next claim shows a monotonicity property of $d^f_i(\cdot )$ for every $i \in N$.

Claim 3

For every $i$, for every $j \ne i$, for every $v_j,v'_j \in V_j$ such that $\partial v_j < \partial v'_j$, we have that $d^f_i(v_j,v_{-ij}) \ge d^f_i(v'_j,v_{-ij})$ for all $v_{-ij} \in V_{-ij}$.

Proof

Fix agents $i$ and $j \ne i$, and consider $v_j,v'_j \in V_j$ such that $\partial v_j < \partial v'_j$. Assume for contradiction that $d^f_i(v_j,v_{-ij}) < d^f_i(v'_j,v_{-ij})$ for some $v_{-ij} \in V_{-ij}$. Let $v_i$ be such that $\partial v_i = d^f_i(v_j,v_{-ij}) + \epsilon < d^f_i(v'_j,v_{-ij})$ for some sufficiently small $\epsilon > 0$. Since $D_i$ is an interval, such a $v_i$ exists. By definition, $f(v_i,v_j,v_{-ij})=a_1$ and $f(v_i,v'_j,v_{-ij})=a_2$. But $\partial v_j < \partial v'_j$ means $f(v_i,v'_j,v_{-ij})=a_1$ by monotonicity. This is a contradiction. $\square$

This leads us to the proof of Theorem 1.

Proof

Lemma 1 shows that every GUF maximizer is implementable. We prove the converse. Let $f$ be an implementable allocation rule, and suppose (sc Ca) or (Cb) holds. For every $i \in N$, define the GUF of agent $i$ as follows: for every $(v_i,v_{-i}) \in V$ let

$$\begin{aligned} u_i(a,v_i,v_{-i}) = \left\{ \begin{array}{l l} 0 &{} \quad \mathrm if \quad ~a = a_2 \\ \partial v_i - d^f_i(v_{-i}) &{} \quad \mathrm if \quad ~a = a_1. \end{array} \right. \end{aligned}$$

By Claim 1, GUFs are well-defined. We show that for any $i \in N$, $u_i$ is strictly monotone. By definition, for every $v_{-i}$, $u_i(a_1,v) = \partial v_i - d^f_i(v_{-i}) > \partial v'_i - d^f_i(v_{-i})$ if $\partial v_i > \partial v'_i$. Now, fix any $j \ne i$ and consider $v_j,v'_j$ such that $\partial v_j > \partial v'_j$. By Claim 3, $u_i(a_1,v_j,v_{-j}) = \partial v_i - d^f_i(v_j,v_{-ij}) \ge \partial v_i - d^f_i(v'_j,v_{-ij}) = u_i(a_1,v'_j,v_{-j})$.

Now, consider any $v \in V$ and suppose $f(v)=a_1$. Then, by definition, for every $i \in N$, $d^f_i(v_{-i}) \le \partial v_i$. Hence, $u_i(a_1,v) \ge u_i(a_2,v)$, which implies that $\sum _{j \in N}u_j(a_1,v) \ge \sum _{j \in N}u_j(a_2,v)$. Similarly, suppose $f(v)=a_2$. Then, for every $i \in N$, since $f$ satisfies agent sovereignty, there is a $v'_i$ such that $f(v'_i,v_{-i})=a_1$. But, by Claim 2, $v_i(a_2) - 0 \ge v_i(a_1) - d^f_i(v_{-i})$. Hence, $u_i(a_2,v) \ge u_i(a_1,v)$, which implies that $\sum _{j \in N}u_j(a_2,v) \ge \sum _{j \in N}u_j(a_1,v)$. This shows that $f$ is representable by GUFs $(u_1,\ldots ,u_n)$. $\square$

4 An axiomatization of affine maximizers

Theorem 1 shows the rich class of “maximizers” that can be implemented when there are two alternatives. However, when we have more than two alternatives, we only get affine maximizers in unrestricted domains. Then, a natural question to ask is: what extra condition(s) besides implementability are needed to pin down the affine maximizers when there are two alternatives? This will help us understand the case of two alternatives even further.

The aim of this section is to axiomatize the affine maximizers for the case of $|A|=2$ using implementability and some additional condition(s). It turns out, we only need one new condition besides implementability. To introduce the new condition, we will need some notation.

We will assume that the set of possible valuations of each for each alternative is an open interval. Hence, throughout this section, we will assume that for every $i \in N$, $V_i = L_i \times L_i$, where $L_i$ is an open interval. We will call this the open interval domain. Notice that the valuation for every alternative lies in the same interval.

Given a profile of valuations $(v_1,\ldots ,v_n)$, we will often be interested in the vector of valuations associated with each alternative. In particular, for $j \in \{1,2\}$, let $v(a_j) \in \mathbb {R}^n$ denote the valuation vector associated with alternative $a_j$. Let $U$ be the set of all valuation vectors for alternatives given our open interval domain assumption. Note that $U$ is an open rectangle in $\mathbb {R}^n$. A profile of valuations contains exactly two valuation vectors from $U$, one denoting the valuations for alternative $a_1$ and the other denoting the valuations for alternative $a_2$. For convenience, we will denote the profile of valuations as $(v(a_1),v(a_2))$ instead of $(v_1,\ldots ,v_n)$. Further, for every $a \in A$, we will sometimes write $(v(a),v(-a))$ to denote the profile of valuations $(v(a_1),v(a_2))$.

We are now ready to state our new condition.

Definition 6

An allocation rule $f$ satisfies independence if for every $a \in A$, for every pair of valuation profiles $v,v'$, and for every $\epsilon \in \mathbb {R}^n_{++}$, we have

$$\begin{aligned} \left. \begin{array}{c} f(v(a),v(-a)) = a \\ \text{ and } \\ f(v'(a),v'(-a)) = a \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} f(v'(a)+\epsilon ,v(-a)) = a \\ \text{ or } \\ f(v(a)+\epsilon ,v'(-a)) = a. \end{array} \right. \end{aligned}$$

Suppose there are two valuation profiles $v,v'$, an alternative $a \in A$ and $\epsilon \in \mathbb {R}^n_{++}$ such that $f(v(a),v(-a))=a$ and $f(v'(a)+\epsilon ,v(-a)) \ne a$. From this, we can infer that the support provided to $a$ by $v(a)$ is stronger than the support provided to $a$ by $v'(a)$. Suppose now that $f(v'(a),v'(-a))=a$. If we replace $v'(a)$ by $v(a)+\epsilon$ in the profile $(v'(a),v'(-a))$, the support in favor of $a$ must increase. Since $a$ was chosen at $(v'(a),v'(-a))$, it must be chosen at $(v(a)+\epsilon ,v'(-a))$. Hence, $f(v(a)+\epsilon ,v'(-a))=a$. This is what independence says.

A similar condition is used in Debreu’s theorem on the additive representation of a binary relation over a Cartesian product (see Theorem 3 in Debreu 1960). The central idea behind an independence condition is the ability to compare a pair of valuation vectors independent of other valuation vectors. With three or more alternatives, the natural notion of independence is binary independence, which requires comparison of valuation vectors of any pair of alternatives independent of the valuation vectors of other alternatives. This condition is implied by implementability and neutrality if there are three or more alternatives (Mishra and Sen 2012).

However, with two alternatives, binary independence cannot be defined. The independence we use is natural with two alternatives: if we take any two valuation vectors of an alternative, the social choice function must evaluate them independent of the valuation vector of the other alternative. Allocation rules satisfying independence are clearly less complicated than those that do not satisfy independence. As it turns out, such implementable allocation rules are affine maximizers. Hence, it rules out “non-linear” allocation rules that are implementable.

First, we show that an affine maximizer allocation rule satisfies independence.

Lemma 2

Every affine maximizer allocation rule satisfies independence.

Proof

Let $f$ be an affine maximizer allocation rule with weights $\lambda _1,\ldots ,\lambda _n \ge 0$ and $\gamma :A \rightarrow \mathbb {R}$. Consider a pair of valuation profiles $v,v'$ such that $f(v)=f(v')=a_1$ (the other case where $f(v)=f(v')=a_2$ can be dealt with similarly). Then, affine maximization gives us

$$\begin{aligned} \sum _{i \in N}\lambda _i v_i(a_1) + \gamma (a_1)&\ge \sum _{i \in N}\lambda _i v_i(a_2) + \gamma (a_2) \\ \sum _{i \in N}\lambda _i v'_i(a_1) + \gamma (a_1)&\ge \sum _{i \in N}\lambda _i v'_i(a_2) + \gamma (a_2). \end{aligned}$$

Adding these two inequalities gives us

$$\begin{aligned} \sum _{i \in N}\lambda _i \big [v_i(a_1)+v'_i(a_1)\big ] + 2\gamma (a_1)&\ge \sum _{i \in N}\lambda _i \big [v_i(a_2)+v'_i(a_2)\big ] + 2\gamma (a_2). \end{aligned}$$

(1)

Now, assume for contradiction $f(v(a_1)+\epsilon ,v'(a_2))=a_2$ and $f(v'(a_1)+\epsilon ',v(a_2))=a_2$ for some $\epsilon ,\epsilon ' \in \mathbb {R}^n_{++}$. Then, $f$ is a non-constant affine maximizer. Since $\epsilon ,\epsilon ' \in \mathbb {R}^n_{++}$, this implies that

$$\begin{aligned} \sum _{i \in N}\lambda _i v'_i(a_2) + \gamma (a_2)&> \sum _{i \in N}\lambda _i v_i(a_1) + \gamma (a_1) \\ \sum _{i \in N}\lambda _i v_i(a_2) + \gamma (a_2)&> \sum _{i \in N}\lambda _i v'_i(a_1) + \gamma (a_1). \end{aligned}$$

Adding these two inequalities gives a contradiction to Inequality 1. $\square$

There are non-affine maximizer allocation rules which are implementable but do not satisfy independence. For instance, consider the implementable allocation rule $\bar{f}$ in Example 1. Suppose $v$ is the valuation profile where $v_1(a_1)=2, v_1(a_2)=0, v_2(a_1)=1,v_2(a_2)=4$ and $v'$ is the valuation profile where $v'_1(a_1)=0,v'_1(a_2)=1,v'_2(a_1)=v'_2(a_2)=3$. By definition, $\bar{f}(v)=\bar{f}(v')=a_1$. Now, for sufficiently small $\epsilon \in \mathbb {R}^2_{++}$, it is easily verified that $\bar{f}(v(a_1)+\epsilon ,v'(a_2))=\bar{f}(v'(a_1)+\epsilon ,v(a_2))=a_2$. Hence, $\bar{f}$ does not satisfy independence.

Under some domain assumption, we show that amongst the implementable allocation rules, only affine maximizers satisfy independence.

Theorem 2

Suppose for every $i \in N$, $L_i$ is an open interval unbounded from above. If an allocation rule is implementable and satisfies independence, then it is an affine maximizer. Conversely, if $f$ is an affine maximizer, then it satisfies independence, and further, if it satisfies UIA, then it is implementable.

The proof of Theorem 2 is in the Appendix. The proof uses another interesting result on axiomatizing weighted efficiency, which we state next.

4.1 An axiomatization of weighted efficiency

Weighted efficiency is a particular form of affine maximizer. An allocation rule $f$ is a weighted efficient allocation rule if there exists weights $\lambda _1,\ldots ,\lambda _n \ge 0$ with $\lambda _i > 0$ for some $i \in N$, such that for every valuation profile $v \in V$, we have $f(v) \in \arg \max _{a \in A}\sum _{i \in N}\lambda _iv_i(a)$.

Among the class of affine maximizer allocation rules, weighted efficient allocation rules do not discriminate between alternatives. We will show that under some additional conditions, implementability will imply weighted efficiency. To define the additional conditions, we need some preparation. First, we introduce a well known monotonicity condition due to Roberts (1979).

Definition 7

An allocation rule $f$ satisfies positive association of differences (PAD) if for every pair of profile of valuations $v,v' \in V$ such that $\partial v_i > \partial v'_i$ for every $i \in N$ and $f(v')=a_1$ we have $f(v)=a_1$.

Consider a pair of profile of valuations $v,v' \in V$ such that $\partial v_i < \partial v'_i$ for every $i \in N$ and $f(v')=a_2$. Note that PAD implies that $f(v)=a_2$. To see this, assume for contradiction $f(v)=a_1$. Then, applying PAD (interchanging the role of $v$ and $v'$ in above definition), we get that $f(v')=a_1$, a contradiction.

Roberts (1979) showed that PAD is a necessary condition for implementability.

Lemma 3

(Roberts 1979) If an allocation rule is implementable, then it satisfies PAD.

It can be shown that monotonicity implies PAD, and hence, Lemma 3 is a direct consequence of Proposition 1.

Given an allocation rule $f$, define the choice set at a profile of valuations $v$ as

$$\begin{aligned} C^f(v)&= \{a \in A: f(v(a)+\epsilon ,v(-a)) = a~\forall ~\epsilon \in \mathbb {R}^n_{++}\}. \end{aligned}$$

Since $U$ is open, $C^f(v)$ is well defined for every profile of valuations $v$. Using PAD, one notices that if $f$ is implementable, then $f(v) \in C^f(v)$ for every valuation profile $v \in V$. Hence, the choice set is non-empty. The choice set allows us to look at potential “candidates” other than $f(v)$ which could have been selected by the allocation rule $f$ at valuation profile $v$.

We now introduce two new conditions on allocation rules. The first one is a transitivity requirement.

Definition 8

An allocation rule $f$ is transitive if for every $x,y,z \in U$, and every $v,v',v'' \in V$ such that $v(a_1)=x=v''(a_1)$, $v(a_2)=y=v'(a_1)$, and $v'(a_2)=z=v''(a_2)$, we have,

• if $C^f(v)=\{a_1\}$   and    $C^f(v')=\{a_1\}$,   then    $f(v'')=a_1$    and

• if $C^f(v)=\{a_2\}$   and    $C^f(v')=\{a_2\}$,   then    $f(v'')=a_2$.

The next condition is unanimity, which is very similar in flavor to the unanimity axiom used in the social choice theory literature.

Definition 9

An allocation rule $f$ is unanimous if $\partial v_i > 0$ for all $i \in N$ implies $f(v) = a_1$ and $\partial v_i < 0$ for all $i \in N$ implies $f(v)=a_2$.

Theorem 3

Suppose for every $i \in N$, $L_i$ is an open interval. If $f$ is an implementable allocation rule that is unanimous and transitive, then it is a weighted efficient allocation rule. Conversely, a weighted efficient allocation rule $f$ is unanimous and transitive, and further, if it satisfies UIA, then it is implementable.

The proof of Theorem 3 is in the Appendix. In Mishra and Sen (2012), it was shown that if the number of alternatives is at least three, then in open interval domains, every neutral and implementable allocation rule is a weighted efficient allocation rule. Neutrality requires that the allocation rule does not discriminate between alternatives. Theorem 3 is the counterpart of this result for the two alternatives case. The proof of Theorem 3 reveals that in the presence of transitivity, unanimity is equivalent to neutrality in our model. Hence, compared to Mishra and Sen (2012), the extra axiom required to characterize weighted efficiency in our two alternatives model is transitivity.

5 Conclusion

In quasi-linear private values environment, Roberts’ affine maximizer theorem is a seminal contribution. Two crucial assumptions of this theorem are (a) there are at least three alternatives and (b) the domain of valuations is unrestricted. We extend this theorem by considering the case of two alternatives. Unlike the three or more alternatives result of Roberts (1979), which requires the domain of valuations to be unrestricted, our results for two alternatives hold in various restricted domains of valuations. An interesting future research direction will be to apply these results to specific problems with two alternatives, and do some optimization—for instance, revenue maximization or budget-balancing with minimal efficiency loss etc.

Finally, the notion of a GUF maximizer can be extended to environments with more than two alternatives also. With suitable restrictions on GUFs, one can make a GUF maximizer implementable in such environments. However, an open question remains whether such GUF maximizers are the only implementable allocation rules (under some additional mild conditions) in such environments.

Appendix

1.1 Proofs of Theorems 2 and 3

We prove Theorems 2 and 3 in this section. Before we do so, we comment on the methodology of the proof. The proof methodology is based on an ordering based approach of Mishra and Sen (2012) (M&S from now on). M&S provide an alternate proof of Roberts’ theorem when there are at least three alternatives. The general idea of their proof is to characterize weighted efficiency using neutrality and implementability. In the unrestricted domain, for every implementable allocation rule, there is another implementable allocation rule that satisfies neutrality. This new allocation rule can be obtained by translating the original allocation rule. One can then leverage the weighted efficiency characterization to get a characterization of affine maximization in the unrestricted domain.

Although, we employ this methodology, our proof is different in many aspects from M&S. This is mainly because we have two alternatives. Our characterization of weighted efficiency requires stronger condition than the neutrality condition of M&S. Further, our affine maximization characterization requires implementability and a new condition called independence, which M&S do not require if there are more than two alternatives.

1.2 Proof of Theorem 3

Like in M&S, we start by proving the characterization of weighted efficiency first, and then use this result to prove the affine maximizer characterization.

Fix an implementable allocation rule $f$. Consider the binary relation $R^f$ over $U$ defined by $x R^f y$ iff $a_{1} \in C^{f}(v)$, with $v(a_{1}) = x$ and $v(a_{2}) = y$. Let $P^f$ and $I^f$ respectively denote the asymmetric and symmetric part of $R^f$. They are well-behaved (in a sense made precise in Lemma 4) if $f$ satisfies a neutrality condition.

Definition 10

An allocation rule $f$ is neutral if for every pair of valuations $v,v' \in V$ such that $v(a_{1})=v'(a_{2})$ and $v(a_{2}) = v'(a_{1})$ we have

$$\begin{aligned} C^{f}(v) = \left\{ \begin{array}{ll} C^{f}(v') &{} \quad \text {if } \quad C^{f}(v) = A \\ A \setminus C^{f}(v) &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

The usual definition of neutrality will require that for every pair of valuations $v, v' \in V$ such that $v(a ) = v'(-a )$ and $v(-a ) = v'(a )$ with $v \ne v'$ we have $\{f(v')\} = A \setminus \{f(v)\}$. One can verify that this version of neutrality implies our version of neutrality if the allocation rule is implementable—see Mishra and Sen (2012) for a proof.

Lemma 4

Suppose $f$ is neutral and implementable. Then $R^{f}$ is reflexive and complete. Further, if $v(a_{1}) = x$ and $v(a_{2}) = y$, then

• $C^{f}(v) = \{a_{1}\}$ implies $xP^{f}y$ and $C^{f}(v) = \{a_{2}\}$ implies $yP^{f}x$, and

• $C^{f}(v) = A$ implies $xI^{f}y$.

Proof

$R^{f}$ is reflexive. For any $x \in U$, consider the valuation profile $v$ where $v(a_{1}) = v(a_{2}) = x$. Since $C^{f}(v)$ is non-empty and $f$ is neutral, $C^{f}(v) = A$. Hence, $x R^f x$.

$R^{f}$ is complete. For every $x, y \in U$, we can construct a valuation profile $v$ with $v(a_{1}) = x$ and $v(a_{2}) = y$. If $a_{1} \in C^{f}(v)$, then $x R^{f} y$. If $a_{1} \notin C^{f}(v)$, then $a_{2} \in C^{f}(v)$. Then, by neutrality, $a_{1} \in C^{f}(v')$, with $v'(a_{1}) = y$ and $v'(a_{2}) = x$. Therefore, $y R^{f} x$.

We now show that $C^{f}(v) = \{a_{1}\}$ implies $xP^{f}y$. Suppose $C^{f}(v) = \{a_{1}\}$. This clearly implies $xR^{f}y$. Assume for contradiction that we also have $y R^{f} x$. This implies that $a_{1} \in C^{f}(v')$, with $v'(a_{1}) = y$ and $v'(a_{2}) = x$. Then, by neutrality, $a_2 \in C^{f}(v)$, which gives us a contradiction.

A similar reasoning ensures that $C^{f}(v) = \{a_{2}\}$ implies $yP^{f}x$.

Finally, we show that $C^{f}(v) = A$ implies $x I^{f} y$. Suppose $C^{f}(v) = A$. This clearly implies $x R^{f} y$. Neutrality implies that $C^{f}(v') = A$, with $v'(a_{1}) = y$ and $v'(a_{2}) = x$. So, $y R^{f} x$, and hence, $x I^f y$. $\square$

Lemma 5

Suppose $f$ is an implementable and transitive allocation rule. Then, $f$ is unanimous if and only if it is neutral.

Proof

Suppose $f$ is neutral and implementable. Consider $x,y \in U$ such that $x_i > y_i$ for all $i \in N$. Then, due to neutrality, $C^f(v)=A$ if $v(a)=y$ for all $a \in A$. By PAD, $C^f(v')=\{a\}$ if $v'(a)=x$ and $v'(-a)=y$. Hence, $f$ is unanimous.

Now, suppose $f$ is unanimous and transitive. Assume for contradiction that $f$ is not neutral. Then, for some $x,y \in U$, we consider $v$ and $v'$ such that $v(a_1)=x=v'(a_2)$ and $v(a_2)=y=v'(a_1)$. We consider two cases.

Case 1. Assume for contradiction $C^f(v)=A$ but $C^f(v')=\{a_1\}$ (the argument does not change if $C^f(v')=\{a_2\}$). Since $a_2 \notin C^f(v')$, there is some $\epsilon \in \mathbb {R}^n_{++}$ such that $f(v'(a_1),v'(a_2)+2\epsilon )=a_1$. This implies that $C^f(v'(a_1),v'(a_2)+\epsilon )=\{a_1\}$. Choose $\epsilon ' \in \mathbb {R}^n_{++}$ such that $\epsilon '_i < \epsilon _i$ for all $i \in N$. Since $C^f(v)=A$, by PAD, $f(v(a_1)+\epsilon ,v(a_2)+\epsilon ')=a_1$. Moreover, by PAD, $C^f(v(a_1)+\epsilon , v(a_2)+\epsilon ')=\{a_1\}$. Now, consider the valuation profile $v''$ such that $v''(a_1)=v'(a_1)=y$ and $v''(a_2)=v(a_2)+\epsilon ' = y+\epsilon '$. By transitivity, $f(v'')=a_1$. But this contradicts the fact that $f$ is unanimous.

Case 2. Assume for contradiction $C^f(v)=\{a_1\}$ but $C^f(v') \ne \{a_2\}$ (the argument is unchanged if $C^f(v)=\{a_2\}$). If $C^f(v')=A$, then we can apply the argument in Case 1 to reach a contradiction (by interchanging the roles of $v$ and $v'$). Now, assume for contradiction $C^f(v')=\{a_1\}$. Since $a_2 \notin C^f(v)$, there is some sufficiently small $\epsilon \in \mathbb {R}^n_{++}$ such that $C^f(v(a_1),v(a_2)+\epsilon )=\{a_1\}$. Also, there is some $\epsilon '$ such that $\epsilon '_i < \epsilon _i$ for all $i \in N$ such that $f(v'(a_1)+\epsilon ,v'(a_2)+\epsilon ')=a_1$. Moreover, by PAD, $C^f(v'(a_1)+\epsilon ,v'(a_2)+\epsilon ')=\{a_1\}$. Consider a valuation profile $v''$ such that $v''(a_1)=v(a_1)=x$ and $v''(a_2)=v'(a_2)+\epsilon '=x+\epsilon$. By transitivity, $f(v'')=a_1$. But this contradicts the fact that $f$ is unanimous. $\square$

Finally, we show that if $f$ is implementable, transitive, and unanimous, then $R^f$ is transitive.

Lemma 6

If an implementable allocation rule $f$ is transitive and unanimous, then $R^f$ is an ordering.

Proof

By Lemmas 4 and 5, if $f$ is an implementable allocation rule that is transitive and unanimous, then $R^f$ is a well-behaved binary relation. We need to show that $R^f$ is transitive. We will show that $P^f$ and $I^f$ are each transitive, and this in turn will imply that $R^f$ is transitive.

$P^f$ is transitive. Consider $x,y,z \in U$ such that $x P^f y$ and $y P^f z$. Fix any $\epsilon \in \mathbb {R}^n_{++}$. By definition, if $v(a_1)=x$ and $v(a_2)=y$, then $f(v(a_1)+2\epsilon ,v(a_2)+\epsilon )=a_1$. Moreover, by PAD, $C^f(v(a_1)+2\epsilon ,v(a_2)+\epsilon )=\{a_1\}$. Similarly, if $v'(a_1)=y$ and $v'(a_2)=z$, then $C^f(v'(a_1)+\epsilon ,v'(a_2))=\{a_1\}$. Consider the valuation profile $v''$ such that $v''(a_1)=x$ and $v''(a_2)=z$. By transitivity, $f(v''(a_1)+2\epsilon ,v''(a_2))=a_1$. Hence, $a_1 \in C^f(v'')$.

Also, for some $\epsilon \in \mathbb {R}^n_{++}$, we have $C^f(v(a_1),v(a_2)+\epsilon )=\{a_1\}$ and for some $\epsilon ' \in \mathbb {R}^n_{++}$, we have $C^f(v'(a_1)+\epsilon , v'(a_2)+\epsilon ') = \{a_1\}$. Again, by transitivity, $f(v''(a_1),v''(a_2)+\epsilon ')=a_1$. Hence, $a_2 \notin C^f(v'')$. This shows that $x P^f z$.

$I^f$ is transitive. Consider $x,y,z \in U$ such that $x I^f y$ and $y I^f z$. Fix some $\epsilon \in \mathbb {R}^n_{++}$. By definition, if $v(a_1)=x$ and $v(a_2)=y$, then $C^f(v(a_1)+2\epsilon ,v(a_2)+\epsilon )=\{a_1\}$. Similarly, if $v'(a_1)=y$ and $v'(a_2)=z$, then $C^f(v'(a_1)+\epsilon ,v'(a_2))=\{a_1\}$. Consider the valuation profile $v''$ such that $v''(a_1)=x$ and $v''(a_2)=z$. By transitivity, $f(v''(a_1)+2\epsilon ,v''(a_2))=a_1$. Hence, $a_1 \in C^f(v'')$. A similar argument shows $a_2 \in C^f(v'')$. Hence, $x I^f z$. $\square$

An ordering $R$ on $U$ satisfies weak Pareto if for any $x, y \in U$ if $x_i > y_i$ for all $i \in N$, then $x P y$.

An ordering $R$ on $U$ satisfies translation invariance (tr-invariance) if for any $x,y \in U$ and $z \in \mathbb {R}^n$ such that $x+z,y+z \in U$, we have $x P y$ implies $(x+z) P (y+z)$ and $x I y$ implies $(x+z) I (y+z)$.

An ordering $R$ on $U$ satisfies continuity if for every $x \in U$, the sets $\{y \in U: x R y\}$ and $\{y \in U: y R x\}$ are closed in $U$.

Lemma 7

If $f$ is an implementable allocation rule such that $R^f$ is an ordering, then $R^f$ satisfies weak Pareto, tr-invariance, and continuity.

Proof

Since $f$ is unanimous, it is clear that $R^f$ satisfies weak Pareto.

Further, since $f$ satisfies PAD (by Lemma 3), $R^f$ satisfies tr-invariance. To see this, pick $x,y \in U$ and $z \in \mathbb {R}^n$ such that $x+z,y+z \in U$. Suppose $x P^f y$. Then, if $v(a_1)=x$ and $v(a_2)=y$ for every $\epsilon \in \mathbb {R}^n_{++}$, $f(v(a_1)+\epsilon ,v(a_2))=a_1$. Choose such an $\epsilon$. By PAD, for every $\epsilon ' \in \mathbb {R}^n_{++}$ such that $\epsilon '_i > \epsilon _i$ for all $i \in N$, we have $f(v(a_1)+z+\epsilon ',v(a_2)+z)=a_1$. Hence, $a_1 \in C^f(v(a_1)+z,v(a_2)+z)$. We also know that for some $\epsilon \in \mathbb {R}^n_{++}$, we have $f(v(a_1),v(a_2)+2\epsilon )=a_1$. By PAD, $f(v(a_1)+z,v(a_2)+z+\epsilon )=a_1$. Hence, $a_2 \notin C^f(v(a_1)+z,v(a_2)+z)$. This shows that $(x+z) P^f (y+z)$. A similar argument shows that $x I^f y$ implies $(x+z) I^f (y+z)$. Hence, $R^f$ satisfies tr-invariance.

We now show that $R^f$ satisfies continuity. To see this consider $x \in U$. We will first show that $\{y \in U: y R^f x\}$ is closed. Consider a sequence of points $\{x^k\}_k$ such that $x^k R^f x$ and the limit of this sequence is $z \in U$. Assume for contradiction that $x P^f z$. Hence, if $v(a_1)=x$ and $v(a_2)=z$, then $f(v(a_1),v(a_2)+\epsilon )=a_1$ for some $\epsilon \in \mathbb {R}^n_{++}$. Hence, $x R^f (z+\epsilon )$. Since the sequence converges to $z$, there is a point $z'$ in the sequence arbitrarily close to $z$ such that $z' R^f x$. Since $z'$ is arbitrarily close to $z$, we know that $(z+\epsilon ) P^f z'$. Hence, by transitivity of $R^f$, $(z+\epsilon ) P^f x$. This is a contradiction.

Next, we show that $\{y \in U: x R^f y\}$ is closed. Consider a sequence of points $\{x^k\}_k$ such that $x R^f x^k$ and the limit of this sequence is $z \in U$. Assume for contradiction that $z P^f x$. Interchanging the role of $x$ and $z$ in the previous argument, we get that $z R^f (x+\epsilon )$ for some $\epsilon \in \mathbb {R}^n_{++}$. Since the sequence converges to $z$, there is a point in the sequence $z'$ arbitrarily close to $z$ such that $x R^f z'$. Since $z'$ is arbitrarily close to $z$, by weak Pareto, $(x+\epsilon ) P^f z'$. This is a contradiction. $\square$

Proof of Theorem 3

Proof

Suppose $f$ is an implementable allocation rule that is unanimous and transitive. By Lemmas 6 and 7, the relation $R^f$ is an ordering on $U$ satisfying weak Pareto, tr-invariance, and continuity. Since $U$ is open and convex, by Mishra and Sen (2012), there exists $\lambda _1,\ldots ,\lambda _n \ge 0$ with $\lambda _i > 0$ for some $i \in N$, such that for every $x,y \in U$, $x R^f y$ if and only if $\sum _{i \in N}\lambda _i x_i \ge \sum _{i \in N}\lambda _i y_i$.

Now, consider any valuation profile $v$. Since $f(v) \in C^f(v)$, we know that $v(f(v)) R^f v(a)$ for all $a \in A$. Hence, $\sum _{i \in N}\lambda _i v_i(f(v)) \ge \sum _{i \in N}\lambda _i v_i(a)$. So, $f$ is a weighted efficient allocation rule.

Clearly, a weighted efficient allocation rule is transitive and unanimous. It is well known that if a weighted efficient allocation rule satisfies UIA, then it is implementable (Mishra and Sen 2012). $\square$

1.3 Proof of Theorem 2

We now use Theorem 3 to give a proof of Theorem 2. Before, we go into the details of the proof, we highlight the richness assumption of our domain. We assume that for every $i \in N$, the range of values for every alternative lies in an open interval $L_i$, which is unbounded from above. This implies that for every $i \in N$, $D_i=\mathbb {R}$,⁴ a fact which we will use extensively in our proofs. Denote by $D=D_1 \times \cdots \times D_n$, and note that $D=\mathbb {R}^n$.

We will use the standard range condition of Roberts (1979) for the proof.

Definition 11

An allocation rule $f$ satisfies non-imposition if for every $a \in A$, there exists $v \in V$ such that $f(v)=a$.

Fix an implementable allocation rule $f$. Suppose $f$ satisfies independence. We first observe that the choice set only depends on differences of valuations.

Lemma 8

Suppose $f$ is implementable. Then, for every pair of valuation profiles, $v,v'$ such that $\partial v_i = \partial v'_i$ for all $i \in N$, we have $C^f(v)=C^f(v')$.

Proof

Choose $v,v'$ such that $\partial v_i = \partial v'_i$ for all $i \in N$. Pick $a \in C^f(v)$ and $\epsilon \in \mathbb {R}^n_{++}$. By definition, $f(v(a)+\frac{\epsilon }{2},v(-a))=a$. By PAD and using the fact that $\partial v_i = \partial v'_i$ for all $i \in N$, we have $f(v'(a)+\epsilon ,v'(-a))=a$. Hence, $a \in C^f(v')$. Switching the role of $v$ and $v'$, we can show that if $a \in C^f(v')$, then $a \in C^f(v)$. As a result, $C^f(v)=C^f(v')$. $\square$

As a consequence of Lemma 8, we will define a mapping $c^f:D \rightarrow \{S \subseteq A: S \ne \emptyset \}$, such that for every $x \in D$, $c^f(x)=C^f(v)$, where $v$ is such that $\partial v_i = x_i$ for all $i \in N$.

Now, define $\kappa ^f$ as follows. For every $\alpha \in \mathbb {R}$, denote by $1_{\alpha }$ the vector in $\mathbb {R}^n$ such that each component of $1_{\alpha }$ has value $\alpha$. By our assumption on $D$, $1_0 \in D$. If $a_1 \in c^f(1_0)$, then let

$$\begin{aligned} \kappa ^f&= -\sup \{\alpha \in \mathbb {R}_+: a_1 \in c^f(1_{-\alpha })\}. \end{aligned}$$

If $a_1 \notin c^f(1_0)$, then let

$$\begin{aligned} \kappa ^f&= \inf \{\alpha \in \mathbb {R}_+: a_1 \in c^f(1_{\alpha })\}. \end{aligned}$$

Lemma 9

If $f$ is an implementable allocation rule satisfying non-imposition, then $\kappa ^f$ is a well defined real number.

Proof

Suppose $a_1\in c^f(1_0)$. By non-imposition (and using Lemma 8), we get that there is some $\beta \in \mathbb {R}$ such that $a_2 \in c^f(1_{-\beta })$. Since $a_1 \in c^f(1_0)$, by PAD, $\beta > \sup \{\alpha \in \mathbb {R}_+: a_1 \in c^f(1_{-\alpha })\} \ge 0$. This shows that $\kappa ^f$ exists since the set $\{\alpha \in \mathbb {R}_+: a_1 \in c^f(1_{-\alpha })\}$ is bounded. So, $\kappa ^f$ is a real number. A similar proof works if $a_1 \notin c^f(1_0)$. $\square$

The next lemma proves another property of $c^f$.

Lemma 10

If $f$ is an implementable allocation rule satisfying non-imposition, then $c^f(1_{\kappa ^f})=A$.

Proof

By our assumption on $D$, $1_{\kappa ^f} \in D$. First, we show that $a_1 \in c^f(1_{\kappa ^f})$. Assume for contradiction that $a_1 \notin c^f(1_{\kappa ^f})$. In that case, for all $v \in V$ with $\partial v_i = \kappa ^f$, we have $a_1 \notin C^f(v)$. This implies that there is some $\epsilon \in \mathbb {R}^n_{++}$ such that $f(v(a_1)+\epsilon ,v(a_2)) \ne a_1$. Hence, $a_1 \notin c^f(1_{\kappa ^f}+\frac{\epsilon }{2})$. But, by definition of $\kappa ^f$, for any $\epsilon ' \in \mathbb {R}^n_{++}$, $a_1 \in c^f(1_{\kappa ^f}+\epsilon ')$, and this is a contradiction.

Next, we show that $a_2 \in c^f(1_{\kappa ^f})$. Again, assume for contradiction that $a_2 \notin c^f(1_{\kappa ^f})$. As in the previous case, there is some $\epsilon \in \mathbb {R}^n_{++}$ and $v \in V$ such that $\partial v_i = \kappa ^f - \epsilon$ and $f(v) \ne a_2$. Hence, $a_2 \notin c^f(1_{\kappa ^f} - \frac{\epsilon }{2})$. But, by definition of $\kappa ^f$, for any $\epsilon ' \in \mathbb {R}^n_{++}$, $a_1 \notin c^f(1_{\kappa ^f}-\epsilon ')$. Since for any $\epsilon ' \in \mathbb {R}^n_{++}$, $c^f(1_{\kappa ^f}-\epsilon ')$ is non-empty, $a_2 \in c^f(1_{\kappa ^f}-\epsilon ')$. This is a contradiction. $\square$

Now, let $f$ be an implementable allocation rule satisfying non-imposition. Define a new allocation rule $\bar{f}$ as follows. For every $v \in V$, define the valuation profile $v^{tr}$ as follows: $\partial v_i^{tr} = \partial v_i + \kappa ^f$ for all $i \in N$. Note that by our assumption of $D$, $v^{tr} \in V$. Now, the allocation rule $\bar{f}$ is defined as:

$$\begin{aligned} \bar{f}(v)&= f(v^{tr}). \end{aligned}$$

We now establish an important lemma.

Lemma 11

If $f$ is an implementable allocation rule satisfying independence and non-imposition, then $\bar{f}$ is implementable, unanimous, and transitive.

Proof

Suppose $f$ is an implementable allocation rule satisfying independence and non-imposition. Let $(p_1,\ldots ,p_n)$ be the payments that implement $f$. For every $i \in N$ and for every $v_{-i}$, let $\bar{p}_i(v_i,v_{-i})=p_i(v^{tr}_i,v^{tr}_{-i}) - \kappa ^f$ if $f(v_i,v_{-i})=a_1$ and $\bar{p}_i(v_i,v_{-i})=p_i(v^{tr}_i,v^{tr}_{-i})$ if $f(v_i,v_{-i})=a_2$. We will show that $(\bar{p}_1,\ldots ,\bar{p}_n)$ implement $\bar{f}$. To see this, consider $i \in N$ and $v_{-i}$. Also, consider $v_i,v'_i$ such that $\bar{f}(v_i,v_{-i})=a_1$ and $\bar{f}(v'_i,v_{-i})=a_2$ (a similar proof works if $\bar{f}(v_i,v_{-i})=a_2$ and $\bar{f}(v'_i,v_{-i})=a_1$). Now,

$$\begin{aligned} v_i(a_1) - \bar{p}_i(v_i,v_{-i})&= v^{tr}_i(f(v^{tr}_i,v^{tr}_{-i})) - p_i(v^{tr}_i,v^{tr}_{-i}) \\&\ge v^{tr}_i(f(v'^{tr}_i,v^{tr}_{-i})) - p_i(v'^{tr}_i,v^{tr}_{-i}) \\&= v_i(\bar{f}(v'_i,v_{-i})) - \bar{p}_i(v'_i,v_{-i}). \end{aligned}$$

Hence, $(\bar{p}_1,\ldots ,\bar{p}_n)$ implement $\bar{f}$.

We show that $\bar{f}$ is unanimous. Consider a valuation profile $v$ such that $v(a_1)=x$, $v(a_2) = y$, and $x_i > y_i$ for all $i \in N$. We need to show that $\bar{f}(v)=a_1$. To see this, consider the valuation profile $v'$ such that $v'(a_1)=y=v'(a_2)$. But $c^{\bar{f}}(1_0)=c^f(1_{\kappa ^f})=A$. Hence, $C^{\bar{f}}(v')=A$, and using PAD, we get that $\bar{f}(v)=a_1$.

Finally, we show that $\bar{f}$ is transitive. For this, we consider $x,y,z \in D$ and $v,v',v''$ such that $v(a_1)=x=v''(a_1)$, $v(a_2)=y=v'(a_1)$, and $v'(a_2)=z=v''(a_2)$.

Suppose $C^{\bar{f}}(v)=\{a_1\}$ and $C^{\bar{f}}(v')=\{a_1\}$. We will show that $\bar{f}(v'')=a_1$. Note that since $C^{\bar{f}}(v')=\{a_1\}$, there is some $\epsilon \in \mathbb {R}^n_{++}$ such that $\bar{f}(v'(a_1)-\epsilon ,v'(a_2))=a_1$. To see this, suppose for all $\epsilon \in \mathbb {R}^n_{++}$, we have $\bar{f}(v'(a_1)-\epsilon ,v'(a_2))=a_2$. We know that for some $\epsilon ' \in \mathbb {R}^n_{++}$, we have $\bar{f}(v'(a_1),v'(a_2)+\epsilon ')=a_1$ (since $a_2 \notin C^{\bar{f}}(v')$). By PAD, $\bar{f}(v'(a_1)-\frac{\epsilon '}{2},v'(a_2))=a_1$. This is a contradiction. Similarly, there is an $\epsilon ' \in \mathbb {R}^n_{++}$ such that $f(v(a_1)-\epsilon ',v(a_2))=a_1$.

Now, choose an $\epsilon '' \in \mathbb {R}^n_{++}$ such that $\bar{f}(v'(a_1)-\epsilon '',v'(a_2))=a_1$ and $\bar{f}(v(a_1)-\frac{\epsilon ''}{2},v(a_2))=a_1$—note that such an $\epsilon ''$ can be chosen. In that case, by independence, either $\bar{f}(v(a_1),v'(a_2))=a_1$ or $\bar{f}(v'(a_1)-\frac{\epsilon ''}{2},v(a_2))=a_1$. Since $v'(a_1)=v(a_2)=y$ and $\bar{f}$ is unanimous, the latter is not possible. Hence, $\bar{f}(v'')=\bar{f}(v(a_1),v'(a_2))=a_1$.

A similar argument shows if $C^{\bar{f}}(v)=\{a_2\}$ and $C^{\bar{f}}(v')=\{a_2\}$, then $\bar{f}(v'')=a_2$. $\square$

This leads to the proof of Theorem 2.

Proof of Theorem 2

Proof

Suppose $f$ is an implementable allocation rule. If $f$ does not satisfy non-imposition, then clearly it is an affine maximizer. Now, suppose $f$ satisfies non-imposition and independence. Then, by Lemma 11, $\bar{f}$ is an implementable allocation rule which is unanimous and transitive. By Theorem 3, there exists non-negative weights $\lambda _1,\ldots ,\lambda _n$ such that for all $v$, if $\sum _{i \in N}\lambda _i \partial v_i > 0$, then $\bar{f}(v)=a_1$ and if $\sum _{i \in N}\lambda _i \partial v_i < 0$, then $\bar{f}(v)=a_2$. Furthermore, we can choose these weights, without loss of generality, such that $\sum _{i \in N}\lambda _i=1$.

Now, using the definition of $\bar{f}$, we get that if $\sum _{i \in N}\lambda _i \partial v_i > \kappa ^f$, then $f(v)=a_1$ and if $\sum _{i \in N}\lambda _i \partial v_i < \kappa ^f$, then $f(v)=a_2$. Setting $\gamma (a_1)=\kappa ^f$ and $\gamma (a_2)=0$, we get that $f$ is an affine maximizer.

For the converse, Lemma 2 shows that an affine maximizer satisfies independence. It is well known that an affine maximizer is implementable by generalized Groves payments if it satisfies UIA. $\square$

1.4 Independence of Axioms used in Theorem 1

We give three examples below to illustrate the requirement of the conditions in Theorem 1. The three examples below refer to the version of Theorem 1 with condition Ca, but can be easily adapted for the version with condition Cb.

Example 3

This example illustrates that there are implementable affine maximizers when $D_i$s are interval which violate agent sovereignty. Hence, the agent sovereignty condition is necessary for our characterization.

Let $D_{i}=[0,1] \ \forall i \in N$ with $n>2$ and $f(v) = \arg \max _{a \in A} \sum _{i \in N} v_{i}(a)$, with ties broken in favor of $a_1$. This allocation rule violates agent sovereignty. Indeed, fix $i \in N$ and note that if $v_{j}(a_1)=0, v_{j}(a_2)=1$ for all $j \ne i$, then $\not \exists ~v_{i} : f(v_i,v_{-i})=a_1$. However, $f$ is clearly monotone and, hence, implementable.

Example 4

This example illustrates that there are implementable allocation rules satisfying agent sovereignty when $D_i$s are not intervals. Hence, the requirement that $D_i$s are intervals is necessary for our characterization.

Let $D_{i}= \mathbb {N}~\forall i \in N$ with $n>2$, where $\mathbb {N}$ is the set of non-negative integers. Let $f(v) = \arg \max _{a \in A} \sum _{i \in N} v_{i}(a)$, with ties broken in favor of $a_1$. This allocation rule is clearly monotone, and hence, implementable. It also satisfies agent sovereignty. But the domain is not an interval.

Example 5

The following example illustrates that there are non-implementable allocation rules satisfying agent sovereignty in domains where $D_i$s are intervals. Hence, agent sovereignty does not imply implementability in such domains.

Let $D_{i}=(0,\infty ) \ \forall i \in N$ with $n>2$ and $f(v) = \arg \max _{a \in A} \Pi _{i \in N} v_{i}(a)$, with ties broken in favor of $a_1$. Allocation rule $f$ satisfies agent sovereignty because the domain is unbounded above. Monotonicity (and hence Implementability) is violated. Indeed, suppose $n=2$. Fix $v_2(a_1)=9,v_2(a_2)=1$. Consider $v_1(a_1)=0.1,v_1(a_2)=1$ and $v'_1(a_1)=1,v'_1(a_2)=2$. Note that $f(v_1,v_2)=a_2$ and $v_1(a_2)-v_1(a_1) = 0.9 < 1 = v'_1(a_2) - v'_1(a_1)$. However, $f(v'_1,v_2)=a_2$, violating monotonicity.