On group strategyproof and optimal object allocation

Abstract

We consider a two-agent, single indivisible object allocation problem. We focus on continuous mechanisms that satisfy agent sovereignty, and investigate implications of group strategyproofness. In particular, we provide an explicit characterization of the strategyproof mechanisms and show that there are non-affine maximizer mechanisms that do not belong to the class characterized by Roberts (North-Holland, 1979). Further, we show that there are no budget-balanced strategyproof mechanisms. Also, we obtain an impossibility for existence of strong group strategyproof mechanism. We find that this impossibility goes away upon relaxing our notion of group strategyproofness, and consequently, present a class of weak group strategyproof mechanisms. Finally, we completely characterize the class of feasible strategyproof mechanisms satisfying individual rationality, and show that there are no optimal strategyproof expected revenue maximizing mechanisms under a general class of well behaved type distributions.

1 Introduction

We consider the standard object allocation model where a single indivisible object is allocated among two agents who have private non-negative valuations for the object and quasi-linear preferences over the object and money. An example of such a situation could be a bilateral bargaining setting where two agents, a seller and a buyer, negotiate over when and how to trade an indivisible object. Similar examples can also be seen in situations where a license, a house, a plot of land or an airport landing right, etc. is to allotted.

We focus on reasonable mechanisms in the sense that they are well behaved (satisfying a mild notion of continuity) and satisfy agent sovereignty (which requires that every agent have some ability to affect the allocation outcome of mechanism). In the class of such mechanisms, we provide an explicit complete characterization of the strategyproof mechanisms, similar to that obtained in Roberts (1979). However, unlike Roberts (1979), this class contains non-affine maximizer mechanisms. This is clearly because in the present setting there are only two alternatives and the domain of valuations is restricted. We then look for stronger notions of non-manipulability, in terms of strong and weak (pairwise) group strategyproofness, that eliminate group level incentives to misreport. We find that there are no strong group strategyproof mechanisms. Instead, we provide a class of mechanisms that are weak group strategyproof. To the best of our knowledge, there are no papers that characterize group strategyproof mechanisms in the present setting.

Further, in line with Jackson (2003), we take a novel approach of using budget balance as a yardstick for efficiency and look for strategyproof budget-balanced mechanisms. Unfortunately, we find no mechanisms that are budget balanced as well as strategyproof. Consequently, we completely characterize the class of feasible strategyproof mechanisms that satisfy individual rationality.¹ Finally, we look for optimal mechanisms that maximize expected payments for the object (under an assumed common prior distribution) in the class of feasible strategyproof mechanism that satisfy individual rationality. We find a strong negative result. That is, there does not exist an optimal strategyproof mechanism when valuations are independently (and possibly non-identically) distributed according to any increasing differentiable cumulative distribution.

On the issue of strategyproofness of mechanisms, the papers that are closest to ours are Mishra and Marchant (2015) and Mishra and Quadir (2014). The former paper investigates strategyproof allocation rules in a two-alternative framework with quasi-linear utilities. Their characterization result applies to the present setting as the number of agents is two. However, our characterization is independent of theirs as we focus on strategyproof mechanisms, whereas they focus on strategyproof rules. The latter paper provides characterization of strategyproof and non-bossy allocation rules in a different setting where objects may remain unallocated and agents have strictly positive valuations. Unlike our paper, none of these papers pursue issues of budget balance, group strategyproofness or optimality.

On the issue of budget-balanced strategyproof mechanisms, the papers closest to ours are Hagerty and Rogerson (1987), Drexl and Kleiner (2015) and Shao and Zhou (2016). The first paper shows that posted-price mechanisms are the only mechanisms that satisfy differentiability, strategyproofness, budget-balancedness, individual rationality, and a technical property involving step functions. The second paper, too, reports a similar result where the only strategyproof budget balanced deterministic mechanism satisfying individual rationality is either a posted-price mechanism or an option-price mechanism.² The third paper updates the findings of Drexl and Kleiner (2015) and finds an identical result by replacing individual rationality with a stronger notion of regularity of type distributions.

In this paper, our supposition of agent sovereignty eliminates such posted-price or option price mechanisms. In comparison, we find that they there are no continuous strategyproof budget-balanced deterministic mechanisms that satisfy agent sovereignty. This confirms the negative results cited above, as upon elimination of posted-price and option-price mechanisms, our investigation of deterministic mechanisms under weaker technical restrictions yields no strategyproof budget-balanced mechanism.³

2 Model and leading definitions

