1 Introduction
We investigate the following basic setting of asymmetric information, which appears in various forms in the theory of incentives. There are a single agent and a principal. The agent holds private information t from some set T. We call t the type of the agent, and T the type set. Depending on the agent’s type the principal wants to select an allocation, or take an action, a from some set A. We call the function \(f : T \rightarrow A\) which determines this selection the allocation rule. We allow for monetary transfers given by a payment function \(p : T \rightarrow \mathbb {R}\) which the principal uses in order to orchestrate incentives. The agent has cardinal preferences for allocations parameterized by his type, given by a valuation function
\(v: A \times T \rightarrow \mathbb {R}\), and quasi-linear utility for allocations and payments. We will call the triple (T, A, v) an environment. Such environments occur as building blocks in numerous applications in the theory of incentives. In particular they have been studied in the context of mechanism design.
We assume that the agent and the principal interact by a revelation mechanism in which the agent announces a type
t, which may be different from his true type
s, and the principal allocates
f(
t) and makes transfer
p(
t), yielding utility
\(v(f(t),s) + p(t)\) for the agent. We call
f
implementable if there exists a
p that makes truthful reports of the agent a weakly dominant strategy, that is, for all
s,
t in
T:
$$\begin{aligned} v(f(s),s)+p(s) \ge v(f(t),s) + p(t). \end{aligned}$$
(1)
Central questions in the theory of incentives are (1) a characterization of all implementable allocation rules
f, (2) ways to construct payments
p, and (3) conditions on when
p is unique up to a constant. The latter property is called
revenue equivalence due to its applications in auctions.
In this paper we provide answers to these questions for the case when
T is a convex subset of
\(\mathbb {R}^d\). Our first result shows that an allocation rule is implementable if and only if it is implementable on every 2-dimensional subset of
T. Let us call a rule
f line-implementable if it is implementable when restricted to any line-segment on
T, and locally implementable if for every type
t there exists some open neighborhood of
t on which it is implementable. Our second result states for the same setting as above that a rule is implementable if and only if it is locally implementable and line implementable. Both results do not require any assumptions on the valuation functions
v or the cardinality of
A. We only need convexity of
T and that the allocation rule in question, if line-implementable, satisfies revenue equivalence on lines. We then restrict to valuation functions that are continuous in types. For such settings, we strengthen the second result by showing that an allocation rule with a finite range is implementable if and only if it is line implementable. The last result generalizes a well-known theorem by Saks and Yu (
2005), and yields as well a new, very easy proof of the original result.
All results are achieved by using directed graphs whose node sets consist of the set of types, and which have arcs between any two types
s and
t with length equal to value differences (more precisely, the length of arc (
s,
t) equals the value difference for the outcome at
t if an agent is of type
t versus of type
s). Non-existence of cycles with negative lengths, called
cycle monotonicity determines whether a rule is implementable, in which case shortest paths lengths yield incentive compatible payments. Also, it is a property on path lengths that determines whether a rule satisfies revenue equivalence. This approach goes back to Rochet (
1987). It has been put into graph theoretic terms by Gui et al. (
2004) and Heydenreich et al. (
2009), and fully refined in the monograph of Vohra (
2011). Non-existence of negative cycles of two nodes, called 2-cycle monotonicity is a direct generalization of monotonicity of allocation rules in single-item auctions. This triggered a serious of results showing that for particular multi-dimensional environments 2-cycle monotonicity implies cycle-monotonicity. All these results require
v to be linear in
T, in which case 2-cycle monotonicity coincides with line-implementability. Our results show that replacing 2-cycle monotonicity by line-implementability provides the right means to extend these results beyond the case of linear valuations. By way of an example we show that line-implementability is a strictly stronger condition than 2-cycle monotonicity.
The definition of an environment used here assumes a single agent, while mechanism design deals typically with more than one agent. This is not limiting the applicability of our results as our definition can be used to grasp the perspective of each individual agent in a mechanism design context. For example, if we are interested in dominant strategy implementable allocation rules f, we get an environment for each select agent and for each possible type report of all other agents. The allocation rule describes the influence of the selected agent’s type reports, given the reports of other agents. Similar does the payment rule determine his payment for outcomes, given the report of the other agents. If we are interested in Bayesian Nash Implementation, the allocation rule maps types of a selected agent to a distribution of outcomes, induced by the distribution of truthful type reports of other agents.
Related work Characterizing settings where 2-cycle monotonicity is sufficient for cycle monotonicity has been a prominent topic in mechanism design (Archer and Kleinberg
2014; Ashlagi et al.
2010; Bikhchandani et al.
2006; Carbajal and Müller
2015; Mishra et al.
2013; Saks and Yu
2005). Common to this literature is a representation of an environment that differs from ours. We shall call it a
domain representation, as opposed to our
parameter representation. A domain representation associates every type with a function
\(\tau \), mapping outcomes to values. A domain is a set of such functions. Both representations are closely linked since domains can be considered as type sets in parameter representations with
\(v(\tau ,a) = \tau (a)\), implying that
v is in fact a linear function in types. Vice versa, parameter representations induce a domain
\(\{v(.,t)\ |\ t \in T\}\). However, convex sets of types in parameter representations do not necessarily induce convex domains. In fact, our results strictly extend work on domain representations whenever the induced domain representation is not convex. We provide an example in Sect.
4. Also, the type set
T in a parameter representation might be finite-dimensional while
A is infinite, in which case the previous literature is silent as well. For finite
A, a parametrization by types may allow for a low-dimensional compact representation of private information, contrary to a high-dimensional corresponding domain. Think for example of additive valuations in multi-item auctions, where a type represents a value for each of the
m items, allowing for types of dimension
m, while the corresponding domain has dimension
\(2^{m}-1\).
Within the framework of parameter representations, a different strand of mechanism design literature deals with explicit representations of payments in terms of path integrals of a particular vector field, yielding generalizations of the Mirrlees representation of indirect utility (Mirrlees
1971). For valuation functions that are differentiable in types Milgrom and Segal (
2002) show that such representations follow from the envelope theorem. Krishna and Maenner (
2001) prove a similar representation to hold for convex valuation functions. Mirrlees’ representation can as well be used for characterizing implementable allocation rules. For example, Jehiel et al. (
1999) and Jehiel and Moldovanu (
2001) derive characterizations for auction environments with linear valuation functions. They show that existence and path-independence of certain integrals provides necessary and sufficient conditions for implementation. This approach has been simplified by Archer and Kleinberg (
2014). They show that for convex type set
T and linear valuation functions monotonicity on line-segments and path-independence of path-integrals along the border of triangles are sufficient for implementability. Furthermore, they show that any rule that is locally implementable, is implementable on all of
T. Berger et al. (
2009) extend the results of Archer and Kleinberg (
2014) to convex valuation functions. We show that neither linearity nor convexity of valuation functions is needed to yield such characterizations, if one replaces the Mirrless representation of indirect utility by distances along line-segments in directed graphs. All what is needed is revenue equivalence on lines and convexity of the type set. Thereby, we significantly extend the approach by Archer and Kleinberg (
2014) and Berger et al. (
2009).
A different generalization of the characterization literature based on Mirrlees representations has been proposed by Carbajal and Ely (
2013). They show how for settings without revenue equivalence a weaker form of Mirrlees representation can be achieved by integration of correspondences. We elaborate on this work in Sect.
3. Carroll (
2012) has investigated the role of local implementability as well. He shows that every locally incentive compatible mechanism is incentive compatible if the type space is convex. In related work, Mishra et al. (
2015) give a different characterization for ordinal type spaces that includes
payment-only incentive compatibility as an additional necessary and sufficient condition. While Caroll as well as Mishra et al. derive characterizations in terms of local properties of an allocation rule
and a payment rule, our results, as those of Archer and Kleinberg (
2014) and Berger et al. (
2009), yield characterizations in terms of local properties of just the allocation rule. At the same time, the results by Carroll and Mishra et al. are more general as they cover ordinal as well as polyhedral type spaces.
Organization In Sect.
2, we define our setting and introduce necessary notation and previous results. We present our main characterization of implementability (Theorem
3) in Sect.
3.1. Then we provide extensions of the results of Archer and Kleinberg (
2014) about local implementability (Theorem
4, Sect.
3.2) and of Saks and Yu (
2005) for allocation rules with finite range (Theorem
5, Sect.
3.3). In Sect.
4 we apply our results to an example given in Vohra (
2011).
2 Incentive compatibility, cycle monotonicity and 2-cycle monotonicity
In this section we provide precise definitions and recall the network approach for our basic model. We consider environments (T, A, v), where T is a set of types, A is a set of allocations, and \(v: A \times T \rightarrow \mathbb {R}\) is a valuation function. We assume quasi linear utilities, so the utility of an agent of type \(t\in T\) for some outcome \(a\in A\) and payment \(\pi \) is equal to \(v(a,t)+\pi \).
It is straightforward to see that adding a constant to a payment rule p of an IC mechanism yields again an IC mechanism. If payment rules are unique up to such modifications, we say that revenue equivalence holds:
Rochet (
1987) identified a property called
cycle monotonicity that characterizes implementable allocation rules. It has later been related to node potentials in
type graphs by Gui et al. (
2004). Here, and further on, a graph consists of a set of
nodes and a set of (directed)
arcs between pairs of nodes.
Given an allocation rule
f, the set of nodes of the type graph
\(T_f\) is equal to
T. Every pair of types
\(s,t\in T\) is connected by arcs from
s to
t and from
t to
s. We define arc lengths
\(l_u(s,t)\) for arcs of
\(T_f\) as follows (and call them
u-length between types
\(s,t \in T\)):
A path from node
s to node
t in
\(T_f\), or (
s,
t)-path for short, is defined as
\(P = (s = s_0,s_1,\ldots , s_k = t)\) such that
\(s_i\in T\) for
\(i = 0,\ldots ,k\). The
u-length of
P is defined as
A cycle is a path with
\(s = t\). For any
t, we regard the path from
t to
t without any arcs as a (
t,
t)-path and define its length to be 0. Let
P(
s,
t) be the set of all (
s,
t)-paths. The
u-distance from
s to
t is defined as
A
node potential
\(\pi \) with respect to
u-length is a function
\(\pi : T \rightarrow \mathbb {R}\) such that for all
\(s,t \in T\) we have
By the definition of
u-length, implementability of an allocation rule
f is equivalent with the existence of node potentials with respect to
u-length. Thereby, for all
t, potential
\(\pi (t)\) equals the net utility
\(v(f(t),t) + p(t)\) with respect to some incentive compatible payment rule
p. Furthermore, revenue equivalence coincides with uniqueness of node potentials with respect to
u-lengths up to a constant.
It is straightforward that if \(T_f\) has a node potential it cannot have a negative cycle. The opposite holds as well, as in the absence of negative cycles we can fix a type s and take distances from s to any type t to yield the node potential \(\pi (t) := \text{ dist }_u(s,t)\). This motivates Rochet’s definition of cycle monotonicity and yields his characterization of implementability.
For later reference we state Rochet’s theorem in terms of distances and combine it with a relation between distances and payment differences that is straightforward to prove.
Finally, a characterization of revenue equivalence due to Heydenreich et al. (
2009) is a direct consequence of what has been said so far:
Combining Theorem
2 and Corollary
1 yields the following.
3 Characterizing implementability on convex type sets
In this section we consider environments (
T,
A,
v), where
T is a convex subset of
\(\mathbb {R}^d\) (
\(d\ge 1)\),
A is an arbitrary set, and
\(v: A \times T \rightarrow \mathbb {R}\) is a valuation function. We start by introducing the notion of line-implementability: when restricting the input of the allocation rule to any line segment in
T, it is implementable. We show how line-implementability can be used to characterize implementability. Next we show that every allocation rule that is locally implementable is globally implementable. Both results need the additional assumption that line-implementable allocation rules satisfy revenue equivalence on these line segments. We explain at the end of this section, how this revenue equivalence assumption can be omitted and thereby relate our results to Carbajal and Ely (
2013).
Finally, we turn to valuation functions that are continuous in types and prove that any allocation rule that is line-implementable and has finite range is globally implementable. In such settings, the revenue equivalence assumption can be made without loss of generality (Chung and Olszewski
2007; Heydenreich et al.
2009).
3.1 Line-implementability
We denote by
\(L_{s,t}\) the line segment between
s and
t in
T:
Obviously, every implementable allocation rule is line-implementable. Furthermore every line-implementable allocation rule is 2-cycle monotone. It is well-known that for linear valuation functions 2-cycle monotonicity and line-implementability are equivalent. The following example shows that for convex, but non-linear valuation functions, 2-cycle monotonicity is not sufficient for line-implementability, even if they are piecewise linear.
Archer and Kleinberg (
2014) prove that for convex type spaces and linear valuation functions, 2-cycle monotonicity of an allocation rule together with path-independence on triangles of particular integrals defined by
f is equivalent with implementability. Example
1 shows that this equivalence cannot hold for arbitrary valuations. Still, we can show that the same principle, as well as its consequences, applies if we replace 2-cycle monotonicity by line-implementability. Thereby, we do not even need integrals, but can fully rely on distances in the type graph. To do so, we need to define distances on lines.
Using these definitions we get the following theorem.
A few remarks about the conditions in the above theorem are at place.
We close this section by a corollary of Theorem
3, which extends a result by Vohra (
2011, Theorem 4.2.11), who has proven it for randomized allocation rules over finitely many outcomes.
3.2 Local implementability
Archer and Kleinberg (
2014) were the first ones who characterized implementability based on local implementabilty. Their proof requires valuation functions to be linear. Motivated by their results we introduce in this section the notion of local implementability and extend their results to general valuation functions. The characterization holds for any outcome space and any valuation function, except that we will need revenue equivalence on lines.
Obviously, implementability guarantees local implementability. To prove the other direction we need the following lemma.
In the following we denote for \(s_1,s_2,s_3\in T\), all three distinct, by \(\blacktriangle _{s_1,s_2,s_3}\) the convex hull of \({s_1,s_2,s_3}\) and by \(\vartriangle _{s_1,s_2,s_3}\) the path describing the boundary of \(\blacktriangle _{s_1,s_2,s_3}\), i.e \( L_{s_1,s_2} \cup L_{s_2,s_3} \cup L_{s_3,s_1}\), with direction \(s_1\rightarrow s_2\rightarrow s_3\rightarrow s_1\).
Now we are prepared to prove the main theorem of this section.
3.3 Finite outcome space and continuous valuations
We prove in this section a generalization of the Theorem of Saks and Yu. We make use of a lemma that is of interest by its own as it describes a fairly general setting for which 2-cycle monotonicity is sufficient for implementability. Ashlagi et al. (
2010) have proven a similar lemma for linear valuations and finite set of outcomes. We show that the result holds in a much more general case. To make it work, we have to make the assumption that valuation functions
v(
a, .) are continuous in
t for all
\(a \in A\).
Now we simplify Theorem
3 in case of allocation rules
f with a finite range, which yields a generalization of the result by Saks and Yu (
2005) and by Archer and Kleinberg for environments with linear valuation functions. The theorem simplifies identifying the implementability of an allocation rule
f to verifying whether
f is implementable on any one dimensional subset of
T.
Note that in the above theorem we cannot replace line-implementability by the weaker condition 2-cycle monotonicity, despite the fact that 2-cycle monotonicity is all we need to apply Lemma
2. This follows from Example
1.
4 Example
In this section we illustrate by example how our results can be used to identify a large class of allocation rules on an environment with a convex type set but non-convex domain for which 2-cycle monotonicity is sufficient for implementability.
The example is based on Vohra (
2011, Example 4, p. 48). Vohra provides in this example a non-convex domain, in which each deterministic and 2-cycle monotone allocation rule is implementable. We extend this result by providing a class of randomized allocation rules with the same property. We model his setting as an environment with convex type set and convex valuation functions. Applying Theorem
5 yields that line-implementability is sufficient for implementability. Proving the increasing difference property of the valuation functions gives us line-implementability from 2-cycle monotonicity (see Remark
2).
We consider a set of outcomes
\(A=\{a,b,ab\}\) and the set of all lotteries over outcomes in
A, that is
\(Z(A)=\{(p_a,p_b,p_{ab}): p_a+p_b+p_{ab}=1, p_a,p_b,p_{ab} \ge 0\}\). The type set is
\(T=[0,1]^2\) and the valuations for a type
\((t_1,t_2)\in T\) are given by
$$\begin{aligned} v(a,(t_1,t_2))&= t_1\\ v(b,(t_1,t_2))&= t_2\\ v(ab,(t_1,t_2))&= \max \{t_1,t_2\}.\\ \end{aligned}$$
These are linearly extended to outcomes in
Z(
A). The domain arising from this environment (as a subset of
\(\mathbb {R}^3\)) is not convex. Moreover, its projection onto the hyperplane
\(\{x \in \mathbb {R}^3\ |\ t_a + t_b +t_{ab} = 1\}\) is also not convex. Therefore, by a result of (Ashlagi et al.
2010), there are randomized allocation rules on this domain which are 2-cycle monotone but not implementable.
However, as Proposition
1 below shows, there is a large class of randomized allocation rules for which 2-cycle monotonicity implies implementability.