Consider a two agent model with set of agents $N=\{1,2\}$ and an indivisible object. Each agent i has an independent private valuation $v_i \ge 0$ for the object. A mechanism $\mu$ is a tuple $(d,\tau )$ such that at any reported profile of valuations $v \in {\mathbb {R}}^N_+$, each agent i is allocated a transfer $\tau _i(v) \in {\mathbb {R}}$ and a decision $d_i(v) \in \{0,1\}$ such that $\sum _{i\in N} d_i(v)=1$. We follow the notation where $d_i(v) = 1$ implies that agent i gets a object, while $d_i(v) = 0$ stands for i not getting the object. Note that we assume that the object is allocated at each profile of reported valuations.⁴ Define w(v) to be the agent getting the object at any profile v.⁵ The utility to agent i with a true valuation of $v_i$ at any reported profile $v' \in {\mathbb {R}}^N_+$, from the mechanism $\mu$ is given by $u(d_i(v'), \tau _i(v'); v_i) = v_i d_i(v') + \tau _i(v')$. Let $\forall \, i\in N$, $\forall \, S\subseteq N$, $\forall \,v\in {\mathbb {R}}^N_+$, $v_{-i}:=(v_1,\ldots ,v_{i-1},v_{i+1},\ldots ,v_n)$, $v_{-S}:=(v_i)_{i\in N\setminus S}$ and $v_{S}:=(v_i)_{i\in S}$. Since $N=\{1,2\}$ in our simple setting, $v_{-i}=v_j$ for all $i\ne j \in N$.

Note that, a priori, a mechanism may have a peculiar allocation decision rule that gives the object to some agent j, whenever she reports some value $\theta > 0$, irrespective of what the other agent $i \ne j$ bids. It could also be that the object is given to i, whenever j reports $\theta$, irrespective of what i bids. In other words, the mechanism treats some agent $i \in N$ as a dictator, whenever any one of the agents reports $\theta$. Two examples of such mechanisms are the aforementioned posted-price mechanisms and option-price mechanisms. In our setting, for any valuation profile v, the former implies existence of a price ${\bar{p}}^P$ such that $d(v) = (0,1)$ if and only if $v_1\le {\bar{p}}^P, v_2 \ge {\bar{p}}^P$, while the latter implies existence of a price ${\bar{p}}^O$ such that $d(v)=(0,1)$ if and only if $v_2 \ge {\bar{p}}^O$. It is easy to see that in both these cases, if $v_2 \in \left[ 0, \min \{{\bar{p}}^P, {\bar{p}}^O\}\right)$, agent 1 gets the good irrespective of what she reports, that is, agent 1 becomes a dictator who must be allocated the good irrespective of what she reports. It is this undesirable feature that leads Hagerty and Rogerson (1987) to “interpret this result as essentially negative.”

In this paper, we exclude such arbitrary mechanisms from our purview of study. Instead, we focus on mechanisms that satisfy agent sovereignty in the following manner: every agent i can change the allocation decision by unilaterally changing her report, if the other agent j reports a positive value. That is, every agent can exert some influence on the mechanism allocation decision, irrespective of what other agents are bidding.⁶

Definition 1

A mechanism $\mu =(d,\tau )$ satisfies agent sovereignty (AS) if for all $i\ne j \in N$ and all $v \in {\mathbb {R}}^N_{++}$, $\exists \; v'_i \ge 0$ such that

$$\begin{aligned} d_i(v) \ne d_i(v'_i,v_j). \end{aligned}$$

Further, we impose a mild technical restriction of continuity, on the mechanisms we study. It requires that for any sequence of profiles, whenever the allocation decision of an agent i is not preserved in limit, the transfer assigned to i at the limit profile is such that she is indifferent between getting or not getting the object.

Definition 2

A mechanism $(d,\tau )$ is continuous (C) if for any $\zeta \in \{0,1\}$, any $i\in N$ and any sequence of profiles $\{v^k\}$ that converges to ${\tilde{v}}$, whenever $d_i(v^k)=\zeta$ for all k,

$$\begin{aligned} d_i({\tilde{v}}) \ne \zeta \implies u((1, \tau _i({\tilde{v}}));{\tilde{v}}_i)=u((0, \tau _i({\tilde{v}}));{\tilde{v}}_i). \end{aligned}$$

Let $\Gamma$ be the class of mechanisms that satisfy agent sovereignty and continuity. In this paper, we focus our attention on the mechanisms in $\Gamma$ that satisfy desirable strategic axioms.

In particular, we study the popular strategic axiom of strategyproofness, which eliminates any incentive to misreport on an individual level. It is defined as follows.

Definition 3

A mechanism $\mu = (d,\tau )$ satisfies strategyproofness (SP) if $\forall \, i\in N$, $\forall \, v,v'\in {\mathbb {R}}^N_+$ such that $v_{-i} = v'_{-i}$,

$$\begin{aligned} u(d_i(v),\tau _i(v);v_i) \ge u(d_i(v'),\tau _i(v');v_i). \end{aligned}$$

3 Results

We start by stating by presenting a modification of a well-known characterization of strategyproof mechanisms.

Result 1

Any continuous mechanism $\mu = (d, \tau )$ satisfies AS and SP only if $\forall \, i \ne j \in N$ and $\forall \, v_j\ge 0$, there exist real-valued functions $K^{\mu }_i:{\mathbb {R}}_+ \mapsto {\mathbb {R}}$ and $T^{\mu }_i:{\mathbb {R}}_+ \mapsto {\mathbb {R}} \cup \{\infty \}$ such that

• (1) $d_i(v)=\left\{ \begin{array}{ll} 1 &{} \text{ if } v_i > T^{\mu }_i(v_j)\\ 0 &{} \text{ if } v_i < T^{\mu }_i(v_j) \end{array} \right. \;\;\; \text{ and } \;\;\; \tau _i(v)=\left\{ \begin{array}{ll} K^{\mu }_i(v_j) - T^{\mu }_i(v_j) &{} \text{ if } d_i(v)=1\\ K^{\mu }_i(v_j) &{} \text{ if } d_i(v)=0. \end{array} \right.$

• (2) For all $i\in N$ and all $x>0$, $T_i^\mu (x) \in [0,\infty )$.

Proof

Condition (1) follows from Proposition 9.27 in Nisan (2007) and Lemma 1 in Mukherjee (2014). Now, any mechanism which satisfies SP would violate AS if image of $T_i^\mu (.)$ function (for any $i\in N$) is unbounded or negative at some positive point in the real line. That is, if there exists a $\theta \in (0,\infty )$ such that $T_i^\mu (\theta )$ is unbounded, then the agent $j\ne i$ gets the object whenever she reports her valuation to be $\theta$, irrespective of what i reports. Similarly, if there exists a $\beta \in (0,\infty )$ such that $T_i^\mu (\beta )$ is negative, then agent i gets the object whenever $j \ne i$ reports her valuation to be $\beta$, irrespective of what i reports. Both these cases violate AS. Thus, for any mechanism that satisfies SP and AS, for all $i\in N$, $T_i^\mu (x) \in [0,\infty )$ for all $x>0$. $\square$

Note that Result 1 allows for arbitrary tie-breaking in allocation decision of the object at any profile $v\in {\mathbb {R}}^N_+$ such that $\forall \, i \ne j \in N$ with $v_i=T^\mu _i(v_j)$, $v_j=T^\mu _j(v_i)$. In this paper, without loss of generality, we assume a lexicographic tie-breaking rule [as in Sprumont (2013)] where the linear order $1\succ 2$ is used to break ties among agents. That is, for any profile v such that $v_j\le T^\mu _j(v_i)$ for all $j\in N$,

$$\begin{aligned} d_1(v) =1\Longleftrightarrow v_1=T^\mu _1(v_2). \end{aligned}$$

The following theorem characterizes the class of strategyproof mechanisms in $\Gamma$.⁷

Theorem 1

Any mechanism $\mu = (d, \tau ) \in \Gamma$satisfies SP if and only if there exist functions, $K^\mu _i:{\mathbb {R}}_+ \mapsto {\mathbb {R}}$and $T^\mu _i:{\mathbb {R}}_+ \mapsto {\mathbb {R}}$, such that

• (1) For all $i\in N$, if $d_i(v)=1$, then $i \in \text{ argmax }_{j \in N} (v_j - T^\mu _j(v_i))$.

• (2) For all $i\in N$, $\tau _i(v)=\left\{ \begin{array}{ll} K^{\mu }_i(v_j) - T^{\mu }_i(v_j) &{} \text{ if } d_i(v)=1\\ K^{\mu }_i(v_j) &{} \text{ if } d_i(v)=0 \end{array} \right.$

• (3) For all $x\ge 0$, $T^\mu _1(T^\mu _2(x)) = T^\mu _2(T^\mu _1(x)) = x$.

• (4) For all $i\in N$, $T_i^\mu$is a strictly increasing continuous function.

• (5) For all $i\in N$, $T^\mu _i(0)=0$.

Proof

See Appendix. $\square$

Remark 1

Note that a special class of strategyproof mechanisms is one, where $T^\mu _i(x)=x$ for all $x \ge 0$ and all $i\in N$. This is the the popular class of VCG mechanisms that have an efficient (welfare maximizing) decision rule.⁸ However, the class of mechanisms characterized in Theorem 1, allows for mechanisms $\mu$ such that $T_1^\mu (x)=x^k$ and $T^\mu _2(x)={x}^{\frac{1}{k}}$, where $k \in {\mathbb {N}}$. Note that whenever $k>1$, these strategyproof mechanisms are not affine maximizer mechanisms of the kind characterized by Roberts (1979). This occurs because the popular Robert’s theorem fails to hold in the present (restricted domain) setting where agents are can only have non-negative valuations for the object.

Note that a strategyproof mechanism guarantees that revealing the true valuation is a weakly dominant strategy for each agent in every simultaneous move game that ensues from the mechanism. But there remains the possibility of agents forming groups and misreporting together. Ideally a mechanism should also be immune to such group misreporting. And so, to study such mechanisms, we define below a stronger notion of truth-telling: strong pair-wise group strategyproofness.⁹

To state this stronger notion of strategyproofness, we introduce the following notation. For any $v\in {\mathbb {R}}^N_+$ and for any non-empty $S \subseteq N$, define $v^\prime \in {\mathbb {R}}^N_+$ to be an S-profile of v if $\forall \; i \not \in S, \, v_i=v'_i$. The following definition states that if a mechanism satisfies strong pair-wise group strategyproofness, then no matter how the two agents misreport: either one of them is worse off, or none of them are better off.

Definition 4

A mechanism $\mu =(d,\tau )$ satisfies strong pair-wise group strategyproofness (SPGS) if $\forall \, v \in {\mathbb {R}}^N_+$, $\not \exists \; S \subseteq N$ such that $|S| \le 2$ and

$$\begin{aligned} u(d_i(v),\tau _i(v); v_i) \le u(d_i(v'),\tau _i(v');v_i), \forall \, i \in S, \end{aligned}$$

and

$$\begin{aligned} u(d_j(v),\tau _j(v); v_j) < u(d_j(v'),\tau _j(v');v_j) \text{ for } \text{ some } j\in S, \end{aligned}$$

where $v'$ is an S-profile of v.

The following corollary of Theorem 1 states that there exists no reasonable mechanism that eliminates the incentive for the two agents to misreport jointly.

Corollary 1

There is no mechanism $\mu =(d,\tau ) \in \Gamma$that satisfies SPGS.

Proof

The result trivially follows from Result 1 and (4) in Theorem 1, as at any type profile v, both agents can deviate as a group in a manner where the agent $j \ne w(v)$ reduces her report unilaterally—which would make the winning agent w(v) strictly better off (as the price that she must pay for the object post-deviation decreases)—while j’s own utility remains unchanged post-deviation. $\square$

Remark 2

This impossibility with respect to SPGS is very interesting. Previously, it has been noted in allocation problems with money that there are no mechanisms that satisfy both efficiency¹⁰ and SPGS (by Mitra and Mutuswami (2011) and (Mukherjee 2013, 2014 )). However, in our paper, we find that even without efficiency, it is impossible to find a reasonable mechanism that satisfies SPGS.

In the related literature, non-existence of mechanisms satisfying strong pairwise group strategyproofness has led to investigation into weaker notions of group level truth-telling. The most popular notion is that of weak pair-wise group strategyproofness.¹¹ This weaker notion requires that no matter how the pair of agents misreport, at least one of them is not strictly better off. As is evident from the definition below, any mechanism satisfying SPGS, also satisfies weak pair-wise group strategyproofness (and of course, satisfies strategyproofness).

Definition 5

A mechanism $\mu = (d,\tau )$ satisfies weak pair-wise group strategyproofness (WPGS) if $\forall \, v \in {\mathbb {R}}^N_+$, $\not \exists \, S \subseteq N$ such that $|S| \le 2$ and

$$\begin{aligned} u(d_i(v), \tau _i(v);v_i) < u(d_i(v'), \tau _i(v');v_i), \forall \; i \in S, \end{aligned}$$

where $v'$ is an S-profile of v.

Unlike the impossibility of existence of reasonable mechanisms that satisfy SPGS in Corollary 1, we find that there exists the following class of mechanisms that satisfy weak pair-wise group strategyproofness.

Theorem 2

A mechanism $\mu =(d,\tau ) \in \Gamma$satisfies WPGS if for all $i \in N$such that for all $x\ge 0$,

$$\begin{aligned} K^\mu _i(x)= C_i+ \min \{T^\mu _i(x), \eta \}, \end{aligned}$$

where $C_i \in {\mathbb {R}}$for all $i\in N$and either $\eta =\infty$or $\eta \in \{x\ge 0| T^\mu _i(x)=x, \forall \, i\in N\}$.

Proof

See appendix. $\square$

Given the impossibility of efficient and strong pair-wise group strategyproof mechanisms described in Remark 1, we must consider the possibility of existence of such mechanisms if one considers an alternate notion of efficiency: budget balance.¹² Informally, a mechanism is budget balanced if there is never any excess or shortage of resources in its execution. The formal definition is as follows.

Definition 6

A mechanism $\mu = (d,\tau )$ satisfies budget balance (BB) if for all $v\in {\mathbb {R}}^N_+$,

$$\begin{aligned} \sum _{i\in N} \tau _i(v)=0. \end{aligned}$$

Unfortunately, as Corollary 2 shows that any reasonable mechanism that satisfies budget balance fails to satisfy even the weakest notion of truth-telling entailed by strategyproofness.

Corollary 2

There is no mechanism $\mu =(d,\tau ) \in \Gamma$that satisfies SP and BB.

Proof

Suppose there exists a mechanism $\mu \in \Gamma$ that is budget balanced and strategyproof. Therefore, from Result 1, it follows that $\forall \;(x,y) \ge 0$,

$$\begin{aligned} \begin{array}{ll} K^\mu _1(y)+K^\mu _2(x)=T^\mu _1(y) &{} \hbox { if}\ d(x,y)=(1,0)\\ K^\mu _1(y)+K^\mu _2(x)=T^\mu _2(x) &{} \hbox { if}\ d(x,y)=(0,1). \end{array} \end{aligned}$$

By Theorem 1, for all $i \in N$, $T^\mu _i(0)=0$ and $T_i(z)> 0, \forall \, z >0$. Therefore, by Result 1, $d(z,0) = (1,0)$ and $d(0,z)=(0,1)$ for all $z>0$. Hence, the equations above imply that for all $z>0$, $K^\mu _i(z)$ is constant for all i. Therefore, $T^\mu _i(z)$ is constant for all $z>0$ and all i, and hence, a contradiction to Theorem 1. Thus, the result follows. $\square$

Corollary 2 confirms the flavour of impossibility in results of Hagerty and Rogerson (1987), Drexl and Kleiner (2015) and Shao and Zhou (2016). That is because Corollary 2 shows that upon excluding unfair mechanisms that violate agent sovereignty, such as posted-price or option price mechanisms: we find no other budget-balanced strategyproof mechanism under weaker technical restrictions. In an unpublished working paper, De and Mitra (2019) also find a similar result in context of sequencing problems where they show that budget balance requires more than two participants in a strategyproof mechanism.

Since Corollary 2 shows that there are no reasonable mechanisms that are strategyproof and budget balanced, in the following theorem, we look to weaken the notion of budget balance to the notion of feasibility (which requires only that a mechanism never lead to a deficit of resources)—and look for feasible strategyproof mechanisms. The following is the formal definition of feasibility.

Definition 7

A mechanism $\mu = (d,\tau )$ satisfies feasibility (F) if for all $v\in {\mathbb {R}}^N_+$,

$$\begin{aligned} \sum _{i\in N} \tau _i(v) \le 0, \end{aligned}$$

Note, however, that the class feasible mechanisms may contain unfair mechanisms that allow for possible extraction of exorbitant taxes from agents participating in a mechanism. Such mechanisms would not only be unreasonable but also be impractical because participating agents, when faced with such mechanisms, may choose to not participate—defeating the whole purpose of allocation exercise. Hence, in our investigation of feasible mechanisms, we look for individually rational mechanisms, which ensure that each participating agent receives a non-negative utility irrespective of the reported valuations. The following is the formal definition of individual rationality.

Definition 8

A mechanism $(d,\tau )$ satisfies individual rationality (IR) if for all $i\in N$ and all $v\in {\mathbb {R}}^N_+$,

$$\begin{aligned} u(d_i(v),\tau _i(v); v_i) \ge 0. \end{aligned}$$

The following theorem completely characterizes the class of strategyproof, feasible and individually rational mechanisms in $\Gamma$. We first define a class of pairs of functions, and then present this result:

$$\begin{aligned} {\mathcal {F}}:=\left\{ (f,g) \Bigg \vert \;\; \begin{array}{l} f(.), g(.)\, \hbox {are strictly increasing continuous bijections over domain} \;[0,\infty )\; \hbox {such}\\ \hbox {that}\; f(0)=0\; \hbox {and} \;g\left( x\right) = f^{-1}\left( x\right) \; \hbox {for all} \;x \ge 0. \end{array} \right\} . \end{aligned}$$

Theorem 3

A mechanism $\mu =(d,\tau ) \in \Gamma$satisfies SP, IR and F, if and only if for all $i\in N$and all $v\in {\mathbb {R}}^N_+$,

$$\begin{aligned} d_i(v)=1 \implies i \in \text{ argmax }_{j \in N} (v_j - T^\mu _j(v_i)), \end{aligned}$$

and

$$\begin{aligned} \tau _i(v)=\left\{ \begin{array}{ll} - T^{\mu }_i(v_j) &{} \text{ if } d_i(v)=1\\ 0 &{} \text{ if } d_i(v)=0, \end{array} \right. \end{aligned}$$

where $\left( T^\mu _1(.), T_2^\mu (.)\right) \in {\mathcal {F}}$.

Proof

For proof of sufficiency, fix any mechanism ${\hat{\mu }}=({\hat{d}},{\hat{\tau }}) \in \Gamma$ that satisfies the properties mentioned in the statement of theorem. It is easy to check that ${\hat{\mu }}$ belongs to the class of mechanisms characterized by Theorem 1 (obtained by setting the function $K_i^{{\hat{\mu }}}(x) = 0$ for all $i\in N$ and $x \ge 0$), and so, satisfies SP. Note that ${\hat{\mu }}$ assigns non-positive transfers to all agents at all reported type profiles, and so, it satisfies F. Further, at any reported valuation profile v, if any agent i is assigned the object by ${\hat{\mu }}$, then Theorem 1 implies that $T_i^{{\hat{\mu }}}(v_j)\le v_i$, which implies that i’s utility from getting the object is non-negative. Since utility to such any agent i continues is 0 whenever ${\hat{\mu }}$ does not assign the object to her, we can infer that ${\hat{\mu }}$ satisfies IR. Also, note that by construction of ${\mathcal {F}}$, $T_i^{{\hat{\mu }}}(.)$ is a strictly increasing bijection over $[0,\infty )$ for all $i\in N$, and so, for all $x > 0$, $T_i^{{\hat{\mu }}}(x) \in (0,\infty )$, which implies that ${\hat{\mu }}$ satisfies AS. Finally, fix any sequence of profiles $\{v^n\}$ in ${\mathbb {R}}_+^N$ that converges some limit profile ${\bar{v}}$, and suppose, without loss of generality, that ${\hat{d}}(v^n)=(1,0)$ for all n. Then by Result 1, $v_1 \ge T_1^{{\hat{\mu }}}(v_2^n), v_2 \le T_2^{{\hat{\mu }}}(v_1^n), \forall \, n$. Now, by construction of ${\mathcal {F}}$, $T_i^{{\hat{\mu }}}(.)$ is continuous for all $i\in N$, and so, in limit ${\bar{v}}_1 \ge T_1^{{\hat{\mu }}}({\bar{v}}_2), {\bar{v}}_2 \le T_2^{{\hat{\mu }}}({\bar{v}}_1)$. Further, construction of ${\mathcal {F}}$ implies that; ${\bar{v}}_1 > T_1^{{\hat{\mu }}}({\bar{v}}_2)\implies {\bar{v}}_2 < T_2^{{\hat{\mu }}}({\bar{v}}_1)$, and ${\bar{v}}_1 = T_1^{{\hat{\mu }}}({\bar{v}}_2) \implies {\bar{v}}_2 = T_2^{{\hat{\mu }}}({\bar{v}}_1)$. Thus, if ${\hat{d}}({\bar{v}}) \ne (1,0)$, then $u((1, {\hat{\tau }}_1({\bar{v}}));{\bar{v}}_1)= {\bar{v}}_1 - T_1^{{\hat{\mu }}}({\bar{v}}_2) = 0 = u((0, {\hat{\tau }}_1({\bar{v}}));{\bar{v}}_1)$, and $u((1, {\hat{\tau }}_2({\bar{v}}));{\bar{v}}_2)= {\bar{v}}_2 - T_2^{{\hat{\mu }}}({\bar{v}}_1) = 0 = u((0, {\hat{\tau }}_2({\bar{v}}));{\bar{v}}_2)$. This establishes continuity of ${\hat{\mu }}$. Thus, the proof of sufficiency follows.

To prove necessity, fix any mechanism $\mu = (d,\tau ) \in \Gamma$ that satisfies SP, IR and F. Note that Theorem 1 implies that $\left( T^\mu _1(.), T_2^\mu (.)\right) \in {\mathcal {F}}$. Therefore, it is easy to see, given Theorem 1, we simply need to show that $K_i^\mu (z)=0$ for all $z \ge 0$ to establish this result. Recall that Theorem 1 implies that for any $z>0$, $T_i^\mu (0) = 0 < T_i^\mu (z)$, and so, $u(d_i(0,v_j),\tau _i(0,v_j);0) = K_i^\mu (v_j)$ whenever $v_j \ge 0$.¹³ Therefore, IR implies that $\mathbf {(a)}\;K_i^\mu (z) \ge 0$ for all $z \ge 0$, and all i. And so, F implies that when reported profile is (0, 0), the condition $0\le K^\mu _1(0)+K^\mu _2(0) \le 0$ holds. Thus, $K^\mu _i(0)=0$ for all $i\in N$. Now, consider a profile $(x,T^\mu _2(y))$, where $x>y\ge 0$. By Result 1, $d(x,T^\mu _2(y))=(1,0)$. Therefore, by feasibility, $K^\mu _1(T^\mu _2(y)) - T^\mu _1(T^\mu _2(y)) +K^\mu _2(x) \le 0$, which, by condition (3) of Theorem 1 and (a) implies that $0\le K^\mu _1(T^\mu _2(y))+K^\mu _2(x) \le y$. Note that this equation holds for all $y\in [0,x)$ and so, by the standard “squeeze” property of limits,

$$\begin{aligned} K^\mu _2(x) = - \lim _{y \rightarrow 0+} K^\mu _1(T^\mu _2(y)). \end{aligned}$$

Now, by (a), $\lim _{y \rightarrow 0+} K^\mu _1(T^\mu _2(y)) \ge 0$, which implies that $K^\mu _2(x) = 0$. Arguing in a similar manner for the profile $(T^\mu _1(y),x)$, we get that $K^\mu _1(x)=0$. Since $x>0$ was chosen arbitrarily, we get that $K_i^\mu (x) = 0$ for all i and $x \ge 0$. $\square$

The following corollary emphasises an interesting connection of the mechanisms characterized by Theorem 3 to group strategyproofness.

Corollary 3

If $\mu =(d,\tau ) \in \Gamma$satisfies SP, IR and F, then it satisfies WPGS.

Proof

The proof easily follows from noting that mechanisms characterized by Theorem 3 belong to the class described by Theorem 2.¹⁴$\square$

Theorem 3 completely characterizes the class of mechanisms in $\Gamma$ that are feasible, strategyproof and satisfy IR. It requires that no positive transfers be made irrespective of whether an agent wins the object or not. Further, Corollary 2 shows that these mechanisms can never be budget balanced. Therefore, the question arises as to whether an expected revenue maximizing risk neutral seller/planner may pick, from the class of mechanisms characterized in Theorem 3, an optimal mechanism. As shown in the proposition below, for a general class of beliefs about type distribution, there does not exist a revenue maximizing optimal strategyproof mechanism satisfying IR in $\Gamma$.

Theorem 4

Let the valuation of each agent i, $v_i$be distributed independently according to a differentiable strictly increasing distribution function $F_i(.)$over the interval $[0,\infty )$. In the class of mechanisms $\mu =(d,\tau ) \in \Gamma$satisfying SP and IR, there exists no mechanism that is optimal.¹⁵

Proof

Suppose an optimal mechanism exists and has threshold functions $\left( {T^*_1}^\mu (.),{T^*_2}^\mu (.) \right) \in {\mathcal {F}}$. For simplicity of notation, let $\theta _y:= {T_1^*}^\mu (y)$ and $\beta _y:= {T^*_2}^\mu (y)$ for all $y\ge 0$. Note that by Result 1, the exact functional form of $K_i^\mu (.)$ functions does not affect the strategyproofness of mechanisms. Further, using Result 1 we can infer that for any mechanism satisfying IR, the $K^\mu _i(.)$ functions must have a range in ${\mathbb {R}}_+$. Therefore, an optimal mechanism must set ${K_i^*}^\mu (.) =0$ for all i. Also, Result 1 implies that for all possible y values, $\theta _y=inf\{x\ge 0 | d(x,y)=(1,0)\}$ and $\beta _y=inf\{x\ge 0 | d(y,x)=(0,1)\}$.

Therefore, by Lemma 1, the seller’s expected revenue from the optimal mechanism is

$$\begin{aligned} V(\theta ,\beta ):=\int _0^\infty \left\{ \theta _{x_2}(1-F_1(\theta _{x_2})) + \int _{0}^{\theta _{x_2}} \beta _{x_1} f_1(x_1) dx_1\right\} f_2(x_2) dx_2. \end{aligned}$$

By Euler’s equation (for calculus of variation), a necessary condition that $(\theta$ and $\beta$ must satisfy to maximize the aforesaid expression is

$$\begin{aligned} \frac{\delta \left[ \left\{ \theta _{x_2}(1-F_1(\theta _{x_2})) + \int _{0}^{\theta _{x_2}} \beta _{x_1} f_1(x_1) dx_1\right\} f_2(x_2) \right] }{\delta \theta _{x_2}} = 0, \end{aligned}$$

which implies that

$$\begin{aligned} \theta _{x_2}=\beta _{\theta _{x_2}} + \frac{1-F_1(\theta _{x_2})}{f_1(\theta _{x_2})}, \forall \, x_2\ge 0. \end{aligned}$$

Now, by condition (3) of Theorem 1, $\beta _{\theta _{x_2}} = {T_2^*}^\mu \left( {T_1^*}^\mu (\theta _{x_2})\right) = x_2$, and so the equation above reduces to

$$\begin{aligned} \theta _{x_2}=x_2 + \frac{1-F_1(\theta _{x_2})}{f_1(\theta _{x_2})}, \forall \, x_2\ge 0. \end{aligned}$$

However, Theorem 1 requires that $\theta _0=0$ and so, it must be that $0=\frac{1-F_1(0)}{f_1(0)}$ which implies that $f_1(0) =\infty$, which is a contradiction to the definition of derivative. $\square$

Note that the impossibility in Theorem 4 reflects a standard fact of calculus of variations where extremal of a functional that does not depend on the slope of feasible functions fails to exist if the feasible functions are required to satisfy boundary conditions.¹⁶ Therefore, one may hope to find existence of optimal mechanisms if zero valuations are excluded from the domain. We leave this as a future exercise as removing possibility of zero valuations would render our proof of Corollary 2 incorrect.

Remark 3

Myerson (1981), Theorem 4 looks at optimal mechanisms that are truthful in the sense of dominant strategy incentive compatibility. It shows that the candidates for optimal strategyproof mechanisms satisfying individual rationality must be those not belonging to $\Gamma$. That is, such mechanisms may be discontinuous or may allow the object to be allocated dictatorially at some profile of reported valuations. Note that this impossibility may also be a result of the restriction implicit in present setting, which requires that the object must be allocated at all profiles. This rules out usage of reserve prices that were shown by Myerson (1981) to be essential components of the optimal strategyproof and individually rational mechanism. Are there any optimal strategyproof mechanisms satisfying some form of individual rationality, if objects are not allocated at all profiles? This appears to be an interesting area of future research.

4 Conclusion

We study group strategyproofness and optimality of mechanisms for a two agent indivisible object allocation problem. We only consider well-behaved mechanisms that satisfy agent sovereignty and a mild continuity condition. We characterize the class of strategyproof mechanisms and show presence of non-affine maximizer strategyproof mechanisms outside the class characterized by Roberts (1979). We obtain impossibilities for the presence of strong group strategyproof mechanisms, as well as for the presence of budget balanced strategyproof mechanisms. However, we find that there exists a large class of weak group strategyproof mechanisms. We also completely characterize the class of feasible strategyproof mechanisms satisfying individual rationality. Finally, we show that there does not exist an expected revenue maximizing strategyproof mechanism satisfying individual rationality, under a large class of distributions of types.

Extension of these results to general n player setting is a difficult exercise as the dimension of the domain of threshold $T_i(.)$ functions (of Result 1) becomes greater than one. This line of inquiry is left for future research.

Appendix

1.1 Proof of Theorem 1

We first prove the following lemma that establishes two particular properties of $T^\mu _i(.)$ functions for any strategyproof mechanism $\mu \in \Gamma$.

Lemma 1

If a mechanism $\mu =(d,\tau ) \in \Gamma$ satisfies SP, then

• (1) For all $i\in N$, $T_i^\mu (.)$is a non-decreasing continuous function.

• (2) For all $x,y \ge 0$, $x=T^{\mu }_1(y) \Longleftrightarrow y=T^{\mu }_2(x)$.

Proof

To prove (1), fix $y,y'$ such that $0\le y<y'$. If $T^\mu _1(y')<T^\mu _1(y)$, then for any $x \in (T^\mu _1(y'), T^\mu _1(y))$ consider the profiles (x, y) and $(x,y')$. By Result 1 and non-decreasingness of $T_i^\mu (.)$ functions, $d_2(x,y')=0$ and $d_2(x,y)=1$, which contradict Result 1 itself. Arguing similarly for agent 2, we get that $T_i^{\mu }(.)$ is a non-decreasing function for both $i\in N$. Therefore, these functions must either be continuous or have jump discontinuities. Without loss of generality, consider the function $T_1^\mu (.)$ and suppose that there exists a $y\ge 0$ such that $T^\mu _1(y) < \lim _{z \rightarrow y+} T^\mu _1(y)$. Fix an $x \in \left( T^\mu _1(y) , \lim _{z \rightarrow y+} T^\mu _1(y) \right)$ and consider the sequence of profiles $\{(x,y^r)\}$ such that for all r, $y^r>y$ and $\{y^r\} \rightarrow y$. By Result 1, $d(x,y^r)=(0,1)$ for all r, but $d(x,y)=(1,0)$. Since, $\mu \in \Gamma$ and hence, continuous, we have $u((1, \tau _1(x,y));x) = u((0, \tau _1(x,y));x)$, which implies that $x=T^\mu _1(y)$. This contradicts our choice of x and so, $T_i^\mu (.)$ functions must be continuous. Thus, condition (1) follows.

To prove (2), fix any $x,y\ge 0$. There are two possibilities: (i) $d_1(x,y)=1$ or (ii) $d_2(x,y)=1$. If case (i) holds, then by Result 1, $x\ge T^{\mu }_1(y)$ and $y\le T^{\mu }_2(x)$. If $x>T^{\mu }_1(y)$ and $y=T^{\mu }_2(x)$, then choose $\nu >0$ such that $x>T^{\mu }_1(y+\nu )$ (by condition (1) established above, such a $\nu$ exists). By Result 1, $d_1(x,y+\nu )=d_2(x,y+\nu )=1$ and hence, a contradiction. Similarly, if $x=T^{\mu }_1(y)$ and $y<T^{\mu }_2(x)$, then choose $\nu >0$ such that $y<T^{\mu }_2(x-\nu )$. As before, Result 1 implies that $d_1(x-\nu ,y)=d_2(x-\nu ,y)=0$ and hence, a contradiction. Arguing in similar manner, we can establish a contradiction in case (ii), and so, the result follows. $\square$

Using Lemma 1 above, we present the following proofs of necessity and sufficiency:

${{\texttt {\textit{Only If:}}}}$

Fix any mechanism $\mu =(d,\tau ) \in \Gamma$ that satisfies SP. Result 1 and Lemma 1 imply the conditions (2) and (3) trivially. Further, condition (3) implies that $T^{{\mu }^{-1}}_i(.)$ functions must be well defined for all i, and so, by Lemma 1, $T_i^\mu (.)$ functions must be strictly increasing. Thus, condition (4) follows, and so, by Result 1, condition (1) follows. Finally, if $T^\mu _1(0)>0$, then by conditions (3) and (4), $T_1^\mu ( T^\mu _2(0))> T_1^\mu (0) \implies 0>T_1^\mu (0)$ which implies that there exists $\nu >0$ such that $0>T^\mu _2(\nu )$ which contradicts Result 1. Arguing similarly for $T^\mu _2(.)$, condition (5) follows.

${{\texttt {\textit{If:}}}}$

Consider any mechanism $\mu = (d,\tau )$ that satisfies the conditions (1)–(5) stated in the theorem. By Result 1, $\mu$ satisfies SP.¹⁷. Also, since $T_i^\mu (x) \in [0,\infty ), \forall \, x\ge 0, \forall \, i$, $\mu$ satisfies AS. To show continuity, consider, without loss of generality, a sequence of profiles $\{v^r\}$ converging to ${\bar{v}}$ such that the allocation decisions are $d(v^r)=(1,0)$ for all r. Therefore, by Result 1, $v^r_1 \ge T^\mu _1(v^r_2)$ and $v^r_2\le T^\mu _2(v^r_1)$ for all r. By condition (4), in limit ${\bar{v}}_1 \ge T^\mu _1({\bar{v}}_2)$ and ${\bar{v}}_2\le T^\mu _2({\bar{v}}_1)$. Now, if the allocation decisions are not preserved in limit, that is, $d({\bar{v}})=(0,1)$; then ${\bar{v}}_1=T^\mu _1({\bar{v}}_2)$ and ${\bar{v}}_2=T^\mu _2({\bar{v}}_1)$, which implies that for both $j\in N$, $u(0,\tau _j({\bar{v}});{\bar{v}}_j)=u(1,\tau _j({\bar{v}});{\bar{v}}_j) = K_j^\mu (v_i)$, where $i \ne j$. Hence, continuity of $\mu$ follows and so, we can infer that $\mu \in \Gamma$. $\square$

1.2 Proof of Theorem 2

There can be only two types of deviations by the pair $\{1,2\}$: (1) decision-preserving deviations where the allocation decision remains same before and after deviation and (2) decision-changing deviations where the allocation decision changes after deviation. Note that for all $i\in N$ and all $z \ge 0$, if $\eta =0$, then $K^\mu _i(z)=C_i$; and if $\eta =\infty$ then $K^\mu _i(z)=C_i + T^\mu _i(z)$. Now if $\eta =0$, it is easy to see that at any original type profile $v=(v_1,v_2)$, no possible misreport that any agent $j\in N$ can make, would affect the $K^\mu _i(.)$ value for the other agent $i\ne j$. So, any $\{1,2\}$ deviation $v'$ that violates WPGS must be decision changing. However, given that $K^\mu _i(.)$ functions are constant functions for both i when $\eta =0$, the winner at v would become strictly worse off by becoming loser at $v'$, which contradicts our supposed violation of WPGS. Further, if $\eta =\infty$, any decision preserving $\{1,2\}$ deviation would leave the winner’s utility unchanged, and so, any such deviation that violates WPGS must be decision changing. Now, when $\eta =\infty$, for any decision changing $\{1,2\}$ deviation from v to $v'$, the utility of w(v) at profile v (that is, $v_{w(v)} + C_{w(v)})$ is, less than her utility at $v'$ (that is, $C_{w(v)}$); which implies that no such $\{1,2\}$ deviation can violate WPGS.

Now, we focus on mechanisms with a finite and positive $\eta \in (0, \infty )$, and show the sufficiency with respect to each possible kind of deviation as a separate case. First, we define for all possible $\{1,2\}$ deviations from the original valuation profile (x, y) to a misreported valuation profile $(x',y')$;

$$\begin{aligned} \Delta _1:= u_1(d_1(x,y), \tau _1(x,y);x)- u_1(d_1(x',y'),\tau _1(x',y');x), \end{aligned}$$

and

$$\begin{aligned} \Delta _2:= u_2(d_2(x,y),\tau _2(x,y);y)- u_2(d_2(x',y'),\tau _2(x',y');y). \end{aligned}$$

Case(i) Decision preserving Suppose there exists a decision preserving deviation from (x, y) to $(x',y')$ that violates WPGS, that is, $\Delta _i <0$ for both i. Consider the possibility where $d(x,y)=d(x',y')=(1,0)$, that is, $\min \{x,x'\} \ge \max \{T^\mu _1(y),T^\mu _1(y')\}$ and $\max \{y,y'\} \le \min \{T_2^\mu (x),T_2^\mu (x')\}$. Note that given the structure of $K_i^\mu (.)$ functions, $\Delta _2 <0$ is possible only if $x <x'$, and $T_2^\mu (x) < \eta$. Similarly, $\Delta _1 <0$ is possible only if $y' <y$, and $\eta <T_1^\mu (y)$. Therefore, under this possibility of violation of WPGS, we can infer that $\mathbf {(I)}\;\; 0\le y' \le y\le T^\mu _2(x)<\eta <T^\mu _1(y) \le x \le x'$. However, by condition (4) of Theorem 1 and construction of $\eta$ such that $T^\mu _i(\eta )=\eta$ for all $i\in N$; we get that

$$\begin{aligned} \left\{ T^\mu _2(x)<\eta<T^\mu _1(y)\right\} \implies x<\eta < y, \end{aligned}$$

and hence, a contradiction to (I).

Arguing in a similar manner for the possibility where $d(x,y)=d(x',y')=(0,1)$, we get that $({{\mathbf {I}}}{{\mathbf {I}}})\;\; 0\le x' \le x< T^\mu _1(y)<\eta <T^\mu _2(x) \le y \le y'$. As before, by Theorem 1 and construction of $\eta$, we get that $y<\eta <x$, which contradicts (II). Therefore, we conclude that there can be no decision preserving $\{1,2\}$-deviation that violates WPGS when $\eta \in (0,\infty )$.

Case(ii) Decision changing Suppose there exists a decision changing deviation from (x, y) to $(x',y')$ that violates WPGS, that is, $\Delta _i<0$ for all $i\in N$. Without loss of generality, suppose that $d(x,y)=(1,0)$ and $d(x', y')=1$. Now, if $\Delta _1 = x+K^\mu _1(y) - T^\mu _1(y) - K^\mu _1(y') <0$, then by Result 1, $y'>y$, $T^\mu _1(y)<\eta$ and $x<\eta$. By Theorem 1 and construction of $\eta$,

$$\begin{aligned} x< \eta \implies \left\{ T^\mu _2(x)<T^\mu _2(\eta )=\eta \right\} , \end{aligned}$$

and so, $K^\mu _2(x)= T^\mu _2(x)+C_2$.

Now, if $x' \le \eta$, then by the same logic, $K^\mu _2(x')= T^\mu _2(x')+C_2$, which implies that $\Delta _2 = K^\mu _2(x) - \{y+K^\mu _2(x') - T^\mu _2(x')\} = T_2^\mu (x) - y$. Now, by supposition $d_2(x,y)=0$, and so, $y \ge T_2^\mu (x)$ implying that $\Delta _2 \ge 0$, which contradicts our supposition. On the contrary, if $x'>\eta$, then arguing as before, $T^\mu _2(x')>\eta$ and so $K^\mu _2(x')=\eta +C_2$. Therefore, by Result 1, $\Delta _2=(T^\mu _2(x)-y)+(T^\mu _2(x') - \eta ) > 0$ and so, a contradiction to our supposition. Thus, there can be no decision changing $\{1,2\}$-deviation that can violates WPGS when $\eta \in (0,\infty )$. $\square$